Mildly-Interacting Fermionic Unitaries are Efficiently Learnable

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 varepsilon in time textrmpoly(n,2t,1/varepsilon). 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 textrmpoly(n,2t,1/varepsilon). 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 textrmpoly(n,1/varepsilon)-time algorithm to distinguish whether an n-mode unitary is of Gaussian dimension at least k or varepsilon-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.