[Jump to code hierarchy]

Concatenated qubit code

Description

A concatenated code whose outer code is a qubit code. In other words, a qubit code that can be thought of as a concatenation of an arbitrary inner code and another qubit outer code. An inner \(C = ((n_1,K,d_1))\) and outer \(C^\prime = ((n_2,2,d_2))\) qubit code yield an \(((n_1 n_2, K, d \geq d_1d_2))\) concatenated qubit code.

Concatenating an \(((n,2,d))\) qubit code can be done recursively, with the \(r\)th level of concatenation yielding an \(((n^r,2,d^r))\) code.

Protection

Any distance-three recursively concatenated code protects against an open set of errors [1]. Concatenating stabilizer codes can help protect against catastrophic errors such as cosmic rays [2].

Decoding

The effective channel for a concatenation of codes is the composition of the codes' effective channels [3].Message passing algorithm for concatenated codes can be equivalent to ML decoding [4].

Fault Tolerance

Fault-tolerant message passing between devices [5].

Threshold

The first methods to achieve a concatenated threshold against local stochastic noise use concatenated qubit stabilizer codes [6–13]; see the book [14].

Cousins

  • Hamiltonian-based code— Concatenated stabilizer code Hamiltonians have been investigated [15].
  • Gauss' law code— The Gauss' law code can be concatenated to form a stabilizer code for fault-tolerant quantum simulation of the underlying gauge theory [16,17].
  • Amplitude-damping (AD) code— Concatenated quantum codes can protect against qubit AD [18].
  • EA qubit stabilizer code— There exist concatenated EA qubit stabilizer codes that saturate the EA quantum Griesmer and Plotkin bounds [19].
  • Amplitude-damping CWS code— Concatenated versions of amplitude-damping CWS codes have been constructed [20,21].
  • \(((n,1,2))\) Bravyi-Lee-Li-Yoshida PI code— The Bravyi-Lee-Li-Yoshida PI code can be concatenated to yield codes that have higher distance and that admit codewords with vanishing entanglement [22; Appx. D] (cf. [23]).
  • \([[2^D,D,2]]\) hypercube quantum code— The hypercube quantum code can be concatenated with a two-qubit quantum repetition code to yield a \([[2^{D+1},D,4]]\) error-detecting code family [24]. It can also be concatenated with a distance-two \(D\)-dimensional surface code to yield a \([[2^D(2^D+1),D,4]]\) error-correcting code family that admits a transversal implementation of the logical \(C^{D-1}Z\) gate [24].
  • \([[4,2,2]]\) Four-qubit code— The \(\{|\overline{00}\rangle,|\overline{01}\rangle\}\) \([[4,1,2]]\) subcode is the smallest QPC, i.e., a concatenation of a two-qubit bit-flip with a two-qubit phase-flip repetition code. Concatenations of \([[4,2,2]]\) and \(C_6\) codes yield fault-tolerant quantum computation schemes [25] admitting a post-selected threshold [26,27] (see also Ref. [28]). Concatenations of quantum Hamming codes with the \([[4,2,2]]\) and \(C_6\) codes yield fault-tolerant quantum computation with constant space and quasi-polylogarithmic time overheads [29,30].' Concatenating the \([[4,2,2]]\) code with the surface code is equivalent to removing stabilizer generators from the 4.8.8 color code [31]. The \([[4,2,2]]\) code can be concatenated with two copies of the surface code to yield the 4.6.12 color code [31]. An \([[8,1,2]]\) QPC correcting a single AD error is equivalent to a concatenation of the \(\{|\overline{01}\rangle,|\overline{11}\rangle\}\) (constant-excitation) subcode of the \([[4,2,2]]\) code with the dual-rail code [32–34]. More generally, an \([[m^2,1,m]]\) QPC corrects \(m-1\) AD errors [35]. Recursively concatenating a \([[4,1,2]]\) subcode attains a threshold [36,37].
  • Five-qubit perfect code— The recursively concatenated five-qubit code has a measurement threshold of one [38]. Code performance against general Pauli channels has been worked out [3,39].
  • \([[6,2,2]]\) \(C_6\) code— Concatenations of \([[4,2,2]]\) and \(C_6\) codes yield fault-tolerant quantum computation schemes [25] admitting a post-selected threshold [26,27] (see also Ref. [28]) and the Meier-Eastin-Knill (MEK) magic-state distillation protocols [40]. Concatenations of quantum Hamming codes with the \([[4,2,2]]\) and \(C_6\) codes yield fault-tolerant quantum computation with constant space and quasi-polylogarithmic time overheads [29,30].
  • \([[6,4,2]]\) error-detecting code— Concatenations of this code with itself yield the level-\(r\) \([[6^r,4^r,2^r]]\) many-hypercube code [41]. The \([[6,4,2]]\) code can be concatenated with the surface code to yield the 6.6.6 color code [31; Appx. A].
  • \([[8,3,2]]\) Smallest interesting color code— The \([[8,3,2]]\) code can be concatenated with a 3D surface code to yield a \([[O(d^3),3,2d]]\) code family that admits a transversal implementation of the logical \(CCZ\) gate [24].
  • \([[9,1,3]]\) Shor code— The Shor code is a concatenation of a three-qubit bit-flip with a three-qubit phase-flip repetition code.
  • Layer code— Each pair of surface-code squares in a layer code are fused (or quasi-concatenated) with perpendicular surface-code squares via lattice surgery.
  • Quantum divisible code— A fault-tolerant \(T\) gate on the five-qubit or Steane code can be obtained by concatenating with particular quantum divisible codes [42].
  • Raussendorf-Bravyi-Harrington (RBH) cluster-state code— Concatenation of the RBH code with small codes such as the \([[2,1,1]]\) repetition code, \([[4,1,1,2]]\) subsystem code, or Steane code can improve thresholds [43].
  • \([[2^r-1, 2^r-2r-1, 3]]\) quantum Hamming code— Concatenations of quantum Hamming codes with the \([[4,2,2]]\) and \(C_6\) codes yield fault-tolerant quantum computation with constant space and quasi-polylogarithmic time overheads [29,30]. Quantum Hamming codes can also be concatenated with surface codes [44].
  • 3D color code— The 3D color code is equivalent to multiple decoupled copies of the 3D surface code via a local constant-depth Clifford circuit [45–47]. This process can be viewed as an ungauging [48–50,50] of certain symmetries. This mapping can also be done via code concatenation [51].
  • \([[15,1,3]]\) quantum Reed-Muller code— The concatenated \([[15,1,3]]\) code has a measurement threshold less than one [38].
  • Subsystem homological product code— Concatenated CSS stabilizer codes are gauge-fixed SP codes [52; Thm. 4].

Member of code lists

Primary Hierarchy

Quantum Domain
Qubit Kingdom
Qubit codeQECC Quantum
Parents
Qubit code
Concatenated quantum codeQECC Quantum
Concatenated qubit code
Children
Majorana color code
The Majorana color code is a concatenation of the 2D color code with a small Majorana stabilizer code.
Quantum turbo code
Auxiliary qubit mapping (AQM) code
Concatenated Steane code
The combination of the concatenated Steane code and QLDPC codes with non-vanishing rate yield fault-tolerant quantum computation with constant space and polylogarithmic time overheads, even when classical computation time is taken into account [53].
Hierarchical code
Hierarchical codes are concatenations of constant-rate QLDPC (outer) codes with (inner) rotated surface codes. The block length of the inner code is picked to grow logarithmically with the block length of the outer code.
Yoked surface code
A yoked surface code is a concatenation of a QMDPC code (outer code) with a rotated surface code (inner code).

References

[1]
J. Fern, J. Kempe, S. N. Simic, and S. Sastry, “Generalized Performance of Concatenated Quantum Codes—A Dynamical Systems Approach”, IEEE Transactions on Automatic Control 51, 448 (2006) arXiv:quant-ph/0409084 DOI
[2]
Q. Xu, A. Seif, H. Yan, N. Mannucci, B. O. Sane, R. Van Meter, A. N. Cleland, and L. Jiang, “Distributed Quantum Error Correction for Chip-Level Catastrophic Errors”, Physical Review Letters 129, (2022) arXiv:2203.16488 DOI
[3]
B. Rahn, A. C. Doherty, and H. Mabuchi, “Exact performance of concatenated quantum codes”, Physical Review A 66, (2002) arXiv:quant-ph/0206061 DOI
[4]
D. Poulin, “Optimal and efficient decoding of concatenated quantum block codes”, Physical Review A 74, (2006) arXiv:quant-ph/0606126 DOI
[5]
M. Christandl, O. Fawzi, and A. Goswami, “Fault-tolerant quantum input/output”, (2024) arXiv:2408.05260
[6]
E. Knill, R. Laflamme, and W. H. Zurek, “Resilient quantum computation: error models and thresholds”, Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences 454, 365 (1998) arXiv:quant-ph/9702058 DOI
[7]
J. Preskill, “Reliable quantum computers”, Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences 454, 385 (1998) arXiv:quant-ph/9705031 DOI
[8]
D. Gottesman, “Fault-tolerant quantum computation with local gates”, Journal of Modern Optics 47, 333 (2000) arXiv:quant-ph/9903099 DOI
[9]
D. Aharonov and M. Ben-Or, “Fault-Tolerant Quantum Computation With Constant Error Rate”, (1999) arXiv:quant-ph/9906129
[10]
K. M. Svore, B. M. Terhal, and D. P. DiVincenzo, “Local fault-tolerant quantum computation”, Physical Review A 72, (2005) arXiv:quant-ph/0410047 DOI
[11]
P. Aliferis, D. Gottesman, and J. Preskill, “Quantum accuracy threshold for concatenated distance-3 codes”, (2005) arXiv:quant-ph/0504218
[12]
P. Aliferis, “Level Reduction and the Quantum Threshold Theorem”, (2011) arXiv:quant-ph/0703230
[13]
K. M. Svore, D. P. DiVincenzo, and B. M. Terhal, “Noise Threshold for a Fault-Tolerant Two-Dimensional Lattice Architecture”, (2006) arXiv:quant-ph/0604090
[14]
D. Gottesman. Surviving as a quantum computer in a classical world (2024) URL
[15]
D. Bacon, “Stability of quantum concatenated-code Hamiltonians”, Physical Review A 78, (2008) arXiv:0806.2160 DOI
[16]
A. Rajput, A. Roggero, and N. Wiebe, “Quantum Error Correction with Gauge Symmetries”, (2022) arXiv:2112.05186
[17]
L. Spagnoli, A. Roggero, and N. Wiebe, “Fault-tolerant simulation of Lattice Gauge Theories with gauge covariant codes”, (2024) arXiv:2405.19293
[18]
T. Jackson, M. Grassl, and B. Zeng, “Concatenated codes for amplitude damping”, 2016 IEEE International Symposium on Information Theory (ISIT) (2016) arXiv:1601.07423 DOI
[19]
N. R. Dash, S. Dutta, R. Srikanth, and S. Banerjee, “Bounds on concatenated entanglement-assisted quantum error-correcting codes”, (2024) arXiv:2412.16082
[20]
A. S. Fletcher, P. W. Shor, and M. Z. Win, “Channel-Adapted Quantum Error Correction for the Amplitude Damping Channel”, (2007) arXiv:0710.1052
[21]
E.-J. Chang and C.-Y. Lai, “High-Rate Amplitude-Damping Shor Codes with Immunity to Collective Coherent Errors”, (2024) arXiv:2412.16450
[22]
S. Bravyi, D. Lee, Z. Li, and B. Yoshida, “How much entanglement is needed for quantum error correction?”, (2024) arXiv:2405.01332
[23]
G. Gour and N. R. Wallach, “Entanglement of subspaces and error-correcting codes”, Physical Review A 76, (2007) arXiv:0704.0251 DOI
[24]
D. Hangleiter, M. Kalinowski, D. Bluvstein, M. Cain, N. Maskara, X. Gao, A. Kubica, M. D. Lukin, and M. J. Gullans, “Fault-tolerant compiling of classically hard IQP circuits on hypercubes”, (2024) arXiv:2404.19005
[25]
E. Knill, “Quantum computing with realistically noisy devices”, Nature 434, 39 (2005) arXiv:quant-ph/0410199 DOI
[26]
B. Reichardt, “Postselection threshold against biased noise”, 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06) 420 (2006) arXiv:quant-ph/0608018 DOI
[27]
P. Aliferis, D. Gottesman, and J. Preskill, “Accuracy threshold for postselected quantum computation”, (2007) arXiv:quant-ph/0703264
[28]
J. Cho, “Fault-tolerant linear optics quantum computation by error-detecting quantum state transfer”, Physical Review A 76, (2007) arXiv:quant-ph/0612073 DOI
[29]
H. Yamasaki and M. Koashi, “Time-Efficient Constant-Space-Overhead Fault-Tolerant Quantum Computation”, Nature Physics 20, 247 (2024) arXiv:2207.08826 DOI
[30]
S. Yoshida, S. Tamiya, and H. Yamasaki, “Concatenate codes, save qubits”, (2024) arXiv:2402.09606
[31]
B. Criger and B. Terhal, “Noise thresholds for the [4,2,2]-concatenated toric code”, Quantum Information and Computation 16, 1261 (2016) arXiv:1604.04062 DOI
[32]
G. Alber, Th. Beth, Ch. Charnes, A. Delgado, M. Grassl, and M. Mussinger, “Stabilizing Distinguishable Qubits against Spontaneous Decay by Detected-Jump Correcting Quantum Codes”, Physical Review Letters 86, 4402 (2001) arXiv:quant-ph/0103042 DOI
[33]
T. C. Ralph, A. J. F. Hayes, and A. Gilchrist, “Loss-Tolerant Optical Qubits”, Physical Review Letters 95, (2005) arXiv:quant-ph/0501184 DOI
[34]
Y. Ouyang, “Avoiding coherent errors with rotated concatenated stabilizer codes”, npj Quantum Information 7, (2021) arXiv:2010.00538 DOI
[35]
R. Duan, M. Grassl, Z. Ji, and B. Zeng, “Multi-error-correcting amplitude damping codes”, 2010 IEEE International Symposium on Information Theory (2010) arXiv:1001.2356 DOI
[36]
A. M. Stephens and Z. W. E. Evans, “Accuracy threshold for concatenated error detection in one dimension”, Physical Review A 80, (2009) arXiv:0902.2658 DOI
[37]
Z. W. E. Evans and A. M. Stephens, “Optimal correction of concatenated fault-tolerant quantum codes”, Quantum Information Processing 11, 1511 (2011) arXiv:0902.4506 DOI
[38]
D. Lee and B. Yoshida, “Randomly Monitored Quantum Codes”, (2024) arXiv:2402.00145
[39]
B. Rahn, A. C. Doherty, and H. Mabuchi, “Exact and Approximate Performance of Concatenated Quantum Codes”, (2001) arXiv:quant-ph/0111003
[40]
A. M. Meier, B. Eastin, and E. Knill, “Magic-state distillation with the four-qubit code”, (2012) arXiv:1204.4221
[41]
H. Goto, “High-performance fault-tolerant quantum computing with many-hypercube codes”, Science Advances 10, (2024) arXiv:2403.16054 DOI
[42]
J. Hu, Q. Liang, and R. Calderbank, “Divisible Codes for Quantum Computation”, (2022) arXiv:2204.13176
[43]
Z. Li, I. Kim, and P. Hayden, “Concatenation Schemes for Topological Fault-tolerant Quantum Error Correction”, Quantum 7, 1089 (2023) arXiv:2209.09390 DOI
[44]
M. Fang and D. Su, “Quantum memory based on concatenating surface codes and quantum Hamming codes”, (2024) arXiv:2407.16176
[45]
B. Yoshida, “Classification of quantum phases and topology of logical operators in an exactly solved model of quantum codes”, Annals of Physics 326, 15 (2011) arXiv:1007.4601 DOI
[46]
A. Kubica, B. Yoshida, and F. Pastawski, “Unfolding the color code”, New Journal of Physics 17, 083026 (2015) arXiv:1503.02065 DOI
[47]
A. B. Aloshious, A. N. Bhagoji, and P. K. Sarvepalli, “On the Local Equivalence of 2D Color Codes and Surface Codes with Applications”, (2018) arXiv:1804.00866
[48]
M. Levin and Z.-C. Gu, “Braiding statistics approach to symmetry-protected topological phases”, Physical Review B 86, (2012) arXiv:1202.3120 DOI
[49]
L. Bhardwaj, D. Gaiotto, and A. Kapustin, “State sum constructions of spin-TFTs and string net constructions of fermionic phases of matter”, Journal of High Energy Physics 2017, (2017) arXiv:1605.01640 DOI
[50]
W. Shirley, K. Slagle, and X. Chen, “Foliated fracton order from gauging subsystem symmetries”, SciPost Physics 6, (2019) arXiv:1806.08679 DOI
[51]
M. Vasmer and D. E. Browne, “Three-dimensional surface codes: Transversal gates and fault-tolerant architectures”, Physical Review A 100, (2019) arXiv:1801.04255 DOI
[52]
W. Zeng and L. P. Pryadko, “Minimal distances for certain quantum product codes and tensor products of chain complexes”, Physical Review A 102, (2020) arXiv:2007.12152 DOI
[53]
S. Tamiya, M. Koashi, and H. Yamasaki, “Polylog-time- and constant-space-overhead fault-tolerant quantum computation with quantum low-density parity-check codes”, (2024) arXiv:2411.03683
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

edit on this site

Zoo Code ID: qubit_concatenated

Cite as:
“Concatenated qubit code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2024. https://errorcorrectionzoo.org/c/qubit_concatenated
BibTeX:
@incollection{eczoo_qubit_concatenated, title={Concatenated qubit code}, booktitle={The Error Correction Zoo}, year={2024}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/qubit_concatenated} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/qubit_concatenated

Cite as:

“Concatenated qubit code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2024. https://errorcorrectionzoo.org/c/qubit_concatenated

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/quantum/qubits/qubit_concatenated.yml.