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 inputoutput 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 nonclassical 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.
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^{1}
states t and f.
The qubit states
 (1) 
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 contextfree. That is, it is independent of what other information is or might be present. A classical bit remains unchanged, no matter by what methods it is inferred. It obeys classical logic. It can be copied. No doubts can be left.
By contrast, 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., onetoone.
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.
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''^{2} 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.^{3} 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.
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 ``paperandpenciloperations'' 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^{N} 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^{N} classical bit states at once. Many researchers in quantum computing interpret this (in the socalled ``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 onetooneness. 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.^{4}
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.
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 realworld 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.
``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_{N} of
N
linear oscillators (``Resonatoren''),


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''

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.^{5} To avoid a shock from a too early exposure to ``exotic'' nomenclature prevalent in physics  the Dirac braket notation  the notation of DunfordSchwartz [50] is adopted.^{6}
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 theoryscalar products, linear summations, subspaces, operators, measures and so on.
Unless stated differently, only finitedimensional Hilbert spaces are considered.^{7}
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).
Every onedimensional projection E_{x} onto a onedimensional 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.^{8}
Elements b_{i},b_{j} Î H of the set of orthonormal base vectors satisfy (b_{i}, b_{j}) = d_{ij}, where d_{ij} = {

 


In the nonpure state case, the system is characterized by the density operator r, which is nonnegative and of trace class.^{9} 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}^{n} P_{i} E_{i}, where E_{i} are projection operators and the P_{i}'s are the associated probabilities (nondegenerate case^{10}).
Any hermitian operator has a spectral representation A = å_{i = 1}^{n} 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.^{11}
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.

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 yfunction? In his 1935 paper ``Die gegenwärtige Situation in der Quantenmechanik'' (``The present situation in quantum mechanics'' [6]), Schrödinger states,^{12}
The yfunction as expectationcatalog: ¼ In it [[the yfunction]] is embodied the momentarilyattained sum of theoretically based future expectation, somewhat as laid down in a catalog. ¼ For each measurement one is required to ascribe to the yfunction ( = the prediction catalog) a characteristic, quite sudden change, which depends on the measurement result obtained, and so cannot be foreseen; from which alone it is already quite clear that this second kind of change of the yfunction has nothing whatever in common with its orderly development between two measurements. The abrupt change [[of the yfunction ( = the prediction catalog)]] by measurement ¼ is the most interesting point of the entire theory. It is precisely the point that demands the break with naive realism. For this reason one cannot put the yfunction directly in place of the model or of the physical thing. And indeed not because one might never dare impute abrupt unforeseen changes to a physical thing or to a model, but because in the realism point of view observation is a natural process like any other and cannot per se bring about an interruption of the orderly flow of natural events.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.



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

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_{0} ) =  [iH/((^{h}/_{2p}) )] y(t). In terms of the set of orthonormal base vectors { b_{1}, b_{2}, ¼}, the Schrödinger equation can be written as i(^{h}/_{2p}) [(¶)/(¶t)] ( b_{i} , y(t) ) = å_{j}H_{ij}( b_{j}, y(t) ).
For stationary states y_{n}(t) = e^{(i/(h/2p) )Ent} y_{n} , the Schrödinger equation can be brought into its timeindependent form H y_{n} = E_{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.
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 inputoutput 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 inputoutput 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 worstcase 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 logicoalgebraic 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.
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 inputoutput 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.
The corresponding observable propositions are:
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 quasiclassical Boolean block. Let us denote by v(x) the block corresponding to input (sequence) x. Then we obtain

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.
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^{2} is identifiedand one obtains a ``Chinese lantern'' lattice MO_{3}. The Hasse diagram of the propositional calculus is drawn in Figure 1.
0.90mm
Picture Omitted
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 (initialstate
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_{1},i_{2},i_{3},¼,i_{n} associated with E, and by
observing the output sequence

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

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.
 (2) 
 (3) 
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)^{2} and P_{f}(x_{a}) = (x_{a},f)^{2} = 1P_{t}(_{a,b}), respectively.
It is well known that any ndimensional unitary matrix U can be composed from elementary unitary transformations in twodimensional subspaces of C^{n}. This is usually shown in the context of parameterization of the ndimensional unitary groups (cf. [25] and [53,67]). Thereby, a transformation in ndimensional spaces is decomposed into transformations in 2dimensional subspaces. This amounts to a successive array of U(2) elements, which in their entirety forms an arbitrary time evolution U(n) in ndimensional Hilbert space.
Hence, all quantum processes and computation tasks which can possibly be executed must be representable by unitary transformations. Indeed, unitary transformations of qubits are a necessary and sufficient condition for quantum computing. The group of unitary transformations in arbitrary but finitedimensional Hilbert space is a model of universal quantum computer.
It remains to be shown that the universal U(2)gate is physically operationalizable. This can be done in the framework of MachZehnder interferometry. Note that the number of elementary U(2)transformations is polynomially bounded and does not exceed (
 

In what follows, a lossless MachZehnder interferometer drawn in Fig. 2 is discussed.
0.70mm
Picture Omitted
The computation proceeds by successive substitution (transition) of
states; i.e.,

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

 



 



 



 



 

 


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

 

 

 (24) 
The correspondence between
T_{21}^{bs} (T(w),a,b,j) with
T_{21}^{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¢ = bw,
a¢ = ap/2,
b¢ = b w and
j¢ = jp/2; i.e.,
 (25) 
Both elementary quantum interference devices are universal in the
sense that
every unitary quantum
evolution operator in twodimensional Hilbert space can be brought into
a onetoone correspondence to T^{bs}_{21} and
T^{MZ}_{21}; with corresponding values of
T,a,b,j or
a,w,b,j.
This can be easily seen by a similar calculation as before; i.e., by
comparing
equations
(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]
 (26) 
 (27) 
 (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
 (29) 
The ``not'' element is defined by
0 ® 1 ,
1 ® 0 and can be realized by
 (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
 (31) 
 (32) 
It is very important that the elementary quantum interference device realizes an arbitrary quantum time evolution of a twodimensional system. The performance of the quantum interference device is determined by four parameters, corresponding to the phases a,b,j, w.
^{1} (t,t) = (f,f) = 1 and (t,f) = 0.
^{2}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, manytooneness.
^{3}Actually, if the eavesdropper has total control over the classical channel, this might be used for a reasonable attack strategy.
^{4}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.
^{5} 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.
^{6} The braket notation introduced by Dirac is widely used in physics. To translate expressions into the braket notation, the following identifications work for most practical purposes: for the scalar product, ``á º ('', ``ñ º )'', ``, º  ''. States are written as  yñ º y, operators as ái  A  j ñ º A_{ij}.
^{7} 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(ij), which is a generalized function in the continuous variables i,j. In the Dirac braket notation, unity is given by 1 = ò_{¥}^{+¥} i)( i di. For a careful treatment, see, for instance, the books by Reed and Simon [51,52].
^{8} 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^{2} +y^{2} are summed up.
^{9} Nonnegativity means (rx,x) = (x,rx) ³ 0 for all x Î H, and trace class means trace(r) = 1.
^{10}If the same eigenvalue of an operator occurs more than once, it is called degenerate.
^{11} Let us first diagonalize A; i.e., A_{ij} = diag(A_{11},A_{22},¼,A_{nn})_{ij} = {

 


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