Quantum computation

The idea of quantum computation goes back to as early as 1982, when Richard Feynman considered simulating quantum-mechanical objects with other quantum systems. However, the unusual power of quantum computation was not really appreciated until 1985 when David Deutsch published a theoretical paper [27] in which he described a universal quantum computer. Then in 1994 Peter Shor devised the first quantum algorithm that, in principle, can perform efficient factorisation [30]. In a sense, Shor's algorithm is a `killer application,' which can do something very useful that is also, it is believed, intractable on conventional computers. In fact, the difficulty of factorising large integers is a working hypothesis on which the security of many common methods of encryption (e.g. RSA) is based. For one thing, RSA is a very popular public key encryption scheme used in many e-commerce applications today. In this section, a brief summary of the quantum computer is presented.

In [27], Deutsch laid down the foundation of quantum computation by considering the Church-Turing conjecture:

Every `function which would naturally be regarded as computable' can be computed by the universal Turing machine.

in physical terms. According to Deutsch, instead of considering the Church-Turing conjecture as a pure mathematical formulation, one should consider the physical version of the Church-Turing principle, which is

`Every finitely realizable physical system can be perfectly simulated by a universal model computing machine operating by finite means.'

Indeed, since classical dynamics is continuous, the possible states of a classical system necessarily form a continuum. But there are only countably many ways of preparing a finite input for a Turing machine. Therefore, a Turing machine cannot perfectly simulate any classical dynamic system. Consequently, the Church-Turing principle does not hold in classical physics. On the other hand, a universal quantum computer is capable of perfectly simulating any finite, realizable physical system.

Specifically, a quantum computer $\cal Q$ consists of two components, a finite processor and an infinite memory. The computation proceeds in steps of fixed duration $T$, and during each step only the processor and a finite part of the memory interact, the rest of the memory remaining static [27].

The processor consists of $M$ 2-state observables

$${\bf\hat n} \equiv \{\hat n_i\}, (i \in \mathbb{Z}_M)$$ (3.21)

where $\mathbb{Z}_m$ is the set of integers from 0 to $M-1$. The memory is an infinite sequence

$${\bf\hat m} \equiv\{\hat m_i\}, (i \in \mathbb{Z})$$ (3.22)

of 2-state observables. This corresponds to the infinitely long memory tape in a Turing machine. One needs another observable $\hat x$ to specify the address number of the currently scanned tape location. Thus the state of $\cal Q$ is a unit vector of the space $\cal H$ spanned by the simultaneous eigenvectors

$$\vert x;{\bf n};{\bf m} \rangle \equiv \vert x;n_0,n_1 \cdots n_{M-1}; \cdots m_{-1},m_0,m_1 \cdots \rangle$$ (3.23)

of $\hat x$, $\bf\hat n$ and $\bf\hat m$, labelled by the corresponding eigenvalues $x$, $\bf n$ and $\bf m$. Usually the spectrum of the 2-state observables is taken as $\mathbb{Z}_2$ (i.e. the set $\{0,1\}$) and is called a qubit. The dynamics of $\cal Q$ is described by a unitary operator $U$ on $\cal H$. During a single computation step, $\cal Q$ is described by

$$\vert\psi (nT) \rangle = U^n\vert\psi (0) \rangle, (n \in \mathbb{Z}^+),$$ (3.24)

with $\vert\psi (t)\rangle \in \cal H$ being the state of the quantum computer at time $t$; $n$ being the ``clock-step.'' The computation starts at $t=0$, when the state of a finite number of $\bf\hat m$ is prepared as the program. In this program, the inputs of the quantum computer and the rest of qubits are set to zero. Thus

$$\left. {\matrix{{\left\vert {\psi (0)} \right\rangle =\sum\n... ...ts_m {\left\vert {\lambda _m} \right\vert^2=1}}\cr }} \right\}$$ (3.25)

where a finite number of the $\lambda_m$ are non-zero. It can be shown that in computing strict functions $\mathbb{Z}\to \mathbb{Z}$, a quantum computer generates the classical recursive functions on account of the correspondence principle between quantum mechanics and classical mechanics.

In the architectures proposed in this thesis, each eigenstate $\vert 0;{\bf0};{\bf m} \rangle$ is associated with a symbol in a particular language. Furthermore, the preparation of the starting state as described in Equation 3.25 is referred to as a representation of a state of affairs. In general, a quantum computer has to have an additional state which is reserved to signal the halt of the computation. However, as far as our language processing applications in this thesis are concerned, we assume that the quantum computer will in any case halt after a sufficiently long sequence of execution (with sufficiently large $n$ in Equation 3.24). Since what we are interested in is the end state of a quantum computer (that is, when the calculation is successfully carried out), $n$ operations are absorbed into one operator with

$$\hat U \equiv U^n.$$

For brevity, $\hat U$ is denoted as $U$ hereafter.