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 <inline-formula> <tex-math notation="LaTeX">$N = 2^{m}$ </tex-math></inline-formula> over <inline-formula> <tex-math notation="LaTeX">$\mathbb {Z}_{4}$ </tex-math></inline-formula>. We show that exponentiating these <inline-formula> <tex-math notation="LaTeX">$\mathbb {Z}_{4}$ </tex-math></inline-formula>-valued codewords by <inline-formula> <tex-math notation="LaTeX">$i \triangleq \sqrt {-1}$ </tex-math></inline-formula> 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 <italic>quantum</italic> description to simplify the derivation of the <italic>classical</italic> weight distribution of Kerdock codes. Next, we organize the stabilizer states to form <inline-formula> <tex-math notation="LaTeX">$N+1$ </tex-math></inline-formula> 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(<inline-formula> <tex-math notation="LaTeX">$2,N$ </tex-math></inline-formula>). We show that this automorphism group acts transitively on the Pauli matrices, which implies that the ensemble is <italic>Pauli mixing</italic> and hence forms a unitary 2-design. The <italic>Kerdock</italic> design described here was originally discovered by Cleve <italic>et al.</italic> (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 <italic>logical</italic> unitary 2-designs. Software implementations are available at <uri>https://github.com/nrenga/symplectic-arxiv18a</uri>, which we use to provide empirical gate complexities for up to 16 qubits.