Stabilizer Ranks, Barnes Wall Lattices and Magic Monotones

Technical Summary: Stabilizer Ranks, Barnes Wall Lattices and Magic Monotones

Problem Statement
The paper addresses the fundamental problem of quantifying the computational cost of simulating universal quantum circuits using classical resources. Specifically, it focuses on the stabilizer rank problem: determining the minimum number of stabilizer states required to decompose a given "magic" state (a non-stabilizer state essential for universality, such as $|H\rangle^{\otimes n}$ or $|T\rangle^{\otimes n}$). While exact decompositions define the stabilizer rank $\chi(|\psi\rangle)$, practical simulation often relies on approximate decompositions, defined by the $\delta$-approximate stabilizer rank $\chi_\delta(|\psi\rangle)$. Existing bounds for these ranks, particularly for tensor powers of magic states, have been limited, with a gap remaining between the best known lower and upper bounds. Furthermore, previous techniques for bounding these ranks have not fully utilized the algebraic structure connecting stabilizer states to specific number-theoretic lattices.

Methodology and Approach
The authors leverage a recent connection established by Kliuchnikov and Schönnenbeck (2024) between Barnes Wall (BW) lattices, stabilizer states, and Clifford operations. They utilize the fact that the automorphism group of the $n$-qubit Barnes Wall lattice corresponds to the Clifford group, and the set of minimum length vectors corresponds to stabilizer states (up to phase).

The methodology proceeds through three main technical pillars:

1. Lattice-Theoretic Bounds: The authors apply Minkowski's theorem for lattices to analyze the Gram matrix of stabilizer states. This allows them to derive quantitative relationships between the coefficients of a stabilizer decomposition and the geometry of the underlying lattice.
2. Definition of New Monotones: They introduce a new magic monotone, the Barnes Wall norm ($N(|\psi\rangle)$), defined as the squared length of the smallest vector on the Barnes Wall lattice proportional to the state $|\psi\rangle$. They also define an approximate variant, $N_\delta(|\psi\rangle)$.
3. Fidelity Amplification: The authors develop an algorithmic technique to trade off approximation error against stabilizer rank. By applying random Clifford operations (specifically $H$ and $I$ gates) and post-selecting, they demonstrate a method to reduce relative error while controlling the growth of the rank.

Key Contributions and Results

• Quantitative Lower Bound on Stabilizer Fidelity:
  The paper establishes the first quantitative lower bound on stabilizer fidelity as a function of stabilizer rank. Specifically, for a state $|\psi\rangle$ with stabilizer rank $k$ and a target state $|\phi\rangle$ with stabilizer fidelity $F_S$, the overlap is bounded by:
  $$\frac{|\langle \phi | \psi \rangle|}{\sqrt{F_S}} \leq \sqrt{e} (2k)^{\frac{2k+1}{2}}$$
  This result yields a linear-over-log lower bound ($k = \Omega(n / \log n)$) for the stabilizer rank of states with exponentially small stabilizer fidelity, such as $|H\rangle^{\otimes n}$. Crucially, this bound holds even when the approximation has only an exponentially small inner product with the target state, representing the best known lower bound in this regime.

• Lower Bounds for Pseudorandom States:
  By combining the fidelity-rank relationship with existing results on pseudorandom states, the authors derive an $\Omega(\log n / \log \log n)$ lower bound on the stabilizer rank of pseudorandom quantum states. This improves upon previous $\omega(1)$ bounds.

• The Barnes Wall Norm as a Magic Monotone:
  The authors prove that the Barnes Wall norm $N$ and its approximate variant $N_\delta$ satisfy the properties of a magic monotone:

  • Invariance under the Clifford group.
  • $N(|\phi\rangle) \geq 1$, with equality if and only if $|\phi\rangle$ is a stabilizer state.
  • Multiplicativity under tensor products: $N(|\phi\rangle \otimes |\psi\rangle) = N(|\phi\rangle)N(|\psi\rangle)$.
  • Non-increasing behavior under uniform Pauli measurements.
  • A divisibility property related to the ring of Gaussian integers $\mathbb{Z}[i]$.
    Furthermore, they show that the CS-count (number of CS gates) required to prepare a state exactly is bounded by the Barnes Wall norm, providing a tight upper bound for states that achieve this limit.

• Relation to Approximate Stabilizer Rank:
  Using a lattice approximation lemma, the authors relate the approximate Barnes Wall norm to the approximate stabilizer rank:
  $$N_{\delta+\delta_0}(|\phi\rangle) \leq \frac{2^{\chi_\delta(|\phi\rangle)}}{\delta_0^2}$$
  This establishes that high approximate Barnes Wall norms imply high approximate stabilizer ranks.

• Fidelity Amplification and Composition:
  The paper presents a Fidelity Amplification algorithm (Theorem 8). Given a stabilizer decomposition with relative error $\epsilon$ and rank $k$, the algorithm produces a decomposition with rank $O(\alpha k)$ and relative error $\epsilon/\alpha$. This allows for the composition of approximate decompositions for tensor products. Applying this to $|0\rangle^{\otimes n}$ recovers the best known approximation for $|H\rangle^{\otimes n}$ with rank $O(2^{0.23n})$. The authors demonstrate that this best-known approximation is effectively a Barnes Wall lattice approximation, asymptotically matching the upper bound derived from the Barnes Wall norm.

• Density of Maximal Rank Product States:
  The authors provide an elementary proof (using vector space and metric space structures rather than algebraic geometry) that product states with maximal stabilizer rank ($2^n$) form a dense and open subset of all product states. This confirms and simplifies previous results by Lovitz and Steffan (2022).

Significance and Claims
The paper claims to bridge a gap between number-theoretic lattice structures and quantum resource theories. By interpreting stabilizer states as minimal vectors in Barnes Wall lattices, the authors provide a new geometric framework for bounding stabilizer ranks.

The significance of the work lies in:

1. Tightening Lower Bounds: Providing the strongest known lower bounds for the stabilizer rank of $|H\rangle^{\otimes n}$ in regimes where previous techniques failed to give non-trivial results.
2. New Tools: Introducing the Barnes Wall norm as a powerful new tool (magic monotone) that connects the geometry of lattices to the complexity of state preparation (CS-count and stabilizer rank).
3. Unification: Showing that the best known approximate decompositions for magic states are not just heuristic constructions but are intrinsically linked to lattice approximations.
4. Methodological Shift: Offering a more accessible, elementary proof for the density of maximal rank states, suggesting that these techniques may be more amenable to extension into the realm of approximate stabilizer ranks compared to previous algebraic geometry approaches.

The authors conclude by outlining future directions, including generalizing the Barnes Wall norm to lattices over $\mathbb{Z}[e^{i\pi/4}]$ to address $|T\rangle$-count bounds and exploring further trade-offs between rank, error, and qubit count.