Fermionic non-Gaussianity via Bell sampling: monotones and efficient quantum algorithms

I. INTRODUCTION

• Existing fermionic non-Gaussianity monotones are either not efficiently computable or lack an operational interpretation tied to state complexity.The introduction identifies the need for a monotone that is both computable and operationally meaningful.Source: §I · p. 3

A. Overview of main results

• Bell sampling enables an efficient two-copy Gaussianity test with perfect completeness and a tolerant variant, and polynomial-sample certification of the 2-design property for matchgate-invariant ensembles.The Gaussianity test is optimal among two-copy tests with perfect completeness.Source: §I · p. 3, A. Overview of main results · p. 8
• The bridge degree is the largest occupied eigenvalue sector of Λ; it is discrete, vanishes exactly for pure fermionic Gaussian states, is additive, and is non-increasing under post-selected Gaussian protocols.It is directly accessible from a state description and can be witnessed experimentally through Bell sampling.Source: §I · p. 3, A. Overview of main results · p. 4
• A state with bridge degree Ω(n) requires Ω(n) non-Gaussian gates to prepare, and one Bell sample certifies at least |λ1|/8 gates.The gate lower bound applies to preparation by probabilistic protocols built from post-selected Gaussian operations and non-Gaussian gates.Source: A. Overview of main results · p. 5
• Post-selected Gaussian protocols cannot split an n-qubit non-Gaussian pure state into m non-Gaussian four-qubit pure states when 4m > n, and the exact-conversion resource theory is irreversible.The conversion impossibility holds even when the input is arbitrarily far from Gaussian states and each output factor is arbitrarily close to them.Source: A. Overview of main results · pp. 5–6
• Every exact state k-design for k ≥ 2 contains a state requiring at least floor(n/4) = Ω(n) non-Gaussian gates.The paper also relates bridge degree to the distance between a state’s matchgate orbit and Haar-random states.Source: A. Overview of main results · p. 6
• The approximate bridge degree is monotone under Gaussian protocols, while bridge fidelity provides an efficiently Bell-sample-estimable lower bound and certifies approximate non-Gaussian preparation cost.The lower bound Fε(ψ)/4 on canonical magic states needed for approximate preparation is efficiently estimable from Bell-sampling data.Source: A. Overview of main results · pp. 6–7
• A Choi–Jamiołkowski construction extends the bridge degree to mixed states, preserving integer-valuedness, faithfulness, additivity, and monotonicity under post-selected Gaussian operations.The mixed-state bridge distribution is not directly accessible from copies alone, but error mitigation enables certification for global depolarizing noise on an underlying pure state.Source: A. Overview of main results · p. 7
• For matchgate-invariant ensembles, the Bell-sampling Gaussianity test uses two copies at a time, has perfect completeness and O(n^2/ε) sample complexity, and minimizes false acceptance on every non-Gaussian state among such tests.The protocol accepts only when every observed Bell outcome corresponds to Λ-eigenvalue λ = 0.Source: A. Overview of main results · p. 8
• For any state prepared by a t-doped Gaussian protocol, the same test distinguishes the two Gaussianity cases with O(t^2/ε) copies, independent of system size n.Source: A. Overview of main results · p. 8
• The tolerant Bell-sampling test distinguishes FG(ψ) ≥ 1−α from FG(ψ) ≤ 1−β when ε := β/n^2−2α > 0 and α = O(ε), using O(n^2/(β−2αn^2) log(1/δ)) copies.Source: A. Overview of main results · p. 8
• For matchgate-invariant ensembles, D(E) is the total-variation distance between ensemble-averaged and Haar bridge spectral distributions and is estimable to additive accuracy ε from e O(√n/ε^2) Bell samples.Each round draws a fresh state from the ensemble and Bell-samples two copies.Source: A. Overview of main results · p. 8
• Exact 2-design testing for matchgate-invariant ensembles distinguishes D(E) = 0 from D(E) ≥ ε using O(n^1/4/ε^2) Bell samples; efficient testing for arbitrary ensembles is not known in general.Source: A. Overview of main results · p. 8

B. Organization

• The paper proceeds from preliminaries and the bridge operator to monotones, conversion and design bounds, approximate and mixed-state extensions, and Bell-sampling algorithms.It closes with a discussion of open problems.Source: B. Organization · p. 9

II. PRELIMINARIES

• The preliminaries set notation for n-qubit systems and introduce trace distance and the Hilbert–Schmidt inner product.Source: §II · p. 9

A. Majorana operators

• The Jordan–Wigner transformation relates n qubits to n fermionic modes, whose Majorana operators satisfy canonical anticommutation relations and generate an operator basis.The parity operator distinguishes even operators and decomposes the Hilbert space into parity sectors.Source: A. Majorana operators · pp. 9–10

B. Fermionic Gaussian states and matchgates

• Fermionic Gaussian states are generated by matchgate unitaries acting on Majorana operators, and pure Gaussian states are matchgate transforms of the vacuum.The bridge operator characterizes pure Gaussian states and is invariant under matchgate unitaries.Source: B. Fermionic Gaussian states and… · p. 10

C. Resource theory of fermionic non-Gaussianity

• The resource theory takes Gaussian states and Gaussian operations as free; post-selected protocols additionally allow conditioning on a measurement outcome.Because Gaussian states are not convex, probabilistic mixtures can be non-Gaussian, motivating a convex resource theory based on their convex hull.Source: C. Resource theory of fermionic… · p. 11

D. Fermionic non-Gaussianity monotones

• Additive monotones bound Gaussian conversion rates, while monotonicity under post-selection extends no-go results to probabilistic conversions.Additivity reduces many-copy conversion bounds to single-copy values.Source: D. Fermionic non-Gaussianity monotones · pp. 11–12
• Gaussian rank and extent relate to classical simulation but involve optimization, while relative entropy is additive and monotone under pure-state Gaussian protocols.Source: D. Fermionic non-Gaussianity monotones · p. 12
• The bridge degree is the only compared monotone that is post-selection monotone, additive, and computable from the state description.Source: D. Fermionic non-Gaussianity monotones · p. 12, Table III · p. 12

E. Haar measure and state designs

• State k-designs match the Haar k-th moment, and trace-distance approximation gives an operational limit on distinguishability from Haar-random states.The twirling channel projects onto the corresponding unitary commutant.Source: E. Haar measure and state designs · p. 13

F. Pauli operators and Bell sampling

• Bell sampling measures two copies in the Bell basis after a Bell-basis-to-computational-basis unitary; either qubit or fermionic hardware admits a depth-1 implementation.The fermionic implementation uses matchgate beam splitters, and the outcome distribution is identical across implementations.Source: F. Pauli operators and Bell sampling · pp. 13–14

III. EIGENSTRUCTURE OF THE BRIDGE OPERATOR

• The bridge operator’s spectral projectors form an orthonormal basis for the second-order matchgate commutant, and its eigenspace weights define a matchgate-invariant distribution.Source: §III · p. 14

A. Spectrum and Bell-state eigenbasis

• Each bridge-operator eigenspace has a basis of tensor products of Bell states, whose eigenvalues are determined by their Majorana-pair eigenvalues.Bell-measurement outcomes provide a dictionary for recovering the bridge eigenvalue and sampling its distribution on two copies.Source: A. Spectrum and Bell-state eigenbasis · pp. 14–15

B. Symmetry constraints from the two-copy structure

• Exchange symmetry places eigenspaces with λ ≡ 0 or 2 (mod 8) in the symmetric subspace and those with λ ≡ 4 or 6 (mod 8) in the antisymmetric subspace.Since two identical pure-state copies are symmetric, outcomes in the latter sectors are excluded.Source: B. Symmetry constraints from the… · p. 16

C. Bell-state weights and eigenvalue restriction

• For even pure states, parity symmetry makes the Bell-state weights symmetric under λ → −λ.Source: C. Bell-state weights and eigenvalue… · p. 17
• Combining exchange and parity symmetry restricts the bridge spectral distribution of an even pure state to eigenvalues λ = 8k, within the operator’s spectrum bound.Source: C. Bell-state weights and eigenvalue… · p. 17

D. The second-order matchgate commutant

• The bridge spectral weights determine the matchgate-twirled two-copy state, so matching weights are equivalent to matching second moments.The spectral projectors form an orthogonal basis for the second-order matchgate commutant.Source: D. The second-order matchgate commutant · pp. 17–19
• An even pure state is Gaussian exactly when its bridge spectral distribution is concentrated at λ = 0.Any weight at λ ≠ 0 is an experimentally accessible signature of non-Gaussianity.Source: D. The second-order matchgate commutant · p. 18
• The distribution is Bell-sample accessible, matchgate-invariant, and supported on at most 2⌊n/4⌋ + 1 integer values.It is a complete second-moment invariant of the matchgate orbit.Source: D. The second-order matchgate commutant · pp. 18–19

A. Definition and basic properties

• The bridge degree is the largest α with nonzero weight pψ(2α); it takes values 4k, vanishes exactly on pure Gaussian states, and is additive and non-increasing under post-selected Gaussian protocols.It is determined directly from the distribution's support rather than an optimization over Gaussian decompositions.Source: A. Definition and basic properties · p. 19, §IV · p. 19
• For even pure states on 4–7 qubits, every non-Gaussian state has bridge degree 4.Non-Gaussianity cannot occur for even pure states on fewer than four qubits.Source: A. Definition and basic properties · p. 20
• The empirical Bell-sampling estimate is a lower bound that becomes exact once the extremal sector is observed, but can need exponentially many samples if its weight is exponentially small.This motivates the approximate bridge-degree variant.Source: A. Definition and basic properties · p. 20

B. Monotonicity under post-selected Gaussian protocols

• The bridge degree is non-increasing under a post-selected Gaussian protocol when the specified even pure input produces a pure output.The condition is pointwise on the input-output pair; the protocol need not preserve purity for every input.Source: B. Monotonicity under post-selected… · p. 20
• Monotonicity and additivity imply that preparing a state with t 4-local non-Gaussian gates requires Λd(ψ) ≤ 4t.The bound applies to t-doped Gaussian protocols, with Gaussian operations between the non-Gaussian gates.Source: B. Monotonicity under post-selected… · pp. 21–22
• The bridge degree organizes even pure states into nested tiers, from pure Gaussian states at F0 to the full even Hilbert space at F4⌊n/4⌋.A particle-preserving counterpart, the Plücker degree, is also monotone under particle-preserving Gaussian protocols.Source: B. Monotonicity under post-selected… · p. 22

A. No-go theorems for Gaussian conversion

• A Gaussian conversion, even with nonzero-probability post-selection, is impossible whenever the input bridge degree is smaller than the target's.The condition follows from monotonicity under post-selected Gaussian protocols.Source: A. No-go theorems for Gaussian… · p. 22
• The bridge degree rules out 2 copies of GHZ6 converting to 3 copies of GHZ4: their degrees are 8 and 12, respectively.The relative entropy of non-Gaussianity does not rule out this conversion, while checking Gaussian rank requires difficult optimization.Source: A. No-go theorems for Gaussian… · p. 23
• For 4 copies of GHZ6 versus 3 copies of GHZ8, the degrees are 16 and 24, a no-go that the other compared monotones cannot efficiently certify.The relative entropy and second moment give equal values for the two tensor-product states; Gaussian rank, extent, and fidelity are not known to be efficiently computable on them.Source: A. No-go theorems for Gaussian… · p. 23
• Additivity together with post-selection monotonicity extends conversion no-go bounds to probabilistic protocols, unlike additive monotones that lack post-selection monotonicity.The paper identifies the bridge degree as the first known non-Gaussianity monotone with both properties.Source: A. No-go theorems for Gaussian… · p. 23
• No post-selected Gaussian protocol can exactly spread an n-qubit even pure non-Gaussian state into m separate 4-qubit even pure non-Gaussian states when n < 4m.This obstruction holds even if the input is arbitrarily far from Gaussian while each target factor is arbitrarily close.Source: A. No-go theorems for Gaussian… · p. 23

B. Irreversibility of the resource theory

• The resource theory of fermionic non-Gaussianity is irreversible under exact post-selected Gaussian protocols: some states have distinct exact distillation and cost rates.The result is confined to exact conversion, rather than the approximate asymptotic setting.Source: B. Irreversibility of the resource… · p. 24
• The rate gap can be made arbitrarily strong using two-fermion pairing states, whose bridge degree is at most 4 while their Gaussian nullity is maximal.For L > 2/ε, the resulting ratio is smaller than any ε > 0; GHZ states do not give this construction because their bridge-degree-to-nullity ratio tends to 1.Source: B. Irreversibility of the resource… · pp. 25–26

C. Lower bounds for state designs

• The state-design analysis computes the Haar bridge spectral distribution and uses its characteristic property to derive non-Gaussian gate-count lower bounds in exact and approximate settings.The supplied passages describe this approach but do not provide the resulting lower-bound values.Source: C. Lower bounds for state designs · p. 26

1. The Haar bridge spectral distribution

• The Haar bridge spectral distribution is binomial, peaked at λ = 0, supported through |λ| ≤ 8⌊n/4⌋, and approximately Gaussian with width √n.For the normalized variable, the distribution converges to a standard Gaussian, with Kolmogorov distance O(1/√n).Source: §1 · pp. 27–28
• The O(1/√n) Kolmogorov-distance rate is sharp, since the discrepancy at zero is Θ(1/√n).This follows from the symmetry of the distribution and the mass at λ = 0.Source: §1 · p. 28

• t = Ω(n) non-Gaussian gates are required for exact state 2-designs prepared by t-doped Gaussian protocols.Source: §2 · p. 29
• At least one state in any exact state 2-design ensemble requires t ≥⌊n/4⌋ non-Gaussian gates.Source: §2 · p. 29
• The exact-design bound is existential, so it leaves open whether hard states form an exponentially small fraction of the ensemble.Source: §2 · p. 29
• Approximate state 2-designs require at least Ω(n log(1/ϵ)) non-Gaussian gates to reproduce Haar statistics.Source: §2 · p. 30
• A state with bridge degree o(n log(1/ϵ)) has a matchgate orbit at trace distance > ϵ from the Haar-random state.Source: §2 · p. 30

VI. THE ϵ-APPROXIMATE BRIDGE DEGREE

• The exact bridge degree can jump to its maximum under an arbitrarily small non-Gaussian perturbation, motivating an approximate variant that tolerates target-state fidelity error.Source: §VI · p. 31
• Although its definition optimizes over nearby states, an efficiently computable lower bound from Bell-sampling data makes approximate-conversion bounds experimentally accessible.Source: §VI · p. 31

A. Monotonicity under Gaussian protocols

• The ϵ-approximate bridge degree is the lowest bridge degree among even pure states with fidelity at least 1 −ϵ to the target.Source: A. Monotonicity under Gaussian protocols · p. 31
• It is monotone when Gaussian protocols output pure states, but this result excludes post-selection on measurement outcomes.Source: §VI · p. 31, A. Monotonicity under Gaussian protocols · p. 32

• The approximate bridge fidelity is the smallest threshold α capturing at least a fraction (1 −ϵ)^2 of the bridge spectral distribution, and it lower-bounds the approximate bridge degree.Source: B. A computable lower bound from the… · p. 33
• For mixed states, the convex-roof extension yields a fidelity witness that can certify non-Gaussianity from target-state fidelity and the approximate bridge fidelity.Source: B. A computable lower bound from the… · p. 33
• A Bell-sampling algorithm estimates the approximate bridge fidelity with probability at least 1 −δ without prior knowledge of the spectral gap Δ.Source: B. A computable lower bound from the… · p. 33

C. Approximate Gaussian conversion

• The approximate bridge degree extends Gaussian-conversion bounds to δ-close targets, including a bound when post-selection succeeds with any nonzero probability.Source: C. Approximate Gaussian conversion · pp. 34–35
• Preparing ψ within ϵ trace distance requires at least Fϵ(ψ)/4 magic states, a cost bound efficiently estimable from Bell-sampling data.Source: C. Approximate Gaussian conversion · p. 36

VII. MIXED-STATE EXTENSION

• The mixed-state bridge degree uses the largest occupied eigenvalue of a Choi-space operator and is non-increasing under post-selected Gaussian operations.Source: §VII · p. 36

A. The bridge operator on the doubled Hilbert space

• For even mixed states, the mixed-state bridge distribution is supported only on eigenvalues in 8Z and is invariant under matchgate unitaries.Source: A. The bridge operator on the doubled… · pp. 38–39
• Bell sampling requires preparing the Choi state; copies of a mixed state alone generally cannot prepare it, though global-depolarizing-noise mitigation can reconstruct the underlying pure-state distribution.Source: A. The bridge operator on the doubled… · p. 39

B. Definition and basic properties

• The mixed-state bridge degree is the largest α ≥ 0 for which the mixed-state bridge spectral distribution has nonzero weight at 4α.Equivalently, it is the smallest α ≥ 0 such that the two-copy Choi state lies in the span of eigenspaces with |j| ≤ 4α.Source: B. Definition and basic properties · p. 39
• It takes values in {0, 2, 4, …}, is faithful on mixed fermionic Gaussian states, and is additive under tensor products of even states.Faithfulness means its value is zero if and only if the state is a mixed fermionic Gaussian state.Source: B. Definition and basic properties · p. 39
• On pure states, the mixed-state bridge degree reduces to the pure-state bridge degree.Thus the pure-state theory is recovered as a special case of the mixed-state framework.Source: B. Definition and basic properties · pp. 39–40

C. Monotonicity under post-selected Gaussian operations

• The mixed-state bridge degree is non-increasing under post-selected Gaussian operations, but is not a monotone under the full class of Gaussian protocols.The paper attributes this boundary to faithfulness only on fermionic Gaussian states, not the larger set of convex-Gaussian states.Source: C. Monotonicity under post-selected… · p. 40
• The mixed-state monotonicity result extends the paper’s Gaussian-conversion no-go theorems to mixed states by replacing the pure-state degree with its mixed-state counterpart.An approximate version can also be developed by following the pure-state construction.Source: C. Monotonicity under post-selected… · p. 41

A. Bounds on Gaussian fidelity

• Bounds relating the second moment MΛ to Gaussian fidelity FG are converted into corresponding bounds for bridge fidelity FΛ0, which is used in the Gaussianity test.The bridge fidelity is directly accessible from Bell sampling.Source: A. Bounds on Gaussian fidelity · p. 41
• MΛ can be estimated to accuracy ε with probability at least 1 − δ using Bell samples from two copies of the state.The section also gives a worst-case sample bound and an adaptive improvement when the bridge degree or MΛ is small.Source: A. Bounds on Gaussian fidelity · p. 42
• An adaptive estimator achieves ε accuracy with high probability without requiring prior knowledge of the bridge degree.It stops when its empirical error bound is at most ε.Source: A. Bounds on Gaussian fidelity · p. 42

B. A Gaussianity test via Bell sampling

• The Bell-sampling test accepts only if every observed eigenvalue is zero; it has perfect completeness and is optimal among two-copy tests with perfect completeness.Its acceptance operator is the projection onto the span of two-copy fermionic Gaussian states.Source: B. A Gaussianity test via Bell sampling · p. 43
• If each Bell sample produces a nonzero eigenvalue with probability at least ε/n², then for N ≥ (n²/ε) log(1/δ), the probability all N yield zero and incorrectly accept is smaller than δ.Source: B. A Gaussianity test via Bell sampling · p. 43
• For t-doped Gaussian states, Gaussianity testing has a sample guarantee independent of system size n and retains perfect completeness.The bound follows by replacing n with 4t in the general test.Source: B. A Gaussianity test via Bell sampling · p. 44
• System-size-independent sample complexity beyond few-gate states is conjectured, not established, although the few-gate result covers states arbitrarily close to Gaussian.The paper notes that such a general guarantee would improve the general test.Source: B. A Gaussianity test via Bell sampling · p. 44
• The tolerant test distinguishes promised cases when ε := β/n^2 − 2α > 0 and α = O(ε), with success probability at least 1 − δ.The section also describes an alternative MΛ-based test with a stricter promise gap, α < β^2/(4n^2).Source: B. A Gaussianity test via Bell sampling · p. 44

IX. CERTIFYING MATCHGATE-INVARIANT STATE 2-DESIGNS

• For matchgate-invariant ensembles, approximate 2-design certification reduces to estimating the total variation distance between the ensemble and Haar bridge spectral distributions from Bell-sampling data.The ensemble distribution encodes the second-order matchgate-invariant content.Source: §IX · p. 45
• Exact 2-design certification for matchgate-invariant ensembles uses O(n^1/4/ε^2) Bell samples.The paper also reports that an exact 2-design generated by a t-doped Gaussian protocol must include at least one state requiring Ω(n) non-Gaussian gates.Source: §IX · p. 48
• For approximate designs, the paper reports non-Gaussian gate lower bounds for t-doped Gaussian generation and a corresponding tolerant certification procedure.The certification estimates D(E) from Bell samples.Source: §IX · pp. 47–48
• The distance D(E) can be estimated to additive accuracy ε from Õ(sqrt(n)/ε^2) Bell samples.This yields a tolerant approximate 2-design test for matchgate-invariant ensembles with the same scaling.Source: §IX · pp. 47–48

A. Discussion

• The bridge spectral distribution and Bell sampling organize the framework, reducing structural and computational questions to statistical questions about pψ.The paper describes the distribution as encoding the matchgate-invariant content of the two-copy state.Source: A. Discussion · p. 49
• The bridge degree yields no-go theorems for Gaussian conversion, exact-conversion irreversibility, and non-Gaussian gate-count lower bounds for fermionic state designs.Exact state 2-designs contain a state requiring Ω(n) non-Gaussian gates; approximate designs contain such states requiring Ω(n log(1/ϵ)) gates with high probability.Source: A. Discussion · p. 49

B. Open problems

• Whether a small bridge degree implies efficient classical simulation remains open, although the bridge degree lower-bounds non-Gaussian gates for state preparation.Establishing that implication would identify the bridge degree as a unifying complexity parameter for fermionic non-Gaussian computation.Source: B. Open problems · p. 49
• Bell sampling is proposed for experimental benchmarking of fermionic platforms, with near-term experiments described as an anticipated application.The discussion names ultracold atoms in optical lattices and digital quantum computers as possible platforms.Source: B. Open problems · p. 49
• For mixed states, the bridge spectral distribution is not directly accessible from copies by Bell sampling; global depolarizing noise is a setting where error mitigation can recover it.The discussion calls for extensions to broader noise models or algorithms that sample from or estimate the mixed-state distribution.Source: B. Open problems · p. 49
• Mixed-state monotones and state-agnostic witnesses remain open needs; the current fidelity witness requires prior knowledge of a high-fidelity reference state.No efficiently computable mixed-state monotone is currently known, according to the discussion.Source: B. Open problems · p. 49
• The tolerant Gaussianity test's accept case assumes input trace distance O(1/n) from an FGS, and whether it extends to a constant-gap regime remains open.The discussion also leaves open whether general-state Gaussianity testing can achieve sample complexity independent of system size.Source: B. Open problems · p. 50
• The state-design results cover ensembles from t-doped Gaussian circuits, leaving unitary designs and higher-order matchgate commutants as extensions.The proposed higher-order direction concerns a k-copy analogue of the bridge spectral distribution.Source: B. Open problems · p. 50

Appendix A: Connection to generalized Pl¨ucker hierarchies

• The particle-preserving Plücker hierarchy recovers Slater determinants at k=1, exhausts the particle-preserving Hilbert space at k=n+1, and its degree is monotone under particle-preserving Gaussian protocols.The monotonicity gives the hierarchy a resource-theoretic interpretation.Source: Appendix A · p. 50

1. Error mitigation of the bridge spectral distribution

• Under global depolarizing noise, the measured distribution is ηpψ(λ) + (1 − η)pI(λ), with η = (1 − p)^2; inversion reconstructs the ideal distribution.The noise parameter can be estimated from the same Bell-sampling data, making the mitigation procedure classical post-processing.Source: §1 · p. 51

2. Error-mitigated lower bound on the bridge degree

• The error-mitigated estimator certifies populated sectors from Bell-sampling data and lower-bounds the underlying pure-state bridge degree with probability at least 1 − α under global depolarizing noise.A certified sector is one whose residual exceeds its confidence threshold; certified sectors belong to the ideal distribution's support.Source: §2 · pp. 52–53
• The sample bound uses Hoeffding's inequality for a distribution-independent confidence guarantee; sharper variance-aware inequalities such as Bernstein may reduce sample requirements.For estimating bridge degree, only the sector with the largest magnitude among occupied sectors needs certification.Source: §2 · p. 53