# 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. – karatechop Jun 27 '18 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. – user1271772 Jun 27 '18 at 23:17
• @user1271772 "Shor code" is a special case of "Bacon-Shor code(s)". – Sanchayan Dutta Jun 28 '18 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. – user1271772 Jun 28 '18 at 22:39

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. – user1271772 Apr 16 at 21:11

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.

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

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.

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. – DaftWullie Jun 28 '18 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. – Sanchayan Dutta Jun 28 '18 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. – user1271772 Jun 28 '18 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. – user820789 Jun 28 '18 at 1:10
• Updated answer to included "fewer stabilizer measurements in order to perform quantum error correction." – user820789 Jun 28 '18 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. – Sanchayan Dutta Jun 28 '18 at 5:20