For another discussion of this topic, see R. Rosen [4] and M. Davis' book [5], p. 11, where the following question is asked:``The reason why we find it possible to construct, say, electronic calculators, and indeed why we can perform mental arithmetic, cannot be found in mathematics or logic. The reason is that the laws of physics `happen to' permit the existence of physical models for the operations of arithmetic such as addition, subtraction and multiplication. If they did not, these familiar operations would be noncomputable functions. We might still know of them and invoke them in mathematical proofs (which would presumably be called `non constructive') but we could not perform them.''
Indeed, the concept of Turing degree [1] yields an extension of universal computation to oracle computation. In a way, the syntactic aspect of computation could thus be ``tuned'' to wider concepts of (physically realisable) computation if that turns out to be necessary. As has been pointed out before, such a change cannot be decided by syntactic reasoning; it has to be motivated by physical arguments. Thus, at least at the level of investigation of ``reasonable'' instances of computation, the theory of computable functions, recursion theory, is part of physics.`` ¼ how can we ever exclude the possibility of our presented, some day (perhaps by some extraterrestrial visitors), with a (perhaps extremely complex) device or ``oracle'' that ``computes'' a non computable function?''
The following features are necessary but not sufficient qualities of quantum computers.
In what follows, a Turing machine will be quantized. This means that all entities of the Turing machine will be described in quantum mechanical, i.e., Hilbert space, terminology.
Assume a universal computer \frak U consistsing of a finite processor and an infinite (tape) memory [7,3]. Its state function \mid y_{\frak U}ñ can be represented as follows. Assume further that the processor consists of M 2state observables
 (1) 
 (2) 
 (3) 
[^x],[^[n\vec]],[^[m\vec]], respectively. The Turing machine's state function \mid y_{\frak U}ñ can then be written as a unit vector in the infinitedimensional Hilbert space \frak H_{\frak U} spanned by the simultaneous eigenvectors
 (4) 
The process of computation can be described as follows. Assume that initially, i.e., at time t = 0, the computer is at position x = 0 and has a ``blank'' processor [n\vec] = [0\vec]. The tape's quantum numbers [m\vec] characterize the ``program'' and the ``input'' of \frak U. A quantum computer can be in a coherent superposition of such states
 (5) 
Let [^U] be the linear unitary evolution operator corresponding to \frak U. The dynamics is discrete; i.e., in time steps T
 (6) 
Turing machines operate ``locally;'' i.e., their tape memory can only shift one position at a single computation step. Furthermore, only the x'th bit of the memory tape participates in a single computation step. This can be implemented by

The ``brute force'' method of obtaining a (universal) quantum computer by quantizing the ``hardware'' components of a Turing machine seems to suffer from the same problem as its classical counterpart.  It seems technologically unreasonable to actually construct a universal quantum device with a ``scaled down'' (to nanometer size) model of a Turing machine in mind.^{1}
One of the novel physical features of quantum information theory is the superposition of classical information. We shall therefore consider quantum interference devices such as the beam splitter or the MachZehnder interferometer.
The elementary quantum interference device T_{21}^{bs} depicted in Fig. (1.a) is just a beam splitter followed by a phase shifter in one of the output ports. According to the ``toolbox'' rules of part I of this review, the process can be quantum mechanically described by^{2}

\mid 0 ñ º \mid 0¢ñ º (
 

\mid 1ñ º \mid 1¢ñ º (
 


The elementary quantum interference device T_{21}^{MZ} depicted in Fig. (1.b) is a (rotated) MachZehnder interferometer with two input and output ports and three phase shifters. According to the ``toolbox'' rules, the process can be quantum mechanically described by

\mid 0ñ º \mid 0¢ñ º (
 

\mid 1ñ º \mid 1¢ñ º (
 

 (22) 
The correspondence between T_{21}^{bs} (T(w),a,b,j) with T_{21}^{MZ} (a¢,b¢,w¢,j¢) in equations (13) (22) can be verified by comparing the elements of these matrices. The resulting four equations can be used to eliminate the four unknown parameters w¢ = 2w, b¢ = bw, a¢ = ap/2, b¢ = b w and j¢ = jp/2; i.e.,
 (23) 
Both elementary quantum interference devices are universal in the sense that every unitary quantum evolution operator in twodimensional Hilbert space can be brought into a onetoone correspondence to T^{bs}_{21} and T^{MZ}_{21}; with corresponding values of T,a,b,j or a,w,b,j. This can be easily seen by a similar calculation as before; i.e., by comparing equations (13) (22) with the ``canonical'' form of a unitary matrix, which is the product of a U(1) = e^{i b} and of the unimodular unitary matrix SU(2) [10]
 (24) 
 (25) 
 (26) 
Let us examine the realization of a few primitive logical ``gates'' corresponding to (unitary) unary operations on qbits. The ``identity'' element \Bbb I is defined by \mid \000 ñ® \mid \000 ñ, \mid \111 ñ® \mid \111 ñ and can be realized by
 (27) 
The ``not'' element is defined by \mid \000 ñ® \mid \111 ñ, \mid \111 ñ® \mid \000 ñ and can be realized by
 (28) 
The next element, ``Ö{not}'' is a truly quantum mechanical; i.e., nonclassical, one, since it converts a classical bit into a coherent superposition of \mid \000 ñ and \mid \111 ñ. Ö{not} is defined by \mid \000 ñ® \mid \000 ñ+ \mid \111 ñ, \mid \111 ñ® \mid \000 ñ+ \mid \111 ñ and can be realized by
 (29) 
 (30) 
Ö{not}¢Ö{not}¢ = not.
It is very important that the elementary quantum interference device realizes an arbitrary quantum time evolution of a twodimensional system. The performance of the quantum interference device is determined by four parameters, corresponding to the phases a,b,j, w.
Any ndimensional unitary matrix U can be composed from elementary unitary transformations in twodimensional subspaces of \Bbb C^{n}. This is usually shown in the context of parametrization of the ndimensional unitary groups (cf. [10], chapter 2 and [11,12]). The number elementary transformations is polynomially bounded and does not exceed
(
 

 (31) 
Thus a suitable arrangement of elementary quantum interference devices  representing unitary transformations on twodimensional subspaces of the computational basis states [cf. equation (4)]  forms a universal quantum network [14,3].
This section deals mainly with Cantor's method of diagonalization, which is applied for undecidability proofs in recursion theory [15,16]. Due to the possibility of a coherent superposition of classical bit states, the usual reductio ad absurdum argument breaks down. Instead, diagonalization procedures in quantum information theory yield qbit solutions which are fixed points of the associated unitary operators.
I shall demonstrate the emergence of fixed points by a simple example. Diagonalization effectively transforms the classical bit value ``\000'' into value ``\111'' and ``\111'' into ``\000.'' The evolution representing diagonalization can be expressed by the unitary operator
[^D] as follows
[^D] \000ñ® \111 ñ, and [^D] \111ñ® \000 ñ. In the state basis
\mid 0ñ º (
 

\mid 1ñ º (
 

 (32) 
[^D] will be called diagonalization operator, despite the fact that the only nonvanishing components are offdiagonal.
As has been pointed out earlier, quantum information theory allows a coherent superposition \mid a,bñ = a \mid \000 ñ+b \mid \111 ñ of the classical bit states. Therefore,
[^D] has a fixed point at
 (33) 
Classical undecidability is recovered if one performs any irreversible measurement on the fixed point state. This causes a state reduction into the classical states \mid \000 ñ and \mid \111 ñ. The probability for the fixed point state [1/( Ö2)],[1/( Ö2)] ñ to be in either \000 ñ or \111 ñ is equal; i.e.,
 (34) 
However, no contradiction is involved in the diagonalization argument. Therefore, standard proofs of the recursive unsolvability of the halting problem do not apply to quantum recursion theory.
Another, less abstract, application for quantum information theory is the handling of inconsistent information in databases. Thereby, two contradicting cbits of information añ and bñ are resolved by the qbit
[1/( Ö2)],[1/( Ö2)] ñ = [1/( Ö2)](añ+ bñ). Throughout the rest of the computation the coherence is maintained. After the processing, the result is obtained by an irreversible measurement. The processing of qbits requires an exponential space overhead on classical computers in cbit base [18]. Thus, in order to remain tractable, the corresponding qbits should be implemented on truly quantum universal computers.
One decisive feature of quantum computation is parallelism. During a cycle of computation, a quantum computer proceeds down all coherent paths at once. It should be mentioned that quantum parallelism is a quite different feature from quantum stochasticity. Quantum mechanics has an ideal ``build in'' randum number generator [19] which can be used by stochastic algorithms. The crucial question is: what can we do with quantum parallelism what we cannot do with classical devices [20,21,22,23,24,25,26]?
A recent proposal by Shor [26] seems to indicate that the high expectations raised by quantum computing are justified. Shor's claim is that quantum factoring and discrete logarithms can be performed in a time which is polynomially (in the number of digits of the input number) bounded on quantum computers. At the heart of Shor's algorithm is a Fourier transformation [27]
 (35) 
The unitary operator [^A]_{g} is used as an (polynomialtime) ``oracle'' for the computation of the order of an element x in the multiplicative group (mod n); i.e., the least integer r such that x^{r} º 1 (mod x). There is a randomized reduction from factoring to the order of an element.
Notice that, in order to factorize a binary integer n with N = O(log_{2} n) places, the dimension of the unitary matrix grows exponentially with N; more specifically, q = O(n^{2}) = O(2^{2N}).
Almost unnoticed by the quantum computing community, erný has put forward a scheme for the solution of the travelling salesman problem [25]. Assume that the number of cities is n. erný's quantum computer consists of a series of n1 slit layers (for cities number 2,3,¼,n) for quantum interference. Each one of the layers has n1 slits (for cities number 2,3,¼,n). The array of slits is irradiated by a beam of quanta (e.g., light, neutrons, electrons). There are (n1)^{n1} possible classical trajectories for any single classical particle. This means that in order to exhaust all trajectories, one needs (n1)^{n1} classical paricles. But quanta are no classical entities. By the coherent superposition of trajectories, every quantum has a nonvanishing amplitude to pass all the (n1)^{n1} trajectories in polynomial time O(n). Stated pointedly, the quantum ``experiences'' exponentially many paths in polynomial time. One may therefore hope to be able to detect the shortest path by a ``suitable'' measurement of the corresponding observable of the quantum.
Now, what can we make from that? At first glance it surely sounds like a ``cheap lunch!'' But erný clearly states that the price is high indeed as far as statistics is concerned: in order to obtain results with reasonable probabilities, one has to dedicate of the order of N! quanta to the task, resulting in a nonpolynomial increase in energy. (This might be exactly the case for classical analog devices.)
The strong ChurchTuring thesis postulates that the class of polynomialtime algorithms is robust; i.e., invariant with respect to variations of ``reasonable'' models of computation. Quantum complexity theory challenges this claim.^{4}
At the heart of the speedup is quantum parallelism. Roughly stated, quantum parallelism assures that a single quantum bit, henceforth called qbit, can ``branch off'' into an arbitrary number of coherent states. A typical physical realization of a qbit is a single field mode of a photon (electron, neutron), with the empty and the onephoton state \mid \000 ñ and \mid \111 ñ representing the classical symbols \000 and \111, respectively. The qbit is representable by a\mid \000 ñ+b\mid \111 ñ with a^{2}+b^{2} = 1. The branching process into coherent beam paths can be realized by an array of beam splitters such as semitransparent mirrors or a double slit. A typical cascade of branching process into n^{k} coherent beam paths is described by a successive array of k identical beam splitters with n slots and vanishing relative phases

 (40) 
More generally, any one of the entangled qbits originating from the branching process can be processed in parallel. The beam path s_{0}s_{1i1}s_{2i2}s_{3i3}¼s_{kik} can be interpreted as a program code [28,29,30,19]. How many programs can be coded into one beam path? Notice that, in order to maintain coherence, no code of a valid program can be the prefix of a code of another valid program. Therefeore, in order to maintain the parallel quality of quantum computation, only prefix or instantaneous codes are allowed. A straightforward proof using induction [28] shows that the instantaneous code of q programs {p_{1},p_{2},¼,p_{q}} with length l_{1} £ l_{2} £ ¼ £ l_{q} satisfies the Kraft inequality
 (41) 
l_{1} = l_{2} = ¼ = l_{q}. The more general case l_{1} £ l_{2} £ ¼ £ l_{q} can be easily realized by allowing beams not to pass all k nslit arrays.
By recalling equation (40), it is easy to compute the probability that a particular program p_{j} of length l_{j} £ k is executed. It is
 (42) 
One possible way to circumvent attenuation would be to amplify the output signals from the beam splitter array. Classically, amplification and copying of bits is no big deal. In quantum mechanics, however, the nocloning theorem [31,32,33,34] does not allow copying of quantum bits. Any attempt to copy qbits would result in the addition of noise (e.g., from spontaneous emmission processes) and, therefore, in errornous computations.
In summary, the price for speedups of computations originating in quantum parallelism is a corresponding attenuation of the computation probability. In order to compensate for an exponential decrease of execution probability, one would have to exponentially increase the number of (bosonic) quanta in the beam paths. This, however, is equivalent to the trivial solution of an arbitrarily complex problem by the introduction of an arbitrary number of classical parallel computers.
We might have to transcend quantum mechanics in order to do better. However, to cite Einstein again, nobody has any idea of how one can find the basis of such a theory.
A final koan: Is the question, ``where is a rainbow?'' a category mistake?
h = 4.136×10^{15} eV sec (Planck's constant)
(^{h}/_{2p}) = h/2p = 6.582×10^{16} eV sec (Planck's constant/2p)
(^{h}/_{2p}) c = 1.973×10^{7} eV m
k_{B} = 8.617×10^{5} eV K^{1} (Boltzmann's constant)
e = 1.602×10^{19} coulomb (elementary electron charge)
a = e^{2}/(^{h}/_{2p}) c = 1/137.036 (fine structure constant)
l_{e} = (^{h}/_{2p}) /m_{e} c = 3.866 ×10^{13} m
a_{¥,Bohr} = (^{h}/_{2p}) /m_{e}e^{2} = 0.529 Å = 5×10^{11} m
(Bohr radius)
m_{Bohr} = e(^{h}/_{2p}) /2m_{e}c = 5.788×10^{9} eV gauss^{1}
type  frequency  energy (×h)  wavelength (c/frequency) 
[sec^{1}]  [eV]  [m]  
electric  
disturbancies (field)  10^{2}  4×10^{13}  3×10^{6} 
radio  5×10^{5}10^{6}  24×10^{9}  63×10^{2} 
FMTV  10^{8}  4×10^{7}  3 
radar  10^{10}  4×10^{5}  3×10^{2} 
light  5×10^{14}10^{15}  24  63×10^{7} 
Xray  10^{18}  4×10^{3}  3×10^{10} 
gradiation  10^{21}  4×10^{6}  3×10^{13} 
cosmic radiation  10^{27}  4×10^{12}  3×10^{19} 
elastic  5×10^{12}  3×10^{3}  10^{9} 
lattice vibrations  (10100 K)  
(phonons)  
Fermi energy  110  
(10^{4}10^{5} K)  
plasma frequency  515  
(10^{4}10^{5} K)  
x=i; x = x/. a > a Exp[I alpha + I*beta ]; x = x/. i > i Exp[I beta]; x = x/. a > (T*e + I*R* d); x = x/. i > (T*d + I*R* e); x = x/. d > d Exp[I varphi]; x = x/. T > Cos[omega]; w = x/. R > Sin[omega]; (* Print[Expand[x]]; *) a22= w/. d > 0; a22= a22/. e > 1; a21= w/. e > 0; a21= a21/. d > 1; x=a; x = x/. a > a Exp[I alpha + I*beta ]; x = x/. i > i Exp[I beta]; x = x/. a > (T*e + I*R* d); x = x/. i > (T*d + I*R* e); x = x/. d > d Exp[I varphi]; x = x/. T > Cos[omega]; w = x/. R > Sin[omega]; (* Print[Expand[x]]; *) a12= w/. d > 0; a12= a12/. e > 1; a11= w/. e > 0; a11= a11/. d > 1; Print["inverse of transition matrix"]; t12=Simplify[{{a11,a12},{a21,a22}}]; Print[t12]; t12i=ComplexExpand[Transpose[Conjugate[ComplexExpand[t12]]]]
x=i; x = x/. a > a Exp[I alpha + I*beta ]; x = x/. i > i Exp[I beta]; x = x/. a > (b + I* c)/Sqrt[2]; x = x/. i > (c + I* b)/Sqrt[2]; x = x/. c > c Exp[I omega]; x = x/. b > (d + I* e)/Sqrt[2]; x = x/. c > (e + I* d)/Sqrt[2]; w = x/. d > d Exp[I varphi]; (* Print[Expand[x]]; *) a22= w/. d > 0; a22= a22/. e > 1; a21= w/. e > 0; a21= a21/. d > 1; x=a; x = x/. a > a Exp[I alpha + I*beta ]; x = x/. i > i Exp[I beta]; x = x/. a > (b + I* c)/Sqrt[2]; x = x/. i > (c + I* b)/Sqrt[2]; x = x/. c > c Exp[I omega]; x = x/. b > (d + I* e)/Sqrt[2]; x = x/. c > (e + I* d)/Sqrt[2]; w = x/. d > d Exp[I varphi]; (* Print[Expand[x]]; *) a12= w/. d > 0; a12= a12/. e > 1; a11= w/. e > 0; a11= a11/. d > 1; Print["inverse of transition matrix"]; t12=Simplify[{{a11,a12},{a21,a22}}]; Print[t12]; t12i=ComplexExpand[Transpose[Conjugate[ComplexExpand[t12]]]]; (* yields Sqrt[not]gate *) y = t12i/. omega > Pi/2; y = y/. alpha > Pi; y = y/. beta > 3Pi/4; y = y/. varphi > 0; Print[Simplify[y]];
Quantum Theory and Measurement (Princeton University Press, Princeton, 1983).
^{1} I would suspect that future historians of science will construct such a device; just as Babbage's calculater has been constructed by staff of the British Museum recently.
^{2} Alternatively, the action of a lossless beam splitter may be described by the matrix
(

 



 


(

 


(

 


^{3} The elementary beam splitter matrix used by Reck is different from ours; it is u(n, f)·diag(q_{1},q_{2}), that is a twoparameter unimodular matrix
u(n,f) = (

 


w,a, b, j have to be properly adapted.
^{4} Quantum complexity theory, however, does not challenge the (weak) ChurchTuring thesis; i.e., all quantumcomputable objects are classically computable.