Quantifying Nonstabilizerness of Codeword-Stabilized Codes

arXiv:2608.22017 · quant-ph · Submitted 2026-08-22 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: We're looking at the paper: "Quantifying Nonstabilizerness of Codeword-Stabilized Codes".

Mira: The gist The nonstabilizerness of a CWS code state is governed by a single classical object, the difference-set multiplicity A(x) of its classical code C,

Kai: First, who's behind it and why it matters.

Paper summary: Mira: Thinking about the title "Quantifying Nonstabilizerness of Codeword-Stabilized Codes," what I see is that they've successfully moved this question from a vague intuition about non-Clifford content to a rigorous, classical measurement tied to translation collision.

Kai: It means we now have a way to calculate the exact nonstabilizerness for these codes, and they point us toward Sidon sets as the optimal structures for maximizing that magic value.

Lev: For building hardware, this tells us that if we want high fidelity, we should look at codes whose difference sets are sparse—Sidon-like structures—because those maximize the nonstabilizerness within the bound of 2k.

Mira: The implication is that instead of searching randomly for codes with high magic, we can use additive combinatorics to construct them, which gives us a predictable path for finding good quantum error correction.

Kai: They also proved that this nonstabilizerness level doesn't change even if you wrap the code in a coset closure; it just depends on the resulting quotient structure.

Lev: So, when we design larger systems, we don't need to re-evaluate everything; we just need to look at the new quotient space and apply the same formulas they derived for things like Kerdock codes.

Mira: This work provides a quantitative bridge between abstract algebraic structures and the practical requirements of implementing non-Clifford gates in actual quantum circuits.

Kai: It turns what was a qualitative intuition into a concrete budget problem, which is exactly what we need when we're trying to design physical qubits and gate sequences.

Conclusion: Kai: So we’re wrapping up on this paper, "Quantifying Nonstabilizerness of Codeword-Stabilized Codes." The big picture here is that they figured out how to measure the non-Clifford content in these specific quantum error correction codes without getting lost in complicated math.

Mira: Right, so they've essentially found a way to pin down the "magic" of these codeword-stabilized states to a classical object—specifically, the difference structure of their classical code.

Lev: From an engineering standpoint, that means we can actually calculate how much non-Clifford stuff is in the state before we even start building physical hardware for it. That’s a huge step for planning qubit requirements.

Kai: It seems like they've moved this from being just a theoretical curiosity about stabilizer codes to something with concrete numbers, tied to things like Sidon sets when those difference structures are sparse.

Mira: Exactly, the most magical codes they found are directly linked to these Sidon sets where all the pairwise differences of the codewords are unique. That’s really neat because it gives us a clear structural target for designing better codes.

Lev: And they showed that this nonstabilizerness stays constant even if you just take a coset closure, meaning we can build these codes with lots of logical qubits and still have that same magic level. The overhead is predictable.

Kai: So the implication is that instead of searching blindly for magic-rich codes, we use additive combinatorics to construct them with known properties. It turns a hard search into a counting problem.

Mira: It really shows how deep the connection is between these abstract algebraic structures and the actual resource budget needed for quantum computation. The constraints they find—like the 2k bound—are really practical limits for what we can achieve in terms of gate complexity versus magic capacity.

Lev: And that gate-nonstabilizerness tradeoff they found, where a diagonal transversal gate on t coordinates forces the nonstabilizerness to be at most two times the gap, that’s a very usable constraint for designing actual quantum circuits.

Kai: So it boils down to this paper giving us tools—classical tools from additive combinatorics—to find codes with high magic and figure out how much transversal non-Clifford gate power they need for those codes.

Mira: And it opens the door to understanding what limits the power of these stabilizer states in a much more precise way than before.

Lev: Next time we talk about this, I want to look at how their exact values for things like Kerdock codes work out based on these Sidon properties they found.

Beijing Institute of Technology

quant-ph

Submitted: 2026-08-22

Updated: 2026-10-19

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 83/100

The gist: The gist The nonstabilizerness of a CWS code state is governed by a single classical object, the difference-set multiplicity A(x) of its classical code C, which reduces the problem to additive

Key concepts

Nonstabilizerness (Magic)
This measures how much a quantum state, like a CWS code's uniform superposition, deviates from being perfectly Clifford. High nonstabilizerness indicates significant non-Clifford content, which is necessary for universal quantum computation.
Codeword-Stabilized (CWS) Codes
These are codes where the stabilizer properties are derived from the structure of the codewords themselves rather than a predefined group. They serve as natural candidates to provide non-Clifford gates needed for universal quantum computation.
Sidon Sets
A Sidon set is a set where all pairwise differences (the results of subtracting any two distinct elements) are unique. The paper shows that the most magical CWS codes are directly related to these sets, as their sparse difference structure maximizes nonstabilizerness.

Summary

The gist The nonstabilizerness of a CWS code state is governed by a single classical object, the difference-set multiplicity A(x) of its classical code C, which reduces the problem to additive combinatorics.

How it works

The paper develops a quantitative theory for the nonstabilizerness (or magic) carried by codeword-stabilized (CWS) codes and shows that this key quantity is classical, fixed by how its codewords collide under translation The most magical codes are exactly the Sidon sets whenever a Sidon set of the required size exists, whose pairwise differences are all distinct. Nonstabilizerness is unchanged by coset closure, which yields non-stabilizer codes with arbitrarily many logical qubits and constant nonstabilizerness as the number of logical qubits grows.

How it works

The magic of a code, i.e., the nonstabilizerness of its code state (the uniform superposition of its codewords), is a natural measure of the non-Clifford content the code itself carries The identity M2 = 4k−log2 E(1)(C) expresses the magic of a CWS code state in terms of the parallelogram energy E(1)(C) of its classical code, and most of the results below follow from it. This identity holds for an arbitrary code-space state once E(1)(C) is replaced by a weighted parallelogram energy E(1)ψ(C) carrying the amplitudes and phases of the state; the code state is then the flat benchmark of this family, and the magic capacity of the code space is its extremum.

How it works

The extremal problem shows that magic is maximized by Sidon sets, which have a sparsest possible difference structure, and every CWS code state obeys M2 ≤ 3k−log2(7·2k−6) < 2k The structural results show that nonstabilizerness lives on the quotient, yielding non-stabilizer codes of constant magic and arbitrarily many logical qubits Diagonal transversal gates are exactly those compatible with the period subgroup P(C) = x A(x) = m, and a logical diagonal transversal gate that is non-Clifford on t coordinates forces the code’s nonstabilizerness to be at most 2(k − t)

How it works

The paper establishes several concrete payoffs, including exact values for families like Kerdock codes, which carry a specific nonstabilizerness value based on the Sidon property Operational readings show that M2/2 lower-bounds the number of non-Clifford gates needed to realize the encoding and the cost of classically simulating the code state Furthermore, a diagonal transversal gate that is non-Clifford on t coordinates forces t ≤ k − M2/2, upgrading the Bravyi–K¨onig dichotomy from a qualitative certificate into a quantitative bound

How it works

The analysis of coset closure shows that nonstabilizerness depends only on the quotient C/S, and for Kerdock codes, this leads to exact computations where M2(K(m)) = 3(m − 1)−log2(7·2m−1−6) The gate–nonstabilizerness tradeoff is a direct application of these theorems, showing that the nonstabilizerness budget and the reach of transversal non-Clifford diagonal gates are complementary

How it works

The paper concludes that the nonstabilizerness of Sidon and coset-closure code states is within reach of small devices through Bell difference sampling The results turn the search for magic-rich codes and transversal non-Clifford gates into classical counting problems, which can be approached with standard tools from additive combinatorics

How it works

The paper provides a quantitative form of the Bravyi–K¨onig intuition by showing that the nonstabilizerness of a code state never exceeds ∼ 2k, no matter how large the physical block length, whereas a generic n-qubit state carries ∼ n bits Nonstabilizerness is invariant under coset closure and depends only on the resulting quotient The most magical codes are offered by the Sidon sets, whose difference structure is as sparse as possible

How it works

The paper provides concrete payoffs, including exact values for families like Kerdock codes, which carry a specific nonstabilizerness value based on the Sidon property Operational readings show that M2/2 lower-bounds the number of non-Clifford gates needed to realize the encoding and the cost of classically simulating the code state Furthermore, a diagonal transversal gate that is non-Clifford on t coordinates forces t ≤ k − M2/2, upgrading the Bravyi–K¨onig dichotomy from a qualitative certificate into a quantitative bound

How it works

The paper provides concrete payoffs, including exact values for families like Kerdock codes, which carry a specific nonstabilizerness value based on the Sidon property Operational readings show that M2/2 lower-bounds the number of non-Clifford gates needed to realize

Improvements for AI systems

  1. A quantitative theory of nonstabilizerness is established, reducing the question to classical combinatorics by fixing a code’s nonstabilizerness by how its codewords collide under translation. This allows AI systems to design codes whose magic content is directly maximized or controlled based on the sparsity of their difference sets, effectively optimizing code structure for specific quantum computational tasks.

  2. AI systems can be engineered to utilize the gate–nonstabilizerness tradeoff by determining whether a transversal gate is logical based on the code's period subgroup, which is defined as the set of directions that leave the code invariant—the very subgroup one quotients by. This means an AI could select non-Clifford gates that are logical for a given code structure, precisely bounded by t ≤ k − M2/2.

  3. The system can perform operational cost estimation using the derived bounds: M2(C⟩) 2 log2 c − O(1) non-Clifford (T) gates to lower-bound the number of gates needed to realize an encoding, and M2/2 lower-bounds the cost of classically simulating the code state. This provides a direct resource budget for both hardware implementation and classical simulation complexity.

  4. AI can construct codes with arbitrarily many logical qubits while maintaining constant nonstabilizerness as the number of logical qubits grows, achieved through coset closure, allowing for scalable quantum circuits where non-stabilizer codes have arbitrarily many logical qubits and constant nonstabilizerness.

Sources

Related papers