Quantum computation and complexity theory II

K. Svozil
Institut für Theoretische Physik
University of Technology Vienna
Wiedner Hauptstraß e 8-10/136
A-1040 Vienna, Austria
e-mail: svozil@tph.tuwien.ac.at

Abstract

Contents

1  Elements of quantum computability and complexity theory

``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 non-computable 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.''

`` ¼ 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.

·

Input, output, program and memory are qbits; the elements of the basis { \mid \000 ñ,\mid \111 ñ} represent the classical bit values \000 and \111, respectively;

·

any computation (step) can be represented by a unitary transformation of the computer as a whole;

·

quantum measurements of the basis states \mid \000 ñ and \mid \111 ñ may be carried out on any qbit at any stage of the computation;

·

because of the unitarity of the quantum evolution operator, any computation is reversible; Therefore, a deterministic computation can be performed by a quantum computer if and only if it is reversible, i.e., if the program does not involve ``deletion'' or ``erasure'' of information (cf. [6]);

·

the output of a quantum computation is representable by qbits and therefore needs not be classical. If a classical decision problem requires classical information, then a measurement of the probability to find the solution in the classical states \mid \000 ñ and \mid \111 ñ should be made. After the measurement, the computer is in a classical bit state. If the output qbit is in a coherent superposition between the classical bit states, then the result is nondeterministic. That is, the quantum computation's solution to the classical decision problem may yield the classical bit values 0 and 1 at random (thereby avoiding inconsistency; see below). Such a measurement usually is irreversible.

2  Universal 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 2-state observables

[^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 infinite-dimensional Hilbert space \frak H_{\frak U} spanned by the simultaneous eigenvectors

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

Let [^U] be the linear unitary evolution operator corresponding to \frak U. The dynamics is discrete; i.e., in time steps T

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

2.1  Universal quantum networks

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.¹

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 Mach-Zehnder interferometer.

The elementary quantum interference device T₂₁^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²

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

1

0

) and

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

0

1

) and R(w) = sinw, T(w) = cosw, then the corresponding unitary evolution matrix which transforms any coherent superposition of \mid 0ñ and \mid 1ñ into a superposition of \mid 0¢ñ and \mid 1¢ñ is given by

The elementary quantum interference device T₂₁^MZ depicted in Fig. (1.b) is a (rotated) Mach-Zehnder 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¢ñ º (

1

0

) and

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

0

1

), then the corresponding unitary evolution matrix which transforms any coherent superposition of \mid 0ñ and \mid 1ñ into a superposition of \mid 0¢ñ and \mid 1¢ñ is given by

The correspondence between T₂₁^bs (T(w),a,b,j) with T₂₁^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¢ = b-w, a¢ = a-p/2, b¢ = b- w and j¢ = j-p/2; i.e.,

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 one-to-one correspondence to T^bs₂₁ and T^MZ₂₁; 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]

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

The ``not'' element is defined by \mid \000 ñ® \mid \111 ñ, \mid \111 ñ® \mid \000 ñ and can be realized by

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

Ö{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 n-dimensional unitary matrix U can be composed from elementary unitary transformations in twodimensional subspaces of \Bbb Cⁿ. This is usually shown in the context of parametrization of the n-dimensional unitary groups (cf. [10], chapter 2 and [11,12]). The number elementary transformations is polynomially bounded and does not exceed

(

n

2

) = [(n (n-1))/ 2] = O(n²). M. Reck has created a program generating the array of beam splitters and phase shifters corresponding to an arbitrary N-dimensional unitary matrix [13].³ For example, the 10-dimensional matrix

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].

3  Quantum recursion theory

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ñ º (

1

0

) and

\mid 1ñ º (

0

1

) (t₁ stands for the Pauli spin operator),

[^D] will be called diagonalization operator, despite the fact that the only nonvanishing components are off-diagonal.

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

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.,

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.

4  Quantum complexity theory

4.1  Factoring

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]

The unitary operator [^A]_g is used as an (polynomial-time) ``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₂ n) places, the dimension of the unitary matrix grows exponentially with N; more specifically, q = O(n²) = O(2^2N).

4.2  Travelling salesman

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 n-1 slit layers (for cities number 2,3,¼,n) for quantum interference. Each one of the layers has n-1 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 (n-1)^n-1 possible classical trajectories for any single classical particle. This means that in order to exhaust all trajectories, one needs (n-1)^n-1 classical paricles. But quanta are no classical entities. By the coherent superposition of trajectories, every quantum has a nonvanishing amplitude to pass all the (n-1)^n-1 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 non-polynomial increase in energy. (This might be exactly the case for classical analog devices.)

4.3  Will the strong Church-Turing thesis survive?

The strong Church-Turing thesis postulates that the class of polynomial-time algorithms is robust; i.e., invariant with respect to variations of ``reasonable'' models of computation. Quantum complexity theory challenges this claim.⁴

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 one-photon 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|²+|b|² = 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

More generally, any one of the entangled qbits originating from the branching process can be processed in parallel. The beam path s₀s_1i1s_2i2s_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₁,p₂,¼,p_q} with length l₁ £ l₂ £ ¼ £ l_q satisfies the Kraft inequality

l₁ = l₂ = ¼ = l_q. The more general case l₁ £ l₂ £ ¼ £ l_q can be easily realized by allowing beams not to pass all k n-slit 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

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 no-cloning 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.

Acknowledgements

A final koan: Is the question, ``where is a rainbow?'' a category mistake?

Appendices

A  Fundamental constants of physics and their relations

A.1  Fundamental constants of physics

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²/(^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_ee² = 0.529 Å = 5×10^-11 m (Bohr radius)
m_Bohr = e(^h/_2p) /2m_ec = 5.788×10^-9 eV gauss^-1

A.2  Conversion tables

A.3  Electromagnetic radiation and other wave phenomena

B  Mathematica code for elementary quantum interference device

Beam splitter

 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]]]]

Mach-Zehnder

 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]];

C  Recommended reading

History of quantum mechanics

Hilbert space quantum mechanics

From single to multiple quanta - ``second'' field quantization

Quantum interference

Copying and cloning of qbits

Context dependence of qbits

Classical versus quantum tautologies

Quantum computation

Universal quantum computers

Universal quantum networks

Quantum recursion theory

Factoring

References

[1]

A. M. Turing, Proc. London Math. Soc. (2), 42, 230 (1936-7), reprinted in [2].

[2]

M. Davis, The Undecidable (Raven Press, New York, 1965).

[3]

D. Deutsch, Proc. R. Soc. Lond. A 400, 97 (1985).

[4]

R. Rosen, Effective Processes and Natural Law, in The Universal Turing Machine. A Half-Century Survey, ed. by R. Herken (Kammerer & Unverzagt, Hamburg, 1988), p. 523.

[5]

M. Davis, Computability & Unsolvability (McGraw-Hill, New York, 1958).

[6]

R. Landauer, Physics Today 44, 23 (Mai 1991).

[7]

P. Benioff, J. Stat. Phys. 29, 515 (1982); Phys. Rev. Lett. 48, 1581 (1982).

[8]

B. Yurke, S. L. McCall and J. R. Clauder, Phys. Rev. A 33, 4033 (1986).

[9]

R. A. Campos, B. E. A. Saleh and M. C. Teich, Phys. Rev. A 42, 4127 (1990).

[10]

F. D. Murnaghan, The Unitary and Rotation Groups (Spartan Books, Washington, 1962).

[11]

M. Reck, A. Zeilinger, H. J. Bernstein and P. Bertani, Phys. Rev. Lett. 73, 58 (1994).

[12]

M. Reck and A. Zeilinger, Quantum phase tracing of correlated photons in optical multiports, in Quantum Interferometry, ed. by F. De Martini, G. Denardo and A. Zeilinger (World Scientific, Singapore, 1994).

[13]

M. Reck, Unitary operators as multiport interferometers, University of Innsbruck preprint and Mathematica program, November 1994.

[14]

R. P. Feynman, Opt. News 11, 11 (1985).

[15]

H. Rogers, Theory of Recursive Functions and Effective Computability (MacGraw-Hill, New York 1967).

[16]

P. Odifreddi, Classical Recursion Theory (North-Holland, Amsterdam, 1989).

[17]

K. Svozil, The consistent use of paradoxa, TU Vienna preprint, May 1994.

[18]

R. P. Feynman, International Journal of Theoretical Physics 21, 467 (1982).

[19]

K. Svozil, Randomness and Undecidability in Physics (World Scientific, Singapore, 1993).

[20]

D. Deutsch and R. Jozsa, Proc. R. Soc. Lond. A 439, 553 (1992).

[21]

D. Deutsch, June 1992 issue of Physics World.

[22]

E. Bernstein and U. Vazirani, Quantum complexity theory, in Prpc. 25th ACM Symp. on Theory of Computation, p. 11 (1993).

[23]

A. Berthiaume and G. Brassard, The quantum challenge to structural complexity theory, in Proc. 7th IEEE Conf. on Structure in Complexity Theory, p. 132 (1992).

[24]

Ch. Bennett, Nature 362, 694 (1993).

[25]

V. erný, Phys. Rev. A 48, 116 (1993).

[26]

P. W. Shor, Algorithms for quantum computation: discrete logarithms and factoring, in Proc. 35th Annual Symposium of on Foundations of Computer Science (IEEE Press, November 1994), in press.

[27]

D. Coppersmith, An approximate Fourier transform useful in quantum factoring IBM research report RC 19642, 1994.

[28]

R. W. Hamming, Coding and Information Theory, Second Edition (Prentice-Hall, Englewood Cliffs, New Jersey, 1980).

[29]

G. J. Chaitin, Information, Randomness and Incompleteness, Second edition (World Scientific, Singapore, 1987, 1990); Algorithmic Information Theory (Cambridge University Press, Cambridge, 1987); Information-Theoretic Incompleteness (World Scientific, Singapore, 1992).

[30]

C. Calude, Information and Randomness - An Algorithmic Perspective (Springer, Berlin, 1994).

[31]

P. W. Milonni and M. L. Hardies, Phys. Lett. 92A, 321 (1982).

[32]

L. Mandel, Nature 304, 188 (1983).

[33]

R. J. Glauber, Quantum Theory of Coherence, in Quantum Optics: Proceedings of the Scottish Universities' Summer School in Physics, 1969 , ed. by S. M. Kay and A. Maitland (Academic Press, London, 1970).

[34]

C. M. Caves, Phys. Rev. D 26, 1817 (1982).

[35]

M. Jammer, The Philosophy of Quantum Mechanics (John Wiley, New York, 1974).

[36]

J. A. Wheeler and W. H. Zurek, eds.,

Quantum Theory and Measurement (Princeton University Press, Princeton, 1983).

[37]

R. P. Feynman, R. B. Leighton and M. Sands, The Feynman Lectures on Physics, Vol. III, Quantum Mechanics (Addison-Wesley, Reading, 1965).

[38]

E. G. Harris, A Pedestrian Approach to Quantum Field Theory (Wiley-Interscience, New York, 1971).

[39]

H. J. Lipkin, Quantum Mechanics, New Approaches to Selected Topics (North-Holland, Amsterdam, 1973).

[40]

L. E. Ballentine, Quantum Mechanics (Prentice Hall, Englewood Cliffs, 1989); for a short expose, see also L. E. Ballentine, Rev. Mod. Phys. 42, 358 (1970).

[41]

A. Messiah, Quantum Mechanics, Volume I (North-Holland, Amsterdam, 1961).

[42]

A. Peres, Quantum Theory: Concepts & Methods (Kluwer Academic Publishers, Dordrecht, 1993).

[43]

J. von Neumann, Mathematische Grundlagen der Quantenmechanik (Springer, Berlin, 1932) [English translation: Mathematical Foundations of Quantum Mechanics (Princeton University Press, Princeton, 1955)].

[44]

J. S. Bell, Speakable and Unspeakable in Quantum Mechanics (Cambridge University Press, Cambridge, 1987).

[45]

J. M. Jauch, The Theory of Photons and Electrons (Addison-Wesley, Cambridge, MA, 1955).

[46]

N. N. Bogoliubov and D. V. Shirkov, Introduction to the Theory of Quantized Fields (Wiley-Interscience, New York, 1959).

[47]

D. Luriè, Particles and Fiels (Interscience Publishers, New York, 1968).

[48]

C. Itzykson and J.-B. Zuber, Quantum Field Theory (MacGraw-Hill, New York, 1980).

[49]

D. B. Greenberger, M. Horne and A. Zeilinger Physics Today 46, 22 (August 1993).

[50]

N. D. Mermin, Rev. Mod. Phys. 65, 803 (1993).

[51]

E. Specker, Selecta (Birkhäuser Verlag, Basel, 1990).

[52]

D. Deutsch, Proc. R. Soc. Lond. A 425, 73 (1989).

Footnotes:

¹ 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.

² Alternatively, the action of a lossless beam splitter may be described by the matrix

(

T(w)	i  R( w)
i R(w)	T( w)

) = (

cosw	i  sinw
i sinw	cosw

). A phase shifter in twodimensional Hilberts space is represented by either

(

eij	0
0	1

) or

(

1	0
0	eij

). The action of the entire device consisting of such elements is calculated by multiplying the matrices in reverse order in which the quanta pass these elements [,].

³ The elementary beam splitter matrix used by Reck is different from ours; it is u(n, f)·diag(q₁,q₂), that is a two-parameter unimodular matrix

u(n,f) = (

sinn	cosn
- eifcosn	eifsinn

) and a matrix diag(q₁,q₂) representing a phase shift at the output ports. In order to reproduce identical results with the universal quantum interference devices defined above, the phases of the physical devices (beam splitter, mirror, phase shifter) corresponding to the parameters

w,a, b, j have to be properly adapted.

⁴ Quantum complexity theory, however, does not challenge the (weak) Church-Turing thesis; i.e., all quantum-computable objects are classically computable.