2Quantum computation
III Quantum Computation
2 Quantum computation
We are now going to start talking about quantum computation. Our model of
quantum computation will be similar to the circuit model.
The main difference is that instead of working with bits, we work with qubits.
A single qubit is an element of C
2
, with basis vectors
|0i =
1
0
, |1i =
0
1
.
When we have multiple qubits, we write them as
|ai|bi
, which is a shorthand
for |ai ⊗ |bi etc.
Now any classical bit string x = i
1
i
2
···i
n
can be encoded as a qubit
|i
1
i|i
2
i···|i
n
i|0i···|0i ∈
n+k
O
i=0
C
2
∼
=
C
2
n+k
,
where we padded
k
extra zeroes at the end. In classical computation, there was
no such need, because within any computation, we were free to introduce or
remove extra bits. However, one peculiarity of quantum computation is that all
processes are invertible, and in particular, the number of qubits is always fixed.
So if we want to do something “on the side” during the computations, the extra
bits needed to do so must b e supplied at the beginning.
Now the quantum gates are not just boolean functions, but unitary operators
on the states. The standard gates will operate on one or two qubits only, and
we can chain them together to get larger operators.
We now list our standard unitary gates. The four main (families) single-qubit
gates we will need are the following (in the standard |0i, |1i basis):
X =
0 1
1 0
, Z =
1 0
0 −1
, H =
1
√
2
1 1
1 −1
, P
ϕ
=
1 0
0 e
ϕ
We also have two “controlled” gates. These controlled gates take in two qubits.
It does not directly change the first qubit, and will decide whether or not to act
on the second bit depending on the value of the first. They are given by
CX |ii|ji = |iiX
i
|ji, CZ |ii|ji = |ii
In the basis {|0i|0i, |0i|1i, |1i|0i, |1i|1i}, we can write these operators as
CX =
1 0 0 0
0 1 0 0
0 0 0 1
0 0 1 0
, CZ =
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 −1
,
These will be taken as the basic unitary gates.
The other thing we are allowed to do in a quantum system is measurement.
What does this do? We wlog we are measuring the first qubit. Suppose the state
before the measurement is given by
c
0
|0i|ai + c
1
|1i|bi,
where |ai, |bi are (n − 1)-qubit states of unit norm, and |c
0
|
2
+ |c
1
|
2
= 1.
Then when we measure the first qubit, we have probability
|c
0
|
2
of getting 0,
and probability
|c
1
|
2
of getting 1. After measuring, the resulting state is either
|0i|ai or |1i|bi, depending on whether we measured 0 or 1 respectively.
Measurements are irreversible, and in particular aren’t given by unitary
matrices. We will allow ourselves to make classical computations based on the
results of the measurements, and decide which future quantum gates we apply
based on the results of the classical computations.
While this seems like a very useful thing to do, it is a mathematical fact
that we can modify such a system to an equivalent quantum one where all
the measurements are done at the end instead. So we are not actually adding
anything new to our mathematical model of computation by allowing such
classical manipluations.
Now what is the analogous notion of a universal set of gates? In the classical
case, the set of boolean functions is discrete, and therefore a finite set of gates
can be universal. However, in the quantum case, the possible unitary matrices
are continuous, so no finite set can be universal (more mathematically, there is
an uncountable number of unitary matrices, but a finite collection of gates can
only generate a countable subgroup of matrices).
Thus, instead of asking for universality, we ask for approximate universality.
To appreciate this, we can take the example of rotations — there is no single
rotation that generates all possible rotations in
R
2
. However, we can pick a
rotation by an irrational angle, and then the set of rotations generated by this
rotation is dense in the set of all rotations, and this is good enough.
Definition
(Approximate universality)
.
A collection of gates is approximately
universal if for any unitary matrix
U
and any
ε >
0, there is some circuit
˜
U
built out of the collection of gates such that
U −
˜
U
< ε.
In other words, we have
sup
kψk=1
U |ψi −
˜
U |ψi
< ε,
where we take the usual norm on the vectors (any two norms are equivalent if
the state space is finite dimensional, so it doesn’t really matter).
We will provide some examples without proof.
Example. The infinite set {CX} ∪ {all 1-qubit gates} is exactly universal.
Example. The collection
{H, T = P
π/4
, CX}
is approximately universal.
Similar to the case of classical computation, we can define the following
complexity class:
Definition
(
BQP
)
.
The complexity class
BQP
(bounded error, quantum
polynomial time) is the class of all decision problems computable with polynomial
quantum circuits with at least 2/3 probability of b eing correct.
We can show that
BQP
is independent of choice of approximately universal
gate set. This is not as trivial as the classical case, since when we switch to
a different set, we cannot just replace a gate with an equivalent circuit — we
can only do so approximately, and we have to make sure we control the error
appropriately to maintain the bound of 2/3.
We will consider
BQP
to be the feasible computations with quantum com-
putations.
It is also a fact that
BPP
is a subset of
BQP
. This, again, is not a trivial
result. In a quantum computation, we act by unitary matrices, which are
invertible. However, boolean functions in classical computing are not invertible
in general. So there isn’t any straightforward plug-in replacement.
However, it turns out that for any classical computation, there is an equivalent
computation that uses reversible/invertible boolean gates, with a modest (i.e.
polynomial) overhead of both space and time resources. Indeed, let
f
:
B
m
→ B
n
be a boolean function. We consider the function
˜
f : B
m+n
→ B
m+n
(x, y) 7→ (x, y ⊕ f(x)),
where
⊕
is the bitwise addition (i.e. addition in (
Z/
2
Z
)
n
, e.g. 011
⊕
110 = 101).
We call x and y the input register and output register respectively.
Now if we set
y
= 0, then we get
f
(
x
) in the second component of
˜
f
. So we
can easily obtain f from
˜
f, and vice versa.
Lemma. For any boolean function f : B
m
→ B
n
, the function
˜
f : B
m+n
→ B
m+n
(x, y) 7→ (x, y ⊕ f(x)),
is invertible, and in fact an involution, i.e. is its own inverse.
Proof.
Simply note that
x ⊕ x
= 0 for any
x
, and bitwise addition is associative.
So we can just consider boolean functions that are invertible. There is an
easy way of making this a unitary matrix.
Lemma.
Let
g
:
B
k
→ B
k
be a reversible permutation of
k
-bit strings. Then
the linear map on C
k
defined by
A : |xi 7→ |g(x)i
on k qubits is unitary.
Proof.
This is because the
x
th column of the matrix of
A
is in fact
A |xi
=
|g(x)i
,
and since g is bijective, the collection of all |g(x)i are all orthonormal.
Thus, given any
f
:
B
m
→ B
n
, we get the
n
+
m
-qubit unitary matrix
denoted by U
f
, given by
U
f
|xi|yi = |xi|y ⊕ f(x)i.
In particular, if we set |yi = |0 ···0i, then we get
|xi|0 ···0i |xi|f(x)i
U
f
,
which we can use to evaluate f(x).
What does quantum computation give us? Our gate
U
f
is unitary, and in
particular acts linearly on the states. So by linearity, we have
1
√
2
n
X
x
|xi|0 ···0i
1
√
2
n
X
x
|xi|f(x)i
U
f
.
Now one run of
U
f
gives us this state that embodies all exponentially many
values of
f
(
x
)’s. Of course, we still need to figure out how we can extract useful
information from this mixed state, and we will figure that out later on.
While the state
|ψi =
1
√
2
n
X
x
|xi
has exponentially many terms, it can be made in polynomial (and in fact linear)
time by n applications of H. Indeed, recall that H is given by
|0i
1
√
2
(|0i + |1i)
H
So for an n-qubit state, we have
|0i···|0i
1
√
2
n
(|0i + |1i) ···(|0i+ |1i)
H⊗···⊗H
,
and expanding the right hand side gives us exactly what we want.