Exponential lower bounds on the fermionic Gaussian rank of magic states and the bosonic coherent state rank of Fock states
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⟩⊗ k consists of Ω(1.4k) terms. Here lvert 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.
Related
- Robust exponential lower bounds for fermionic and bosonic Gaussian ranks
- Testing bosonic and fermionic Gaussian states with a constant number of copies
- Entangled measurements are necessary for optimal tomography of mixed fermionic Gaussian states and of bosonic Gaussian states near the vacuum
- Optimal testing of fermionic and bosonic Gaussian states
- Exponential de Finetti Theorems for Fermionic Gaussian States
BibTeX
@misc{reardonsmith2026exponential,
title = {{Exponential lower bounds on the fermionic Gaussian rank of magic states and the bosonic coherent state rank of Fock states}},
author = {Oliver Reardon-Smith},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.03699},
eprint = {2610.03699},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.03699},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Exponential lower bounds on the fermionic Gaussian rank of magic states and the bosonic coherent state rank of Fock states
AU - Oliver Reardon-Smith
PY - 2026
DA - 2026/10/02
PB - arXiv
DO - 10.48550/arxiv.2610.03699
UR - https://arxiv.org/abs/2610.03699
AB - 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⟩^⊗ k consists of Ω(1.4^k) terms. Here lvert 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 m_j bosons in mode j is exactly ∏_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.
ER -