Improved bounds on stabilizer extent and Clifford rank
Abstract
We prove that every pure state of stabilizer rank at most k has stabilizer extent at most 2O(√(klog(k+1))), and establish the analogous bound for the squared Clifford coefficient norm of Clifford-rank-k operators. This implies stabilizer fidelity at least 2−O(√(klog(k+1))), resolving the quantitative conjecture of (Mehraban-Tamasbi, STOC, 2025), and proves an Ω(n2/log n) lower bound for the approximate stabilizer rank of tensor powers of any non-stabilizer qubit state. The latter result generalizes the best-known lower bound for tensor powers of T-states (Mehraban-Tamasbi, STOC, 2024) to arbitrary non-stabilizer qubit states, including magic states. As a consequence of the Clifford rank--norm inequality, we obtain an Ω(n2/log n) lower bound for exact representations of n-bit AND function by quadratic phases, improving the previous best-known linear bound. Further consequences rule out pseudorandom state and unitary ensembles with approximate stabilizer and Clifford rank O((log n)2/loglog n), respectively, a log n improvement over prior work (Kalra-Sinha, Quantum, 2026). We also obtain tomography algorithms for states of stabilizer rank at most k, with poly(n)2O(√(klog(k+1))) time and copy complexity, a nearly square-root improvement in the exponent over the best-known algorithm.
Related
- Clifford-hierarchy stabilizer formalism with applications to twisted quantum doubles
- A three-eighths upper bound on the stabilizer-rank exponent of face-center magic states
- A note on tomography of states with low stabilizer rank
- Stabilizer entropy cones as self-dual slices of linear rank cones: a five-party gap and dependence on the local dimension
- Improved Transversal Non-Clifford Gates from Cup Products
BibTeX
@misc{sinha2026improved,
title = {{Improved bounds on stabilizer extent and Clifford rank}},
author = {Pulkit Sinha and Benjamin Lovitz},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.06819},
eprint = {2610.06819},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.06819},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Improved bounds on stabilizer extent and Clifford rank
AU - Pulkit Sinha
AU - Benjamin Lovitz
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2610.06819
UR - https://arxiv.org/abs/2610.06819
AB - We prove that every pure state of stabilizer rank at most k has stabilizer extent at most 2^O(√(klog(k+1))), and establish the analogous bound for the squared Clifford coefficient norm of Clifford-rank-k operators. This implies stabilizer fidelity at least 2^−O(√(klog(k+1))), resolving the quantitative conjecture of (Mehraban-Tamasbi, STOC, 2025), and proves an Ω(n^2/log n) lower bound for the approximate stabilizer rank of tensor powers of any non-stabilizer qubit state. The latter result generalizes the best-known lower bound for tensor powers of T-states (Mehraban-Tamasbi, STOC, 2024) to arbitrary non-stabilizer qubit states, including magic states. As a consequence of the Clifford rank--norm inequality, we obtain an Ω(n^2/log n) lower bound for exact representations of n-bit AND function by quadratic phases, improving the previous best-known linear bound. Further consequences rule out pseudorandom state and unitary ensembles with approximate stabilizer and Clifford rank O((log n)^2/loglog n), respectively, a log n improvement over prior work (Kalra-Sinha, Quantum, 2026). We also obtain tomography algorithms for states of stabilizer rank at most k, with poly(n)2^O(√(klog(k+1))) time and copy complexity, a nearly square-root improvement in the exponent over the best-known algorithm.
ER -