REVIEW
A Class of Quantum Error-Correcting Codes Saturating the Quantum Hamming Bound
Quantum Physics · Submitted 29 Apr 1996 · 12 references
Pith's verdict: The paper that gave the field its standard language and the quantum analogue of Hamming codes; the general-j proofs are informal but the construction is explicit and correct.
Why Pith says this
Highlight any text to comment on it.
Referee report
The paper
The paper claims
Gottesman constructs an infinite family of quantum codes that exactly meets the quantum Hamming bound, encoding $n-j-2$ qubits in $2^j$ physical qubits while correcting one error.
The reading
What carries the argument
The load-bearing device is the stabilizer: the subgroup $H$ of the Pauli group $G$ (generated by $X_i$, $Y_i$, $Z_i$ on each qubit) whose elements fix every code word. If an error $E$ anticommutes with any member of $H$, then $E$ maps code words to a subspace orthogonal to the code, so errors can be told apart. Because $H$ must be abelian and every element must square to $+1$, $H$ is a copy of $(Z_2)^a$ generated by $a$ commuting Pauli products, and the code space has dimension $2^{n-a}$. The construction then becomes a labelling problem: assign to each single-qubit error $X_i$, $Y_i$, $Z_i$ a distinct $a$-bit string recording which generators it anticommutes with, i.e. the homomorphism $f(N) = (f_{M_1}(N), dots, f_{M_a}(N))$ with $f_M(N) = 0$ if $[M,N] = 0$ and $1$ if ${M,N} = 0$. Distinct labels for all $3n$ one-qubit errors is exactly the condition that the code correct one error. The paper's specific scheme spends two bits saying whether the error is $X$, $Y$ or $Z$ and the remaining $j$ bits encoding the qubit index, with the $Z$-labels counting $0,0,1,1,2,2, dots$ in binary and then bitwise complementing one member of each pair, so that the resulting $Y$-labels stay distinct.
Extended reading notes
Core claim
The central claim is that the quantum Hamming bound is saturated, not merely approached, by an explicit infinite family of non-degenerate codes. The bound counts: a code correcting up to $t$ errors must fit $2^k$ code words together with all $3^l n$-choose-$l$ error images into the $2^n$-dimensional Hilbert space, giving $2^k (1 + 3n) le 2^n$ at $t = 1$, hence $k le n - j - 2$ when $n = 2^j$. Gottesman exhibits codes meeting this with equality for every $j ge 3$, including a concrete $k = 3$, $n = 8$ example whose eight code words are written out explicitly as superpositions of 16 computational basis states each. The author notes that Steane, and separately Calderbank, Rains, Shor and Sloane, arrived at $k = 3$, $n = 8$ codes by other routes, so the eight-qubit case is not unique to this construction; what is new here is the general $j$ family and the stabilizer machinery used to build and certify it. A secondary result, in Appendix A, is a proof that degenerate codes of a restricted type — where linearly independent error matrices can only map code words into a one-dimensional subspace — also obey the quantum Hamming bound at $t = 1$.
Load-bearing premise
The family works for every $j$ only if the label assignment in the paper's table really gives distinct $(j+2)$-bit labels to all $X_i$, $Y_i$ and $Z_i$; the distinctness of the $Y$ labels is argued by inspecting a table of bit patterns rather than by a closed-form proof, and a single collision would make two different one-qubit errors indistinguishable.
Editorial extensions
If this is right
- For every $j ge 3$ there is a non-degenerate one-error-correcting code with $n = 2^j$ and $k = n - j - 2$, so no non-degenerate code with those parameters can do better than this family.
- The rate $k/n = 1 - (j+2)/2^j$ tends to 1, so large blocks protect almost all of their qubits against a single error while still meeting the counting bound exactly.
- The eight-qubit instance gives a $k = 3$, $n = 8$ code, matching codes found independently by Steane and by Calderbank, Rains, Shor and Sloane.
- Any degenerate code whose only degeneracies collapse code words into a one-dimensional subspace still obeys the quantum Hamming bound at $t = 1$, so beating the bound would require a genuinely different kind of degeneracy.
- The stabilizer description supplies a general recipe: pick a distinct binary label for each short Pauli error, read off the generators, and verify that they commute and square to $+1$.
Reading between the lines
- The construction is really a perfect-hashing problem in disguise: the $j+2$ bit labels must separate $3 cdot 2^j$ error classes, and the paper's two-bit prefix plus parity-complement scheme is one explicit perfect hash for that set. Recognizing this suggests other combinatorial designs — for instance Sidon-type or difference-set constructions — as candidate label assignments.
- Extending the family to $t ge 2$ would require labelling products of up to $2t$ single-qubit errors distinctly, which is a much larger set; the paper explicitly leaves this open, and the difficulty is a counting one rather than a conceptual one, so the same stabilizer method should apply if a suitable labelling is found.
- Because the family saturates rather than approaches the bound, it gives a sharp test case for any claim that degenerate codes can beat the quantum Hamming bound: such a code would have to be degenerate in a way that is not a one-dimensional collapse, so the appendix narrows where to look.
- The stabilizer language introduced here is the natural bookkeeping for any question about which errors a code can distinguish, so the machinery may outlast the specific family — the paper itself says it does not know whether every code in the $X, Y, Z$ basis admits such a description.
Original abstract
I develop methods for analyzing quantum error-correcting codes, and use these methods to construct an infinite class of codes saturating the quantum Hamming bound. These codes encode $k=n-j-2$ qubits in $n=2^j$ qubits and correct $t=1$ error.
The compiled record
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
The abstract, sentence by sentence
I develop methods for analyzing quantum error-correcting codes, and use these methods to construct an infinite class of codes saturating the quantum Hamming bound. These codes encode $k=n-j-2$ qubits in $n=2^j$ qubits and correct $t=1$ error.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | I develop methods for analyzing quantum error-correcting codes, and use these methods to construct an infinite class of codes saturating the quantum Hamming bound. | contribution 1.00 | 0.96 | 0.83 | asserted 1.00 |
| s1 | These codes encode $k=n-j-2$ qubits in $n=2^j$ qubits and correct $t=1$ error. | result 0.74 | 0.88 | 0.31 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v2
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
References
How later papers used it
153 later papers cite it
2 later papers by other authors are listed below: 1 used its method or tool and 1 compared its own results with it.
Uses its method or tool 1 of 10 papers with this label
-
Now, in order to associate an $n$-qubit state to any connected graph we follow the stabilizer formalism [ref] and to each vertex $v_i∈𝒱$ we associate an operator defined as
Certification of multi-qubit quantum systems with temporal inequalities (2024) · Graph states · 0.90
Compares with it 1 of 2 papers with this label
-
Constructed quantum stabilizer codes with parameters [[2^m, 2^m-m-2, 3]] that are the same as those constructed in this paper.
A Construction of Quantum Stabilizer Codes Based on Syndrome Assignment by Classical Parity-Check Matrices (2007) · 0.96 · paraphrased: the licence does not allow quoting
How the literature uses it
37 arXiv papers cite this in 54 sentences
Papers citing it · 22 sentences without a confident label
Uses its method or tool 2 papers
-
We thus will largely study “random Clifford circuits" with the Haar unitaries replaced by random two-qubit Clifford unitaries, and the single qubit measurements restricted to the Pauli group [ref] .
Measurement-driven entanglement transition in hybrid quantum circuits · Introduction · 0.88
-
The Gottesman-Knill theorem [ref] enables efficient simulation of Clifford circuits of up to thousands of qubits on a laptop, allowing us to perform detailed scaling analyses.
Conformal invariance and quantum non-locality in critical hybrid circuits · Introduction · 0.97
Compares with it 1 paper
-
In [ref] , the quantum Hamming bound says that for an $[[n,k,d≥d=2t+1]]$ quantum code, [equation] and the asymptotic form is [equation] or [equation] The quantum singleton bound [ref] says that for an $[[n,k,d]]$ quantum code, [equation] or [equation] The Gilbert-Varshamov bound for a general quantum stabilizer codes, proved in Theorem 2 in [ref] , says that an $[[n,k,d=2t+1]]$ stabilizer code exists if [equation] or [equation] The Gilbert-Varshamov bound for CSS codes, proved in Section V in [ref] , says that an $[[n,k,d=2t+1]]$ CSS code exists if [equation] or [equation] The above known quantum bounds in the literature are depicted in Fig. [ref].
A Construction of Quantum Stabilizer Codes Based on Syndrome Assignment by Classical Parity-Check Matrices · Asymptotic Coding Efficiency · 0.97
Cites it as background 24 papers
-
The idea of stabilizer codes was proposed in [ref] and the properties of stabilizer codes were extensively addressed in [ref] .
A Construction of Quantum Stabilizer Codes Based on Syndrome Assignment by Classical Parity-Check Matrices · Introduction · 1.00
-
Before long, a simple and systematic method of slicing the state vector space into discretely labeled subspaces with help of classical error correcting codes was discovered by Calderbank and Shor [ref] and Steane [ref] , and generalized to what is now known as stabilizer codes by Gottesman [ref] or symplectic/additive codes by Calderbank, Rains, Shor and Sloane [ref] .
Algebraic Methods for Quantum Codes on Lattices · Introduction · 0.99
-
An $[[n, k]]$ quantum stabilizer code $V_𝖲$ is defined as a $p^k$-dimensional subspace of $(^p)^n$ fixed by the stabilizer group $𝖲 = ⟨g_1, ⋯, g_n-k⟩$ generated by a commuting set of operators $g_i = g(^(i), ^(i)) (i=1, ⋯, n-k)$ [ref] .
Supersymmetric conformal field theories from quantum stabilizer codes · Narain code CFTs · 0.92
Discussion
Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.