Quantum Error Correction
Quantum Error Correction
Copyright By PowCoder代写 加微信 powcoder
Perimeter Institute
The Classical and Quantum Worlds
Quantum Errors
A general quantum error is a superoperator:
Ak Ak†
Examples of single-qubit errors:
Bit Flip X: X0 = 1, X1 = 0
Phase Flip Z: Z0 = 0, Z1 = -1
Complete dephasing: ( + ZZ†)/2 (decoherence)
Rotation: R0 = 0, R1 = ei1
Classical Repetition Code
To correct a single bit-flip error for classical data, we can use the repetition code:
If there is a single bit flip error, we can correct the state by choosing the majority of the three bits, e.g. 010 0. When errors are rare, one error is more likely than two.
No-Cloning Theorem
There is no device that will copy an unknown quantum state:
0 00, 1 11
0 + 1 00 + 11
(0 + 1)(0 + 1)
By linearity,
(Related to Heisenberg Uncertainty Principle)
Barriers to Quantum Error Correction
Measurement of error destroys superpositions.
No-cloning theorem prevents repetition.
Must correct multiple types of errors (e.g., bit flip and phase errors).
How can we correct continuous errors and decoherence?
Measurement Destroys Superpositions?
Let us apply the classical repetition code to a quantum state to try to correct a single bit flip error:
0 + 1 000 + 111
Bit flip error (X) on 2nd qubit:
010 + 101
2nd qubit is now different from 1st and 3rd. We wish to measure that it is different without finding its actual value.
Measure the Error, Not the Data
Use this circuit:
Encoded state
Error syndrome
1st bit of error syndrome says whether the first two bits of the state are the same or different.
2nd bit of error syndrome says whether the second two bits of the state are the same or different.
Ancilla qubits
Measure the Error, Not the Data
With the information from the error syndrome, we can determine whether there is an error and where it is:
E.g., 010 + 101 has syndrome 11, which means the second bit is different. Correct it with a X operation on the second qubit. Note that the syndrome does not depend on and .
We have learned about the error without learning about the data, so superpositions are preserved!
Redundancy, Not Repetition
This encoding does not violate the no-cloning theorem:
0 + 1 000 + 111
(0 + 1)3
We have repeated the state only in the computational basis; superposition states are spread out (redundant encoding), but not repeated (which would violate no-cloning).
Update on the Problems
Measurement of error destroys superpositions.
No-cloning theorem prevents repetition.
Must correct multiple types of errors (e.g., bit flip and phase errors).
How can we correct continuous errors and decoherence?
Correcting Just Phase Errors
Hadamard transform H exchanges bit flip and phase errors:
H (0 + 1) = + + -
X+ = +, X- = -- (acts like phase flip)
Z+ = -, Z- = + (acts like bit flip)
Repetition code corrects a bit flip error
Repetition code in Hadamard basis corrects a phase error.
+ + - +++ + —
Nine-Qubit Code
To correct both bit flips and phase flips, use both codes at once:
0 + 1
(000 + 111)3 + (000 – 111)3
Repetition 000, 111 corrects a bit flip error, repetition of phase +++, — corrects a phase error
Actually, this code corrects a bit flip and a phase, so it also corrects a Y error:
Y = iXZ: Y0 = i1, Y1 = -i0
(global phase irrelevant)
Update on the Problems
Measurement of error destroys superpositions.
No-cloning theorem prevents repetition.
Must correct multiple types of errors (e.g., bit flip and phase errors).
How can we correct continuous errors and decoherence?
Correcting Continuous Rotation
Let us rewrite continuous rotation
R0 = 0, R1 = ei1
R = ( )= ei/2( )
= cos (/2) I – i sin (/2) Z
R(k) = cos (/2) – i sin (/2) Z(k)
(R(k) is R acting on the kth qubit.)
Correcting Continuous Rotations
How does error correction affect a state with a continuous rotation on it?
R(k) = cos (/2) – i sin (/2) Z(k)
cos (/2)I – i sin (/2) Z(k) Z(k)
Error syndrome
Measuring the error syndrome collapses the state:
Prob. cos2 (/2): (no correction needed)
Prob. sin2 (/2): Z(k) (corrected with Z(k))
Correcting All Single-Qubit Errors
Theorem: If a quantum error-correcting code (QECC) corrects errors A and B, it also corrects A + B.
Any 2×2 matrix can be written as I + X + Y + Z.
A general single-qubit error Ak Ak† acts like a mixture of Ak, and Ak is a 2×2 matrix.
Any QECC that corrects the single-qubit errors X, Y, and Z (plus I) corrects every single-qubit error.
Correcting all t-qubit X, Y, Z on t qubits (plus I) corrects all t-qubit errors.
The Pauli Group
Define the Pauli group Pn on n qubits to be generated by X, Y, and Z on individual qubits. Then Pn consists of all tensor products of up to n operators I, X, Y, or Z with overall phase ±1, ±i.
Any pair M, N of Pauli operators either commutes (MN = NM) or anticommutes (MN = -NM).
The weight of M Pn is the number of qubits on which M acts as a non-identity operator.
The Pauli group spans the set of all n-qubit errors.
Small Error on Every Qubit
Suppose we have a small error U on every qubit in the QECC, where U = I + E.
Un = + (E(1) + … + E(n)) + O(2).
If the code corrects one-qubit errors, it corrects the sum of the E(i)s. Therefore it corrects the O() term, and the state remains correct to order 2.
A code correcting t errors keeps the state correct to order t+1.
QECC is Possible
Measurement of error destroys superpositions.
No-cloning theorem prevents repetition.
Must correct multiple types of errors (e.g., bit flip and phase errors).
How can we correct continuous errors and decoherence?
QECC Conditions
Thm.: A QECC can correct a set E of errors iff
iEa†Ebj = Cab ij
where {i} form a basis for the codewords, and Ea, Eb E.
Note: The matrix Cab does not depend on i and j.
As an example, consider Cab = ab. Then we can make a measurement to determine the error.
If Cab has rank < maximum, code is degenerate.
Erasure Errors
Suppose we know the location of an error, but not its type (I, X, Y, or Z). This is called an erasure.
By QECC conditions iEa†Ebj = Cab ij:
Correct t general errors
Correct 2t erasures
For erasures, QECC conditions become:
TrA does not depend on encoded state , where A is set of qubits which are not erased.
That is, erased qubits have no info. about .
Stabilizer Codes
Error Syndromes Revisited
Let us examine more closely the error syndrome for the classical repetition code.
For correctly-encoded state 000 or 111: first two bits have even parity (an even number of 1’s), and similarly for the 2nd and 3rd bits.
We can rephrase this by saying a codeword is a +1 eigenvector of ZZI and a state with an error on the 1st or 2nd bit is a -1 eigenvector of ZZI.
For state with error on one of the first two bits: odd parity for the first two bits.
Error Syndromes Revisited
For the three-qubit phase error correcting code, a codeword has eigenvalue +1 for XXI, whereas a state with a phase error on one of the first two qubits has eigenvalue -1 for XXI.
Measuring ZZ detects bit flip (X) errors, and measuring XX detects phase (Z) errors.
Error syndrome is formed by measuring enough operators to determine location of error.
Stabilizer for Nine-Qubit Code
X X X X X X
X X X X X X
We can write down all the operators determining the syndrome for the nine-qubit code.
These generate a group, the stabilizer of the code, consisting of all Pauli operators M with the property that M = for all encoded states .
Properties of a Stabilizer
The stabilizer is a group:
If M = and N = , then MN = .
The stabilizer is Abelian:
If M = and N = , then
(MN-NM) = MN - NM = 0
(For Pauli matrices)
Given any Abelian group S of Pauli operators, define a code space T(S) = { s.t. M = M S}. Then T(S) encodes k logical qubits in n physical qubits when S has n-k generators (so size 2n-k).
Stabilizer Elements Detect Errors
Suppose M S and Pauli error E anticommutes with M. Then:
M (E) = - EM = - E,
so E has eigenvalue -1 for M.
Conversely, if M and E commute for all M S,
M (E) = EM = E M S,
so E has eigenvalue +1 for all M in the stabilizer.
The eigenvalue of an operator M from the stabilizer detects errors which anticommute with M.
Distance of a Stabilizer Code
Let S be a stabilizer, and let T(S) be the corresponding QECC. Define
N(S) = {N Pn s.t. MN=NM M S}.
Then the distance d of T(S) is the weight of the smallest Pauli operator N in N(S) \ S.
The code detects any error not in N(S) \ S (i.e., errors which commute with the stabilizer are not detected).
Why minus S? “Errors” in S leave all codewords fixed, so are not really errors. (Degenerate QECC.)
Error Syndromes and Stabilizers
To correct errors, we must accumulate enough information about the error to figure out which one occurred.
The error syndrome is the list of eigenvalues of the generators of S: If the error E commutes with M S, then M has eigenvalue +1; if E and M anticommute, M has eigenvalue -1.
We can then correct a set of possible errors if they all have distinct error syndromes.
Stabilizer Codes Correct Errors
A stabilizer code with distance d corrects (d-1)/2 errors (i.e., to correct t errors, we need d = 2t+1):
E and F act the same, so we need not distinguish.
Thm.: The code corrects errors for which E†F N(S) \ S for all possible pairs of errors (E, F).
E and F have same error syndrome
E and F commute with same elements of S
E†F N(S)
E†F =
F = E
Stabilizer Codes Summary
Choose an Abelian subgroup of the Pauli group. This will be the stabilizer S of the QECC.
The codewords: { s.t. M = M S}
If S has r generators on n qubits, the QECC has k = n-r encoded qubits.
The codes corrects errors if E†F N(S) \ S for all pairs (E, F) of possible errors. The distance d is the minimum weight of N(S) \ S.
Application: 5-Qubit Code
We can generate good codes by picking an appropriate stabilizer. For instance:
X Z Z X I
I X Z Z X
X I X Z Z
Z X I X Z
n = 5 physical qubits
- 4 generators of S
k = 1 encoded qubit
Distance d of this code is 3.
Notation: [[n,k,d]] for a QECC encoding k logical qubits in n physical qubits with distance d. The five-qubit code is a non-degenerate [[5,1,3]] QECC.
The Smallest QECC
Can we do better than a [[5,1,3]] QECC? No.
Recall that correcting 1 general error is equivalent to correcting 2 erasure errors.
Suppose we had a 4-qubit code which could correct 2 erasure errors:
Each pair of qubits has 2 erasures
Cloning machine
Classical Linear Codes
A large and useful family of classical error-correcting codes can be defined similarly, using a parity check matrix. Let H be a (n-k) x n binary matrix, and define a classical error-correcting code C of n-bit vectors by
v C Hv = 0.
C is linear: v,w C v+w C. Also, let the distance d of C be the weight (# of non-zero entries) of the smallest non-zero v C. Then a code with distance 2t+1 corrects t errors: the error syndrome of error e is He, and He = Hf only if e+f C.
Classical Hamming Codes
H = ( )
1 1 1 1 0 0 0
1 1 0 0 1 1 0
1 0 1 0 1 0 1
Define a parity check matrix whose columns are all vectors of length r. E.g., for r=3:
This code has distance 3: if error e has weight 1, the error syndrome He specifies its location. Thus, the Hamming code for r is an [n=2r-1, k=2r-r-1, d=3] ECC (with k logical bits encoded in n physical bits and distance 3).
E.g., for r=3, we have a [7,4,3] code.
Linear Codes and Stabilizers
The classical parity check matrix H is analogous to the stabilizer S of a quantum error-correcting code. Indeed, if we replace all of the 1’s of H with Z operators, we get a stabilizer S defining exactly the same classical code. In particular, it can correct the same number of bit-flip errors.
E.g., Stabilizer of the [7,4,3] Hamming code:
Z Z Z Z I I I
Z Z I I Z Z I
Z I Z I Z I Z
We can then define a quantum error-correcting code by choosing two classical linear codes C1 and C2, and replacing the parity check matrix of C1 with Z’s and the parity check matrix of C2 with X’s.
X X X X I I I
X X I I X X I
X I X I X I X
Z Z Z Z I I I
Z Z I I Z Z I
Z I Z I Z I Z
C1: [7,4,3] Hamming
C2: [7,4,3] Hamming
[[7,1,3]] QECC
Which CSS Codes Are Possible?
Not all pairs C1 and C2 are possible: the stabilizer must be Abelian.
If v C1 and w C2, the corresponding Pauli operators commute iff v w = 0. Thus, w C2 is also in (C1) = C1.
The dual C of a classical code C is the set of vectors w s.t. v w = 0 for all v C. The rows of the parity check matrix for C generate C.
To make a CSS code, we require C2 C1.
Properties of CSS Codes
The parameters of a CSS code made from C1, a [n,k1,d1] code, and C2, a [n,k2,d2] code, are
[[n, k1 + k2 - n, d’]] with d’ min (d1,d2).
Why ? Because of degeneracy (e.g., 9-qubit code).
Codewords of a CSS code are superpositions of classical codewords: For v C1,
v = v+w
If v-v’ C2, v and v’ are the same state, so v should run over C1/C2. (Recall C2 C1.)
Summary: Stabilizer Codes
We can describe a quantum stabilizer code by giving its stabilizer, an Abelian subgroup of the Pauli group.
By looking at the stabilizer, we can learn all of the most interesting properties of a QECC, including the set of errors it can correct.
One interesting and useful class of stabilizer codes is the family of CSS codes, derived from two classical codes. The 7-qubit code is the smallest example.
Quantum Error Correction Sonnet
We cannot clone, perforce; instead, we split
Coherence to protect it from that wrong
That would destroy our valued quantum bit
And make our computation take too long.
Correct a flip and phase - that will suffice.
If in our code another error's bred,
We simply measure it, then God plays dice,
Collapsing it to X or Y or Zed.
We start with noisy seven, nine, or five
And end with perfect one. To better spot
Those flaws we must avoid, we first must strive
To find which ones commute and which do not.
With group and eigenstate, we've learned to fix
Your quantum errors with our quantum tricks.
Fault-Tolerant Quantum Computation
Error Propagation
When we perform multiple-qubit gates during a quantum computation, any existing errors in the computer can propagate to other qubits, even if the gate itself is perfect.
CNOT propagates bit flips forward:
Phase errors propagate backwards:
Fault-Tolerance
Fault-tolerant error correction
Fault-tolerant measurement
Fault-tolerant encoded gates
Fault-tolerant preparation of encoded state
We need to avoid error propagation, and also need to perform gates without decoding the QECC.
Ideal Decoder and t-Filter
Ideal decoder
Corrects errors and decodes state producing an unencoded qubit.
These operations cannot be performed using real gates, but they are useful for defining and proving fault-tolerance.
t-Error filter
Projects on states that are within t errors of a valid codeword
code block
decoded qubit
Properties of FT gates
Gate Prop. 1:
Gate Prop. 2:
Errors propagate benignly. (Similarly for preparation.)
A good FT gate performs the right gate on the encoded state. (Similarly for preparation and measurement.)
(r+s 1 for distance 3 code)
(r+s 1 for distance 3 code)
Transversal Operations
Error propagation is only a serious problem if it propagates errors within a block of the QECC. Then one wrong gate could cause the whole block to fail.
The solution: Perform gates transversally - i.e. only between corresponding qubits in separate blocks.
7-qubit code
7-qubit code
Encoded X and Z
X X X X I I I
X X I I X X I
X I X I X I X
Z Z Z Z I I I
Z Z I I Z Z I
Z I Z I Z I Z
Operations which commute with a stabilizer, but are not in it, perform encoded operations: We can identify them as logical Pauli gates. Also, they are transversal.
X X X X X X X
Z Z Z Z Z Z Z
Logical Gates
For the 7-qubit code, CNOT, Hadamard H, and phase gate P = R/2 = diag (1,i) can all be done with transversal gates. (They generate the Clifford group, which can be efficiently simulated classically.)
For instance, for CNOT:
CNOT7 v+w v’+w’
= v+w (v+v’)+(w+w’)
= (logical CNOT) v v’
FT Preparation and Measurement
FT measurement for a CSS code:
v = v+w
If we measure each qubit, we get a classical codeword v from C1, shifted by a random codeword from C2. Use classical EC to find v.
FT preparation:
Encode using any circuit.
Perform FT error correction.
Test encoded state.
Properties of FT Error Correction
EC Prop. 1:
Good error correction corrects any pre-existing errors.
Good error correction leaves the encoded state alone.
(s 1 for distance 3 code)
(r+s 1 for distance 3 code)
EC Prop. 2:
Fault-Tolerant Error Correction
How can we perform error correction transversally?
Encoded state
Non-fault-tolerant measurement of Z Z Z Z:
An error here could propagate to two qubits.
Fault-Tolerant Error Correction
How can we perform error correction transversally?
Even strings
0000 + 1111
Encoded state
Fault-tolerant measurement of Z Z Z Z:
Measure parity
Fault-Tolerant Error Correction
Create and verify “cat” states 0000 + 1111.
Measure stabilizer generators to learn syndrome.
Repeat for more confidence.
More advanced FT syndrome measurement techniques use more complicated ancillas, but fewer operations on the data:
Steane error correction (uses encoded states)
Knill error correction (based on teleportation)
Shor fault-tolerant error correction:
Steane Error Correction
data block
For CSS codes:
Ancilla blocks are encoded using same code (verify them before using)
bit flips propagate forwards
phase errors propagate backwards
errors in classical codewords reveal locations of errors
random classical codeword w/ error
Universal Fault-Tolerant QC
To complete a universal set of gates, we need some additional gate outside the Clifford group, for instance the /8-gate: R/4 0 = e-i/80, R/4 1 = ei/81.
We cannot perform it transversally, so we will need a more complicated construction:
Create special ancilla state
Perform teleportation-like procedure
Perform Clifford group logical “correction”
Teleporting Quantum Gates
Quantum teleportation followed by U:
Bell measurement
2 classical bits
00 + 11
Pauli operator Q specified by classical bits
Correction operator UQU† specified by classical bits
Special ancilla
Fault-Tolerant /8-Gate
/8 gate has a special and useful property:
R/4 X R/4† = e-i/4 PX, R/4 Z R/4† = Z
The correction required after teleportation is a Clifford group gate, for which we already know a fault-tolerant procedure!
Create ancilla state: encoded 00 + ei/4 11
Perform teleportation-like procedure
Perform Clifford group logical “correction”
Extended Rectangles
Definition: An “extended rectangle” (or “ExRec”) consists of an EC step (“leading”), fo
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com