Kerdock Codes Determine Unitary 2-Designs

Abstract

The non-linear binary Kerdock codes are known to be Gray images of certain extended cyclic codes of length $N=2^m$ over ${\mathbb{Z}}_4$. We show that exponentiating these ${\mathbb{Z}}_4$-valued codewords by $ı\triangleq \sqrt{-1}$ produces stabilizer states, that are quantum states obtained using only Clifford unitaries. These states are also the common eigenvectors of commuting Hermitian matrices forming maximal commutative subgroups (MCS) of the Pauli group. We use this quantum description to simplify the derivation of the classical weight distribution of Kerdock codes. Next, we organize the stabilizer states to form $N+1$ mutually unbiased bases and prove that automorphisms of the Kerdock code permute their corresponding MCS, thereby forming a subgroup of the Clifford group. When represented as symplectic matrices, this subgroup is isomorphic to the projective special linear group PSL($2,N$). We show that this automorphism group acts transitively on the Pauli matrices, which implies that the ensemble is Pauli mixing and hence forms a unitary $2$-design. The Kerdock design described here was originally discovered by Cleve et al. (arXiv:1501.04592), but the connection to classical codes is new which simplifies its description and translation to circuits significantly. Sampling from the design is straightforward, the translation to circuits uses only Clifford gates, and the process does not require ancillary qubits. Finally, we also develop algorithms for optimizing the synthesis of unitary $2$-designs on encoded qubits, i.e., to construct logical unitary $2$-designs. Software implementations are available at https://github.com/nrenga/symplectic-arxiv18a, which we use to provide empirical gate complexities for up to $16$ qubits.

arXiv comment16 pages double-column, 4 figures, and some circuits. Accepted to 2019 Intl. Symp. Inf. Theory (ISIT), and PDF of the 5-page ISIT version is included in the arXiv package

References in corpus (27)

• Good Quantum Error-Correcting Codes Exist
• Improved Simulation of Stabilizer Circuits
• A Theory of Fault-Tolerant Quantum Computation
• Exact and Approximate Unitary 2-Designs: Constructions and Applications
• Simple Quantum Error Correcting Codes
• Scalable Noise Estimation with Random Unitary Operators
• Characterizing Quantum Gates via Randomized Benchmarking
• Quantum advantage with shallow circuits
• Evenly distributed unitaries: on the structure of unitary designs
• Quantum Data Hiding
• Random Quantum Circuits are Approximate 2-designs
• The Clifford group, stabilizer states, and linear and quadratic operations over GF(2)
• A decoupling approach to the quantum capacity
• Fault-tolerant conversion between the Steane and Reed-Muller quantum codes
• An Introduction to Quantum Error Correction and Fault-Tolerant Quantum Computation
• Fault-tolerant quantum computation with few qubits
• Optimizing quantum process tomography with unitary 2-designs
• Unitary designs and codes
• How to efficiently select an arbitrary Clifford group element
• Decoupling with unitary approximate two-designs
• Shorter stabilizer circuits via Bruhat decomposition and quantum circuit transformations
• Fault-Tolerant Quantum Computing in the Pauli or Clifford Frame with Slow Error Diagnostics
• Multi-qubit Randomized Benchmarking Using Few Samples
• Unitary $2$-designs from random $X$- and $Z$-diagonal unitaries
• Synthesis of Logical Clifford Operators via Symplectic Geometry
• Low rank matrix recovery from Clifford orbits
• Minimax quantum state estimation under Bregman divergence

Cited by in corpus (2)

• Sampling Overhead Analysis of Quantum Error Mitigation: Uncoded vs. Coded Systems
• Logical Clifford Synthesis for Stabilizer Codes