Magic states, pivotal for universal quantum computation via classically simulable Clifford gates, often undergo decomposition into resourceless stabilizer states, facilitating simulation through classical means. This approach yields three operationally significant metrics: stabilizer rank, fidelity, and extent. We extend these simulation methods to encompass matchgate circuits (MGCs), and define equivalent metrics for this setting. We begin with an investigation into the algebraic constraints defining Gaussian states, marking the first explicit characterisation of these states. The explicit description of Gaussian states is pivotal to our methods for tackling all the simulation tasks. Central to our inquiry is the concept of Gaussian rank -- a pivotal metric defining the minimum terms required for decomposing a quantum state into Gaussian constituents. This metric holds paramount significance in determining the runtime of rank-based simulations for MGCs featuring magic state inputs. The absence of low-rank decompositions presents a computational hurdle, thereby prompting a deeper examination of fermionic magic states. We find that the Gaussian rank of 2 instances of our canonical magic state is 4 under symmetry-restricted decompositions. Additionally, our numerical analysis suggests the absence of low-rank decompositions for 2 or 3 copies of this magic state. Further, we explore the Gaussian extent, a convex metric offering an upper bound on the rank. We prove the Gaussian extent's multiplicative behaviour on 4-qubit systems, along with initial strides towards proving its sub-multiplicative nature in general settings. One important result in that direction we present is an upper bound on the Gaussian fidelity of generic states.
Magic states, pivotal for universal quantum computation via classically simulable Clifford gates, often undergo decomposition into resourceless stabilizer states, facilitating simulation through classical means. This approach yields three operationally significant metrics: stabilizer rank, fidelity, and extent. We extend these simulation methods to encompass matchgate circuits (MGCs), and define equivalent metrics for this setting. We begin with an investigation into the algebraic constraints defining Gaussian states, marking the first explicit characterisation of these states. The explicit description of Gaussian states is pivotal to our methods for tackling all the simulation tasks. Central to our inquiry is the concept of Gaussian rank -- a pivotal metric defining the minimum terms required for decomposing a quantum state into Gaussian constituents. This metric holds paramount significance in determining the runtime of rank-based simulations for MGCs featuring magic state inputs. The absence of low-rank decompositions presents a computational hurdle, thereby prompting a deeper examination of fermionic magic states. We find that the Gaussian rank of 2 instances of our canonical magic state is 4 under symmetry-restricted decompositions. Additionally, our numerical analysis suggests the absence of low-rank decompositions for 2 or 3 copies of this magic state. Further, we explore the Gaussian extent, a convex metric offering an upper bound on the rank. We prove the Gaussian extent's multiplicative behaviour on 4-qubit systems, along with initial strides towards proving its sub-multiplicative nature in general settings. One important result in that direction we present is an upper bound on the Gaussian fidelity of generic states.
Recent algorithms for classical simulation of quantum mechanics have runtime whose superpolynomial component is given by a linear dependence on the number of terms required to write large tensor products of certain "magic" states as superpositions of "free" states (which may be stabilizer states, fermionic Gaussian states or others). Surprisingly little is known about the number of terms in such decompositions, called ranks (e.g. the stabilizer rank, fermionic-Gaussian rank etc.). For complexity theoretic reasons they are expected to grow exponentially in the number of tensor factors but, while exponential upper bounds are known for both the stabilizer and fermionic-Gaussian rank of magic states; the best known lower bounds on the stabiliser rank are quadratic, and no bounds on the fermionic-Gaussian rank are known beyond fixed constants. In this work we prove that any fermionic Gaussian decomposition of ∣M⟩⊗k consists of Ω(1.4k) terms. Here ∣M⟩ is the most standard magic state for fermionic linear optics: the 4 qubit state that may be consumed to implement a swap gate. We also prove essentially matching bounds on the δ-approximate rank of the same state, lower bounding it by the same quantity that bounds the exact rank, multiplied by a factor of 1−δ2. Our results on exact fermionic Gaussian rank apply directly to any product of k fixed parity non-Gaussian states, although the same is not true of the approximate rank. Finally, we prove that the coherent state border rank of an n-mode bosonic Fock state with mj bosons in mode j is exactly ∏j(1+mj), answering a conjecture of Ref. [1] and obtain lower bounds on the approximate coherent state rank given by the same quantity multiplied by a function of the fidelity of the approximation, emphasizing the broad applicability of the method we employ.
Fermionic Gaussian circuits can be simulated efficiently on a classical computer, but become universal when supplemented with non-Gaussian operations. Similar to stabilizer circuits augmented with non-stabilizer resources, these non-Gaussian circuits can be simulated classically using rank- or extent-based methods. These methods decompose non-Gaussian states or operations into Gaussian ones, with runtimes that scale polynomially with measures of non-Gaussianity such as the rank and the extent -- quantities that typically grow exponentially with the number of non-Gaussian resources. Current fermionic rank- and extent-based simulators have mostly been limited to Gaussian circuits with magic-state injection. Extending them to mixed states and non-unitary channels has been hindered by the lack of known extent-optimized decompositions for physically relevant gates and noisy channels. In this work, we address this gap. First, we derive analytic decompositions for key non-Gaussian gates and channels, including decompositions for arbitrary two-qubit fermionic gates which are provably optimal for diagonal gates or those acting on Jordan-Wigner-adjacent qubit pairs. Second, we show that stochastic Pauli noise can reduce the effective extent of non-Gaussian rotation gates, but that fermionic magic is substantially more robust to such noise than stabilizer magic. Finally, we demonstrate how these decompositions can accelerate classical sampling from the output distribution of a quantum circuit. This involves a generalization of existing sparsification methods, previously limited to convex-unitary channels, to circuits involving intermediate measurements and feed-forward. Our decompositions also yield speedups for emulating noisy Pauli rotations with quasiprobability simulators in the large-angle/arbitrary-strength-noise and small-angle/low-noise parameter regimes.
Magic states were introduced in the context of Clifford circuits as a resource that elevates classically simulatable computations to quantum universal capability, while maintaining the same gate set. Here we study magic states in the context of matchgate (MG) circuits, where the notion becomes more subtle, as MGs are subject to locality constraints. Nevertheless a similar picture of gate-gadget constructions applies, and we show that every pure fermionic state which is non-Gaussian, i.e., which cannot be generated by MGs from a computational basis state, is a magic state for MG computations. This result has significance for prospective quantum computing implementation in view of the fact that MG circuit evolutions coincide with the quantum physical evolution of noninteracting fermions.
The power and limitations of classical simulation are central to understanding quantum computational advantages. A leading simulation paradigm is based on coherent decomposition into classically tractable free states where the decomposition rank determines the simulation complexity. Proving strong lower bounds on this number is a notoriously difficult and mathematically rich problem, as exemplified by the qubit stabilizer rank problem. Here, we study the Gaussian version of this problem in both bosonic and fermionic systems and establish robust exponential lower bounds on Gaussian rank. In particular, we prove that for every pure non-Gaussian state on finitely many modes, with definite parity in the fermionic case, the approximate border Gaussian rank of its tensor powers grows at least exponentially at any fixed norm error below one. Our proofs combine reduction to four modes with Majorana spectral bounds for fermions, and Gaussian postselection with an entropy-based rank bound for bosons. As concrete examples, we derive explicit exponential lower bounds for the four-mode fermionic GHZ state and the bosonic single-photon state. The bosonic results require no assumption on the energy of the target state. Our results show that non-Gaussianity universally entails exponential Gaussian decomposition complexity, setting fundamental limitations on decomposition-based classical simulation of bosonic and fermionic systems.
Distinct Clifford orbits of magic states can exhibit different stabilizer ranks at small tensor powers. We establish this for qutrits, where the single-qutrit Clifford group has four inequivalent orbits of magic states: Strange, Norrell, Hadamard-eigenstate, and the qutrit T-state, but a nontrivial upper bound on the asymptotic exponent had been pinned down for only the qutrit T-state. For the other three orbits we give explicit stabilizer decompositions, yielding upper bounds on the per-copy asymptotic stabilizer-rank exponent: γS≤log3(2)/2≈0.316 for the Strange state, and γH3,γN≤log3(4)/3≈0.421 for the Hadamard-eigenstate and Norrell orbits, all strictly below the prior γT3≤1/2 baseline. We also prove the first nontrivial Ω(m/logm) asymptotic lower bounds for the Hadamard-eigenstate and Norrell orbits, and exhibit two-qutrit Clifford circuits that convert two copies of these states into an injectable phase state with constant success probability, enabling constant-overhead injection of one non-Clifford diagonal gate per orbit. In the case of qubits, we give a closed-form decomposition of the qubit T-type orbit at four copies matching the existing γT≤log2(3)/4≈0.396 exponent via a direct algebraic identity rather than an entangled cat-state construction. An open-source library stabrank accompanies the paper, with Lean 4 proof formalizations of all the decompositions.
Classically hard-to-simulate quantum states, or "magic" states, are prerequisites to quantum advantage, highlighting an apparent separation between classically and quantumly tractable problems. Classically simulable states such as Clifford circuits on stabilizer states, free bosonic states, free fermions, and matchgate circuits are all in some sense Gaussian. While free bosons and fermions arise from quadratic Hamiltonians, recent works have demonstrated that bosonic and qudit systems converge to Gaussians and stabilizers under convolution. In this work, we similarly identify convolution for fermions and find efficient measures of non-Gaussian magic in pure fermionic states. We demonstrate that three natural notions for the Gaussification of a state—(1) the Gaussian state with the same covariance matrix, (2) the fixed point of convolution, and (3) the closest Gaussian in relative entropy—coincide by proving a central limit theorem for fermionic systems. We then utilize the violation of Wick's theorem and the matchgate identity to quantify non-Gaussian magic in addition to a SWAP test.