PAC-learning of free-fermionic states is NP-hard
arXiv:2404.03585 · doi:10.22331/q-2025-03-20-1665
Abstract
Free-fermionic states, also known as matchgates or Gaussian states, are a fundamental class of quantum states due to their efficient classical simulability and their crucial role across various domains of Physics. With the advent of quantum devices, experiments now yield data from quantum states, including estimates of expectation values. We establish that deciding whether a given dataset, formed by a few Majorana correlation functions estimates, can be consistent with a free-fermionic state is an NP-complete problem. Our result also extends to datasets formed by estimates of Pauli expectation values. This is in stark contrast to the case of stabilizer states, where the analogous problem can be efficiently solved. Moreover, our results directly imply that free-fermionic states are computationally hard to properly PAC-learn, where PAC-learning of quantum states is a learning framework introduced by Aaronson. Remarkably, this is the first class of classically simulable quantum states shown to have this property.
19 pages, 1 figure
References in corpus (17)
- Logical quantum processor based on reconfigurable atom arrays
- Efficient quantum state tomography
- Matchgates and classical simulation of quantum circuits
- A mathematical and computational review of Hartree-Fock SCF methods in Quantum Chemistry
- Fast and converged classical simulations of evidence for the utility of quantum computing before fault tolerance
- Matrix product operators and states: NP-hardness and undecidability
- Efficient tensor network simulation of IBM's largest quantum processors
- The computational difficulty of finding MPS ground states
- Learning t-doped stabilizer states
- Bell sampling from quantum circuits
- Efficient learning of quantum states prepared with few fermionic non-Gaussian gates
- Learning fermionic correlations by evolving with random translationally invariant Hamiltonians
- On the NP-completeness of the Hartree-Fock method for translationally invariant systems
- Classical surrogate simulation of quantum systems with LOWESA
- A survey on the complexity of learning quantum states
- Gaussian decomposition of magic states for matchgate computations
- Learning finitely correlated states: stability of the spectral reconstruction