78 4. TOP
an integer number equal to or greater than 0. For both of our two synthesis strategies, the formula
gives a zero overhead, expressing that both methods are ideally efficient.
4.8 FURTHER SYNTHESIS
For the synthesis of classical reversible circuits, after the primal synthesis (Section 2.3) and the
dual synthesis (Section 2.4), Section 2.6 presented a “refined synthesis.” Is such a third synthesis
method also possible for quantum circuits? Unfortunately, the answer is “no.”
Indeed, for classical computing, a controlled 2 2 matrix can only be either a controlled
IDENTITY gate or a controlled NOT gate. As a controlled IDENTITY gate, in fact, it is performing
no action at all; it can be deleted from any circuit. Hence, for classical computing, a controlled
2 2 matrix is a controlled NOT gate. For quantum computing, a controlled 2 2 gate can be
any of the 1
4
matrices of U(2). erefore, a controlled U(2) gate, acting on the first qubit, is
represented by a matrix like (2.3), however, with the 2
w1
blocks, either
1 0
0 1
or
0 1
1 0
replaced by blocks from U(2). For w D 3, this looks like
0
B
B
B
B
B
B
B
B
B
B
B
@
a
1
b
1
a
2
b
2
a
3
b
3
a
4
b
4
c
1
d
1
c
2
d
2
c
3
d
3
c
4
d
4
1
C
C
C
C
C
C
C
C
C
C
C
A
; (4.14)
where each block
a
j
b
j
c
j
d
j
is some U(2) matrix. Hence, each controlled U(2) has 2
w1
times
four degrees of freedom, thus 2
wC1
degrees of freedom. A cascade of 2w 1 controlled U(2)
gates thus has a total of .2w 1/2
wC1
parameters. With n D 2
w
, this means 2nŒ2 log
2
.n/ 1
degrees of freedom, i.e., too few to synthesize an arbitrary member of the n
2
-dimensional group
U(n).
We thus can conclude that a “refined synthesis” method is impossible for quantum com-
puting. Fortunately, such a method is not necessary, as both the “primal synthesis” method and
the “dual synthesis” method are already optimal in the quantum case.
We finaly remark that, both in quantum circuit (4.5) and in quantum circuit (4.10), we
can change the order of the blocks, as mentioned in Section 2.8 for classical circuits. We also
can vary the order of the quantum wires. And, finally, we can reduce the number of controlling
qubits.
4.9. AN EXTRA DECOMPOSITION 79
4.9 AN EXTRA DECOMPOSITION
We close the present chapter by drawing the hierarchy of the unitary group U(n) for even n:
Figure 4.2. We note the extra subgroup of U(n), casually introduced in Section 3.6: the group
aZU(n) of n n unitary matrices with upper-left entry equal to unity.
2
In other words, the aZU
matrices are the matrices of form (3.12).
From top to bottom of the graph, we recognize:
• the group U(n) of dimension n
2
,
• the groups XU(n) and aZU(n), both of dimension .n 1/
2
, each other’s Fourier conjugate,
• the groups bXU(n) and bZU(n), both of dimension .n=2/
2
, each other’s Hadamard con-
jugate,
• the groups cXU(n) and ZU(n), both of dimension n 1, each other’s Fourier conjugate,
and
• the group 1(n) of zero dimension.
anks to the groups bXU(n) and bZU(n), we have both the primal bZbXbZ decomposition
(Section 4.2) and the dual bXbZbX decomposition (Section 4.4). anks to the groups XU(n)
and ZU(n), we have the ZXZ decomposition (Section 3.7). It therefore is no surprise that the
groups cXU(n) and aZU(n) also lead to a matrix decomposition. Indeed, we can apply a trick
similar to the one in Section 4.4: we apply the ZXZ decomposition (3.14) not to an arbitrary
matrix U of U(n), but to its conjugate u D F
1
UF :
u D e
i˛
Z
1
XZ
2
:
We insert two F
1
F products and thus find
U D F uF
1
D F e
i˛
Z
1
F
1
F X F
1
F Z
2
F
1
D e
i˛
.FZ
1
F
1
/.FXF
1
/.FZ
2
F
1
/ D e
i˛
C
1
A C
2
;
i.e., a decomposition into a scalar e
i˛
, two matrices (i.e., C
1
and C
2
) from cXU(n) and one
matrix (i.e., A) from aZU(n). Because the proof of the ZXZ decomposition is not constructive,
the CAC decomposition theorem also is not constructive. We have to use numerical methods
to find approximations for the number ˛ and the matrices C
1
, A, and C
2
.
2
Here, the prescript a in the expression aZU has no meaning, in contrast to b in bXU and bZU meaning “block” and c in
cXU meaning “circulant.” It is chosen for the sake of symmetry.
80 4. TOP
U(?)
XU(?)
bXU(?)
cXU(?) ZU(?)
bZU(?)
aZU(?)
1(?)
Figure 4.2: Hierarchy of the Lie groups U(n), XU(n), bXU(n), cXU(n), ZU(n), aZU(n), and
bZU(n) and the finite group 1(n).
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.