84 5. TOP-DOWN
Miraculously, the two HADAMARDs have disappeared from the synthesis. We now are in
a position to discuss the case of U being an n n permutation matrix, representing a classical
reversible computation.
5.3 PRIMAL DECOMPOSITION
First, we will prove that
1
2
I C C I C
I C I C C
is a structured permutation matrix. If U is an n n
permutation matrix, then both
n=2
n=2
blocks
U
11
and U
12
are light, the sum of their weights
11
and
12
being equal to n=2. e matrices P
11
and P
12
are diagonal, with entries equal to 0
or 1, with the special feature that, wherever there is a zero entry in P
11
, the matrix P
12
has
a 1 on the same row, and vice versa. e matrix P
11
iP
12
thus is diagonal, with all diagonal
entries either equal to 1 or to i. Hence, the matrix .P
11
iP
12
/
2
is diagonal, with all diagonal
entries either equal to 1 or to 1, and so is matrix C according to (4.11). Hence, the matrices
I C C and I C are diagonal with entries either 0 or 2. 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
represents a cascade of 1-qubit IDENTITY and NOT gates acting
on the first qubit and controlled by the w 1 other qubits. us, the 2
w1
NEGATOR gates of the
previous section all equal a classical gate: either an IDENTITY gate or a NOT gate.
Next, we proceed with proving that D is also a permutation matrix. e matrices V
11
and
V
12
are complex permutation matrices. e matrix V
11
contains n=2 non-zero entries. Among
them, n=2
11
can be chosen arbitrarily,
11
being the weight of U
11
. We denote these ar-
bitrary numbers by x
j
, analogous to x in the above example (5.1). Analogously, we denote by
y
k
the n=2
12
arbitrary entries of V
12
. Because U is a permutation matrix, the weight sum
11
C
12
necessarily equals n=2. e matrix iV
11
V
12
in (4.11) also is a complex permutation
matrix and thus has n=2 non-zero entries. is number matches the total number of degrees
of freedom .n=2
11
/ C .n=2
12
/ D n=2. Because U is a permutation matrix, V
11
and V
12
can be chosen such that the non-zero entries of the product iV
11
V
12
depend only on an x
j
or
on an y
k
but not on both. More particularly these entries are either of the form i=x
j
or of the
form iy
k
. By choosing all x
j
equal to i and all y
k
equal to i, the matrix iV
11
V
12
, and thus
D, is a permutation matrix.
Because U ,
1
2
I C C I C
I C I C C
, and
I
D
are permutation matrices,
A
B
also is an
n n permutation matrix. Ergo, given an n n permutation matrix U , the Führ–Rzeszotnik
procedure allows us to construct a 3-sandwich of permutation matrices. erefore, we recover
here the Birkhoff decomposition method for permutation matrices and thus, for n D 2
w
, the
primal synthesis method for classical reversible logic circuits in Chapter 2.
In an analogous way, application of (4.12) instead of (4.11) also yields a permutation-
matrix decomposition into three permutation matrices. And there is more: we obtain exactly
the same decomposition. Indeed, if we start from a permutation matrix U , then .P
11
C iP
12
/
2
is the same diagonal matrix as .P
11
iP
12
/
2
and substituting x
j
D i and y
k
D i into iV
11
V
12
gives the same matrix as substituting x
j
D i and y
k
D i into iV
11
V
12
. We conclude that the
5.3. PRIMAL DECOMPOSITION 85
two primal decompositions of a quantum circuit have one and the same primal decomposition
of a classical circuit as a special case.
As an extra example, we consider the 8 8 permutation matrix
U D
0
B
B
B
B
B
B
B
B
B
B
B
@
0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 0
0 0 0 0 0 1 0 0
1 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 1 0 0 0 0 0
0 1 0 0 0 0 0 0
1
C
C
C
C
C
C
C
C
C
C
C
A
: (5.2)
We have the following four polar decompositions:
U
11
D
0
B
B
@
0 0 0 1
0 0 0 0
0 0 0 0
0 0 0 0
1
C
C
A
D
0
B
B
@
1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
1
C
C
A
0
B
B
@
0 0 0 1
x
1
0 0 0
0 x
2
0 0
0 0 x
3
0
1
C
C
A
;
U
12
D
0
B
B
@
0 0 0 0
0 0 0 1
0 0 1 0
0 1 0 0
1
C
C
A
D
0
B
B
@
0 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
1
C
C
A
0
B
B
@
y
1
0 0 0
0 0 0 1
0 0 1 0
0 1 0 0
1
C
C
A
;
U
21
D
0
B
B
@
1 0 0 0
0 0 0 0
0 0 1 0
0 1 0 0
1
C
C
A
D
0
B
B
@
1 0 0 0
0 0 0 0
0 0 1 0
0 0 0 1
1
C
C
A
0
B
B
@
1 0 0 0
0 0 0 z
1
0 0 1 0
0 1 0 0
1
C
C
A
; and
U
22
D
0
B
B
@
0 0 0 0
1 0 0 0
0 0 0 0
0 0 0 0
1
C
C
A
D
0
B
B
@
0 0 0 0
0 1 0 0
0 0 0 0
0 0 0 0
1
C
C
A
0
B
B
@
0 w
1
0 0
1 0 0 0
0 0 w
2
0
0 0 0 w
3
1
C
C
A
:
We note that, in each of the four polar decompositions U
jk
D P
jk
V
jk
, a zero eigenvalue of
the positive semidefinite P
jk
is accompanied by a free parameter in the unitary V
jk
. Choos-
ing x
1
D x
2
D x
3
D i, y
1
D i, z
1
D i, and w
1
D i, and applying (4.11), leads to the primal
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.