skip to main content

Title: Quantum stabilizer codes, lattices, and CFTs
A bstract There is a rich connection between classical error-correcting codes, Euclidean lattices, and chiral conformal field theories. Here we show that quantum error-correcting codes, those of the stabilizer type, are related to Lorentzian lattices and non-chiral CFTs. More specifically, real self-dual stabilizer codes can be associated with even self-dual Lorentzian lattices, and thus define Narain CFTs. We dub the resulting theories code CFTs and study their properties. T-duality transformations of a code CFT, at the level of the underlying code, reduce to code equivalences. By means of such equivalences, any stabilizer code can be reduced to a graph code. We can therefore represent code CFTs by graphs. We study code CFTs with small central charge c = n ≤ 12, and find many interesting examples. Among them is a non-chiral E 8 theory, which is based on the root lattice of E 8 understood as an even self-dual Lorentzian lattice. By analyzing all graphs with n ≤ 8 nodes we find many pairs and triples of physically distinct isospectral theories. We also construct numerous modular invariant functions satisfying all the basic properties expected of the CFT partition function, yet which are not partition functions of any known CFTs. We more » consider the ensemble average over all code theories, calculate the corresponding partition function, and discuss its possible holographic interpretation. The paper is written in a self-contained manner, and includes an extensive pedagogical introduction and many explicit examples. « less
Award ID(s):
Publication Date:
Journal Name:
Journal of High Energy Physics
Sponsoring Org:
National Science Foundation
More Like this
  1. A bstract We discuss the holographic description of Narain U(1) c × U(1) c conformal field theories, and their potential similarity to conventional weakly coupled gravitational theories in the bulk, in the sense that the effective IR bulk description includes “U(1) gravity” amended with additional light degrees of freedom. Starting from this picture, we formulate the hypothesis that in the large central charge limit the density of states of any Narain theory is bounded by below by the density of states of U(1) gravity. This immediately implies that the maximal value of the spectral gap for primary fields is ∆ 1 = c /(2 πe ). To test the self-consistency of this proposal, we study its implications using chiral lattice CFTs and CFTs based on quantum stabilizer codes. First we notice that the conjecture yields a new bound on quantum stabilizer codes, which is compatible with previously known bounds in the literature. We proceed to discuss the variance of the density of states, which for consistency must be vanishingly small in the large- c limit. We consider ensembles of code and chiral theories and show that in both cases the density variance is exponentially small in the central charge.
  2. A bstract We study some special features of F 24 , the holomorphic c = 12 superconformal field theory (SCFT) given by 24 chiral free fermions. We construct eight different Lie superalgebras of “physical” states of a chiral superstring compactified on F 24 , and we prove that they all have the structure of Borcherds-Kac-Moody superalgebras. This produces a family of new examples of such superalgebras. The models depend on the choice of an $$ \mathcal{N} $$ N = 1 supercurrent on F 24 , with the admissible choices labeled by the semisimple Lie algebras of dimension 24. We also discuss how F 24 , with any such choice of supercurrent, can be obtained via orbifolding from another distinguished c = 12 holomorphic SCFT, the $$ \mathcal{N} $$ N = 1 supersymmetric version of the chiral CFT based on the E 8 lattice.
  3. Quantum error-correcting codes can be used to protect qubits involved in quantum computation. This requires that logical operators acting on protected qubits be translated to physical operators (circuits) acting on physical quantum states. We propose a mathematical framework for synthesizing physical circuits that implement logical Clifford operators for stabilizer codes. Circuit synthesis is enabled by representing the desired physical Clifford operator in CN ×N as a 2m × 2m binary sym- plectic matrix, where N = 2m. We show that for an [m, m − k] stabilizer code every logical Clifford operator has 2k(k+1)/2 symplectic solutions, and we enumerate them efficiently using symplectic transvections. The desired circuits are then obtained by writing each of the solutions as a product of elementary symplectic matrices. For a given operator, our assembly of all of its physical realizations enables optimization over them with respect to a suitable metric. Our method of circuit synthesis can be applied to any stabilizer code, and this paper provides a proof of concept synthesis of universal Clifford gates for the well- known [6, 4, 2] code. Programs implementing our algorithms can be found at
  4. Locally testable codes (LTC) are error-correcting codes that have a local tester which can distinguish valid codewords from words that are far from all codewords, by probing a given word only at a very small (sublinear, typically constant) number of locations. Such codes form the combinatorial backbone of PCPs. A major open problem is whether there exist LTCs with positive rate, constant relative distance and testable with a constant number of queries. In this paper, we present a new approach towards constructing such LTCs using the machinery of high-dimensional expanders. To this end, we consider the Tanner representation of a code, which is specified by a graph and a base code. Informally, our result states that if this graph is part of an {\em agreement expander} then the local testability of the code follows from the local testability of the base code. Agreement expanders allow one to stitch together many mostly-consistent local functions into a single global function. High-dimensional expanders are known to yield agreement expanders with constant degree. This work unifies and generalizes the known results on testability of the Hadamard, Reed-Muller and lifted codes, all of which are proved via a single round of local self-correction: the correctedmore »value at a vertex v depends on the values of all vertices that share a constraint with v. In the above codes this set includes all of the vertices. In contrast, in our setting the degree of a vertex might be a constant, so we cannot hope for one-round self-correction. We overcome this technical hurdle by performing iterative self correction with logarithmically many rounds and tightly controlling the error in each iteration using properties of the agreement expander. Given this result, the missing ingredient towards constructing a constant-query LTC with positive rate and constant relative distance is an instantiation of a base code and a constant-degree agreement expander that interact well with each other.« less
  5. Testing membership in lattices is of practical relevance, with applications to integer programming, error detection in lattice-based communication and cryptography. In this work, we initiate a systematic study of {\em local testing} for membership in lattices, complementing and building upon the extensive body of work on locally testable codes. In particular, we formally define the notion of local tests for lattices and present the following: \begin{enumerate} \item We show that in order to achieve low query complexity, it is sufficient to design one-sided non-adaptive {\em canonical} tests. This result is akin to, and based on an analogous result for error-correcting codes due to Ben-Sasson \etal\ (SIAM J. Computing 35(1) pp1--21). \item We demonstrate upper and lower bounds on the query complexity of local testing for membership in {\em code formula} lattices. We instantiate our results for code formula lattices constructed from Reed-Muller codes to obtain nearly-matching upper and lower bounds on the query complexity of testing such lattices. \item We contrast lattice testing from code testing by showing lower bounds on the query complexity of testing low-dimensional lattices. This illustrates large lower bounds on the query complexity of testing membership in {\em knapsack lattices}. On the other hand, we showmore »that knapsack lattices with bounded coefficients have low-query testers if the inputs are promised to lie in the span of the lattice. \end{enumerate}« less