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.
AI Summary
The paper asks whether fermionic states with an extensive number of non-Gaussian resource blocks remain efficiently learnable after unknown number-conserving Gaussian evolution hides their mode decomposition. The input family consists of disjoint blocks, each with definite particle number and a superposition of Fock configurations whose occupied mode sets are mutually disjoint. Block coefficients, mode supports, and the evolution are unknown.
For homogeneous blocks containing a fixed, known $p$ particles, reconstruction uses only the $1$- and $p$-particle reduced density matrices (RDMs). For heterogeneous blocks with unknown particle numbers bounded by a fixed $r$, RDMs through order $r$ suffice, including when always-occupied and vacuum modes are present. Both algorithms use single-copy measurements and have sample and classical computational costs $m^{O(r)}\varepsilon_{\mathrm{fid}}^{-2}\log(mr/\delta)$, producing a compact pure-state description with fidelity at least $1-\varepsilon_{\mathrm{fid}}$ with probability at least $1-\delta$.
Reconstruction exploits RDM spectra, using high-occupation subspaces of the $1$-RDM to stabilize extraction of block contributions. A randomized Gram-splitting procedure separates individual blocks; heterogeneous reconstruction recursively removes products of previously recovered factors. Perturbation bounds control finite-sample errors. Two orthogonal single-block states have identical RDMs at every order below $r$, establishing worst-case necessity of order $r$ for RDM-based reconstruction.
The guarantees require disjoint branch supports and number-conserving evolution. Polynomial efficiency assumes fixed $r$, and the bounds have large system-size exponents. Optimal complexities, overlapping branches, and general Gaussian evolution remain open.
Little sign of AI-generated textAI use disclosedStrong assumptions
Generative artificial intelligence (AI) tools (ChatGPT 5 and 6) assisted with exploring reconstruction and post-processing ideas, deriving and refining some proofs, and drafting and revising portions of the manuscript.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
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.
The paper asks whether fermionic states with an extensive number of non-Gaussian resource blocks remain efficiently learnable after unknown number-conserving Gaussian evolution hides their mode decomposition. The input family consists of disjoint blocks, each with definite particle number and a superposition of Fock configurations whose occupied mode sets are mutually disjoint. Block coefficients, mode supports, and the evolution are unknown.
For homogeneous blocks containing a fixed, known p particles, reconstruction uses only the 1- and p-particle reduced density matrices (RDMs). For heterogeneous blocks with unknown particle numbers bounded by a fixed r, RDMs through order r suffice, including when always-occupied and vacuum modes are present. Both algorithms use single-copy measurements and have sample and classical computational costs mO(r)εfid−2log(mr/δ), producing a compact pure-state description with fidelity at least 1−εfid with probability at least 1−δ.
Reconstruction exploits RDM spectra, using high-occupation subspaces of the 1-RDM to stabilize extraction of block contributions. A randomized Gram-splitting procedure separates individual blocks; heterogeneous reconstruction recursively removes products of previously recovered factors. Perturbation bounds control finite-sample errors. Two orthogonal single-block states have identical RDMs at every order below r, establishing worst-case necessity of order r for RDM-based reconstruction.
The guarantees require disjoint branch supports and number-conserving evolution. Polynomial efficiency assumes fixed r, and the bounds have large system-size exponents. Optimal complexities, overlapping branches, and general Gaussian evolution remain open.
We prove copy-optimal learning of the full Gaussian orbit of paired magic states on n fermionic modes. The unknown evolution may be any parity-preserving quadratic circuit, including pair creation and annihilation, and each copy is measured once, in a fixed basis, on a single quartic Majorana observable. A nonadaptive learner returns a Gaussian preparation within trace distance ε from Θ(n6/ε2) copies at fixed confidence, and no learner in this measurement model, adaptive or not, can do better. Measured quartic correlations certify the trace distance of the result. Our second result extends learning to a broader family: pure states whose unknown input blocks are superpositions of disjoint occupation patterns with bounded particle number, under the same evolution. Using single-copy Gaussian rotations and occupation readout, a batch-adaptive learner returns an input and a Gaussian circuit with infidelity f from O(n7/f) copies and polynomial classical processing. Connected quartic correlations reveal the hidden mode groups, and fresh local measurements restore the branches and their coherences. No particle-number conservation, minimum branch weight or spectral gap is assumed.
Fermionic Gaussian states are the workhorse reference states for qubit-based quantum simulation of fermionic systems, yet existing certification protocols either proceed via fidelity estimation, leading to suboptimal sample complexity in the target precision ε, only apply to Haar-typical states, or require adaptive measurements on a large fraction of qubits. We give an adaptive protocol that certifies any d-mode pure fermionic Gaussian state using O(d2ε−1) copies, single-qubit measurements with only one qubit measured adaptively per copy, and O(d3) classical processing time per copy. The ε−1 dependence is optimal for the certification problem, even among strategies using entangled measurements. The sample complexity is controlled by the spectral gap of a d↔d−2 down-up walk---a Markov chain studied in the theory of high-dimensional expanders, equivalent to a two-site Glauber dynamics in statistical physics---relating certification efficiency to relaxation time to equilibrium. The worst-case bound is tight for this protocol and is attained by physically relevant states, including ground states of the fully dimerized Su-Schrieffer-Heeger (SSH) chain and BCS pair states. In contrast, numerics up to d=14 suggest that O(dε−1) copies suffice to certify Haar-typical Gaussian states, a factor of d improvement over the worst-case bound. Finally, because the bound depends only on the target's computational-basis distribution, the protocol extends to efficiently phase-dressed states---states obtained by injecting an efficiently computable diagonal phase to Gaussian states---with the same sample complexity. The class includes a continuous family of four-mode non-Gaussian magic states for matchgate computation.
Predicting local fermionic correlations is a central task in quantum many-body physics, as these correlations encode many physically relevant local observables. The ubiquitous particle-number symmetry imposes strong structural constraints on quantum states, suggesting that local correlations should be learned with fewer samples than by symmetry-agnostic approaches. However, it has remained unclear whether such a provable advantage exists in collective learning of local correlations. Here, we develop a framework of number-conserving fermionic-shadow tomography based on random orbital rotations. We prove that, for every given order k, we can simultaneously estimate all k-body fermionic correlations of an N-mode η-particle state with a given variance ε2 using only Ok(ηk/ε2) samples, which are independent of the system size N. We further establish a matching information-theoretic lower bound Ωk(ηk/ε2) for any adaptive protocol based on single-copy measurements, showing that the (ηk,ε)-dependence is optimal up to constants depending only on k. Furthermore, numerical studies show a 20-fold query reduction for one-body correlation estimation at N=200, η=20, and ε=10−2, compared with the best alternative including Heisenberg-limited estimation methods. Relative to fermionic Gaussian-unitary shadows, sample costs for the square-lattice Fermi-Hubbard model at N=288 are reduced by factors of 148 for energy density and 161 for spin structure factor estimation. For molecular energy derivatives with respect to atomic coordinates, our method reduces sample requirements by factors of 53 for Cr2 and 18.5 for [Fe2S2]2− at N=128. These results demonstrate the practical advantage of particle-number symmetry for fermionic observable estimation.
The experimental realization of increasingly complex quantum states underscores the pressing need for new methods of state learning and verification. In one such framework, quantum state tomography, the aim is to learn the full quantum state from data obtained by measurements. Without prior assumptions on the state, this task is prohibitively hard. Here, we present an efficient algorithm for learning states on n fermion modes prepared by any number of Gaussian and at most t non-Gaussian gates. By Jordan-Wigner mapping, this also includes n -qubit states prepared by nearest-neighbor matchgate circuits with at most t gates. Our algorithm is based exclusively on single-copy measurements and produces a classical representation of a state, guaranteed to be close in trace distance to the target state. The sample and time complexity of our algorithm is poly ( n , 2 t ) ; thus if t = O ( log ( n ) ) , it is efficient. We also show that, if t scales more than logarithmically, any learning algorithm to solve the same task must be inefficient, under common cryptographic assumptions. We also provide an efficient property-testing algorithm that, given access to copies of a state, determines whether such a state is far or close to the set of states for which our learning algorithm works. In addition to the outputs of quantum circuits, our tomography algorithm is efficient for some physical target states, such as those arising in time dynamics and low-energy physics of impurity models. Beyond tomography, our work sheds light on the structure of states prepared with few non-Gaussian gates and offers an improved upper bound on their circuit complexity, enabling an efficient circuit-compilation method.
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 algorithms for classical simulation of quantum mechanics have runtime whose superpolynomial component is given by a linear dependence on the number of terms required to write large tensor products of certain "magic" states as superpositions of "free" states (which may be stabilizer states, fermionic Gaussian states or others). Surprisingly little is known about the number of terms in such decompositions, called ranks (e.g. the stabilizer rank, fermionic-Gaussian rank etc.). For complexity theoretic reasons they are expected to grow exponentially in the number of tensor factors but, while exponential upper bounds are known for both the stabilizer and fermionic-Gaussian rank of magic states; the best known lower bounds on the stabiliser rank are quadratic, and no bounds on the fermionic-Gaussian rank are known beyond fixed constants. In this work we prove that any fermionic Gaussian decomposition of ∣M⟩⊗k consists of Ω(1.4k) terms. Here ∣M⟩ is the most standard magic state for fermionic linear optics: the 4 qubit state that may be consumed to implement a swap gate. We also prove essentially matching bounds on the δ-approximate rank of the same state, lower bounding it by the same quantity that bounds the exact rank, multiplied by a factor of 1−δ2. Our results on exact fermionic Gaussian rank apply directly to any product of k fixed parity non-Gaussian states, although the same is not true of the approximate rank. Finally, we prove that the coherent state border rank of an n-mode bosonic Fock state with mj bosons in mode j is exactly ∏j(1+mj), answering a conjecture of Ref. [1] and obtain lower bounds on the approximate coherent state rank given by the same quantity multiplied by a function of the fidelity of the approximation, emphasizing the broad applicability of the method we employ.