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. – heather 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

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.[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. – 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. – meowzz Jun 28 '18 at 1:10
• Updated answer to included "fewer stabilizer measurements in order to perform quantum error correction." – meowzz 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