1.13. BOTTOM-UP VS. TOP-DOWN 21
ey fill a four-dimensional (curved) space. As an example, we mention the 2 2 discrete
Fourier transform, a.k.a. the Hadamard matrix:
H D
1
p
2
1 1
1 1
:
It corresponds with the parameter values D =2, ' D =4, D =2, and D =2.
In (1.11), we see that the order of a direct product of finite groups equals the product of
the orders of the subgroups. We have a similar property for the dimension of continuous groups:
the dimension of a direct product of continuous groups equals the sum of the dimensions of its
subgroups
3
:
dim.G
1
G
2
G
m
/ D dim.G
1
/ C dim.G
2
/ C C dim.G
m
/ :
us, the Lie group U.n
1
/ U.n
2
/ U.n
k
/, subgroup of the Lie group U(n), based on
the partition n D n
1
C n
2
C Cn
k
, has dimension n
2
1
C n
2
2
C Cn
2
k
. For example
0
B
B
@
i 0 0 0
0 1=4 .1 3i /=4 .2 Ci/=4
0 .1 C3i/=4 1=2 .1 C i/=4
0 .2 C i/=4 .1 i/=4 3=4
1
C
C
A
is member of a U(1) U(3) subgroup of U(4). Wherear U(4) is 16-dimensional, U(1) U(3)
has only 1
2
C 3
2
D 10 dimensions.
e finite group P(n) is a subgroup of the Lie group U(n). Table 1.8 gives some orders
of P(n) and U(n), for some values n D 2
w
. We note that any finite group may be considered a
zero-dimensional Lie group. Whereas P(2
w
) describes classical reversible computers [9], U(2
w
)
describes quantum computers [22].
1.13 BOTTOM-UP VS. TOP-DOWN
In the previous section, we introduced the infinite group U(n), as a supergroup of the finite
group P(n):
U.n/ P.n/ ;
3
is is not a great surprise. Indeed, we may write
1
dim.G/
D order.G/ D order.G
1
G
2
G
m
/
D order.G
1
/ order.G
2
/ order.G
m
/
D 1
dim.G
1
/
1
dim.G
2
/
1
dim.G
m
/
D 1
dim.G
1
/Cdim.G
2
/CCdim.G
m
/
and thus
dim.G/ D dim.G
1
/ C dim.G
2
/ C C dim.G
m
/ :
22 1. INTRODUCTION
Table 1.8: e number of different (classical) reversible circuits and the number of different
quantum circuits, as a function of the number w of (qu)bits
Classical Quantum
1
2
3
4
2
24
40,320
20,922,789,888,000
∞
4
∞
16
∞
64
∞
256
with orders
1
n
2
> nŠ :
is relationship is depicted in Figure 1.2. Such graph is either read from top to bottom as “U(n)
is supergroup of P(
n
)” or from bottom to top as “P(
n
) is subgroup of U(
n
).” In the figure, the
group 1(n) is the trivial group consisting of a single matrix, that is, the n n unit matrix. is
group is isomorphic to S
1
and has order 1.
U(?)
P(?)
1(?)
Figure 1.2: Hierarchy of the Lie group U(n) and the finite groups P(n) and 1(n).
As U(n) is huge compared to P(n), in the next chapters we will look for intermediate
groups, simultaneously subgroups of U(n) and supergroups of P(n), thus investigating in detail
the relationship between U(n) and P(n), in other words, between quantum computing and clas-
sical computing. In next chapters, the simple Figure 1.2 will thus be completed with new, that
is, intermediate, groups. We thus look for groups X(n) satisfying
P.n/ X.n/ U.n/ (1.15)
and thus with order satisfying
nŠ < order[X.n/ < 1
n
2
:
1.13. BOTTOM-UP VS. TOP-DOWN 23
In Chapter 3 we will proceed from bottom to top. is means we will, step by step, look for ever
larger supergroups of the small group P(n) until we arrive at U(n). In Chapter 5 we will proceed
from top to bottom. is means we will look for ever smaller subgroups of the large group U(n)
until we arrive at P(n).
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.