Shor's code and basic Quantum Error Correction (with calculations)
Sometimes the calculations help...
The effects of an arbitrary error being handled by Shor’s code seems to be dealt in either a hand-wavy manner or in a super-technical manner(at least in all the literature I came across online and in Nielsen and Chuang).
The main motivation behind this post is to show you the calculations behind it. Scroll to the very bottom if you want to only see that.
For all the others who want to build up to it, I have tried to make this post as self-contained as possible. I haven’t gone into the theory too much (stabilizer codes and more), but there’s plenty of resources available.
(PS. Please let me know if there are any improvements that can be made to the post.)
So let’s start.
Primer
The objective is to reduce errors as much as possible and maintain fidelity as high as possible.
In classical systems, errors occur due to interference, signal distortion and attenuation. In quantum circuits, decoherence is a major problem due to the sensitive nature of the setup. The nature of the system also gives rise to more “variety” in the errors that can occur, as we shall see.
For our purposes, we need to understand only one technique that is used in classical error correction.
Repetition code:
Let us say that we want to transfer a classical bit through a noisy channel (eg. a region of intense electric fields) where the probability of a bitflip is p.
To mitigate this, instead of passing the bit as it is (as 0 or 1), we pass 000 or 111 instead.
If the bits received by B has one bit whose state differs from the other two, we follow the majority.
This method fails if two or more bits are flipped by the channel.
Thus, this method is beneficial only when p < 0.5.
The QEC methods we shall cover will all be based on this.
QEC methods-
3 Qubit bit flip channel:
In this channel, with a probability p the bit gets flipped, thus:
Quirk Circuit and Q-Composer circuit
Here, q[0] is the initial information carrying qubit, which for the purposes of explanation I have encoded as:
Through the application of CNOT gates on q[1] and q[2], we get:
Let us assume that the middle qubit is flipped by the channel.
This flipping changes the state of the syndrome qubits q[3] and q[4] which are controlled by the clever application of CNOT gates. Since our syndrome qubits read 11, we determine that the middle qubit was affected and we can apply the X gate to get our original data.
(Alternatively, we can choose to ignore that qubit’s data and not apply the correction.)
Note that the measurement of the syndrome qubits does not give us any information about the states of the qubits that are carrying the data, all it tells us is where the error has occurred.
3 Qubit phase flip channel:
In this channel, with a probability p the phase of the qubit gets flipped, thus:
We see that just as the bit flip channel flips a 0 to a 1, we see that the phase flip channel flips |+⟩ to |-⟩.
The only modifications we have to make is to encode our information into the above Hadamard basis states, which can be done by a Hadamard gate.
Once the error is detected, we can apply the inverse gate (which is the Hadamard itself) to get back our error-affected information in our computational basis states and apply the required correction.
Quirk circuit and Q-Composer circuit
Here, q[0] is the initial information carrying qubit, for the purpose of demonstration encoded as:
Through the CNOT gates, we get:
After the Hadamard transform, we get:
Let us assume that the middle qubit is phase flipped by the channel, due to which we get:
Applying the Hadamard transform again gives us:
Now,we can apply the same procedure we did for the bit flip channel. Since our syndrome qubits read 11, we determine that the middle qubit was affected and we can apply the X gate to get our intended data.
Shor's Code
Before we dive into Shor’s code, there is one final point we need to consider.
In the repetition code setup, if we are only concerned with the bitflip error in a particular qubit, we can correct the error without having to perform any measurements to if there is an error.
This collection of gates does bitflip corrections for the first qubit (and it’s quite easy to see).
This is the key element of Shor’s code.
Coming to the construction:
Quirk circuit and Q-Composer circuit (It will be helpful to open them on a new tab to constantly refer to.)
This circuit is able to correct bit flip and phase flip errors (and can be shown to handle an arbitrary error as well) by creating a hierarchy inside the circuit.
Here we are not concerned in correcting the errors that occur in the other qubits, but we use them to rectify the error in the first qubit.
The inner layer corrects bit flips, while the outer layer corrects phase flips.
The inner layer has three groups, with each group having a primary qubit and two syndrome qubits.
In this case, the inner groups are:
The outer layer consists of the primary qubits of the groups:
(These are the groups qubits on which the Hadamard has been applied.)
For our purposes here, we have set the original information carrying qubit to be:
After the application of the CNOT gates and the Hadamard (and the second set of CNOT gates), the state we have obtained (marked at the divider) is:
Let us see what happens under the following errors:
Bit flips:
Bit flip of 1st qubit of inner layer's 1st group:
When the CNOT gates are applied concurrently in the three groups, it flips the two syndrome bits associated to the first group of the inner layer, due to which:
As we can see, in the groups where there is no bitflip the CNOT gates do the job of “turning off” the syndrome qubits associated to that group. The code rectifies this error with the Toffoli gate:
Now, the Hadamard gate only acts on the primary qubits which we can see are not corrupted, so everything else continues as normal.
Thus, this circuit can deal with single bit flip errors within any group.
For a single flip within a group:
Phase flips:
We will see how the outer layer deals with the phase flip error.
Phase flip of first qubit in 1st inner group:
Why does the phase flip of one qubit in an inner group cause the phase flip of all the qubits in that inner group?
The maths is clear on this, since:
But what is the physical interpretation of this? I hope to cover this in the future.
After CNOT and Toffoli gates:
On applying the Hadamard gate on the primary qubits (1st, 4th and 7th qubit), we get:
It is clear to see that even if a bitflip had occurred in any of the inner groups (or even on the same qubit), it would have been corrected prior to the application of the Hadamard gate and not affected the state of the primary qubits.
For convenience, we neglect the syndrome bits of each inner group and simplify. (We are able to ignore the syndrome qubits as their measurement does not affect the primary qubits in this case.)
Thus, we see that due to the way the circuit has been constructed, the phase flip in the first inner group results in the bitflip of the first primary qubit.
After this, we apply the gate combination that we had defined in the starting of this section on Shor’s code; treating the second and third primary qubits as the syndrome qubits to the first primary qubit.
Unlike the bit flips, this circuit cannot deal with phase flip in more than one inner group.
Thus, this circuit not only is error-correcting for errors on the first qubit, the measurement of the other 8 qubits tell us where the bit flip and the phase flip occurred.
Arbitrary error:
There is an astronomically low possibility that an error or interference with a qubit causes a perfect bit or phase flip. More often errors cause the rotation of the qubit’s state about a random axis by an arbitrary degree. Shor’s code has the ability to correct such an error.
First is the mathematical explanation of why is can deal with an arbitrary errors on a single qubit:
Let us assume that the error does not cause the collapse of the qubit’s state itself. Following this assumption, we can say that the error is equivalent to the action of an arbitrary gate U.
For a four dimensional complex vector, I have made the following adjustment in notation:
Through this, we can see that every unitary matrix can be defined as a unit vector in this space. We can show that a set of unitary matrices span the 4-dimensional complex vector space:
The arbitrary gate is equivalent to the linear combination of the elementary gates with some probability amplitude.
Here, sum of squares of coefficients=1.
Since the circuit can deal with these gates separately, it can deal with any arbitrary gate.
What does this mean?
The result above tells us that the effect of an arbitrary error/gate acting on the qubit is equivalent to a superposition of the qubit's state after the action of elementary gates I,X,Z and/or XZ on it.
Measurement of the other 8 qubits will collapse the error that has occurred on the first qubit to that of an elementary gate’s action (and it is clear that measuring the 8 qubits isn’t necessary for the error to be corrected in the first place). Since the code can deal with the action of elementary gates, due to the reasoning above it can deal with the action of arbitrary gates as well.
Won't the measurement of the qubit collapse the information encoded in it to classical information, thus rendering the circuit useless?
The circuit consists of 1 main qubit and 8 qubits that are dependent on it. The key point is that the measurement of the the dependent qubits tells us which operation has acted, not the state itself. In other words, measuring U|Ψ⟩ collapses it to either I|Ψ⟩,X|Ψ⟩,Z|Ψ⟩ or XZ|Ψ⟩. Deferred measurement principle deals with measurement on the first qubit.
This is best showed by an example:
Let the error be the equivalent of the action of the Hadamard gate.
This implies that on the measurement of the other 8 qubits, we will see a 50% chance of a bitflip having acted, or 50% chance of phaseflip having acted.
Let the first qubit’s state be:
As before, we set up so that we get:
We will now be ignoring the 2nd and the 3rd group, and solely focusing on the first group’s expression.
Applying the Hadamard (which serves as the error) on the first group’s first qubit gives:
After the CNOT gates:
After the Toffoli gate (that corrects the bitflip if triggered by syndrome qubits):
As we can see, if we were to measure the error syndrome and it were to be 11, then the net result of the Hadamard gate would be equivalent to a bitflip. If 00 is measured, then the net effect of the Hadamard gate would be indistinguishable from a phase flip.
The Hadamard gate’s action presents itself as a superposition of the action of the X and Z with equal probability, and the measurement collapses it to one of the above.
Calculations for an arbitrary error:
U's operation on a qubit can be written as:
Let us say that this error occurs on the first qubit of the first inner group.
Which can be expanded as:
After CNOT and Toffoli,
After Hadamard on primary qubits (and neglecting syndrome bits of inner groups since we are not measuring them here):
Which further simplifies to:
After the final set of CNOT and Toffoli operations:
Which can be regrouped as:
Giving the final result of:
In the last two steps, we have only performed matrix manipulations, and its “physical” interpretation is that the measurement of the other two primary qubits and all the remaining syndrome qubits tells us what error has been measured and where.