Stabilizer rank of tensor powers of the T state

Quantum circuits made of Clifford gates acting on stabilizer states can be simulated efficiently on a classical computer, and adding copies of the magic state $\lvert T\rangle$ makes them universal. Classical simulators therefore write $\lvert T\rangle^{\otimes n}$ as a sum of stabilizer states, at a cost that grows with the number of terms, the stabilizer rank. This rank is expected to grow exponentially in $n$, yet no super-polynomial lower bound has been proved.

Problem

Let $\lvert T\rangle=2^{-1/2}\big(\lvert0\rangle+e^{i\pi/4}\lvert1\rangle\big)$. An $n$-qubit stabilizer state is a state $C\lvert0\rangle^{\otimes n}$ with $C$ a Clifford circuit, built from Hadamard, phase and CNOT gates; equivalently, it is the joint $+1$ eigenvector of $n$ independent commuting Pauli operators. The stabilizer rank of an $n$-qubit state $\lvert\psi\rangle$ is

$$\chi(\psi)=\min\Big\{r:\ \lvert\psi\rangle=\sum_{j=1}^{r}c_j\lvert\varphi_j\rangle,\ c_j\in\mathbb{C},\ \lvert\varphi_j\rangle \text{ stabilizer states}\Big\}.$$

Question. Is $\chi(T^{\otimes n})$ bounded by a polynomial in $n$? Bravyi, Smith and Smolin conjectured that in fact $\chi(T^{\otimes n})\ge 2^{\Omega(n)}$ [1].

Since $\chi$ is submultiplicative under tensor products, the rate $\gamma=\lim_{n\to\infty}\frac1n\log_2\chi(T^{\otimes n})$ exists, and $0\le\gamma\le\frac14\log_2 3$ [2]. Is $\gamma>0$? The same questions can be asked for the approximate rank $\chi_\delta(\psi)$, the least stabilizer rank of a vector within Euclidean distance $\delta$ of $\lvert\psi\rangle$.

Background

Bravyi, Smith and Smolin introduced simulation by low-rank stabilizer decompositions of magic states in 2016 [1]. They noted that if universal quantum computation cannot be simulated classically in polynomial time, $\chi(T^{\otimes n})$ must grow super-polynomially, and that a bound $2^{o(n)}$ would allow sub-exponential simulation of constant-depth Clifford+T circuits; they could not prove a super-polynomial bound unconditionally [1]. Up to polynomial factors, the approximate rank of $T^{\otimes n}$ bounds the cost of simulating circuits with Clifford gates and $n$ T gates (Bravyi and Gosset) [4]. Lower bounds concern decompositions into quadratic phase functions over $\mathbb{F}_2$ and are close to circuit lower bounds [3, 4].

What is known

• Upper bound: $\chi(T^{\otimes n})=O(2^{\alpha n})$ with $\alpha=\frac14\log_2 3\le0.3963$ (Qassim, Pashayan and Gosset, 2021), from decompositions built by contracting entangled cat states [2]. This improved on the exponent $\log_2(7)/6\le0.468$ from the 7-term decomposition of $T^{\otimes 6}$ found by Bravyi, Smith and Smolin, and on a later bound of about $0.463$ [1, 2]. The same paper showed $\chi(T^{\otimes 6})\le 6$, disproving the conjecture that it equals 7 [2].
• Small cases: $\chi(T^{\otimes 2})=2$ and $\chi(T^{\otimes 3})=3$, while for five, six and seven copies the best listed upper bounds are 6, 6 and 12 [2].
• Exact lower bounds: $\Omega(\sqrt n)$ [1], improved to $\Omega(n)$ by Peleg, Shpilka and Volk [3]. Three different techniques from 2022 all stop at a linear bound [4].
• Approximate lower bounds: $\Omega(\sqrt n/\log n)$ for small constant $\delta$ [3], and $\chi_\delta(T^{\otimes n})=\Omega(n^2)/\mathrm{polylog}(n)$ for every $0<\delta<1$ (Mehraban and Tahmasbi, STOC 2024) [4]. An exact decomposition is also an approximate one, so this is the best lower bound on $\chi$ as well. An October 2026 preprint by Sinha and Lovitz, not yet refereed, proves $\Omega(n^2/\log n)$ for the approximate stabilizer rank of $\psi^{\otimes n}$ for every non-stabilizer single-qubit state $\psi$ [5].
• Conditionally, $\chi(T^{\otimes n})$ is super-polynomial unless the permanent has polynomial-size circuits [4].

What would count as progress

• A lower bound on $\chi(T^{\otimes n})$ or $\chi_\delta(T^{\otimes n})$ of order $n^{2+\varepsilon}$ for some $\varepsilon>0$; a super-polynomial bound would settle the question.
• A decomposition of $T^{\otimes k}$ into fewer than $3^{k/4}$ stabilizer states for some $k$, for example at most 8 terms for $k=8$ (the listed bound is 12 [2]), which by submultiplicativity lowers $\alpha$ below $\frac14\log_2 3$. It can be checked exactly by expanding the sum.
• The exact value of $\chi(T^{\otimes 5})$, known to be at most 6 [2], with a computer-checkable certificate for the lower bound.

References

1. S. Bravyi, G. Smith and J. A. Smolin, "Trading classical and quantum computational resources", Physical Review X 6, 021043 (2016). doi:10.1103/PhysRevX.6.021043
2. H. Qassim, H. Pashayan and D. Gosset, "Improved upper bounds on the stabilizer rank of magic states", Quantum 5, 606 (2021). doi:10.22331/q-2021-12-20-606
3. S. Peleg, A. Shpilka and B. L. Volk, "Lower bounds on stabilizer rank", Quantum 6, 652 (2022). doi:10.22331/q-2022-02-15-652
4. S. Mehraban and M. Tahmasbi, "Quadratic lower bounds on the approximate stabilizer rank: a probabilistic approach", in Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC), 608–619 (2024). doi:10.1145/3618260.3649733
5. P. Sinha and B. Lovitz, "Improved bounds on stabilizer extent and Clifford rank", arXiv:2610.06819 (2026). arXiv:2610.06819

Source

Imported from QIQCOP Zoo op_37f7b003ec78a028, curated by Bikun Li, Qicheng Tang, Changhao Li, Chengkai Zhu, Minbo Gao, Zhong-Xia Shang, Bin Cheng and Naixu Guo. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.