Institut für Theoretische Physik
Technische Universität Wien
Wiedner Hauptstraß e 8-10/136
A-1040 Vienna, Austria
Reveived July 5, 1995; revised September 1, 1995
The classical methods used by recursion theory and formal logic to block paradoxes do not work in quantum information theory. Since quantum information can exist as a coherent superposition of the classical ``yes'' and ``no'' states, certain tasks which are not conceivable in the classical setting can be performed in the quantum setting. Classical logical inconsistencies do not arise, since there exist fixed point states of the diagonalization operator. In particular, closed timelike curves need not be eliminated in the quantum setting, since they need not lead to the classical antinomies. Quantum information theory can also be subjected to the treatment of inconsistent information in databases and expert systems. It is suggested that any two pieces of contradicting information are stored and processed as coherent superposition. In order to be tractable, this strategy requires quantum computation.
Key words: time paradox, consitency of quantum mechanics, quantum fixed point operator, closed worldlines
This letter introduces two novel features of quantum information theory. Physically, it is shown how quantum information allows the consistent implementation of nonlocal correlations. Technically, a diagonalization operator is used to compute consistent fixed point solutions to classical ``paradoxical'' tasks. The implications for quantum recursion theory  and algorithmic information theory  as well as for database applications will only be shortly sketched.
Classical information theory (e.g., ) is based on the bit as fundamental atom. This classical bit, henceforth called cbit, is in one of two classical states. It is customary to use the symbols ``0'' and ``1'' as the names of these states.
In quantum information theory (cf. [4,5,6,7,8,9,10,11]), the most elementary unit of information, henceforth called qbit, may be physically represented by a coherent superposition of the two states |0ñ and |1ñ, which correspond to the symbols 0 and 1, respectively. The quantum bit states
In what follows we shall consider the hypothetical transmission of information backward in time. To be more specific, we shall use an EPR-type telegraph which uses entangled particles in a singlet state (i.e., the total angular momentum of the two particles is zero) as drawn in Fig. 1.
Fig. 1. Scheme of backward-in-time signalling by EPR-type telegraph. Two entangled particles (e.g., photons) are emitted from source the S. Assume (without loss of generality) that there is an observer A far from the source S, and an observer B close to S. The postulated controllability of outcomes in 1, mediated via 2, is used to transmit information. The flow of information is indicated by the arrow. ``·'' stands for the active mode; i.e., controllable outcome (preparation). ``°'' stands for the passive mode; i.e., measurement. The two signs are drawn on top and at bottom to indicate the opposite orientation (relative angle p) of the measurement apparata of the two observers A and B.
The apparatus is tuned to convey perfect correlations of the direction of angular momentum labeled by ``+'' and ``-''; i.e., the outcomes are either + + or - -. (Perfect correlations can be achieved by choosing a relative angle of measurement of p.) The (unphysical) assumption necessary for signalling backwards in time is that on one side, say for particles in path 1, the outcome can be controlled. This means that it will be assumed possible to produce a particle with, say, direction of angular momentum ``+'' (``-'') in the path 1 at tA, thereby transmitting a signal ``+'' (``-'') via its perfectly correlated entangled partner in path 2 to a second observer back in time at tB; thereby, tA > tB > tS but otherwise arbitrary.
An alternative setup for backward in time signalling operates with parameter dependence [12,13]. There, the (unphysical) assumption is that the measurement outcomes in one path depend on the setting of the measurement angle ( = the parameter) in the other path. From now on, we shall use the term outcome control to refer also to parameter dependence.
We shall make use of the EPR-type telegraph to construct a time paradox and argue against and outcome controllability in any form. In a similar manner, the liar paradox  was translated by Gödel into arithmetic  to argue against a complete description of a formal system within that very system . For instance, the gödelian sentence  claiming its own unprovability in a particular system appears undecidable within that very system.
This recursion theoretic terminology has to be translated into physics . In particular, undecidability must be interpreted on the phenomenological level. Is there, for instance, a physical correspondent to a logical contradiction ? Can a particle, for example, be here and somewhere else ( º not here) ? On the phenomenological level, the answer is no. To put it pointedly: there is no such thing as an inconsistent phenomenon. In a yes-no experiment which can have two possible outcomes, only one of these outcomes will actually be measured. In contradistinction, a theoretical description might allow the consistent ``existence'' of mutually exclusive states only if it is indeterministic (probabilistic), thereby implementing undecidability. One might even conceive of a hierarchically organized scenario with an inside/outside distinction. In such a setup, there might exist a ``hidden parameter (extrinsic , exo- ) arena,'' in which a particular outcome could be deterministically accounted for. Yet, for an intrinsic observer who is embedded in the system , this level will be permanently inaccessible . As will be argued below, quantum mechanics implements undecidability both by the superposition principle and by the postulate of randomness of certain outcomes (i.e., the ``wave function collapse''). Related arguments have been put forward in [19,27,28,29,30,31,32].
Consider two backward-in-time signalling EPR-type telegraphs of the above type arranged as drawn in Fig. 2.
Fig. 2. Time paradox. Two backward-in-time signalling devices are used here, but only one would be necessary, the other could be subluminal quantum information channel. The important point is the outcome controllability at tA with regards to the measurement at tA¢.
Physically, the flow of information is mediated via the two entangled pairs in paths 1-2 and 3-4. An information in 2 is perfectly mirrored by M in 3. By this instrument, some agent A (e.g., computer, observer), which is given the power of outcome control, can exchange information with itself on closed timelike lines [33,34,35,36]. It is thereby tacitly assumed that, stated pointedly, by ``free will,'' agent A can choose the outcome. In the following, A shall be confronted with the following paradoxical task. Whenever A registers the information ``+'' (``-'') at time tA¢, A feels compelled to stimulate the opposite outcome ``-'' (``+'') at the later time tA.
Before discussing the paradox, let us consider the two states |0ñ º ``-'' and |1ñ º ``+'' which are accessible to A. These states can be the basis of a cbit with the identification of the symbols ``0'' and ``1'' for |0ñ and |1ñ, respectively. Quantum mechanically any coherent superposition of them is allowed. A's paradoxical task can be formalized by a unitary evolution operator
[^D] as follows
[^D] will be called diagonalization operator, despite the fact that its only nonvanishing components are off-diagonal. (Notice that A's task would be perfectly consistent if there were no ``bit switch'' and if thus
[^D] = diag(1,1).)
The paradoxical feature of the construction [40,41] reveals itself in the following question: what happens to A? In particular: what does A register and send?
Let us first consider these questions from a classical perspective. Classically, the particles with which A operates can only be in one of two possible states, namely in |0ñ or in |1ñ, corresponding to the classical bit states. By measuring the particle in beam 4, A gets either the outcome ``+'' or ``-''. In both cases, the agent A is lead to a complete contradiction.
For, if A receives ``+'', corresponding to cbit state 1, A is obliged to send out ``-'', corresponding to cbit state 0 (A has been assumed to be able to control the outcomes in beam 1). Due to the perfect EPR-correlations, the partner particle in beam 2 is registered as ``-'' at the mirror at time tB. By controlling the outcome in beam 3, this mirrored cbit can again be sent backwards in time, where ``-'' is received by A via a measurement of the particle in beam 4. This, however, contradicts the initial assumption that the outcome in beam 4 is ``+''.
On the other hand, if A receives ``-'', corresponding to cbit state 0, A is obliged to send out ``+'', corresponding to cbit state 1; yet, since at tB the cbit is just reflected as described above, A should have received ``+''. Thus classically, agent A is in an inescapable dilemma.
The defense strategy in formal logic and classical recursion theory
against such inconsistencies is to avoid the appearance of a paradox by claiming (stronger: requiring) overall consistency, resulting in no-go theorems; i.e., in the postulate of the impossibility of any operational method, procedure or device which would have the potentiality to cause a paradox. (Among the many impossible objects giving rise to paradoxes are such seemingly innocent devices as a ``halting algorithm'' computing whether or not another arbitrary computable algorithm produces a particular output; or an algorithm identifying another arbitrary algorithm by input-output experiments.)
We shortly discuss some classical defense strategies against such time paradoxes. (No claim of completeness is made here.) Let us first concentrate on the implicit assumption that there is an objective distinction between cause and effect. This has been addressed by Peres and Schulman [42,43], Gatlin  and Peres , and also by the BDS/Feinberg/Recami [46,47,41] ``switching principle.'' Peres and Schulman, based on a model by Wheeler and Feynman , and subsequently Gatlin proposed to eliminate the feature of a perfect mirror reflection in tB. Thereby, the mirror responses indeterministically. If the signal is mirrored by a conscious being, then the responses might originate from ``free will.'' Gatlin proposes to eliminate the paradox by assuming that the mirror at time tB (or, equivalently, some decision-making agent in the backward-in-time signalling channel), has no causal connection to the source A. This is in essence a denial that a certain type of information can be transmitted backwards in time. The analysis of Peres and Schulman yields a consistent solution for the equation of motion at the price of determinacy, thereby eliminating the original assumption of indeterminism and the existence of ``free will,'' as well as of an objective distinction between cause and effect. In particular, Peres  suggests that, to the observer, certain processes and decisions appear completely random, but may actually be completely determined by very complex yet deterministic processes. The observer's experience that certain decisions originate in ``free will'' might be an illusion. Thus, as a consequence of the subjective evaluation of the observer, cause and effect merely appear objectively distinct. This has also been Gödel's resolution of time paradoxes . A related ``switching principle'' approach [46,47,41] is based on the standard quantum field theoretic reinterpretation of negative energy particles moving forward in time as positive energy particles moving backward in time, which in turn are reinterpreted [49,50] as positive energy antiparticles moving forward in time with reversed charges and velocities. In this process, any emission (cause) is reinterpreted as absorption (effect) and vice versa.
Another possibility to block time paradoxes is the postulate of the impossibility of any backward-in-time information flow or, more specifically, the impossibility of closed timelike lines. This view seems to have been adopted by Hawking, who calls it the ``chronology protection conjecture'' [51,52].
Notice that one feature of the backward-in-time information flow has been outcome controllability. Therefore, a third option, the postulate of the impossibility of outcome controllability eliminates the time paradox. Hence, the time paradox - encoded by the diagonalization argument - can be used against outcome controllability, resulting in an intrinsic randomness of the individual outcomes. This view resembles the Peres-Schulman and the Gatlin scheme - in some sense it reconciles both schemes - but emphasizes the hierarchical structure originating from an inside/outside distinction: Whereas it might be possible to conceive the whole dynamics deterministically from the outside, the phenomena might remain principally unpredictable from within. If the ``phenomenologic power'' - the things which are physically operational - would become too strong, the world would become inconsistent.
Quantum mechanics implements exactly that kind of recursion theoretic undecidability argument; yet in a form which is not common in recursion theory. Observe that the paradox is resolved when A is allowed a nonclassical qbit of information. In particular, A's task can consistently be performed if it inputs a qbit corresponding to the fixed point state of [^D]; i.e.,
We close the discussion on the consistent use of paradoxes in physics with a few comments. First, it is important to recognize that the above considerations have no immediate bearing on quantum complementarity. In the author's opinion, complementarity is a general feature of the intrinsic perception of computer-generated universes, which is realizable already at a very elementary pre-diagonalization level [54,55,39]; i.e., without the requirement of computational universality or its arithmetic equivalent.
As has been pointed out before, the above argument remains valid for any conceivable (local or nonlocal [56,57]) hidden variable theory. The consistency of the physical phenomenology requires that hidden variables remain inaccessible to an intrinsic observer. Pointedly stated, from an intrinsic, operational point of view, when re-interpreted properly, a paradox marks the appearance of uncertainty and uncontrollability (cf. a statement by Gödel ).
As remote the above considerations may appear from any application, they are relevant for the treatment of inconsistencies in general and inconsistent database management in particular. For instance, a similar treatment of the halting problem  for a quantum computer leads to the conclusion that the quantum recursion theoretic ``solution'' of the halting problem reduces to the tossing of a fair (quantum ) coin . Another, less abstract, application for quantum information theory is the handling of inconsistent information in databases and expert systems. Thereby, two contradicting cbits of information |añ and |bñ are resolved by the qbit
|1/ Ö2,1/ Ö2 ñ = (1/ Ö2)(|añ+ |bñ). Throughout the rest of the computation the coherence is maintained . After the processing, the result is obtained by a measurement. As an consequence, the contradicting sectors of the knowledge base need not be totally eliminated while at the same time the undesirable inconsistencies are avoided. However, the processing of qbits requires 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.
Acknowledgments: Related topics were vigorously discussed in seminars and regular Viennese coffee house sessions with Anton Zeilinger (some time ago), Johann Sumhammer and Günther Krenn. Günther Krenn took the pain to read, contribute and comment to several versions of the manuscript. Three anonymous referees suggested many revisions. Nonetheless, any blame should remain solely with the author.
Y = y(1)+ y(2) of the amplitude for the particle to go through slit 1 and slit 2.