Optimal Haar random fermionic linear optics circuits
Paolo Braccia, N. L. Diaz, Martín Larocca, Marco Cerezo, Diego García-Martín · arXiv (Cornell University) · 2025
Sampling unitary Fermionic Linear Optics (FLO), or matchgate circuits, has become a fundamental tool in quantum information. Such capability enables a large number of applications ranging from randomized benchmarking of continuous gate sets, to fermionic classical shadows. In this work, we introduce optimal algorithms to sample over the non-particle-preserving (active) and particle-preserving (passive) FLO Haar measures. In particular, we provide appropriate distributions for the gates of $n$-qubit parametrized circuits which produce random active and passive FLO. In contrast to previous approaches, which either incur classical $\mathcal{O}(n^3)$ compilation costs or have suboptimal depths, our methods directly output circuits which simultaneously achieve an optimal down-to-the-constant-factor $Θ(n)$ depth and $Θ(n^2)$ gate count; with only a $Θ(n^2)$ classical overhead. Finally, we also provide quantum circuits to sample Clifford FLO with an optimal $Θ(n^2)$ gate count.