加入
Stabilizer rank of tensor powers of the T state
Decide whether the number of stabilizer states needed to write n copies of the T magic state is bounded by a polynomial in n.
shoal 2周前提交
0 个父提交
提交 214289f04cab514b68be99715016e7ad4abb5b00
+43 −0 README.md 新增 查看文件
| @@ -0,0 +1,43 @@ | ||
| 1 | +# Stabilizer rank of tensor powers of the T state | |
| 2 | + | |
| 3 | +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. | |
| 4 | + | |
| 5 | +## Problem | |
| 6 | + | |
| 7 | +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 | |
| 8 | + | |
| 9 | +$$\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\}.$$ | |
| 10 | + | |
| 11 | +**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]. | |
| 12 | + | |
| 13 | +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$. | |
| 14 | + | |
| 15 | +## Background | |
| 16 | + | |
| 17 | +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]. | |
| 18 | + | |
| 19 | +## What is known | |
| 20 | + | |
| 21 | +- 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]. | |
| 22 | +- 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]. | |
| 23 | +- 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]. | |
| 24 | +- 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]. | |
| 25 | +- Conditionally, $\chi(T^{\otimes n})$ is super-polynomial unless the permanent has polynomial-size circuits [4]. | |
| 26 | + | |
| 27 | +## What would count as progress | |
| 28 | + | |
| 29 | +- 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. | |
| 30 | +- 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. | |
| 31 | +- The exact value of $\chi(T^{\otimes 5})$, known to be at most 6 [2], with a computer-checkable certificate for the lower bound. | |
| 32 | + | |
| 33 | +## References | |
| 34 | + | |
| 35 | +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](https://doi.org/10.1103/PhysRevX.6.021043) | |
| 36 | +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](https://doi.org/10.22331/q-2021-12-20-606) | |
| 37 | +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](https://doi.org/10.22331/q-2022-02-15-652) | |
| 38 | +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](https://doi.org/10.1145/3618260.3649733) | |
| 39 | +5. P. Sinha and B. Lovitz, "Improved bounds on stabilizer extent and Clifford rank", arXiv:2610.06819 (2026). [arXiv:2610.06819](https://arxiv.org/abs/2610.06819) | |
| 40 | + | |
| 41 | +## Source | |
| 42 | + | |
| 43 | +Imported from [QIQCOP Zoo op_37f7b003ec78a028](https://qiqc-op.com/problem/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. | |