Fermionic Gaussian unitaries are known to be efficiently learnable and simulatable. In this paper, we present a learning algorithm that learns an $n$-mode circuit containing $t$ parity-preserving non-Gaussian gates. While circuits with $t = \textrm{poly}(n)$ are unlikely to be efficiently learnable, for constant $t$, we present a polynomial-time algorithm for learning the description of the unknown fermionic circuit within a small diamond-distance error. Building on work that studies the state-learning version of this problem, our approach relies on learning approximate Gaussian unitaries that transform the circuit into one that acts non-trivially only on a constant number of Majorana operators. Our result also holds for the case where we have a qubit implementation of the fermionic unitary.
Fermionic Gaussian unitaries are known to be efficiently learnable and simulatable. In this paper, we present a learning algorithm that learns an n-mode circuit containing t parity-preserving non-Gaussian gates. While circuits with t=poly(n) are unlikely to be efficiently learnable, for constant t, we present a polynomial-time algorithm for learning the description of the unknown fermionic circuit within a small diamond-distance error. Building on work that studies the state-learning version of this problem, our approach relies on learning approximate Gaussian unitaries that transform the circuit into one that acts non-trivially only on a constant number of Majorana operators. Our result also holds for the case where we have a qubit implementation of the fermionic unitary.
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.
We revisit the problem of learning fermionic linear optics (FLO), also known as fermionic Gaussian unitaries. Given black-box query access to an unknown FLO, previous proposals required O(n5/ε2) queries, where n is the system size and ε is the error in diamond distance. These algorithms also use unphysical operations (i.e., violating fermionic superselection rules) and/or n auxiliary modes to prepare Choi states of the FLO. In this work, we establish efficient and experimentally friendly protocols that obey superselection, use minimal ancilla (at most 1 extra mode), and exhibit improved dependence on both parameters n and ε. For arbitrary (active) FLOs this algorithm makes at most O(n4/ε) queries, while for number-conserving (passive) FLOs we show that O(n3/ε) queries suffice. The complexity of the active case can be further reduced to O(n3/ε) at the cost of using n ancilla. This marks the first FLO learning algorithm that attains Heisenberg scaling in precision. As a side result, we also demonstrate an improved copy complexity of O(nη2/ε2) for time-efficient state tomography of η-particle Slater determinants in ε trace distance, which may be of independent interest.
We present the first computationally-efficient algorithm for average-case learning of shallow quantum circuits with many-qubit gates. Specifically, we provide a quasi-polynomial time and sample complexity algorithm for learning unknown QAC0 circuits -- constant-depth circuits with arbitrary single-qubit gates and polynomially many CZ gates of unbounded width -- with at most logarithmic ancilla, up to inverse-polynomially small error. Furthermore, we show that the learned unitary can be efficiently synthesized in poly-logarithmic depth. This work expands the family of efficiently learnable quantum circuits, notably since in finite-dimensional circuit geometries, QAC0 circuits require polynomial depth to implement.
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.
We study the problem of learning nearly (s,ε)-sparse unitaries, meaning that the Pauli spectrum is concentrated on at most s components with at most ε residual mass in Pauli ℓ1-norm. This class generalizes well-studied families, including sparse unitaries, quantum k-juntas, 2k-Pauli dimensional channels, and compositions of depth O(loglogn) circuits with near-Clifford circuits.
Given query access to an unknown nearly sparse unitary U, our goal is to efficiently (both in time and query complexity) construct a quantum channel that is close in diamond distance to U. We design a learning algorithm achieving this guarantee using O~(s6/ε4) forward queries to U, and running time polynomial in relevant parameters.
A key contribution is an efficient quantum algorithm that, given query access to an arbitrary unknown unitary U, estimates all Pauli coefficients (up to a shared global phase) whose magnitude exceeds a given threshold θ, extending existing sparse recovery techniques to general unitaries.
We also study the broader class of unitaries with bounded Pauli ℓ1-norm. For that class, we prove an exponential query lower bound Ω(2n/2). We introduce a more relaxed accuracy metric which is the diamond distance restricted to a set of input states. Then, we show that, under this metric, unitaries with Pauli ℓ1-norm uniformly bounded by L1 are learnable with O~(L18/ε16).
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.