Fermion Sampling: A Robust Quantum Computational Advantage Scheme Using Fermionic Linear Optics and Magic Input States

Fermionic linear optics (FLO) is a restricted model of quantum computation, which in its original form is known to be efficiently classically simulable. We show that, when initialized with suitable input states, FLO circuits can be used to demonstrate quantum computational advantage with strong hardness guarantees. Based on this, we propose a quantum advantage scheme, which is a fermionic analog of boson sampling: fermion sampling with magic input states. We consider in parallel two classes of circuits: particle-number conserving (passive) FLO and active FLO that preserves only fermionic parity. Using low-dimensional continuous symmetry groups that underpin these classes of quantum circuits, we prove anticoncentration and robust average-case hardness of computation of output probabilities probabilities. Taken together, these findings provide hardness guarantees comparable to the paradigm of random circuit sampling and boson sampling, the leading candidates for attaining quantum computational advantage. Our scheme is experimentally feasible. FLO circuits are relevant for quantum chemistry and many-body physics, and have been successfully implemented in superconducting architectures. We also argue that due to the structured nature of FLO circuits, they can be efficiently certified using resources scaling polynomially with the system size, with partial trust in the quantum device.