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 $Θ(n^6/ε^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 $\widetilde O(n^7/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.
Comments
59 pages, 3 figures; v2 adds copy-optimal paired-orbit learning under fixed-basis quartic measurements and improves the general-family copy bound; supporting Lean files included as ancillary material
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.
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.
We prove that learning an unknown mixed fermionic Gaussian state on m modes to trace distance ε requires Ω(m3/ε2) copies when measurements act on one copy at a time, even with arbitrary POVMs, fresh ancillas and classical adaptivity, but without quantum memory between copies. The bound holds for 0<ε≤1/3600 and separates this model from the known collective rate Θ(m2/ε2). It follows from a uniform single-copy Fisher-information budget and a dimension-independent comparison between trace distance and Gaussian parameters. On covariance matrices of operator norm at most 1−c, we prove a Frobenius-to-trace-norm continuity bound with constant [2c(2−c)]−1/2; matchgate shadows then attain O(m3/(cε2)) copies. This also gives explicit error certificates for thermal free-fermion states. For a class of mixed passive bosonic Gaussian states with total mean photon number at most one, a reduction to bounded-block qudit tomography gives a single-copy lower bound Ω(m3/(ε2log(m/ε))), versus collective complexity Θ(m2/ε2). These separations answer the mixed-state measurement-resource question posed by Chen et al. A two-mode example has optimal two-copy Fisher trace 5, versus the separable ceiling 4. An IBM replication gave a pre-registered witness lower bound 4.12 at one-sided 95% shot-noise confidence; its interpretation assumes the prescribed preparations and a common measurement channel and does not bound preparation systematics.
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.
The classical cost of simulating free-fermion (matchgate) circuits depends on both the input state and the computational task. We develop classical algorithms for circuits with non-Gaussian inputs, addressing exact sampling and both additive-error and exact estimation of expectation values. For inputs consisting of n copies of the four-mode magic state, we give exact sampling algorithms, generalizing the Clifford and Clifford algorithm for Boson sampling, for passive and active free-fermion dynamics with worst-case arithmetic cost O(2n) per sample, without any multiplicative polynomial prefactor. The passive algorithm enables an exact simulation of the non-interacting regime of a recent trapped-ion experiment. We also extend recently developed additive-error estimation of number correlators and related observables from passive to active dynamics with runtime polynomial in n and the inverse additive-error, for input states formed by products of n four-mode even parity states. Our estimator uses a Gaussian-state decomposition adapted to each sampled state to control its second moment. This includes estimation of individual output probabilities. Finally, we show that for even-parity product inputs composed of constant-size blocks, expectation values of Majorana monomials of logarithmic weight can be computed exactly in polynomial time, improving on prior Majorana propagation-style algorithms with quasi-polynomial runtime. The exact algorithm processes the input blocks by dynamic programming, sharing calculations across subsets of Majorana factors. Our suite of algorithms provide classical benchmarks for fermionic quantum simulations across a broad spectrum of computational tasks.
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.
We give collective tomography protocols for quantum states and channels with known symmetries, using random purification and dilation to reduce learning to pure-state estimation. For states commuting with a compact-group representation with multiplicities mλ, the optimal copy complexity is Θ((∑λmλ2+logη−1)/ε2) for sufficiently small trace-distance error ε and failure probability η for the nontrivial case ∑λmλ2>1. For G-covariant channels with finite-dimensional unitary representations of a compact group G, parallel O(DG/ε2) queries achieve a diamond-distance error $\varepsilon $ at fixed success probability 2/3, where DG counts the real parameters of covariant Choi operators before imposing trace preservation. For permutation-covariant channels on k qudits of fixed local dimension d, at sufficiently small fixed error and fixed success probability 2/3, we obtain the optimal query scalings Θd(kd4−1) for diamond distance and Θd(kd4−d2) for Choi trace distance. Furthermore, we resolve an open problem in quantum tomography of constructing efficient quantum circuits that approximate the Hayashi measurement for optimal pure-state estimation. We encode states in the symmetric subspace into bosonic occupation modes, realize the measurement by heterodyne detection and normalization, and approximate this procedure on qubits using the quantum Hermite transform. Combined with our symmetry-compatible purification and dilation circuits, this yields query-optimal and gate-efficient learners of permutation-covariant states and channels with gate complexity Od(poly(k,ε−1,logη−1)).