Q2L6c.txt

#
# File:   content-mit-8371x-subtitles/Q2L6c.txt
#
# Captions for 8.421x module
#
# This file has 137 caption lines.
#
# Do not add or delete any lines.  If there is text missing at the end, please add it to the last line.
#
#----------------------------------------

Fault tolerant computation requires gates on encoded data.
What gates can be performed on quantum codes
such as stabilizer codes?
Recall that under a unitary transform,
a stabilizer changes by conjugation.
We define the normalizer of S in the Pauli group G
to be N of S, the set of Pauli operators G,
such that G conjugates every element of S back to itself.
Equivalently, we may also define the normalizer
as being the set of Pauli operators
which commute with every element in the stabilizer.
Let us prove this lemma.
Recall that for any two elements, g and h in the Pauli
group, either g and h commute or anti-commute.
What does this tell us about how they conjugate each other?
Well, this means that ghg dagger is either plus or minus hgg
dagger.
And that means plus or minus h.
However, remember that minus h cannot be in the stabilizer
because minus identity is excluded from the stabilizer
by definition.
Therefore, that g conjugates h back
to itself is implied by g commuting with h.
Let us look at some examples of normalizers.
Consider the stabilizer generated by IZ and ZI.
If you look for all possible Paulis which
commute with both of these generators,
we find that that set includes the identity ZZ, ZI, and IZ.
In fact, we find that the normalizer of S
is a super set of the stabilizer itself.
Consider as another example the stabilizer generated by XX.
What is the normalizer for this stabilizer?
Well, in fact let us look at the normalizer excluding
the stabilizer.
This set includes IX and XI.
Go look at this example more yourself
and you'll see that a bit flip on any single qubit
here transforms between the two code words of this stabilizer
code, namely 0 0 plus 1 1 and 0 1 plus 1 0.
Let us turn to another example.
Consider the stabilizer generated by IXX and IZZ
This seems to encode a single qubit.
And in fact, that is exactly shown
by the normalizer modulo of the stabilizer, which
has X and Z on the first qubit.
This suggests the normalizer captures the logical behavior
of a qubit.
Consider the stabilizer of the three qubit code.
Here, the normalizer modulo S has XXX and other elements.
Recognizing that XXX flips 0 0 0 to 1 1 1,
we may call it a logical operator X bar.
It acts on the code words of the three qubit
code, which encodes one qubit to flip logical 0 and logical 1.
Conceptually, we may picture normalizers
and their relationship to stabilizers as follows.
Within the space of all Pauli operators G,
we have a subspace of normalizers N of S. N of S
includes S. This group S, though, has
multiple cosets within N of S.
For example, a coset representative N1
may multiply S or N2 or N3 and so forth.
Normalizer operations, therefore, transform states
within a stabilizer without taking states outside
of the stabilizer.
They are thus useful for describing errors.
Define the weight of a stabilizer element
g as a number of non-identity Pauli operators in g.
We may then say that a stabilizer code C of S
has distance d If the normalizer modulo of the stabilizer
has no elements with weight less than d.
This is the direct analog of the Hamming distance used
for classical linear codes.
It is also useful to generalize the concept of a normalizer
beyond just the Pauli group to allow any unitary operation
on the stabilizer state.
Let us denote such a generalized normalizer as N tilde
and ask the question, what is N tilde acting on the Pauli
group.
Well, it is straightforward to see
that the normalizer, the generalized normalizer,
of the one qubit Pauli group is generated by the Hadamard gate
and the Phase gate S. Recall, S is square root of Z. This
is the group of local Clifford operators
as we have seen previously.
More explicitly, we can see that H transforms
X, Y, and z to become Z, minus Y, and X,
while S produces y, x and z.
It is straightforward to see any permutation of x y z
and signs can be constructed from H and S.
And thus, they generate the normalizer
of the single qubit Pauli group.
How about the normalizer of the two qubit Pauli group?
Well, recall that we have seen that the controlled NOT
gate also conjugates Paulis to Paulis.
If we have an X operating on the target
before the controlled NOT gate, that corresponds to an X
after the CNOT gate.
If we have an X on the control before the CNOT,
then that conjugates to become two X-gates
after the CNOT gate.
Therefore, we have a truth table which looks like this.
The CNOT gate conjugates the inputs IX, XI, IZ, and ZI,
labeled as control and target in that order
to become IX, XX, ZZ, and ZI.
We define C2 as being the normalizer of the Pauli group
and claim that it is generated by H, S, and the CNOT.
This group is known as the Clifford group.
I invite you to prove to yourself
that it is the normalizer of the Pauli group.
Let us capture this important statement as a theorem.
This theorem, known as the Gottesman-Knill theorem,
is fundamental to our study of operations
on quantum stabilizer codes.
The theorem has two parts.
First, suppose u is a unitary operator
which conjugates Paulis to Paulis for all Paulis
in the Pauli group.
Then, the theorem holds that u can
be constructed from order of n squared, H, S, and CNOT gates.
This means that a natural description
of stabilizer operations is given by H, S, and CNOT gates.
Note that the proof gives this construction explicitly.
The second part of the theorem holds
that any quantum circuit composed from H, S, and CNOT
gates acting on an input state of qubits all in the 0 state,
possibly including measurement in the computational bases
and any additional classical control,
including feed forward control, any such quantum circuit
may be simulated efficiently and entirely classically.
This is a remarkable and important theorem which you
will prove in the problem set.
The Gottesman-Knill theorem therefore states that universal
quantum computation cannot be generated by using H, S,
and CNOT gates alone.
Something more is needed, something beyond the Clifford
group is needed for universal quantum computation.