Q1L5d.txt

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

An important subgroup of stabilizer states
may be given a graphical representation.
These are called graph states.
Let us begin with a representation of stabilizer
states known as the symplectic representation,
sometimes also called a check matrix representation
or a binary representation of a stabilizer.
This form is defined as follows.
For a stabilizer given by a set of generators g1 through gk
the binary representation is a k by 2n matrix of 0s and ones.
The matrix has k rows, and given that there
are n qubits being acted upon by the k generators,
this matrix has 2n columns.
The reason there are 2n columns
is because half represents the X operators and half represent
the Z operators.
Again, there are k rows, each row corresponding
to one generator, and each of the X and Z matrices
have n columns.
Again, the X matrix is composed of 0s and ones, and the Z
matrix also of 0s and ones.
Each row corresponds to a generator of S,
where an I is replaced by a zero and an X is replaced
by a one in the X matrix, a Z is replaced
by a one in the Z matrix, and a Y
produces a one in both the X and the Z matrices.
Recognizing that stabilizer generators may
have signs or factors of i, the overall sign for each row
may also be included with a sign or factor of plus or minus i
for each row.
Let us examine what a graph representation of a state
is for a specific example.
Consider the stabilizer generated by XX and ZZ.
The binary matrix representation of this
is the four-column two-row matrix,
where the left represents the fact
that there are XX in the first generator
and ZZ has a one one in the bottom right.
Another example is the GHZ state,
which has stabilizers XXX, IZZ, and ZZI,
And its binary matrix representation looks like this.
Again, the X is on the left, Z is on the right.
A third example is given by a stabilizer with a YY,
such as XX and minus YY.
Here we show what happens with the sign.
We have a stabilizer matrix now with a minus one one and one
one for the YY operator.
This binary matrix representation
is useful, as we now turn to the definition of a graph state.
A graph state is a stabilizer state
which has a particular structure for its binary representation
matrix.
Namely, that on the left has an identity matrix of full rank,
and on the right has a matrix that
is appropriate for being the adjacency matrix of a graph.
Namely, that it has zeroes on the diagonals and is symmetric.
For an n qubit system, this matrix has n rows,
the identity matrix is n by n, and the adjacency matrix also
n by n.
Let me emphasize this is a representation
for states and not of vector spaces, which
are multi-dimensional.
This is the symplectic or binary representation
for a graph state.
But of course we can also rewrite it in the normal
operator representation with X's and Z's.
X's would correspond to nodes and Z's would
correspond to links.
Let us see how this works by looking at some examples.
First, consider a simple three-qubit system
with a stabilizer given by XZI, ZXZ, and IZX.
This has a binary matrix representation
with an identity on the left and a adjacency matrix
on the right, as can be verified by seeing
that this matrix is symmetric and has zeroes on its diagonal.
Labeling the qubits as one, two, and three,
we may take the nodes to be labeled one, two,
and three in the corresponding graph
and link the nodes, which have Z operators between them.
Namely, one goes to two and two goes to three.
So these links shown by the adjacency matrix
give us a graph representation of this particular stabilizer
state.
Keep in mind, though, an important fact-- graph states
are a subset of stabilizer states.
We may always construct a graph state from a stabilizer state
as I will show.
But a given graph state may represent multiple stabilizer
states.
This degeneracy is captured by the concept of local Clifford
operations.
These are the unitary transforms generated by the Hadamard
gate and the s gate.
Again, these are single-qubit operations,
and that is what local refers to.
The Hadamard gate is something we are familiar with.
The s gate-- the phase gate is one, zero, zero, i,
or may be considered the square root of the Pauli Z gate.
These two gates have a familiar transformation
of Pauli operators.
H transforms X to Z and Z to X. As we have written many times
before, this is by conjugation.
And in addition, H changes the sign of Y,
but leaves it unchanged.
The phase gate leaves Z unchanged,
but flips X and Y. That is SXS dagger is equal to Y,
and SYS dagger is equal to X. So it
flips X and Y as a permutation.
Local Clifford operators are important in mapping
from stabilizer states to graph states.
I claim that all stabilizer states
are equivalent to a graph state under some local Clifford
operation.
I will not prove this in its entirety here,
but I will give the main idea behind the proof,
and there are three steps.
First, for a stabilizer state, each qubit
must have at least one X or Z acting on it in some stabilizer
generator.
This may be transformed into an X Pauli operator
using H. Or if necessary, if it's a Y,
then transform with an s.
Second, all X's and Y's which appear off the diagonal
may be transformed into Z's by using a method of gaussian
elimination.
I'll show this in an example shortly.
Finally, the Z's which remain will
be symmetric about the diagonal, and this
is because all the generator elements
must commute with each other.
So any time there is an XZ in one row,
there must be a ZX in another row.
These ideas are perhaps best understood
through some examples.
Let us return to the GHZ state, where we have zero,
zero, zero plus one, one, one.
The stabilizer is generated by XXX, ZZI, and IZZ, for example.
Working directly in this representation,
let us write the three generators out
as rows of a matrix.
The first step is to get X's on the diagonal,
so let us apply Hadamard to the two right-hand qubits.
This gives us a transformed set of generators, XZZ, IXX,
and ZXI.
Now, doing Gaussian elimination, we want to remove all
the elements on the lower triangle which are not
X's and transform them into Z's.
So let us multiply the last two generators giving us
ZIX for the last generator, leaving the first two
generators the same.
Now we have X's along the diagonal,
and if we look at the lower triangle,
we have no X's and only Z's.
On the upper triangle, we still have an X.
And we want to transform that to remove it,
and therefore we may multiply the middle generator
by the bottom generator and replace to get ZXI.
Now we have the desired form.
The lower and upper triangles have no X's, and the matrix
has a diagonal set of X's and is symmetric in its Z
representation.
The binary symplectic form of this stabilizer
has an identity on the left, and on the right
a symmetric matrix, which is interpretable
as an adjacency matrix.
Labeling the nodes as one, two, and three,
we may then draw this state as a graph.
From the adjacency matrix we see that one is connected to two
and one is connected to three.
Of course, this graph is isomorphic to the one which
we saw earlier, which has a linear structure of one, two,
and three connected to each other.
OK, now let us turn to a more complex example,
the five-qubit code.
I have gone ahead and written out all the transformation
steps.
Note the initial state has an additional X to the five
added to it to make it a state and not just a code.
First we want to eliminate these two
X's in the first qubit of the lower triangle.
We do this by multiplying this middle stabilizer together
with the first stabilizer, which has an X on the diagonal,
and replacing.
Thus we may write out G prime of 3,
the third generator is replaced by G1 times G3.
That gives us IZYYZ.
Similarly, for the fifth generator,
we may multiply it by G1 to obtain minus IYYIX.
Second, let's eliminate the non-Z operators
happening in the second qubit in the lower triangle.
We have Y in this last generator,
let's multiply that by G2 to get rid of it.
And then X in this fourth generator, let's
again multiply by G2.
And next we do the third qubit.
We multiply the last generator by G3,
and then we do the same to remove the last lower triangle
qubit, which is non-Z. So we multiply G4 and G5.
And finally, we are left with a stabilizer which has a lower
triangle set with only Z's in it, no X's or Y's.
Note that our diagonal doesn't completely have X's yet,
but don't worry, we'll fix that in a little bit.
Now for the second stage, we fix the upper right triangle.
Gaussian elimination again, starting from the bottom,
moving up.
So we observe that we have a Y here in G4, so we replace G4
by G4 times G5.
Next let us do qubit four.
We observe that we have a Y here in G3.
And we eliminate that by multiplying G3 by G4.
And similarly, we observe we have an X here in G1,
so we remove that again by multiplying by G4.
Normally, we would continue this for qubits 3 and 2,
but by inspection, we note that we are done at this point.
Each of the generators one by one
may be confirmed to have only Z operators
on the right of the diagonal as well
as on the left of the diagonal.
Therefore, we are done with the transformation
to a graph state form.
To be more explicit, let us write this out
in the binary symplectic matrix form.
We find that the X's gives us an identity
matrix of full rank on the left.
And the Z's give us a matrix which is a suitable adjacency
matrix on the right.
This adjacency matrix gives us a graph
with five nodes, which looks like a pentagram, where
each one of the nodes is connected to its nearest
neighbor in this shape.
The same transformation can be done for other stabilizer
states as well.
I encourage you to try it.
For example, see what the seven-qubit code state turns out to be as a graph.