We’ve taken the circuit analogy for quantum computation up to gates. Can
we go further? Can we identify a set of universal gates, as we did for classical
computation?
Since a computation is essentially the evaluation of a function of the inputs,
let’s first fix what we mean by a quantum function evaluation. Consider a
function f : {0, 1}
n
7→ {0, 1}
m
that takes an n-bit input x and produces an
m-bit output f(x). A reversible implementation of this function would have
an n + m-bit input and the same number of bits in the output. We will use
this to define the unitary operator implementing f (x).
134 Introduction to Quantum Physics and Information Processing
Definition 7.1. A quantum function evaluator is a unitary operator U
f
,
for f : {0, 1}
n
7→ {0, 1}
m
, such that
U
f
|xi|yi = |xi|f(x) ⊕ yi. (7.23)
This is essentially an f-controlled XOR gate (which is like an f-controlled
NOT gate if m = 1), expressed in the circuit of Figure 7.15.
|xi
U
f
|xi
|yi |f(x) ⊕ yi
FIGURE 7.15: Quantum function evaluator.
Here, |xi is an n-qubit basis state while |yi is an m-qubit one. Note that
U
f
will be represented by an n + m square matrix. If the input lower register
y = 0, then the output on the register is just f(x).
Exercise 7.14. Show that U
f
as defined in Equation 7.23 is unitary and therefore
reversible.
The important feature of a unitary transformation is not only that it admits
an inverse, but also that it is linear. So it acts on superpositions thus:
U
f
(c
1
|x
1
i + c
2
|x
2
i) |yi = c
1
U
f
(|x
1
i|yi) + c
2
U
f
(|x
2
i|yi) . (7.24)
For instance, if the input is the uniform superposition of two qubits, the
linearity of U
f
means that
U
f
1
√
2
(|0i + |1i) |0i =
1
√
2
(|0i|f(0)i + |1i|f (1)i) .
The output is an entangled superposition state of both registers, containing
both f(0) as well as f(1). This generalizes to multiple qubits as well. A uniform
superposition of n qubits is the normalized sum of all 2
n
possible n-qubit basis
states |0i, |1i. . . |2
n
− 1i. So we have
U
f
1
√
2
n
2
n
−1
X
x=0
|xi
n
!
|0i
m
=
1
√
2
n
2
n
−1
X
x=0
|xi
n
|f(x)i
m
(7.25)
where the subscripts on the states indicate the dimensionality. The function
has been evaluated in parallel on all inputs. This has been referred to as
quantum parallelism. The catch is, however, that this superposition does
not mean much to our classical minds, until we measure the output, upon
which one of the answers is selected! We can never know all the f(x)’s at
once, nor can we clone the output and hope to learn f (x) by making repeated
measurements of the output state.
Nevertheless, this feature is enormously useful in designing quantum algo-
rithms. One has to additionally choose clever modifications of the output such
that the state containing the answer occurs with high amplitude. We will see
this in action in the next chapters
Leave a Reply