QUANTUM COMPUTING - Bio-Inspired and Nanoscale Integrated Computing - page 68

a Turing Machine) can be transformed to do reversible computations. Bennett's
reversibility construction required extra space to store information to insure
reversibility; Li Vitanyi [6] give tradeoffs between time and space in the resulting
reversible machine. An innovative technique due to Bennett [2, 7] can be used
to make reversible functions bijective, as required for quantum computations.
Given a bijective function f, suppose we can reversibly compute in time T(x)a
bijective function f and it's inverse f 1 using auxiliary registers for storage of the
input. He proves in time O(T(n)) we can also reversibly compute the bijective
mapping, ð x

; 0 ; 0 Þ!ð f ð x Þ; 0 ; 0 Þ , without use of auxiliary registers for storage of

the input.

3.1.2. An Introduction to Quantum Computation
Computations and methods that do not make use of quantum mechanics will be
termed classical. In contrast, quantum computation (QC) applies quantum me-
chanics to do computation. A single molecule (or collection of particles and/or
atoms) may have a number n of degrees of freedom known as qubits. Associated
with each fixed setting X of the n qubits to Boolean values is a basis state denoted
7

.
Quantum mechanics allows for a linear superposition (also termed an
entangled quantum state) of these basis states to exist simultaneously. Each basis
state

a S

7 a S of the superposition is assigned a given complex amplitude a ; this is

denoted a . Unitary transformations are reversible operations on the super-

positions which can be represented by unitary matrices A (e.g., permutation
matrices, rotation matrices, and the matrices of Fourier transforms) where
AA T =I. The sum of the squares of the magnitudes of the amplitudes of all basis
states is 1. This sum remains invariant due to the application of a unitary
transformations. The Hilbert space H n is the set of all possible such linear
superpositions.
QC is a method of computation where various operations can be executed on
these superpositions:

7 a S

unitary operations,and

observation operations, which allow for the (strong) measurement of each
qubit, providing a mapping from the current superposition to a super-
position where the measured qubit is assigned a Boolean value with
probability given by the square of the amplitude of the qubit in its original
superposition.

Elementary unitary operations that suffice for any quantum computation over
qubits (see [8] and [9]) include a conditional form of the conditional XOR
operation , the Boolean operation NOT, and a constant Boolean operation
yielding 0. The time bound for a quantum computations is defined to be the
number of such elementary unitary operations.