82 5. TOP-DOWN
and decomposition (4.10), that is,
U
H
H
H
H
D
D
0
C
0
B
0
A
0
:
e question arises whether (2.4) can be deduced from (4.5) and whether (2.5) can be deduced
from (4.10), as a permutation matrix is a special case of a unitary matrix. is question will be
addressed in the present chapter.
5.2 LIGHT MATRICES
As a special case of the two synthesis methods of Chapter 4, we consider for U a permutation
matrix. Such a choice is particularly interesting, as a 2
w
2
w
permutation matrix represents a
classical reversible computation on w bits, i.e., the subject of Chapter 2. For w D 2, we investi-
gate the example
U D
0
B
B
@
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0
1
C
C
A
: (5.1)
Its four constitutive blocks and their polar decompositions are
U
11
D
0 1
0 0
D
1 0
0 0
0 1
x 0
U
12
D
0 0
0 1
D
0 0
0 1
y 0
0 1
U
21
D
1 0
0 0
D
1 0
0 0
1 0
0 z
U
22
D
0 0
1 0
D
0 0
0 1
0 w
1 0
;
where x, y, z, and w are arbitrary unit-modulus numbers. us, in this example, none of the
four polar decompositions U
jk
D P
jk
V
jk
is unique. If, in particular, we choose x D w D i and
y D z D i, then we find, by means of (4.11), a primal bZbXbZ decomposition of U consisting
5.2. LIGHT MATRICES 83
exclusively of permutation matrices:
0
B
B
@
0 1
1 0
1 0
0 1
1
C
C
A
0
B
B
@
0 1
1 0
1 0
0 1
1
C
C
A
0
B
B
@
1 0
0 1
0 1
1 0
1
C
C
A
:
In the next section, we will demonstrate that such decomposition is possible for any n n per-
mutation matrix (provided n is even).
e above example leads us to a deeper analysis of sparse unitary matrices.
Definition 5.1 Let M be an m m matrix with, in each row and each column, maximum one
non-zero entry. We call such a sparse matrix “light.” Let be the number of non-zero entries
of M . We call the weight of M . We have 0 m. If D m, then M is regular; if < m,
then M is singular.
e reader will easily understand the proof for the following two lemmas.
Lemma 5.2 Let P U (with P a positive-semidefinite matrix and U a unitary matrix) be the polar
decomposition of an m m light matrix M . en P is a diagonal matrix and U is a complex permu-
tation matrix. If , the weight of M , equals m, then U is unique; otherwise, we have an .m /-
dimensional infinity of choices for U .
Lemma 5.3 If P is a diagonal matrix and U is a complex permutation matrix, then U
P U is a
diagonal matrix, with the same entries as P , in a permuted order.
We now combine these two lemmas. Assume that the n n matrix U consists of four
n=2 n=2 blocks, such that the two blocks U
11
and U
12
are light. en, by virtue of Lemma 5.2,
the positive-semidefinite matrices P
11
and P
12
are diagonal. erefore P
11
iP
12
is diagonal
and so is .P
11
iP
12
/
2
. By virtue of Lemma 5.2 again, the matrix V
11
is a complex permu-
tation matrix. Finally, because of Lemma 5.3, the matrix C D V
11
.P
11
iP
12
/
2
V
11
in (4.11)
is diagonal and so are I C C and I C . As a result, for n D 2
w
, the matrix G
I
C
G D
1
2
I C C I C
I C I C C
is of a form like (4.14) with all
a b
c d
of NEGATOR type and thus represents
a cascade of 2
w1
NEGATOR gates acting on the first qubit and controlled by the w 1 other
qubits:
H
H
diagonal C
D
:
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.