Description
A code constructed in a multi-partite quantum system, i.e., a physical space consisting of a tensor product of \(n > 1\) identical factors called subsystems, parties, or bodies. The subsystems include qubits, modular qudits, Galois qudits, oscillators, groups, or categories. For finite dimensional codes, the dimension of the underlying subsystem is denoted by \(q\) and is sometimes called the local dimension.
While codewords \(c\) of block codes are elements of \(\Sigma^n\) for some alphabet \(\Sigma\), quantum states of block quantum codes are \(L^2\)-normalizable functions on \(\Sigma^n\). Put differently, the configuration space of the canonical (a.k.a. computational) basis states \(|c\rangle\) of an \(n\)-body quantum system is the classical \(n\)-coordinate alphabet \(\Sigma^n\).
Protection
Block codes protect from erasures or, more generally, errors acting on a few of the \(n\) subsystems. A block code with distance \(d\) detects errors acting on up to \(d-1\) subsystems, and corrects erasure errors on up to \(d-1\) subsystems. The subsystems that are erased are known to the receiver, and erasures of subsystems at unknown locations are called deletion errors [1–4]. More general forms of noise are caused by insertion errors [1–4], where subsystems are inserted into the block, and synchronization errors (a.k.a. misalignment) [5], where the code block is misplaced in a larger block by one or more locations. There are relations between deletion and insertion errors [6,7].
The weight of an operator on a tensor-product Hilbert space is the number of subsystems on which the operator acts non-trivially. For example, an operator acting on two subsystem is called a weight-two operator or a two-body operator.
General noise models for block codes include stochastic noise, in which every possible error is assigned a probability. In the case of local stochastic noise, the probability decreases rapidly (typically, exponentially) with the number of subsystems that an error acts on. On the other hand, the adversarial noise model consists of errors acting on at most a fixed number of subsystems. Errors acting on subsystems in a geometrically local region are called burst errors [8–10].
Bounds on code parameters
Bounds on finite dimensional block code performance include the quantum Singleton bound, quantum Hamming bound, quantum GV bound, various quantum linear programming (LP) bounds [11,12] (see the book [13]), and other bounds [14,15]. A code whose parameters attain the quantum Hamming bound (quantum Singleton bound) is called a perfect quantum code (a quantum MDS code). We are often interested in how parameters of particular infinite block quanutm code families scale with increasing block length \(n\), necessitating the use of asymptotic notation.
Quantum GV bound: The quantum GV bound [16] (see also Refs. [17–21]) for Galois qudits states that a pure \([[n,k,d]]_q\) Galois-qudit stabilizer code exists if \begin{align} \frac{q^{n-k+2}-1}{q^{2}-1}>\sum_{j=1}^{d-1}(q^{2}-1)^{j-1}\binom{n}{j}~. \tag*{(1)}\end{align} The bound gives rise to the asymptotic quantum GV bound (i.e., quantum GV bound in the \(n\to\infty\) limit), expressed in terms of the maximum achievable rate \(R\) and relative distance \(\delta\), \begin{align} R\geq 1-\delta\log_q(q+1) - h_{q}(\delta)~, \tag*{(2)}\end{align} where \(h_q\) is the \(q\)-ary entropy function.
Transversal Gates
Eastin-Knill theorem: Transversal gatesare logical gates on block codes that can be realized as tensor products of unitary operations acting on subsets of subsystems whose size is independent of \(n\). For subsets of size one, gates are sometimes called strongly transversal the single-subsystem unitaries are identical and weakly transversal otherwise. A universal gate set for a finite-dimensional block quantum code cannot be transversal for any code that detects single-block errors due to the Eastin-Knill theorem [22].
Notes
Tables of linear-programming upper bounds on general block quantum codes for various \(n\), \(k\), and \(q\), based on algorithms developed in Refs. [23,24], are maintained by M. Grassl at this website. A Magma implementation exists at this website.States of block quantum codes can be classified in terms of the complexity of their underlying encoding circuit; see Complexity Zoo exhibit.Cousins
- Monolithic quantum code— Block quantum codes for \(n=1\) are monolithic codes.
- Block code
Member of code lists
Primary Hierarchy
References
- [1]
- M. Hagiwara and A. Nakayama, “A Four-Qubits Code that is a Quantum Deletion Error-Correcting Code with the Optimal Length”, (2020) arXiv:2001.08405
- [2]
- A. Nakayama and M. Hagiwara, “Single Quantum Deletion Error-Correcting Codes”, (2020) arXiv:2004.00814
- [3]
- Y. Ouyang, “Permutation-invariant quantum coding for quantum deletion channels”, 2021 IEEE International Symposium on Information Theory (ISIT) 1499 (2021) arXiv:2102.02494 DOI
- [4]
- T. Shibayama and M. Hagiwara, “Permutation-Invariant Quantum Codes for Deletion Errors”, 2021 IEEE International Symposium on Information Theory (ISIT) 1493 (2021) arXiv:2102.03015 DOI
- [5]
- Y. Fujiwara, “Block synchronization for quantum information”, Physical Review A 87, (2013) arXiv:1206.0260 DOI
- [6]
- T. Shibayama and Y. Ouyang, “The equivalence between correctability of deletions and insertions of separable states in quantum codes”, 2021 IEEE Information Theory Workshop (ITW) 1 (2021) arXiv:2105.07214 DOI
- [7]
- T. Shibayama, “Necessary and sufficient condition for constructing a single qudit insertion/deletion code and its decoding algorithm”, (2025) arXiv:2501.07027
- [8]
- S. Kawabata, “Quantum Interleaver: Quantum Error Correction for Burst Error”, Journal of the Physical Society of Japan 69, 3540 (2000) arXiv:quant-ph/0002020 DOI
- [9]
- S. Kawabata, “Quantum Interleaver: Quantum Error Correction for Burst Error”, Journal of the Physical Society of Japan 69, 3540 (2000) DOI
- [10]
- F. Vatan, V. P. Roychowdhury, and M. P. Anantram, “Spatially correlated qubit errors and burst-correcting quantum codes”, IEEE Transactions on Information Theory 45, 1703 (1999) DOI
- [11]
- E. M. Rains, “Quantum shadow enumerators”, (1997) arXiv:quant-ph/9611001
- [12]
- A. Ashikhmin and S. Litsyn, “Upper Bounds on the Size of Quantum Codes”, (1997) arXiv:quant-ph/9709049
- [13]
- D. Gottesman. Surviving as a quantum computer in a classical world (2024) URL
- [14]
- Keqin Feng, San Ling, and Chaoping Xing, “Asymptotic bounds on quantum codes from algebraic geometry codes”, IEEE Transactions on Information Theory 52, 986 (2006) DOI
- [15]
- G. Chiribella, M. Dall’Arno, G. M. D’Ariano, C. Macchiavello, and P. Perinotti, “Quantum error correction with degenerate codes for correlated noise”, Physical Review A 83, (2011) arXiv:1007.3655 DOI
- [16]
- K. Feng and Z. Ma, “A Finite Gilbert–Varshamov Bound for Pure Stabilizer Quantum Codes”, IEEE Transactions on Information Theory 50, 3323 (2004) DOI
- [17]
- A. Ekert and C. Macchiavello, “Error Correction in Quantum Communication”, (1996) arXiv:quant-ph/9602022
- [18]
- A. Ashikhmin, A. Barg, E. Knill, and S. Litsyn, “Quantum Error Detection II: Bounds”, (1999) arXiv:quant-ph/9906131
- [19]
- G. S. B. Smith, Upper and Lower Bounds on Quantum Codes, California Institute of Technology, 2006 DOI
- [20]
- A. Ashikhmin and E. Knill, “Nonbinary quantum stabilizer codes”, IEEE Transactions on Information Theory 47, 3065 (2001) DOI
- [21]
- Y. Ma, “The asymptotic probability distribution of the relative distance of additive quantum codes”, Journal of Mathematical Analysis and Applications 340, 550 (2008) DOI
- [22]
- B. Eastin and E. Knill, “Restrictions on Transversal Encoded Quantum Gate Sets”, Physical Review Letters 102, (2009) arXiv:0811.4262 DOI
- [23]
- M. Grassl, “Searching for linear codes with large minimum distance”, Algorithms and Computation in Mathematics 287 DOI
- [24]
- M. Frederic Ezerman, M. Grassl, S. Ling, F. Özbudak, and B. Özkaya, “Characterization of Nearly Self-Orthogonal Quasi-Twisted Codes and Related Quantum Codes”, IEEE Transactions on Information Theory 71, 499 (2025) arXiv:2405.15057 DOI
Page edit log
- Victor V. Albert (2023-02-14) — most recent
Cite as:
“Block quantum code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/block_quantum