Quantum algorithmic information theory

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
www: http://tph.tuwien.ac.at/[  \tilde]svozil

Abstract

1  Information is physical, so is computation

The reasoning in constructive mathematics [,,] and recursion theory, at least insofar as their applicability to worldly things is concerned, makes implicit assumptions about the operationalizability of the entities of discourse. It is this postulated correspondence between practical and theoretical objects, subsumed by the Church-Turing thesis, which confers power to the formal methods. Therefore, any finding in physics concerns the formal sciences; at least insofar as they claim to be applicable in the physical universe. In this sense one might quite justifiably say that the Church-Turing thesis is under permanent physical attack.¹ Conversely, any feature of the (constructive or non-constructive [,,]) formalism should correspond to some physically operationalizable [] property.

Hence, any theory of information, if applicable, has to deal with entities which are operational [,,,,]. In Bridgman's words [],

``the meaning of one's terms are to be found by an analysis of the operations which one performs in applying the term in concrete situations or in verifying the truth of statements or in finding the answers to questions.''

The classical digital computer, at least up to finite resources, seems to be a canonical example for physical information representation and processing. Classical digital computers, however, are designed to behave classically. That is, if functioning correctly, certain of their physical states can be mapped one-to-one onto the set of classical bit states. (This is achieved by appropriately filtering out noise.) The set of instructions implement the classical propositional calculus and so on.

In miniaturizing components, however, one encounters limits to the quasi-classical domain. The alternative is either to stop miniaturization before quantum effects become dominant, or to take the quantum domain seriously. The latter alternative (at least to the author) seems the only progressive one, but it results in a head-on collision with long-held classical properties. Several long-held assumptions about the character of information have to be adapted. Furthermore, the formal computational techniques in manipulating information have to be revised.

This can be rather negatively perceived as a failure of the old models; but I think that we are justified to think of it in very positive terms: Physics, in particular quantum physics, stimulates us to re-consider our conceptions. We could hope that the outcome will be new tools and technologies in computing.

Indeed, right now, we are experiencing an attack on the ``Cook-Karp thesis,'' putting into question the robustness of the notion of tractability or polynomial time complexity class with respect to variations of ``reasonable'' models of computation. In particular, factoring may require polynomial time on quantum computers within ``reasonable statistics'' []. I would suspect that it is wise of mathematicians and computer scientists to keep an eye on new developments in physics, just as we physicists are required to be open for the great advances in the formal sciences.

2  Hilbert space quantum mechanics

In extension of Planck's discretized resonator energy model, Einstein [] proposed a quantization of the electromagnetic field. Every field mode of frequency n could carry a discrete number of light quanta of energy hn per quantum.

The present quantum theory is still a continuum theory in many respects: for infinite systems, there is a continuity of field modes of frequency w. Also the quantum theoretical coefficients characterizing the mixture between orthogonal states, as well as space and time and other coordinates remain continuous - all but one: action. Thus, in the old days, discretization of phase space appeared to be a promising starting point for quantization. In a 1916 article on the structure of physical phase space, Planck emphasized that the quantum hypothesis should not be interpreted at the level of energy quanta but at the level of action quanta, according to the fact that the volume of 2f-dimensional phase space (f degrees of freedom) is a positive integer of h^f [],²

Es bestätigt sich auch hier wieder, daß  die Quantenhypothese nicht auf Energieelemente, sondern auf Wirkungselemente zu gründen ist, entsprechend dem Umstand, daß  das Volumen des Phasenraumes die Dimension von h^f besitzt.

The following is a very brief introduction to quantum mechanics for logicians and computer scientists.³ To avoid a shock from a too early exposure to `exotic' nomenclature prevalent in physics-the Dirac bra-ket notation-the notation of Dunford-Schwartz [] is adopted.⁴

All quantum mechanical entities are represented by objects of Hilbert spaces []. A Hilbert space is a linear vector space \frak H over the field F of complex numbers (with vector addition and scalar multiplication), together with a complex function (·,·), the scalar or inner product, defined on \frak H×\frak H such that (i) (x,x) = 0 if and only if x = 0; (ii) (x,x) ³ 0 for all x Î \frak H; (iii) (x+y,z) = (x,z)+(y,z) for all x,y,z Î \frak H; (iv) (ax,y) = a(x,y) for all x,y Î \frak H, a Î F; (v) (x,y) = [`(y,x)] for all x,y Î \frak H ([`(a)] stands for the complex conjugate of a); (vi) If x_n Î \frak H, n = 1,2,¼, and if lim_n,m®¥ (x_n-x_m,x_n-x_m) = 0, then there exists an x Î \frak H with lim_{n® ¥} (x_n-x,x_n-x) = 0.

The following identifications between physical and theoretical objects are made (a caveat: this is an incomplete list):

(I)

A physical state is represented by a vector of the Hilbert space \frak H . Therefore, if two vectors x,y Î \frak H represent physical states, their vector sum z = x+y Î \frak H represent a physical state as well. This state z is called the coherent superposition of state x and y. Coherent state superpositions will become most important in quantum information theory.

(II)

Observables A are represented by self-adjoint operators A on the Hilbert space \frak H such that (Ax,y) = (x,Ay) for all x,y Î \frak H. (Observables and their corresponding operators are identified.)

In what follows, unless stated differently, only finite dimensional Hilbert spaces are considered.⁵ Then, the vectors corresponding to states can be written as usual vectors in complex Hilbert space. Furthermore, bounded self-adjoint operators are equivalent to bounded Hermitean operators. They can be represented by matrices, and the self-adjoint conjugation is just transposition and complex conjugation of the matrix elements.

Elements b_i,b_j Î \frak H of the set of orthonormal base vectors satisfy (b_i, b_j) = d_ij, where d_ij is the Kronecker delta function. Any state x can be written as a linear combination of the set of orthonormal base vectors {b₁,b₂,¼}, i.e., x = å_{i = 1}^N b_i b_i, where N is the dimension of \frak H and b_i = (b_i,x) Î F. In the Dirac bra-ket notation, unity is given by 1 = å_{i = 1}^N |b_iñáb_i|. Furthermore, any Hermitean operator has a spectral representation A = å_{i = 1}^N a_i P_i, where the P_i's are orthogonal projection operators onto the orthonormal eigenvectors a_i of A (nondegenerate case).

As infinite dimensional examples, take the position operator [\frak x\vec] = [x\vec] = (x₁,x₂,x₃), and the momentum operator [\frak p\vec]_x = [((^h/_2p))/i] [(Ñ)\vec] = [((^h/_2p))/i] ([(¶)/(¶x₁)],[(¶)/(¶x₂)],[(¶)/(¶x₃)]), where (^h/_2p) = [h/(2p)]. The scalar product is given by ([x\vec],[y\vec]) = d³ ([x\vec]-[y\vec]) = d(x₁-y₁)d(x₂-y₂)d(x₃-y₃). The non-relativistic energy operator (Hamiltonian) is H = [[\frak p\vec] [\frak p\vec]/2m]+V(x) = - [((^h/_2p)²)/2m]Ѳ+V(x).

Observables are said to be compatible if they can be defined simultaneously with arbitrary accuracy; i.e., if they are ``independent.'' A criterion for compatibility is the commutator. Two observables A,B are compatible, if their commutator vanishes; i.e., if [A,B] = AB -BA = 0. For example, position and momentum operators⁶ [\frak x,\frak p_x] = \frak x\frak p_x-\frak p_x\frak x = x[((^h/_2p))/i] [(¶)/(¶x)]-[((^h/_2p))/i] [(¶)/(¶x)]x = i (^h/_2p) ¹ 0 and thus do not commute. Therefore, position and momentum of a state cannot be measured simultaneously with arbitrary accuracy. It can be shown that this property gives rise to the Heisenberg uncertainty relations DxDp_x ³ [((^h/_2p))/2], where Dx and Dp_x is given by Dx = Ö{áx²ñ-áxñ²} and Dp_x = Ö{áp_x²ñ-áp_xñ²}, respectively. The expectation value or average value á·ñ is defined in

(V) below.

It has recently been demonstrated that (by an analog embodiment using particle beams) every self-adjoint operator in a finite dimensional Hilbert space can be experimentally realized [].

(III)

The result of any single measurement of the observable A on a state x Î \frak H can only be one of the real eigenvalues of the corresponding Hermitean operator A. If x is in a coherent superposition of eigenstates of A, the particular outcome of any such single measurement is indeterministic; i.e., it cannot be predicted with certainty. As a result of the measurement, the system is in the state which corresponds to the eigenvector a_n of A with the associated real-valued eigenvalue a_n; i.e., Ax = a_n a_n (no summation convention here).

This ``transition'' x® a<sub>n</sub> has given rise to speculations concerning the ``collapse of the wave function (state).'' But, as has been argued recently [], it is possible to reconstruct coherence; i.e., to ``reverse the collapse of the wave function (state)'' if the process of measurement is reversible. After this reconstruction, no information about the measurement must be left, not even in principle. How did Schrödinger, the creator of wave mechanics, perceive the y-function? In his 1935 paper ``Die Gegenwärtige Situation in der Quantenmechanik'' (``The present situation in quantum mechanics'' []), Schrödinger states,⁷

Die y-Funktion als Katalog der Erwartung: ¼ Sie [[die y-Funktion]] ist jetzt das Instrument zur Voraussage der Wahrscheinlichkeit von Maß zahlen. In ihr ist die jeweils erreichte Summe theoretisch begründeter Zukunftserwartung verkörpert, gleichsam wie in einem Katalog niedergelegt. ¼ Bei jeder Messung ist man genötigt, der y-Funktion ( = dem Voraussagenkatalog) eine eigenartige, etwas plötzliche Veränderung zuzuschreiben, die von der gefundenen Maß zahl abhängt und sich nicht vorhersehen läß t; woraus allein schon deutlich ist, daß  diese zweite Art von Veränderung der y-Funktion mit ihrem regelmäß igen Abrollen zwischen zwei Messungen nicht das mindeste zu tun hat. Die abrupte Veränderung durch die Messung ¼ ist der interessanteste Punkt der ganzen Theorie. Es ist genau der Punkt, der den Bruch mit dem naiven Realismus verlangt. Aus diesem Grund kann man die y-Funktion nicht direkt an die Stelle des Modells oder des Realdings setzen. Und zwar nicht etwa weil man einem Realding oder einem Modell nicht abrupte unvorhergesehene Änderungen zumuten dürfte, sondern weil vom realistischen Standpunkt die Beobachtung ein Naturvorgang ist wie jeder andere und nicht per se eine Unterbrechung des regelmäß igen Naturlaufs hervorrufen darf.

It therefore seems not unreasonable to state that, epistemologically, quantum mechanics is more a theory of knowledge of an (intrinsic) observer rather than the platonistic physics ``God knows.'' The wave function, i.e., the state of the physical system in a particular representation (base), is a representation of the observer's knowledge; it is a representation or name or code or index of the information or knowledge the observer has access to.

(IV)

The probability P_y(x) to find a system represented by state x in some state y of an orthonormalized basis is given by P_y(x) = |(x,y) |² .

(V)

The average value or expectation value of an observable A in the state x is given by áAñ_x = å_{i = 1}^N a_i|(x,a_i) |².

(VI)

The dynamical law or equation of motion can be written in the form x (t) = Ux (t₀) , where U^f = U^-1 (``f stands for transposition and complex conjugation) is a linear unitary evolution operator.

The Schrödinger equation i(^h/_2p) [(¶)/(¶t)] y(t) = H y(t) is obtained by identifying U with U = e^-iHt/(h/_2p) , where H is a self-adjoint Hamiltonian (``energy'') operator, by differentiating the equation of motion with respect to the time variable t; i.e., [(¶)/(¶t)] y(t) = - [iH/((^h/_2p))]e^-iHt/(h/_2p)y(t₀ ) = - [iH/((^h/_2p) )] y(t). In terms of the set of orthonormal base vectors { b₁, b₂, ¼}, the Schrödinger equation can be written as i(^h/_2p) [(¶)/(¶t)] ( b_i , y(t) ) = å_jH_ij( b_j, y(t) ). In the case of position base states y(x,t) = ( x, y(t)), the Schrödinger equation takes on the form i(^h/_2p) [(¶)/(¶t)] y(x,t) = H y(x,t) = [[\frak p \frak p/2m]+V(x)]y(x,t) = [- [((^h/_2p)²)/2m]Ѳ+V(x)] y(x,t).

For stationary y_n(t) = e^{-(i/(h/_2p) )E_nt} y_n , the Schrödinger equation can be brought into its time-independent form H y_n = E_n y_n . Here, i(^h/_2p) [(¶)/(¶t)] y_n (t) = E_n  y_n (t) has been used; E_n and y_n stand for the n'th eigenvalue and eigenstate of H, respectively.

Usually, a physical problem is defined by the Hamiltonian H. The problem of finding the physically relevant states reduces to finding a complete set of eigenvalues and eigenstates of H. Most elegant solutions utilize the symmetries of the problem, i.e., of H. There exist two ``canonical'' examples, the 1/r-potential and the harmonic oscillator potential, which can be solved wonderfully by these methods (and they are presented over and over again in standard courses of quantum mechanics), but not many more. (See, for instance, [] for a detailed treatment of various Hamiltonians H.)

For a quantum mechanical treatment of a two-state system, see appendix . For a review of the quantum theory of multiple particles, see appendix .

3  Quantum information theory

Classical information theory (e.g., []) is based on the classical bit as fundamental atom. This classical bit, henceforth called cbit, is in one of two classical states t (often interpreted as ``true'') and f (often interpreted as ``false''). It is customary to code the classical logical states by \ulcorner t\urcorner = 1 and \ulcorner f\urcorner = 0 (\ulcorners\urcorner stands for the code of s). The states can, for instance, be realized by some condenser who is discharged ( º cbit state 0) or charged ( º cbit state 1).

In quantum information theory [,,,,,,], the most elementary unit of information is the quantum bit, henceforth called qbit. Qbits can be physically represented by a coherent superposition of the two orthonormal⁸ states t and f. The qbit states

xa,b = at+bf

(1)

form a continuum, with |a|²+|b|² = 1, a,b Î \BbbC.

3.1  Coding

Notice that, provided that a,b ¹ 0, a qbit is not in a pure classical state. Therefore, any practical determination of the qbit x_a,b amounts to a measurement of the state amplitude of t or f. Any such single measurement will be indeterministic (provided again that a,b ¹ 0). That is, the outcome of a single measurement occurs unpredictably. Yet, according to the rules of quantum mechanics, the probabilities that the qbit x_a,b is measured in states t and f is P_t(x_a,b) = |(x_a,b,t)|² and P_f(x_a,b) = |(x_a,b,f)|² = 1-P_t(_a,b), respectively.

The classical and the quantum mechanical concept of information differ from each other in several aspects. Intuitively and classically, a unit of information is context-free. That is, it is independent of what other information is or might be present. A classical bit remains unchanged, no matter by what methods it is inferred. It obeys classical logic. It can be copied. No doubts can be left.

By contrast, quantum information is contextual [,]. A quantum bit may appear different, depending on the method by which it is inferred. Quantum bits cannot be copied or ``cloned'' [,,,,,]. Classical tautologies are not necessarily satisfied in quantum information theory. Quantum bits obey quantum logic. And, as has been argued before, they are coherent superpositions of classical information.

3.2  Reading the book of Nature-a short glance at the prediction catalog

To quote Landauer [], ``What is measurement? If it is simply information transfer, that is done all the time inside the computer, and can be done with arbitrary little dissipation.'' And, one may add, without destroying coherence.

Indeed, as has been briefly mentioned in (III), there is reason to believe that-at least up to a certain magnitude of complexity-any measurement can be ``undone'' by a proper reconstruction of the wave-function. A necessary condition for this to happen is that all information about the original measurement is lost. In Schrödinger's terms, the prediction catalog (the wave function) can be opened only at one particular page. We may close the prediction catalog before reading this page. Then we can open the prediction catalog at another, complementary, page again. By no way we can open the prediction catalog at one page, read and (irreversible) memorize the page, close it; then open it at another, complementary, page. (Two non-complementary pages which correspond to two co-measurable observables can be read simultaneously.)

Can we then in some sense ``undo'' knowledge from conscious observation? This question relates to a statement by Wheeler [] that ``no elementary phenomenon is a phenomenon until it is a[[n irreversible]] registered (observed) phenomenon.'' Where does this irreversible observation take place? Since the physical laws (with the possible exception of the weak force) are time-reversible, the act of irreversible observation must, according to Wigner [], occur in the consciousness, thereby violating quantum mechanics.

4  Quantum recursion theory

4.1  Reversible computation and deletion of (q)bits

As a prelude to quantum computation, we briefly review classical reversible computation [,,,,]. This type of computation is characterized by a single-valued inverse transition function. In irreversible computations, logical functions are performed which do not have a single-valued inverse, such as AND or OR; i.e., the input cannot be deduced from the output. Also deletion of information or other many (states)-to-one (state) operations are irreversible. Reversible calculation requires every single step to be reversible. Figure [] draws the difference between one-to-one and many-to-one computation. This logical irreversibility is associated with physical irreversibility and requires a minimal heat generation of the computing machine.

It is possible to embed any irreversible computation in an appropriate environment which makes it reversible. For instance, the computing agent could keep the inputs of previous calculations in successive order. It could save all the information it would otherwise throw away. Or, it could leave markers behind to identify its trail, the Hänsel and Gretel strategy described by Landauer []. That, of course, might amount to a tremendous overhead in dynamical memory space (and time) and would merely postpone the problem of throwing away unwanted information. But, as has been pointed out by Bennett [], for classical computations this overhead could be circumvented by making the computer to erase all intermediate results, leaving behind only the desired output and the originally furnished input. Bennett's trick is to do a computation reversible, then copy its output⁹ and then, with one output as input for the reversible computation, run the computation backwards. In order not to consume exceedingly large intermediate storage resources, this strategy could be applied after every single step. The price is a doubling of computation time, since it requires one additional step for the back-computation.¹⁰ Since qbits cannot be copied, the trick does not work for quantum computations.

4.2  Selected features of quantum computation

The following features are important, but not sufficient qualities of quantum computers.

• Input, output, program and memory are represented by qbits.

• Any computation (step) can be represented by a unitary transformation of the computer as a whole.

• Any computation is reversible. Because of the unitarity of the quantum evolution operator, 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" of information or "many-to-one" operations. Only one-to-one operations are allowed. Compared to classical irreversible computation, this may result in a space and time overheads. Furthermore, no öne-to-many" operations are allowed. Thus, unless classical, qbits cannot be copied.

• Unless classical, qbits are context-dependent. That is, their value may depend on the method by which they have been inferred, and on the co-measured qbits.

• Measurements may be carried out on any qbit at any stage of the computation. But, unless classical, a qbit cannot be measured by a single experiment with arbitrary accuracy. The computation process and the measurement have to be repeated in order to obtain sufficient statistics.-Any such single measurement will yield merely a "click" on some counter, from which information about the qbit state must be inferred. Thereby, any single measurement is indeterminate and coherence is destroyed. Therefore, it seems more proper to realize that there is no such operational concept of ä single qbit." Because of complementarity, single qbits cannot be determined precisely. What is henceforth called "determination" or "measurement" of a qbit is, in effect, the observation of a successive number of such qbits, one after the other, from ßimilar" computation processes (same preparation, same evolution). By performing these measurements on ßimilar" qbits, one can "determine" this qbit within an epsilon-neighborhood only. The parameter epsilon depends on the number of successive measurements made.

• Quantum parallelism: during a computation (step), a quantum computer proceeds down all coherent paths at once. If managed properly, this may give rise to speedups.

• Any subroutine must not leave around any qbits beyond it's computed answer, because the computational paths with different residual information can no longer interfere.

In order to appreciate quantum computation, one should make proper use of the above features-quantum parallelism, unerasability of information, non-copying, context-dependence and impossibility to directly measure the atoms of quantum information, the qbits, related to quantum indeterminism.

Thereby, the ``solution'' to a decision problem may yield the classical bit values at random. It may depend on other qbits of information which are inferred. It cannot be arbitrarily copied and, in this sense, is unique.

4.2.1  Copying of quantum bits

Can a non-classical qbit be copied? No! - This answer amazes the classical mind.¹¹ Informally speaking, the reason is that, depending on the strategy, any attempt to copy a coherent superposition of states results either in a state reduction, destroying coherence, or, most important of all, in the addition of noise which manifests itself as the spontaneous excitations of previously nonexisting field modes [,,,,,]. Therefore, qbits can be copied if and only if they are (known to be) classical. Only one-to-one computation processes depicted in Fig. 1a) are allowed.

This can be seen by a short calculation [] which requires the multi-quantum formalism developed in appendix . A physical realization¹² of the qbit state is a two-mode boson field with the identifications

xa,b = af +bt    , (4) f = | 01,12ñ    , (5) t = | 11,02ñ    . (6)

The classical bit states are |0₁,1₂ñ (field mode 1 unfilled, field mode 2 filled with one quantum) and |1₁,0₂ñ (field mode 1 filled with one quantum, field mode 2 unfilled).

An ideal amplifier, denoted by A, should be able to copy a classical bit state; i.e., it should create an identical particle in the same mode

Ai|01,12ñ®Af|01,22ñ    ,      Ai|11,02ñ®Af|21,02ñ    .

(7)

Here, A_i and A_f stand for the initial and the final state of the amplifier.

What about copying a proper qbit; i.e., a coherent superposition of the cbits f = |0₁,1₂ñ and t = |1₁,0₂ñ? According to the quantum evolution law, the corresponding amplification process should be representable by a linear (unitary) operator; thus

Ai(a|01,12ñ+b|11,02ñ)® Af(a|01,22ñ+b|21,02ñ)    .

(8)

Yet, the true copy of that qbit is the state

(xa,b)2 | 01,02ñ = (a a2f +b a1f )2 | 01, 02ñ = [ a2  (a2f)2+ab (a2f a1f +a1f a2f) +b2  (a1f )2 ] | 01,02ñ = [ a2  (a2f)2+2ab a2f a1f +b2  (a1f )2 ] | 01,02ñ = a2 |01,22ñ+2ab|11,12ñ +b2 |21,02ñ    . (9)

By comparing (8) with (9) it can be seen that a reasonable (linear unitary quantum mechanical evolution for an) amplifier which could copy a qbit exists only if the qbit is classical.

A more detailed analysis (cf. [,], in particular [,]) reveals that the copying (amplification) process generates an amplification of the signal but necessarily adds noise at the same time. This noise can be interpreted as spontaneous emission of field quanta (photons) in the process of amplification.

One application of this feature is quantum cryptography [,,]. Thereby, the impossibility to copy qbits is used for a cryptographic communication via quantum channels.

4.2.2  Context dependence of qbits

Assume that in an EPR-type arrangement [] one wants to measure the product

P = mx1mx2my1my2mz1mz2

of the direction of the spin components of each one of the two associated particles 1 and 2 along the x, y and z-axes. Assume that the operators are normalized such that |m_i^j| = 1, i Î { x,y,z}, j Î { 1,2}. One way to determine P is measuring and, based on these measurements, ``counterfactually inferring'' [,] the three ``observables'' m_x¹m_y², m_y¹m_x² and m_z¹m_z². By multiplying them, one obtains +1. Another, alternative, way to determine P is measuring and, based on these measurements, ``counterfactually inferring'' the three ``observables'' m_x¹m_x², m_y¹m_y² and m_z¹m_z². By multiplying them, one obtains -1. In that way, one has obtained either P = 1 or P = -1. Associate with P = 1 the bit state zero 0 and with P = -1 the bit state 1. Then the bit is either in state zero or one, depending on the way or context it was inferred.

This kind of contextuality is deeply rooted in the non-Boolean algebraic structure of quantum propositions. Note also that the above argument relies heavily on ``counterfactual reasoning,'' because, for instance, only two of the six observables m<sub>i</sub><sup>j</sup> can actually be experimentally determined. Here, the term ``counterfactual reasoning'' [,] stands for arguments involving results of incompatible experiments, i.e., experiments which could never be performed simultaneously, since the associated operators do not commute. The results thus have to be inferred rather than measured, and the existence of such ``elements of physical reality'' thus have to be tacitly assumed [].

4.3  Universal quantum computer based on the U(2)-gate

The ``brute force'' method of obtaining a (universal) quantum computer [,,] by quantizing the ``hardware'' components of a Turing machine suffers 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.

We therefore pursue a more fundamental approach [,]. Recall that an arbitrary quantum time evolution in finite-dimensional Hilbert space is given by x (t) = Ux (t₀) , where U is unitary.

It is well known that any n-dimensional unitary matrix U can be composed from elementary unitary transformations in two-dimensional subspaces of \Bbb Cⁿ. This is usually shown in the context of parameterization of the n-dimensional unitary groups (cf. [] and [,]). Thereby, a transformation in n-dimensional spaces is decomposed into transformations in 2-dimensional subspaces. This amounts to a successive array of U(2) elements, which in their entirety forms an arbitrary time evolution U(n) in n-dimensional Hilbert space.

Hence, all quantum processes and computation tasks which can possibly be executed must be representable by unitary transformations. Indeed, unitary transformations of qbits are a necessary and sufficient condition for quantum computing. The group of unitary transformations in arbitrary- but finite-dimensional Hilbert space is a model of universal quantum computer.

Unitary quantum mechanical operations are a natural extension of Turing's ``simple'' classical paper and pencil operations on a sheet of (one-dimensional) paper []. If one wants to extend that notion further, one would have to extend physical theory, in particular quantum theory. However, at the moment, such a further extension (beyond quantum mechanics) seems only a remote possibility.

It remains to be shown that the universal U(2)-gate is physically operationalizable. This is done in appendix in the framework of Mach-Zehnder interferometry. Note that the number of elementary U(2)-transformations is polynomially bounded and does not exceed (

n

2

) = n (n-1)/ 2 = O(n²).

4.4  Other models of universal quantum computation

Deutsch [] has proposed a model of universal computation based on quantum computation networks. Thereby, the states in a 2ⁿ-dimensional Hilbert space are constructed as the product state of n particles in two-dimensional Hilbert space. A set of gates that consists of all U(2) (one-bit) quantum gates and the two-bit exclusive-or gate (that maps Boolean values (x,y) to (x,x Åy)) is universal in the sense that all unitary operations on arbitrarily many bits n (U(2ⁿ)) can be expressed as compositions of these gates [].

This approach should be distinguished from the interferometric approach using U(2)-gates discussed before, which is based on single particle states in 2ⁿ-dimensional Hilbert space. In the product state model, the addition of one particle effectively doubles the dimensionality of the associated Hilbert space. In the interferometric model, this could only be achieved by doubling the number of input and output ports. This could give rise to non-polynomial space overhead. In the case of the product state model, in order to obtain a mixing between different particle states, xor-gates are needed. The interferometric approach does not need xor-gates explicitly.

It has been claimed [,] that certain supposedly NP-hard problems such as factoring can be solved in polynomial time on quantum computers. However, it should be noted that this result faces difficulties. For, it might not be easy to keep the quantum computer in a coherent superposition state over sufficient time and space scales in order to be able to execute tasks which are hard to do classically-the computation may ``decohere,'' reducing the qbits to classical ones []. Furthermore, in order to obtain sufficient statistical data, a ``great'' (non-polynomially bounded) number of single particles may be needed []. We shall not pursue these matters further [,,,,,].

4.5  Nomenclature

4.6  Diagonalization

This is neither the place for a comprehensive review of the diagonalization method [,], nor suffices the author's competence for such an endeavor. Therefore, only a few hallmarks are stated. As already Gödel pointed out in his classical paper on the incompleteness of arithmetic [], the undecidability theorems of formal logic [] (and the theory of recursive functions [,]) are based on semantical paradoxes such as the liar [] or Richard's paradox. A proper translation of the semantic paradoxes results in the diagonalization method. Diagonalization has apparently first been applied by Cantor to demonstrate the non-enumerability of real numbers []. It has also been used by Turing for a proof of the recursive undecidability of the halting problem [].

A brief review of the classical algorithmic argument will be given first. Consider a universal computer C. For the sake of contradiction, consider an arbitrary algorithm B(X) whose input is a string of symbols X. Assume that there exists a ``halting algorithm'' HALT which is able to decide whether B terminates on X or not. The domain of HALT is the set of legal programs. The range of HALT are cbits (classical case) and qbits (quantum mechanical case).

Using HALT(B(X)) we shall construct another deterministic computing agent A, which has as input any effective program B and which proceeds as follows: Upon reading the program B as input, A makes a copy of it. This can be readily achieved, since the program B is presented to A in some encoded form \ulcorner B\urcorner , i.e., as a string of symbols. In the next step, the agent uses the code \ulcorner B\urcorner as input string for B itself; i.e., A forms B(\ulcorner B\urcorner ), henceforth denoted by B(B). The agent now hands B(B) over to its subroutine HALT. Then, A proceeds as follows: if HALT(B(B)) decides that B(B) halts, then the agent A does not halt; this can for instance be realized by an infinite DO-loop; if HALT(B(B)) decides that B(B) does not halt, then A halts.

The agent A will now be confronted with the following paradoxical task: take the own code as input and proceed.

4.6.1  Classical case

Then, whenever A(A) halts, HALT(A(A)) outputs 1 and forces A(A) not to halt. Conversely, whenever A(A) does not halt, then HALT(A(A)) outputs 0 and steers A(A) into the halting mode. In both cases one arrives at a complete contradiction. Classically, this contradiction can only be consistently avoided by assuming the nonexistence of A and, since the only nontrivial feature of A is the use of the peculiar halting algorithm HALT, the impossibility of any such halting algorithm.

4.6.2  Quantum mechanical case

Recall that a quantum computer C evolves according to a unitary operator U such that (t stands for the discrete time parameter) C(t,p_i) = U C(t-1, p_i) = U^t C(0,p_i).

As has been pointed out before, in quantum information theory a qbit may be in a coherent superposition of the two classical states t and f. Due to this 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.

In what follows it will be demonstrated how the task of the agent A can be performed consistently if A is allowed to process quantum information. To be more specific, assume that the output of the hypothetical ``halting algorithm'' is a halting qbit

HALT ( B(X) ) = ha, b    .

(11)

One may think of HALT ( B(X) ) as a universal ``watchdog'' computer C¢ simulating C and containing a dedicated halting bit, which it outputs at every (discrete) time cycle []. Alternatively, it can be assumed that the computer C contains its own halting bit indicating whether it has completed its task or not. Note that the halting qbit h<sub>a, b</sub> can be represented by a normalized<sup>13</sup> vector in two-dimensional complex Hilbert space spanned by the the orthonormal vectors ``t '' and ``f .'' Let the halting state h <sub>1,0</sub> = t (up to factors modulus 1) be the physical realization that the computer has ``halted;'' likewise let h _0,1 = f (up to factors modulus 1) be the physical realization that the computer has not ``halted.'' Note that, since quantum computations are governed by unitary evolution laws which are reversible, the halting state does not imply that the computer does not change as time evolves. It just means that it has set a signal - the halting bit - to indicated that it has finished its task. a and b are complex numbers which are a quantum mechanical measure of the probability amplitude that the computer is in the halting and the non-halting states, respectively. The corresponding halting and non-halting probabilities are |a|² and |a|², respectively.

Initially, i.e., at t = 0, the halting bit is prepared to be a 50:50 mixture of the classical halting and non-halting states t and f; i.e., h_{1/Ö2 , 1/Ö2} . If later C¢ finds that C converges (diverges) on B(X), then the halting bit of C¢ is set to the classical value t (f).

The emergence of fixed points can be demonstrated by a simple example. Agent A's diagonalization task can be formalized as follows. Consider for the moment the action of diagonalization on the cbit states. (Since the qbit states are merely a coherent superposition thereof, the action of diagonalization on qbits is straightforward.) Diagonalization effectively transforms the cbit value t into f and vice versa. Recall that in equation (10), the state t has been identified with the halting state and the state f with the non-halting state. Since the halting state and the non-halting state exclude each other, f,t can be identified with orthonormal basis vectors in a two-dimensional vector space. Thus, the standard basis of Cartesian coordinates can be chosen for a representation of t and f; i.e.,

t º æ ç è 1 0 ö ÷ ø and f º æ ç è 0 1 ö ÷ ø     .

(12)

The evolution representing diagonalization (effectively, agent A's task) can be expressed by the unitary operator D by

D t = f and D f = t    .

(13)

Thus, D acts essentially as a not-gate. In the above state basis, D can be represented as follows:

D = æ ç è 0 1 1 0 ö ÷ ø     .

(14)

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 h_a,b = at+bf of the cbit states t and f. D acts on cbits. It has a fixed point at the qbit state

h* : = h [1/(Ö2)],[1/(Ö2)] = t+f Ö2 º 1 Ö2 æ ç è 1 1 ö ÷ ø     .

(15)

h^* does not give rise to inconsistencies []. If agent A hands over the fixed point state h ^* to the diagonalization operator D, the same state h^* is recovered. Stated differently, as long as the output of the ``halting algorithm'' to input A(A) is h<sup>*</sup>, diagonalization does not change it. Hence, even if the (classically) ``paradoxical'' construction of diagonalization is maintained, quantum theory does not give rise to a paradox, because the quantum range of solutions is larger than the classical one. Therefore, standard proofs of the recursive unsolvability of the halting problem do not apply if agent A is allowed a qbit.

Another, less abstract, application for quantum information theory is the handling of inconsistent information in databases. Thereby, two contradicting cbits of information t and f are resolved by the qbit h^* = (t+f)/ Ö2. 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, however, would require an exponential space overhead on classical computers in cbit base []. Thus, in order to remain tractable, the corresponding qbits should be implemented on truly quantum universal computers.

It should be noted, however, that the fixed point qbit ``solution'' to the above halting problem, as far as problem solving is concerned, is of not much practical help. In particular, if one is interested in the ``classical'' answer whether or not A(A) halts, then one ultimately has to perform an irreversible measurement on the fixed point state. This causes a state reduction into the classical states corresponding to t and f. Any single measurement will yield an indeterministic result. There is a 50:50 chance that the fixed point state will be either in t or f, since P_t(h ^*) = P_f(h^* ) = ¹/₂. Thereby, classical undecidability is recovered. Stated pointedly: With regards to the question of whether or not a computer halts, the ``solution'' h^* is equivalent to the throwing of a fair coin.

Therefore, the advance of quantum recursion theory over classical recursion theory is not so much classical problem solving but the consistent representation of statements which would give rise to classical paradoxes.

4.6.3  Proper quantum diagonalization

Consider the entire range of two-dimensional unitary transformations []

U(2)(w,a,b,j) = e-i b  æ ç è ei a cosw -e-i j sinw ei j sinw e-i a cosw ö ÷ ø     ,

(16)

where -p £ b,w £ p, - [(p)/2] £ a,j £ [(p)/2], to act on the qbit. A typical example of a nonclassical operation on a qbit is the ``square root of not'' gate ( Ö{not}Ö{not} = D)

Ö   not   = 1 2 æ ç è 1+i 1-i 1-i 1+i ö ÷ ø     .

(17)

Not all these unitary transformations have eigenvectors associated with eigenvalues 1 and thus fixed points. Indeed, it is not difficult to see that only unitary transformations of the form

[U(2)(w,a,b,j)]-1  diag(1,eil)  U(2)(w,a,b,j) =        = æ ç ç ç ç è cosw2 + ei l sinw2 [(-1 + ei l)/2]e-i (a+j)   sin(2 w) -1 + ei l 2 ei (a+j)   sin(2 w) ei l cosw2 + sinw2 ö ÷ ÷ ÷ ÷ ø (18)

have fixed points.

Applying nonclassical operations on qbits with no fixed points

D¢ = [U(2)(w,a,b,j)]-1 diag( eim ,eil) U(2)(w,a,b,j) = æ ç ç ç ç ç ç ç ç è ei m cos(w)2 + ei l sin(w)2 e-i ( a+ p ) 2   ( ei l - ei m )  sin(2 w) ei ( a+ p ) 2   ( ei l - ei m )  sin(2 w) ei l cos(w)2 + ei m sin(w)2 ö ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ø (19)

with m,l ¹ np, n Î \Bbb N₀ gives rise to eigenvectors which are not fixed points, but which acquire nonvanishing phases m, l in the generalized diagonalization process.

5  Quantum algorithmic information

Quantum algorithmic information theory can be developed in analogy to algorithmic information theory [,,,]. Before proceeding, though, one decisive strategic decision concerning the physical character of the program has to be made. This amounts to a restriction to purely classical prefix-free programs.

The reason for classical programs, as well as for the requirement of instant decodability, is the desired convergence of the Kraft sum over the exponentially weighted program length å_p exp(|p|logk) £ 1, where |p| stands for the length of p and k is the base of the code (for binary code, k = 2). If arbitrary qbits were allowed as program code, then the Kraft sum would diverge.

Nevertheless, qbits are allowed as output. Since they are objects defined in Hilbert space \frak H, the basic definitions of algorithmic information theory have to be slightly adapted.

The canonical program associated with an object s Î \frak H representable as vector in a Hilbert space \frak H is denoted by s^* and defined by

s* = min C(p) = s  p    .

(20)

I.e., s^* is the first element in the ordered set of all strings that is a program for C to calculate s. The string s^* is thus the code of the smallest-size program which, implemented on a quantum computer, outputs s. (If several binary programs of equal length exist, the one is chosen which comes first in an enumeration using the usual lexicographic order relation ``0 < 1.'')

Let again ``|x |'' of an object encoded as (binary) string stand for the length of that string. The quantum algorithmic information H(s) of an object s Î \frak H representable as vector in a Hilbert space \frak H is defined as the length of the shortest program p which runs on a quantum computer C and generates the output s:

H(s) = |s* | = min C(p) = s  |p|    .

(21)

If no program makes computer C output s, then H(s) = ¥.

The joint quantum algorithmic information H(s,t) of two objects s Î \frak H and t Î \frak H representable as vectors in a Hilbert space \frak H is the length of the smallest-size binary program to calculate s and t simultaneously.

The relative or conditional quantum algorithmic information H(s|t) of s Î \frak H given t Î \Bbb N is the length of the smallest-size binary program to calculate s from a smallest-size program for t:

H(s|t) = min C(p,t* ) = s  |p|    .

(22)

Most features and results of algorithmic information theory hold for quantum algorithmic information as well. In particular, we restrict our attention to universal quantum computers whose quantum algorithmic information content is machine-independent, such that the quantum algorithmic information content of an arbitrary object does not exceed a constant independent of that object. That is, for all objects s Î \frak H and two computers C and C¢ of this class,

|HC-HC¢| = O(1)    .

(23)

Furthermore, let s and t be two objects representable as vectors in Hilbert space. Then (recall that t Î \Bbb N),

H(s,t) = H(t,s)+O(1)    ; (24) H(s|s) = O(1)    ; (25) H(H(s)|s) = O(1)    ; (26) H(s) £ H(s,t)+O(1)    ; (27) H(s|t) £ H(s)+O(1)    ; (28) H(s,t) = H(s)+H(t|s* )+O(1)     (if s* is classical)     ; (29) H(s,t) £ H(s)+H(t)+O(1)     (subadditivity)     ; (30) H(s,s) = H(s)+O(1)    ; (31) H(s,H(s)) = H(s)+O(1)    . (32)

Notice that there exist sets of objects S = {s₁,¼,s_n}, n < ¥ whose algorithmic information content H(S) is arbitrary small compared to the algorithmic information content of some unspecified single elements s_i Î S; i.e.,

H(S) < max si Î S  H(si)    .

(33)

6  Quantum omega

Here, W is generalized to quantum computations.¹⁴

In the orthonormal halting basis { t ,f}, the computer C with classical input p_i can be represented by C(t,p_i) = t (t, C(t,p_i))+f (f,C(t,p_i)).

Recall that initially, i.e., at time t = 0, the halting bit is in a coherent 50:50-superposition; i.e., in terms of the halting basis, C(0,p_i) = ( t+f)/ Ö2 for all p_i Î A^*. This corresponds to the fact that initially it is unknown whether or not the computer halts on p_i. When during the time evolution the computer has completed its task, the halting bit value is switched to t by some internal operation. If the computer never halts, the halting bit value is switched to f by some internal operation. Otherwise it remains in the coherent 50:50-superposition.

Alternatively, the computer could be initially prepared in the non-halting state f . After completion of the task, the halting bit is again switched to the halting state t.

In analogy to the fully classical case [,,,], the quantum halting amplitude¹⁵ W can be defined as a weighted expectation over all computations of C with classical input p_i (|p_i| stands for the length of p_i)

W º å C(pi) Î \frak H  2-|pi|/2 ( t, C(pi) )    .

(34)

Likewise, the halting amplitude for a particular output state s,

U( s ) º å C(pi) = s   2-|pi|/2( t,C(pi) )    .

(35)

For a set of output states S = {s₁ ,s₂ ,s₃ ,¼, s_n} which correspond to mutually orthogonal vectors in Hilbert space,

U( S ) º å C(pi) Î S   2-|pi|/2( t, C(pi) )    .

(36)

Terms corresponding to different programs and states have to be summed up incoherently. Thus, the corresponding probabilities are

|W|2 = å C(pi) Î \frak H  2-|pi||( t, C(pi) ) |2 (37) P(s) º |U(s)|2 = å C(pi) = s  2-|pi||( t, C(pi) ) |2 (38) P(S) º å C(pi) Î S  |U(s)|2 = å C(pi) Î S  2-|pi||( t, C(pi) ) |2    . (39)

The following relations hold,

U( S ) = å si Î S  U(si)    , (40) W = U( \frak H) = å si Î \frak H  U(si)    . (41)

For s Ì S Ì \frak H,

0 £ P(s) £ P(S) £ |W|2 £ 1    .

(42)

Alternatively, the quantum halting probability and the quantum algorithmic information by the quantum algorithmic information content. That is,

P* (s) = 2-|s* | = 2-H(s) (43) P* (S) = å si Î S  P* (s) = å s Î S  2-H(s) (44) P* (\frak H ) = |W* |2 = å n Î \frak H   2-H(n)     . (45)

|W* |2 £ |W|2    , (46) P* (s) £ P (s)    , (47) P* (S) £ P (S)    . (48)

The following relations are either a direct consequence of the definition (43) or follow from the fact that for programs in prefix code, the algorithmic probability is concentrated on the minimal size programs, or alternatively, that there are few minimal programs:

H(s) = -log2 P* (s)    ; (49) H(s) = -log2 P(s)+O(1)    . (50)

Notice again that, because of complementarity, single qbits cannot be determined precisely. They just appear experimentally as some clicks in a counter. What we can effectively do is to observe a successive number of such qbits, one after the other, from ``similar'' computation processes (same preparation, same evolution). By performing these measurements on ``similar'' qbits, one can ``determine'' this qbit within an e-neighborhood only.

For nontrivial choices of the quantum computer C, several remarks are in order. (In what follows, we mention only W, but the comments apply to U as well.) If the program is also coded in qbits, the above sum becomes an integral over continuously many states per code symbol of the programs. In this case, the Kraft sum needs not converge. Just as for the classical analogue it is possible to ``compute'' W as a limit from below by considering in the t'th computing step (time t) all programs of length t which have already halted. (This ``computation'' suffers from a radius of convergence which decreases slower than any recursive function.) The quantum W is complex. |W|² can be interpreted as a measure for the halting probability of C; i.e., the probability that an arbitrary (prefix-free) program halts on C.

Finally, any irreversible measurement of |W|² causes a state collapse. Since C(t,p_i) may not be in a pure state, the series in (34) and (35) will not be uniquely defined even for finite times. Thus the nondeterministic character of W is not only based on classical recursion theoretic arguments [,] but also on the metaphysical assumption that God plays the quantum dice.

Appendices

A  Two-state system

Having set the stage of the quantum formalism, an elementary two-dimensional example of a two-state system shall be exhibited ([]). Let us denote the two base states by 1 and 2. Any arbitrary physical state y is a coherent superposition of 1 and 2 and can be written as y = 1 ( 1, y) +2 ( 2, y) with the two coefficients ( 1, y) ,( 2, y) Î \Bbb C.

Let us discuss two particular types of evolutions.

First, let us discuss the Schrödinger equation with diagonal Hamilton matrix, i.e., with vanishing off-diagonal elements,

Hij = æ ç è E1 0 0 E2 ö ÷ ø     .

(51)

In this case, the Schrödinger equation decouples and reduces to

i(h/2p) ¶ ¶t ( 1 , y(t) ) = E1 ( 1 , y(t) )    ,      i(h/2p) ¶ ¶t ( 2 , y(t) ) = E2 ( 2 , y(t) )    ,

(52)

resulting in

( 1 , y(t) ) = a e-iE1t/(h/2p)    ,      ( 2 , y(t) ) = b e-iE2t/(h/2p)    ,

(53)

with a,b Î \Bbb C, |a|²+|b|² = 1. These solutions correspond to stationary states which do not change in time; i.e., the probability to find the system in the two states is constant

|( 1 , y) |2 = |a|2    ,      |( 2 , y) |2 = |b|2    .

(54)

Second, let us discuss the Schrödinger equation with with non-vanishing but equal off-diagonal elements -A and with equal diagonal elements E of the Hamiltonian matrix; i.e.,

Hij = æ ç è E -A -A E ö ÷ ø     .

(55)

In this case, the Schrödinger equation reads

i(h/2p) ¶ ¶t ( 1 , y(t) ) = E ( 1 , y(t) ) - A ( 2 , y(t) )    , (56) i(h/2p) ¶ ¶t ( 2 , y(t) ) = E ( 2 , y(t) ) - A ( 1 , y(t) )    . (57)

These equations can be solved in a number of ways. For example, taking the sum and the difference of the two, one obtains

i(h/2p) ¶ ¶t (( 1 , y(t) ) +( 2, y(t) ) ) = (E-A) (( 1 , y(t) ) + ( 2 , y(t) ))    , (58) i(h/2p) ¶ ¶t (( 1 , y(t) ) -( 2, y(t)) ) = (E+A) (( 1 , y(t) ) - ( 2 , y(t) ))    . (59)

The solution are again two stationary states

( 1 , y(t) ) +( 2 , y(t) ) = ae-(i/(h/2p) )(E-A)t    , (60) ( 1 , y(t)) -( 2 , y(t)) = be-(i/(h/2p) )(E+A)t    . (61)

Thus,

( 1 , y(t)) = a 2 e-(i/(h/2p) )(E-A)t+ b 2 e-(i/(h/2p) )(E+A)t    , (62) ( 2 , y(t)) = a 2 e-(i/(h/2p) )(E-A)t- b 2 e-(i/(h/2p) )(E+A)t    . (63)

Assume now that initially, i.e., at t = 0, the system was in state , 1) = , y(t = 0)). This assumption corresponds to ( 1 , y(t = 0) ) = 1 and ( 2 , y(t = 0) ) = 0. What is the probability that the system will be found in the state 2 at the time t > 0, or that it will still be found in the state 1 at the time t > 0? Setting t = 0 in equations (62) and (63) yields

( 1 , y(t = 0)) = a+b 2 = 1    ,      ( 2 , y(t = 0)) = a-b 2 = 0    ,

(64)

and thus a = b = 1. Equations (62) and (63) can now be evaluated at t > 0 by substituting 1 for a and b,

( 1 , y(t)) = e-(i/(h/2p) )Et é ê ë e(i/(h/2p) )At+e-(i/(h/2p) )At 2 ù ú û = e-(i/(h/2p) )Etcos At (h/2p)     , (65) ( 2 , y(t)) = e-(i/(h/2p) )Et é ê ë e(i/(h/2p) )At-e-(i/(h/2p) )At 2 ù ú û = i e-(i/(h/2p) )Etsin At (h/2p)     . (66)

Finally, the probability that the system is in state , 1) and , 2) is

|( 1 , y(t)) |2 = cos2 At (h/2p)     ,      |( 2 , y(t)) |2 = sin2 At (h/2p)     ,

(67)

respectively. This results in an oscillation of the transition probabilities.

Let us shortly mention one particular realization of a two-state system which, among many others, has been discussed in the Feynman lectures []. Consider an ammonia (NH₃) molecule. If one fixes the plane spanned by the three hydrogen atoms, one observes two possible spatial configurations , 1) and , 2), corresponding to position of the nitrogen atom in the lower or the upper hemisphere, respectively (cf. Fig. ). The nondiagonal elements of the Hamiltonian H₁₂ = H₂₁ = -A correspond to a nonvanishing transition probability from one such configuration into the other.

If the ammonia has been originally in state , 1), it will constantly swing back and forth between the two states, with a probability given by equations (67).

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

The quantum formalism introduced in the main text is about single quantized objects. What if one wants to consider many such objects? Do we have to add assumptions in order to treat such multi-particle, multi-quanta systems appropriately?

The answer is yes. Experiment and theoretical reasoning (the representation theory of the Lorentz group [] and the spin-statistics theorem [,,,]) indicate that there are (at least) two basic types of states (quanta, particles): bosonic and fermionic states. Bosonic states have what is called ``integer spin;'' i.e., s<sub>b</sub> = 0,(<sup>h</sup>/<sub>2p</sub>) ,2 (<sup>h</sup>/<sub>2p</sub>) ,3(<sup>h</sup>/<sub>2p</sub>) ,¼, whereas fermionic states have ``half-integer spin;'' s_f = [(1(^h/_2p))/2],[(3(^h/_2p))/2],[(5(^h/_2p))/2]¼. Most important, they are characterized by the way identical copies of them can be ``brought together.'' Consider two boxes, one for identical bosons, say photons, the other one for identical fermions, say electrons. For the first, bosonic, box, the probability that another identical boson is added increases with the number of identical bosons which are already in the box. There is a tendency of bosons to ``condensate'' into the same state. The second, fermionic box, behaves quite differently. If it is already occupied by one fermion, another identical fermion cannot enter. This is expressed in the Pauli exclusion principle: A system of fermions can never occupy a configuration of individual states in which two individual states are identical.

How can the bose condensation and the Pauli exclusion principle be implemented? There are several forms of implementation (e.g., fermionic behavior via Slater-determinants), but the most compact and widely practiced form uses operator algebra. In the following we shall present this formalism in the context of quantum field theory [,,,,,,].

A classical field can be represented by its Fourier transform (``*'' stands for complex conjugation)

A(x,t) = A(+)(x,t)+A(-)(x,t) (68) A(+)(x,t) = [A(-)(x,t)]* (69) A(+)(x,t) = å ki,si  aki,siuki,si(x)e-iwki t    , (70)

where n = w_ki/2p stands for the frequency in the field mode labeled by momentum k_i and s_i is some observable such as spin or polarization. u_ki,si stands for the polarization vector (spinor) at k_i,s_i, and, most important with regards to the quantized case, complex-valued Fourier coefficients a_ki,si Î \Bbb C.

>From now on, the k_i,s_i-mode will be abbreviated by the symbol i; i.e., 1 º k₁,s₁, 2 º k₂,s₂, 3 º k₃,s₃, ¼, i º k_i,s_i, ¼.

In (second¹⁶) quantization, the classical Fourier coefficients a_i become re-interpreted as operators, which obey the following algebraic rules (scalars would not do the trick). For bosonic fields (e.g., for the electromagnetic field), the commutator relations are (``f'' stands for self-adjointness):

[ai,ajf ] = ai ajf - ajf ai = dij     , (71) [ai,aj] = [aif,ajf] = 0     . (72)

For fermionic fields (e.g., for the electron field), the anti-commutator relations are:

{ai,ajf} = aiajf+ajfai = dij     , (73) {ai,aj} = {aif,ajf} = 0     . (74)

The anti-commutator relations, in particular {a_j^f,a_j^f} = 2(a_j^f)² = 0, are just a formal expression of the Pauli exclusion principle stating that, unlike bosons, two or more identical fermions cannot co-exist.

The operators a_i^f and a_i are called creation and annihilation operators, respectively. This terminology suggests itself if one introduces Fock states and the occupation number formalism. a_i^f and a_i are applied to Fock states to following effect.

The Fock space associated with a quantized field will be the direct product of all Hilbert spaces \frak H_i; i.e.,

Õ i Î \Bbb I  \frak Hi    ,

(75)

where \Bbb I is an index set characterizing all different field modes labeled by i. Each boson (photon) field mode is equivalent to a harmonic oscillator [,]; each fermion (electron, proton, neutron) field mode is equivalent to the Larmor precession of an electron spin.

In what follows, only finite-size systems are studied. The Fock states are based upon the Fock vacuum. The Fock vacuum is a direct product of states | 0_iñ of the i'th Hilbert space \frak H_i characterizing mode i; i.e.,

| 0ñ = Õ i Î \Bbb I  | 0 ñi = | 0 ñ1 Ä | 0 ñ2 Ä | 0 ñ3 ļ = | È i Î \Bbb I  {0i} ñ = | {01,02,03,¼}ñ    , (76)

where again \Bbb I is an index set characterizing all different field modes labeled by i. ``0<sub>i</sub>'' stands for 0 (no) quantum (particle) in the state characterized by the quantum numbers i. Likewise, more generally, ``N_i'' stands for N quanta (particles) in the state characterized by the quantum numbers i.

The annihilation operators a_i are designed to destroy one quantum (particle) in state i:

aj | 0ñ = 0    , (77) aj | {01,02,03,¼,0j-1,Nj,0j+1, ¼}ñ =        = Ö   Nj   | {01,02,03,¼,0j-1,(Nj-1),0j+1, ¼}ñ    . (78)

The creation operators a_i^f are designed to create one quantum (particle) in state i:

ajf | 0 ñ = | {01,02,03,¼,0j-1,1j,0j+1, ¼}ñ    .

(79)

More generally, N_j operators (a_j^f )^N_j create an N_j-quanta (particles) state

(ajf )Nj | 0ñ µ | {01,02,03,¼,0j-1,Nj,0j+1, ¼}ñ    .

(80)

For fermions, N_j Î { 0,1} because of the Pauli exclusion principle. For bosons, N_j Î \Bbb N₀. With proper normalization [which can motivated by the (anti-)commutator relations and by |( X, X)|² = 1], a state containing N₁ quanta (particles) in mode 1, N₂ quanta (particles) in mode 2, N₃ quanta (particles) in mode 3, etc., can be generated from the Fock vacuum by

| È i Î \Bbb I  {Ni} ñ º | {N1,N2,N3,¼}ñ = Õ i Î \Bbb I  (aif )Ni Ö Ni! | 0 ñ    .

(81)

As has been stated by Glauber [],

¼ in quantum theory, there is an infinite set of complex numbers which specifies the state of a single mode. This is in contrast to classical theory where each mode may be described by a single complex number. This shows that there is vastly more freedom in quantum theory to invent states of the world than there is in the classical theory. We cannot think of quantum theory and classical theory in one-to-one terms at all. In quantum theory, there exist whole spaces which have no classical analogues, whatever.

C  Quantum interference

In what follows, we shall make use of a simple ``toolbox''-scheme of combining lossless elements of an experimental setup for the theoretical calculation []. The elements of this ``toolbox'' are listed in Table . These ``toolbox'' rules can be rigorously motivated by the full quantum optical calculations (e.g., [,]) but are much easier to use. In what follows, the factor i resulting from a phase shift of p/2 associated with the reflection at a mirror M is omitted. However, at a half-silvered mirror beam splitter, the relative factor i resulting from a phase shift of p/2 is kept. (A detailed calculation [] shows that this phase shift of p/2 is an approximation which is exactly valid only for particular system parameters). T and R = Ö[(1-T<sup>2</sup>)] are transmission and reflection coefficients. Notice that the ``generic'' beam splitter can be realized by a half-silvered mirror and a successive phase shift of j = -p/2 in the reflected channel; i.e., a ®( b +i c)/Ö2 ®( b +ie^-ip/2 c)/Ö2 ®( b + c)/Ö2. Note also that, in the ``second quantization'' notation, for i < j,

| iñ | jñ º aif ajf | 0ñ = | iñÄ | jñ = | 01,02,03,¼,0i-1,1i,0i+1,¼, 0j-1,1j,0j+1,¼ñ    .

(82)

In present-day quantum optical nonlinear devices (NL), parametric up- or down-conversion, i.e., the production of a single quant (particle) from two field quanta (particles) and the production of two field quanta (particles) from a single one occurs at the very low amplitude rate of h » 10^-6.

In what follows, a lossless Mach-Zehnder interferometer drawn in Fig. is discussed.

The computation proceeds by successive substitution (transition) of states; i.e.,

S1:  a ® ( b +i c)/Ö2    , (83) P:  b ® b ei j    , (84) S2:  b ® ( e + id )/Ö2    , (85) S2:  c ® ( d + ie )/Ö2    . (86)

The resulting transition is

a ® y = i æ ç è eij +1 2 ö ÷ ø d + æ ç è eij -1 2 ö ÷ ø e     .

(87)

Assume that j = 0, i.e., there is no phase shift at all. Then, equation (87) reduces to a ® i d , and the emitted quant is detected only by D₁. Assume that j = p. Then, equation (87) reduces to a ® - e , and the emitted quant is detected only by D₂. If one varies the phase shift j, one obtains the following detection probabilities:

PD1(j) = |( d, y) |2 = cos2( j 2 )    ,   PD2(j) = |( e, y) |2 = sin2( j 2 )    .

(88)

For some ``mindboggling'' features of Mach-Zehnder interferometry, see [].

D  Universal 2-port quantum gate

The elementary quantum interference device T₂₁^bs depicted in Fig. (4.a) is just a beam splitter followed by a phase shifter in one of the output ports. According to the ``toolbox'' rules of appendix C, the process can be quantum mechanically described by¹⁷

P1:  0 ® 0 eia+b    , (89) P2:  1 ® 1ei b    , (90) S:  0 ® T 1¢+iR 0¢    , (91) S:  1 ® T 0¢+iR 1¢    , (92) P3:  0¢ ® 0¢eij    . (93)

If 0 º 0¢ º (

1

0

) and 1 º 1¢ º (

0

1

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

T21bs (w,a,b,j) = é ê ë ei b  æ ç è i  ei(a+j)  sinw eia  cosw eij cosw i sinw ö ÷ ø ù ú û -1   = e-i b  æ ç è -i  e-i(a+j)  sinw e-ij  cosw e-ia cosw -i sinw ö ÷ ø     . (94)

The elementary quantum interference device T₂₁^MZ depicted in Fig. (4.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

P1:  0 ® 0 eia+b    , (95) P2:  1 ® 1 eib    , (96) S1:  1 ® ( b +i c )/Ö2    , (97) S1:  0 ® ( c +i b )/Ö2    , (98) P3:  c ® c ei w    , (99) S2:  b ® ( 1¢+ i 0¢)/Ö2    , (100) S2:  c ® ( 0¢+ i 1¢)/Ö2    , (101) P4:  0¢ ® 0¢eij    . (102)

When again 0 º 0¢ º (

1

0

) and 1 º 1¢ º (

0

1

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

T21MZ (a,b,w,j) = -i e-i(b+[(w)/2])   æ ç ç ç ç ç ç ç ç è -e-i (a+j) sin w 2 e-i j cos w 2 e-i a cos w 2 sin w 2 ö ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ø     .

(103)

The correspondence between T₂₁^bs (T(w),a,b,j) with T₂₁^MZ (a¢,b¢,w¢,j¢) in equations (94) (103) 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.,

T21bs (w,a,b,j) = T21MZ (a- p 2 , b-w,2w,j- p 2 )    .

(104)

Both elementary quantum interference devices are universal in the sense that every unitary quantum evolution operator in two-dimensional 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 (94) (103) 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) []

T (w,a,j) = æ ç è ei a cosw -e-i j sinw ei j sinw e-i a cosw ö ÷ ø     ,

(105)

where -p £ b,w £ p, - [(p)/2] £ a,j £ [(p)/2]. Let

T (w,a,b,j) = e-i bT (w,a,j)    .

(106)

A proper identification of the parameters a,b,w,j yields

T (w,a,b,j) = T21bs (w- p 2 ,-a-j- p 2 ,b+ a+ p 2 ,j-a+ p 2 )    .

(107)

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 0 ® 0 , 1 ® 1 and can be realized by

\Bbb I = Tbs21(- p 2 ,- p 2 , p 2 , p 2 ) = TMZ21(-p,p,-p,0) = æ ç è 1 0 0 1 ö ÷ ø     .

(108)

The ``not'' element is defined by 0 ® 1 , 1 ® 0 and can be realized by

not = Tbs21(0,0,0,0) = TMZ21(-  p 2 ,0,0,-  p 2 ) = æ ç è 0 1 1 0 ö ÷ ø     .

(109)

The next element, `` Ö{not}'' is a truly quantum mechanical; i.e., nonclassical, one, since it converts a classical bit into a coherent superposition of 0 and 1 . Ö{not} is defined by 0 ® 0 + 1 , 1 ® - 0 + 1 and can be realized by

Ö   not   = Tbs21(- p 4 ,- p 2 , p 2 , p 2 ) = TMZ21(-p, 3p 4 ,- p 2 ,0 ) = 1 Ö2 æ ç è 1 -1 1 1 ö ÷ ø     .

(110)

Note that Ö{not}·Ö{not} = not·diag(1,-1) = not (mod  1). The relative phases in the output ports showing up in diag(1,-1) can be avoided by defining

Ö   not   ¢ = Tbs21(-  p 4 ,0, p 4 ,0) = TMZ21(-  p 2 , p 2 ,-  p 2 ,-  p 2 ) = 1 2 æ ç è 1+i 1-i 1-i 1+i ö ÷ ø     .

(111)

With this definition, Ö{not}¢Ö{not}¢ = not.

It is very important that the elementary quantum interference device realizes an arbitrary quantum time evolution of a two-dimensional system. The performance of the quantum interference device is determined by four parameters, corresponding to the phases a,b,j, w.

References

[]

Albert, D. Z. On quantum-mechanical automata. Physics Letters 94A, 5,6 (1983), 249-252.

[]

Anderson, A. R. St. Paul's epistle to Titus. In The Paradox of the Liar, R. L. Martin, Ed. Yale University Press, New Haven, 1970. The Bible contains a passage which refers to Epimenides, a Crete living in the capital city of Cnossus: ``One of themselves, a prophet of their own, said, `Cretans are always liars, evil beasts, lazy gluttons.' '',- St. Paul, Epistle to Titus I (12-13).

[]

Ballentine, L. E. Quantum Mechanics. Prentice Hall, Englewood Cliffs, NJ, 1989.

[]

Barenco, A., Bennett, C. H., Cleve, R., DiVincenzo, D. P., Margolus, N., Shor, P., Sleator, T., Smolin, J., and Weinfurter, H. Elementary gates for quantum computation.
e-print http://xxx.lanl.gov/abs/quant-ph/9503016.

[]

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

[]

Benioff, P. A. Quantum mechanical hamiltonian models of turing machines. Journal of Statistical Physics 29, 3 (1982), 515-546.

[]

Benioff, P. A. Quantum mechanical hamiltonian models of computers. Annals of the New York Akademy of Sciences 480 (1986), 475-486.

[]

Bennett, C. H. Logical reversibility of computation. IBM Journal of Research and Development 17 (1973), 525-532. Reprinted in [].

[]

Bennett, C. H. The thermodynamics of computation-a review. In International Journal of Theoretical Physics [], pp. 905-940. Reprinted in [].

[]

Bennett, C. H. Night thoughts, dark sight. Nature 371 (1994), 479-480.

[]

Bennett, C. H., Bessette, F., Brassard, G., Salvail, L., and Smolin, J. Experimental quantum cryptography. Journal of Cryptology 5 (1992), 3-28.

[]

Bennett, C. H., and Brassard, G. Quantum cryptography: Public key distribution and coin tossing. In Proceedings of the IEEE International Conference on Computers, Systems, and Signal Processing, Bangalore, India (1984), IEEE Computer Society Press, pp. 175-179.

[]

Bennett, C. H., Brassard, G., Breidbart, S., and Wiesner, S. Quantum cryptography, or unforgable subway tokens. In Advances in Cryptography: Proceedings of Crypto '82 (New York, 1982), Plenum Press, pp. 78-82.

[]

Bernstein, E., and Vazirani, U. Quantum complexity theory. In Proceedings of the 25th Annual ACM Symposium on Theory of Computing, San Diego, California, May 16-18, 1993 (1993), ACM Press, pp. 11-20.

[]

Berthiaume, A., and Brassard, G. The quantum challenge to structural complexity theory. In Proceedings, Structure in Complexity Theory, seventh annual conference, Boston University, Boston, Massachusetts, June 22-25, 1992 (1992), IEEE Computer Society Press, pp. 132-137.

[]

Bishop, E., and Bridges, D. S. Constructive Analysis. Springer, Berlin, 1985.

[]

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

[]

Born, M., and Wolf, E. Principles of Optics: Electromagnetic Theory of Propagation, Interference and Diffraction of Light, 6th ed. Pergamon Press, Oxford, 1993.

[]

Bridges, D., and Richman, F. Varieties of Constructive Mathematics. Cambridge University Press, Cambridge, 1987.

[]

Bridges, D. S. Computability. Springer, New York, 1994.

[]

Bridgman, P. W. A physicists second reaction to Mengenlehre. Scripta Mathematica 2 (1934), 101-117, 224-234. Cf. R. Landauer [].

[]

Bridgman, P. W. Reflections of a Physicist. Philosophical Library, New York, 1950.

[]

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

[]

Campos, R. A., Saleh, B. E. A., and Teich, M. C. Fourth-order interference of joint single-photon wave packets in lossless optical systems. Physical Review A42 (1990), 4127.

[]

Cantor, G. Gesammelte Abhandlungen. Springer, Berlin, 1932.

[]

Caves, C. M. Quantum limits on noise in linear amplifiers. Physical Review D26 (1982), 1817-1839.

[]

Cerný, V. Quantum computers and intractable (NP-complete) computing problems. Physical Review A48 (1993), 116-119.

[]

Chaitin, G. J. Algorithmic Information Theory. Cambridge University Press, Cambridge, 1987.

[]

Chaitin, G. J. Information, Randomness and Incompleteness, second ed. World Scientific, Singapore, 1990. This is a collection of G. Chaitin's publications.

[]

Chuang, I., Laflamme, R., Shor, P., and Zurek, W. Quantum computers, factoring, and decoherence.
e-print http://xxx.lanl.gov/abs/quant-ph/9503007.

[]

Davis, M. Computability and Unsolvability. McGraw-Hill, New York, 1958.

[]

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

[]

Davydov, A. S. Quantum Mechanics. Addison-Wesley, Reading, MA, 1965.

[]

Deutsch, D. Quantum theory, the Church-Turing principle and the universal quantum computer. Proceedings of the Royal Society London A 400 (1985), 97-119.

[]

Deutsch, D. Quantum computational networks. Proceedings of the Royal Society London A 425 (1989), 73-90.

[]

Deutsch, D., and Jozsa, R. Rapid solution of problems by quantum computation. Proceedings of the Royal Society London A 439 (1992), 553-558.

[]

Dieks, D. Communication by EPR devices. Physics Letters 92A, 6 (1982), 271-272.

[]

Dirac, P. A. M. The Principles of Quantum Mechanics. Oxford University Press, Oxford, 1947.

[]

Dunford, N., and Schwartz, J. T. Linear Operators I. Interscience Publishers, New York, 1958.

[]

Einstein, A. Über einen die Erzeugung und Verwandlung des Lichtes betreffenden heuristischen Gesichtspunkt. Annalen der Physik 17 (1905), 132-148.

[]

Einstein, A., Podolsky, B., and Rosen, N. Can quantum-mechanical description of physical reality be considered complete? Physical Review 47 (1935), 777-780. Reprinted in [].

[]

Feynman, R. P. Simulating physics with computers. International Journal of Theoretical Physics 21 (1982), 467-488.

[]

Feynman, R. P. Quantum mechanical computers. Optics News 11 (February 1985), 11-20.

[]

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

[]

Fredkin, E., and Toffoli, T. Conservative logic. International Journal of Theoretical Physics 21 (1982), 219-253.

[]

Glauber, R. J. Amplifyers, attenuators and the quantum theory of measurement. In Frontiers in Quantum Optics, E. R. Pikes and S. Sarkar, Eds. Adam Hilger, Bristol, 1986.

[]

Gödel, K. Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme. Monatshefte für Mathematik und Physik 38 (1931), 173-198. English translation in [], and in [].

[]

Gödel, K. In Collected Works. Publications 1929-1936. Volume I, S. Feferman, J. W. Dawson, S. C. Kleene, G. H. Moore, R. M. Solovay, and J. van Heijenoort, Eds. Oxford University Press, Oxford, 1986.

[]

Greenberger, D. B., Horne, M., and Zeilinger, A. Multiparticle interferometry and the superposition principle. Physics Today 46 (August 1993), 22-29.

[]

Greenberger, D. B., and YaSin, A. ``Haunted'' measurements in quantum theory. Foundation of Physics 19, 6 (1989), 679-704.

[]

Hamming, R. W. Coding and Information Theory, second ed. Prentice-Hall, Englewood Cliffs, NJ, 1980.

[]

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

[]

Herbert, N. FLASH-a superluminal communicator based upon a new kind of quantum measurement. Foundation of Physics 12, 12 (1982), 1171-1179.

[]

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

[]

Jammer, M. The Philosophy of Quantum Mechanics. John Wiley & Sons, New York, 1974.

[]

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

[]

Kochen, S., and Specker, E. P. Logical structures arising in quantum theory. In Symposium on the Theory of Models, Proceedings of the 1963 International Symposium at Berkeley (Amsterdam, 1965), North Holland, pp. 177-189.

[]

Kochen, S., and Specker, E. P. The problem of hidden variables in quantum mechanics. Journal of Mathematics and Mechanics 17, 1 (1967), 59-87.

[]

Landauer, R. Letter, june 1st, 1994.

[]

Landauer, R. Fundamental physical limitations of the computational process; an informal commentary. Cybernetics Machine Group Newsheet (1/1/1987).

[]

Landauer, R. Irreversibility and heat generation in the computing process. In IBM Journal of Research and Development [], pp. 183-191. Reprinted in [].

[]

Landauer, R. Wanted: a physically possible theory of physics. IEEE Spectrum 4 (1967), 105-109.

[]

Landauer, R. Computation, measurement, communication and energy dissipation. In Selected Topics in Signal Processing, S. Haykin, Ed. Prentice Hall, Englewood Cliffs, NJ, 1989, p. 18.

[]

Landauer, R. Information is physical. Physics Today 44 (May 1991), 23-29.

[]

Landauer, R. Advertisement for a paper I like. In On Limits, J. L. Casti and J. F. Traub, Eds. Santa Fe Institute Report 94-10-056, Santa Fe, NM, 1994, p. 39.

[]

Landauer, R. Zig-zag path to understanding. In Proceedings of the Workshop on Physics and Computation PHYSCOMP '94 (Los Alamitos, CA, 1994), IEEE Computer Society Press, pp. 54-59.

[]

Leff, H. S., and Rex, A. F. Maxwell's Demon. Princeton University Press, Princeton, 1990.

[]

Li, M., and Vitányi, P. M. B. Kolmogorov complexity and its applications. In Handbook of Theoretical Computer Sciences. Elsevier Science Publishers, Amsterdam, 1990. [].

[]

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

[]

Loudon, R., and Knight, P. L. Squeezed light. Journal of Modern Optics 34 (1987), 709-759.

[]

Luriè, D. Particles and Fields. Interscience Publishers, New York, 1968.

[]

Mandel, L. Is a photon amplifier always polarization dependent? Nature 304 (1983), 188.

[]

Mermin, N. D. What's wrong with these elements of reality? Physics Today 43, 6 (June 1990), 9-10.

[]

Messiah, A. Quantum Mechanics, vol. I. North-Holland, Amsterdam, 1961.

[]

Milonni, P. W., and Hardies, M. L. Photons cannot always be replicated. Physics Letters 92A, 7 (1982), 321-322.

[]

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

[]

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

[]

Peres, A. Quantum Theory: Concepts and Methods. Kluwer Academic Publishers, Dordrecht, 1993.

[]

Planck, M. Ueber eine Verbesserung der Wien'schen Spectralgleichung. Verhandlungen der deutschen physikalischen Gesellschaft 2 (1900), 202.

[]

Planck, M. Die physikalische Struktur des Phasenraumes. Annalen der Physik 50 (1916), 385-418.

[]

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

[]

Reck, M., Zeilinger, A., Bernstein, H. J., and Bertani, P. Experimental realization of any discrete unitary operator. Physical Review Letters 73 (1994), 58-61.

[]

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

[]

Rosen, R. Effective processes and natural law. In The Universal Turing Machine. A Half-Century Survey, R. Herken, Ed. Kammerer & Unverzagt, Hamburg, 1988, p. 523.

[]

Schrödinger, E. Die gegenwärtige Situation in der Quantenmechanik. Naturwissenschaften 23 (1935), 807-812, 823-828, 844-849. English translation in [].

[]

Sexl, R. U., and Urbantke, H. K. Relativität, Gruppen, Teilchen. Springer, Vienna, 1976.

[]

Shor, P. W. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings of the 35th Annual Symposium of on Foundations of Computer Science, Santa Fe, NM, Nov. 20-22, 1994 (November 1994), IEEE Computer Society Press.
e-print http://xxx.lanl.gov/abs/quant-ph/9508027.

[]

Solomonoff, R. J. A formal theory of inductive inference. part i. Information and Control 7 (1964), 1-22.

[]

Solovay, R. M. unpublished manuscript.

[]

Svozil, K. The consistent use of paradoxes. Foundations of Physics Letters, in press.

[]

Svozil, K. Speedup in quantum computation is associated with attenuation of processing probability.
e-print http://tph.tuwien.ac.at/~svozil/publ/kraft.ps
e-print http://xxx.lanl.gov/abs/hep-th/9412046.

[]

Svozil, K. Randomness & Undecidability in Physics. World Scientific, Singapore, 1993.

[]

Svozil, K. Halting probability amplitude of quantum computers. Journal of Universal Computer Science 1, 3 (March 1995).

[]

Svozil, K. Quantum computation and complexity theory. part I. Bulletin of the European Association of Theoretical Computer Sciences 55 (1995), 170-207.
e-print http://tph.tuwien.ac.at/~svozil/publ/qct1.ps.

[]

Svozil, K. Quantum computation and complexity theory. part II. Bulletin of the European Association of Theoretical Computer Sciences 56 (1995), 116-136.
e-print http://tph.tuwien.ac.at/~svozil/publ/qct2.ps.

[]

Svozil, K. Set theory and physics. Foundations of Physics 25 (1995), 1541-1560.

[]

Turing, A. M. On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, Series 2 42 and 43 (1936-7 and 1937), 230-265 and 544-546. reprinted in [].

[]

van Leeuwen, J. Algorithms and Complexity, vol. A. Elsevier and MIT Press, Amsterdam and Cambridge, MA, 1990.

[]

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

[]

Wheeler, J. A., and Zurek, W. H. Quantum Theory and Measurement. Princeton University Press, Princeton, 1983.

[]

Wigner, E. P. The unreasonable effectiveness of mathematics in the natural sciences. Richard Courant Lecture delivered at New York University, May 11, 1959. Communications on Pure and Applied Mathematics 13 (1960), 1.

[]

Wooters, W. K., and Zurek, W. H. A single quantum cannot be cloned. Nature 299 (1982), 802-803.

[]

Yurke, B., McCall, S. L., and Klauder, J. R. SU(2) and SU(1,1) interferometers. Physical Review A33 (1986), 4033-4054.

Footnotes:

¹ For an early discussion of this topic, see Davis []:

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

² Again it is confirmed that the quantum hypothesis is not based on energy elements but on action elements, according to the fact that the volume of phase space has the dimension h^f.

³ Introductions to quantum mechanics can be found in Feynman, Leighton & M. Sands [], Harris [], Lipkin [], Ballentine [], Messiah [], Dirac [], Peres [], von Neumann [], and Bell [], among many other expositions. The history of quantum mechanics is reviewed by Jammer []. Wheeler & Zurek [] published a helpful resource book.

⁴ The bra-ket notation introduced by Dirac is widely used in physics. To translate expressions into the bra-ket notation, the following identifications work for most practical purposes: for the scalar product, ``á º   ('', ``ñ º   )'', ``, º    | ''. States are written as | yñ º y, operators as ái | A | j ñ º A_ij.

⁵ Infinite dimensional cases and continuous spectra are nontrivial extensions of the finite dimensional Hilbert space treatment. As a heuristic rule, it could be stated that the sums become integrals, and the Kronecker delta function d_ij becomes the Dirac delta function d(i-j), which is a generalized function in the continuous variables i,j. In the Dirac bra-ket notation, unity is given by 1 = ò_-¥^+¥ |iñái| di.

⁶the expressions should be interpreted in the sense of operator equations; the operators themselves act on states.

⁷ The y-function as expectation-catalog: ¼ In it [[the y-function]] is embodied the momentarily-attained sum of theoretically based future expectation, somewhat as laid down in a catalog. ¼ For each measurement one is required to ascribe to the y-function ( = the prediction catalog) a characteristic, quite sudden change, which depends on the measurement result obtained, and so cannot be foreseen; from which alone it is already quite clear that this second kind of change of the y-function has nothing whatever in common with its orderly development between two measurements. The abrupt change [[of the y-function ( = the prediction catalog)]] by measurement ¼ is the most interesting point of the entire theory. It is precisely the point that demands the break with naive realism. For this reason one cannot put the y-function directly in place of the model or of the physical thing. And indeed not because one might never dare impute abrupt unforeseen changes to a physical thing or to a model, but because in the realism point of view observation is a natural process like any other and cannot per se bring about an interruption of the orderly flow of natural events.

⁸ (t,t) = (f,f) = 1 and (t,f) = 0.

⁹ Copying can be done reversible in classical physics, if the memory used for the copy is initially blank. Quantum mechanically, this cannot be done on qbits; cf. below.

¹⁰ If an irreversible computing agent exists which computes the input from a given output, then it is possible to translate an irreversible computation from input to output into one which is reversible and erases everything else except the final output, including the original input; i.e., that simply maps inputs into outputs. For details, see Bennett [,].

¹¹Copying of qbits would allow circumvention of the Heisenberg uncertainty relation by measuring two incompatible observables on two identical qbit copies. It would also allow faster-than-light transmission of information, as pointed out by Herbert []. Herbert's suggestion stimulated the development of ``no-cloning theorems'' reviewed here.

¹²the most elementary realization is a one-mode field with the symbol 0 corresponding to | 0ñ (empty mode) and 1 corresponding to | 1ñ (one-quantum filled mode).

¹³ (h_{a, b},h_{a, b}) = 1.

¹⁴The quantum omega was invented in a meeting of G. Chaitin, A. Zeilinger and the author in a Viennese coffee house (Café Bräunerhof) in January 1991. Thus, the group should be credited for the original invention, whereas any blame should remain with the author.

¹⁵ The definition of W and U differ slightly from the ones introduced by the author previously [].

¹⁶of course, there is only ``the one and only'' quantization, the term ``second'' often refers to operator techniques for multiquanta systems; i.e., quantum field theory

¹⁷ 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 a two-dimensional Hilbert 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 [,].