3.2. MORE ROOTS OF NOT 53
• 24 matrices of level 0,
• 2,472 matrices of level 1,
• 73,920 matrices of level 2,
• 1,152,000 matrices of level 3,
• and so on.
As circuits of width 2 form a subgroup of the circuits of width w (where w is any integer
larger than 2), the same conclusion holds for any width larger than 2. Figure 3.1 shows the group
hierarchy. From bottom to top, the respective group orders are:
1 < nŠ < @
0
< 1
n
2
:
For n D 2
w
, Table 3.2 gives some numbers.
Table 3.2: e number of different reversible circuits, as a function of the circuit width w: clas-
sical, classical plus square roots of NOT, and full quantum
Classical
Classical
Plus √NOT
Quantum
1
2
3
4
2
24
40,320
20,922,789,888,000
4
ℵ
0
ℵ
0
ℵ
0
∞
4
∞
16
∞
64
∞
256
3.2 MORE ROOTS OF NOT
Inspired by the fact that the X gate is a square root of the I gate (because X
2
D I) and V is a
square root of X, one can envisage to introduce W, a square root of the V:
W
D
1
4
2 C
p
2 C i
p
2 2
p
2 i
p
2
2
p
2 i
p
2 2 C
p
2 C i
p
2
!
:
(3.4)
We indeed have W
2
D V. e matrix W generates a cyclic group of order 8, consisting of W, W
2
,
…, W
8
, where W
2
D V, W
4
D X, and W
8
D I. In circuits with w bits (w 2), we can introduce
controlled W gates. is results in a group of 2
w
2
w
matrices of order @
0
, supergroup of .2
w
/.
Of course, one can continue this way indefinitely, introducing higher and higher degrees of
roots [46]. Surprising is the fact that (for w 2) all resulting groups have the same order, i.e., @
0
.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.