Quantum Gates
with Multiple Controls
Andreas Klappenecker
Thursday, September 25, 2014
diag(1 , 2 ) = P U P . Then P diagonalizes V as well, so P V P = diag(a, b).
Since
diag(1 , 2 ) = P U P = (P V P )(P V P ) = diag(a2 , b2 ),
it follows that a = 1 and b = 2 are complex numbers of absolute value
1. Therefore, diag(a, b) is a unitary matrix and we can conclude that V =
P diag(a, b)P is a unitary matrix as well.
Goal
Theorem 2 A unitary gate controlled by two control bits can be expressed
in terms of singly controlled quantum gates as follows:
=
U
where V is a 2 2 unitary matrix such that U = V 2 .
Proof. The gate on the left hand side acts on basis states in the following way:
Thursday, September 25, 2014
|00 |x
|01 |x
|10 |x
|11 |x
|00 |x
|01 |x
|10 |x
|11 U |x
matrix and we can conclude that V =
1.it Therefore,
diag(a,
b)
is
a
unitary
follows that a = 1 and b = 2 are complex numbers of absolute value
P1.diag(a,
b)P is diag(a,
a unitary
as well.
Therefore,
b) matrix
is a unitary
matrix and we can conclude that V =
Proof
diag(a, b)P is a unitary matrix as well.
P
Theorem 2 A unitary gate controlled by two control bits can be expressed
in terms of singly controlled quantum gates as follows:
Theorem 2 A unitary gate controlled by two control bits can be expressed
in terms of singly controlled quantum gates as follows:
=
U
= V
U
V
V
where V is a 2 2 unitary matrix such that U = V 2 .
Proof.
left hand
side acts
basis
states
whereThe
V isgate
a 2on
2the
unitary
matrix
suchon
that
U=
V 2 . in the following way:
|x side
acts
|00on
|x
Proof. The gate on the|00
left
hand
basis states in the following way:
|01 |x |01 |x
|00
|x |10|00
|x
|10
|x
|x
|01
|x |11|01
|x
|11
|x
U|x
|10 |x |10 |x
for x {0, 1}. The five gates
in
circuit
right
|11
|x on
the
|11
Uhand
|x side act on the basis
states as follows:
for x
1}.The
gates
in circuit
act
on|x
the basis
|00
|x{0,
|00
|x five
|00
|x
|00 on
|xthe right
|00hand
|x side
|00
states
asfollows:
|01
|x
|01 V |x|01 V |x|01 V V |x|01 |x |01 |x
Thursday, September 25, 2014
|10
|x
|10
|x
|11
|x
|11
V
|x
|10
V
|x |x
|00 |x|00 |x |00 |x |00 |x
|00 |x
|x|10
|00
2
|11
|x
|11
V
|x
|10
V
|x
|10
V
|x
|11 V |x |11 V |x
|01 |x|01 V |x|01 V |x|01 V V |x|01 |x |01 |x
=
it follows that a = 1 and b = 2 are complex numbers of absolute value
1. Therefore, diag(a, b) is a unitary matrix and we can conclude that V =
U
V
V
V
P diag(a, b)P is a unitary matrix as well.
Proof
2.
where
V
is
a
2
2
unitary
matrix
such
that
U
=
V
Theorem 2 A unitary gate controlled by two control bits can be expressed
in terms of singly controlled quantum gates as follows:
Proof. The gate on the left hand side acts on basis states in the following way:
|00 |x
= |x
|01
|10 |x
V
|11 |x
|00 |x
|01 |x
|10 |x
V U |x
|11
for
x V{0,
five gates
in circuit
theUright
side act on the basis
where
is1}.
a 2 The
2 unitary
matrix
suchon
that
= V 2hand
.
states as follows:
Proof.
The
actson
states
the following
way:
|00 |x
gate
|00 on
|xtheleft
|00hand
|xside
|00
|xbasis
|00 in|x
|00 |x
|01 |x|01 V |x|01 V |x|01 V V |x|01 |x |01 |x
|00 |x |00 |x
|10 |x|10 |x |11 |x |11 V |x |10 V |x|10 |x
|01 |x |01 |x
|11 |x|11 V |x|10 V |x|10 V |x |11 V |x |11 V 2 |x
|10 |x
|10 |x
|11 |x
|11 U |x
for x {0, 1}. The five gates in circuit on the right hand side act on the basis
states as follows:
Thursday, September 25, 2014
|00 |x|00 |x |00 |x |00 |x
|00 |x
|01 |x|01 V |x|01 V |x|01 V V |x|01 |x
|00 |x
|01 |x
Loose Ends...
It remains to show that for a given 2x2 unitary matrix U, there
really exists a unitary 2x2 matrix V that is the square-root of U.
Thursday, September 25, 2014
matrix V such that U = V 2 . The next lemma gives a convenient way to
find a square root of a unitary 2 2 matrix without tedious eigenvalue and
eigenvector calculations. This construction will be helpful when trying to
replace a quantum gate with two control bits by simpler gates that have one
control bit.
Convenient Squareroot Lemma
Lemma 2 Let U be a unitary 2 2 matrix that is not a multiple of the
identity matrix I. Then
1
V =
(U
tr U 2 det U
det U I)
is a unitary matrix satisfying U = V 2 .
Thursday, September 25, 2014
Proof. Let us first show that V
is a well-defined matrix. Seeking a contradiction, we assume that tr U 2 det U = 0. Let 1 , 2 be the eigenvalues of U .
We have det U = 1 2 and tr U = 1 + 2 . It follows that
1 + 2 = tr U = 2 det U = 2 1 2 .
Since U is unitary, |1 | = |2 | = 1. Therefore, |1 + 2 | = 2| 1 2 | = 2.
This means that the triangle inequality |1 + 2 | 2 = |1 | + |2 | holds with
equality, which implies that 1 = r2 for some positive real number r. Since
identity matrix I. Then
1
Proof of Squareroot Lemma
V =
(U
tr U 2 det U
det U I)
is a unitary matrix satisfying U = V 2 .
Proof. Let us first show that V
is a well-defined matrix. Seeking a contradiction, we assume that tr U 2 det U = 0. Let 1 , 2 be the eigenvalues of U .
We have det U = 1 2 and tr U = 1 + 2 . It follows that
1 + 2 = tr U = 2 det U = 2 1 2 .
Since U is unitary, |1 | = |2 | = 1. Therefore, |1 + 2 | = 2| 1 2 | = 2.
This means that the triangle inequality |1 + 2 | 2 = |1 | + |2 | holds with
equality, which implies that 1 = r2 for some positive real number r. Since
|1 | = |2 | = 1, we have |r| = r = 1, which means that the eigenvalues 1 and
2 must be the same. This would imply that U isa multiple of the identity,
contradicting our hypothesis. Therefore, tr U 2 det U is nonzero and the
matrix V is well-defined.
Thursday, September 25, 2014
Proof
of
Squareroot
Lemma
42
CHAPTER 4. UNIVERSALITY
By the Cayley-Hamilton theorem, the unitary 2 2 matrix U satisfies its
characteristic equation U 2 + (tr U )U + (det U )I = 0; thus,
(tr U )U = U 2 + (det U )I.
Using this relation, we obtain
V
=
=
=
Thursday, September 25, 2014
1
2
(U
det
U
I)
tr U 2 det U
1
2
(U
+
(det
U
)I
2
det
U
tr U det U
1
(tr U 2 det U )U = U
tr U 2 det U
U)
It remains to show that V is a unitary matrix. Recall that the unitary matrix
U can be diagonalized by a base change with some unitary matrix P , say
diag(1 , 2 ) = P U P . Then P diagonalizes V as well, so P V P = diag(a, b).
Since
diag(1 , 2 ) = P U P = (P V P )(P V P ) = diag(a2 , b2 ),
it follows that a = 1 and b = 2 are complex numbers of absolute value
(tr U )U = U + (det U )I.
ProofV of
Squareroot Lemma
=
Using this relation, we obtain
=
=
1
2
(U
det
U
I)
tr U 2 det U
1
2 + (det U )I 2 det U
(U
tr U det U
1
(tr
U
2
det
U
)U
=
U
tr U 2 det U
U)
It remains to show that V is a unitary matrix. Recall that the unitary matrix
U can be diagonalized by a base change with some unitary matrix P , say
diag(1 , 2 ) = P U P . Then P diagonalizes V as well, so P V P = diag(a, b).
Since
diag(1 , 2 ) = P U P = (P V P )(P V P ) = diag(a2 , b2 ),
it follows that a = 1 and b = 2 are complex numbers of absolute value
1. Therefore, diag(a, b) is a unitary matrix and we can conclude that V =
P diag(a, b)P is a unitary matrix as well.
Theorem 2 A unitary gate controlled by two control bits can be expressed
in terms of singly controlled quantum gates as follows:
=
Thursday, September 25, 2014
Conclusions
A quantum gate with 2 control bits can be realized with quantum
gates that have just a single control bit.
More generally, a quantum gate with m control bits can be realized
with quantum gates that have m-1 control bits.
In summary, a quantum gates with multiple controls can be realized
by quantum gates that have just single controls, and those can be
realized by single quantum bit gates and controlled-not gates.
Thursday, September 25, 2014
