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⁵ / varepsilon²\) 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⁴ / varepsilon\) queries, while for number-conserving (passive) FLOs we show that mathcal{O}\(n³ / varepsilon\) queries suffice. The complexity of the active case can be further reduced to widetilde{mathcal{O}}\(n³ / 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 η² / varepsilon²\) for time-efficient state tomography of η-particle Slater determinants in varepsilon trace distance, which may be of independent interest.