49
C H A P T E R 3
Bottom-Up
3.1 THE SQUARE ROOT OF THE NOT
In the bottom-up approach, we take the finite group S
n
(with n D 2
w
) and one or more extra
generators fg
1
; g
2
; : : :g. ese generators together with the elements of S
n
generate a new group
G, i.e., the closure of S
n
and fg
1
; g
2
; : : :g. It automatically is a supergroup of S
n
. Below we give
two examples: we add either one (g
1
) or two (g
1
and g
2
) generators and wonder how much
order(G) exceeds order(S
n
) = nŠ.
3.1.1 ONE-(QU)BIT CALCULATIONS
According to Section 1.12, a single qubit is represented by a quantum vector
a
1
a
2
, with a
1
a
1
C
a
2
a
2
D 1. If a
1
D 1 and a
2
D 0, then the input is a classical input bit equal to 0; if a
1
D 0 and
a
2
D 1, then the input is a classical input bit equal to 1. In all other cases, the input is in a
quantum-mechanical superposition of 0 and 1:
a
1
a
2
D a
1
1
0
C a
2
0
1
:
We introduce, besides the matrices I and X of Section 2.1, the 2 2 unitary matrix
V D
1
2
1 C i 1 i
1 i 1 C i
:
It satisfies V
2
D X, with X the NOT gate of Section 2.1:
X D
0 1
1 0
:
us V is the notorious square root of NOT [38–42]:
V V
=
X
:
It plays the role of generator, generating a matrix group of order four with elements
I D
1 0
0 1
; V D
!
; X D
0 1
1 0
; and V
D
!
;
50 3. BOTTOM-UP
where I stands for the IDENTITY gate, where is the complex number given by
D
1
2
C i
1
2
;
and is its complex conjugate:
D
1
2
i
1
2
:
e matrix V
obeys
V
2
D X and thus is the “other” square root of NOT. Together, the four ma-
trices form a group with respect to the operation of ordinary matrix multiplication, isomorphic
to the cyclic group of order 4, i.e., to C
4
(Section 1.5). Indeed, we have V
1
D V, V
2
D X, V
3
D V
,
and V
4
D I. We thus have found a group X satisfying the desired property (1.15). Indeed we
have
P.2/ C
4
U.2/ ;
with orders
2 < 4 < 1
4
:
Any of the four matrices transforms the input state
a
1
a
2
into an output state
p
1
p
2
:
p
1
p
2
D
U
11
U
12
U
21
U
22
a
1
a
2
:
Because the matrix U is unitary, a
1
a
1
C a
2
a
2
D 1 automatically yields p
1
p
1
C p
2
p
2
D 1. If the
input is in a classical state (either .a
1
; a
2
/ D .1; 0/ or .a
1
; a
2
/ D .0; 1/), then the output is in a
quantum superposition. For example,
p
1
p
2
D
!
1
0
D
: (3.1)
But, as the output of one circuit may be the input of a subsequent circuit, we have to consider
the possibility of .a
1
; a
2
/ being in such a superposition. In fact, we have to consider all possible
values of .a
1
; a
2
/ and .p
1
; p
2
/, which may be transformed into one another. ese values turn
out to be either a column or a row of one of the four matrices. us, in total, four and only four
states have to be considered: .1; 0/, .0; 1/, .; /, and .; /. Such an object, which may be in four
different states, is intermediate to a bit (which can be in only two different states) and a qubit
(which may be in as many as 1
3
different states).
Table 3.1 displays how each of the four matrices acts on the column vector .a
1
a
2
/
T
. e
tables constitute the truth tables of the four reversible transformations. Each of these tables
expresses a permutation of the four objects .1; 0/, .0; 1/, .; /, and .; /. e four tables replace
the two tables in Table 2.1 of Chapter 2. Together they form a permutation group which is a
subgroup of the symmetric group S
4
. And indeed we have C
4
S
4
.
..................Content has been hidden....................

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