Free Fermion Distributions Are Hard to Learn
Reviewed by Pith T0 review T1 audit T2 compute T3 formal T4 kernel pith:KZH3L7Z4record.jsonopen to challenge →
read the original abstract
Free fermions are some of the best studied quantum systems. However, little is known about the complexity of learning free-fermion distributions. In this work we establish the hardness of this task in the particle number non-preserving case. In particular, we give an information theoretical hardness result for the general task of learning from expectation values and, in the more general case when the algorithm is given access to samples, we give a computational hardness result based on the LPN assumption for learning the probability density function.
This paper has not been read by Pith yet.
Forward citations
Cited by 1 Pith paper
-
On the Complexity of Quantum States and Circuits from the Orthogonal and Symplectic Groups
Random states from symplectic and orthogonal unitaries show exponentially large strong state complexity and near-orthogonality, with average-case hardness for learning circuits from these groups.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.