Asymptotic growth of the stabilizer rank of T-state tensor powers

Problem

Does the exact stabilizer rank of the tensor powers of the single-qubit magic state \(|T\rangle\) grow polynomially in the number of copies, or is it not polynomially bounded? The state is

\begin{equation} |T\rangle := 2^{-1/2}\bigl(|0\rangle + e^{i\pi/4}|1\rangle\bigr), \tag{1} \end{equation}

and, for an \(n\)-qubit pure state \(|\psi\rangle\), its exact stabilizer rank is

\begin{equation} \chi(\psi) := \min\Bigl\{r : |\psi\rangle = \sum_{j=1}^{r} c_j\,|\varphi_j\rangle \text{ for some } c_j \in \mathbb{C} \text{ and } n\text{-qubit stabilizer states } |\varphi_j\rangle\Bigr\}, \tag{2} \end{equation}

where an \(n\)-qubit stabilizer state is the common \(+1\) eigenstate of \(n\) independent commuting Hermitian Pauli operators. Which of the two alternatives holds for \(\chi\bigl(|T\rangle^{\otimes n}\bigr)\): does there exist a constant \(k\) with \(\chi\bigl(|T\rangle^{\otimes n}\bigr) \le n^{k}\) for all sufficiently large \(n\), or is \(\chi\bigl(|T\rangle^{\otimes n}\bigr)\) not bounded by any polynomial in \(n\)? The best current bounds are

\begin{equation} \Omega\!\left(\frac{n^{2}}{\operatorname{polylog} n}\right) \le \chi\bigl(|T\rangle^{\otimes n}\bigr) \le O\bigl(2^{\alpha n}\bigr), \qquad \alpha = \tfrac{1}{4}\log_{2} 3 \le 0.3963, \tag{3} \end{equation}

which leave both alternatives open. A sharper sub-question is whether the exponential rate \(\gamma = \lim_{n\to\infty} \frac{1}{n}\log_{2} \chi\bigl(|T\rangle^{\otimes n}\bigr)\), which exists by sub-multiplicativity of the rank under tensor product and Fekete’s lemma, is strictly positive, since Eq. (3) only pins \(\gamma\) to the interval \([0, 0.3963]\). The small-copy frontier of the quantity in Eq. (2) on copies of the state in Eq. (1) is also open: the exact values \(\chi\bigl(|T\rangle^{\otimes 2}\bigr) = 2\) and \(\chi\bigl(|T\rangle^{\otimes 3}\bigr) = 3\) are proved, while at four through seven copies only upper bounds are known, \(\chi\bigl(|T\rangle^{\otimes 4}\bigr) \le 4\), \(\chi\bigl(|T\rangle^{\otimes 5}\bigr) \le 6\), \(\chi\bigl(|T\rangle^{\otimes 6}\bigr) \le 6\), and \(\chi\bigl(|T\rangle^{\otimes 7}\bigr) \le 12\), the four-copy bound having since been certified as the exact value \(\chi\bigl(|T\rangle^{\otimes 4}\bigr) = 4\) by an exhaustive computer search; determine the exact values at \(t = 5\), \(6\), and \(7\).

Source

Bravyi, Smith, and Smolin introduced the quantity \(\chi\bigl(|T\rangle^{\otimes n}\bigr)\) and its use for classical simulation, explicitly posed its asymptotic scaling, observed that super-polynomial growth follows assuming universal quantum computation cannot be simulated classically in polynomial time, proved only an \(\Omega(\sqrt{n}\,)\) lower bound while stating that they were unable to derive an unconditional super-polynomial one, and conjectured \(\chi\bigl(|T\rangle^{\otimes n}\bigr) \ge 2^{\Omega(n)}\) [BSS16]; Bravyi, Browne, Calpin, Campbell, Gosset, and Howard sharpened the question to its polynomial-or-not form, stating that polynomial scaling of the exact or approximate stabilizer rank would entail complexity-theoretic heresies such as \(\mathsf{BQP} = \mathsf{BPP}\) or \(\mathsf{P} = \mathsf{NP}\), and that no techniques are known for proving unconditional super-polynomial lower bounds [BBC+19].

Progress

Bravyi, Smith, and Smolin introduced low-rank stabilizer decompositions of magic-state tensor powers for classical simulation and proved an \(\Omega(\sqrt{n}\,)\) lower bound on the exact stabilizer rank of tensor powers of a single-qubit magic state, finding \(\chi\bigl(|T\rangle^{\otimes 6}\bigr) = 7\) numerically, a value conjectured optimal [BSS16]; the sampling algorithm of Bravyi and Gosset for circuits dominated by Clifford gates had used approximate stabilizer decompositions [BG16].
Bravyi, Browne, Calpin, Campbell, Gosset, and Howard developed the theory of exact and approximate stabilizer rank; the proved exact values are \(\chi\bigl(|T\rangle^{\otimes 2}\bigr) = 2\) and \(\chi\bigl(|T\rangle^{\otimes 3}\bigr) = 3\), and past three copies only upper bounds are known, namely \(\chi\bigl(|T\rangle^{\otimes 4}\bigr) \le 4\), \(\chi\bigl(|T\rangle^{\otimes 5}\bigr) \le 6\), and \(\chi\bigl(|T\rangle^{\otimes 7}\bigr) \le 12\) as tabulated by Qassim, Pashayan, and Gosset, and no finite set of copy counts can settle the asymptotic growth in either direction [BBC+19], [QPG21].
The upper bound in Eq. (3) is due to Qassim, Pashayan, and Gosset: entangled six-qubit magic cat states of stabilizer rank exactly \(3\) give \(\chi\bigl(|T\rangle^{\otimes n}\bigr) \le O\bigl(2^{\alpha n}\bigr)\), with the exponent attained only in the limit of an infinitely long chain of contracted cat states, improving the previous \(\chi\bigl(|T\rangle^{\otimes 12}\bigr) \le 47\), that is \(\alpha \le 0.463\), of Kocia [Koc20], and disproving the conjectured value \(7\) at six copies by showing \(\chi\bigl(|T\rangle^{\otimes 6}\bigr) \le 6\) [QPG21].
Peleg, Shpilka, and Volk proved an \(\Omega(n)\) lower bound on the exact stabilizer rank of tensor powers of single-qubit magic states, improving the \(\Omega(\sqrt{n}\,)\) of Bravyi, Smith, and Smolin, as well as \(\Omega(\sqrt{n}/\log n)\) for \(\delta\)-close approximate rank, the first nontrivial approximate bound; these direct exact-rank techniques stop at linear [PSV22].
Two further exact-rank techniques reach only linear lower bounds: higher-order Fourier analysis [Lab22], and the new techniques of Lovitz and Steffan [LS22].
Mehraban and Tahmasbi proved \(\chi_{\delta}\bigl(|T\rangle^{\otimes m}\bigr) = \Omega\bigl((1-\delta^{2})^{2} m^{2}/\operatorname{polylog} m\bigr)\) for every \(0 < \delta < 1\), where \(\chi_{\delta}(\psi)\) is the least stabilizer rank of a pure state within \(2\)-norm distance \(\delta\) of \(|\psi\rangle\); fixing any constant \(\delta\) and using the monotonicity \(\chi \ge \chi_{\delta}\) yields the lower bound in Eq. (3), the only super-linear technique known. They further show that polynomial exact rank would imply \(\mathsf{P}^{\#\mathsf{P}} \subseteq \mathsf{P}/\mathsf{poly}\) (Theorem 1.6), give a conditional super-polynomial approximate-rank bound under average-case \(\#\mathsf{P}\)-hardness (Theorem 1.11), and prove that a quadratic approximate bound alone cannot yield super-quadratic exact bounds in general (Lemma A.5) [MT24].
Kalra and Sinha proved the first quantitative lower bound on the stabilizer fidelity as a function of stabilizer rank, via Barnes-Wall lattices and magic monotones, but for stabilizer rank it reproduces only the existing lower bound, linear up to a logarithmic factor, on the approximate rank of the tensor powers of the Hadamard magic state \(|H\rangle\), together with an elementary proof of the Lovitz-Steffan density of maximal-stabilizer-rank product states; neither side of Eq. (3) for \(|T\rangle^{\otimes n}\) moves [KS25].
Labib and Russo gave explicit stabilizer decompositions for the three previously unbounded qutrit magic-state orbits, with per-copy exponents \(0.316\) and \(0.421\), and the first \(\Omega(m/\log m)\) lower bounds for the qutrit Hadamard-eigenstate and Norrell orbits; for qubits, a closed-form four-copy decomposition of stabilizer rank exactly \(3\) for the face-center orbit (T-type in their naming, which swaps T and H relative to this record: their H-type orbit contains the \(|T\rangle\) of Eq. (1)) merely matches the exponent \(\alpha\) of Eq. (3), and an exhaustive search there rigorously confirms \(\chi\bigl(|T\rangle^{\otimes 4}\bigr) = 4\), so neither side of the qubit question moves [LR26].

Comment

What remains unresolved is the alternative itself: neither an \(n^{O(1)}\) upper bound nor a super-polynomial lower bound on \(\chi\bigl(|T\rangle^{\otimes n}\bigr)\) is known, and the two sides of Eq. (3) have stood since 2021 and 2024 respectively. A polynomial upper bound established merely as a rank statement would not by itself give a uniform simulation: a bound on \(\chi\) does not construct a stabilizer decomposition of \(|T\rangle^{\otimes m}\) or compute its coefficients, and by gadgetizing every T gate through state injection into a Clifford circuit acting on \(|T\rangle^{\otimes m}\) with the decomposition supplied as polynomial advice, Theorem 1.6 of [MT24] draws from such a bound only the nonuniform consequence \(\mathsf{P}^{\#\mathsf{P}} \subseteq \mathsf{P}/\mathsf{poly}\), so it is believed false. A polynomial-time classical strong-simulation algorithm for all Clifford+T circuits with polynomially many T gates would need the additional hypothesis that some polynomial-length decomposition of \(|T\rangle^{\otimes m}\) can be constructed, with coefficients computable to the required precision, in polynomial time, as the explicit cat-state constructions behind Eq. (3) can be. Settling the super-polynomial alternative requires a lower bound that rules out \(\chi\bigl(|T\rangle^{\otimes n}\bigr) \le n^{k}\) for every constant \(k\); a bound of one fixed exponent, such as \(n^{2+\varepsilon}\) for some \(\varepsilon > 0\), would improve the current \(\Omega\bigl(n^{2}/\operatorname{polylog} n\bigr)\) but is still polynomial and would leave the alternative open. A genuinely super-polynomial lower bound would be the first unconditional bound beyond the \(\Omega\bigl(n^{2}/\operatorname{polylog} n\bigr)\) level, since the direct methods of Peleg, Shpilka, and Volk, Labib, and Lovitz and Steffan stop at linear and a quadratic approximate bound alone cannot give super-quadratic exact bounds in general. Constant-factor improvements — a smaller \(\alpha\) in Eq. (3), sharpening the lower bound to \(\Omega(n^{2})\), or new small-\(n\) exact values — do not settle the question. The zoo’s record “Universal purification with classically simulable operations” shares the boundary between stabilizer and magic resources but asks a dynamical resource-conversion question about purification fidelity, not a state-decomposition question.

References

[BSS16]: S. Bravyi, G. Smith, and J. A. Smolin, “Trading classical and quantum computational resources,” Physical Review X 6, 021043 (2016).DOI arXiv
[BG16]: S. Bravyi and D. Gosset, “Improved classical simulation of quantum circuits dominated by Clifford gates,” Physical Review Letters 116, 250501 (2016).DOI
[BBC+19]: S. Bravyi, D. Browne, P. Calpin, E. Campbell, D. Gosset, and M. Howard, “Simulation of quantum circuits by low-rank stabilizer decompositions,” Quantum 3, 181 (2019).DOI arXiv
[Koc20]: L. Kocia, “Improved strong simulation of universal quantum circuits,”(2020).arXiv
[QPG21]: H. Qassim, H. Pashayan, and D. Gosset, “Improved upper bounds on the stabilizer rank of magic states,” Quantum 5, 606 (2021).DOI arXiv
[PSV22]: S. Peleg, A. Shpilka, and B. L. Volk, “Lower Bounds on Stabilizer Rank,” Quantum 6, 652 (2022).DOI arXiv
[Lab22]: F. Labib, “Stabilizer rank and higher-order Fourier analysis,” Quantum 6, 645 (2022).DOI
[LS22]: B. Lovitz and V. Steffan, “New techniques for bounding stabilizer rank,” Quantum 6, 692 (2022).DOI
[MT24]: S. Mehraban and M. Tahmasbi, “Quadratic Lower bounds on the Approximate Stabilizer Rank: A Probabilistic Approach,” in Proceedings of STOC 2024 (2024).DOI arXiv
[KS25]: A. R. Kalra and P. Sinha, “Stabilizer Ranks, Barnes Wall Lattices and Magic Monotones,”(2025).arXiv
[LR26]: F. Labib and V. Russo, “Stabilizer rank bounds for magic-state orbits,”(2026).arXiv

Asymptotic growth of the stabilizer rank of T-state tensor powers

Problem

Source

Progress

Comment

References

Cite this problem

BibTeX

Plain text

Problem

Source

Progress

Comment

References

Related problems