⚛️ quantum physics

Exponential lower bounds on the fermionic Gaussian rank of magic states and the bosonic coherent state rank of Fock states

This paper establishes exponential lower bounds on the fermionic Gaussian rank of magic states and proves that the coherent state border rank of bosonic Fock states equals the product of their mode occupations, thereby resolving a long-standing conjecture and advancing the understanding of classical simulation complexity for quantum systems.

Original authors: Oliver Reardon-Smith

Published 2026-10-05

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Oliver Reardon-Smith

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the quest to understand how the universe works at its smallest scales, physicists have long relied on a powerful trick: if a system is simple enough, we can calculate its behavior with a standard computer. For decades, a specific class of quantum systems—those involving particles that follow strict rules of exclusion and symmetry, known as fermions—could be simulated efficiently. These systems, often described as "free" or "Gaussian," behave in a predictable, orderly fashion that classical machines can handle without breaking a sweat. However, to build a truly powerful quantum computer, scientists must introduce a special ingredient that breaks this order. They call these ingredients "magic states." These are highly complex quantum configurations that, when added to the simple systems, unlock the ability to perform calculations that are impossible for classical computers to keep up with. The central question for researchers has been: just how much extra work does a classical computer need to do to simulate these magic states? The answer lies in a number called the "rank," which essentially counts how many simple, orderly pieces are required to build a single complex, magic piece.

For years, scientists knew that this number had to be large, but they could not prove exactly how large. They knew it grew quickly as you added more magic states, but the best mathematical proofs only showed it growing at a slow, quadratic pace, while the most basic simulations suggested it could grow exponentially. This gap left a huge uncertainty in the field. If the number grew slowly, it might be possible to simulate these powerful quantum computers on ordinary machines after all. If it grew exponentially, it confirmed that quantum computers would remain a distinct and superior class of machine. In a recent study, Oliver Reardon-Smith from the Centre for Theoretical Physics of the Polish Academy of Sciences has finally narrowed this gap for a specific, critical type of magic state. By developing a new mathematical method, the researcher proved that the number of simple pieces needed to build these complex states does not just grow quickly; it explodes exponentially, with a lower bound of roughly 1.4 raised to the power of the number of copies. While the paper notes that a large gap remains between this new lower bound and the known upper bound of 2 raised to the power of the number of copies, and that the exact value of the rank within this region is completely unknown for more than two copies, this result significantly strengthens the evidence for exponential complexity.

The study focuses on a specific four-particle configuration, a state that acts as a fundamental building block for quantum logic, capable of swapping the positions of particles. The researcher asked a straightforward question: if you take two of these states and combine them, how many simple, orderly states do you need to add together to recreate the result? Previous methods could not rule out the possibility that a small number of simple states might suffice. Reardon-Smith's work demonstrates that this is impossible. For just two copies of the state, the proof shows that you need at least four simple states to reconstruct it. When you scale this up to many copies, the requirement does not just double; it multiplies by a factor of roughly 1.4 for every single new copy you add. This means that as you add more magic states, the computational effort required to simulate them on a classical computer skyrockets, confirming that these systems are indeed intractable for classical machines, at least within the proven lower bounds.

To reach this conclusion, the researcher employed a technique that acts like a high-resolution microscope for mathematical structures. Instead of trying to build the complex state from scratch, the method analyzes the state by projecting it into a different mathematical space. Imagine trying to understand the shape of a complex 3D object by looking at its shadow; if the shadow is simple, the object might be simple, but if the shadow is incredibly complex, the object must be complex. In this case, the researcher constructed a specific matrix, a grid of numbers representing the state, and proved that for the magic states, this grid is always full of independent information. In contrast, for the simple, orderly states, the grid is always very thin and repetitive. By comparing the "thickness" of these grids, the researcher showed that no matter how you try to combine the simple states, you can never generate the thickness required to match the magic state unless you use a vast number of them. This method provided an unbreakable lower bound, proving that the complexity is inherent and unavoidable.

The findings also extend beyond the specific four-particle state to a broader class of quantum systems involving light and sound waves, known as bosons. In this realm, the researcher addressed a long-standing guess about how many simple wave patterns are needed to create a specific, highly excited state of light. The study confirmed that the number of patterns required is exactly equal to the product of the number of particles in each mode plus one. This result settles a debate that had lingered in the field, showing that the complexity of these light-based states is determined by the specific distribution of particles across modes. Furthermore, the study looked at what happens when the simulation is not perfect. In the real world, computers often work with approximations, accepting a tiny bit of error to save time. The researcher proved that even if you allow for a small margin of error, the number of simple states required remains almost as high as the exact number. The complexity does not vanish just because you are willing to be slightly less precise.

This work is significant because it removes a major doubt about the power of quantum computers. For some time, there was a lingering hope that clever mathematical tricks might allow classical computers to simulate these magic states efficiently, perhaps by finding a way to describe them with fewer pieces than expected. This study closes that door for the specific states examined, at least regarding the proven lower bounds. It confirms that the "magic" is real and that the computational cost of simulating it is at least exponential, growing at a rate of roughly 1.4 per copy. The results suggest that as quantum computers scale up, adding more of these magic states will make them increasingly difficult for classical machines to mimic, securing the advantage of quantum technology. While the exact number of pieces needed for larger systems remains a subject for future refinement, as the gap between the lower and upper bounds is still wide, the direction is now clear: the complexity grows at a rate that ensures quantum computers will remain a unique and powerful tool, far beyond the reach of classical simulation.

Technical Summary: Exponential Lower Bounds on Fermionic Gaussian and Bosonic Coherent State Ranks

Problem Statement
Recent classical simulation algorithms for quantum mechanics rely on decomposing "magic" states (non-free states) into linear combinations of "free" states (e.g., stabilizer states, fermionic Gaussian states, or bosonic coherent states). The computational cost of these simulations is governed by the rank of the magic state—the minimum number of free states required for such a decomposition. While exponential upper bounds are known for the stabilizer and fermionic Gaussian ranks of magic states, rigorous lower bounds have been scarce. For the stabilizer rank, the best known lower bounds are quadratic ( $\tilde{\Omega}(k^2)$ ), and for the fermionic Gaussian rank of magic states, no bounds beyond trivial constants were previously established. Similarly, in the bosonic context, while Ref. [1] proved superpolynomial lower bounds for the coherent-state rank of Fock states, the exact value remained a conjecture. This work addresses the lack of unconditional exponential lower bounds for these ranks.

Methodology
The paper employs a generalized flattening map approach, utilizing matrix-valued functions of statevectors to derive rank lower bounds. The core technique involves constructing a matrix $M(\psi)$ where columns correspond to the action of a specific set of linear operators (e.g., Majorana monomials or specific differential operators) on the target state $|\psi\rangle$ . By the subadditivity of matrix rank, if $|\psi\rangle = \sum_{i=1}^r \alpha_i |f_i\rangle$ , then $\text{rank}(M(\psi)) \leq \sum \text{rank}(M(|f_i\rangle))$ .

Fermionic Case:
- Operators: The author defines maps $C_p(\psi)$ where columns are generated by applying degree- $p$ Majorana monomials to the state.
- Target State: The focus is on the tensor product of $k$ copies of the 4-qubit magic state $|M\rangle = \frac{1}{\sqrt{2}}(|0000\rangle + |1111\rangle)$ .
- Analysis: The rank of $C_p(|M\rangle^{\otimes k})$ (numerator) is lower-bounded by counting orthogonal vectors generated by the stabilizer group of the magic state, utilizing combinatorial arguments involving cosets of the projective Pauli group. The rank of $C_p(|0\rangle)$ (denominator, representing a Gaussian state) is upper-bounded using geometric series estimates.
- Approximate Rank: For $\delta$ -approximate rank, the author utilizes the Eckart–Young–Mirsky theorem, relating the Frobenius norm distance between the target and its approximation to the singular values of the flattened matrix.
- Small $k$ Exact Rank: For $k=2$ , the asymptotic method yields a weak bound ( $r \geq 3$ ). To prove $r \geq 4$ , the author utilizes Spin(16, $\mathbb{C}$ ) invariants. They map the problem to the second secant variety of the spinor variety and use Gröbner bases to construct invariant polynomials that vanish on the set of states with rank $\leq 3$ but are non-zero on $|M\rangle^{\otimes 2}$ .
Bosonic Case:
- Operators: The author defines a "flattening" matrix $M^m$ for a Fock state $|m\rangle = |m_1, \dots, m_n\rangle$ , indexed by vectors $p, q$ in a specific range, with entries derived from Fock basis coefficients.
- Analysis: They prove that for any coherent state, this matrix has rank 1. Conversely, for the Fock state $|m\rangle$ , the matrix has full rank $d = \prod_j (1+m_j)$ .
- Approximate Rank: Robust bounds are derived using the fidelity $F$ between the target and the approximation, leveraging the continuity of the matrix rank and Cauchy-Schwarz inequalities on the Frobenius norm.

Key Contributions and Results

Fermionic Gaussian Rank (Exact):
The paper proves that the exact fermionic Gaussian rank of $|M\rangle^{\otimes k}$ is lower-bounded by:
$r \geq \frac{8}{9(k+1)} \left( \frac{27(8 + 2\sqrt{7})}{256} \right)^k \approx \frac{8}{9(k+1)} (1.4018)^k$
This establishes an unconditional exponential lower bound ( $\Omega(1.4^k)$ ) for the first time for this specific class of magic states.
Fermionic Gaussian Rank (Approximate):
For a $\delta$ -approximate decomposition, the rank is lower-bounded by the exact bound multiplied by a factor of $(1-\delta^2)$ .
Exact Rank for $k=2$ :
Using Spin(16, $\mathbb{C}$ ) invariants and Gröbner bases, the author proves that the exact rank of $|M\rangle^{\otimes 2}$ is exactly 4. This implies that for any $k \geq 2$ , the rank is at least 4, improving upon the trivial bound of 2.
Generalization to Non-Gaussian States:
Using Lemma 2, the author shows that the rank of any tensor product of $k$ fixed-parity non-Gaussian states is at least the rank of $|M\rangle^{\otimes k}$ . Thus, the exponential lower bound applies broadly to tensor products of non-Gaussian states, though the author notes the bound may be loose for states with more than 4 qubits due to the reduction method.
Bosonic Coherent State Rank:
The paper proves Conjecture 1 from Ref. [1]: The coherent state border rank of an $n$ -mode Fock state $|m_1, \dots, m_n\rangle$ is exactly $\prod_{j=1}^n (1+m_j)$ .
- For the specific case of $|1\rangle^{\otimes n}$ , the rank is $2^n$ .
- Robust bounds for approximate rank are provided, scaling with the fidelity of the approximation.

Significance and Claims
The paper claims to provide the first unconditional exponential lower bounds for the fermionic Gaussian rank of magic states, addressing a significant gap in the complexity-theoretic understanding of classical simulation limits. While the base of the exponential ( $\approx 1.4$ ) is smaller than the known upper bound ($2$), the result is a rigorous step forward from previous polynomial or constant bounds.

In the bosonic context, the work resolves a specific conjecture regarding the exact border rank of Fock states, confirming the exponential growth ( $2^n$ ) for the $|1\rangle^{\otimes n}$ state. The author emphasizes the broad applicability of their method, noting its connection to algebraic geometry (secant varieties, flattening maps) and its potential utility in other areas like entanglement theory, though they explicitly state that applying these specific matrix rank methods to the stabilizer rank of qubit magic states (e.g., $|T\rangle$ ) faces significant obstacles due to the properties of the Clifford group.

The author modestly notes that while their bounds are exponential, they do not yet rule out polynomial rank for small numbers of copies (beyond $k=2$ where they prove $r=4$ ) and that the reduction from general non-Gaussian states to the 4-qubit case likely yields loose bounds for larger systems. The work also highlights the potential implications for the resource theory of fermionic non-Gaussianity, though it does not propose new experimental protocols.

Technical Summary: Exponential Lower Bounds on Fermionic Gaussian and Bosonic Coherent State Ranks

More like this