A Caltech Library Service

Kerdock Codes Determine Unitary 2-Designs

Can, Trung and Rengaswamy, Narayanan and Calderbank, Robert and Pfister, Henry D. (2020) Kerdock Codes Determine Unitary 2-Designs. IEEE Transactions on Information Theory, 66 (10). pp. 6104-6120. ISSN 0018-9448.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


The non-linear binary Kerdock codes are known to be Gray images of certain extended cyclic codes of length N=2^m over Z₄. We show that exponentiating these Z₄-valued codewords by i≜√-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. (2016), 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, which we use to provide empirical gate complexities for up to 16 qubits.

Item Type:Article
Related URLs:
URLURL TypeDescription ItemConference Paper ItemCode
Rengaswamy, Narayanan0000-0002-2369-3159
Calderbank, Robert0000-0003-2084-9717
Pfister, Henry D.0000-0001-5521-4397
Additional Information:© 2020 IEEE. Manuscript received April 23, 2019; accepted July 24, 2020. Date of publication August 11, 2020; date of current version September 22, 2020. This work was supported in part by the National Science Foundation (NSF) under Grant 1718494 and Grant 1908730. This article was presented in part at the 2019 IEEE International Symposium on Information Theory. (Trung Can and Narayanan Rengaswamy contributed equally to this work.)
Funding AgencyGrant Number
Subject Keywords:Heisenberg-Weyl group, Pauli group, quantum computing, clifford group, symplectic geometry, Kerdock codes, Delsarte-Goethals codes, gray map, stabilizer states, mutually unbiased bases, unitary t-designs
Issue or Number:10
Record Number:CaltechAUTHORS:20201012-134120392
Persistent URL:
Official Citation:T. Can, N. Rengaswamy, R. Calderbank and H. D. Pfister, "Kerdock Codes Determine Unitary 2-Designs," in IEEE Transactions on Information Theory, vol. 66, no. 10, pp. 6104-6120, Oct. 2020, doi: 10.1109/TIT.2020.3015683
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:105987
Deposited By: Tony Diaz
Deposited On:12 Oct 2020 20:57
Last Modified:12 Oct 2020 20:57

Repository Staff Only: item control page