Quantum information: the new frontier

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

Abstract

1  Is Nature telling us something?

Friends in experimental physics tell me that the essence of their observations are clicks in some counter. There is a click or there is none. This is experimental physics in a nutshell. There may be some magic in properly designing experiments and some magic in interpreting those clicks, but that is all there is.

A single click represents some elementary physical proposition. It is also an answer to a question which might not even have been posed consciously. It is tempting to state that ``Nature wants to tell us something'' with these clicks about some formal structures, symmetries, music or numbers beyond the phenomena. Maybe that is the case, and most physicists tend to believe so; but maybe we are just observing crap, erratic emanations devoid of any meaning [1].

Anyway, we have to deal with those clicks, and one way to deal with them is to interpret them as information. For example, in an experimental input-output scheme, information is received, transformed and communicated by the system. One might think of a physical system as a black box with an input and an output interface [2]. The experimenter inputs some information and the black box responds with some information as output.

If we are dealing with mechanical systems, all the conceivable gadgets inside the black box can be isomorphically translated into a sheet or a tape of paper on which finite computations are performed and vice versa. This was Turing's insight.

But if the black box is essentially quantum driven, then the paper metaphor becomes questionable. The quantum is illusive and highly nonintuitive. In the words of John Archibald Wheeler, one is capturing a ``smoky [[quantum]] dragon'' [3] inside the black box. Or, in Danny Greenberger's dictum, ``quantum mechanics is magic'' [4]. In addition, quantized systems such as the quantized electromagnetic field have ``more'' degrees of freedom as compared to their classical correspondents. Therefore, any isomorphic translation into classical mechanistic devices remains very expensive in terms of paper consumption, at best. To make things worse, under certain reasonable side assumption, it can be proven that a complete ``mechanical'' paper set of all quantum answers is inconsistent.

Because of these novel non-classical features it is so exiting to pursue the quantum information concept. But even if we look aside and do not want to be bothered with the quantum, the quantum catches up on us: due to the progressing miniaturization of circuits forming logical gates, we shall soon be confronted with quantum phenomena there. In the following, some of the recent developments are reviewed below; and some speculations and prospects are mentioned.

2  Formalization of quantum information

In order to be applicable, any formalization of information has to be based on its proper realization in physical terms; i.e., as states of a physical system. In this view, information theory is part of physics; or conversely, physics is part of information theory. And just as the classical bit represents the distinction between two classical physical states, the quantum bit, henceforth often abbreviated by the term `qubit,' represents the conceivable states of the most elementary quantized system. As we shall see, qubits feature quantum mechanics `in a nutshell.' Quantum bits are more general structures than classical bits. That is, classical bits can be represented as the limit of qubits, but not vice versa.

Classical information theory 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 # ( t) = 1 and # ( f) = 0 (# (s) stands for the code of s). The states can, for instance, be realized by some condenser which is discharged ( º cbit state 0) or charged ( º cbit state 1).

In quantum information theory (see Appendix A for a brief outline of quantum mechanics) qubits can be physically represented by a `coherent superposition' of the two orthonormal¹ states t and f. The qubit states

xa = at+bf

(1)

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

What is a coherent superposition? Formally it is just a sum of two elements (representing quantum states) in Hilbert space, which results in an element (a quantum state) again per definition. So, formally we are on the safe side. Informally speaking, a coherent superposition of two different and classically distinct states contains them both. Now classically this sounds like outright nonsense! A classical bit cannot be true and false at the same time. This would be inconsistent, and inconsistencies in physics sound as absurd as in mathematics [5].

Yet, quantum mechanics (so far consistently) achieves the implementation of classically inconsistent information into a single quantum bit. Why is that possible? Maybe we get a better feeling for this when we take up Erwin Schrödinger's interpretation of the quantum wave function (in our terms: of the qubit states) as a sort of ``catalogue of expectation values'' [6]. That is, the qubit appears to be a representation of the state of our knowledge about a physical system rather than what may be called ``its true state.'' (Indeed we have to be extremely careful here with what we say. The straightforward classical pretension that quantum systems must have ``a true state'', albeit hidden to us, yields to outright contradictions!)

Why have I mentioned quantum superpositions here? Because they lie at the heart of quantum parallelism. And quantum parallelism lies at the heart of the quantum speedups which caused so much hype recently.

The coding of qubits is discussed in Appendix C.

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

By contrast, to mention just a few nonclassical properties of qubits:

• Qubits are contextual [7]. A quantum bit may appear different, depending on the method by which it is inferred.

• Qubits cannot be copied or ``cloned'' [8,9,10,11,12,13]. This due to the fact that the quantum evolution is reversible, i.e., one-to-one.

• Qubits do not necessarily satisfy classical tautologies such as the distributive law [14,15].

• Qubits obey quantum logic [16] which is different from classical logic.

• Qubits are coherent superpositions of classically distinct, contradicting information.

• Qubits are subject to complementarity.

3  Complementarity and quantum cryptography

Before we proceed to quantum computing, which makes heavy use of the possibility to superpose classically distinct information, we shall mention an area of quantum information theory which has already matured to the point where the applications have almost become commercially available: quantum cryptography. At the moment, this might be seen as the ``killer app'' of quantum information theory.

Quantum cryptography (for a detailed review see [17]) is based on the quantum mechanical feature of complementarity. A formalization of quantum complementarity has been attempted by Edward Moore [18] who started finite automata theory with this. (Recent results are contained in Ref. [19] and [20]; see also Appendix B.)

Informally speaking, quantum complementarity stands for the principal impossibility to measure two observables at the same time with arbitrary position. If you decide to precisely measure the first observable, you ``loose control'' over the second one and vice versa. By measuring one observable, the state of the system undergoes a ``state reduction'' or, expressed differently, ``the wave function collapses'' and becomes different from the original one. This randomizes a subsequent measurement of the second, complementary observable: in performing the subsequent measurement, one obtains some measurement results (i.e., clicks, you remember?), but they dont tell us much about the original qubit, they are unusable crap. There is no other way of recoving the original state than by completely ``undoing'' the first measurement in such a way that no trace is left of the previous measurement result; not even a copy of the ``classical measurement''² result!

So how can this quantum property of complentarity can be put to use in cryptography? The answer is straightforward (if one knows it already): By taking advantage of complementarity, the sender ``Alice'' of a secret and the receiver ``Bob'' are able to monitor the secure quantum communication channel and to know when an eavesdropper is present.

This can be done as follows. Assume that Alice sends Bob a qubit and an eavesdropper is present. This eavesdropper is in an inescapable dilemma: neither can the qubit be copied, nor can it be measured. The former case is forbidden in quantum information theory and the letter case would result in a state reduction which modifies Alice's qubit to the point where it is nonsense for Bob. Bob and Alice can realize this by comparing some of their results over a classical (insecure) channel.³ The exact protocol can for instance be found in [17]. Another scheme [21] operates with entangled pairs of qubits. Here entanglement means that whatever measurement of a particular type is performed on one qubit, if you perform the same measurement on the other qubit of the pair, the result is the same.

Actually, in the real world, the communication over the insecure classical channel has to go back and forth, and they have to constantly compare a certain amount of their measured qubits in order to be able to assure a guaranteed amount of certainty that no eavesdropper is present. That is by no means trivial [22]. But besides this necessary overhead, the quantum channel can be certified to be secure, at least up to some desired amount of certainty and up to the point where someone comes up with a theory which is ``better than quantum mechanics'' and which circumvents complementarity somehow. Of course, the contemporaries always believe and assure the authorities that there will never be such a theory!

Quantum cryptographic schemes of the above type have already been demonstrated to work for distances of 1000m (and longer) and net key sizes (after error correction) of 59000 Bits at sustained (105 s) production rates of 850 Bits/s [23]. Yet there is no commercially available solution so far.

4  Quantum computing

Quantum computers operate with qubits. We have dealt with qubits already. Now what about the operation of quantum computers on qubits? We have to find something similar than Turing's ``paper-and-pencil-operations'' on paper or tape. The most natural candidate for a formalization is the unitary time evolution of the quantum states. This is all there is (maybe besides measurement [24]), because there is nothing beyond the unitary time evolution. Unitary operators stand for generalized rotations in complex Hilbert spaces. Therefore, a universal quantum computer can just be represented by the most general unitary operator!

That is a straightforward concept: given a finite dimensional Hilbert space of, say, dimension n, then the most general unitary operator U(n) can for instance be parameterized by composition of unitary operations in two (sub)dimensions U(2) [25]. Now we all know how U(2) looks like (cf. Appendix D), so we know how U(n) looks like. Hence we all know how to properly formalize a universal quantum computer!

This looks simple enough, but where is the advantage? Of course one immediate answer is that it is perfectly all right to simulate a quantized system with a quantum computer - we all know that every system is a perfect copy of itself!

But that is not the whole story. What is really challenging here is that we may be able to use quantum parallelism for speedups. And, as mentioned already, at the heart of quantum parallelism is the superposition principle and quantum entanglement. Superposition enables the quantum programmer to ``squeeze'' 2<sup>N</sup> classical bits into N qubits. In processing 1 qubit state at+bf, the computer processes 2 classical bit states t and f at once. In processing N qubit states, the computer may be able to processes 2<sup>N</sup> classical bit states at once. Many researchers in quantum computing interpret this (in the so-called ``Everett interpretation of quantum mechanics'') as an indication that 2^N seperate computer run in 2^N seperate worlds (one computer in each world); thereby running through each one of the computational passes in parallel. That might certainly be a big advantage as compared to a classical routine which might only be able to process the cases consecutively, one after the other.

There are indeed indications that speedups are possible. The most prominent examples are Shor's quantum algorithm for prime factoring [26,27] and Grover's search algorithm [28] for a single item satisfying a given condition in an unsorted database. A detailed review of the suggested quantum algorithms exceeds the scope of this brief discussion and can for instance be found in Gruska's book [29].

One fundamental feature of the unitary evolution is its bijectivity, its one-to-oneness. This is the reason why copying is not allowed, but this is also the reason why there is no big waste basked where information vanishis into oblivion or nirvana forever. In a quantum computer, one and the same ``message'' is constantly permutated. It always remains the same but expresses itself through different forms. Information is neither created nor discarded but remains constant at all times.⁴

Is there a price to be paid for parallelism? Let me just mention one important problem here: the problem of the readout of the result. This is no issue in classical computation. But in quantum computation, to use the Everett metaphor, it is by no means trivial how the many parallel entangled universes communicate with each other in such a way that the classical result can be properly communicated. In many cases one has to make sure that, through positive interference, the proper probability amplitudes indicating this result build up. One may even speculate that there is no sufficient buildup of the states if the problem allows for many nonunique solutions [30,31].

Another problem is the physical overhead which has to be invested in order for the system to remain "quantum" and not turn classical [32]. One may speculate that the necessary equipment to process more qubits grows exponentially with the number of qubits. If that would be the case, then the advantages of quantum parallelism would be essentially nullified.

5  Summary and outlook

Let me close with a few observations. So far, quantum information theory has applied the quantum features of complementarity, entanglement and quantum parallelism to more or less real-world applications. Certain other quantum features such as contextuality have not been put to use so far.

There are good prospects for quantum computing; if not for other reasons but because our computer parts will finally reach the quantum domain. We may be just at the very beginning, having conceived the quantum analogies of classical tubes (e.g., quantum optical devices). Maybe in the near future someone comes up with a revolutionary design such as a ``quantum transistor'' which will radically change the technology of information processing.

This is a very exciting and challenging new field of physics and computer sciences.

Appendix A: All (and probably more that) you ever wanted to know about quantum mechanics

``Quantization'' has been introduced by Max Planck around 1900 [33,34,35]. In a courageous, bold step Planck assumed a discretization of the total energy U<sub>N</sub> of N linear oscillators (``Resonatoren''),

UN = Pe Î { 0,e,2e,3e,4e,¼},

where P Î N₀ is zero or a positive integer and e stands for the smallest quantum of energy. e is a linear function of frequency w and proportional to Planck's fundamental constant (^h/_2p) » 10^-34 Js; i.e.,

e = (h/2p) w.

That was a bold step in a time of the predominant continuum models of classical mechanics.

In extension of Planck's discretized resonator energy model, Einstein [36] proposed a quantization of the electromagnetic field. According to the light quantum hypothesis, energy in an electric field mode characterized by the frequency w can be produced, absorbed and exchanged only in a discrete number n of ``lumps'' or ``quanta'' or ``photons''

En = n(h/2p) w ,  n = 0,1,2,3,¼  .

The following is a very brief introduction to the principles of quantum mechanics for logicians and computer scientists, as well as a reminder for physicists.⁵ To avoid a shock from a too early exposure to ``exotic'' nomenclature prevalent in physics - the Dirac bra-ket notation - the notation of Dunford-Schwartz [50] is adopted.⁶

Quantum mechanics, just as classical mechanics, can be formalized in terms of a linear space structure, in particular by Hilbert spaces [46]. That is, all objects of quantum physics, in particular the ones used by quantum logic, ought to be expressed in terms of objects based on concepts of Hilbert space theory-scalar products, linear summations, subspaces, operators, measures and so on.

Unless stated differently, only finite-dimensional Hilbert spaces are considered.⁷

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

We shall make the following identifications between physical and theoretical objects (a caveat: this is an incomplete list).

(0)

The dimension of the Hilbert space corresponds to the number of degrees of freedom.

(I)

A pure physical state x is represented either by the one-dimensional linear subspace (closed linear manifold) \sp (x) = {y | y = ax,  a Î C,  x Î H} spanned by a (normalized) vector x of the Hilbert space H or by the orthogonal projection operator E_x onto \sp (x). Thus, a vector x Î H represents a pure physical state.

Every one-dimensional projection E_x onto a one-dimensional linear subspace \sp (x) spanned by x Î H can be represented by the dyadic product E_x = |x)(x|.

If two nonparallel vectors x,y Î H represent pure physical states, their vector sum z = x+y Î H is again a vector representing a pure physical state. This state z is called the superposition of state x and y.⁸

Elements b_i,b_j Î H of the set of orthonormal base vectors satisfy (b_i, b_j) = d_ij, where d_ij = {

1	if i = j
0	if i ¹ j

is the Kronecker delta function. Any pure state x can be written as a linear combination of the set of orthonormal base vectors {b₁,b₂,¼}, i.e., x = å_{i = 1}ⁿ b_i b_i, where n is the dimension of H and b_i = (b_i,x) Î C. In the Dirac bra-ket notation, unity is given by 1 = å_{i = 1}ⁿ |b_i )( b_i|.

In the nonpure state case, the system is characterized by the density operator r, which is nonnegative and of trace class.⁹ If the system is in a nonpure state, then the preparation procedure does not specify the decomposition into projection operators (depending on the choice of basis) precisely. r can be brought into its spectral form r = å_{i = 1}ⁿ P_i E_i, where E_i are projection operators and the P_i's are the associated probabilities (nondegenerate case¹⁰).

(II)

Observables A are represented by hermitian operators A on the Hilbert space H such that (Ax,y) = (x,Ay) for all x,y Î H. (Observables and their corresponding operators are identified.) In matrix notation, the adjoint matrix A^f is the complex conjugate of the transposed matrix of A; i.e., (A^f)_ij = (A^* )_ji. Hermiticity means that (A^f)_ij = A_ij.

Any hermitian operator has a spectral representation A = å_{i = 1}ⁿ a_i E_i, where the E_i's are orthogonal projection operators onto the orthonormal eigenvectors a_i of A (nondegenerate case).

Note that the projection operators, as well as their corresponding vectors and subspaces, have a double rôle as pure state and elementary proposition (that the system is in that pure state).

Observables are said to be compatible or comeasurable if they can be defined simultaneously with arbitrary accuracy. Compatible observables are polynomials (Borel measurable functions in the infinite dimensional case) of a single ``Ur''-observable.

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. In this case, the hermitian matrices A and B can be simultaneously diagonalized, symbolizing that the observables corresponding to A and B are simultaneously measurable.¹¹

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

Actually, one can also measure normal operators N which can be decomposed into the sum of two commuting operators A,B according to N = A+iB, with [A,B] = 0.

(III)

The result of any single measurement of the observable A on an arbitrary state x Î H can only be one of the real eigenvalues of the corresponding hermitian operator A. (Actually, one can also measure normal operators which can be decomposed into the sum of two commuting If x = b₁a₁+¼+b_ia_i+¼+b_na_n is in a superposition of eigenstates { a₁,¼,a_n} of A, the particular outcome of any such single measurement is indeterministic; i.e., it cannot be predicted with certainty. As a result of the measurement, the system is in the state a_i which corresponds to the associated real-valued eigenvalue a_i which is the measurement outcome; i.e.,

x® ai .

The arrow symbol ``®'' denotes an irreversible measurement; usually interpreted as a ``transition'' or ``reduction'' of the state due to an irreversible interaction of the microphysical quantum system with a classical, macroscopic measurement apparatus. This ``reduction'' has given rise to speculations concerning the ``collapse of the wave function (state).''

As has been argued recently (e.g., by Greenberger and YaSin [54], and by Herzog, Kwiat, Weinfurter and Zeilinger [55]), it is possible to reconstruct the state of the physical system before the measurement; i.e., to ``reverse the collapse of the wave function,'' if the process of measurement is reversible. After this reconstruction, no information about the measurement is left, not even in principle.

How did Schrödinger, the creator of wave mechanics, perceive the quantum physical state, or, more specifically, the y-function? In his 1935 paper ``Die gegenwärtige Situation in der Quantenmechanik'' (``The present situation in quantum mechanics'' [6]), Schrödinger states,¹²

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

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

(IV)

The probability P_x(y) to find a system represented by a normalized pure state x in some normalized pure state y is given by

Px(y) = |(x,y) |2 ,     |x|2 = |y|2 = 1.

In the nonpure state case, The probability P(y) to find a system characterized by r in a pure state associated with a projection operator E_y is

Pr (y) = trace(rEy).

(V)

The average value or expectation value of an observable A represented by a hermitian operator A in the normalized pure state x is given by

áAñx = n å i = 1  ai|(x,ai) |2,     |x|2 = |ai|2 = 1.

The average value or expectation value of an observable A represented by a hermitian operator A in the nonpure state r is given by

áAñ = trace(rA) = n å i = 1  aitrace(rEi).

(VI)

The dynamical law or equation of motion between subsequent, irreversible, measurements can be written in the form x (t) = Ux (t₀) , where U^f = U^-1 (``f stands for transposition and complex conjugation) is a linear unitary evolution operator.<sup>13</sup> Per definition, this evolution is reversible; i.e., bijective, one-to-one. So, in quantum mechanics we have to distinguish between unitary, reversible evolution of the system inbetween measurements, and the ``collapse of the wave function'' at an irreversible measurement.

The Schrödinger equation i(^h/_2p) [(¶)/(¶t)] y(t) = H y(t) for some state y is obtained by identifying U with U = e^-iHt/(h/_2p) , where H is a hermitian Hamiltonian (``energy'') operator, by partially differentiating the equation of motion with respect to the time variable t; i.e., [(¶)/(¶t)] y(t) = - [iH/((^h/_2p))]e^-iHt/(h/_2p)y(t₀ ) = - [iH/((^h/_2p) )] y(t). In terms of the set of orthonormal base vectors { b₁, b₂, ¼}, the Schrödinger equation can be written as i(^h/_2p) [(¶)/(¶t)] ( b_i , y(t) ) = å_jH_ij( b_j, y(t) ).

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

Appendix B: Complementarity and automaton logic

A systematic, formal investigation of the black box system or any finite input/output system can be given by finite automata. Indeed, the study of finite automata was motivated from the very beginning by their analogy to quantum systems [18]. Finite automata are universal with respect to the class of computable functions. That is, universal networks of automata can compute any effectively (Turing-) computable function. Conversely, any feature emerging from finite automata is reflected by any other universal computational device. In this sense, they are ``robust''. All rationally conceivable finite games can be modeled by finite automata.

Computational complementarity, as it is sometimes called [56], can be introduced as a game between Alice and Bob. The rules of the game are as follows. Before the actual game, Alice gives Bob all he needs to know about the intrinsic workings of the automaton. For example, Alice tells Bob, ``if the automaton is in state 1 and you input the symbol 2, then the automaton will make a transition into state 2 and output the symbol 0,'' and so on. Then Alice presents Bob a black box which contains a realization of the automaton. Attached to the black box are two interfaces: a keyboard for the input of symbols, and an output display, on which the output symbols appear. Again, no other interfaces are allowed. In particular, Bob is not allowed to ``screw the box open.''

Suppose now that Alice chooses some initial state of the automaton. She may either throw a dice, or she may make clever choices using some formalized system. In any case, Alice does not tell Bob about her choice. All Bob has at his disposal are the input-output interfaces.

Bob's goal is to find out which state Alice has chosen. Alice's goal is to fool Bob.

Bob may simply guess or rely on his luck by throwing a dice. But Bob can also perform clever input-output experiments and analyze his data in order to find out. Bob wins if he gives the correct answer. Alice wins if Bob's guess is incorrect. (So, Alice has to be really mean and select worst-case scenarios).

Suppose that Bob tries very hard. Is cleverness sufficient? Will Bob always be able to uniquely determine the initial automaton state?

The answer to that question is ``no.'' The reason is that there may be situations when Bob's input causes an irreversible transition into a black box state which does not allow any further queries about the initial state.

What has been introduced here as a game between Alice and Bob is what the mathematicians have called the state identification problem [18,57,58,59]: given a finite deterministic automaton, the task is to locate an unknown initial state. Thereby it is assumed that only a single automaton copy is available for inspection. That is, no second, identical, example of the automaton can be used for further examination. Alternatively, one may think of it as choosing at random a single automaton from a collection of automata in an ensemble differing only by their initial state. The task then is to find out which was the initial state of the chosen automaton.

The logico-algebraic structure of the state identification problem has been introduced in [60], and subsequently studied in [60,61,62,63,64,65,66,19]. We shall deal with it next.

Step 1: Computation of the experimental equivalence classes.

Suppose again that the only unknown feature of an automaton is its initial state; all else is known. The automaton is presented in a black box, with input and output interfaces. The task in this complementary game is to find (partial) information about the initial state of the automaton [18].

To illustrate this, consider the Mealy automaton M_s discussed above. Input/output experiments can be performed by the input of just one symbol i (in this example, more inputs yield no finer partitions). Suppose again that Bob does not know the automaton's initial state. So, Bob has to choose between the input of symbols 1,2, or 3. If Bob inputs, say, symbol 1, then he obtains a definite answer whether the automaton was in state 1 - corresponding to output 1; or whether the automaton was not in state 1 - corresponding to output 0. The latter proposition ``not 1'' can be identified with the proposition that the automaton was either in state 2 or in state 3.

Likewise, if Bob inputs symbol 2, he obtains a definite answer whether the automaton was in state 2 - corresponding to output 1; or whether the automaton was not in state 2 - corresponding to output 0. The latter proposition ``not 2'' can be identified with the proposition that the automaton was either in state 1 or in state 3. Finally, if Bob inputs symbol 3, he obtains a definite answer whether the automaton was in state 3 - corresponding to output 1; or whether the automaton was not in state 3 - corresponding to output 0. The latter proposition ``not 3'' can be identified with the proposition that the automaton was either in state 1 or in state 2.

Recall that Bob can actually perform only one of these input-output experiments. This experiment will irreversibly destroy the initial automaton state (with the exception of a ``hit''; i.e., of output 1). Let us thus describe the three possible types of experiment as follows.

·

Bob inputs the symbol 1.

·

Bob inputs the symbol 2.

·

Bob inputs the symbol 3.

The corresponding observable propositions are:

p_{1} º {1}: On input 1, Bob receives the output symbol 1.

p_{2,3} º {2,3}: On input 1, Bob receives the output symbol 0.

p_{2} º {2}: On input 2, Bob receives the output symbol 1.

p_{1,3} º {1,3}: On input 2, Bob receives the output symbol 0.

p_{3} º {3}: On input 3, Bob receives the output symbol 1.

p_{1,2} º {1,2}: On input 3, Bob receives the output symbol 0.

Note that, in particular, p_{1},p_{2},p_{3} are not comeasurable. Note also that, for e_ijk ¹ 0, p_{i}¢ = p_{j,k} and p_{j,k} = p_{i}¢; or equivalently {i}¢ = {j,k} and {j,k} = {i}¢.

In that way, we naturally arrive at the notion of a partitioning of automaton states according to the information obtained from input/output experiments. Every element of the partition stands for the proposition that the automaton is in (one of) the state(s) contained in that partition. Every partition corresponds to a quasi-classical Boolean block. Let us denote by v(x) the block corresponding to input (sequence) x. Then we obtain

no input:

v(Æ) = {{1,2,3}},

one input symbol:

input		output		output
		1		0
v(1)	=	{{1}	,	{2,3}}
v(2)	=	{{2}	,	{1,3}}
v(3)	=	{{3}	,	{1,2}}.

Conventionally, only the finest partitions are included into the set of state partitions.

Step 2: Pasting of the partitions.

Just as in quantum logic, the automaton propositional calculus and the associated partition logic is the pasting of all the blocks of partitions v(i) on the atomic level. That is, elements of two blocks are identified if and only if the corresponding atoms are identical.

The automaton partition logic based on atomic pastings differs from previous approaches [60,61,62,63,64,65,66,19]. Atomic pasting guarantees that there is no mixing of elements belonging to two different order levels. Such confusions can give rise to the nontransitivity of the order relation [60] in cases where both p® q and q® r are operational but incompatible, i.e., complementary, and hence p® r is not operational.

For the Mealy automaton M_s discussed above, the pasting renders just the horizontal sum - only the least and greatest elements 0,1 of each 2² is identified-and one obtains a ``Chinese lantern'' lattice MO₃. The Hasse diagram of the propositional calculus is drawn in Figure 1.

Let us give a formal definition for the procedures sketched so far. Assume a set S and a family of partitions B of S. Every partition E Î B can be identified with a Boolean algebra B_E in a natural way by identifying the elements of the partition with the atoms of the Boolean algebra. The pasting of the Boolean algebras B_E,E Î B on the atomic level is called a partition logic, denoted by (S,B).

The logical structure of the complementarity game (initial-state identification problem) can be defined as follows. Let us call a proposition concerning the initial state of the machine experimentally decidable if there is an experiment E which determines the truth value of that proposition. This can be done by performing E, i.e., by the input of a sequence of input symbols i₁,i₂,i₃,¼,i_n associated with E, and by observing the output sequence

lE(s) = l(s,i1),l(d(s,i1),i2), ¼,l( d(¼d(s,i1)¼,in-1) n-1 times  ,in).

The most general form of a prediction concerning the initial state s of the machine is that the initial state s is contained in a subset P of the state set S. Therefore, we may identify propositions concerning the initial state with subsets of S. A subset P of S is then identified with the proposition that the initial state is contained in P.

Let E be an experiment (a preset or adaptive one), and let l_E(s) denote the obtained output of an initial state s. l_E defines a mapping of S to the set of output sequences O^*. We define an equivalence relation on the state set S by

s E º   t if and only if lE(s) = lE(t)

for any s,t Î S. We denote the partition of S corresponding to [ E || ( º )] by S/[ E || ( º )]. Obviously, the propositions decidable by the experiment E are the elements of the Boolean algebra generated by S/[ E || ( º )], denoted by B_E.

There is also another way to construct the experimentally decidable propositions of an experiment E. Let l_E(P) = È\limits_{s Î P}l_E(s) be the direct image of P under l_E for any P Í S. We denote the direct image of S by O_E; i.e., O_E = l_E(S).

It follows that the most general form of a prediction concerning the outcome W of the experiment E is that W lies in a subset of O_E. Therefore, the experimentally decidable propositions consist of all inverse images l_E^-1(Q) of subsets Q of O_E, a procedure which can be constructively formulated (e.g., as an effectively computable algorithm), and which also leads to the Boolean algebra B_E.

Let B be the set of all Boolean algebras B_E. We call the partition logic R = (S,B) an automaton propositional calculus.

Appendix C: Quantum coding

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

Appendix D: Universal manipulation of a single qubit: the U(2)-gate

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

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

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

n

2

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

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

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

S1:  a ® ( b +i c)/Ö2    , (4) P:  b ® b ei j    , (5) S2:  b ® ( e + id )/Ö2    , (6) S2:  c ® ( d + ie )/Ö2    . (7)

The resulting transition is

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

(8)

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

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

(9)

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

The elementary quantum interference device T₂₁^bs depicted in Fig. (3.a) is just a beam splitter followed by a phase shifter in one of the output ports.

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

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

) = (

cosw	i  sinw
i sinw	cosw

). A phase shifter in a two-dimensional Hilbert space is represented by either (

eij	0
0	1

) or (

1	0
0	eij

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

P1:  0 ® 0 eia+b    , (10) P2:  1 ® 1ei b    , (11) S:  0 ® T 1¢+iR 0¢    , (12) S:  1 ® T 0¢+iR 1¢    , (13) P3:  0¢ ® 0¢eij    . (14)

If 0 º 0¢ º (

1

0

) and 1 º 1¢ º (

0

1

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

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

The elementary quantum interference device T₂₁^MZ depicted in Fig. (3.b) is a (rotated) Mach-Zehnder interferometer with two input and output ports and three phase shifters. According to the ``toolbox'' rules, the process can be quantum mechanically described by

P1:  0 ® 0 eia+b    , (16) P2:  1 ® 1 eib    , (17) S1:  1 ® ( b +i c )/Ö2    , (18) S1:  0 ® ( c +i b )/Ö2    , (19) P3:  c ® c ei w    , (20) S2:  b ® ( 1¢+ i 0¢)/Ö2    , (21) S2:  c ® ( 0¢+ i 1¢)/Ö2    , (22) P4:  0¢ ® 0¢eij    . (23)

When again 0 º 0¢ º (

1

0

) and 1 º 1¢ º (

0

1

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

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

(24)

The correspondence between T₂₁^bs (T(w),a,b,j) with T₂₁^MZ (a¢,b¢,w¢,j¢) in equations (15) (24) can be verified by comparing the elements of these matrices. The resulting four equations can be used to eliminate the four unknown parameters w¢ = 2w, b¢ = b-w, a¢ = a-p/2, b¢ = b- w and j¢ = j-p/2; i.e.,

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

(25)

Both elementary quantum interference devices are universal in the sense that every unitary quantum evolution operator in two-dimensional Hilbert space can be brought into a one-to-one correspondence to T^bs₂₁ and T^MZ₂₁; with corresponding values of T,a,b,j or a,w,b,j. This can be easily seen by a similar calculation as before; i.e., by comparing equations (15) (24) 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) [25]

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

(26)

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

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

(27)

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

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

(28)

Let us examine the realization of a few primitive logical ``gates'' corresponding to (unitary) unary operations on qubits. The ``identity'' element I is defined by 0 ® 0 , 1 ® 1 and can be realized by

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

(29)

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

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

(30)

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

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

(31)

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

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

(32)

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

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

References

[1]

Cristian Calude and F. Walter Meyerstein. Is the universe lawful? Chaos, Solitons & Fractals, 10(6):1075-1084, 1999.

[2]

Karl Svozil. Quantum interfaces. e-print arXiv:quant-ph/0001064 available http://arxiv.org/abs/quant-ph/0001064, 2000.

[3]

John A. Wheeler. Law without law. In John A. Wheeler and W. H. Zurek, editors, Quantum Theory and Measurement, pages 182-213. Princeton University Press, Princeton, 1983. [49].

[4]

Daniel M. Greenberger. Private communication.

[5]

David Hilbert. Über das Unendliche. Mathematische Annalen, 95:161-190, 1926.

[6]

Erwin Schrödinger. Die gegenwärtige Situation in der Quantenmechanik. Naturwissenschaften, 23:807-812, 823-828, 844-849, 1935. English translation in [71] and [49].

[7]

Simon Kochen and Ernst P. Specker. The problem of hidden variables in quantum mechanics. Journal of Mathematics and Mechanics, 17(1):59-87, 1967. Reprinted in [72].

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

Simon Kochen and Ernst P. Specker. Logical structures arising in quantum theory. In Symposium on the Theory of Models, Proceedings of the 1963 International Symposium at Berkeley, pages 177-189, Amsterdam, 1965. North Holland. Reprinted in [72].

[15]

Simon Kochen and Ernst P. Specker. The calculus of partial propositional functions. In Proceedings of the 1964 International Congress for Logic, Methodology and Philosophy of Science, Jerusalem, pages 45-57, Amsterdam, 1965. North Holland. Reprinted in [72].

[16]

Garrett Birkhoff and John von Neumann. The logic of quantum mechanics. Annals of Mathematics, 37(4):823-843, 1936.

[17]

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

[18]

Edward F. Moore. Gedanken-experiments on sequential machines. In C. E. Shannon and J. McCarthy, editors, Automata Studies. Princeton University Press, Princeton, 1956.

[19]

Cristian Calude, Elena Calude, Karl Svozil, and Sheng Yu. Physical versus computational complementarity I. International Journal of Theoretical Physics, 36(7):1495-1523, 1997.

[20]

K. Svozil. Quantum Logic. Springer, Singapore, 1998.

[21]

Artur Ekert. Quantum cryptography based on Bell's theorem. Physical Review Letters, 67:661-663, 1991.

[22]

M. Hamrick G. Gilbert. Practical quantum cryptography: A comprehensive analysis (part one). MITRE report MTR 00W0000052 and e-print arXiv:quant-ph/0009027 available at http://arxiv.org/abs/quant-ph/0009027, 2000.

[23]

T. Jenewein, G. Weihs, C. Simon, H. Weinfurter, and A. Zeilinger. Poster, 1998.

[24]

Karl Svozil. The information interpretation of quantum mechanics. e-print arXiv:quant-ph/0006033 available http://arxiv.org/abs/quant-ph/0006033, 2000.

[25]

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

[26]

Peter W. Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings of the 35th Annual Symposium of on Foundations of Computer Science, Santa Fe, NM, Nov. 20-22, 1994. IEEE Computer Society Press, November 1994. arXiv:quant-ph/9508027.

[27]

Artur Ekert and Richard Jozsa. Quantum computation and Shor's factoring algorithm. Reviews of Modern Physics, 68(3):733-753, 1996.

[28]

L. K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pages 212-219. 1996.

[29]

Josef Gruska. uantum Computing. McGraw-Hill, London, 1999.

[30]

Georg Gottlob. Private communication.

[31]

Cristian S. Calude, Michael J. Dinneen, and Karl Svozil. Reflections on quantum computing. Complexity, 2000. in print;
e-print http://www.cs.auckland.ac.nz/CDMTCS//researchreports/130cris.pdf.

[32]

Günther Mahler. private communication.

[33]

Max Planck. Ueber eine Verbesserung der Wien'schen Spectralgleichung. Verhandlungen der deutschen physikalischen Gesellschaft, 2:202, 1900. See also [34].

[34]

Max Planck. Ueber das Gesetz der Energieverteilung im Normalspectrum. Annalen der Physik, 4:553-566, 1901.

[35]

Max Planck. Zur Theorie des Gesetzes der Energieverteilung im Normalspectrum. Verhandlungen der deutschen physikalischen Gesellschaft, 2:237, 1900. See also [34].

[36]

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

[37]

Richard P. Feynman, Robert B. Leighton, and Matthew Sands. The Feynman Lectures on Physics. Quantum Mechanics, volume III. Addison-Wesley, Reading, MA, 1965.

[38]

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

[39]

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

[40]

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

[41]

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

[42]

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

[43]

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

[44]

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

[45]

George W. Mackey. The Mathematical Foundations of Quantum Mechanics. W. A. Benjamin, Reading, MA, 1963.

[46]

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

[47]

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

[48]

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

[49]

John Archibald Wheeler and Wojciech Hubert Zurek. Quantum Theory and Measurement. Princeton University Press, Princeton, 1983.

[50]

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

[51]

Michael Reed and Barry Simon. Methods of Mathematical Physics I: Functional Analysis. Academic Press, New York, 1972.

[52]

Michael Reed and Barry Simon. Methods of Mathematical Physics II: Fourier Analysis, Self-Adjointness. Academic Press, New York, 1975.

[53]

M. Reck, Anton Zeilinger, H. J. Bernstein, and P. Bertani. Experimental realization of any discrete unitary operator. Physical Review Letters, 73:58-61, 1994. See also [25].

[54]

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

[55]

Thomas J. Herzog, Paul G. Kwiat, Harald Weinfurter, and Anton Zeilinger. Complementarity and the quantum eraser. Physical Review Letters, 75(17):3034-3037, 1995.

[56]

David Finkelstein and Shlomit R. Finkelstein. Computational complementarity. International Journal of Theoretical Physics, 22(8):753-779, 1983.

[57]

Gregory J. Chaitin. An improvement on a theorem by E. F. Moore. IEEE Transactions on Electronic Computers, EC-14:466-467, 1965.

[58]

J. H. Conway. Regular Algebra and Finite Machines. Chapman and Hall Ltd., London, 1971.

[59]

W. Brauer. Automatentheorie. Teubner, Stuttgart, 1984.

[60]

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

[61]

Martin Schaller and Karl Svozil. Partition logics of automata. Il Nuovo Cimento, 109B:167-176, 1994.

[62]

Martin Schaller and Karl Svozil. Automaton partition logic versus quantum logic. International Journal of Theoretical Physics, 34(8):1741-1750, August 1995.

[63]

Martin Schaller and Karl Svozil. Automaton logic. International Journal of Theoretical Physics, 35(5):911-940, May 1996.

[64]

Anatolij Dvurecenskij, Sylvia Pulmannová, and Karl Svozil. Partition logics, orthoalgebras and automata. Helvetica Physica Acta, 68:407-428, 1995.

[65]

Karl Svozil and Roman R. Zapatrin. Empirical logic of finite automata: microstatements versus macrostatements. International Journal of Theoretical Physics, 35(7):1541-1548, 1996.

[66]

Karl Svozil and Josef Tkadlec. Greechie diagrams, nonexistence of measures in quantum logics and Kochen-Specker type constructions. Journal of Mathematical Physics, 37(11):5380-5401, November 1996.

[67]

M. Reck and Anton Zeilinger. Quantum phase tracing of correlated photons in optical multiports. In F. De Martini, G. Denardo, and Anton Zeilinger, editors, Quantum Interferometry, Singapore, 1994. World Scientific.

[68]

Charles H. Bennett. Night thoughts, dark sight. Nature, 371:479-480, 1994.

[69]

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

[70]

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

[71]

J. D. Trimmer. The present situation in quantum mechanics: a translation of Schrödinger's ``cat paradox''. Proc. Am. Phil. Soc., 124:323-338, 1980. Reprinted in [49].

[72]

Ernst Specker. Selecta. Birkhäuser Verlag, Basel, 1990.

Footnotes:

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

²I put a quote here because if one is able to ``undo a measurement'', then this process cannot be classical: per definition, classicality means irreversibility, many-to-oneness.

³Actually, if the eavesdropper has total control over the classical channel, this might be used for a reasonable attack strategy.

⁴This implicit time symmetry spoils the very notion of ``progress'' or ``achievement,'' since what is a valuable output is purely determined by the subjective meaning the observer associates with it and is devoid of any syntactic relevance.

⁵ Introductions to quantum mechanics can be found in Feynman, Leighton & M. Sands [37], Harris [38], Lipkin [39], Ballentine [40], Messiah [41], Davydov [42], Dirac [43], Peres [44], Mackey [45], von Neumann [46], and Bell [47], among many other expositions. The history of quantum mechanics is reviewed by Jammer [48]. Wheeler & Zurek [49] published a helpful resource book.

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

⁷ Infinite dimensional cases and continuous spectra are nontrivial extensions of the finite dimensional Hilbert space treatment. As a heuristic rule, which is not always correct, it might be stated that the sums become integrals, and the Kronecker delta function d_ij becomes the Dirac delta function d(i-j), which is a generalized function in the continuous variables i,j. In the Dirac bra-ket notation, unity is given by 1 = ò_-¥^+¥ |i)( i| di. For a careful treatment, see, for instance, the books by Reed and Simon [51,52].

⁸ x+y is sometimes referred to as ``coherent'' superposition to indicate the difference to ``incoherent'' mixtures of state vectors, in which the absolute squares |x|² +|y|² are summed up.

⁹ Nonnegativity means (rx,x) = (x,rx) ³ 0 for all x Î H, and trace class means trace(r) = 1.

¹⁰If the same eigenvalue of an operator occurs more than once, it is called degenerate.

¹¹ Let us first diagonalize A; i.e., A_ij = diag(A₁₁,A₂₂,¼,A_nn)_ij = {

Aii	if i = j
0	if i ¹ j

. Then, if A commutes with B, the commutator [A,B]_ij = (AB-BA)_ij = A_ikB_ki-B_ikA_kj = (A_ii-A_jj)B_ij = 0 vanishes. If A is nondegenerate, then A_ii ¹ A_jj and thus B_ij = 0 for i ¹ j. In the degenerate case, B can only be block diagonal. That is, each one of the blocks of B corresponds to a set of equal eigenvalues of A such that the corresponding subblockmatrix of A is proportional to the unit matrix. Thus, each block of B can be diagonalized separately without affecting A [44].

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

¹³ Any unitary operator U(n) in finite-dimensional Hilbert space can be represented by the product - the serial composition - of unitary operators U(2) acting in twodimensional subspaces [25,53].