93
C H A P T E R 6
Conclusion
We summarize the previous chapters:
• In Chapter 2, we presented three synthesis methods for classical reversible circuits, based
on three decompositions of an arbitrary permutation matrix, with increasing efficiency:
– a primal matrix decomposition,
– a dual matrix decomposition, and
– a refined matrix decomposition.
ey lead to three circuits, each composed of exclusively controlled NOT gates. e third
method needs only 2w 1 such gates (w being the width of the circuit, i.e., the number
of processed bits) and therefore is almost optimally efficient.
• In Chapter 3, we replaced controlled NOT gates by controlled NEGATOR gates and controlled
PHASOR gates. is enables us to step from classical computing to quantum computing.
• In Chapter 4, we presented two synthesis methods for quantum circuits, based on two
decompositions of an arbitrary unitary matrix:
– a primal matrix decomposition and
– a dual matrix decomposition.
Both methods are optimally efficient, as they need (besides HADAMARD gates) only .2
w
/
2
gates, i.e., as many as there are degrees of freedom in the unitary matrix.
• In Chapter 5, we demonstrated how
– the primal unitary decomposition of Chapter 4 contains the primal permutation de-
composition of Chapter 2 as a special case, but
– the dual unitary decomposition of Chapter 4 does not contain the dual permutation
decomposition of Chapter 2.
All chapters successfully take advantage of group theory, both of finite groups (classical com-
puting) and Lie groups (quantum computing). e relevant groups follow a definite hierarchy:
in Chapter 3, we have constructed the group graph of Figure 3.3; in Chapter 5, we have con-
structed the group graph of Figure 5.3. Merging both figures gives Figure 6.1. We note that the
94 6. CONCLUSION
symmetry in Figure 6.1 is broken: whereas we have an edge between the vertices bXU(n) and
XU(n), we lack an edge between the vertices bZU(n) and ZU(n). Indeed, XU(n) is a supergroup
of bXU(n), but ZU(n) is not a supergroup of bZU(n).
U(?)
S(?)
1(?)
P(?)
XU(?) ZU(?)
Q(?)
P
x
(?) Q
z
(?)
bXU(?) bZU(?)
Figure 6.1: Hierarchy of the Lie groups U(n), XU(n), ZU(n), bXU(n), and bZU(n) and the
finite groups S(n), P(n), Q(n), P
x
(n), Q
z
(n), and 1(n).
In order to better illustrate the relation between the quantum case (i.e., the unitary-matrix
case) and the classical case (i.e., the permutation-matrix case), we recall here (for even n) two
subgroups of P(n). For this purpose, we consider the n n permutation matrix P as composed
of four n=2 n=2 blocks:
P D
P
11
P
12
P
21
P
22
:
95
e two subgroups are defined as follows:
• the group P
x
(n) consists of the permutation matrices with all four blocks P
11
, P
12
, P
21
,
and P
22
diagonal and
• the group P
z
(n) consists of the permutation matrices with block P
11
equal to the n=2 n=2
unit matrix I .
e group P
x
(n) is already mentioned in Sections 2.2 and 5.4. It equals P(n) bXU(n). e
group P
z
(n) is mentioned in Section 2.2 and equals P(n) bZU(n). From Chapter 2 it is clear
that the closure of P
x
(n) and P
z
(n) equals P(n). Figure 6.2 (fusion of Figures 2.3 and 4.1) shows
the group hierarchy. e graph is symmetric. However, this symmetry is broken when we look at
the group orders: Figure 6.3. Whereas bXU(n) and bZU(n) have the same dimension, P
x
(n) has
lower order than P
z
(n). e reason is as follows. If C is an arbitrary n=2 n=2 unitary matrix,
then automatically
1
2
I C C I C
I C I C C
is also an n n unitary matrix. In contrast, if C is an
arbitrary n=2 n=2 permutation matrix, then
1
2
I C C I C
I C I C C
is not an n n permutation
matrix (except if C D I ).
P(?)
U(?)
P
x
(?)
bXU(?)
P
z
(?)
bZU(?)
1(?)
Figure 6.2: Hierarchy of the Lie groups U(n), bXU(n), and bZU(n) and the finite groups P(n),
P
x
(n), P
z
(n), and 1(n).
e symmetry between bXU(n) and bZU(n) is the reason why the quantum primal and
dual synthesis methods have the same efficiency; the asymmetry between P
x
(n) and P
z
(n) is
the reason why the classical dual synthesis method is more efficient than the classical primal
synthesis method and also the reason why a “refined” method performs even better than the
dual method.
96 6. CONCLUSION
?!
2
?/2
(?/2)!
1
∞
?
2
∞
?
2
/2
∞
?
2
/2
Figure 6.3: Orders of the Lie groups U(n), bXU(n), and bZU(n) and the finite groups P(n),
P
x
(n), P
z
(n), and 1(n).
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.