We give an efficient classical algorithm that recovers the distribution of a non-interacting fermion state over the computational basis. For a system of $n$ non-interacting fermions and $m$ modes, we show that $O(m^2 n^4 \log(m/\delta)/ \varepsilon^4)$ samples and $O(m^4 n^4 \log(m/\delta)/ \varepsilon^4)$ time are sufficient to learn the original distribution to total variation distance $\varepsilon$ with probability $1 - \delta$. Our algorithm empirically estimates the one- and two-mode correlations and uses them to reconstruct a succinct description of the entire distribution efficiently.
We give an efficient classical algorithm that recovers the distribution of a non-interacting fermion state over the computational basis. For a system of n non-interacting fermions and m modes, we show that O(m2n4log(m/δ)/ε4) samples and O(m4n4log(m/δ)/ε4) time are sufficient to learn the original distribution to total variation distance ε with probability 1−δ. Our algorithm empirically estimates the one- and two-mode correlations and uses them to reconstruct a succinct description of the entire distribution efficiently.
We give an efficient algorithm that learns a non-interacting-fermion state, given copies of the state. For a system of n non-interacting fermions and m modes, we show that O(m³ n² log(1/δ) / ε⁴) copies of the input state and O(m⁴ n² log(1/δ)/ ε⁴) time are sufficient to learn the state to trace distance at most ε with probability at least 1 - δ. Our algorithm empirically estimates one-mode correlations in O(m) different measurement bases and uses them to reconstruct a succinct description of the entire state efficiently.
We establish efficient learning for a family of fermionic magic states under unknown number-conserving free-fermion evolution. Each input block has a definite particle number and is a superposition of Fock states, with occupied mode sets disjoint both within and across blocks. The key idea is to exploit the spectral structure of particle reduced density matrices (RDMs) to separate contributions from individual blocks from those involving several blocks, allowing us to reconstruct the hidden block structure. For a fixed upper bound on the particle number per block, our algorithm uses single-copy measurements and polynomial sample and classical computational complexity to recover a compact description of the state with prescribed fidelity and high probability, without prior knowledge of the block decomposition or the evolution. RDMs up to this upper bound suffice for reconstruction. We further show that this RDM order is necessary in general: two orthogonal states in the family can have identical RDMs at every lower order. These results show that an extensive number of non-Gaussian blocks can be compatible with efficient state learning.
Continuous-variable systems enable key quantum technologies in computation, communication, and sensing. Bosonic Gaussian states emerge naturally in various such applications, including gravitational-wave and dark-matter detection. A fundamental question is how to characterize an unknown bosonic Gaussian state from as few samples as possible. Despite decades-long exploration, the ultimate efficiency limit remains unclear. In this work, we study the necessary and sufficient number of copies to learn an n-mode Gaussian state, with energy less than E, to ε trace distance with high probability. We prove a lower bound of Ω(n3/ε2) for Gaussian measurements, matching the best known upper bound up to doubly-log energy dependence, and Ω(n2/ε2) for arbitrary measurements. We further show an upper bound of O(n2/ε2) given that the Gaussian state is promised to be either pure or passive. Interestingly, while Gaussian measurements suffice for nearly optimal learning of pure Gaussian states, non-Gaussian measurements are provably required for optimal learning of passive Gaussian states. Finally, focusing on learning single-mode Gaussian states via non-entangling Gaussian measurements, we provide a nearly tight bound of Θ(E/ε2) for any non-adaptive schemes, showing adaptivity is indispensable for nearly energy-independent scaling. As a byproduct, we establish sharp bounds on the trace distance between Gaussian states in terms of the total variation distance between their Wigner distributions, and obtain a nearly tight sample complexity bound for learning the Wigner distribution of any Gaussian state to ε total variation distance. Our results significantly advance quantum learning theory in the bosonic regimes and have practical impact in quantum sensing and benchmarking applications.
Recent work has shown that one can efficiently learn fermionic Gaussian unitaries, also commonly known as nearest-neighbor matchcircuits or non-interacting fermionic unitaries. However, one could ask a similar question about unitaries that are near Gaussian: for example, unitaries prepared with a small number of non-Gaussian circuit elements. These operators find significance in quantum chemistry and many-body physics, yet no algorithm exists to learn them. We give the first such result by devising an algorithm which makes queries to an n-mode fermionic unitary U prepared by at most O(t) non-Gaussian gates and returns a circuit approximating U to diamond distance ε in time poly(n,2t,1/ε). This resolves a central open question of Mele and Herasymenko under the strongest distance metric. In fact, our algorithm is much more general: we define a property of unitary Gaussianity known as unitary Gaussian dimension and show that our algorithm can learn n-mode unitaries of Gaussian dimension at least 2n−O(t) in time poly(n,2t,1/ε). Indeed, this class subsumes unitaries prepared by at most O(t) non-Gaussian gates but also includes several unitaries that require up to 2O(t) non-Gaussian gates to construct. In addition, we give a poly(n,1/ε)-time algorithm to distinguish whether an n-mode unitary is of Gaussian dimension at least k or ε-far from all such unitaries in Frobenius distance, promised that one is the case. Along the way, we prove structural results about near-Gaussian fermionic unitaries that are likely to be of independent interest.
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.
Fermion sampling is to generate probability distribution of a many-body Slater-determinant wave function, which is termed ``determinantal point process'' in statistical analysis. For its inherently embedded Pauli exclusion principle, its application reaches beyond simulating fermionic quantum many-body physics to constructing machine learning models for diversified datasets. Here we propose a fermion sampling algorithm, which has a polynomial time complexity---quadratic in the fermion number and linear in the system size. This algorithm is about 100 more efficient in computation time than the best known algorithms. In sampling the corresponding marginal distribution, our algorithm has a more drastic improvement, achieving a scaling advantage. We demonstrate its power on several test applications, including sampling fermions in a many-body system and a machine learning task of text summarization, and confirm its improved computation efficiency over other methods by counting floating-point operations.