Quantum divisible code

Quantum divisible code[1–3]

Description

A level-\(\nu\) quantum divisible code is a CSS code whose \(X\)-type stabilizers form a \(\nu\)-even linear binary code in the symplectic representation and which admits a transversal gate at the \(\nu\)th level of the Clifford hierarchy. A CSS code is doubly even (triply even) if all \(X\)-type stabilizers have weight divisible by four (eight), i.e., if they form a doubly even (triply even) linear binary code.

The definition can be generalized to weakly \(\nu\)-divisible (see, e.g., Ref. [4]), which means that there exist some disjoint qubit subsets \(M^{\pm}\) such that \begin{align} | x \cap M^{+} | - | x \cap M^{-} | \equiv 0 \mod \nu \tag*{(1)}\end{align} for all rows \(x\) of the code's \(X\)-type stabilizer generator matrix. CSS codes satisfying the above with \(\nu = 2\) (\(\nu = 4\), \(\nu = 8\)) are called weak even (weak doubly even, weak triply even). This generalization reduces to the original definition when \(M^{+}\) is the full set of qubits, and \(M^{-}\) the empty set.

An alternative definition [5,6], not used here, is a CSS code defined from two linear binary codes \(C_{1,2}\) such that it is quantum divisible with \(\nu > 1\), and all weights in each coset of \(C_2\) in \(C_1\) are congruent to \(\nu\). For example [6], if \(C_2\) is the first-order RM\((1,m)\) code, and \(C_1/ C_2\) consists of quadratic forms with a bounded rank, then \([[n = 2m − 1, 1 \leq k \leq 1 + \sum_{i=1}^{m-4}(m − i), d = 3]]\) is a family of such codes.

Transversal Gates

Doubly even codes can yield a transversal \(S\) gate, while triply even codes yield a logical \(T\) gate for odd \(n\) via physical action of \(T\) gates on each qubit [7].If the \(X\)-type stabilizers of a CSS code form an \(\nu\)-even classical code, and if all \(X\)-type logicals are \((\nu-1)\)-even, then the code admits a diagonal transversal gate in the \(\nu\)th level of the Clifford hierarchy [8; Prop. 8].

Gates

The \([[2m − 1, 1 \leq k \leq 1 + \sum_{i=1}^{m-4}(m − i), 3]]\) quantum divisible code family can serve as outer codes of either the five-qubit \([[5,1,3]]\) or Steane \([[7,1,3]]\) code to realize a \(T\) gate on the inner code [6]. For example, when \(m=5\) (\(m=6\)), the resulting \([[31,5,3]]\) (\([[63,7,3]]\)) code yields the \(T\) gate on the inner five-qubit (Steane) code.

Fault Tolerance

The \(T\) gate realized by concatenating members of the \([[2m − 1, 1 \leq k \leq 1 + \sum_{i=1}^{m-4}(m − i), 3]]\) quantum divisible code family with either the five-qubit \([[5,1,3]]\) or Steane \([[7,1,3]]\) code is fault-tolerant and does not require magic-state distillation [6]. The gate is performed on the inner five-qubit/Steane code and does require encoding and decoding algorithms to pass between the inner and outer codes.

Realizations

Triply even codes can yield secure multi-party quantum computation [9].

Cousins

Divisible code— The \(X\)-type stabilizers of a level-\(\nu\) quantum divisible code form a \(\nu\)-even linear binary code.
\([2^m,m+1,2^{m-1}]\) First-order RM code— Quantum divisible codes can be constructed out of first-order RM\((1,m)\) codes [6].
Concatenated qubit code— A fault-tolerant \(T\) gate on the five-qubit or Steane code can be obtained by concatenating with particular quantum divisible codes [6].
Five-qubit perfect code— A fault-tolerant \(T\) gate on the five-qubit code can be obtained by concatenating with particular quantum divisible codes [6].
\([[7,1,3]]\) Steane code— A fault-tolerant \(T\) gate on the Steane code can be obtained by concatenating with particular quantum divisible codes [6].
Quasi-cyclic code— Certain double circulant codes can be used to construct doubly even \([[55,1,11]]\) and \([[87,1,15]]\) codes [10].
Quantum Reed-Muller code— Fault-tolerant universal computation can be achieved via code switching between the \([[127,1,15]]\) self-dual doubly even punctured quantum RM code and the \([[127,1,7]]\) triply even punctured quantum RM code [11].
Doubled color code— Doubled color codes are subsystem codes constructed using a generalization of the doubling transformation [12] that combines doubly even linear binary codes to make triply even codes. The doubling transformation is a special case of level lifting (from two to three) [13; Sec. VI.D].
Quantum quadratic-residue (QR) code— Qubit quantum QR codes are doubly even and admit transversal implementations of the single-qubit Clifford group [4]. They yield a family of high-distance triorthogonal and weak triply even codes via the doubling transformation [4]; such codes admit transversal implementations of the \(T\) gate.

Member of code lists

Primary Hierarchy

Quantum Domain

Qubit Kingdom

Qubit codeQECC Quantum

Union stabilizer (USt) codeQECC Quantum

Qubit stabilizer codeStabilizer Hamiltonian-based Qubit QECC Quantum

Coherent-parity-check (CPC) code

Qubit CSS codeCSS Stabilizer Qubit Hamiltonian-based QECC Quantum

Generalized quantum divisible code

Parents

Generalized quantum divisible code

Generalized level-\(\nu\) quantum divisible codes reduce to quantum level-\(\nu\) divisible codes when \(t\) is a vector with \(\pm 1\) entries. The classical code formed by their \(X\)-type stabilizer generator matrix is \(\nu\)-even [13; pg. 10]. Both types of codes realize transversal gates outside of the Clifford group.

Quantum divisible code

Children

\([[3k + 8, k, 2]]\) triorthogonal code

\([[49,1,5]]\) triorthogonal code

\([[2^r-1,1,3]]\) simplex code

\([[2^r-1,1,3]]\) simplex codes come from RM\((1,m=r)\) codes, which are \((r-1)\)-even [14,15], and admit transversal gates at levels of the Clifford hierarchy. Building a tower of generalized divisible codes by starting with the Steane code yields the \([[2^r-1,1,3]]\) simplex codes [13; Sec. VI.B].

References

[1]: A. J. Landahl and C. Cesare, “Complex instruction set computing architecture for performing accurate quantum \(Z\) rotations with less magic”, (2013) arXiv:1302.3240
[2]: E. T. Campbell and M. Howard, “Unified framework for magic state distillation and multiqubit gate synthesis with reduced resource cost”, Physical Review A 95, (2017) arXiv:1606.01904 DOI
[3]: J. Haah and M. B. Hastings, “Codes and Protocols for DistillingT, controlled-S, and Toffoli Gates”, Quantum 2, 71 (2018) arXiv:1709.02832 DOI
[4]: S. P. Jain and V. V. Albert, “High-distance codes with transversal Clifford and T-gates”, (2024) arXiv:2408.12752
[5]: J. Hu, Q. Liang, and R. Calderbank, “Designing the Quantum Channels Induced by Diagonal Gates”, Quantum 6, 802 (2022) arXiv:2109.13481 DOI
[6]: J. Hu, Q. Liang, and R. Calderbank, “Divisible Codes for Quantum Computation”, (2022) arXiv:2204.13176
[7]: S. Bravyi and A. Cross, “Doubled Color Codes”, (2015) arXiv:1509.03239
[8]: C. Vuillot and N. P. Breuckmann, “Quantum Pin Codes”, IEEE Transactions on Information Theory 68, 5955 (2022) arXiv:1906.11394 DOI
[9]: P. A. Mishchenko and K. Xagawa, “Secure multiparty quantum computation protocol for quantum circuits: The exploitation of triply even quantum error-correcting codes”, Physical Review A 110, (2024) arXiv:2206.04871 DOI
[10]: A. M. Steane, “Space, Time, Parallelism and Noise Requirements for Reliable Quantum Computing”, Fortschritte der Physik 46, 443 (1998) arXiv:quant-ph/9708021 DOI
[11]: A. Gong and J. M. Renes, “Computation with quantum Reed-Muller codes and their mapping onto 2D atom arrays”, (2024) arXiv:2410.23263
[12]: K. Betsumiya and A. Munemasa, “On triply even binary codes”, Journal of the London Mathematical Society 86, 1 (2012) arXiv:1012.4134 DOI
[13]: J. Haah, “Towers of generalized divisible quantum codes”, Physical Review A 97, (2018) arXiv:1709.08658 DOI
[14]: R. J. McEliece, “On periodic sequences from GF(q)”, Journal of Combinatorial Theory, Series A 10, 80 (1971) DOI
[15]: R. J. McEliece, “Weight congruences for p-ary cyclic codes”, Discrete Mathematics 3, 177 (1972) DOI

Page edit log

Jingzhen Hu (2022-05-04) — most recent
Victor V. Albert (2022-05-04)

Cite as:

“Quantum divisible code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/quantum_divisible

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/quantum/qubits/stabilizer/magic/k-divisible/quantum_divisible.yml.