Robust quantum computational advantage using fermionic linear optics and magic input states*

A fermionic analogue of Boson Sampling, known as Fermionic Linear Optics (FLO), is a restricted model of quantum computation which 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. We consider particle-number conserving (passive) FLO, and active FLO, also known as Matchgate circuits. We prove anticoncentration for probabilities in random FLO circuits. We also show robust average-case hardness of computation of probabilities in our scheme. We achieve this by adopting to representations of Lie groups the worst-to average-case reduction by Movassagh. These findings give together hardness guarantees matching that of the Random Circuit Sampling and surpassing Boson Sampling. Our scheme is experimentally feasible. FLO circuits are relevant for quantum chemistry and many-body physics, and have been successfully implemented in the superconducting architectures. Preparation of the desired input state is done by a simple shallow and parallelizable circuit. 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.