10 1. INTRODUCTION
the example C
2
ŠS
2
. Another example of two groups isomorphic to one another will be given
in Section 1.9.
For computations and experiments with (finite) groups, the computer algebra package GAP
is recommended [7].
1.6 REVERSIBLE COMPUTING
e first step in bridging the gap between classical and quantum computation is replacing con-
ventional classical computing by reversible classical computing. Whereas conventional logic
gates are represented by truth tables with an arbitrary number w
i
of input columns and an
arbitrary number w
o
of output columns, reversible logic gates are described by truth tables with
an equal number w of input and output columns. We call w
i
, w
o
, and w the input width, the
output width, and the width of the circuit, respectively.
Besides an equal input and output width, a reversible truth table has the property that
all output rows are different, such that the 2
w
output words are merely a permutation of the
2
w
input words [8–10]. Table 1.6 gives an example of a conventional gate (i.e., the AND gate,
with two input bits A and B and one output bit R), as well as an example of a reversible gate (i.e.,
a TOFFOLI gate, a.k.a. a controlled NOT gate, with three input bits A, B, and C and three output
bits P , Q, and R). We call Table 1.6a (with w
i
D 2 inputs and w
o
D 1 outputs) an irreversible
truth table because knowledge of the output value is not sufficient to recover the input values.
Indeed, if we know that R D 0, this is not sufficient to trace what A and B “have been.” We call
Table 1.6b (with widths w
i
D w
o
D 3) reversible, because knowledge of the output values P ,
Q
, and
R
is sufficient to recover the input values
A
,
B
, and
C
.
e reader may verify that the irreversible AND function is embedded in the reversible
TOFFOLI function, as presetting in Table 1.6b the input C to logic 0 leads to the output R being
equal to A AND B, as is highlighted by boldface. In the general case, any irreversible truth table
can be embedded in a reversible truth table with w D w
i
C w
o
or less bits [11].
Because the eight output words PQR of the reversible truth table are a permutation of the
eight input words, automatically all three functions P.A; B; C /, Q.A; B; C /, and R.A; B; C / are
balanced. eir minimal ESOP expressions are
P D A
Q D B
R D C ˚ AB :
Because the 2
w
output words of a reversible truth table are a permutation of the 2
w
input
words, we have to study in detail the group of the permutations of n objects. We denote this
group by P(n) and recall that it is isomorphic to the symmetric group S
n
of order nŠ.
e next step in the journey from the conventional to the quantum world is replacing the
reversible truth table by a permutation matrix. As all eight output words 0 0 0, 0 0 1, …, and 1 1 0
are merely a permutation of the eight input words 0 0 0, 0 0 1, …, and 1 1 1, Table 1.6b can be
1.6. REVERSIBLE COMPUTING 11
Table 1.6: Truth table of two basic Boolean functions: (a) the AND function, (b) the TOFFOLI
function
AB R
0 0
0 1
1
0
1 1
0
0
0
1
(a)
ABC PQR
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 1
1 1 0
(b)
replaced by an 8 8 permutation matrix, i.e.,
0
B
B
B
B
B
B
B
B
B
B
B
@
1 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 0
1
C
C
C
C
C
C
C
C
C
C
C
A
: (1.6)
An arbitrary classical reversible circuit, acting on w bits, is represented by a permutation
matrix of size 2
w
2
w
. In contrast, a quantum circuit, acting on w qubits, is represented by a
unitary matrix U of size 2
w
2
w
. Both kinds of matrices are depicted by symbols with w input
lines and w output lines:
A
U
P
B
Q
C R :
Invertible square matrices, together with the operation of ordinary matrix multiplication, form
a group. e finite matrix group P(2
w
) consisting solely of permutation matrices is a subgroup
of the continuous group U(2
w
) of unitary matrices. In Chapter 3, we will show a natural means
to enlarge the subgroup to its supergroup, in other words, how to upgrade a classical computer
to a quantum computer.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.