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

3.2. QUANTUM COMPUTING MODELS
Quantum TMs and other Automata. Deutsch [56] gave the first formal
description of a quantum computer, known as a quantum TM. The tape
contents of the TM are qubits. Quantum configurations of the QTM are
superpositions of (classical) TM configurations. A transition of the QTM is
a unitary mapping on quantum configurations of the QTM. Thus, a
computation of the QTM is a unitary mapping from the initial quantum
configuration to the final quantum configuration. Various papers general-
ize machines and automata to the quantum case. Moore, Crutchfield [57]
propose quantum finite-state and push-down automata, and regular and
context-free grammars; they generalize several formal language and auto-
mata theorems, e.g., pumping lemmas, closure properties, rational and
algebraic generating functions, and Greibach normal form. Kondacs and
Watrous [58] partially characterize the power of quantum finite state
automata. Dunlavey [59] gives a space efficient simulation of a determi-
nistic finite state machine (FSM) on a quantum computer (using Grover's
search algorithm discussed below). Watrous [60] investigates quantum
cellular automata and Du¨ rr et al. [61, 62] give decision procedures for
unitary linear (one dimensional) quantum cellular automata.
Quantum Gates. A set of Boolean gates are universal if any Boolean
operation on arbitrarily many bits can be expressed as compositions of
these gates. Toffoli [5] defined an extended XOR 3-bit gate (which is an
XOR gate condition on one of the inputs and is known as the Toffoli gate)
and showed that this gate, in combination with certain 1-bit gates, is
universal. A set of quantum qubit gates are universal for Boolean
computations for QC if any unitary operation on arbitrarily many qubits
can be expressed as compositions of these gates. Deutsch defined the
extended quantum XOR 3-qubit gate (known as the Deutsch-Toffoli gate)
and proved this gate, in combination with certain one qubit gates, is
universal. Barenco [63], Sleator et al. [64], Barenco et al. [65], and
DiVincenzo [66] proved the 2-qubit XOR gates with certain 1-qubit gates
can implement the Deutsch-Toffoli gate, so are universal for QC (also see
Smolin and DiVincenzo [67], DiVincenzo et al. [68], Poyatos et al. [69], and
Mozyrsky et al. [70, 71]). Lloyd [72] then proved that almost any
2-qubit quantum logic gate (with certain 1-qubit gates) is universal for
QC. Monroe et al. [73], DiVincenz et al. [74] gave experimental demonstra-
tions of quantum gates [75]. Defined a quantum computing model known
as a quantum gate array, which allows execution of a (possibly cyclic)
sequence of quantum gates, each input is a qubit, and each gate computes a
unitary transformation.
Quantum Circuits. Yao [76] restricted the concept to (acyclic) quantum
circuits, which are a generalization of Boolean logic circuits for quantum
gates. It suffices that a quantum circuit use only these universal gates. Yao
[76] proved that QTM computations are equivalent to uniform quantum