Learning finitely correlated states: stability of the spectral reconstruction

• URL: http://arxiv.org/abs/2312.07516v2
• Date: Thu, 2 May 2024 17:20:02 GMT
• Title: Learning finitely correlated states: stability of the spectral reconstruction
• Authors: Marco Fanizza, Niklas Galke, Josep Lumbreras, Cambyse Rouzé, Andreas Winter,
• Abstract summary: We show that marginals of blocks of $t$ systems of any finitely correlated translation invariant state on a chain can be learned, in trace distance, with $O(t2)$ copies. The algorithm requires only the estimation of a marginal of a controlled size, in the worst case bounded by the minimum bond dimension.
• Score: 1.9573380763700716
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We show that marginals of blocks of $t$ systems of any finitely correlated translation invariant state on a chain can be learned, in trace distance, with $O(t^2)$ copies -- with an explicit dependence on local dimension, memory dimension and spectral properties of a certain map constructed from the state -- and computational complexity polynomial in $t$. The algorithm requires only the estimation of a marginal of a controlled size, in the worst case bounded by the minimum bond dimension, from which it reconstructs a translation invariant matrix product operator. In the analysis, a central role is played by the theory of operator systems. A refined error bound can be proven for $C^*$-finitely correlated states, which have an operational interpretation in terms of sequential quantum channels applied to the memory system. We can also obtain an analogous error bound for a class of matrix product density operators reconstructible by local marginals. In this case, a linear number of marginals must be estimated, obtaining a sample complexity of $\tilde{O}(t^3)$. The learning algorithm also works for states that are only close to a finitely correlated state, with the potential of providing competitive algorithms for other interesting families of states.

Related papers

• Transfer Operators from Batches of Unpaired Points via Entropic Transport Kernels [3.099885205621181]
  We derive a maximum-likelihood inference functional, propose a computationally tractable approximation and analyze their properties. We prove a $Gamma$-convergence result showing that we can recover the true density from empirical approximations as the number $N$ of blocks goes to infinity.
  arXiv  Detail & Related papers  (2024-02-13T12:52:41Z)
• Classifying fermionic states via many-body correlation measures [0.0]
  We make progress in establishing the link between fermionic correlations and efficient computational physics methods. We find a rigorous classification of states relative to $k$-fermion correlations, which admits a computational physics interpretation.
  arXiv  Detail & Related papers  (2023-09-14T18:00:02Z)
• Nonlocality under Computational Assumptions [51.020610614131186]
  A set of correlations is said to be nonlocal if it cannot be reproduced by spacelike-separated parties sharing randomness and performing local operations. We show that there exist (efficient) local producing measurements that cannot be reproduced through randomness and quantum-time computation.
  arXiv  Detail & Related papers  (2023-03-03T16:53:30Z)
• Learning Transition Operators From Sparse Space-Time Samples [11.859913430860335]
  We consider the nonlinear problem of learning a transition operator $mathbfA$ from partial observations at different times. We show that no more than $mathcalOrn log(nT)$ space-time samples are sufficient to ensure accurate recovery of a rank-$r$ operator.
  arXiv  Detail & Related papers  (2022-12-01T18:33:59Z)
• Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiency [111.83670279016599]
  We study reinforcement learning for partially observed decision processes (POMDPs) with infinite observation and state spaces. We make the first attempt at partial observability and function approximation for a class of POMDPs with a linear structure.
  arXiv  Detail & Related papers  (2022-04-20T21:15:38Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  We use kernel Hilbert spaces for estimating the value function of an infinite-horizon discounted Markov reward process. We derive a non-asymptotic upper bound on the error with explicit dependence on the eigenvalues of the associated kernel operator. We prove minimax lower bounds over sub-classes of MRPs.
  arXiv  Detail & Related papers  (2021-09-24T14:48:20Z)
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers [50.85524803885483]
  This work proposes a formal definition of statistically meaningful (SM) approximation which requires the approximating network to exhibit good statistical learnability. We study SM approximation for two function classes: circuits and Turing machines.
  arXiv  Detail & Related papers  (2021-07-28T04:28:55Z)
• An $L^2$ Analysis of Reinforcement Learning in High Dimensions with Kernel and Neural Network Approximation [9.088303226909277]
  This paper considers the situation where the function approximation is made using the kernel method or the two-layer neural network model. We establish an $tildeO(H3|mathcal A|frac14n-frac14)$ bound for the optimal policy with $Hn$ samples. Even though this result still requires a finite-sized action space, the error bound is independent of the dimensionality of the state space.
  arXiv  Detail & Related papers  (2021-04-15T21:59:03Z)
• Improved rates for prediction and identification of partially observed linear dynamical systems [4.68299658663016]
  Identification of a linear time-in dynamical system from partial observations is a fundamental problem in control theory. We propose an algorithm that learns such systems with non-asymptotic statistical rates depending on the inherentity $d$ of the system. Our algorithm is based on multi-scale low-rank approximation SVD applied to Hankel matrices of increasing sizes.
  arXiv  Detail & Related papers  (2020-11-19T18:04:18Z)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  We study the efficient learnability of high-dimensional Gaussian mixtures in the adversarial-robust setting. We provide an algorithm that learns the components of an $epsilon$-corrupted $k$-mixture within information theoretically near-optimal error proofs of $tildeO(epsilon)$. Our main technical contribution is a new robust identifiability proof clusters from a Gaussian mixture, which can be captured by the constant-degree Sum of Squares proof system.
  arXiv  Detail & Related papers  (2020-05-13T16:44:12Z)
• Quantum Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
  We give scalable, explicit digital quantum algorithms to simulate the lattice Schwinger model in both NISQ and fault-tolerant settings. In lattice units, we find a Schwinger model on $N/2$ physical sites with coupling constant $x-1/2$ and electric field cutoff $x-1/2Lambda$. We estimate observables which we cost in both the NISQ and fault-tolerant settings by assuming a simple target observable---the mean pair density.
  arXiv  Detail & Related papers  (2020-02-25T19:18:36Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.