arXiv:2610.03699
Exponential lower bounds on the fermionic Gaussian rank of magic states and the bosonic coherent state rank of Fock states
Oliver Reardon-Smith
Abstract
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 $\lvert M\rangle^{\otimes k}$ consists of $Ω(1.4^k)$ terms. Here $\lvert M\rangle$ 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 $m_j$ bosons in mode $j$ is exactly $\prod_{j}(1+m_j)$, 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.
AI Summary
The paper studies how many free states are needed to express, or approximate, resource states used in decomposition-based classical simulation. It addresses fermionic Gaussian decompositions of $|M\rangle^{\otimes k}$, where $|M\rangle=(|0000\rangle+|1111\rangle)/\sqrt2$, and coherent-state decompositions of bosonic Fock states. For fermions, both the exact rank and the $\delta$-approximate rank have exponential lower bounds: the latter is at least $(1-\delta^2)\frac{8}{9(k+1)}b^k$, with $b=27(8+2\sqrt7)/256\approx1.4018$; setting $\delta=0$ gives the exact bound. The exact lower bound also applies to products containing $k$ fixed-parity non-Gaussian factors, via postselected Gaussian reductions. A separate invariant-polynomial argument proves that two copies of $|M\rangle$ have rank exactly four. For bosons, the coherent-state border rank of $|m_1,\ldots,m_n\rangle$ is exactly $\prod_j(m_j+1)$, resolving the stated conjecture for $|1\rangle^{\otimes n}$. For that state, any coherent-state superposition with fidelity $F$ requires at least $2^nF$ terms. General Fock-state fidelity bounds are also given; nonvacuum Fock states have infinite exact coherent-state rank. The proofs use linear matrix-valued flattenings and rank subadditivity. Majorana-monomial actions yield the fermionic bounds; selecting orthogonal columns makes them robust using singular-value approximation. Bosonic Hankel-type matrices give matching border-rank bounds, with finite differences supplying the constructions. The fermionic upper bound remains $2^k$, and exact ranks beyond two copies remain unknown. The general-product extension does not hold for approximate rank. Bosonic Gaussian decompositions beyond coherent states remain untreated. Independent concurrent work obtains essentially matching asymptotic fermionic results.
ChatGPT 5.6 Sol was used for literature review and some calculations
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- This work was performed independently of the interesting arXiv:2610.02172 appearing in a previous arXiv listing