Quantifying Nonstabilizerness of Codeword-Stabilized Codes

Abstract

Universal quantum computation requires non-Clifford gates, which stabilizer codes can provide transversally only up to a finite level of the Clifford hierarchy. Non-stabilizer codes are not subject to this bound and are the natural candidates to fill the gap. However, it is difficult to efficiently evaluate the nonstabilizerness (or magic) of non-stabilizer codes. Here, we resolve this problem for codeword-stabilized (CWS) codes by showing that the nonstabilizerness of a CWS code is determined by the difference structure of its codewords. Whenever a Sidon set of the required size exists, the most magical codes are related to the Sidon sets, whose pairwise differences are all distinct. Structural analysis demonstrates that nonstabilizerness is invariant under coset closure, giving rise to non-stabilizer codes with arbitrarily many logical qubits and constant nonstabilizerness. Nonstabilizerness of whole code families becomes exactly computable, and we obtain closed-form values for the Kerdock codes. Moreover, we reveal a tradeoff between nonstabilizerness and transversal gates. For a code with $k$ logical qubits, a diagonal transversal gate that is non-Clifford on $t$ coordinates forces the nonstabilizerness benchmark to be at most $2(k-t)$. These results reduce the search for codes with high nonstabilizerness and for transversal non-Clifford gates to classical counting problems, to which the standard tools of additive combinatorics apply.