Quantum Error Correction 3:
The stabilizer formalism
QuIC Seminar 48
Tuesday Sep. 29, 2020
Outline
Fault-tolerant logical state preparation.
(a) Encoding circuit(s).
(b) Bit flip errors.
Raw: Do nothing.
Correction: Correct errors.
Detection: Discard errors.
(c) Logical T2 time.
*OK, there’s a lot in this paper (especially experimental descriptions) which we won’t fully get into. But we’ll understand a solid chunk of it.
*OK, there’s a lot in this paper (especially experimental descriptions) which we won’t get into to. But we’ll understand a large majority of the paper.
Today.
Next week.
Next next week.
Outline
The stabilizer formalism: A preview
We’ll then use this formalism for:
The Pauli group
The Pauli group
Stabilizers
A stabilizer S is a subgroup of the n-qubit Pauli group.
Stabilizers
A stabilizer S is a subgroup of the n-qubit Pauli group.
A +1 eigenstate of every element in S is a codeword.
Stabilizers
A stabilizer S is a subgroup of the n-qubit Pauli group.
A +1 eigenstate of every element in S is a codeword.
The codespace is the span of all codewords.
Condition for a nontrivial codespace
Theorem: Let S be a stabilizer. If -I is in S or S is non-abelian, then the C(S) is trivial.
Stabilizer elements
Theorem: Every element of a (nontrivial) stabilizer squares to identity, and therefore has eigenvalues +1 and -1.
Group generators
Example: The stabilizer for the bit-flip code is S = {I, Z1 Z2, Z2 Z3, Z1 Z3}.
Show that S = <Z1 Z2, Z2 Z3>.
Show that S = <Z1 Z2, Z1 Z3>.
Symplectic notation
Symplectic notation
Symplectic notation
Symplectic notation
Symplectic notation
Symplectic notation
Examples: Symplectic notation
Write the following in symplectic notation. Assume all are on three qubits.
Examples: Symplectic notation
Write the following in symplectic notation. Assume all are on three qubits.
Examples: Symplectic notation
Write the following in symplectic notation. Assume all are on three qubits.
Examples: Symplectic notation
Write the following in symplectic notation. Assume all are on three qubits.
Examples: Symplectic notation
Write the following in symplectic notation. Assume all are on three qubits.
Examples: Symplectic notation
Write the following in symplectic notation. Assume all are on three qubits.
Outline
Multiplication in Symplectic notation
We can easily multiply Pauli strings by addition module two in our symplectic notation.
Multiply
Add (mod 2)
Symplectic notation
Notice that the RHS is binary vectors of length 2n.
Formally, this space is which is a group under addition modulo two.
Pauli multiplication is identical to vector addition.
Symplectic notation is thus a group homomorphism
That is, a mapping such that r(A B) = r(A) r(B).
Why is this useful? Independent stabilizer elements
Suppose I give you S1, …, Sn, another Pauli S, and ask whether
Why is this useful? Independent stabilizer elements
Suppose I give you S1, …, Sn, another Pauli S, and ask whether
If S is not in the set, we say {S1, …, Sn, S} is an independent set of stabilizers.
Why is this useful? Independent stabilizer elements
Suppose I give you S1, …, Sn, another Pauli S, and ask whether
If S is not in the set, we say {S1, …, Sn, S} is an independent set of stabilizers.
Symplectic notation allows us to answer this with a simple linear algebra problem:
Why is this useful? Independent stabilizer elements
Suppose I give you S1, …, Sn, another Pauli S, and ask whether
If S is not in the set, we say {S1, …, Sn, S} is an independent set of stabilizers.
Symplectic notation allows us to answer this with a simple linear algebra problem:
Theorem: {S1, …, Sn, S} is an independent set of stabilizers iff {r(S1), …, r(Sn), r(S)} is a linearly independent set of vectors.
Why is this useful? Independent stabilizer elements
Theorem: {S1, …, Sn, Sj} is an independent set of stabilizers iff {r(S1), …, r(Sn), r(Sj)} is a linearly independent set of vectors.
Proof: We prove the contrapositive. (If the vectors are linearly dependent, the set is dependent.)
Commutativity in symplectic notation
Suppose I give you S1, S2 and ask whether
Commutativity in symplectic notation
Suppose I give you S1, S2 and ask whether
This can be done with symplectic notation also.
Commutativity in symplectic notation
Suppose I give you S1, S2 and ask whether
This can be done with symplectic notation also.
Theorem:
Commutativity in symplectic notation
Why is this true?
Commutativity in symplectic notation
Why is this true?
Two Paulis commute if they match on X and Z in an even number of places, else they anti-commute.
Commutativity in symplectic notation
Why is this true?
Two Paulis commute if they match on X and Z in an even number of places, else they anti-commute.
The matrix reverses the X and Z blocks (1st/2nd half) of the vector it acts on.
Commutativity in symplectic notation
Why is this true?
Two Paulis commute if they match on X and Z in an even number of places, else they anti-commute.
The matrix reverses the X and Z blocks (1st/2nd half) of the vector it acts on.
Thus is equal to the number of places that S1 and S2 match on X and Z (modulo 2).
Example: Commutativity in symplectic notation
Example: Commutativity in symplectic notation
Check matrix
Stabilizer codes are sometimes presented via their check matrix M(S).
Check matrix
Stabilizer codes are sometimes presented via their check matrix M(S).
Given stabilizer the check matrix is simply
Check matrix
Stabilizer codes are sometimes presented via their check matrix M(S).
Given stabilizer the check matrix is simply
Check matrix
Stabilizer codes are sometimes presented via their check matrix M(S).
Given stabilizer the check matrix is simply
Q: What is the check matrix for the phase-flip code?
Shor’s 9-qubit code in the stabilizer formalism
Recall the codewords for Shor’s 9-qubit code.
Shor’s 9-qubit code in the stabilizer formalism
Recall the codewords for Shor’s 9-qubit code.
Q: What are the stabilizers (stabilizer generators)?
Shor’s 9-qubit code in the stabilizer formalism
Recall the codewords for Shor’s 9-qubit code.
Q: What are the stabilizers (stabilizer generators)?
A: Start with the bit-flip code <Z1 Z2, Z2 Z3> and do this in each block:
Block 1
Block 2
Block 3
Shor’s 9-qubit code in the stabilizer formalism
Recall the codewords for Shor’s 9-qubit code.
Q: What are the stabilizers (stabilizer generators)?
A: Start with the bit-flip code <Z1 Z2, Z2 Z3> and do this in each block:
Now the phase-flip code has generators <X1 X2, X2 X3>. Do this across each block:
Block 1
Block 2
Block 3
Shor’s 9-qubit code in the stabilizer formalism
In summary, the generators for Shor’s 9-qubit code are:
Verify that:
Note the logical operators do not necessarily have any relation to the physical operations which implement them!
Quick note on logical operators
It can be shown that logical operators for X and Z exists for any stabilizer code.
We’ll show this in a future seminar.
This will also give us insight into how to form codewords from stabilizers.
Error correction conditions in the stabilizer formalism
Since we’re now describing codes with stabilizer generators, it would be nice to have conditions on which errors are correctable in terms of the stabilizer generators. (Analogue to Knill-Laflamme conditions.)
Error correction conditions in the stabilizer formalism
Since we’re now describing codes with stabilizer generators, it would be nice to have conditions on which errors are correctable in terms of the stabilizer generators. (Analogue to Knill-Laflamme conditions.)
The condition is written in terms of the centralizer (set of commuting elements).
Error correction conditions in the stabilizer formalism
Since we’re now describing codes with stabilizer generators, it would be nice to have conditions on which errors are correctable in terms of the stabilizer generators. (Analogue to Knill-Laflamme conditions.)
The condition is written in terms of the centralizer (set of commuting elements).
With this, the error correction conditions expressed in the stabilizer formalism are...
Error correction conditions in the stabilizer formalism
Theorem: Let S be a stabilizer and {E_j} a set of errors (elements of the n-qubit Pauli group). Then, {E_j} is correctable by S if, for all j and k,
Error correction conditions in the stabilizer formalism
Theorem: Let S be a stabilizer and {E_j} a set of errors (elements of the n-qubit Pauli group). Then, {E_j} is correctable by S if, for all j and k,
S
Z(S)
Bad
region
Error correction conditions in the stabilizer formalism
Theorem: Let S be a stabilizer and {E_j} a set of errors (elements of the n-qubit Pauli group). Then, {E_j} is correctable by S if, for all j and k,
Proof: Deferred! (Nielsen and Chuang Chp. 10.)
S
Z(S)
Bad
region
Error correction conditions in the stabilizer formalism
S
Z(S)
Bad
region
Yes
No
Good!
Yes
No
Good!
Bad!
Stabilizer QEC conditions for the bit-flip code
Consider the bit-flip code
A generating set for bit-flip errors is
Stabilizer QEC conditions for the bit-flip code
Consider the bit-flip code
A generating set for bit-flip errors is
Lemma: An element g commutes with all generators of S if and only if g is in Z(S).
Stabilizer QEC conditions for the bit-flip code
Consider the bit-flip code
A generating set for bit-flip errors is
Lemma: An element g commutes with all generators of S if and only if g is in Z(S).
Why? Suppose and, for all i,
Stabilizer QEC conditions for the bit-flip code
Consider the bit-flip code
A generating set for bit-flip errors is
Lemma: An element g commutes with all generators of S if and only if g is in Z(S).
Why? Suppose and, for all i,
Any element B in S can be written
Stabilizer QEC conditions for the bit-flip code
Consider the bit-flip code
A generating set for bit-flip errors is
Lemma: An element g commutes with all generators of S if and only if g is in Z(S).
Why? Suppose and, for all i,
Any element B in S can be written
Then,
showing that g commutes with all elements.
Stabilizer QEC conditions for the bit-flip code
Consider the bit-flip code
A generating set for bit-flip errors is
Lemma: An element g commutes with all generators of S if and only if g is in Z(S).
Why? Suppose and, for all i,
Any element B in S can be written
Then,
showing that g commutes with all elements. Other direction is obvious.
Stabilizer QEC conditions for the bit-flip code
Consider the bit-flip code
The bit-flip errors are
Stabilizer QEC conditions for the bit-flip code
Consider the bit-flip code
The bit-flip errors are
Consider
Stabilizer QEC conditions for the bit-flip code
Consider the bit-flip code
The bit-flip errors are
Consider
Stabilizer QEC conditions for the bit-flip code
Consider the bit-flip code
The bit-flip errors are
Consider
Stabilizer QEC conditions for the bit-flip code
Consider the bit-flip code
The bit-flip errors are
Consider
The second equation tells us g does not commute with this generator.
Stabilizer QEC conditions for the bit-flip code
Consider the bit-flip code
The bit-flip errors are
Consider
The second equation tells us g does not commute with this generator.
Therefore, g is not in Z(S) - S. So far, so good. Continue in this fashion for all Ej, Ek.
Stabilizer QEC conditions for the bit-flip code
Consider the bit-flip code
The single qubit phase-flip errors are
All products clearly commute with every stabilizer generator.
Therefore these errors are not correctable (as we know).
Stabilizer QEC conditions for the bit-flip code
Consider the bit-flip code
The single qubit phase-flip errors are
All products clearly commute with every stabilizer generator.
Therefore these errors are not correctable (as we know).
Do the same analysis for the phase-flip code.
The five qubit code
Note that the last three generators are the first generator shifted to the right.
The five qubit code
Note that the last three generators are the first generator shifted to the right.
Isn’t it easier to describe the code with stabilizers than with codewords?
The five qubit code
Why does this correct arbitrary single qubit errors?
The five qubit code
Why does this correct arbitrary single qubit errors?
Generating set for single qubit errors is E = {X1, …, X5, Z1, …, Z5}.
The five qubit code
Why does this correct arbitrary single qubit errors?
Generating set for single qubit errors is E = {X1, …, X5, Z1, …, Z5}.
Any element Ej Ek will be of the form or or
The five qubit code
Why does this correct arbitrary single qubit errors?
Generating set for single qubit errors is E = {X1, …, X5, Z1, …, Z5}.
Any element Ej Ek will be of the form or or
We need to show that every Ej Ek does not commute with at least one generator.
The five qubit code
Why does this correct arbitrary single qubit errors?
Generating set for single qubit errors is E = {X1, …, X5, Z1, …, Z5}.
Any element Ej Ek will be of the form or or
We need to show that every Ej Ek does not commute with at least one generator.
This can be seen by inspecting the column structure of the generators.
The five qubit code
Why does this correct arbitrary single qubit errors?
Generating set for single qubit errors is E = {X1, …, X5, Z1, …, Z5}.
Any element Ej Ek will be of the form or or
We need to show that every Ej Ek does not commute with at least one generator.
This can be seen by inspecting the column structure of the generators.
Pick any two columns - there will be at least one row r such that r(j) + r(k) = 1.
The five qubit code
Why does this correct arbitrary single qubit errors?
Generating set for single qubit errors is E = {X1, …, X5, Z1, …, Z5}.
Any element Ej Ek will be of the form or or
We need to show that every Ej Ek does not commute with at least one generator.
This can be seen by inspecting the column structure of the generators.
Pick any two columns - there will be at least one row r such that r(j)+ r(k) = 1.
This guarantees non-commutativity (recall the symplectic notation condition).
The five qubit code
Why does this correct arbitrary single qubit errors?
Generating set for single qubit errors is E = {X1, …, X5, Z1, …, Z5}.
Any element Ej Ek will be of the form or or
The five qubit code
Why does this correct arbitrary single qubit errors?
Generating set for single qubit errors is E = {X1, …, X5, Z1, …, Z5}.
Any element Ej Ek will be of the form or or
Ex: X2 Z3
The five qubit code
Why does this correct arbitrary single qubit errors?
Generating set for single qubit errors is E = {X1, …, X5, Z1, …, Z5}.
Any element Ej Ek will be of the form or or
Ex: X2 Z3
The five qubit code
Why does this correct arbitrary single qubit errors?
Generating set for single qubit errors is E = {X1, …, X5, Z1, …, Z5}.
Any element Ej Ek will be of the form or or
Ex: X2 X4
The five qubit code
Why does this correct arbitrary single qubit errors?
Generating set for single qubit errors is E = {X1, …, X5, Z1, …, Z5}.
Any element Ej Ek will be of the form or or
Ex: X2 X4
The five qubit code
Why does this correct arbitrary single qubit errors?
Generating set for single qubit errors is E = {X1, …, X5, Z1, …, Z5}.
Any element Ej Ek will be of the form or or
Ex: Z1 Z5
The five qubit code
Why does this correct arbitrary single qubit errors?
Generating set for single qubit errors is E = {X1, …, X5, Z1, …, Z5}.
Any element Ej Ek will be of the form or or
Ex: Z1 Z5
The five qubit code
Why does this correct arbitrary single qubit errors?
Generating set for single qubit errors is E = {X1, …, X5, Z1, …, Z5}.
Any element Ej Ek will be of the form or or
Continue in this fashion to show that the five-qubit code can correct all single qubit errors!
Summary: Important takeaways
Questions