Universal quantum gates

4.1 Universal quantum gates I

Universal quantum gates I
In this exercise and the two that follow , we will establish that several
simple sets of gates are universal for quantum computation.
The Hadamard transformation H is the single-qubit gate that acts in
the standard basis as

in quantum circuit notation, we denote the Hadamard gate as

The single-qubit phase gate P acts in the standard basis as

and is denoted

A two-qubit controlled phase gate acts in the standard basis
as the diagonal 4 × 4 matrix

and can be denoted

Despite this misleading notation, the gate actually acts symmetrically
on the two qubits:

We will see that the two gates H and comprise a universal gate
set – any unitary transformation can be approximated to arbitrary
accuracy by a quantum circuit built out of these gates.

a) Consider the two-qubit unitary transformations U₁ and U₂ defined
by quantum circuits

Let denote the element of the standard basis where a labels
the upper qubit in the circuit diagram and b labels the lower
qubit. Write out U₁ and U₂ as 4 × 4 matrices in the standard
basis. Show that U₁ and U₂ both act trivially on the states

b) Thus U₁ and U₂ act nontrivially only in the two-dimensional space
spanned by

Show that, ex pressed in this basis , they are

c) Now express the action of U₁ and U₂ on this two-dimensional
subspace in the form

What are the unit vectors ?

d) Consider the transformation (Note that can also be
constructed from the gates H and .) Show that it performs
a rotation with half-angle θ/2 in the two-dimensional space
spanned by the basis eq. (5), where cos(θ/2) = 1/4.

4.2 Universal quantum gates II

We have now seen how to compose our fundamental quantum gates to
perform, in a two-dimensional subspace of the four-dimensional Hilbert
space of two qubits, a rotation with cos(θ/2) = 1/4. In this exercise, we
will show that the angle θ is not a rational multiple of . Equivalently,
we will show that

is not a root of unity: there is no finite integer power n such that

Recall that a polynomial of degree n is an expression

with a_n ≠ 0. We say that the polynomial is rational if all of the a_k’s
are rational numbers, and that it is monic if a_n = 1. A polynomial
is integral if all of the a_k’s are integers, and an integral polynomial is
primitive if the greatest common divisor of {a₀, a₁, . . . , a_n} is 1.

a) Show that the monic rational polynomial of minimal degree that
has as a root is

The property that is not a root of unity fol lows from the result
(a) and the

Theorem If a is a root of unity, and P(x) is a monic rational polynomial
of minimal degree with P(a) = 0, then P(x) is integral.

Since the minimal monic rational polynomial with root is not
integral, we conclude that is not a root of unity. In the rest of
this exercise, we will prove the theorem.

b) By “long division” we can prove that if A(x) and B(x) are rational
polynomials, then there exist rational polynomials Q(x) and R(x)
such that

where the “remainder” R(x) has degree less than the degree of
B(x). Suppose that aⁿ = 1, and that P(x) is a rational polynomial
of minimal degree such that P(a) = 0. Show that there is a
rational polynomial Q(x) such that

c) Show that if A(x) and B(x) are both primitive integral polynomials,
then so is their product C (x) = A(x)B(x). Hint: If
is not primitive, then there is a prime number
p that divides all of the c_k’s. Write A(x) = , and
, let a_r denote the coefficient of lowest order in
A (x) that is not divisible by p (which must exist if A(x) is primitive),
and let b_s denote the coefficient of lowest order in B(x)
that is not divisible by p. Express the product a_rb_s in terms of
c _r+s and the other a_l’s and b_m’s, and reach a contradiction.

d) Suppose that a monic integral polynomial P(x) can be factored into
a product of two monic rational polynomials, P(x) = A(x)B(x).
Show that A(x) and B(x) are integral. Hint: First note that we
may write , and , where r, s
are positive integers, and are primitive integral;
then use (c) to show that r = s = 1.

e) Combining (b) and (d), prove the theorem.

What have we shown? Since is a rotation by an irrational
multiple of π, the powers of are dense in a U(1) subgroup.

Similar reasoning shows that is a rotation by the same angle
about a different axis , and therefore its powers are dense in another
U(1) subgroup. Products of elements of these two noncommuting U(1)
sub groups are dense in the SU(2) subgroup that contains both U₁ and U₂

Furthermore, products of are dense in another SU(2), spanned by

Together, these two SU(2) subgroups close on the SU(3) subgroup
that acts on the three-dimensional space orthogonal to Conjugating
this SU(3) by we obtain another SU(3) acting on the three
dimensional space orthogonal to The
only subgroup of SU(4) that contains both of these SU(3) subgroups
is SU(4) itself.

Therefore, the circuits constructed from the gate set are
dense in SU(4)— we can approximate any two-qubit gate to arbitrary
accuracy, which we know suffices for universal quantum computation.
Whew!

4.3 Universal quantum gates III

We have shown that the gate set is universal. Thus any
gate set from which both can be constructed is also
universal. In particular, we can see that is a universal
set.

a) It is sometimes convenient to characterize a quantum gate by specifying
the action of the gate when it conjugates a Pauli operator.
Show that H and P have the properties

and

b) Note that, since, the gate can be
constructed using H and P. Show that

c) Construct circuits for and using the gate set .
Then complete the proof of universality for this gate set by constructing
using

The Toffoli gate is universal for reversible classical computation.
What must be added to realize the full power of quantum
computing? We have just seen that the single-qubit gates H and P,
together with the Toffoli gate, are adequate for reaching any unitary
transformation. But in fact, just H and suffice to efficiently
simulate any quantum computation.

Of course, since H and are both real orthogonal matrices,
a circuit composed from these gates is necessarily real — there are
complex n -qubit unitaries that cannot be constructed with these tools.
But a 2ⁿ-dimensional complex vector space is isomorphic to a 2ⁿ⁺¹–
dimensional real vector space. A complex vector can be encoded by a
real vector according to

and the action of the unitary transformation U can be represented by
a real orthogonal matrix defined as

To show that the gate set is “universal,” it suffices to
demonstrate that the real encoding of can be constructed
from and H.

d) Verify that
e) Use and H to construct a circuit for .

Thus, the classical Toffoli gate does not need much help to unleash the
power of quantum computing. In fact, any nonclassical single-qubit
gate ( one that does not preserve the computational basis), combined
with the Toffoli gate, is sufficient.

4.4 Universality from any entangling two-qubit gate

We say that a two-qubit unitary quantum gate is local if it is a tensor
product of single-qubit gates, and that the two-qubit gates U and V
are locally equivalent if one can be transformed to the other by local
gates:

It turns out (you are not asked to prove this) that every two-qubit
gate is locally equivalent to a gate of the form:

where

a) Show that V (π/4,π/4,π/4) is (up to an overall phase) the SWAP
operation that inter changes the two qubits :

b) Show that V (0, 0,π/4) is locally equivalent to the CNOT gate
.

As discussed in the lecture notes, the CNOT gate together with
arbitrary single-qubit gates form a universal gate set. But in fact
there is nothing special about the the CNOT gate in this regard. Any
two-qubit gate U, when combined with arbitrary single-qubit gates,
suffices for universality unless U is either local or locally equivalent to
SWAP.

To demonstrate that U is universal when assisted by local gates it
suffices to construct using a circuit containing only local gates
and U gates

Lemma If U is locally equivalent to , then can be
constructed from a circuit using local gates and U gates except in two
cases: (1) (U is local), (2) (U
is locally equivalent to SWAP)..

You will prove the Lemma in the rest of this exercise

c) Show that:

d) Show that V (0, 0, θ) is locally equivalent to the controlled rotation
for an arbitrary
axis of rotation (Here = (X, Y ,Z).)

e) Now use the results of (c) and (d) to prove the Lemma.