Correcting quantum errors

Introduction

Quantum computing has the potential to enable efficient solutions to computational tasks for which efficient classical algorithms are not known, and possibly don't exist. There are, however, very significant challenges that will need to be overcome before we can reliably implement the sorts of large-scale quantum computations we hope will one day be possible.

The heart of the matter is that quantum information is extremely fragile — you can literally ruin it just by looking at it. For this reason, to correctly operate, quantum computers need to isolate the quantum information they store from the environment around them to an extreme degree. But at the same time, quantum computers must provide the user with very precise control over this quantum information, including proper initialization, accurate and reliable unitary operations, and the ability to perform measurements so that the results of the computation can be obtained.

There's clearly some tension between these requirements, and in the early days of quantum computing some viewed that the fragility of quantum information, and its susceptibility to both inaccuracies and environmental noise, would ultimately make quantum computing impossible. Today there's little doubt that building an accurate and reliable large-scale quantum computer is a monumental challenge. But we have a key tool to help us in this endeavour that leads most people who are knowledgeable about the field to be optimistic about large-scale quantum computing one day becoming a reality, and that tool is quantum error correction.

For the next four lessons we'll discuss quantum error correction, with a focus on the fundamentals. In this lesson we'll take a first look at quantum error correction, including the very first quantum error correcting code discovered — the 9-qubit Shor code — and we'll also discuss a foundational concept in quantum error correction known as the discretization of errors.

Classical repetition codes

We'll begin the lesson with classical repetition codes, which form the basis for the 9-qubit Shor code.

Encoding and decoding

Repetition codes are extremely basic examples of error correcting codes. The idea is that we can protect bits against errors by simply repeating each bit some fixed number of times. In particular, let's first consider the 3-bit repetition code. Here we encode one bit into three by repeating the bit three times, so $0$ is encoded as $000$ and $1$ is encoded as $111.$

If nothing goes wrong we can obviously distinguish the two possibilities for the original bit from their encodings. The point is that if there was an error and one of the three bits flipped, meaning that a 0 changes into a 1 or a 1 changes to a 0, then we can still figure out what the original bit was by determining which of the two binary values appears twice. Equivalently, we can decode by computing the majority value (i.e., the binary value that appears most frequently).

Of course, if 2 or 3 bits of the encoding flip, then the decoding won't work properly and the wrong bit will be recovered, but if at most 1 of the 3 bits flip, the decoding will be correct. This is a typical property of error correcting codes: they may allow for the correction of errors, but only if there aren't too many of them.

Binary symmetric channels

For an example of a situation in which the chances of making an error can be decreased using a repetition code, suppose that our goal is to communicate a single bit to a hypothetical receiver, and we're able to transmit bits through a so-called binary symmetric channel, which flips each bit sent through it independently with some probability $p.$ That is, with probability $1-p$ the receiver gets whatever bit was sent through the channel, but with probability $p$ the bit flips and the receiver gets the opposite bit value.

So, if we choose not to use the 3-bit repetition code, and simply send whatever bit we have in mind through the channel, the receiver therefore receives the wrong bit with probability $p.$ On the other hand, if we first encode the bit we want to send using the 3-bit repetition code, and then send each of the three bits of the encoding through the channel, then each one of them flips independently with probability $p.$ The chances of a bit-flip are now greater because there are now three bits that might flip rather than one — but if at most one of the bits flips then the receiver will decode correctly. So, an error persists after decoding only if two or more of the bits flip during transmission.

The probability that two bits flip during transmission is $3p^2(1-p),$ which is $p^2(1-p)$ for each of the three choices for the bit that doesn't flip, while the probability that all three bits flip is $p^3.$ The total probability of two or three bit flips is therefore

For values of $p$ smaller than one-half this results in a decrease in the probability that the receiver ends up with the wrong bit. There will still be a chance of an error in this case, but the code decreases the likelihood. (For values of $p$ greater than one-half, on the other hand, the code actually increases the likelihood that the receiver gets the wrong bit.)

Repetition code for qubits

The 3-bit repetition code is a classical error correcting code, but we can consider what happens if we try to use it to protect qubits against errors. As we'll see, it's not a very impressive quantum error correcting code: it actually makes some errors more likely. It is, however, the first step toward the Shor code, and it will also serve us well from a pedagogical viewpoint.

Encoding

To be clear, when we refer to the 3-bit repetition code being used for qubits, we have in mind an encoding of a qubit where standard basis states are repeated three times, so that a single-qubit state vector is encoded as follows.

This encoding is easily implemented by the following quantum circuit that makes use of two initialized workspace qubits and two controlled-NOT gates.

Notice in particular that this encoding is not the same as repeating the quantum state three times, as in a given qubit state vector being encoded as $\vert\psi\rangle \mapsto \vert\psi\rangle\vert\psi\rangle\vert\psi\rangle.$ Such an encoding cannot be implemented for an unknown quantum state $\vert\psi\rangle$ by the no cloning theorem.

Bit-flip error detection

Now suppose that an error takes place after the encoding has been performed. In particular, let's suppose that an $X$ gate, or in other words a bit flip, occurs on one of the qubits. For instance, if the middle qubit experiences a bit-flip, the state of the three qubits is transformed into this state:

Of course, this isn't the only sort of error that could occur — and it's also reasonable to question the assumption that an error takes the form of a perfect, unitary operation. We'll return to these issues in the last section of the lesson, and for now we can view an error of this form as being just one possibility (albeit a fundamentally important one) for an error.

We can see clearly from the mathematical expression for the state above that the middle bit is the one that's different inside of each ket — but suppose that we had the three qubits in our possession and didn't know their state. If we suspected that a bit-flip may have occurred, one option to verify that a bit flipped would be to perform a standard basis measurement, which in the case at hand causes us to see $010$ or $101$ with probabilities $\vert\alpha\vert^2$ and $\vert\beta\vert^2,$ respectively. In either case our conclusion would be that the middle bit flipped — but unfortunately the original quantum state $\alpha\vert 0\rangle + \beta \vert 1\rangle$ is now lost. This is the state we're trying to protect, so measuring in the standard basis is an unsatisfactory option.

What we can do instead is to use the following quantum circuit, feeding the encoded state into the top three qubits. This circuit nondestructively measures the parity of the standard basis states of the top two qubits as well as the bottom two qubits of the three-qubit encoding.

Under the assumption that at most one bit flipped, one can easily deduce from the measurement outcomes the location of the bit flip (or the absence of one). In particular, as the following four circuit diagrams illustrate, the measurement outcome $00$ indicates that no bit flip occurred, while the three other possibilities indicate which qubit experienced a bit flip.

Crucially, the state of the top three qubits does not collapse in any of the cases, which allows us to correct a bit-flip error if one has occurred — by simply applying it again. The following table summarizes the states we obtain from at most one bit flip, the measurement outcomes (which are called the syndrome in the context of error correction), and the correction needed to get back to the original encoding.

Once again, we're only considering the possibility that at most one bit-flip occurred. This wouldn't work correctly if two or three bit-flips occurred — and we also haven't considered other possible errors besides bit-flips.

Phase-flip errors

In the quantum setting, bit flip errors aren't the only errors we need to worry about. For instance, we also have to worry about phase-flip errors, which are described by $Z$ gates. Along the same lines as bit-flip errors, we can think about phase-flip errors as representing just another possibility for an error that can affect a qubit. However, as we will see in the last section of the lesson on the so-called discretization of errors for quantum error correcting codes, a focus on bit-flip errors and phase-flip errors turns out to be well-justified. Specifically, the ability to correct a bit-flip error, a phase-flip error, or both of these errors simultaneously automatically implies the ability to correct an arbitrary quantum error on a single qubit.

Unfortunately, the 3-bit repetition code doesn't protect against phase flips at all. For instance, suppose that a qubit state $\alpha\vert 0\rangle + \beta\vert 1\rangle$ has been encoded using the 3-bit repetition code, and a phase-flip error occurs on the middle qubit. This results in the state

which is exactly the state we would have obtained from encoding the qubit state $\alpha\vert 0\rangle - \beta\vert 1\rangle.$ Indeed, a phase-flip error on any one of the three qubits of the encoding has this same effect, which is equivalent to a phase-flip error occurring on the original qubit prior to encoding. Under the assumption that the original quantum state is an unknown state, there's therefore no way to detect that an error has occurred — because it's a perfectly valid encoding of a different qubit state. In particular, running the error detection circuit from before on the state $\alpha \vert 000\rangle - \beta \vert 111\rangle$ is certain to result in the syndrome $00,$ which wrongly suggests that no errors have occurred.

Meanwhile, there are now three qubits rather than one that could potentially experience phase-flip errors. So, in a situation in which phase-flip errors are assumed to occur independently on each qubit with some nonzero probability $p$ (similar to a binary symmetric channel except for phase flips rather than bit flips), this code actually increases the likelihood of a phase-flip error after decoding for small values of $p.$ In particular, we'll get a phase-flip error on the original qubit after decoding whenever there are an odd number of phase-flip errors on the three qubits of the encoding, which happens with probability $3 p (1 - p)^2 + p^3.$ This value is larger than $p$ when $0<p<1/2,$ so the code increases the probability of a phase-flip error for values of $p$ in this range.

Modified repetition code for phase-flip errors

We've observed that the 3-bit repetition code is completely oblivious to phase-flip errors, so it doesn't seem to be very helpful for dealing with this sort of error. We can, however, modify the 3-bit repetition code in a simple way so that it does detect phase flip errors. This modification will render the code oblivious to bit-flip errors — but as we'll see in the next section, we can combine together the 3-bit repetition code with this modified versions to obtain the Shor code, which can correct against both bit-flip and phase-flip errors.

Here is the modified version of the encoding circuit from earlier in the lesson, which will now be able to detect phase-flip errors. The modification is very simple: we simply apply a Hadamard gate to each qubit after performing the two controlled-NOT gates.

A Hadamard gate transforms a $\vert 0\rangle$ state into a $\vert + \rangle$ state, and a $\vert 1\rangle$ state into a $\vert - \rangle$ state, so the net effect is that the single qubit state $\alpha\vert 0\rangle + \beta \vert 1\rangle$ is encoded as

where $\vert {+}\,{+}\,{+} \rangle = \vert + \rangle \otimes \vert + \rangle \otimes\vert + \rangle$ and $\vert {-}\,{-}\,{-} \rangle = \vert - \rangle \otimes \vert - \rangle \otimes\vert - \rangle.$

A phase-flip error, or equivalently a $Z$ gate, flips between the states $\vert + \rangle$ and $\vert - \rangle,$ so this encoding will be useful for detecting (and correcting) phase-flip errors. Specifically, the error-detection circuit from earlier can be modified as follows.

In words, we take the circuit from before and simply put Hadamard gates on the top three qubits at both the beginning and the end. The idea is that the first three Hadamard gates transform $\vert + \rangle$ and $\vert - \rangle$ states back into $\vert 0\rangle$ and $\vert 1\rangle$ states, the same parity checks as before take place, and then the second layer of Hadamard gates transforms the state back to $\vert + \rangle$ and $\vert - \rangle$ states so that we recover our encoding. For future reference, let's observe that this phase-flip detection circuit can be simplified as follows.

The following four circuit diagrams describe how our modified version of the 3-bit repetition code, including the encoding step and the error detection step, functions when at most one phase-flip error occurs. The behavior is similar to the ordinary 3-bit repetition code for bit-flips.

Here's an analogous table to the one from above, this time considering the possibility of at most one phase-flip error.

Unfortunately, this modified version of the 3-bit repetition code can now no longer correct bit-flip errors. All is not lost, however. As suggested previously, we'll be able to combine these two codes into one code — the 9-qubit Shor code — that can correct both bit-flip and phase-flip errors (and therefore any error on a single qubit).

The 9-qubit Shor code

Now we turn to the 9-qubit Shor code, which is a quantum error correcting code obtained by combining together the two codes considered in the previous section: the 3-bit repetition code for qubits, which allows for the correction of a single bit-flip error, and the modified version of that code, which allows for the correction of a single phase-flip error.

Code description

To be precise, the 9-qubit Shor code is the code we obtain by concatenating the two codes from the previous section. This means that we first apply one encoding, which encodes one qubit into three, and then we apply the other encoding to each of the three qubits used for the first encoding, resulting in 9 qubits in total. While we could apply the two codes in either order in this particular case, we'll make an arbitrary choice to first apply the modified version of the 3-bit repetition code (which detects phase-flip errors), and then we'll encode each of the resulting three qubits independently using the original 3-bit repetition code (which detects bit-flip errors).

Here is a circuit diagram representation of this encoding.

As the figure suggests, we'll think about the 9 qubits of the Shor code as being grouped into three blocks of three qubits, where each block is obtained from the second encoding step (which is the ordinary 3-bit repetition code). The ordinary 3-bit repetition code, which here is applied three times independently, is called the inner code in this context, whereas the outer code is the code used for the first encoding step, which is the modified version of the 3-bit repetition code that detects phase-flip errors.

We can alternatively specify the code by describing how the two standard basis states for our original qubit get encoded.

Once we know this we can determine by linearity how an arbitrary qubit state vector gets encoded.

Errors and CNOT gates

To analyze how $X$ and $Z$ errors affect encodings of qubits, both for the 9-qubit Shor code as well as other codes, it will be helpful to observe a few simple relationships between these errors and CNOT gates. As we begin to analyze the 9-qubit Shor code, this is a reasonable moment to pause to do this.

The following circuit diagrams illustrate three basic relationships among $X$ gates and CNOT gates. In particular, applying an $X$ gate to the target qubit prior to a CNOT is equivalent to swapping the order and performing the CNOT first, but applying an $X$ gate to the control qubit prior to a CNOT is equivalent to applying $X$ gates to both qubits after the CNOT. Finally, applying $X$ gates to both qubits prior to a CNOT is equivalent to applying the CNOT first and then applying an $X$ gate to the control qubit. These relationships can easily be verified by performing the required matrix multiplications or computing the effect of the circuits on standard basis states.

The situation is similar for $Z$ gates, except that the roles of the control and target qubits switches. In particular, we have the three relationships depicted by the following quantum circuits.

Correcting bit-flip errors

Now we'll consider how errors can be detected and corrected using the 9-qubit Shor code, starting with bit-flip errors — which we'll generally refer to as $X$ errors hereafter for the sake of brevity.

To detect and correct $X$ errors, we can simply treat each of the three blocks in the encoding separately. Each block is an encoding of a qubit using the 3-bit repetition code, which protects against $X$ errors — so by performing the syndrome measurements and $X$ error corrections described in the previous section independently to each block, we can detect and correct up to one $X$ error per block. In particular, if there is at most one $X$ error on the 9 qubits of the encoding, this error will be detected and corrected by this procedure.

In short, correcting bit-flip errors is a simple matter for this code, due to the fact that the inner code corrects bit-flip errors.

Correcting phase-flip errors

Next we'll consider phase-flip errors, or $Z$ errors for brevity. This time it's not quite as clear what we should do because the outer code is the one that detects $Z$ errors, but the inner code seems to be somehow "in the way," making the detection and correct these errors slightly more difficult.

Suppose that a $Z$ error occurs on one of the 9 qubits of the Shor code, such as the one indicated in this diagram.

We've already observed what happens when a $Z$ error occurs when we're using the 3-bit repetition code — it's equivalent to a $Z$ error occurring prior to encoding. In the context of the 9-qubit Shor code, this means that a $Z$ error on any one of the three qubits within a block always has the same effect, which is equivalent to a $Z$ error occurring on the corresponding qubit prior to the inner code being applied.

For example, the circuit diagram above is equivalent to the following diagram. This can be reasoned using the relationships between $Z$ and CNOT gates described above, or by simply evaluating the circuits on an arbitrary qubit state $\vert\psi\rangle.$

This suggests one option for detecting and correcting $Z$ errors, which is to decode the inner code, leaving us with the three qubits used for the outer encoding along with six initialized workspace qubits. We can then check these three qubits of the outer code for $Z$ errors, and then finally we can re-encode using the inner code, to bring us back to the 9-qubit encoding we get from the Shor code. If we do detect a $Z$ error, we can either correct it prior to re-encoding with the inner code, or we can correct it after re-encoding, by applying a $Z$ gate to any of the qubits in that block.

Here's a circuit diagram that includes the encoding circuit and the error suggested above together with the steps just described (but not the actual correction step).

In this particular example, the syndrome measurement is $11,$ which locates the $Z$ error as having occurred on one of the qubits in the middle block.

One advantage of correcting $Z$ errors after the re-encoding step rather than before is that we can simplify the circuit above. The following circuit is equivalent but requires four fewer CNOT gates.

Once again, the syndrome doesn't indicate which qubit has been affected by a $Z$ error, but rather which block has experienced a $Z$ error, with the effect being the same regardless of which qubits within the block was affected. We can then correct the error by applying a $Z$ gate to any of the three qubits of whichever block was affected (or the top qubit of that block, let us say, to be concrete).

As an aside, here we see an example of degeneracy in a quantum error-correcting code, where we're able to correct certain errors ($Z$ errors in this case) without being able to identify them uniquely.

Simultaneous bit- and phase-flip errors

We've now seen how both $X$ and $Z$ errors can be detected and corrected using the 9-qubit Shor code, and in particular how at most one $X$ error or at most one $Z$ error can be detected and corrected. Now let's suppose that both a bit-flip and a phase-flip error occur, possibly on the same qubit. As it turns out, nothing different needs to be done in this situation from what has already been discussed — the code is able to detect and correct up to one $X$ error and one $Z$ error simultaneously without further modification.

To be more specific, $X$ errors are detected by applying the ordinary 3-bit repetition code syndrome measurement, which is performed separately on each of the three blocks of three qubits; and $Z$ errors are detected through the procedure described just above, which is equivalent to decoding the inner code, performing the syndrome measurement for the modified 3-bit repetition code for phase-flips, and then re-encoding. These two error detection steps — as well as the corresponding corrections — can be performed completely independently of one another, and in fact it doesn't matter in which order they're performed.

To see why this is, consider the example depicted in the following circuit diagram, where both an $X$ and a $Z$ error have affected the bottom qubit of the middle block.

Let's first observe that the ordering of the errors doesn't matter, in the sense that reversing the position of the $X$ and $Z$ errors yields an equivalent circuit. To be clear, $X$ and $Z$ do not commute, they anti-commute:

This implies that the following circuit is equivalent to the one just above up to a global phase factor of $-1.$

We can now move the $Z$ error just like before to obtain another equivalent circuit.

At this point it's evident that if the procedure to detect and correct $X$ errors is performed first, the $X$ error will be corrected, after which the procedure for detecting and correcting $Z$ errors can be performed to eliminate the $Z$ error as before.

Alternatively, the procedure to detect and correct $Z$ errors can be performed first. The fact that this procedure works as expected, even in the presence of one or more $X$ errors, follows from the fact that $X$ gates on any of the 9 qubits used for the encoding commute with all of the gates in our simplified circuit for measuring the syndrome for $Z$ errors. Thus, this syndrome measurement will still correctly identify which block has been affected by a $Z$ error. The fact that a $Z$ error on any block is corrected by applying a $Z$ gate to any qubit of that block, even if an $X$ error has also occurred, follows from the same argument as above concerning the ordering of $X$ and $Z$ gates giving us equivalent circuits up to a global phase.

It follows that the 9-qubit Shor code can correct an $X$ error, a $Z$ error, or both, on any one of the 9 qubits used for this code. In fact we can correct more errors than that, including multiple $X$ errors (as long as they fall into different blocks) or multiple $Z$ errors (as long as at most one block gets an odd number of them) — but going forward, what will be most relevant for the purposes of this lesson is that we can correct an $X$ error, a $Z$ error, or both on any one qubit.

Random errors

Before we move on to the last section of the lesson, which concerns arbitrary quantum errors, let's briefly consider the performance of the 9-qubit Shor code when errors represented by Pauli matrices occur randomly on the qubits.

To be more concrete, let's consider a simple noise model where errors occur independently on the qubits, with each qubit experiencing an error with probability $p$, and with no correlation between errors on different qubits — along similar lines to a binary symmetric channel for classical bits. We could assign different probabilities for $X,$ $Y,$ and $Z$ errors to occur, but to keep things as simple as possible we'll consider the worst case scenario for the 9-qubit Shor code, which is that a $Y$ error occurs on each of the affected qubits. A $Y$ error, by the way, is equivalent (up to an irrelevant global phase) to both an $X$ and a $Z$ error occurring on the same qubit, given that $Y = iXZ,$ which explains our apparent disregard of $Y$ errors up to this point.

Now, supposing that $\mathsf{Q}$ is a qubit in some particular state that we'd like to protect against errors, we can consider the option to use the 9-qubit Shor code. A natural question to ask is, "Should we use it?"

The answer is not necessarily "yes." If there's too much noise, meaning in this context that $p$ is too large, using the Shor code could actually make things worse — just like the 3-bit repetition code is worse than no code when $p$ is larger than one-half. But, if $p$ is small enough, then the answer is "yes," we should use the code, because it will decrease the likelihood that the encoded state becomes corrupted. Let's see why this is, and what it means for $p$ to be too large or small enough for this code.

The Shor code corrects any Pauli error on a single qubit, including a $Y$ error of course, but it doesn't properly correct two or more $Y$ errors. To be clear, we're assuming that we're using the $X$ and $Z$ error corrections described earlier in the section. Of course, if we knew in advance that we only had to worry about $Y$ errors, we would naturally choose our corrections differently — but that's cheating the noise model and we'd always be able to change the model by selecting different Pauli errors to make this new choice of corrections fail whenever two or more qubits are affected by errors.

So, the code protects $\mathsf{Q}$ so long as at most one of the 9 qubits is affected by an error, which happens with probability

Otherwise, with probability

the code fails to protect $\mathsf{Q}.$ Specifically, what that means in this context is that, up to a global phase, a non-identity Pauli operation will be applied to our qubit $\mathsf{Q}$ (as a logical qubit). That is, if $X$ and $Z$ errors are detected and corrected for the Shor code as described earlier in the lesson, we'll be left with the encoding of a state that's equivalent, up to a global phase, to the encoding of a non-identity Pauli operation applied to the original state of $\mathsf{Q}.$ A more succinct way to say this is that a logical error will have occurred. That may or may not have an effect on the original state of $\mathsf{Q}$ — or in other words the logical qubit we've encoded with 9 physical qubits — but for the sake of this analysis we're considering this event to mean failure.

On the other hand, if we din't bother using the code, our one and only qubit would suffer a similar fate (of being subject to a non-identity Pauli operation) with probability $p.$ The code helps when the first probability is smaller than the second:

Here's a plot that illustrates that for very small values of $p$ the code provides an advantage, with the break-even point occurring at about $0.0323.$

If $p$ is smaller than this break-even point, then the code helps; at the break-even point the probabilities are equal, so we're just wasting our time along with 8 qubits if we use the code; and beyond the break-even point we should absolutely not be using this code because it's increasing our chances of a logical error on $\mathsf{Q}.$

Three and a quarter percent or so may not seem like a very good break-even point, particular when compared to $50\%,$ which is the analogous break-even point for the 3-bit repetition code for classical information. This difference is, in large part, due to the fact that quantum information is more delicate and harder to protect than classical information. But also — while recognizing that the 9-qubit Shor code represents a brilliant discovery, as the world's first quantum error correcting code — we can acknowledge that it isn't actually a very good code in practical terms.

Discretization of errors

So far we've considered $X$ errors and $Z$ errors in the context of the 9-qubit Shor code. In this section we'll consider arbitrary errors — and what we'll find is that to handle such errors we actually don't need to do anything different from what we've already discussed; the ability to correct $X$ errors, $Z$ errors, or both, implies the ability to correct arbitrary errors. This phenomenon is sometimes called the discretization of errors.

Unitary qubit errors

Let's begin with single-qubit unitary errors. For example, such an error could correspond to a very small rotation of the Bloch sphere, possibly representing an error incurred by a gate that isn't perfect for instance. Or it could be any other unitary operation on a qubit and not necessarily one that's close to the identity. It might seem like correcting for such errors is difficult. After all, there are infinitely many possible errors like this, and it's inconceivable that we could somehow identify exactly what the error is and then undo it.

However, as long as we can correct for a bit-flip, a phase-flip, or both, then we will in fact succeed in correcting an arbitrary single-qubit unitary error using the procedures described earlier in the lesson. The reasoning for why this is begins with the recognition that we can express an arbitrary $2 \times 2$ unitary matrix $U,$ representing an error on a single qubit, as a linear combination of the four Pauli matrices (including the identity matrix).

As we will see, when the error detection circuits are run, the measurements that give us the syndrome bits effectively collapse the state of the encoding, probabilistically, to one where an error (or lack of an error) represented by one of the four Pauli matrices has taken place. (A necessary but not sufficient condition on $\alpha,$ $\beta,$ $\gamma,$ and $\delta$ for the linear combination above to be unitary is that $\vert\alpha\vert^2 + \vert\beta\vert^2 + \vert\gamma\vert^2 + \vert\delta\vert^2 = 1,$ and indeed the values $\vert\alpha\vert^2,$ $\vert\beta\vert^2,$ $\vert\gamma\vert^2,$ and $\vert\delta\vert^2$ are the probabilities with which the encoded state collapses to one for which the corresponding Pauli error has occurred.)

To explain how this works in greater detail, it will be convenient to use subscripts to indicate which qubit a given qubit unitary operation acts upon. For example, using Qiskit's qubit numbering convention $(\mathsf{Q}_8,\mathsf{Q}_7,\ldots,\mathsf{Q}_0)$ to number the 9 qubits used for the Shor code, we have these expressions for various unitary operations on single qubits, where in each case we tensor the unitary matrix with the identity matrix on every other qubit.

So, in particular, for a given qubit unitary operation $U,$ we can specify the action of $U$ applied to qubit $k$ by the following formula, which is similar to the one before except that each matrix represents an operation applied to qubit $k.$

Now suppose that $\vert\psi\rangle$ is the 9-qubit encoding of a qubit state. If the error $U$ takes place on qubit $k,$ we obtain the state $U_k \vert\psi\rangle,$ which can be expressed as a linear combination of Pauli operations acting on $\vert\psi\rangle$ as follows.

At this point let's make the substitution $Y = iXZ.$

Now consider the error-detection and correction steps described previously. We can think about the measurement outcomes for the three inner code parity checks along with the one for the outer code collectively as a single syndrome consisting of 8 bits. Just prior to the actual standard basis measurements that produce these syndrome bits, the state has the following form.

To be clear, we have two systems at this point. The system on the left is the 8 qubits we'll measure to get the syndrome, where $\vert \mathbb{I} \text{ syndrome}\rangle,$$\vert X_k \text{ syndrome}\rangle,$ and so on, refer to whatever 8 qubit standard basis state is consistent with the corresponding error (or, in the case of $\mathbb{I},$ non-error). The system on the right is the 9 qubits we're using for the encoding.

Notice that these two systems are now correlated (in general), and this is the key to why this works. By measuring the syndrome, the state of the 9 qubits on the right effectively collapses to one in which a Pauli error consistent with the measured syndrome has been applied to one of the qubits. Moreover, the syndrome itself provides enough information so that we can undo the error and recover the original encoding $\vert\psi\rangle.$ In particular, if the syndrome qubits are measured and the appropriate corrections are made, we obtain a state of the following form

where

Critically, this is a product state: we have our original, uncorrupted encoding as the right-hand tensor factor, and on the left we have a density matrix $\xi$ that describes a random error syndrome. There is no longer any correlation with the system on the right, which is the one we care about, because the errors have been corrected. At this point we can throw the syndrome qubits away or reset them so we can use them again. This is how the randomness — or entropy — created by errors is removed from the system.

This is the discretization of errors for the special case of unitary errors. In essence, by measuring the syndrome we effectively project the error onto an error that's described by a Pauli matrix.

At first glance it may seem too good to be true that we can correct for arbitrary unitary errors like this, even errors that are tiny and hardly noticeable on their own. But what's important to realize here is that this is a unitary error on a single qubit, and by the design of the code, a single qubit operation can't change the state of the logical qubit that's been encoded. All it can possibly do is to move the state out of the subspace of valid encodings, but then the error detections collapse the state and the corrections bring it back to where it started.

Arbitrary qubit errors

Finally, let's consider arbitrary, not necessarily unitary errors. To be precise, we'll consider an error described by an arbitrary qubit channel $\Phi.$ For example, this could be a dephasing or depolarizing channel, a reset channel, or a strange channel that we've never thought about before.

The first step is to consider any Kraus representation of $\Phi.$

This is a qubit channel, so each $A_j$ is a $2\times 2$ matrix, which we can express as a linear combination of Pauli matrices.

This allows us to express the action of the error $\Phi$ on a chosen qubit $k$ in terms of Pauli matrices as follows.

In short, we've simply expanded out all our Kraus matrices as linear combinations of Pauli matrices.

If we now compute and measure the error syndrome, and correct for any errors that are revealed, we'll obtain a similar sort of state to what we had in the case of a unitary error:

where this time we have

The details are a bit messier and are not shown here. Conceptually speaking, the idea is identical to the unitary case.

Generalizations

The discretization of errors generalizes to other quantum error-correcting codes, including ones that can detect and correct errors on multiple qubits. In such a case, errors on multiple qubits can be expressed as tensor products of Pauli matrices, and correspondingly different syndromes specify Pauli operation corrections that might be performed on multiple qubits rather than just one qubit.

Again, by measuring the syndrome, errors are effectively projected or collapsed onto a discrete set of possibilities represented by tensor products of Pauli matrices, and by correcting for those Pauli errors, we can recover the original encoded state. Meanwhile, whatever randomness is generated in the process is moved into the syndrome qubits, which are discarded or reset, thereby removing the randomness generated in this process from the system storing the encoding.