4Measurement-based quantum computing
III Quantum Computation
4 Measurement-based quantum computing
In this chapter, we are going to look at an alternative model of quantum
computation. This is rather weird. Instead of using unitary gates and letting
them act on state, we prepare a generic starting state known as a graph state, then
we just keep measuring them. Somehow, by cleverly planning the measurements,
we will be able to simulate any quantum computation in the usual sense with
such things.
We will need a bunch of new notation.
Notation. We write
|±
α
i =
1
√
2
(|0i ± e
−iα
|1i).
In particular, we have
|±
0
i = |±i =
1
√
2
(|0i ± |1i)
Then
B(α) = {|+
α
i, |−
α
i}
is an orthonormal basis. We have 1-qubit gates
J(α) =
1
√
2
1 e
iα
1 −e
iα
= HP(α),
where
H =
1
√
2
1 1
1 −1
, P(α) =
1 0
0 e
iα
.
We also have the “Pauli gates”
X =
0 1
1 0
, Z =
1 0
0 −1
= P(π)
We also have the 2-qubit gates
E = CZ = diag(1, 1, 1, −1).
We also have 1-qubit measurements
M
i
(α) = measurement of qubit i in basis B(α).
The outcome |+
α
i is denoted 0 and the outcome |−
α
i is denoted 1.
We also have M
i
(Z), which is measurement of qubit
i
in the standard basis
{|0i, |1i}.
Finally, we have the notion of a graph state. Suppose we have an undirected
graph
G
= (
V, E
) with vertices
V
and edges
E
with no self-loops and at most
one edge between two vertices, we can define the graph state
|ψ
G
i
that is a state
of
|V |
qubits as follows: for each vertex
i ∈ V
, introduce a qubit
|+i
i
. For each
edge
e
:
i → j
, we apply
E
ij
(i.e.
E
operating on the qubits
i
and
j
). Since all
these E
ij
commute, the order does not matter.
Example. If G
1
is
0 1
then we have
|ψ
G
1
i = E
12
|+i
1
|+i
2
=
1
2
[|00i + |01i + |10i − |11i],
and this is an entangled state.
If G
2
is
0 1 2
then we have
|ψ
G
2
i = E
12
E
23
|+i
1
|+i
2
|+i
3
.
A cluster state is a graph state |ψ
G
i for G being a rectangular 2D grid.
The main result of measurement-based quantum computation is the following:
Theorem.
Let
C
be any quantum circuit on
n
qubits with a sequence of
gates
U
1
, ··· , U
K
(in order). We have an input state
|ψ
in
i
, and we perform
Z-measurements on the output states on specified qubits
j
=
i
1
, ··· , i
k
to obtain
a k-bit string.
We can always simulate the process as follows:
(i)
The starting resource is a graph state
|ψ
G
i
, where
G
is chosen depending
on the connectivity structure of C.
(ii)
The computational steps are 1-qubit measurements of the form M
i
(
α
), i.e.
measurement in the basis
B
(
α
). This is adaptive —
α
may depend on the
(random) outcomes s
1
, s
2
, ··· of previous measurements.
(iii)
The computational pro cess is a prescribed (adaptive) sequence M
i
1
(
α
1
),
M
i
2
(α
2
), ···, M
i
N
(α
N
), where the qubit labels i
1
, i
2
, ··· , i
N
all distinct.
(iv)
To obtain the output of the process, we perform further measurements
M(Z) on
k
specified qubits not previously measured, and we get results
s
i
1
, ··· , s
i
k
, and finally the output is obtained by further (simple) classical
computations on s
i
1
, ··· , s
i
k
as well as the previous M
i
(α) outcomes.
The idea of the last part is that the final measurement
s
i
1
, ··· , s
i
k
has to be
re-interpret in light of the results M
i
(α
i
).
This is a funny process, because the result of each measurement
M
i
(
α
) is
uniformly random, with probability
1
2
for each outcome, but somehow we can
obtain useful information by doing adaptive measurements.
We now start the process of constructing such a system. We start with the
following result:
Fact. The 1-qubit gates J(α) with E
i,i±1
is a universal set of gate.
In particular, any 1-qubit U is a product of 3 J’s.
We call these E
i,i±1
nearest neighbour E
ij
’s.
Proof. This is just some boring algebra.
So we can assume that our circuit
C
’s gates are all of the form J(
α
)’s or E
0
ij
s
,
and it suffices to try to implement these gates in our weird system.
The next result we need is what we call the J-lemma:
Lemma (J-lemma). Given any 1-qubit state |ψi, consider the state
E
12
(|ψi
1
|+i
2
).
Suppose we now measure M
1
(
α
), and supp os e the outcome is
s
1
∈ {
0
,
1
}
. Then
after measurement, the state of 2 is
X
s
1
J(α) |ψi.
Also, two outcomes
s
= 0
,
1 always occurs with probability
1
2
, regardless of the
values of |ψib, α.
Proof. We just write it out. We write
|ψi = a |0i + b |1i.
Then we have
E
12
(|ψi
1
|+i
2
) =
1
√
2
E
12
(a |0i|0i + a |0i|1i + b |1i|0i + b |1i|1i)
=
1
√
2
(a |0i|0i + a |0i|1i + b |1i|0i − b |1i|1i)
So if we measured 0, then we would get something proportional to
h+
α
|
1
E
12
(|ψi
1
|+i
2
) =
1
2
(a |0i + a |1i + be
iα
|0i − be
iα
|1i)
=
1
2
1 e
iα
1 −e
iα
a
b
,
as required. Similarly, if we measured 1, then we get XJ(α) |ψi.
We will usually denote processes by diagrams. In this case, we started with
the graph state
|ψi |+i
and the measurement can be pictured as
α
s
1
|ψi |+i
If we measure Z, we denote that by
Z
i
In fact, this can be extended if 1 is just a single qubit part of a larger multi-qubit
system 1S, i.e.
Lemma. Suppose we start with a state
|ψi
1S
= |0i
1
|ai
S
+ |1i
1
|bi
S
.
We then apply the
J
-lemma process by adding a new qubit
|+i
for 2
6∈ S
, and
then query 1. Then the resulting state is
X
s
1
2
J
2
(α) |ψi
2S
.
So the J-lemma allows us to simulate J-gates with measurements. But we
want to do many J gates. So we need the concatenation lemma:
Lemma
(Concatenation lemma)
.
If we concatenate the process of J-lemma on a
row of qubits 1
,
2
,
3
, ···
to apply a sequence of J(
α
) gates, then all the entangling
operators E
12
, E
23
, ··· can be done first before any measurements are applied.
It is a fact that for any composite quantum system
A ⊗ B
, any local actions
(unitary gates or measurements) done on
A
always commutes with anything
done on
B
, which is easy to check by expanding out the definition. So the proof
of this is simple:
Proof.
For a state
|ψi
1
|+i
2
|+i
3
···
, we can look at the sequence of J-processes
in the sequence of operations (left to right):
E
12
M
1
(α
1
)E
23
M
2
(α
2
)E
34
M
3
(α
3
) ···
It is then clear that each E
ij
commutes with all the measurements before it. So
we are safe.
We can now determine the measurement-based quantum computation process
corresponding to a quantum circuit
C
of gates
U
1
, U
2
, ··· , U
K
with each
U
i
either
a J(
α
) or a nearest-neighbour E
ij
. We may wlog assume the input state to
C
is
|+i···|+i
as any 1-qubit product state may be written as
|ψi = U |+i
for suitable
U
, which is then represented as at most three J(
α
)’s. So we simply
prefix C with these J(α) gates.
Example. We can write |ji for j = 0, 1 as
|ji = X
j
H |+i.
We also have
H = J(0), X = J(π)J(0).
So the idea is that we implement these J(
α
) gates by the J-processes we just
described, and the nearest-neighbour E
ij
gates will just be performed when we
create the graph state.
We first do a simple example:
Example. Consider the circuit C given by
|+i
|+i
J(α
1
)
J(α
2
)
J(α
3
)
where the vertical line denotes the
E
12
operators. At the end, we measure the
outputs i
1
, i
2
by M(Z) measurements.
We use the graph state
In other words, we put a node for a
|+i
, horizontal line for a J(
α
) and a vertical
line for an E.
If we just measured all the qubits for the
J
-process in the order
α
1
, α
2
, α
3
,
and then finally read off the final results i
1
, i
2
:
s
1
α
1
s
2
α
2
s
3
α
3
i
1
Z
i
2
Z
then we would have effected the circuit
|+i
|+i
J(α
1
)
J(α
2
)
X
s
1
X
s
2
J(α
3
)
X
s
3
Now the problem is to get rid of the
X
i
’s. We know each
X
i
comes with
probability
1
2
. So the probability of them all not appearing is tiny for more
complicated circuits, and we cannot just rely on pure chance for it to turn out
right.
To deal with the unwanted
X
i
“errors”, we want to commute them out to
the end of the circuit. But they do not commute, so we are going to use the
following commutation relations:
J(α)X = e
iα
ZJ(−α)
In other words, up to an overall phase, the following diagrams are equivalent:
X
J(α)
is equivalent to
J(−α)
X
More generally, we can write
J
i
(α)X
s
i
= e
−iαs
Z
s
i
J
i
((−1)
s
α)
J
i
(α)Z
s
i
= X
s
i
J
i
(α)
E
ij
Z
s
i
= Z
s
i
E
ij
E
ij
X
s
i
= X
s
i
Z
s
i
E
ij
Here the subscripts tell us which qubit the gates are acting on.
The last one corresponds to
X
is equivalent to
X
Z
All of these are good, except for the first one where we have a funny phase and
the angle is negatived. The phase change is irrelevant because it doesn’t affect
measurements, but the sign changes are problematic. To fix this, we need to use
adaptive measurements.
Example. Consider the simpler 1-qubit circuit
|+i J(α
1
) J(α
2
)
We first prepare the graph sate
We now measure the first qubit to get
r
1
α
1
We have thus done
|+i J(α
1
)
X
r
1
To deal with the unwanted X
r
1
, we note that
X
r
1
J(α
2
)
is equivalent to
J((−1)
r
1
α
2
)
Z
r
1
So we adapt the sign of the second measurement angle to depend on the previous
measurement result:
r
1
α
1
r
2
(−1)
r
1
α
2
Then this measurement results in
J(α
1
)
X
r
1
J((−1)
r
1
α
2
)
X
r
2
which is equivalent to
J(α
1
) J(α
2
)
Z
r
1
X
r
2
If we had further J-gates, we need to commute both Z
r
1
and X
r
2
over.
Note that while we are introducing a lot of funny X’s and Z’s, these are all
we’ve got, and the order of applying them does not matter, as they anti-commute:
XZ = −ZX.
So if we don’t care about the phase, they effectively commute.
Also, since X
2
= Z
2
=
I
, we only need to count the number of X’s and Z’s
mod 2, which is very helpful.
Now what do we do with the Z and X at the end? For the final Z-measurement,
having moved everything to the end, we simply reinterpret the final, actual
Z-measurement result j:
(i)
The Z-gate does not affect outcome or probability of a Z-measurement,
becasuse if
|ψi = a |0i + b |1i,
then
Z |ψi = a |0i − b |1i.
So the probabilities of |0i and |1i are |a|
2
and |b|
2
regardless.
(ii)
The X gate simply interchanges the labels, while leavining probabilities
the same, because if
|ψi = a |0i + b |1i,
then
X |ψi = a |1i + b |0i.
So we ignore all Z-errors, and for each X
r
error, we just modify the seen
measurement outcome j by j 7→ j ⊕ r.
If we actually implement measurement-based quantum computations, the
measurements can always be done “left to right”, implementing the gates in order.
However, we don’t have to do that. Recall that quantum operations on disjoint
qubits always commute. Since the only thing we are doing are measurements,
all
M
i
(
α
) measurements can be performed simultaneously if the angles
α
do
not depend on other measurements. This gives us a novel way to parallel a
computation.
For example, in our simple example, we can start by first measuring
r
1
and
j
, and then measuring
r
2
after we know
r
1
. In particular, we can first measure
the “answer”
j
, before we do any other thing! The remaining measurements just
tell us how we should interpret the answer.
In general, we can divide the measurements into “layers” — the first layer
consists of all measurements that do not require any adaptation. The second
layer then consists of the measurements that only depends on the first layer. The
logical depth is the least number of layers needed, and this somewhat measures
the complexity of our circuit.