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 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 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.
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.
Free-fermionic states, also known as fermionic Gaussian states, represent an important class of quantum states that are ubiquitous in physics. They are uniquely and efficiently described by their correlation matrix. However, in practical experiments, the correlation matrix can only be estimated with finite accuracy. This raises the question: How does the error in estimating the correlation matrix affect the trace-distance error of the state? We show that if the correlation matrix is known with an error ε , the trace-distance error also scales as ε (and vice versa). Specifically, we provide distance bounds between (both pure and mixed) free-fermionic states in relation to their correlation-matrix distance. Our analysis also extends to cases in which one state may not be free-fermionic. Importantly, we leverage our preceding results to derive significant advancements in property testing and tomography of free-fermionic states. Property testing involves determining whether an unknown state is close to or far from being a free-fermionic state. We first demonstrate that any algorithm capable of testing arbitrary (possibly mixed) free-fermionic states would inevitably be inefficient, implying that there is no efficient strategy to estimate the non-Gaussianity of a state. Then, we present an efficient algorithm for testing low-rank free-fermionic states. For free-fermionic state tomography, we provide improved bounds on the sample complexity in the pure-state scenario, substantially improving over previous literature, and we generalize the efficient algorithm to mixed states, discussing its noise robustness.
Quantum measurements are probabilistic and, in general, provide only partial information about the underlying quantum state. Obtaining a full classical description of an unknown quantum state requires the analysis of several different measurements, a task known as quantum-state tomography. Here we analyse the ultimate achievable performance in the tomography of continuous-variable systems, such as bosonic and quantum optical systems. We prove that tomography of these systems is extremely inefficient in terms of time resources, much more so than tomography of finite-dimensional systems such as qubits. Not only does the minimum number of state copies needed for tomography scale exponentially with the number of modes, but, even for low-energy states, it also scales unfavourably with the trace-distance error between the original state and its estimated classical description. On a more positive note, we prove that the tomography of Gaussian states is efficient by establishing a bound on the trace-distance error made when approximating a Gaussian state from knowledge of the first and second moments within a specified error bound. Last, we demonstrate that the tomography of non-Gaussian states prepared through Gaussian unitaries and a few local non-Gaussian evolutions is efficient and experimentally feasible.
Quantum measurements are probabilistic and, in general, provide only partial information about the underlying quantum state. Obtaining a full classical description of an unknown quantum state requires the analysis of several different measurements, a task known as quantum-state tomography. Here we analyse the ultimate achievable performance in the tomography of continuous-variable systems, such as bosonic and quantum optical systems. We prove that tomography of these systems is extremely inefficient in terms of time resources, much more so than tomography of finite-dimensional systems such as qubits. Not only does the minimum number of state copies needed for tomography scale exponentially with the number of modes, but, even for low-energy states, it also scales unfavourably with the trace-distance error between the original state and its estimated classical description. On a more positive note, we prove that the tomography of Gaussian states is efficient by establishing a bound on the trace-distance error made when approximating a Gaussian state from knowledge of the first and second moments within a specified error bound. Last, we demonstrate that the tomography of non-Gaussian states prepared through Gaussian unitaries and a few local non-Gaussian evolutions is efficient and experimentally feasible.
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.