Fermionic Linear Optics (FLO) is a restricted model of quantum computation which in its original form is known to be efficiently classically simulable.
A team of researchers showed that, when initialized with suitable input states, FLO circuits can be used to demonstrate quantum computational advantage with strong hardness guarantees.
Based on this, they proposed a quantum advantage scheme which is a fermionic analogue of Boson Sampling: Fermion Sampling with magic input states.
They considered in parallel two classes of circuits: particle-number conserving (passive) FLO and active FLO that preserves only fermionic parity and is closely related to Matchgate circuits introduced by Valiant.
Mathematically, these classes of circuits can be understood as fermionic representations of the Lie groups U(d) and SO(2d). They first showed anti-concentration for probabilities in random FLO circuits of both kind. Moreover, they proved robust average-case hardness of computation of probabilities. To achieve this, they have adapted the worst-to-average-case reduction based on Cayley transform, introduced recently by Movassagh, to representations of low-dimensional Lie groups. Taken together, these findings provide hardness guarantees comparable to the paradigm of Random Circuit Sampling.
Most importantly, their scheme has also a potential for experimental realization. Both passive and active FLO circuits are relevant for quantum chemistry and many-body physics and have been already implemented in proof-of-principle experiments with superconducting qubit architectures. Preparation of the desired quantum input states can be obtained by a simple quantum circuit acting independently on disjoint blocks of four qubits and using 3 entangling gates per block.
They have also argued that due to the structured nature of FLO circuits, they can be efficiently certified.