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 ChurchTuring 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 ChurchTuring thesis is under permanent physical attack.^{1} Conversely, any feature of the (constructive or nonconstructive [,,]) 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 [],
In particular, the fundamental atom of information, the bit, must be represented by whatever physical theories are available and must be experimentally producible and manipulable by whatever physical operations are available.``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 onetoone 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 quasiclassical 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 headon collision with longheld classical properties. Several longheld 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 reconsider 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 ``CookKarp 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.
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 2fdimensional phase space (f degrees of freedom) is a positive integer of h^{f} [],^{2}
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.^{3} To avoid a shock from a too early exposure to `exotic' nomenclature prevalent in physicsthe Dirac braket notationthe notation of DunfordSchwartz [] is adopted.^{4}
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):
In what follows, unless stated differently, only finite dimensional Hilbert spaces are considered.^{5} Then, the vectors corresponding to states can be written as usual vectors in complex Hilbert space. Furthermore, bounded selfadjoint operators are equivalent to bounded Hermitean operators. They can be represented by matrices, and the selfadjoint 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_{1},b_{2},¼}, 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 braket 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_{1},x_{2},x_{3}), and the momentum operator [\frak p\vec]_{x} = [((^{h}/_{2p}))/i] [(Ñ)\vec] = [((^{h}/_{2p}))/i] ([(¶)/(¶x_{1})],[(¶)/(¶x_{2})],[(¶)/(¶x_{3})]), where (^{h}/_{2p}) = [h/(2p)]. The scalar product is given by ([x\vec],[y\vec]) = d^{3} ([x\vec][y\vec]) = d(x_{1}y_{1})d(x_{2}y_{2})d(x_{3}y_{3}). The nonrelativistic energy operator (Hamiltonian) is H = [[\frak p\vec] [\frak p\vec]/2m]+V(x) =  [((^{h}/_{2p})^{2})/2m]Ñ^{2}+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^{6} [\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^{2}ñáxñ^{2}} and Dp_{x} = Ö{áp_{x}^{2}ñáp_{x}ñ^{2}}, 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 selfadjoint operator in a finite dimensional Hilbert space can be experimentally realized [].
This ``transition'' x® a_{n} 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 yfunction? In his 1935 paper ``Die Gegenwärtige Situation in der Quantenmechanik'' (``The present situation in quantum mechanics'' []), Schrödinger states,^{7}
Die yFunktion als Katalog der Erwartung: ¼ Sie [[die yFunktion]] 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 yFunktion ( = 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 yFunktion 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 yFunktion 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.
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 selfadjoint 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_{0} ) =  [iH/((^{h}/_{2p}) )] y(t). In terms of the set of orthonormal base vectors { b_{1}, b_{2}, ¼}, the Schrödinger equation can be written as i(^{h}/_{2p}) [(¶)/(¶t)] ( b_{i} , y(t) ) = å_{j}H_{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})^{2})/2m]Ñ^{2}+V(x)] y(x,t).
For stationary y_{n}(t) = e^{(i/(h/2p) )Ent} y_{n} , the Schrödinger equation can be brought into its timeindependent 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/rpotential 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 twostate system, see appendix . For a review of the quantum theory of multiple particles, see appendix .
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^{8}
states t and f.
The qbit states
 (1) 
 (2) 
 (3) 
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)^{2} and P_{f}(x_{a,b}) = (x_{a,b},f)^{2} = 1P_{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 contextfree. 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.
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 thatat least up to a certain magnitude of complexityany measurement can be ``undone'' by a proper reconstruction of the wavefunction. 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 noncomplementary pages which correspond to two comeasurable 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 timereversible, the act of irreversible observation must, according to Wigner [], occur in the consciousness, thereby violating quantum mechanics.
As a prelude to quantum computation, we briefly review classical reversible computation [,,,,]. This type of computation is characterized by a singlevalued inverse transition function. In irreversible computations, logical functions are performed which do not have a singlevalued inverse, such as AND or OR; i.e., the input cannot be deduced from the output. Also deletion of information or other many (states)toone (state) operations are irreversible. Reversible calculation requires every single step to be reversible. Figure [] draws the difference between onetoone and manytoone computation. This logical irreversibility is associated with physical irreversibility and requires a minimal heat generation of the computing machine.
0.70mm
Picture Omitted
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^{9} 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 backcomputation.^{10} Since qbits cannot be copied, the trick does not work for quantum computations.
The following features are important, but not sufficient qualities of quantum computers.
In order to appreciate quantum computation, one should make proper use of the above featuresquantum parallelism, unerasability of information, noncopying, contextdependence 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.
Can a nonclassical qbit be copied? No!  This answer amazes the classical mind.^{11} 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 onetoone computation processes depicted in Fig. 1a) are allowed.
This can be seen by a short calculation [] which requires the
multiquantum formalism developed in appendix .
A physical realization^{12}
of the qbit state
is a twomode boson field
with the identifications

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
 (7) 
What about copying a proper qbit; i.e., a coherent superposition
of the cbits
f = 0_{1},1_{2}ñ and
t = 1_{1},0_{2}ñ?
According to the quantum evolution law,
the corresponding amplification process should be
representable by a linear (unitary) operator; thus
 (8) 
Yet, the true copy of that qbit is the state

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.
Assume that in an EPRtype arrangement
[]
one wants to measure the product

This kind of contextuality is deeply rooted in the nonBoolean 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_{i}^{j} 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 [].
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 counterpartit 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 finitedimensional Hilbert space is given by x (t) = Ux (t_{0}) , where U is unitary.
It is well known that any ndimensional unitary matrix U can be composed from elementary unitary transformations in twodimensional subspaces of \Bbb C^{n}. This is usually shown in the context of parameterization of the ndimensional unitary groups (cf. [] and [,]). Thereby, a transformation in ndimensional spaces is decomposed into transformations in 2dimensional subspaces. This amounts to a successive array of U(2) elements, which in their entirety forms an arbitrary time evolution U(n) in ndimensional 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 finitedimensional 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 (onedimensional) 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 MachZehnder interferometry. Note that the number of elementary U(2)transformations is polynomially bounded and does not exceed (
 

Deutsch [] has proposed a model of universal computation based on quantum computation networks. Thereby, the states in a 2^{n}dimensional Hilbert space are constructed as the product state of n particles in twodimensional Hilbert space. A set of gates that consists of all U(2) (onebit) quantum gates and the twobit exclusiveor 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^{n})) 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^{n}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 nonpolynomial space overhead. In the case of the product state model, in order to obtain a mixing between different particle states, xorgates are needed. The interferometric approach does not need xorgates explicitly.
It has been claimed [,] that certain supposedly NPhard 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 classicallythe computation may ``decohere,'' reducing the qbits to classical ones []. Furthermore, in order to obtain sufficient statistical data, a ``great'' (nonpolynomially bounded) number of single particles may be needed []. We shall not pursue these matters further [,,,,,].
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 nonenumerability 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 DOloop; 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.
 (10) 
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.
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(t1, 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
 (11) 
Initially, i.e., at t = 0, the halting bit is prepared to be a 50:50 mixture of the classical halting and nonhalting 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 nonhalting
state. Since the halting state and the nonhalting state exclude each
other,
f,t can be identified with orthonormal basis vectors in a
twodimensional vector space. Thus, the standard basis of
Cartesian coordinates can be chosen for a representation of t and f;
i.e.,
 (12) 
The evolution representing diagonalization (effectively, agent
A's task) can be expressed by the unitary operator D by
 (13) 
 (14) 
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
 (15) 
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^{*} ) = ^{1}/_{2}. 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.
Consider the entire range of twodimensional unitary transformations
[]
 (16) 
 (17) 

Applying nonclassical operations on qbits with no fixed points

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 prefixfree 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(plogk) £ 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
 (20) 
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:
 (21) 
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 smallestsize binary program to calculate s and t simultaneously.
The relative or conditional quantum algorithmic information
H(st) of s Î \frak H given t Î \Bbb N
is the length of the
smallestsize binary program to calculate s from a
smallestsize program for t:
 (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 machineindependent, 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,
 (23) 
Furthermore, let s and t be two objects representable as vectors in
Hilbert space. Then (recall that t Î \Bbb N),

Notice
that there exist sets of objects
S = {s_{1},¼,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.,
 (33) 
Here, W is generalized to quantum computations.^{14}
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:50superposition; 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:50superposition.
Alternatively, the computer could be initially prepared in the nonhalting 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^{15}
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})
 (34) 
Likewise, the halting amplitude for a particular output state
s,
 (35) 
 (36) 
Terms corresponding to different programs and states have to be summed
up incoherently.
Thus, the corresponding probabilities are

The following relations hold,

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


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:

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 eneighborhood 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^{2} can be interpreted as a measure for the halting probability of C; i.e., the probability that an arbitrary (prefixfree) program halts on C.
Finally, any irreversible measurement of W^{2} 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.
Having set the stage of the quantum formalism, an elementary twodimensional example of a twostate 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 offdiagonal elements,
 (51) 
 (52) 
 (53) 
 (54) 
Second, let us discuss the Schrödinger equation with
with nonvanishing but equal offdiagonal elements A
and with equal diagonal elements E
of the
Hamiltonian matrix; i.e.,
 (55) 




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
 (64) 

 (67) 
Let us shortly mention one particular realization of a twostate system which, among many others, has been discussed in the Feynman lectures []. Consider an ammonia (NH_{3}) 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_{12} = H_{21} = A correspond to a nonvanishing transition probability from one such configuration into the other.
Picture Omitted
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).
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 multiparticle, multiquanta systems appropriately?
The answer is yes. Experiment and theoretical reasoning (the representation theory of the Lorentz group [] and the spinstatistics 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_{b} = 0,(^{h}/_{2p}) ,2 (^{h}/_{2p}) ,3(^{h}/_{2p}) ,¼, whereas fermionic states have ``halfinteger 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 Slaterdeterminants), 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)

>From now on, the k_{i},s_{i}mode will be abbreviated by the symbol i; i.e., 1 º k_{1},s_{1}, 2 º k_{2},s_{2}, 3 º k_{3},s_{3}, ¼, i º k_{i},s_{i}, ¼.
In (second^{16}) quantization,
the classical Fourier coefficients a_{i} become reinterpreted 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 selfadjointness):

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

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.,
 (75) 
In what follows, only finitesize 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.,

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

The creation operators
a_{i}^{f}
are designed to create one quantum (particle) in state i:
 (79) 
 (80) 
 (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 onetoone terms at all. In quantum theory, there exist whole spaces which have no classical analogues, whatever.
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 halfsilvered 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 = Ö[(1T^{2})] are transmission and reflection coefficients.
Notice that the ``generic''
beam splitter can be realized by a
halfsilvered 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,
 (82) 
physical process  symbol  state transformation 
reflection at mirror  a ® b = i a  
0.70mm
Picture Omitted
 
``generic'' beam splitter  a ® ( b + c)/Ö2  
Picture Omitted
 
transmission/reflection  a ® ( b +i c)/Ö2  
by a beam splitter  a ® T b +iR c,  
(halfsilvered mirror)  T^{2}+R^{2} = 1, T,R Î [0,1]  
0.70mm
Picture Omitted
 
phaseshift j  a ® b = a e^{ij}  
Picture Omitted
 
parametric downconversion  a ñ® hbñc ñ  
0.70mm
Picture Omitted
 
parametric upconversion  añ  b ñ® hc ñ  
0.70mm
Picture Omitted
 
amplification  A_{i} a ® b ;G,Nñ  
Picture Omitted
 
In what follows, a lossless MachZehnder interferometer drawn in Fig. is discussed.
0.70mm
Picture Omitted
The computation proceeds by successive substitution (transition) of
states; i.e.,

 (87) 
 (88) 
For some ``mindboggling'' features of MachZehnder interferometry, see [].
The
elementary quantum interference device T_{21}^{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^{17}

 

 


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

 

 

 (103) 
The correspondence between
T_{21}^{bs} (T(w),a,b,j) with
T_{21}^{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¢ = bw,
a¢ = ap/2,
b¢ = b w and
j¢ = jp/2; i.e.,
 (104) 
Both elementary quantum interference devices are universal in the
sense that
every unitary quantum
evolution operator in twodimensional Hilbert space can be brought into
a onetoone correspondence to T^{bs}_{21} and
T^{MZ}_{21}; with corresponding values of
T,a,b,j or
a,w,b,j.
This can be easily seen by a similar calculation as before; i.e., by
comparing
equations
(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) []
 (105) 
 (106) 
 (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
 (108) 
The ``not'' element is defined by
0 ® 1 ,
1 ® 0 and can be realized by
 (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
 (110) 
 (111) 
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.
^{1} 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?''A main theme of Landauer's work has been the connections between physics and computation; see, for example, his 1967 article [] ``Wanted: a physically possible theory of physics,'' or his more recent survey [] ``Information is physical.'' See also Rosen []. As Deutsch puts it more recently [],
``The reason why we find it possible to construct, say, electronic calculators, and indeed why we can perform mental arithmetic, cannot be found in mathematics or logic. The reason is that the laws of physics `happen to' permit the existence of physical models for the operations of arithmetic such as addition, subtraction and multiplication. If they did not, these familiar operations would be noncomputable functions. We might still know of them and invoke them in mathematical proofs (which would presumably be called `non constructive') but we could not perform them.''
^{2} 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}.
^{3} 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.
^{4} The braket notation introduced by Dirac is widely used in physics. To translate expressions into the braket 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}.
^{5} 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(ij), which is a generalized function in the continuous variables i,j. In the Dirac braket notation, unity is given by 1 = ò_{¥}^{+¥} iñái di.
^{6}the expressions should be interpreted in the sense of operator equations; the operators themselves act on states.
^{7} The yfunction as expectationcatalog: ¼ In it [[the yfunction]] is embodied the momentarilyattained sum of theoretically based future expectation, somewhat as laid down in a catalog. ¼ For each measurement one is required to ascribe to the yfunction ( = 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 yfunction has nothing whatever in common with its orderly development between two measurements. The abrupt change [[of the yfunction ( = 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 yfunction 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.
^{8} (t,t) = (f,f) = 1 and (t,f) = 0.
^{9} 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.
^{10} 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 [,].
^{11}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 fasterthanlight transmission of information, as pointed out by Herbert []. Herbert's suggestion stimulated the development of ``nocloning theorems'' reviewed here.
^{12}the most elementary realization is a onemode field with the symbol 0 corresponding to  0ñ (empty mode) and 1 corresponding to  1ñ (onequantum filled mode).
^{13} (h_{a, b},h_{a, b}) = 1.
^{14}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.
^{15} The definition of W and U differ slightly from the ones introduced by the author previously [].
^{16}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
^{17} Alternatively, the action of a lossless beam splitter may be described by the matrix (

 



 



 



 

