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 2^{O(√(k log(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(√(k log(k+1)))}, resolving the quantitative conjecture of (Mehraban-Tamasbi, STOC, 2025), and proves an Ω(n²/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²/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)²/log log 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(√(k log(k+1)))} time and copy complexity, a nearly square-root improvement in the exponent over the best-known algorithm.

Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.