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.
arXiv comment19 pages, 1 figure
References in corpus (45)
- Anyons in an exactly solved model and beyond
- Predicting Many Properties of a Quantum System from Very Few Measurements
- Logical quantum processor based on reconfigurable atom arrays
- Matrix Product States and Projected Entangled Pair States: Concepts, Symmetries, and Theorems
- Efficient quantum state tomography
- Quantum certification and benchmarking
- Classical simulation of noninteracting-fermion quantum circuits
- Improved classical simulation of quantum circuits dominated by Clifford gates
- The computational complexity of PEPS
- Simulation of quantum circuits by low-rank stabilizer decompositions
- Computational Complexity of interacting electrons and fundamental limitations of Density Functional Theory
- Efficient tomography of a quantum many-body system
- Matchgates and classical simulation of quantum circuits
- Quantum Hypergraph States
- Sample-optimal tomography of quantum states
- Fermionic partial tomography via classical shadows
- Theory of quantum system certification: a tutorial
- A mathematical and computational review of Hartree-Fock SCF methods in Quantum Chemistry
- Measuring magic on a quantum processor
- Fermionic Gaussian states: an introduction to numerical approaches
- 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
- Matchgate Shadows for Fermionic Quantum Simulation
- Efficient and feasible state tomography of quantum many-body systems
- Efficient tensor network simulation of IBM's largest quantum processors
- The computational difficulty of finding MPS ground states
- Fidelity witnesses for fermionic quantum simulations
- Learning t-doped stabilizer states
- Learning efficient decoders for quasi-chaotic quantum scramblers
- Computational Difficulty of Global Variations in the Density Matrix Renormalization Group
- Pseudo-dimension of quantum circuits
- Unscrambling Quantum Information with Clifford decoders
- A single -gate makes distribution learning hard
- Bell sampling from quantum circuits
- Learning quantum many-body systems from a few copies
- Local optimization on pure Gaussian state manifolds
- Fermionic correlation functions from randomized measurements in programmable atomic quantum devices
- 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
- Clifford Circuits can be Properly PAC Learned if and only if
- Gaussian decomposition of magic states for matchgate computations
- Learning finitely correlated states: stability of the spectral reconstruction