Learning fermionic linear optics with Heisenberg scaling and physical operations

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 $widetilde{mathcal{O}}(n^5 / varepsilon^2)$ queries, where $n$ is the system size and $varepsilon$ 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 $varepsilon$. For arbitrary (active) FLOs this algorithm makes at most $widetilde{mathcal{O}}(n^4 / varepsilon)$ queries, while for number-conserving (passive) FLOs we show that $mathcal{O}(n^3 / varepsilon)$ queries suffice. The complexity of the active case can be further reduced to $widetilde{mathcal{O}}(n^3 / varepsilon)$ 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 $widetilde{mathcal{O}}(n η^2 / varepsilon^2)$ for time-efficient state tomography of $η$-particle Slater determinants in $varepsilon$ trace distance, which may be of independent interest.