Fermionic linear optics (FLO) with Gaussian resources is known to be efficiently classically simulable. We show that this changes for fermions with internal degrees of freedom once the circuit is equipped with mid-circuit number monitoring and classical feedforward. In our architecture, the measurement record routes the selected blocks into a fixed-order Bell-fusion pairing geometry. On the level of the classical description, the permutation sum then no longer collapses to a single determinant or Pfaffian. Each accepted branch expands as a signed sum of path-ordered products of typically non-commuting dressed blocks, and branch amplitudes are matrix elements of the resulting non-commutative trace polynomials. Numerically, we observe Porter-Thomas statistics for the conditional branch distribution and rapid growth of the minimal order-respecting matrix product operator bond dimension. Under reasonable complexity assumptions, these results identify mid-circuit measurement-induced non-commutativity as a route to sampling hardness for noninteracting fermions, with the non-Gaussianity confined to a fixed preparation-and-readout interface rather than to the coherent FLO evolution.
Fermionic linear optics (FLO) with Gaussian resources is known to be efficiently classically simulable. We show that this changes for fermions with internal degrees of freedom once the circuit is equipped with mid-circuit number monitoring and classical feedforward. In our architecture, the measurement record routes the selected blocks into a fixed-order Bell-fusion pairing geometry. On the level of the classical description, the permutation sum then no longer collapses to a single determinant or Pfaffian. Each accepted branch expands as a signed sum of path-ordered products of typically non-commuting dressed blocks, and branch amplitudes are matrix elements of the resulting non-commutative trace polynomials. Numerically, we observe Porter-Thomas statistics for the conditional branch distribution and rapid growth of the minimal order-respecting matrix product operator bond dimension. Under reasonable complexity assumptions, these results identify mid-circuit measurement-induced non-commutativity as a route to sampling hardness for noninteracting fermions, with the non-Gaussianity confined to a fixed preparation-and-readout interface rather than to the coherent FLO evolution.
Gaussian building blocks are essential for photonic quantum information processing, and universality can be practically achieved by equipping Gaussian circuits with adaptive measurement and feedforward. The number of adaptive steps then provides a natural parameter for computational power. Rather than assessing power only through sampling problems—the usual benchmark—we follow the ongoing shift toward tasks of practical relevance and study the quantum mean-value problem, i.e., estimating observable expectation values that underpin simulation and variational algorithms. More specifically, we analyze bosonic circuits with adaptivity and prove that when the number of adaptive measurements is small, the mean-value problem admits efficient classical algorithms even if a large amount of non-Gaussian resources are present in the input state, whereas less constrained regimes are computationally hard. This yields a task-level contrast with sampling, where non-Gaussian ingredients alone often induce hardness, and provides a clean complexity boundary parameterized by the number of adaptive measurement-and-feedforward steps between classical simulability and quantum advantage. Beyond the main result, we introduce classical techniques—including a generalization of Gurvits’ second algorithm to arbitrary product inputs and Gaussian circuits—for computing the marginal quantities needed by our estimators, which may be of independent interest.
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 O(n5/ε2) queries, where n is the system size and ε 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 ε. For arbitrary (active) FLOs this algorithm makes at most O(n4/ε) queries, while for number-conserving (passive) FLOs we show that O(n3/ε) queries suffice. The complexity of the active case can be further reduced to O(n3/ε) 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 O(nη2/ε2) for time-efficient state tomography of η-particle Slater determinants in ε trace distance, which may be of independent interest.
Establishing the precise computational boundary between classically tractable fermionic systems and those capable of genuine quantum advantage is a central challenge in quantum simulation. While injecting non-Gaussian ``magic" inputs into free-fermion circuits is widely expected to generate intractable complexity, we identify a physically motivated intermediate regime. We prove that for block-product paired non-Gaussian fermionic states, essential quantum simulation primitives -- transition amplitudes, overlaps, and arbitrary-weight number correlators -- can be efficiently approximated to additive error under free-fermionic dynamics. This tractability stems from an algebraic reduction that compresses exponentially large multiparticle interference into a single coefficient of a multivariate Pfaffian polynomial. Because these classical estimators match the intrinsic O(1/K) statistical uncertainty of quantum hardware utilizing K measurement shots, they constitute a practical benchmark. Building on this foundation, we construct an additive-error estimator for high-weight Wilson observables in the noninteracting quench of recent trapped-ion experiments, providing a rigorous classical benchmark. Extending this to quantum chemistry, we demonstrate that core overlap-based subroutines for antisymmetrized products of strongly orthogonal geminals admit efficient additive-error Pfaffian-kernel estimators. Ultimately, these results sharpen the boundary of quantum advantage, establishing that the paired-electron scaffold is dequantized and clarifying where quantum resources are indispensable.
We propose efficient algorithms for classically simulating fermionic linear optics operations applied to non-Gaussian initial states. By gadget constructions, this provides algorithms for fermionic linear optics with non-Gaussian operations. We argue that this problem is analogous to that of simulating Clifford circuits with non-stabilizer initial states: Algorithms for the latter problem immediately translate to the fermionic setting. Our construction is based on an extension of the covariance matrix formalism which permits to efficiently track relative phases in superpositions of Gaussian states. It yields simulation algorithms with polynomial complexity in the number of fermions, the desired accuracy, and certain quantities capturing the degree of non-Gaussianity of the initial state. We study one such quantity, the fermionic Gaussian extent, and show that it is multiplicative on tensor products when the so-called fermionic Gaussian fidelity is. We establish this property for the tensor product of two arbitrary pure states of four fermions with positive parity.
Sampling-based quantum advantage raises a basic resource question: how much non-Gaussianity is needed to reproduce the random-matrix statistics often associated with quantum chaos? Passive fermionic linear optics preserves Gaussian structure, and even Haar-random mode mixing fails to anticoncentrate for Slater inputs. We show that overcoming this obstruction requires an extensive input resource. For any pure half-filled input state, the one-body defect ν, defined as the summed occupation variance of the natural orbitals, must scale linearly with system size. For products of bounded-size blocks on 4N modes, this condition is also sufficient, with normalized collision moment asymptotic to 2N/ν, compared with the Porter-Thomas value 2. For four-mode products, the full Porter-Thomas moment hierarchy is recovered precisely when the defect density tends to its maximum. Assuming average-case hardness, approximate classical sampling remains hard near maximal density, with an error tolerance that increases with the density. Two-copy number fluctuations measure ν directly, and the same quantity lower-bounds the combined cost of non-Gaussian resource modes and parity-preserving local gates in deterministic exact preparation. Fermionic randomness therefore carries an extensive magic cost, with a quantitative link between sampling statistics, preparation resources, and an experimentally accessible witness.
Quantum generative learning is a promising application of quantum computers, but faces several trainability challenges, including the difficulty in experimental gradient estimations. For certain structured quantum generative models, however, expectation values of local observables can be efficiently computed on a classical computer, enabling fully classical training without quantum gradient evaluations. Although training is classically efficient, sampling from these circuits is still believed to be classically hard, so inference must be carried out on a quantum device, potentially yielding a computational advantage. In this work, we introduce Fermionic Born Machines as an example of such classically trainable quantum generative models. The model employs parameterized magic states and fermionic linear optical (FLO) transformations with learnable parameters. The training exploits a decomposition of the magic states into Gaussian operators, which permits efficient estimation of expectation values. Furthermore, the specific structure of the ansatz induces a loss landscape that exhibits favorable characteristics for optimization. The FLO circuits can be implemented, via fermion-to-qubit mappings, on qubit architectures to sample from the learned distribution during inference. Numerical experiments on systems up to 160 qubits demonstrate the effectiveness of our model and training framework.