PHYS598500 · Week 10
Detecting Errors Using Syndromes
Quantum error correction
A qubit must couple to its control and readout lines. Noise reaches it through the same couplings.
Good physical qubits have errors near \(10^{-3}\) per gate. Many algorithms need errors near \(10^{-15}\).
Quantum error correction stores one logical qubit in several physical qubits.
In each cycle, measure the syndrome, find the error and correct it. The syndrome shows the error. It does not show the stored state.
\(c_0|0\rangle+c_1|1\rangle\)encode
store it in
several qubitserrors
bit flip \(\hat X\),
phase flip \(\hat Z\)syndrome
measure parities
with ancillascorrection
undo the error
with \(\hat X\) or \(\hat Z\)repeat in every cycle
Google Quantum AI, Nature 595, 383 (2021).
PHYS598500 · Week 10
Quantum errors
Errors on one qubit
Bit flip \(\hat X\): \(c_0|0\rangle+c_1|1\rangle\to c_0|1\rangle+c_1|0\rangle\).
Phase flip \(\hat Z\): \(c_0|0\rangle+c_1|1\rangle\to c_0|0\rangle-c_1|1\rangle\). A classical bit has no such error.
Bit and phase flip \(\hat Y=i\hat X\hat Z\): \(c_0|0\rangle+c_1|1\rangle\to ic_0|1\rangle-ic_1|0\rangle\).
An error can also be a small turn by \(2\varepsilon\) about any unit axis \((n_x,n_y,n_z)\):
A code must handle all of them.
PHYS598500 · Week 10
Repetition code
Classical repetition code
Noise can flip a stored bit: \(0\to1\) or \(1\to0\).
Use three bits. Bit 1 holds the information, \(0\) or \(1\). Bits 2 and 3 start at \(0\).
The encoder sets bits 2 and 3 equal to bit 1: \(000\to000\), \(100\to111\).
One logical bit consists of three physical bits.
To get the information back, read the three bits and take the majority:
| stored 111, read | flips | majority | result |
|---|---|---|---|
| 111 | 0 | 1 | right |
| 011, 101, 110 | 1 | 1 | right |
| 001, 010, 100 | 2 | 0 | wrong |
| 000 | 3 | 0 | wrong |
One flip is corrected. Two or three flips give the wrong bit.
How often the vote fails
Each bit flips with the probability \(p\), independently of the others.
| flips | probability | vote |
|---|---|---|
| 0 | \((1-p)^3\) | right |
| 1 | \(3p(1-p)^2\) | right |
| 2 | \(3p^2(1-p)\) | wrong |
| 3 | \(p^3\) | wrong |
The vote is wrong when two or three bits flip:
Example: at \(p=1\,\%\), one bit alone is wrong in \(1\,\%\) of the runs. The vote is wrong in only \(0.03\,\%\).
The code helps only if the vote is wrong less often than one bit, \(P_{\rm fail}<p\). This is true for \(p<\frac{1}{2}\).
Four problems
The classical code encodes, reads the bits and votes. For a qubit in an arbitrary state \(c_0|0\rangle+c_1|1\rangle\), four problems stop this method:
| problem | reason | |
|---|---|---|
| 1 | no copies | an arbitrary state cannot be copied |
| 2 | no direct readout | a readout gives 0 or 1 and destroys \(c_0\), \(c_1\) |
| 3 | phase errors | \(\hat Z\) changes a sign; a bit has no such error |
| 4 | continuous errors | small turns and random phases, not only flips |
In 1995, Shor found a code with nine qubits that solves all four.
P. W. Shor, Phys. Rev. A 52, R2493 (1995).
PHYS598500 · Week 10
No-cloning theorem
No-cloning theorem
Suppose that a gate \(\hat U\) copies an arbitrary state: \(\hat U|\psi\rangle|0\rangle=|\psi\rangle|\psi\rangle\). This includes \(|0\rangle\) and \(|1\rangle\).
\(\hat U\) is linear. For an arbitrary \(|\psi\rangle=c_0|0\rangle+c_1|1\rangle\):
But two copies are:
The two are equal only if \(c_0=0\) or \(c_1=0\). So no gate copies an arbitrary state. This is the no-cloning theorem.
Thus error correction cannot keep backup copies of an arbitrary state \(c_0|0\rangle+c_1|1\rangle\).
W. K. Wootters and W. H. Zurek, Nature 299, 802 (1982); D. Dieks, Phys. Lett. A 92, 271 (1982).
Inner-product proof of no-cloning
Suppose that a gate \(\hat U\) copies two arbitrary states \(|\psi\rangle\) and \(|\phi\rangle\):
\(\hat U\) is unitary, so the inner product before and after \(\hat U\) is the same:
So \(\langle\psi|\phi\rangle=0\) or \(1\): the two states are orthogonal or equal. But arbitrary states can have other inner products, for example \(\langle0|+\rangle=\frac{1}{\sqrt2}\). So no gate copies arbitrary states.
\(|0\rangle\) and \(|1\rangle\) can be copied, because \(\langle0|1\rangle=0\). \(|0\rangle\) and \(|+\rangle\) cannot, also when we know the two states.
M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information (Cambridge University Press, 2000), Box 12.1.
No-cloning with a copier state
A copier can also use its own qubits in a state \(|M\rangle\). Suppose that a gate \(\hat U\) copies two arbitrary states \(|\psi\rangle\) and \(|\phi\rangle\). After the copy, these qubits can be in different states \(|M_\psi\rangle\) and \(|M_\phi\rangle\):
\(\hat U\) is unitary, so the inner product before and after \(\hat U\) is the same:
If \(\langle\psi|\phi\rangle\neq0\), then \(\langle\psi|\phi\rangle\langle M_\psi|M_\phi\rangle=1\). The magnitude of each factor is at most 1, so \(|\langle\psi|\phi\rangle|=1\).
So \(|\langle\psi|\phi\rangle|=0\) or \(1\): the two states are orthogonal or the same state up to a global phase. But arbitrary states can have other values, for example \(|\langle0|+\rangle|=\frac{1}{\sqrt2}\). So even with \(|M\rangle\), no \(\hat U\) copies arbitrary states.
A measurement and a gate that uses its result are also one \(\hat U\) on more qubits. So no process copies an arbitrary state.
W. K. Wootters and W. H. Zurek, Nature 299, 802 (1982); M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information (Cambridge University Press, 2000), Box 12.1.
Copying with a CNOT
The classical encoder sets bits 2 and 3 equal to bit 1. For qubits, a CNOT does this:
Try the same for \(|+\rangle=\frac{1}{\sqrt2}\big(|0\rangle+|1\rangle\big)\). The CNOT acts on each term:
Two copies of \(|+\rangle\) would be:
The two states are not equal. The CNOT does not copy \(|+\rangle\), so it does not copy an arbitrary state. It entangles the two qubits.
Copying in a known basis
Orthogonal states can be copied. The CNOT copies \(|0\rangle\) and \(|1\rangle\).
For \(|+\rangle\) and \(|-\rangle\), use \(\hat H\) on qubit 1, the CNOT, then \(\hat H\) on both qubits:
The inner product is \(\langle+|-\rangle=0\) before and \(\langle+|-\rangle^2=0\) after. A unitary gate allows this.
This gate does not copy \(|0\rangle\). It entangles the two qubits, as the CNOT does with \(|+\rangle\).
Each copier works only for its own orthogonal states. So no copier works for an arbitrary state.
| input | after \(\hat H\) | after CNOT | after \(\hat H\), \(\hat H\) |
|---|---|---|---|
| \(|+\rangle|0\rangle\) | \(|0\rangle|0\rangle\) | \(|00\rangle\) | \(|+\rangle|+\rangle\) |
| \(|-\rangle|0\rangle\) | \(|1\rangle|0\rangle\) | \(|11\rangle\) | \(|-\rangle|-\rangle\) |
| \(|0\rangle|0\rangle\) | \(|+\rangle|0\rangle\) | \(\tfrac{1}{\sqrt2}\big(|00\rangle+|11\rangle\big)\) entangled | \(\tfrac{1}{\sqrt2}\big(|00\rangle+|11\rangle\big)\) entangled |
PHYS598500 · Week 10
Three-qubit code
Encoding without copies
Two CNOT gates spread the amplitudes of an arbitrary state over three qubits:
Logical states: \(|0_L\rangle=|000\rangle\), \(|1_L\rangle=|111\rangle\). Encoded state: \(|\psi_L\rangle=c_0|0_L\rangle+c_1|1_L\rangle\).
This is not three copies. Three copies use all 8 basis states. The encoded state uses 2.
No qubit alone holds \(c_0\) and \(c_1\). They are in the correlation of the three qubits.
Computational subspace and code subspace
Each qubit uses two levels, \(|0\rangle\) and \(|1\rangle\): the computational subspace.
Three qubits have \(2^3=8\) basis states, \(|000\rangle\) to \(|111\rangle\). A state of the three qubits has 8 amplitudes.
| subspace | basis states |
|---|---|
| code subspace | \(|000\rangle\), \(|111\rangle\) |
| error subspace of qubit 1 | \(|100\rangle\), \(|011\rangle\) |
| error subspace of qubit 2 | \(|010\rangle\), \(|101\rangle\) |
| error subspace of qubit 3 | \(|001\rangle\), \(|110\rangle\) |
The code subspace holds the encoded states \(c_0|000\rangle+c_1|111\rangle\). It uses 2 of the 8 basis states.
The other 6 basis states are empty. An error moves the state there, so we can see it.
Error subspaces
An \(\hat X\) error flips one qubit in both basis states. \(c_0\) and \(c_1\) do not change:
| error | state | subspace |
|---|---|---|
| none | \(c_0|000\rangle+c_1|111\rangle\) | code subspace |
| \(\hat X_1\) | \(c_0|100\rangle+c_1|011\rangle\) | error on qubit 1 |
| \(\hat X_2\) | \(c_0|010\rangle+c_1|101\rangle\) | error on qubit 2 |
| \(\hat X_3\) | \(c_0|001\rangle+c_1|110\rangle\) | error on qubit 3 |
| \(\hat X_1\hat X_2\) | \(c_0|110\rangle+c_1|001\rangle\) | error on qubit 3 |
\(\hat X_1\), \(\hat X_2\), \(\hat X_3\) each lead to their own pair of basis states: three error subspaces.
The four subspaces do not overlap, and \(4\times2=8\). Find the subspace, and you know the error.
Two errors, \(\hat X_1\hat X_2\), land in the subspace of \(\hat X_3\).
PHYS598500 · Week 10
Syndrome measurement
Measurement collapse of the encoded state
Classical method: read all three qubits and compare them.
After \(\hat X_2\), the state is \(c_0|010\rangle+c_1|101\rangle\). The readout gives 010 with the probability \(|c_0|^2\), or 101 with \(|c_1|^2\).
Both results show that qubit 2 differs. The error is found.
But after the readout the state is \(|010\rangle\) or \(|101\rangle\). \(c_0\) and \(c_1\) are lost.
We must find the error without reading the qubits.
One-qubit measurement with an ancilla
An extra qubit, the ancilla, starts in \(|0\rangle_a\). One CNOT from data 1 writes the value of data 1 on it:
Readout 0 leaves data 1 in \(|0\rangle\). Readout 1 leaves it in \(|1\rangle\).
| data | after the CNOT | readout | data after readout |
|---|---|---|---|
| \(|0\rangle\) | \(|0\rangle|0\rangle_a\) | 0 · \(\hat Z_1=+1\) | \(|0\rangle\) |
| \(|1\rangle\) | \(|1\rangle|1\rangle_a\) | 1 · \(\hat Z_1=-1\) | \(|1\rangle\) |
| \(c_0|0\rangle+c_1|1\rangle\) | \(c_0|0\rangle|0\rangle_a+c_1|1\rangle|1\rangle_a\) entangled | 0 with \(|c_0|^2\) 1 with \(|c_1|^2\) | \(|0\rangle\) \(|1\rangle\) \(c_0\), \(c_1\) lost |
One-qubit measurement with an ancilla
An extra qubit, the ancilla, starts in \(|0\rangle_a\). One CNOT from data 1 writes the value of data 1 on it:
Readout 0 keeps the basis states with \(b_1=0\). Readout 1 keeps those with \(b_1=1\).
The ancilla must take a parity, not the value of one qubit.
| data | after the CNOT | readout | data after readout |
|---|---|---|---|
| \(|00\rangle\) | \(|00\rangle|0\rangle_a\) | 0 · \(\hat Z_1=+1\) | \(|00\rangle\) |
| \(|01\rangle\) | \(|01\rangle|0\rangle_a\) | 0 · \(\hat Z_1=+1\) | \(|01\rangle\) |
| \(|10\rangle\) | \(|10\rangle|1\rangle_a\) | 1 · \(\hat Z_1=-1\) | \(|10\rangle\) |
| \(|11\rangle\) | \(|11\rangle|1\rangle_a\) | 1 · \(\hat Z_1=-1\) | \(|11\rangle\) |
| \(c_0|00\rangle+c_1|11\rangle\) | \(c_0|00\rangle|0\rangle_a+c_1|11\rangle|1\rangle_a\) entangled | 0 with \(|c_0|^2\) 1 with \(|c_1|^2\) | \(|00\rangle\) \(|11\rangle\) \(c_0\), \(c_1\) lost |
Parity check on two qubits
Ask a smaller question: do qubits 1 and 2 have the same value? \(\hat Z\) gives the sign −1 to \(|1\rangle\). So \(\hat Z_1\hat Z_2\) multiplies the signs of the two qubits:
\(b_1\oplus b_2\) is the sum modulo 2, the parity. +1: the same. −1: different. It does not ask for the values: \(|00\rangle\) and \(|11\rangle\) both give +1.
So \(\hat Z_1\hat Z_2\big(c_0|00\rangle+c_1|11\rangle\big)=+\big(c_0|00\rangle+c_1|11\rangle\big)\). A measurement of \(\hat Z_1\hat Z_2\) gives +1 and keeps \(c_0\) and \(c_1\).
Parity onto an ancilla
We can read only single qubits. So we copy the parity onto an extra qubit, the ancilla, with two CNOT gates:
After the first CNOT, the ancilla is entangled with the data:
After the second CNOT, it is not: \(\big(c_0|00\rangle+c_1|11\rangle\big)|0\rangle_a\). The ancilla holds only the parity. Reading it does not touch \(c_0\), \(c_1\).
| data | after CNOT 1 | after CNOT 2 | readout |
|---|---|---|---|
| \(|00\rangle\) | \(|00\rangle|0\rangle_a\) | \(|00\rangle|0\rangle_a\) | 0 · even |
| \(|01\rangle\) | \(|01\rangle|0\rangle_a\) | \(|01\rangle|1\rangle_a\) | 1 · odd |
| \(|10\rangle\) | \(|10\rangle|1\rangle_a\) | \(|10\rangle|1\rangle_a\) | 1 · odd |
| \(|11\rangle\) | \(|11\rangle|1\rangle_a\) | \(|11\rangle|0\rangle_a\) | 0 · even |
| \(c_0|00\rangle+c_1|11\rangle\) | \(c_0|00\rangle|0\rangle_a+c_1|11\rangle|1\rangle_a\) entangled | \(\big(c_0|00\rangle+c_1|11\rangle\big)|0\rangle_a\) | 0 · even |
| \(c_0|01\rangle+c_1|10\rangle\) | \(c_0|01\rangle|0\rangle_a+c_1|10\rangle|1\rangle_a\) entangled | \(\big(c_0|01\rangle+c_1|10\rangle\big)|1\rangle_a\) | 1 · odd |
| \(c_0|10\rangle+c_1|01\rangle\) | \(c_0|10\rangle|1\rangle_a+c_1|01\rangle|0\rangle_a\) entangled | \(\big(c_0|10\rangle+c_1|01\rangle\big)|1\rangle_a\) | 1 · odd |
Parity checks with CZ gates
CZ gives the sign −1 only to \(|11\rangle\). A CNOT is a CZ between two \(\hat H\) gates on the target qubit.
The parity check puts two CNOT gates onto the ancilla. Each CNOT is \(\hat H\), CZ, \(\hat H\). Because \(\hat H\hat H=\hat I\), the two \(\hat H\) gates in the middle cancel:
After the first \(\hat H\), the ancilla is in \(|+\rangle_a\). Each data qubit in \(|1\rangle\) changes it between \(|+\rangle_a\) and \(|-\rangle_a\).
Even parity gives \(|+\rangle_a\), odd parity \(|-\rangle_a\). The last \(\hat H\) gives \(|b_1\oplus b_2\rangle_a\).
For \(c_0|00\rangle+c_1|11\rangle\), the ancilla is entangled with the data between the two CZ gates. At the end, it is not.
| data | after \(\hat H\) | after CZ | after CZ | after \(\hat H\) | readout |
|---|---|---|---|---|---|
| \(|00\rangle\) | \(|+\rangle_a\) | \(|+\rangle_a\) | \(|+\rangle_a\) | \(|0\rangle_a\) | 0 · even |
| \(|01\rangle\) | \(|+\rangle_a\) | \(|+\rangle_a\) | \(|-\rangle_a\) | \(|1\rangle_a\) | 1 · odd |
| \(|10\rangle\) | \(|+\rangle_a\) | \(|-\rangle_a\) | \(|-\rangle_a\) | \(|1\rangle_a\) | 1 · odd |
| \(|11\rangle\) | \(|+\rangle_a\) | \(|-\rangle_a\) | \(|+\rangle_a\) | \(|0\rangle_a\) | 0 · even |
| \(c_0|00\rangle+c_1|11\rangle\) | \(|+\rangle_a\) | entangled | \(|+\rangle_a\) | \(|0\rangle_a\) | 0 · even |
Parity checks on three qubits
The three-qubit code uses two parity checks. \(\hat Z_1\hat Z_2\) compares qubits 1 and 2. \(\hat Z_2\hat Z_3\) compares qubits 2 and 3. Each check does not act on the third qubit:
+1: the same. −1: different. It does not ask for the values.
\(\hat Z_1\hat Z_2\) gives +1 on both code states, \(|000\rangle\) and \(|111\rangle\). So it does not change \(c_0|000\rangle+c_1|111\rangle\). An operator like this is a stabilizer of the code. \(\hat Z_2\hat Z_3\) is the second stabilizer.
The code subspace is where both stabilizers give +1. \(\hat X_1\) anticommutes with \(\hat Z_1\hat Z_2\) (\(\hat X_1\hat Z_1=-\hat Z_1\hat X_1\)), so after \(\hat X_1\) that stabilizer gives −1.
Syndrome
Both basis states of a subspace give the same answers. So each subspace has its own pair of stabilizer results, the syndrome:
| subspace | basis states | \(\hat Z_1\hat Z_2\) | \(\hat Z_2\hat Z_3\) | \(\hat Z_1\hat Z_2\) on a superposition | \(\hat Z_2\hat Z_3\) on a superposition |
|---|---|---|---|---|---|
| code | \(|000\rangle\), \(|111\rangle\) | +1 | +1 | \(\begin{aligned}&\hat Z_1\hat Z_2\big(c_0|000\rangle+c_1|111\rangle\big)\\&\quad=+1\,\big(c_0|000\rangle+c_1|111\rangle\big)\end{aligned}\) | \(\begin{aligned}&\hat Z_2\hat Z_3\big(c_0|000\rangle+c_1|111\rangle\big)\\&\quad=+1\,\big(c_0|000\rangle+c_1|111\rangle\big)\end{aligned}\) |
| error on qubit 1 | \(|100\rangle\), \(|011\rangle\) | −1 | +1 | \(\begin{aligned}&\hat Z_1\hat Z_2\big(c_0|100\rangle+c_1|011\rangle\big)\\&\quad=-1\,\big(c_0|100\rangle+c_1|011\rangle\big)\end{aligned}\) | \(\begin{aligned}&\hat Z_2\hat Z_3\big(c_0|100\rangle+c_1|011\rangle\big)\\&\quad=+1\,\big(c_0|100\rangle+c_1|011\rangle\big)\end{aligned}\) |
| error on qubit 2 | \(|010\rangle\), \(|101\rangle\) | −1 | −1 | \(\begin{aligned}&\hat Z_1\hat Z_2\big(c_0|010\rangle+c_1|101\rangle\big)\\&\quad=-1\,\big(c_0|010\rangle+c_1|101\rangle\big)\end{aligned}\) | \(\begin{aligned}&\hat Z_2\hat Z_3\big(c_0|010\rangle+c_1|101\rangle\big)\\&\quad=-1\,\big(c_0|010\rangle+c_1|101\rangle\big)\end{aligned}\) |
| error on qubit 3 | \(|001\rangle\), \(|110\rangle\) | +1 | −1 | \(\begin{aligned}&\hat Z_1\hat Z_2\big(c_0|001\rangle+c_1|110\rangle\big)\\&\quad=+1\,\big(c_0|001\rangle+c_1|110\rangle\big)\end{aligned}\) | \(\begin{aligned}&\hat Z_2\hat Z_3\big(c_0|001\rangle+c_1|110\rangle\big)\\&\quad=-1\,\big(c_0|001\rangle+c_1|110\rangle\big)\end{aligned}\) |
The syndrome tells the subspace. It does not tell \(c_0\) or \(c_1\).
Syndrome extraction
| ancillas | correction |
|---|---|
| 00 | none |
| 10 | \(\hat X_1\) |
| 11 | \(\hat X_2\) |
| 01 | \(\hat X_3\) |
start: \(\big(c_0|0\rangle+c_1|1\rangle\big)|00\rangle|00\rangle_a\)encode, CNOT 1 → 2: \(c_0|000\rangle|00\rangle_a+c_1|110\rangle|00\rangle_a\)encoded: \(c_0|000\rangle|00\rangle_a+c_1|111\rangle|00\rangle_a\)no error: \(c_0|000\rangle|00\rangle_a+c_1|111\rangle|00\rangle_a\)no error: \(c_0|000\rangle|00\rangle_a+c_1|111\rangle|10\rangle_a\)no error: \(c_0|000\rangle|00\rangle_a+c_1|111\rangle|00\rangle_a\)no error: \(c_0|000\rangle|00\rangle_a+c_1|111\rangle|01\rangle_a\)no error: \(c_0|000\rangle|00\rangle_a+c_1|111\rangle|00\rangle_a\)no error: \(c_0|000\rangle|00\rangle_a+c_1|111\rangle|00\rangle_a\) · ancillas 00 → correction nonestart: \(\big(c_0|0\rangle+c_1|1\rangle\big)|00\rangle|00\rangle_a\)encode, CNOT 1 → 2: \(c_0|000\rangle|00\rangle_a+c_1|110\rangle|00\rangle_a\)encoded: \(c_0|000\rangle|00\rangle_a+c_1|111\rangle|00\rangle_a\)\(\hat X_1\): \(c_0|100\rangle|00\rangle_a+c_1|011\rangle|00\rangle_a\)\(\hat X_1\): \(c_0|100\rangle|10\rangle_a+c_1|011\rangle|00\rangle_a\)\(\hat X_1\): \(c_0|100\rangle|10\rangle_a+c_1|011\rangle|10\rangle_a\)\(\hat X_1\): \(c_0|100\rangle|10\rangle_a+c_1|011\rangle|11\rangle_a\)\(\hat X_1\): \(c_0|100\rangle|10\rangle_a+c_1|011\rangle|10\rangle_a\)\(\hat X_1\): \(c_0|100\rangle|10\rangle_a+c_1|011\rangle|10\rangle_a\) · ancillas 10 → correction \(\hat X_1\)start: \(\big(c_0|0\rangle+c_1|1\rangle\big)|00\rangle|00\rangle_a\)encode, CNOT 1 → 2: \(c_0|000\rangle|00\rangle_a+c_1|110\rangle|00\rangle_a\)encoded: \(c_0|000\rangle|00\rangle_a+c_1|111\rangle|00\rangle_a\)\(\hat X_2\): \(c_0|010\rangle|00\rangle_a+c_1|101\rangle|00\rangle_a\)\(\hat X_2\): \(c_0|010\rangle|00\rangle_a+c_1|101\rangle|10\rangle_a\)\(\hat X_2\): \(c_0|010\rangle|10\rangle_a+c_1|101\rangle|10\rangle_a\)\(\hat X_2\): \(c_0|010\rangle|11\rangle_a+c_1|101\rangle|10\rangle_a\)\(\hat X_2\): \(c_0|010\rangle|11\rangle_a+c_1|101\rangle|11\rangle_a\)\(\hat X_2\): \(c_0|010\rangle|11\rangle_a+c_1|101\rangle|11\rangle_a\) · ancillas 11 → correction \(\hat X_2\)start: \(\big(c_0|0\rangle+c_1|1\rangle\big)|00\rangle|00\rangle_a\)encode, CNOT 1 → 2: \(c_0|000\rangle|00\rangle_a+c_1|110\rangle|00\rangle_a\)encoded: \(c_0|000\rangle|00\rangle_a+c_1|111\rangle|00\rangle_a\)\(\hat X_3\): \(c_0|001\rangle|00\rangle_a+c_1|110\rangle|00\rangle_a\)\(\hat X_3\): \(c_0|001\rangle|00\rangle_a+c_1|110\rangle|10\rangle_a\)\(\hat X_3\): \(c_0|001\rangle|00\rangle_a+c_1|110\rangle|00\rangle_a\)\(\hat X_3\): \(c_0|001\rangle|00\rangle_a+c_1|110\rangle|01\rangle_a\)\(\hat X_3\): \(c_0|001\rangle|01\rangle_a+c_1|110\rangle|01\rangle_a\)\(\hat X_3\): \(c_0|001\rangle|01\rangle_a+c_1|110\rangle|01\rangle_a\) · ancillas 01 → correction \(\hat X_3\)start: \(\big(c_0|0\rangle+c_1|1\rangle\big)|00\rangle|00\rangle_a\)encode, CNOT 1 → 2: \(c_0|000\rangle|00\rangle_a+c_1|110\rangle|00\rangle_a\)encoded: \(c_0|000\rangle|00\rangle_a+c_1|111\rangle|00\rangle_a\)\(\hat X_1\hat X_2\): \(c_0|110\rangle|00\rangle_a+c_1|001\rangle|00\rangle_a\)\(\hat X_1\hat X_2\): \(c_0|110\rangle|10\rangle_a+c_1|001\rangle|00\rangle_a\)\(\hat X_1\hat X_2\): \(c_0|110\rangle|00\rangle_a+c_1|001\rangle|00\rangle_a\)\(\hat X_1\hat X_2\): \(c_0|110\rangle|01\rangle_a+c_1|001\rangle|00\rangle_a\)\(\hat X_1\hat X_2\): \(c_0|110\rangle|01\rangle_a+c_1|001\rangle|01\rangle_a\)\(\hat X_1\hat X_2\): \(c_0|110\rangle|01\rangle_a+c_1|001\rangle|01\rangle_a\) · ancillas 01 → correction \(\hat X_3\) → wrong: two errors look like \(\hat X_3\)
PHYS598500 · Week 10
Error correction
Correction
One cycle: error, syndrome measurement, correction.
The syndrome gives the subspace. \(\hat X_k\) on that qubit moves the state back to the code subspace. \(c_0\) and \(c_1\) do not change.
Two errors, \(\hat X_1\hat X_2\), give the syndrome of \(\hat X_3\). The correction \(\hat X_3\) then makes \(\hat X_1\hat X_2\hat X_3\): \(c_0\) and \(c_1\) are exchanged. This is a logical error.
| error | syndrome | correction | result |
|---|---|---|---|
| none | \((+1,+1)\) | none | \(c_0|000\rangle+c_1|111\rangle\) |
| \(\hat X_1\) | \((-1,+1)\) | \(\hat X_1\) | \(c_0|000\rangle+c_1|111\rangle\) |
| \(\hat X_2\) | \((-1,-1)\) | \(\hat X_2\) | \(c_0|000\rangle+c_1|111\rangle\) |
| \(\hat X_3\) | \((+1,-1)\) | \(\hat X_3\) | \(c_0|000\rangle+c_1|111\rangle\) |
| \(\hat X_1\hat X_2\) | \((+1,-1)\) | \(\hat X_3\) | \(c_0|111\rangle+c_1|000\rangle\): logical error |
As with the classical vote, it happens with the probability \(\approx3p^2\).
Feedback loop
One cycle: syndrome circuit, readout of the ancillas, correction, reset of the ancillas. Then the next cycle starts.
The readout gives classical bits. A classical controller finds the correction in the syndrome table and sends that gate to the data qubit.
The result of a measurement decides the next gate. This is a feedback loop.
The controller must decide before the next cycle. If it is slow, new errors add up before the correction.
Only the ancillas are read. The data qubits keep \(c_0\) and \(c_1\) through all cycles.
data qubits + ancillas
CNOT gatesreadout of the ancillas
syndrome bits
1 0classical controller
syndrome table
1 0 → \(\hat X_1\)correction
\(\hat X_1\) on data 1
reset the ancillas to \(|0\rangle_a\)bitsgatenext cyclequbitsclassical bits
Feedback correction
After the readout, the two ancilla bits are classical bits: the syndrome.
A classical computer reads them, finds the correction in the table and sends that \(\hat X\) to one data qubit.
Then the ancillas are reset to \(|0\rangle_a\), and the next cycle starts.
The data keep \(c_0\) and \(c_1\). Two errors give a wrong correction.
| ancillas | correction |
|---|---|
| 00 | none |
| 10 | \(\hat X_1\) |
| 11 | \(\hat X_2\) |
| 01 | \(\hat X_3\) |
no error: \(c_0|000\rangle|00\rangle_a+c_1|111\rangle|00\rangle_a\)after the syndrome circuit: \(c_0|000\rangle|00\rangle_a+c_1|111\rangle|00\rangle_a\)readout 0 0: two classical bits go to the computerthe computer finds 00 → none in the tableno correction: \(c_0|000\rangle|00\rangle_a+c_1|111\rangle|00\rangle_a\)reset the ancillas: \(c_0|000\rangle|00\rangle_a+c_1|111\rangle|00\rangle_a\). The next cycle can start.\(\hat X_1\): \(c_0|100\rangle|00\rangle_a+c_1|011\rangle|00\rangle_a\)after the syndrome circuit: \(c_0|100\rangle|10\rangle_a+c_1|011\rangle|10\rangle_a\)readout 1 0: two classical bits go to the computerthe computer finds 10 → \(\hat X_1\) in the table\(\hat X_1\) on data 1: \(c_0|000\rangle|10\rangle_a+c_1|111\rangle|10\rangle_a\)reset the ancillas: \(c_0|000\rangle|00\rangle_a+c_1|111\rangle|00\rangle_a\). The next cycle can start.\(\hat X_2\): \(c_0|010\rangle|00\rangle_a+c_1|101\rangle|00\rangle_a\)after the syndrome circuit: \(c_0|010\rangle|11\rangle_a+c_1|101\rangle|11\rangle_a\)readout 1 1: two classical bits go to the computerthe computer finds 11 → \(\hat X_2\) in the table\(\hat X_2\) on data 2: \(c_0|000\rangle|11\rangle_a+c_1|111\rangle|11\rangle_a\)reset the ancillas: \(c_0|000\rangle|00\rangle_a+c_1|111\rangle|00\rangle_a\). The next cycle can start.\(\hat X_3\): \(c_0|001\rangle|00\rangle_a+c_1|110\rangle|00\rangle_a\)after the syndrome circuit: \(c_0|001\rangle|01\rangle_a+c_1|110\rangle|01\rangle_a\)readout 0 1: two classical bits go to the computerthe computer finds 01 → \(\hat X_3\) in the table\(\hat X_3\) on data 3: \(c_0|000\rangle|01\rangle_a+c_1|111\rangle|01\rangle_a\)reset the ancillas: \(c_0|000\rangle|00\rangle_a+c_1|111\rangle|00\rangle_a\). The next cycle can start.\(\hat X_1\hat X_2\): \(c_0|110\rangle|00\rangle_a+c_1|001\rangle|00\rangle_a\)after the syndrome circuit: \(c_0|110\rangle|01\rangle_a+c_1|001\rangle|01\rangle_a\)readout 0 1: two classical bits go to the computerthe computer finds 01 → \(\hat X_3\) in the table\(\hat X_3\) on data 3: \(c_0|111\rangle|01\rangle_a+c_1|000\rangle|01\rangle_a\) → wrong: \(c_0\) and \(c_1\) changed places, a logical errorreset the ancillas: \(c_0|111\rangle|00\rangle_a+c_1|000\rangle|00\rangle_a\) → the logical state is flipped
Measurement-free correction
The correction can also run with no readout. The ancillas control the correction gates directly.
A CNOT from ancilla 1 to data 1, a CNOT from ancilla 2 to data 3, and three Toffoli gates (controlled-controlled-\(\hat X\)), one to each data qubit, all controlled by both ancillas.
The ancillas still hold the syndrome. A reset to \(|0\rangle_a\) removes it before the next cycle. Without the reset, the old syndrome stays, and the next cycle makes a wrong correction.
No readout and no controller are necessary. But each Toffoli gate acts on three qubits: it is slow and adds errors.
With three transmon qubits, a Toffoli gate corrected one flipped qubit without a measurement.
| ancillas | gates that act | correction |
|---|---|---|
| 0 0 | none | none |
| 1 0 | CNOT from ancilla 1 | \(\hat X_1\) |
| 1 1 | both CNOTs, three Toffolis | \(\hat X_1\hat X_3\cdot\hat X_1\hat X_2\hat X_3=\hat X_2\) |
| 0 1 | CNOT from ancilla 2 | \(\hat X_3\) |
M. D. Reed et al., Nature 482, 382 (2012).
Measurement-free correction
The correction can also run with no readout. The ancillas control the correction gates directly.
A CNOT from ancilla 1 to data 1, a CNOT from ancilla 2 to data 3, and a Toffoli gate (controlled-controlled-\(\hat X\)) from both ancillas to the three data qubits.
The ancillas still hold the syndrome. A reset to \(|0\rangle_a\) removes it before the next cycle. Without the reset, the old syndrome stays, and the next cycle makes a wrong correction.
No readout and no controller are necessary. But the Toffoli gate acts on three qubits: it is slow and adds errors.
With three transmon qubits, a Toffoli gate corrected one flipped qubit without a measurement.
| ancillas | gates that act | correction |
|---|---|---|
| 0 0 | none | none |
| 1 0 | CNOT from ancilla 1 | \(\hat X_1\) |
| 1 1 | both CNOTs and the Toffoli | \(\hat X_1\hat X_3\cdot\hat X_1\hat X_2\hat X_3=\hat X_2\) |
| 0 1 | CNOT from ancilla 2 | \(\hat X_3\) |
M. D. Reed et al., Nature 482, 382 (2012).
Four problems
| problem | status | |
|---|---|---|
| 1 | no copies | ✓ encoding without copies: \(c_0|000\rangle+c_1|111\rangle\) |
| 2 | no direct readout | ✓ parity checks with ancillas: the syndrome |
| 3 | phase errors | |
| 4 | continuous errors |
The bit-flip code solves problems 1 and 2. It finds and corrects one \(\hat X\) error and keeps \(c_0\), \(c_1\).
Problems 3 and 4 are still open: a \(\hat Z\) error is not found, and real errors are not only flips.
PHYS598500 · Week 10
Phase errors
The Hadamard basis
\(\hat H|0\rangle=|+\rangle\) and \(\hat H|1\rangle=|-\rangle\), with \(|\pm\rangle=\frac{1}{\sqrt2}\big(|0\rangle\pm|1\rangle\big)\).
| state | after \(\hat X\) | after \(\hat Z\) |
|---|---|---|
| \(|0\rangle\) | \(|1\rangle\): flipped | \(|0\rangle\): no change |
| \(|1\rangle\) | \(|0\rangle\): flipped | \(-|1\rangle\): only a sign |
| \(|+\rangle\) | \(|+\rangle\): no change | \(|-\rangle\): flipped |
| \(|-\rangle\) | \(-|-\rangle\): only a sign | \(|+\rangle\): flipped |
In the \(|\pm\rangle\) basis, \(\hat Z\) is the flip and \(\hat X\) only changes a sign: \(\hat H\hat Z\hat H=\hat X\).
So a check for flips in the \(|\pm\rangle\) basis finds \(\hat Z\) errors.
Phase-flip code
In the \(|\pm\rangle\) basis, \(\hat Z\) is a flip: \(\hat Z|\pm\rangle=|\mp\rangle\). So use the bit-flip code in this basis:
Encoder: the bit-flip encoder, then \(\hat H\) on each qubit.
Stabilizers: \(\hat X_1\hat X_2\) and \(\hat X_2\hat X_3\). A stabilizer gives +1 if its two qubits are the same, −1 if they are different:
A \(\hat Z_2\) error gives \(|{+}{-}{+}\rangle\). Both stabilizers give −1, so qubit 2 is different. Correction: \(\hat Z_2\).
Now \(\hat Z\) errors are found, and \(\hat X\) errors are not.
Two encoders
Four problems
| problem | status | |
|---|---|---|
| 1 | no copies | ✓ encoding without copies: \(c_0|000\rangle+c_1|111\rangle\) |
| 2 | no direct readout | ✓ parity checks with ancillas: the syndrome |
| 3 | phase errors | half: the phase-flip code finds \(\hat Z\), not \(\hat X\) |
| 4 | continuous errors |
The phase-flip code corrects one \(\hat Z\) error. The bit-flip code corrects one \(\hat X\) error.
A code must correct both kinds at the same time.
PHYS598500 · Week 10
Shor nine-qubit code
Phase errors in the bit-flip code
The state stays in the code subspace. The syndrome is \((+1,+1)\). No error is found.
But the sign of \(c_1\) has changed. The stored qubit turns by 180° about \(z\): a logical error.
| error | state | syndrome |
|---|---|---|
| \(\hat Z_1\), \(\hat Z_2\) or \(\hat Z_3\) | \(c_0|000\rangle-c_1|111\rangle\) | \((+1,+1)\): not found |
| \(\hat X_1\) | \(c_0|100\rangle+c_1|011\rangle\) | \((-1,+1)\): found |
The bit-flip code protects only against \(\hat X\), the phase-flip code only against \(\hat Z\).
Shor code
Put the two codes together: a phase-flip code whose qubits are bit-flip blocks. Nine qubits:
After step 1: \(c_0|000\rangle+c_1|111\rangle\) on qubits 1, 4, 7.
After step 2: \(c_0|{+}{+}{+}\rangle+c_1|{-}{-}{-}\rangle\), the phase-flip code.
Step 3 is a bit-flip encoder in each block: \(|\pm\rangle|00\rangle\to\frac{1}{\sqrt2}\big(|000\rangle\pm|111\rangle\big)\).
P. W. Shor, Phys. Rev. A 52, R2493 (1995).
Shor code
| gates | state after the step | |
|---|---|---|
| step 1 | CNOT from 1 to 4, 7 | \(\big(c_0|000\rangle_{1,4,7}+c_1|111\rangle_{1,4,7}\big)|0\rangle_2|0\rangle_3|0\rangle_5|0\rangle_6|0\rangle_8|0\rangle_9\) |
| step 2 | \(\hat H\) on 1, 4, 7 | \(\big(c_0|{+}{+}{+}\rangle_{1,4,7}+c_1|{-}{-}{-}\rangle_{1,4,7}\big)|0\rangle_2|0\rangle_3|0\rangle_5|0\rangle_6|0\rangle_8|0\rangle_9\) |
| step 3 | CNOT inside each block | \(\begin{aligned}&\tfrac{c_0}{2\sqrt2}\big(|000\rangle+|111\rangle\big)_{1,2,3}\big(|000\rangle+|111\rangle\big)_{4,5,6}\big(|000\rangle+|111\rangle\big)_{7,8,9}\\&+\tfrac{c_1}{2\sqrt2}\big(|000\rangle-|111\rangle\big)_{1,2,3}\big(|000\rangle-|111\rangle\big)_{4,5,6}\big(|000\rangle-|111\rangle\big)_{7,8,9}\end{aligned}\) |
P. W. Shor, Phys. Rev. A 52, R2493 (1995).
Errors in the Shor code
An \(\hat X\) error stays in its block. The two \(\hat Z\hat Z\) checks of the block find it, as in the bit-flip code.
A \(\hat Z\) error changes the sign of its block: \(|000\rangle+|111\rangle\to|000\rangle-|111\rangle\). Two checks \(\hat X^{\otimes6}\) compare the signs of neighbouring blocks.
\(\hat Y=i\hat X\hat Z\) fires both kinds of checks. It is corrected as \(\hat X\) and \(\hat Z\) together.
These eight checks are the stabilizers of the Shor code. Eight ancillas measure them: 17 qubits for one logical qubit.
P. W. Shor, Phys. Rev. A 52, R2493 (1995).
Z error check of the Shor code
A \(\hat Z\) error changes the sign of its block. In one block, \(\hat X_1\hat X_2\hat X_3\) exchanges \(|000\rangle\) and \(|111\rangle\), so it gives this sign:
\(\hat X_1\) alone does not give the sign, because it changes \(|000\rangle\) to \(|100\rangle\). One block alone is not a check either: \(\hat X_1\hat X_2\hat X_3\) gives +1 on \(|0_L\rangle\) and −1 on \(|1_L\rangle\), so a readout of it destroys \(c_0\), \(c_1\).
After step 2, qubits 1, 4, 7 hold the phase-flip code, with the checks \(\hat X_1\hat X_4\) and \(\hat X_4\hat X_7\). Step 3 makes each of these qubits a block. Each \(\hat X\) becomes \(\hat X\hat X\hat X\) on its block. This gives the two checks of the Z error check:
Each check gives +1 if its two blocks have the same sign, −1 if not. A \(\hat Z\) error in block 1, 2 or 3 gives \((-1,+1)\), \((-1,-1)\) or \((+1,-1)\).
P. W. Shor, Phys. Rev. A 52, R2493 (1995).
Stabilizers
Every check of this week measures a stabilizer: a product of Pauli operators that gives +1 on all code states.
| code | qubits | stabilizers | finds |
|---|---|---|---|
| bit-flip | 3 | \(\hat Z_1\hat Z_2\), \(\hat Z_2\hat Z_3\) | one \(\hat X\) |
| phase-flip | 3 | \(\hat X_1\hat X_2\), \(\hat X_2\hat X_3\) | one \(\hat Z\) |
| Shor | 9 | six \(\hat Z\hat Z\), two \(\hat X^{\otimes6}\) | any one-qubit error |
The code subspace is where all stabilizers give +1. An error that anticommutes with a stabilizer turns its result to −1.
The list of results is the syndrome. It depends on the error, not on \(c_0\), \(c_1\).
Bit-flip and phase-flip codes in the Shor code
The Shor code is the phase-flip code across three blocks. Each of its three qubits is encoded again in the bit-flip code.
A Z-type check measures a product of \(\hat Z\) and finds \(\hat X\) errors. An X-type check measures a product of \(\hat X\) and finds \(\hat Z\) errors.
| bit flips: \(\hat X\) errors | phase flips: \(\hat Z\) errors | |
|---|---|---|
| code | bit-flip code: \(|000\rangle\), \(|111\rangle\) | phase-flip code: \(|{+}{+}{+}\rangle\), \(|{-}{-}{-}\rangle\) |
| in the Shor code | inside each block | across the three blocks |
| encoder | X encode: CNOT inside each block | Z encode: CNOT 1 → 4, 7, then \(\hat H\) on 1, 4, 7 |
| stabilizers | Z-type: \(\hat Z_1\hat Z_2\), \(\hat Z_2\hat Z_3\), \(\hat Z_4\hat Z_5\), \(\hat Z_5\hat Z_6\), \(\hat Z_7\hat Z_8\), \(\hat Z_8\hat Z_9\) | X-type: \(\hat X_1\hat X_2\hat X_3\hat X_4\hat X_5\hat X_6\), \(\hat X_4\hat X_5\hat X_6\hat X_7\hat X_8\hat X_9\) |
| name in this lecture | X error check | Z error check |
M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information (Cambridge University Press, 2000), Sec. 10.1–10.2. P. W. Shor, Phys. Rev. A 52, R2493 (1995).
Shor code: encode to correction
P. W. Shor, Phys. Rev. A 52, R2493 (1995).
Four problems
| problem | status | |
|---|---|---|
| 1 | no copies | ✓ encoding without copies: \(c_0|000\rangle+c_1|111\rangle\) |
| 2 | no direct readout | ✓ parity checks with ancillas: the syndrome |
| 3 | phase errors | ✓ Shor code: \(\hat X\), \(\hat Y\), \(\hat Z\) on any one qubit |
| 4 | continuous errors |
The Shor code corrects \(\hat X\), \(\hat Y\) and \(\hat Z\) on any one qubit.
Problem 4 is still open: real errors are small turns and random phases.
PHYS598500 · Week 10
Continuous errors
Continuous error on one qubit
A real error is often a small turn, not a full flip. A turn by \(2\varepsilon\) about \(x\) on qubit 1 is \(e^{-i\varepsilon\hat X_1}=\cos\varepsilon\,\hat I-i\sin\varepsilon\,\hat X_1\). On the encoded state:
The first part is in the code subspace, the second in the error subspace of qubit 1. The syndrome circuit writes this on the ancillas:
Read the ancillas:
| readout | probability | state after the readout | correction | result |
|---|---|---|---|---|
| 00 | \(\cos^2\varepsilon\) | \(c_0|000\rangle+c_1|111\rangle\) | none | \(c_0|000\rangle+c_1|111\rangle\) |
| 10 | \(\sin^2\varepsilon\) | \(c_0|100\rangle+c_1|011\rangle\) | \(\hat X_1\) | \(c_0|000\rangle+c_1|111\rangle\) |
The readout makes the small turn into no error or one \(\hat X_1\), and both are corrected. So the code must correct only \(\hat X\) errors, not every small turn.
Continuous error on one qubit
Any one-qubit error
A small error can turn about any axis, the unit vector \((n_x,n_y,n_z)\). It is a sum of \(\hat I\), \(\hat X\), \(\hat Y\) and \(\hat Z\):
Each term has its own syndrome. So the readout keeps one term, with its probability, and we know which one. Shor code, error on qubit 5:
| term | probability | checks that give −1 | correction |
|---|---|---|---|
| \(\hat I\) | \(\cos^2\varepsilon\) | none | none |
| \(\hat X_5\) | \(n_x^2\sin^2\varepsilon\) | \(\hat Z_4\hat Z_5\), \(\hat Z_5\hat Z_6\) | \(\hat X_5\) |
| \(\hat Y_5\) | \(n_y^2\sin^2\varepsilon\) | \(\hat Z_4\hat Z_5\), \(\hat Z_5\hat Z_6\), \(\hat X_1\hat X_2\hat X_3\hat X_4\hat X_5\hat X_6\), \(\hat X_4\hat X_5\hat X_6\hat X_7\hat X_8\hat X_9\) | \(\hat Y_5\) |
| \(\hat Z_5\) | \(n_z^2\sin^2\varepsilon\) | \(\hat X_1\hat X_2\hat X_3\hat X_4\hat X_5\hat X_6\), \(\hat X_4\hat X_5\hat X_6\hat X_7\hat X_8\hat X_9\) | \(\hat Z\) on qubit 4, 5 or 6 |
After the readout, the error is \(\hat I\), \(\hat X_5\), \(\hat Y_5\) or \(\hat Z_5\), and the table gives its correction. So a code that corrects \(\hat X\), \(\hat Y\) and \(\hat Z\) on each qubit corrects every one-qubit error.
Any one-qubit error
P. W. Shor, Phys. Rev. A 52, R2493 (1995).
Summary
| problem | solved by | example: bit-flip code | |
|---|---|---|---|
| ✓ | no copies | spread the amplitudes into the code subspace | \(c_0|000\rangle+c_1|111\rangle\) |
| ✓ | no direct readout | parity checks with ancillas: the syndrome | \(\hat X_2\): syndrome \((-1,-1)\) |
| ✓ | phase errors | checks in the \(|\pm\rangle\) basis; the Shor code corrects both kinds | \(\hat Z_1\) is not found by \(\hat Z\hat Z\) |
| ✓ | continuous errors | the syndrome measurement keeps one Pauli term | \(\cos^2\varepsilon\) or \(\sin^2\varepsilon\) |
One logical qubit uses several physical qubits. Ancillas measure the syndrome. A correction moves the state back to the code subspace.
A code helps only below a threshold error rate. For the three-bit vote: \(p<\frac{1}{2}\).
The goal is a fault-tolerant computer: errors in the gates and checks are corrected too.
PHYS598500 · Week 10
Gates on logical qubits
Physical and logical gates
A gate on one qubit acts on its states: \(\hat X|0\rangle=|1\rangle\) and \(\hat X|1\rangle=|0\rangle\).
A logical qubit is stored in many qubits, the physical qubits. In the Shor code, nine physical qubits hold:
A logical gate acts on the stored qubit: \(\hat X_L|0_L\rangle=|1_L\rangle\) and \(\hat X_L|1_L\rangle=|0_L\rangle\). It is made of gates on the nine physical qubits.
Logical X gate
In \(|0_L\rangle\) each block is \(|000\rangle+|111\rangle\). In \(|1_L\rangle\) it is \(|000\rangle-|111\rangle\). \(\hat Z_1\) changes the sign of \(|111\rangle\). So one \(\hat Z\) in each block exchanges \(|0_L\rangle\) and \(|1_L\rangle\):
Each Z error check compares the signs of two blocks. \(\hat Z_1\) alone changes one block: a Z error check sees an error. \(\hat X_L\) changes all three blocks: both Z error checks give +1.
\(\hat Z\) on each qubit is also \(\hat X_L\): \((-1)^3=-1\) in each block. Gates that each act on one qubit of the code make a transversal gate.
On a transmon, \(\hat Z\) is a virtual Z gate: the controller shifts the phase of later drive pulses by \(\pi\). So \(\hat X_L\) needs no pulse.
| input | \(\hat Z\) on qubits 1, 4, 7 | \(\hat Z\) on each qubit |
|---|---|---|
| \(|0_L\rangle\) | \(|1_L\rangle\) | \(|1_L\rangle\) |
| \(|1_L\rangle\) | \(|0_L\rangle\) | \(|0_L\rangle\) |
| syndrome readout | all +1 | all +1 |
| logical gate | \(\hat X_L\) | \(\hat X_L\) |
Logical Z gate
\(\hat Z_L\) must multiply \(|1_L\rangle\) by −1 and leave \(|0_L\rangle\) unchanged. \(\hat X_1\hat X_2\hat X_3\) exchanges \(|000\rangle\) and \(|111\rangle\) in block 1:
Block 1 has + in \(|0_L\rangle\) and − in \(|1_L\rangle\). So \(\hat Z_L=\hat X_1\hat X_2\hat X_3\).
\(\hat X\) on each qubit is also \(\hat Z_L\): each block of \(|1_L\rangle\) gives −1, and \((-1)^3=-1\). The names swap: \(\hat Z_L\) uses \(\hat X\) gates.
\(\hat X\) is a real pulse, not a virtual gate. The controller can skip the three pulses and note \(\hat Z_L\) in its memory, the Pauli frame. Later it flips the readouts of qubits 1, 2, 3: 010 becomes 101.
| input | \(\hat X\) on qubits 1, 2, 3 | \(\hat X\) on each qubit |
|---|---|---|
| \(|0_L\rangle\) | \(|0_L\rangle\) | \(|0_L\rangle\) |
| \(|1_L\rangle\) | \(-|1_L\rangle\) | \(-|1_L\rangle\) |
| syndrome readout | all +1 | all +1 |
| logical gate | \(\hat Z_L\) | \(\hat Z_L\) |
E. Knill, Nature 434, 39 (2005).
Logical CNOT gate
Two logical qubits use qubits 1 to 9 and qubits 10 to 18. CNOT gates from qubit 1 to 10, 2 to 11, 3 to 12, 4 to 13, 5 to 14, 6 to 15, 7 to 16, 8 to 17 and 9 to 18 make a transversal gate: each CNOT acts on one qubit of each logical qubit.
It is a logical CNOT from logical qubit 2 to logical qubit 1: the direction is reversed. \(|0_L\rangle\) and \(|1_L\rangle\) differ only in the sign of the blocks, as \(|+\rangle\) and \(|-\rangle\) do. In the \(|\pm\rangle\) basis, a CNOT acts from its target to its control.
An error on one qubit spreads to at most one qubit of the other logical qubit. The Shor code corrects any error on one qubit.
| input: logical qubit 1, logical qubit 2 | after the nine CNOT gates |
|---|---|
| \(|0_L\rangle|0_L\rangle\) | \(|0_L\rangle|0_L\rangle\) |
| \(|0_L\rangle|1_L\rangle\) | \(|1_L\rangle|1_L\rangle\) |
| \(|1_L\rangle|0_L\rangle\) | \(|1_L\rangle|0_L\rangle\) |
| \(|1_L\rangle|1_L\rangle\) | \(|0_L\rangle|1_L\rangle\) |
Logical CZ gate
The logical CZ multiplies \(|1_L\rangle|1_L\rangle\) by −1. CZ gates on the same nine pairs (1 and 10, 2 and 11, 3 and 12, 4 and 13, 5 and 14, 6 and 15, 7 and 16, 8 and 17, 9 and 18) are not a logical gate: they keep only \(\tfrac{1}{16}\) of each logical state in the code subspace.
The logical CZ is a logical CNOT with \(\hat H_L\) before and after on its target. Here the nine CNOT gates go from qubits 10 to 18 to qubits 1 to 9, so they are a logical CNOT from logical qubit 1 to logical qubit 2. Its target, logical qubit 2, gets \(\hat H_L\).
So the logical CZ needs \(\hat H_L\), the logical H gate.
| input: logical qubit 1, logical qubit 2 | after the logical CZ |
|---|---|
| \(|0_L\rangle|0_L\rangle\) | \(|0_L\rangle|0_L\rangle\) |
| \(|0_L\rangle|1_L\rangle\) | \(|0_L\rangle|1_L\rangle\) |
| \(|1_L\rangle|0_L\rangle\) | \(|1_L\rangle|0_L\rangle\) |
| \(|1_L\rangle|1_L\rangle\) | \(-|1_L\rangle|1_L\rangle\) |
Logical H gate
\(\hat H_L\) must turn \(|0_L\rangle\) into \(|{+}_L\rangle\) and \(|1_L\rangle\) into \(|{-}_L\rangle\), with \(|{\pm}_L\rangle=\tfrac{1}{\sqrt2}\big(|0_L\rangle\pm|1_L\rangle\big)\). It is a five-qubit gate, not a transversal gate:
After the gate, \(\hat H\) on qubit 1 is \(\tfrac{1}{\sqrt2}(\hat X_1+\hat Z_1)\). \(\hat H\) on each qubit turns a block of \(|0_L\rangle\) into \(\tfrac{1}{\sqrt2}\big(|{+}{+}{+}\rangle+|{-}{-}{-}\rangle\big)\). Each 1 in \(|{-}{-}{-}\rangle\) gives −1, so the terms with an odd number of 1s cancel.
The syndrome readout finds \(\hat X_1\) or a \(\hat Z\) in block 1; the correction removes it. After \(\hat H\) on each qubit it is random. The correction gives \(\hat H_L\) with a Pauli \(\hat P\), but it cannot show an error made here. So the Shor code uses a prepared state.
| \(\hat H\) on qubit 1 | \(\hat H\) on each qubit | |
|---|---|---|
| after the gate | \(\tfrac{1}{\sqrt2}\big(\hat X_1+\hat Z_1\big)\) | \(\tfrac{1}{2}\big(|000\rangle+|011\rangle+|101\rangle+|110\rangle\big)\) \(\tfrac{1}{2}\big(|001\rangle+|010\rangle+|100\rangle+|111\rangle\big)\) |
| syndrome readout | \(\hat X_1\) or \(\hat Z\) in block 1 | random |
| after the correction | \(c_0|0_L\rangle+c_1|1_L\rangle\) | \(\hat P\,\hat H_L\big(c_0|0_L\rangle+c_1|1_L\rangle\big)\) |
| \(\hat H_L\) would give | \(c_0|{+}_L\rangle+c_1|{-}_L\rangle\) | \(c_0|{+}_L\rangle+c_1|{-}_L\rangle\) |
| logical gate | ✗ none | ✗ an error here is not seen |
Logical H gate with a prepared state
A and B start in \(|0\rangle\). \(\hat H\) on qubits 10 and 19, one CZ between them, then Z encode and X encode give the prepared state \(\tfrac{1}{\sqrt2}\big(|0_L\rangle|{+}_L\rangle+|1_L\rangle|{-}_L\rangle\big)\).
Nine CNOT gates from A to the input make a logical CNOT from the input to A. The readouts give \(\hat X_L=\hat Z_1\hat Z_4\hat Z_7\) of the input and \(\hat Z_L=\hat X_{10}\hat X_{11}\hat X_{12}\) of A. These set a Pauli \(\hat P\): B is \(\hat P\,\hat H_L|\psi_L\rangle\), and the correction \(\hat P\) gives \(\hat H_L|\psi_L\rangle\).
D. Gottesman and I. L. Chuang, Nature 402, 390 (1999).
Result of the logical H gate
Write \(|\psi_L\rangle=c_0|0_L\rangle+c_1|1_L\rangle\). After the logical CNOT from the input to A, the three codes (input, A, B) are in:
The readout of A keeps the terms with A in \(|0_L\rangle\) (\(\hat Z_L=+1\)) or in \(|1_L\rangle\) (\(\hat Z_L=-1\)). For the readout of the input, write \(|0_L\rangle=\tfrac{1}{\sqrt2}\big(|{+}_L\rangle+|{-}_L\rangle\big)\) and \(|1_L\rangle=\tfrac{1}{\sqrt2}\big(|{+}_L\rangle-|{-}_L\rangle\big)\). Each pair of results has the probability \(\tfrac14\):
| \(\hat X_L\) of the input | \(\hat Z_L\) of A | B after the readouts | \(\hat P\) |
|---|---|---|---|
| \(+1\) | \(+1\) | \(c_0|{+}_L\rangle+c_1|{-}_L\rangle\) | \(\hat I\) |
| \(+1\) | \(-1\) | \(c_0|{-}_L\rangle+c_1|{+}_L\rangle\) | \(\hat Z_L\) |
| \(-1\) | \(+1\) | \(c_0|{+}_L\rangle-c_1|{-}_L\rangle\) | \(\hat X_L\) |
| \(-1\) | \(-1\) | \(c_0|{-}_L\rangle-c_1|{+}_L\rangle\) | \(-\hat X_L\hat Z_L\) |
In every row B is \(\hat P\,\hat H_L|\psi_L\rangle\), with \(\hat H_L|\psi_L\rangle=c_0|{+}_L\rangle+c_1|{-}_L\rangle\). \(\hat P\) is a Pauli (the −1 in the last row is a global phase). The correction \(\hat P\), or a note in the Pauli frame, gives \(\hat H_L|\psi_L\rangle\).
D. Gottesman and I. L. Chuang, Nature 402, 390 (1999).
T gate on one qubit
\(\hat T\) changes only the phase of \(|1\rangle\):
On the Bloch sphere, \(\hat T\) turns the state by \(\tfrac{\pi}{4}\) about \(z\). Two \(\hat T\) gates make \(\hat S=\hat T^2\).
| input | after \(\hat T\) |
|---|---|
| \(|0\rangle\) | \(|0\rangle\) |
| \(|1\rangle\) | \(e^{i\frac{\pi}{4}}|1\rangle\) |
| \(c_0|0\rangle+c_1|1\rangle\) | \(c_0|0\rangle+e^{i\frac{\pi}{4}}c_1|1\rangle\) |
| \(|+\rangle\) | \(\tfrac{1}{\sqrt2}\big(|0\rangle+e^{i\frac{\pi}{4}}|1\rangle\big)\) |
On a transmon, \(\hat T\) is a virtual Z gate. The controller shifts the phase of all later drive pulses by \(\tfrac{\pi}{4}\). It sends no pulse for \(\hat T\).
D. C. McKay et al., Phys. Rev. A 96, 022330 (2017).
Logical T gate
\(\hat T_L\) must multiply \(|1_L\rangle\) by \(e^{i\frac{\pi}{4}}\) and leave \(|0_L\rangle\) unchanged: a 45° turn of the stored qubit about \(z\). With \(\hat Z_L=\hat X_1\hat X_2\hat X_3\), it is:
This is a three-qubit gate, not a transversal gate. One error in it can spread to \(\hat X_1\hat X_2\hat X_3\).
After the gate, \(\hat T\) puts a phase on \(|111\rangle\) of a block. A code block has only + or − there.
The syndrome readout finds \(\hat Z\) errors. After the correction, \(\hat T\) on qubit 1 leaves no change. \(\hat T\) on each qubit leaves a random turn about \(x\), \(\theta\) = −172° or 135°. Neither is \(\hat T_L\). So the Shor code makes \(\hat T_L\) with magic state injection.
| \(\hat T\) on qubit 1 | \(\hat T\) on each qubit | |
|---|---|---|
| after the gate | \(e^{i\frac{\pi}{4}}\) on \(|111\rangle\) of block 1 | \(e^{i\frac{3\pi}{4}}\) on \(|111\rangle\) of each block |
| syndrome readout | \(\hat Z\) in block 1, or none | \(\hat Z\) errors |
| after the correction | \(c_0|0_L\rangle+c_1|1_L\rangle\) | \(e^{-i\frac{\theta}{2}\hat X_L}\big(c_0|0_L\rangle+c_1|1_L\rangle\big)\) |
| \(\hat T_L\) would give | \(c_0|0_L\rangle+e^{i\frac{\pi}{4}}c_1|1_L\rangle\) | \(c_0|0_L\rangle+e^{i\frac{\pi}{4}}c_1|1_L\rangle\) |
| logical gate | ✗ none | ✗ a random turn about \(x\) |
Magic state injection
The magic state is \(\hat T|+\rangle\) in the Shor code: \(\tfrac{1}{\sqrt2}\big(|0_L\rangle+e^{i\frac{\pi}{4}}|1_L\rangle\big)\) on qubits 10 to 18. \(\hat H\) and \(\hat T\) on qubit 10, then Z encode and X encode, make it.
Nine CNOT gates, each from a magic qubit to the data qubit at the same place, make a logical CNOT from the data to the magic state; the direction is reversed. Then \(\hat H\) and a readout on qubits 10 to 18 give a result, + or −. Only if it is −, \(\hat S_L=\hat T_L^2\) corrects the data: it multiplies \(|1_L\rangle\) by \(i\).
S. Bravyi and A. Kitaev, Phys. Rev. A 71, 022316 (2005).
Result of magic state injection
Each block of qubits 10 to 18 (10 to 12, 13 to 15, 16 to 18) gives its sign by the parity of its three readouts. The majority of the three signs is the result:
| result | probability | data after the readout | correction | data after the correction |
|---|---|---|---|---|
| + | \(\tfrac{1}{2}\) | \(c_0|0_L\rangle+e^{i\frac{\pi}{4}}c_1|1_L\rangle\) | none | \(c_0|0_L\rangle+e^{i\frac{\pi}{4}}c_1|1_L\rangle\) |
| − | \(\tfrac{1}{2}\) | \(c_0|0_L\rangle+e^{-i\frac{\pi}{4}}c_1|1_L\rangle\) | \(\hat S_L\) | \(c_0|0_L\rangle+e^{i\frac{\pi}{4}}c_1|1_L\rangle\) |
\(\hat S_L\) is not transversal either. It is made in the same way, with \(\hat S|+\rangle\) in the code; its result − needs only \(\hat Z_L\), which the controller records.
The data never get a \(\hat T\) gate. Test each magic state first. Discard a bad magic state.
S. Bravyi and A. Kitaev, Phys. Rev. A 71, 022316 (2005).
PHYS598500 · Week 10
Connectivity problem
Connectivity of the Shor code
Each ancilla sits between its data qubits. X error check: every CNOT joins neighbours. Z error check: each ancilla joins six data qubits, up to five lines away.
P. W. Shor, Phys. Rev. A 52, R2493 (1995).
Surface code
On a chip, a qubit couples only to its neighbours. The Z error check of the Shor code needs couplings over five lines. This is the connectivity problem.
The surface code puts data qubits and ancillas on a square grid. Each check uses only the data qubits next to its ancilla: \(\hat Z\) on four qubits finds \(\hat X\) errors, \(\hat X\) on four qubits finds \(\hat Z\) errors (two at the edges).
Every coupling is between neighbours. With 17 qubits, as the Shor code, it corrects any one-qubit error. A larger grid corrects more errors.
A. G. Fowler, M. Mariantoni, J. M. Martinis and A. N. Cleland, Phys. Rev. A 86, 032324 (2012).
PHYS598500 · Week 10