Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this community
I'm at the AQC conference at NASA and everybody seems to suddenly be talking about the Bacon-Shor code but there is no Wikipedia page and the pdf that I gave a link to does not really explain what it is and how it works.
How does it compare to the Shor code ?
I'll add my own two cents. Personally, I find it best to understand the Bacon-Shor code in terms of how one would decode the error syndromes.
Since OP seems to already understand the Shor code, let's first see how one would decode the error syndromes in the Shor code. The Shor code is just the concatenation of two repetition codes: an outer X-type code, each qubit of which further encoded in an inner Z-type code. For concreteness, below I will consider specifically the 9-qubit Shor code, which means both repetition codes are 3-qubit codes. It may help to visualize the qubits as in a grid:
1 2 3
4 5 6
7 8 9
Here each row (e.g. qubits 1, 2, and 3) corresponds to one instance of the inner Z-type code.
X errors and Z errors in the Shor code can be corrected individually. To correct X errors, we look at the two Z-type measurements in each row (remember that Z-type measurements are what help correct X errors, and vice versa), such as $Z_1Z_2$ and $Z_2Z_3$. If they are both +1, then there was probably no X error in this block. If one or two results are -1, then which ones are -1 will indicate which qubit among qubits 1, 2, and 3 is probably flipped, and the error can be corrected by applying a physical X gate. (If 2 or 3 X errors have happened in this row, then this goes horribly wrong and results in a logical X error.)
Meanwhile, to correct Z errors, we have to look at each row as a whole, and apply X measurements to two entire rows. This is trickier to implement, requiring weight-6 stabilizer measurements such as $X_1X_2X_3X_4X_5X_6$ (this works because e.g. $X_1X_2X_3$ is a logical X operator for the inner code in the top row). The results of those weight-6 stabilizer measurements are then used as error syndromes for the outer X-type repetition code.
One helpful way to understand this is that we no longer care about whether each of qubits 1, 2, and 3 individually has a Z error; we only care about whether qubits 1, 2, and 3 together has an odd number of Z errors. We don't care about whether a Z error happened on qubit 1 or qubit 2 because $Z_1Z_2$ is a stabilizer anyway.
The Bacon-Shor code corrects both X errors and Z errors in the way the Shor code corrects Z errors. So we still have weight-6 X-type stabilizer measurements such as $X_1X_2X_3X_4X_5X_6$, but also Z-type ones such as $Z_1Z_2Z_4Z_5Z_7Z_8$.
Correct! As an example, consider what combinations of two X errors or two Z errors a 9-qubit Shor code can correct. The Shor code can correct two X errors as long as they are not in the same row; in fact, it can correct any number of X errors as long as each row only contains a single error. This is rather obvious since in decoding each row is handled individually. Meanwhile, it can correct two Z errors only when they are in the same row (in which case the error really just corrects itself). Any two Z errors not in the same row will translate to two Z errors for the outer code, which defeats the 3-qubit repetition code.
Since the Bacon-Shor code handles X errors and Z errors symmetrically, it can only correct two X errors when they are in the same column. This is a strictly stronger condition than "they are not in the same row".
The trick is that even though both types of stabilizers are weight-6, we can actually measure both with only weight-2 Pauli measurements. For example, instead of directly measuring $X_1X_2X_3X_4X_5X_6$, we can measure the "gauges" $X_1X_4$, $X_2X_5$, and $X_3X_6$. This was not possible for the Shor code because e.g. $X_1X_4$ would anti-commute with the stabilizer $Z_1Z_2$. Of course, this works symmetrically for the Z-type measurements — instead of measuring $Z_1Z_2Z_4Z_5Z_7Z_8$ we still just measure $Z_1Z_2$, $Z_4Z_5$, and $Z_7Z_8$. Since those are only gauges and not stabilizers, we don't care if they anti-commute among themselves.
If you smell something weird here (e.g. "Don't the gauge measurements disturb the code state?"), it's probably one of the peculiarities of the subsystem code, which other answers have mentioned. I can add more information if you have any concrete questions to ask.
The Bacon-Shor code trades some "raw" error correcting ability for the ability to extract error syndromes using only spatially local two-qubit Pauli measurements. It naturally generalizes to a $d\times d$ grid, where the locality matters even more. This can be a very good trade-off in the context of fault-tolerant computation, because there the main difficulty is the possibility of an error happening in the syndrome extraction process itself, and the more complicated the process, the more error-prone it becomes.
The key difference is that the Bacon-Shor code is a subsystem code, while the Shor code is a stabilizer code. They have the same stabilizer operators, but the error correction procedure is different. The canonical reference for this construction is [Poulin].
Stabilizer codes rely on measuring eigenvalues of commuting operators (the stabilizers). Because these operators commute, we can label subspaces of the state space by these eigenvalues. In particular, the joint +1 eigenspace is the codespace. If any of our measurements result in a -1 eigenvalue, we know that the state has wandered out of the codespace and can (hopefully) do something to rectify this.
With subsystem codes, we also measure eigenvalues of some operators, but this time they do not form a commuting set of operators. These operators are called gauge operators. They generate a group called the gauge group. The trick to this construction is that the center of the gauge group is the stabilizer group. This is the group of operators generated by the gauge operators that commute with every element of the gauge group.
How this works in practice: suppose you have a stabilizer operator $s$ written as a product of gauge operators $\{g_i\}$:
$$ s = \prod_i g_i. $$
Now we go ahead and measure each of the $g_i$. Each measurement gives a random eigenvalue $\lambda_i = \pm 1$ but the product of these $\lambda = \prod \lambda_i$ labels the eigenspace of $s$ that the state belongs to. Once we have all the eigenvalues of the stabilizers in this way we can (hopefully) do something to rectify the state.
An example: I find it helpful to think of the "4-qubit Bacon-Shor code". This is an error detecting subsystem code. The gauge operators are
$$\{XXII, IIXX, ZIZI, IZIZ\}.$$
Think of these as operating on a $2\times 2$ lattice of qubits. These operators generate the stabilizers $XXXX$ and $ZZZZ.$ Once we measure $XXII$ and $IIXX$ we multiply the two eigenvalue measurements to find the eigenvalue of $XXXX$. These gauge operators are "easier" to measure, because they only involve two qubits, but the cost is that we mess up the state in other ways. These "other ways" are the gauge qubits, and we don't care about these. The encoded qubits, or logical qubits are the ones we are trying to preserve. The operators that act on the encoded qubits are the logical operators. For this example these are $ZZII$ and $XIXI$. As an exercise I would recommend working out the corresponding eigenvectors (and eigenspaces) for all these operators.
Larger Bacon-Shor codes work similarly. For an $n\times n$ lattice of qubits, there are a bunch of 2-qubit gauge operators, arranged like "dominoes" on the lattice. The $X$ type gauge operators are horizontal dominoes, and the $Z$ type gauge operators are vertical dominoes. A vertical stack of $n$ of the $X$ type dominoes generates an $X$ type stabilzer on $n\times 2$ qubits. And so on.
The relevance to adiabatic quantum computing is that we can form a Hamiltonian from these operators, as the negative sum of the gauge operators. The groundspace of the Hamiltonian corresponds to the logical qubits of the gauge code, and excitations of the state correspond to errors. For the Bacon-Shor code, the gap of this Hamiltonian goes to zero as the size of the system grows. Therefore this Hamiltonian does not work to protect the encoded state (energetically.) This Hamiltonian is also known as the quantum compass model.
I also wrote a paper about subsystem codes and Hamiltonians.
Bacon Shor code is still very hot today! Assume you have some familiarity with Shor's code, here I just highlight the difference between these two.
The Shor's code has distance 3 for both X and Z type errors. The distance is a metric for error-correcting capability. It means some errors with such weight can be undetected but produce a logical failure. Distance 3 also means the code can correct any single error and detect any double error. Hence Shor's code is the first code to be able to correct any single Pauli errors (X, Y, or Z).
The strange part is that Shor code has six Z-type measurements and two X-type measurements, even though X and Z distances are the same. Any sequence from that? Indeed! The distance only tells you the worst error configuration the code fails, but the code may be able to correct many errors with weight up to or even higher the distance. That is where the six measurements matter. The six Z-type measurements will be able to correct more X error configurations compares with the two X-type measurements for Z errors.
The Bacon Shor code has six measurements for both X and Z-type. It is symmetric with respect to X and Z. Compared to Shor code, its advantages are
and disadvantages
The Bacon Shor code is optimal for small systems. But the few large-weight stabilizers lead to bad asymptotic performance for large systems. Some recent work in fact overcomes this drawback and suggests using measurement information from small-weight gauge measurements directly. This makes Bacon Shor code as well as general subsystem code promising again.
Disclaimer: This answer is based on what I deduced from a brief Googling session. I might make further additions/improvements as and when I will understand the details more thoroughly. Feel free to make suggestions in the comments.
The $9$-qubit Shor code $[[9,1,3]]$ (qubits laid in a $3\times 3$ lattice) is the smallest member in the family of $m^2$-qubit Bacon-Shor code(s) $[[m^2,1,m]]$ (qubits laid in a $m\times m$ lattice). Shor's code, as you know, can correct both Pauli sign flip and Pauli bit-flip errors in a single qubit. Moreover, to correct any single-qubit error (with a high probability), it is sufficient to be able to correct against any single qubit Pauli error.[1]
Now, Bacon-Shor code(s) is(/are) a generalization of this concept to noise models where the qubits in a code block are subject to both bit-flip errors with probability $p_X$ and dephasing errors with probability $p_Z$. The noise is assumed to act independently on each qubit and the $X$ and $Z$ errors are uncorrelated.
In (Napp and Preskill, 2013) the authors find that the optimally-sized Bacon-Shor code for equal $X$ and $Z$ errors rate $p$ is given by $m=\frac{\log 2}{4p}$ and for that optimal choice they can bound the logical $X$(or $Z$) error rate as $\tilde p(p) \lesssim \exp(\frac{-0.06}{p})$[2].
It is also possible to work with asymmetric Bacon-Shor codes with qubits in an $n \times m$ array. Asymmetric codes can have better performance when, say, $Z$ errors are more likely than $X$ errors[3].
References:
Shor Code
Can detect and correct arbitrary single qubit errors, but if there are 2 or more single qubit errors before a correction round, the correction will fail. -Intuition for Shor code failure probability
Bacon-Shor Code
Bacon-Shor codes, quantum subsystem codes which are well suited for applications to fault-tolerant quantum memory because the error syndrome can be extracted by performing two-qubit measurements. Optimal Bacon-Shor codes
Contrarily to Shor's code, these stabilizers cannot identify the precise qubit on which a bit-flip occurs, they can only identify the column in which it occurs. - Quantum Error Correction
For the $[[n^2, 1, n]]$ Bacon-Shor code the qubits are laid out in a 2D n × n square array. It is also possible to work with asymmetric Bacon-Shor codes with qubits in a n × m array. - Quantum Error Correction for Quantum Memories pg. 34
We have shown that for every generalized Shor code there is an subsystem code with the same parameters but which requires significantly fewer stabilizer measurements in order to perform quantum error correction. - Quantum Error Correcting Subsystem Codes From Two Classical Linear Codes
Also, here is a video from Microsoft Universal Fault-Tolerant Computing with Bacon-Shor Codes.
