K. Svozil
  
Institut für Theoretische Physik
Technische Universität Wien
Wiedner Hauptstraß e 8-10/136
A-1040 Vienna, Austria
e-mail: svozil@tph.tuwien.ac.at  
 
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 [1] and algorithmic information theory [2] as well as for database applications will only be shortly sketched.

Classical information theory (e.g., [3]) 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 t_A, thereby transmitting a signal ``+'' (``-'') via its perfectly correlated entangled partner in path 2 to a second observer back in time at t_B; thereby, t_A > t_B > t_S 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 [14] was translated by Gödel into arithmetic [15] to argue against a complete description of a formal system within that very system [18]. For instance, the gödelian sentence [19] claiming its own unprovability in a particular system appears undecidable within that very system.

This recursion theoretic terminology has to be translated into physics [20]. In particular, undecidability must be interpreted on the phenomenological level. Is there, for instance, a physical correspondent to a logical contradiction [21]? Can a particle, for example, be here and somewhere else ( º not here) [22]? 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 [23], exo- [24]) arena,'' in which a particular outcome could be deterministically accounted for. Yet, for an intrinsic observer who is embedded in the system [25], this level will be permanently inaccessible [26]. 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 t_A with regards to the measurement at t_A¢.

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 t<sub>A¢</sub>, A feels compelled to stimulate the opposite outcome ``-'' (``+'') at the later time t_A.

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 t<sub>B</sub>. 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 t_B 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 [44] and Peres [45], and also by the BDS/Feinberg/Recami [46,47,41] ``switching principle.'' Peres and Schulman, based on a model by Wheeler and Feynman [48], and subsequently Gatlin proposed to eliminate the feature of a perfect mirror reflection in t<sub>B</sub>. 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 t_B (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 [45] 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 [33]. 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 [18]).

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 [37] 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 [58]) coin [59]. 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 [60]. 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 [61]. 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.

References

[1]

K. Svozil, ``Quantum recursion theory,'' submitted.

[2]

K. Svozil, ``Halting probability amplitude of quantum computers,'' Journal of Universal Computer Science 1, nr. 3, 1-4 (March 1995); ``Quantum algorithmic information theory,'' e-print quant-ph/9510005 (URL: http://xxx.lanl.gov/ps/quant-ph/9510005).

[3]

R. W. Hamming, Coding and Information Theory, 2nd edn. (Prentice-Hall, Englewood Cliffs, New Jersey, 1980).

[4]

D. Z. Albert, Phys. Lett. 94A, 249 (1983).

[5]

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

[6]

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

[7]

A. Peres, Phys. Rev. A32, 3266 (1985).

[8]

P. Benioff, Ann. N.Y. Akad. Sci. 480, 475 (1986).

[9]

N. Margolus, Ann. N.Y. Akad. Sci. 480, 487 (1986).

[10]

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

[11]

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

[12]

A. Shimony, ``Controllable and uncontrollable non-locality'', in Procceedings of the International Symposiun on the Foundations of Quantum Mechanics, S. Kamefuchi et al., eds. (Physical Society of Japan, Tokyo, 1984), reprinted in A. Shimony, Search for a Naturalistic World View, Volume II (Cambridge University Press, Cambridge, 1993), p. 130.

[13]

A. Shimony, ``Events and Processes in the Quantum World'', in Quantum Concepts in Space and Time, R. Penrose and C. I. Isham, eds. (Clarendon Press, Oxford, 1986), reprinted in A. Shimony, Search for a Naturalistic World View, Volume II (Cambridge University Press, Cambridge, 1993), p. 140.

[14]

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). For more details, see A. R. Anderson, St. Paul's Epistle to Titus, in The Paradox of the Liar, R. L. Martin, ed. (Yale University Press, New Haven, 1970).

[15]

K. Gödel, Monatshefte für Mathematik und Physik 38, 173 (1931); English translation in [16] and in Davis, ref. [17].

[16]

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

[17]

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

[18]

The following citation is taken from K. Gödel's reply to a letter by A. W. Burks, reprinted in J. von Neumann's Theory of Self-Reproducing Automata, A. W. Burks, ed. (University of Illinois Press, Urbana, 1966), p. 55; see also S. Feferman, Philosophia Naturalis 21, 546 (1984), p. 554, ``¼ the fact that a complete epistemological description of a language A cannot be given in the same language A, because the concept of truth of sentences of A cannot be defined in A. It is this theorem which is the true reason for the existence of undecidable propositions in the formal systems containing arithmetic.''

[19]

K. R. Popper, Brit. J. Phil. Sci. 1, 117, 173 (1950).

[20]

Gödel's attitude towards the introduction of the incompleteness theorems into physics seems to have been a negative one [cf. J. A. Wheeler, private communication and J. Bernstein, Quantum Profiles (Princeton University Press, Princeton, 1991), pp. 140-141].

[21]

Hilbert was so angry about this question (possibly raised by Brouwer) that he dedicated a whole paragraph to a polemic in D. Hilbert, ``Über das Unendliche,'' Math. Ann. 95, 161-190 (1926).

[22]

In a double-slit experiment, the wave function Y is actually in a coherent superposition

Y = y(1)+ y(2) of the amplitude for the particle to go through slit 1 and slit 2.

[23]

K. Svozil, Europhys. Lett. 2, 83 (1986); Nuovo Cimento 96B, 127 (1986); and [39], Chap. 6.

[24]

O. E. Rössler, in Endophysics, in Real Brains, Artificial Minds, J. L. Casti and A. Karlquist, eds. (North-Holland, New York, 1987), p. 25; O. E. Rössler, in Endophysics, Die Welt des inneren Beobachters, P. Weibel, ed. (Merwe Verlag, Berlin, 1992).

[25]

T. Toffoli, ``The role of the observer in uniform systems'', in Applied General Systems Research, G. Klir, ed. (Plenum, New York, 1978).

[26]

The observer is situated, in O. E. Rössler's dictum, in a ``Cartesian prison''; cf. H. Atmanspacher and G. Dalenoort, eds., Inside Versus Outside (Springer, Berlin, 1994), p. 156.

[27]

J. Rothstein, Internat. J. Theoret. Phys. 21, 327 (1982).

[28]

A. Peres, Found. Phys. 15, 201 (1985).

[29]

St. Wolfram, Phys. Rev. Lett. 54, 735 (1985); Physica D10, 1 (1984); Rev. Mod. Phys. 55, 601 (1983).

[30]

Ch. D. Moore, Phys. Rev. Lett. 64, 2354 (1990).

[31]

A. C. Elitzur, Phys. Lett. A167, 335 (1992), as well as S. Popescu and D. Rohrlich, Found. Phys. 24, 379 (1994), refer to a talk of Professor Y. Aharonov delivered at the Einstein centennial.

[32]

A. Posiewnik, ``On inconsistency of the language of physics,'' University of Gdansk preprint, 1993.

[33]

K. Gödel, Rev. Mod. Phys. 21, 447 (1949): K. Gödel, ``A remark about the relationship between relativity theory and idealistic philosophy'', in Albert Einstein, Philosopher-Scientist, P. A. Schilpp, ed. (Open Court, Evanston, Ill., 1949), p. 555.

[34]

E. Recami, Found. Phys. 17, 239 (1987).

[35]

J. S. Bell, Physics 1, 195 (1964); J. S. Bell, Speakable and Unspeakable in Quantum Mechanics (Cambridge University Press, Cambridge, 1987).

[36]

D. Deutsch, Phys. Rev. D44, 3197 (1991).

[37]

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

[38]

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

[39]

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

[40]

For more detailed accounts of this paradox, which is sometimes referred to as Tolman's paradox, see R. C. Tolman, The Theory of Relativity of Motion (Berkeley, 1917), G. A. Benford, D. L. Book, and W. A. Newcomb, Phys. Rev. D2, 263 (1970).

[41]

E. Recami, Tachyons, Monopoles, and Related Topics (North-Holland, Amsterdam, 1978); Riv. Nuovo Cimento 9, 1 (1986); Found. Phys. 17, 239 (1987).

[42]

A. Peres and L. S. Schulman, Phys. Rev. D5, 2654 (1972).

[43]

A. Peres and L. S. Schulman, Internat. J. Theoret. Phys. 6, 377 (1972).

[44]

L. L. Gatlin, Internat. J. Theoret. Phys. 19, 25 (1980).

[45]

A. Peres, Found. Phys. 16, 573 (1986).

[46]

O. M. Bilaniuk, V. K. Deshpande, and E. C. G. Surdashan, Am. J. Phys. 30, 718 (1962).

[47]

G. Feinberg, Phys. Rev. 159, 1089 (1967).

[48]

J. A. Wheeler and R. P. Feynman, Rev. Mod. Phys. 21, 425 (1949).

[49]

E. C. G. Stückelberg, Helv. Phys. Acta 14, 322, 588 (1941).

[50]

R. P. Feynman, Quantum Electrodynamics (Benjamin, New York, 1961).

[51]

S. W. Hawking, Phys. Rev. D46, 603 (1992).

[52]

J. F. Woodward, Found. Phys. Lett. 8, 1 (1995).

[53]

In an abstract form, the above argument is the analogon to the fixed point or paradoxical combinator in combinatory logic; cf. H. B. Curry and R. Feys, Combinatory Logic (North-Holland, Amsterdam, 1958), p. 151 and 178, and H. P. Barendregt, The Lambda Calculus (rev. edn.) (North Holland, Amsterdam, 1984).

[54]

E. F. Moore, Gedanken Experiments on Sequential Machines, in Automata Studies, ed. by C. E. Shannon and J. McCarthy (Princeton University Press, Princeton, 1956).

[55]

D. Finkelstein and S. R. Finkelstein, Internat. J. Theoret. Phys. 22, 753 (1983).

[56]

I. Pitowsky, Phys. Rev. Lett. 48, 1299 (1982); Phys. Rev. D27, 2316 (1983); N. D. Mermin, Phys. Rev. Lett. 49, 1214 (1982); A. L. Macdonald, ibid., 1215 (1982); I. Pitowsky, ibid., 1216 (1982).

[57]

I. Pitowsky, Quantum Probability - Quantum Logic (Springer, Berlin, 1989).

[58]

K. Svozil, Phys. Lett. 140, 5 (1989).

[59]

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

[60]

Note that, unlike in fuzzy logic, |[1/( Ö2)],[1/( Ö2)] ñ is a probability amplitude rather than a probability for 0 and 1.

[61]

R. P. Feynman, Internat. J. Theoret. Phys. 21, 467 (1982).

Picture Omitted
Fig. 2

Picture Omitted