Stabilizer Ranks, Barnes Wall Lattices and Magic Monotones
Amolak Ratan Kalra, Pulkit Sinha · 2025
Read Stabilizer Ranks, Barnes Wall Lattices and Magic Monotones by Amolak Ratan Kalra, Pulkit Sinha (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-04101.txt.
Introduction
Stabilizer states are the part of quantum computing that classical machines can mimic. The cost of going beyond them is measured by stabilizer rank. Amolak Ratan Kalra and Pulkit Sinha connect Barnes Wall lattices and Clifford operations to that cost. They prove the first quantitative lower bound on stabilizer fidelity as a function of rank. The bound reproduces a known linear-by-log bound for copies of the H state. It holds even when the match is exponentially poor.
They also define a new magic monotone for pure states, the Barnes Wall norm. They bound it by the CS-count of state preparation and by stabilizer ranks, and the CS-count bound is tight. A fidelity amplification algorithm trades approximation error against rank and lets approximate decompositions compose across tensor products. The paper also gives a simpler proof that product states with maximal stabilizer ranks exist and are dense.
Catalog record
| CREATOR | Amolak Ratan Kalra, Pulkit Sinha |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 65 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-04101
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Stabilizer Ranks, Barnes Wall Lattices and Magic Monotones Amolak Ratan Kalra, Pulkit Sinha Abstract In 2024, Kliuchnikov and Schönnenbeck showed a connection between the Barnes Wall lattices, stabilizer states and Clifford operations. In this work, we study their results and relate them to the problem of lower bounding stabilizer ranks. We show the first quantitative lower bound on stabilizer fidelity as a function of stabilizer ranks, which reproduces the linear-by-log lower bound for χ δ ( | H ⟩ ⊗ n ) \chi_{\delta}({\ket{H}^{\otimes n}}) , i.e., on the approximate stabilizer rank of | H ⟩ ⊗ n \ket{H}^{\otimes n} . In fact, we show that the lower bound holds even when the fidelity between the approximation and | H ⟩ ⊗ n \ket{H}^{\otimes n} is exponentially small, which is currently the best lower bound in this regime. This is shown via an intermediate result between stabilizer fidelity and stabilizer rank , which also gives us an Ω ( log n / log log n ) \Omega(\log n/\log\log n) lower bound on the stabilizer rank of pseudorandom quantum states. Next, we define a new magic monotone for pure states, the Barnes Wall norm , and its corresponding approximate variant. We upper bound these monotones by the C S CS -count of state preparation and also by the stabilizer ranks. In particular, the upper bound given by the C S CS -count is tight, in the sense that we exhibit states that achieve the bound. Apart from these results, we give a Fidelity Amplification algorithm, which provides a trade-off between approximation error and the stabilizer rank. As a corollary, it gives us a way to compose approximate stabilizer decompositions into approximate decompositions of their tensor products. In particular this recovers the best known approximation for | H ⟩ ⊗ n {\ket{H}^{\otimes n}} . Furthermore we show that this best known approximation is effectively a Barnes Wall lattice approximation. It can also be shown that the Barnes wall norm of this approximation asymptotically matches the upper bound we present. Finally, we provide an alternative, elementary proof of the existence and density of product states with maximal stabilizer ranks, which was first proven by Lovitz and Steffan (2022), where they used results from algebraic geometry. 1 Introduction Understanding the boundary between classical and quantum computation is a problem of vital importance in the field of quantum information. One way to approach this problem is via the lens of classical simulation of quantum circuits. In this arena, we attempt to quantify the cost of simulating different families of quantum circuits by giving explicit classical algorithms to simulate them and then study how the efficiency of these algorithms scales with the number of input qubits. The first landmark result in this approach was given by Gottesman and Knill [ 1 ] , which showed that arbitrary quantum circuits using stabilizer states and measurements can be classically simulated efficiently (see also [ 2 ] ). While these stabilizer circuits are not universal, they can be made to perform universal quantum computation by supplementing them with special non-stabilizer states called magic states. In [ 3 ] , Bravyi, Smith and Smolin described a new algorithm to simulate these universal quantum circuits. They decomposed the magic states as linear combinations of a small number of stabilizer states, and then simulated the stabilizer circuits on this combination instead. The minimum number of such stabilizer states needed for a given magic state \ket{\psi} is referred to as the stabilizer rank of \ket{\psi} , denoted as \chi(\ket{\psi}) . For such simulation algorithms, \chi({\ket{\psi}}) is effectively the most important metric of efficiency or computational complexity. In particular, if we are able to efficiently find polynomially sized decompositions for magic states like \ket{H}^{\otimes n} , then this has various complexity-theoretic implications such as BQP=BPP and even P=NP [ 4 ] . Also, instead of finding an exact decomposition in terms of stabilizers, we can also hope to approximate the magic states with linear combination of stabilizer states instead. The corresponding rank in this case is called the \delta -approximate stabilizer rank, denoted as \chi_{\delta}(\ket{\psi}) . The problem of finding optimal bounds for \chi(\ket{\psi}) and \chi_{\delta}(\ket{\psi}) for tensor powers of magic states, termed the stabilizer rank problem, has received a lot of attention, with various works chipping away at both the upper and lower bounds, with most results focusing on the ranks of \ket{H}^{\otimes n} or (equivalently) \ket{T}^{\otimes n} . Here, \ket{H}=\cos\frac{\pi}{8}\ket{0}+\sin\frac{\pi}{8}\ket{1} , and \ket{T}=\frac{1}{\sqrt{2}}(\ket{0}+e^{i\pi/4}\ket{1}) . For \chi(\ket{H}^{\otimes n}) , the first lower bound of \Omega(\sqrt{n}) was given by Bravyi, Smith and Smolin in [ 3 ] , with a corresponding upper bound of O(2^{n/2}) . In a series of works, [ 3 , 5 , 6 , 4 , 7 , 8 , 9 ] , these lower and upper bounds were improved to \Omega(\frac{n^{2}}{\mathrm{polylog}(n)}) and O(2^{0.4n}) respectively. For \chi_{\delta}(\ket{H}^{\otimes n}) , the best known lower and upper bounds are \Omega(\frac{n^{2}}{\mathrm{polylog}(n)}) [ 7 ] and O(2^{0.23n}) [ 5 ] for constant \delta . In order to study the stabilizer rank, various other measures of stabilizer complexities have been introduced, including but not limited to: stabilizer fidelity, stabilizer extent and stabilizer alignment (see [ 5 ] ), with emphasis on relating these to each other and as well as to stabilizer ranks [ 10 , 5 , 11 ] . In particular, we know that tensor products of magic states, such as \ket{H}^{\otimes n} , have exponentially large stabilizer extent, and exponentially small stabilizer fidelity. 1.1 Overview of the Main Results In a recent work, Kliuchnikov and Schönnenbeck [ 12 ] demonstrated that for n qubit Barnes Wall lattices, the automorphism group of the lattice, as well as the set of minimum length vectors, are upto phase exactly the Clifford unitaries and stabilizer states respectively. In our work, we study the problem of bounding stabilizer ranks and other notions of stabilizer complexities from the perspective of these recent results. Till now none of the techniques developed to study stabilizer ranks make use of this particular connection. Another reason to pursue this connections is that similar number theoretic techniques have been used to give synthesis algorithms for single qubits with close to optimal T -count [ 13 , 14 ] . We first use such a lattice interpretation in Section 3 to prove the first quantitative lower bound on stabilizer fidelity based on the stabilizer rank. Such a bound was shown to exist by Mehraban and Tahmasbi [ 10 ] , but the result was only existential and did not give a concrete bound. We do this via an intermediate result between the stabilizer rank and stabilizer extent: Theorem 1 (Upper bound on stabilizer extent) . Let \ket{\phi} be a pure state such that \ket{\phi}=\sum_{j=1}^{k}c_{i}\ket{s_{j}} , where \ket{s_{j}} ’s are all linearly independent stabilizer states, c_{j}\in\mathbb{C} . Then, we have that \left\|\mathbf{c}\right\|_{1}\leq\sqrt{e}\cdot(2k)^{\frac{2k+1}{2}} . This theorem is established using Minkowski’s theorem for lattices. At an intuitive level, it tells us that the determinant of the Gram matrix of lattice generators is large, if the minimal vector of the lattice is long. When we consider the lattice generated by the stabilizer states in the above theorem, since this determinant is large,