What is a Bacon-Shor code and what is its significance?

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 ?

• This seems to have a good summary...let me know if this helps; I'm still reading through it. Jun 27, 2018 at 23:14
• I am not looking for a super long essay on the Bacon-Shor code, just a short and simple explanation of what it is and what it's significance is, with an explanation for why it's different from the "Shor code". I will accept an answer that is short and sweet, not a lengthy essay that explains every single detail. Jun 27, 2018 at 23:17
• @user1271772 "Shor code" is a special case of "Bacon-Shor code(s)". Jun 28, 2018 at 5:50
• I'm still looking for an answer to accept. The two given, are mainly just quotations from other places, pieced together. If someone can give me a simple and concise description and why it's important (preferably someone who's really familiar with QEC at a research level rather than someone looking up primary resources to piece together an answer), I would happy to accept an answer without hesitation. Jun 28, 2018 at 22:39

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.

Motivating example: Shor code

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.

Bacon-Shor code

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$$.

Doesn't this just perform worse?

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".

So what's the point?

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.

Conclusion

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.

• +25 nice first answer! Welcome to our community! Dec 15, 2022 at 1:11
• Thanks! Seeing you being nice in the comment section motivated me to answer :) Dec 15, 2022 at 1:25

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

• preserve distance 3 for both X and Z
• preserve one logical qubit
• need only weight-2 measurements for neighboring qubits

• has only two stabilizers with large weights for both X and Z-type. From the above argument, this weakens the error-correcting capability for X errors to be the same as that for Z errors.

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.

• +1 and welcome to our community! Thank you for your contribution, and we hope to see much more of you in the future!!! I'm accepting this answer for now, but will read it in more detail later. Apr 16, 2021 at 21:11

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:

• My memory is that an important feature of these codes is that they are subsystem codes. What that means and why it's relevant probably needs explaining. Jun 28, 2018 at 7:40
• @DaftWullie True, I need to add that part. FWIW pages 8-12 of the first reference (Terhal's) seem to cover it well. Going through them. Jun 28, 2018 at 7:51

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.

• Bacon-Shor code cannot identify the precise qubit on which a bit-flip can occur, therefore it allows higher fault tolerance than the Shor code? This does not make sense to me. Also an edit suggestion: next to the two quotes you gave, add the citation so that we know right away which quote comes from which reference. Jun 28, 2018 at 0:27
• Apologies. I changed format & in the process I think I combined sources in an inaccurate way based on an intuition. Rolled back. Jun 28, 2018 at 1:10
• Updated answer to included "fewer stabilizer measurements in order to perform quantum error correction." Jun 28, 2018 at 1:30
• @user1271772 Bacon-Shor codes are used for larger system of qubits (where more than one qubit can be subjected to errors) compared Shor's 9-qubit code (which allows only for correction of a single qubit error with high probability). However, technically speaking, Shor's code is a Shor-Bacon code (think of it as a special case). I have elaborated a bit in my answer above. Jun 28, 2018 at 5:20