5.5. DUAL DECOMPOSITION 89
P
x
.n/ D G Q
z
.n/ G and Q
z
.n/ D G P
x
.n/ G ;
where G is the n n matrix given by (4.4).
5.5 DUAL DECOMPOSITION
Each of the four blocks U
jk
of a permutation matrix U simply consists of lines with:
• either all zeroes or
• zeroes and one 1.
e situation is more complicated for the conjugate matrix u D GUG, as the matrix u is not
a permutation matrix. erefore, its blocks
u
11
, u
12
, u
21
, and u
22
are not f0; 1g matrices. e
block u
11
D
1
2
.U
11
C U
12
C U
21
C U
22
/ of u consists of lines with:
• either zeroes and one 1 or
• zeroes and twice 1=2;
the blocks u
12
D
1
2
.U
11
U
12
C U
21
U
22
/ and u
21
D
1
2
.U
11
C U
12
U
21
U
22
/ consist of
lines with:
• either zeroes or
• zeroes and twice ˙1=2;
the block u
22
D
1
2
.U
11
U
12
U
21
C U
22
/ consists of lines with:
• either zeroes and one ˙1 or
• zeroes and twice ˙1=2.
For the example (5.2), we have the following blocks u
11
, u
12
, u
21
, and u
22
and their polar
decompositions:
u
11
D
1
2
0
B
B
@
1 0 0 1
1 0 0 1
0 0 2 0
0 2 0 0
1
C
C
A
D
1
2
0
B
B
@
1 1 0 0
1 1 0 0
0 0 2 0
0 0 0 2
1
C
C
A
1
2
0
B
B
@
1 C x
1
0 0 1 x
1
1 x
1
0 0 1 C x
1
0 0 2 0
0 2 0 0
1
C
C
A
;
u
12
D
1
2
0
B
B
@
1 0 0 1
1 0 0 1
0 0 0 0
0 0 0 0
1
C
C
A
D
1
2
0
B
B
@
1 1 0 0
1 1 0 0
0 0 0 0
0 0 0 0
1
C
C
A
1
2
0
B
B
@
1 C y
1
0 0 1 y
1
1 C y
1
0 0 1 y
1
0 0 2y
2
0
0 2y
3
0 0
1
C
C
A
;
90 5. TOP-DOWN
u
21
D
1
2
0
B
B
@
1 0 0 1
1 0 0 1
0 0 0 0
0 0 0 0
1
C
C
A
D
1
2
0
B
B
@
1 1 0 0
1 1 0 0
0 0 0 0
0 0 0 0
1
C
C
A
1
2
0
B
B
@
1 z
1
0 0 1 z
1
1 C z
1
0 0 1 C z
1
0 0 2z
2
0
0 2z
3
0 0
1
C
C
A
;
and
u
22
D
1
2
0
B
B
@
1 0 0 1
1 0 0 1
0 0 2 0
0 2 0 0
1
C
C
A
D
1
2
0
B
B
@
1 1 0 0
1 1 0 0
0 0 2 0
0 0 0 2
1
C
C
A
1
2
0
B
B
@
1 w
1
0 0 1 w
1
1 w
1
0 0 1 w
1
0 0 2 0
0 2 0 0
1
C
C
A
:
Again, zero eigenvalues of the positive semidefinite factor are accompanied by degrees of free-
dom in the unitary factor. If x
1
D ˙i, y
1
D x
1
, y
2
D ˙i, y
3
D ˙i, z
1
D x
1
, z
2
D ˙i, and
z
3
D ˙i, then we obtain a dual decomposition with exclusively permutation matrices. Choos-
ing, in particular, x
1
D z
2
D z
3
D i and y
2
D y
3
D i, we find
0
B
B
B
B
B
B
B
B
B
B
B
@
1 0
0 1
1 0
1 0
0 1
1 0
0 1
0 1
1
C
C
C
C
C
C
C
C
C
C
C
A
0
B
B
B
B
B
B
B
B
B
B
B
@
0 0 0 1
1 0 0 0
0 0 1 0
0 1 0 0
1 0 0 0
0 0 0 1
0 0 1 0
0 1 0 0
1
C
C
C
C
C
C
C
C
C
C
C
A
0
B
B
B
B
B
B
B
B
B
B
B
@
0 1
0 1
0 1
1 0
1 0
1 0
1 0
0 1
1
C
C
C
C
C
C
C
C
C
C
C
A
:
In order to prove that a permutation matrix U always can be decomposed into three per-
mutation matrices in the dual way, it would be sufficient to prove that, with the help of (4.13),
we always can construct three matrices
1
2
I C A
0
I A
0
I A
0
I C A
0
;
B
0
C
0
; and
1
2
I C D
0
I D
0
I D
0
I C D
0
5.5. DUAL DECOMPOSITION 91
that are permutation matrices. Unfortunately, such a case is not possible, as is demonstrated by
the example
U D
0
B
B
B
B
B
B
B
B
B
B
B
@
1 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1
1
C
C
C
C
C
C
C
C
C
C
C
A
: (5.3)
Indeed, here we have U
12
D U
21
D 0 and
U
11
D
0
B
B
@
1
1
1
1
1
C
C
A
and U
22
D
0
B
B
@
1
1
1
1
1
C
C
A
:
e resulting matrices u
11
and u
12
have the following polar decompositions:
u
11
D
1
2
0
B
B
@
1 1 0 0
0 1 1 0
1 0 1 0
0 0 0 2
1
C
C
A
D
1
6
0
B
B
@
4 1 1 0
1 4 1 0
1 1 4 0
0 0 0 6
1
C
C
A
1
3
0
B
B
@
2 2 1 0
1 2 2 0
2 1 2 0
0 0 0 3
1
C
C
A
and
u
12
D
1
2
0
B
B
@
1 1 0 0
0 1 1 0
1 0 1 0
0 0 0 0
1
C
C
A
D
1
2
p
3
0
B
B
@
2 1 1 0
1 2 1 0
1 1 2 0
0 0 0 0
1
C
C
A
1
3
0
B
B
@
x C
p
3 x
p
3 x 0
x x C
p
3 x
p
3 0
x
p
3 x x C
p
3 0
0 0 0 3y
1
C
C
A
:
Applying (4.13) results in
B
0
D
1
2
p
3
0
B
B
B
@
p
3 C i
p
3 C i 2i 0
2i
p
3 C i
p
3 C i 0
p
3 C i 2i
p
3 C i 0
0 0 0 2
p
3
1
C
C
C
A
;
92 5. TOP-DOWN
a matrix which is unitary (and, in fact, an XU matrix), but unfortunately not a permutation
matrix. e cause of this problem is the lack of degrees of freedom in W
11
. e above matrix
W
11
is unique because det.u
11
/ D 1=4 and thus is non-zero. A non-zero determinant of u
11
appears whenever u
11
contains exclusively k k cycles G
k
with odd k. Here, G
k
is defined by
G
1
D .1/ and, for k > 1, by
G
k
D
1
2
0
B
B
B
B
B
B
B
@
1 1
1 1
1 1
:
:
:
:
:
:
1 1
1 1
1
C
C
C
C
C
C
C
A
:
Indeed, if k is even, then det.2G
k
/ D 0 and thus the polar decomposition of G
k
is not unique,
but if k is odd, then det.2G
k
/ D 2 and the decomposition is unique. us the conclusion of the
present section is: a dual classical decomposition exists but cannot always be found by means of
the quantum method of Section 4.4. It can be found by the classical method of Section 2.4.
us, whereas the primal decomposition of a permutation matrix according to the quan-
tum algorithm of Section 4.2 always supplies a decomposition into permutation matrices, the
dual decomposition of a permutation matrix according to the quantum algorithm of Section 4.4
does not always supply a decomposition into permutation matrices. If the n n matrix U is a
permutation matrix, then we can always get rid of the two HADAMARD gates in (4.5), but not
always the four HADAMARD gates in (4.10).
..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset