000 111 Quantum computation and complexity theory I

Quantum computation and complexity theory I

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

Abstract

The Hilbert space formalism of quantum mechanics is reviewed with emphasis on applications to quantum computing.

Contents

1  The Quantum of action
2  Quantum mechanics for the computer scientist
    2.1  Hilbert space quantum mechanics
    2.2  From single to multiple quanta - ``second'' field quantization
    2.3  Quantum interference
    2.4  Hilbert lattices and quantum logic
    2.5  Partial algebras
3  Quantum information theory
    3.1  Information is physical
    3.2  Copying and cloning of qbits
    3.3  Context dependence of qbits
    3.4  Classical versus quantum tautologies
Appendix
A  Hilbert space
B  Mathematica code for quantum interference
    B.1  Mach-Zehnder interferometer
    B.2  Mandel interferometer
Bibliography

1  The Quantum of action

``Quantization,'' as it is presently understood, has been introduced by Max Planck1 in 1900 [2] in an attempt to study the energy spectrum of blackbody radiation.2 ``Quantization,'' according to Planck, is the discretization of the total energy UN of N linear oscillators (``Resonatoren''),

UN = Pe { 0,e,2e,3e,4e,},
(1)
where P \Bbb N0 is zero or a positive integer. e is the smallest quantum of energy. It is a linear function of frequency n and proportional to Planck's fundamental constant h; i.e.,
e = hn.
(2)

In 1905, Einstein's light quantum hypothesis extended Planck's (``Resonator'') quantization to the electromagnetic field [3]. In Einstein's own words (cf. [3], p. 133),3

Es scheint nun in der Tat, daß   die Beobachtungen über die ``schwarze Strahlung'', Photoluminiszenz, die Erzeugung von Kathodenstrahlen durch ultraviolettes Licht und andere die Erzeugungung bez. Verwandlung des Lichtes betreffende Erscheinungsgruppen besser verständlich erscheinen unter der Annahme, daß  die Energie des Lichtes diskontinuierlich im Raume verteilt sei. Nach der hier ins Auge zu fassenden Annahme ist bei der Ausbreitung eines von einem Punkte ausgehenden Lichtstrahles die Energie nicht kontinuierlich auf größ er und größ er werdende Räume verteilt, sondern es besteht dieselbe aus einer endlichen Zahl von in Raumpunkten lokalisierten Energiequanten, welche sich bewegen, ohne sich zu teilen und nur als Ganze absorbiert und erzeugt werden können.

Einstein's light quantum hypothesis asserts that, as far as emission and absorption processes are concerned, the energy of a light ray which is emitted at some point is not distributed continuously over increasing regions of space, but is concentrated in a finite number of energy quanta, which can only be absorbed and emitted as a whole. With this assumption, the photoelectric effect could properly be described (cf. Figure 1).


Picture Omitted
Figure 1: The photoelectric effect. A beam of light of frequency n impinges upon an electrode. Electrons are emitted with kinetic energy E = hn-W, where W < hn is the ``threshold energy'' necessary to release an electron (it is material dependent). Any increase in the intensity of light of frequency n is accompanied by an increase in the number of emitted electrons of energy hn-W. The energy of the single electrons is not altered by this intensity increase. An increase in the Frequency n > n, however, yields an energy increase of the emitted electrons by Dn = n-n.

Thus, in extension of Planck's discretized resonator energy model, Einstein proposed a quantization of the electromagnetic field. Every field mode of frequency n could carry a discrete number of light quanta of energy hn per quantum (cf. 2.2, p. pageref).

The present quantum theory is still a continuum theory in many respects: for infinite systems, there is a continuity of field modes of frequency w. Also the quantum theoretical coefficients characterising the mixture between orthogonal states, as well as space and time and other coordinates remain continuous - all but one: action. Thus, in the old days, discretization of phase space appeared to be a promising starting point for quantization. In a 1916 article on the structure of physical phase space, Planck emphasized that the quantum hypothesis should not be interpreted at the level of energy quanta but at the level of action quanta, according to the fact that the volume of 2f-dimensional phase space (f degrees of freedom) is a positive integer of hf (cf. [4], p. 387),4

Es bestätigt sich auch hier wieder, daß  die Quantenhypothese nicht auf Energieelemente, sondern auf Wirkungselemente zu gründen ist, entsprechend dem Umstand, daß  das Volumen des Phasenraumes die Dimension von hf besitzt.

Since position and momentum cannot be measured simultaneously with arbitrary accuracy, the classical notion of a point in phase space has to be substituted by the notion of a cell of volume hf. Stated differently: for periodic, onedimensional systems, the area of phase space occupied by the n'th orbit is



dp  dq =
p  dq = nh.
(3)

Let us consider two examples: a linear oscillator and the quantum phase space of a rotator [5]. For the onedimensional linear oscillator with frequency n, the equation of motion is

q (2pn)2 + d2 q
dt2
= 0.
(4)
Equation (4) has the solution

q = a sin2pnt, where a is an arbitrary constant. The canonical momentum is

p = m[dq/ dt] = 2pnm a cos2 pnt. Elimination of the time parameter t yields a trajectory in the (p,q)-phase space which is an ellipse; i.e.,

[(q2)/( a2)]+[(p2)/( b2)] = 1, where b = 2 pnm a. The area of the ellipse is

abp = 2p2nm a2. Insertion of (3) yields

2p2nm a2 = nh.
(5)
Figure 2a shows the area of phase space occupied by the n 10'th orbit for a onedimensional harmonic oscillator with a = 2b.

a)

Figureb)


Picture Omitted

Figure 2: a) area of phase space occupied by the n 10'th orbit for a onedimensional harmonic oscillator. b) area of phase space occupied by the first orbits of a rotator.

As a second example, consider a rotator, defined by a constant circular motion of a mass m and of radius a around a center. Let q = j be the angular coordinate in the plane of motion, then the rotator energy is given by

E =
m (a .
q
 
)2

2
.
(6)
The associated momentum is p = [d E/ d[q\dot]] = ma2 [q\dot]. For constant motion, [q\dot] is constant and -p < q p, one obtains by equation (3) a quantization of momentum of the form
2 pp = nh.
(7)
Figure 2b shows the area of phase space occupied by the first orbits of a rotator.

Now, then, what does the quantum mean? Is it merely a metaphor, a way to compute? Or is it an indication of a discrete organization of the physical universe? One may safely state that the rôle of the quantum and our understanding of it as a hint towards a more fundamental discrete theory has not changed much over the years. As Einstein put it ([6], p. 163),5

Man kann gute Argumente dafür anführen, daß  die Realität überhaupt nicht durch ein kontinuierliches Feld dargestellt werden könne. Aus den Quantenphänomenen scheint nämlich mit Sicherheit hervorzugehen, daß  ein endliches System von endlicher Energie durch eine endliche Zahl von Zahlen (Quanten-Zahlen) vollständig beschrieben werden kann. Dies scheint zu einer Kontinuums-Theorie nicht zu passen und muß  zu einem Versuch führen, die Realität durch eine rein algebraische Theorie zu beschreiben. Niemand sieht aber, wie die Basis einer solchen Theorie gewonnen werden könnte.

2  Quantum mechanics for the computer scientist

Is there a difference between quantum theory for physicists and quantum theory for logicians and computer scientists? Of course not, in principle!

Yet, a second glance reveals that there is a difference in aim. Courses in ``hard-core'' quantum theory for physicists tend to stress potential theory, and there the two solvable problems - the hydrogen atom and the harmonic oscillator. Computer scientists are more interested in quantum information and computing. They would like to concentrate on quantum coherence and the superposition principle and are therefore more attracted by recent developments in the ``foundations'' of quantum mechanics. (A very few are even attracted by quantum logic; for mere curiosity, it seems!) The following brief outline attempts to satisfy this demand.

2.1  Hilbert space quantum mechanics

In what follows, we shall make a great leap in time [7,8], thereby omitting the Schrödinger-de Broglie wave mechanics and Heisenberg's formalism, and consider ``state-of-the-art'' Hilbert space quantum mechanics [9,10,11,12,13,14,15,64]. (For a short review of Hilbert spaces, see appendix A.) It consists of the following (incomplete list of) rules. Thereby, every physical entity of a quantized system corresponds to an object in or defined by Hilbert space.

(I) Following Dirac [9], a physical state is represented by a ket vector of complex Hilbert space \frak H, or ket, represented by the symbols `` \mid  ''. In order to distinguish the kets from each other, a particular letter or index or other symbol is inserted. Thus, the vector y \frak H is represented by the symbol ``\mid y''.

Since kets are defined as vectors in complex Hilbert space, any linear combination of ket vectors is also a ket vector. I.e.,

\mid y = a\mid 1+b\mid 2 \frak H    ,    a,b \Bbb C    .
(8)
For continuous index t and infinite dimensional Hilbert space,
\mid y =
t2

t1 
a(t)\mid t \frak H    ,    a(t) \Bbb C    .
(9)
Such a linear combination of states is also called ``coherent superposition'' or just ``superposition'' of states.

(II) Vectors of the dual Hilbert space \frak Hf are called bra vectors or bras. They are denoted by the symbol ``  \mid ''. Again, in order to distinguish the bras from each other, a particular letter or index or other symbol is inserted. Thus, the vector y \frak Hf is represented by the symbol `` y\mid ''.

The metric of \frak H can now be defined as follows. Assume that there is a one-to-one correspondence (isomorphism) between the kets and the bras. Bra and ket thus corresponding to each other are said to be conjugates of each other and are labelled by the same symbols. Thus,

\mid y = (y\mid )f    ,      y\mid = (\mid y)f     .
(10)

Here, the symbol ``f'' has been introduced to indicate the transition to dual space, with the following syntactic rules:

(a)f
a*
(11)
(y\mid )f
\mid y
(12)
(\mid y)f
y\mid
(13)
(y\mid j)f
j\mid y = (y\mid j)*     .
(14)

Note that, by this definition,

(a\mid 1+b\mid 2)f = a* 1\mid +b* 2\mid , where ``*'' denotes complex conjugation.

(III) The scalar product of the ket \mid y and the ket \mid j is the number j\mid y, i.e., the value j(\mid y) taken by the linear functional associated with the bra conjugate to \mid j.6

(IV) Elements of the set of orthonormal base vectors { \mid i\mid i \Bbb I} (\Bbb I stands for some index set of the cardinality of the dimension of the Hilbert space \frak H) satisfy

i\mid j = dij =

0   
if  i j
1   
if  i = j
    .
(15)
where dij is the Kronecker delta function. For infinite dimensional Hilbert spaces, dij is substituted by the Dirac delta function

x\mid y = d(x-y) = [1/( 2p)] - ei(x-y)tdt, which has been introduced for this occasion.

Furthermore, any state \mid y can be written as a linear combination of the set orthonormal base vectors { \mid i\mid i \Bbb I}; i.e.,

\mid y =

i \Bbb I 
ai\mid i
(16)
with
ai = i\mid y \Bbb C    .
(17)

The identity operator 1 (not to be confused with the index set!) can be written in terms of the orthonormal basis vectors as (ai = 1)

1 =

i \Bbb I 
\mid ii \mid     .
(18)
The sums become integrals for continuous spectra.

E.g., if the index i is identified by the spatial position (operator) x and the state is \mid y(t) time-dependent, then x\mid y(t) = y(x,t) is just the usual (Schrödinger) wave function.

(V) Observables are represented by self-adjoint operators [^R] = [^R]f on the Hilbert space \frak H. For finite dimensional Hilbert spaces, bounded self-adjoint operators are equivalent to bounded Hermitean operators. They can be represented by matrices, and the self-adjoint conjugation is just transposition and complex conjugation of the matrix elements.

Self-adjoint operators have a spectral representation

^
R
 
=

n 
rn ^
P
 

n 
    ,
(19)
where the [^P]n are orthogonal projection operators related to the orthonormal eigenvectors of [^R] by
^
P
 

n 
=

a 
\mid a,rna,rn\mid    .
(20)
Here, the rn are the eigenvalues of [^R], and the parameter a labels the degenerate eigenvectors which belong to the same eigenvalue of [^R]. For nondegenerate eigenstates, equation (19) reduces to

[^R] = n rn\mid rnrn\mid . Again, the sums become integrals for continuous spectra. Note also that self-adjoint operators in complex Hilbert space have real-valued eigenvalues; i.e., rn \BbbR.

For example, in the base { \mid x\mid x \Bbb R} , the position operator is just [^\frak x] = x, the momentum operator is [^(\frak px)] = px [((h/2p))/ i] [()/( x)], where

(h/2p) = [h/( 2p)], and the non-relativistic energy operator (hamiltonian) is

[^H] = [[^[\frak p\vec]] [^[\frak p\vec]]/2m]+[^V](x) = - [((h/2p)2)/2m]2+V(x).

Observables are said to be compatible if they can be defined simultaneously with arbitrary accuracy; i.e., if they are ``independent.'' A criterion for compatibility is the commutator. Two observables [^A],[^B] are compatible, if their commutator vanishes; i.e.,


^
A
 
, ^
B
 

= ^
A
 
^
B
 
- ^
B
 
^
A
 
= 0    .
(21)
For example, position and momentum operators7


^
\frak x
 
, ^
\frak px
 

= ^
\frak x
 
^
\frak px
 
- ^
\frak px
 
^
\frak x
 
= x (h/2p)
i

x
- (h/2p)
i

x
x = i (h/2p) 0
(22)
and thus do not commute. Therefore, position and momentum of a state cannot be measured simultaneously with arbitrary accuracy. It can be shown that this property gives rise to the Heisenberg uncertainty relations
DxDpx (h/2p)
2
    ,
(23)
where

Dx and

Dpx is given by

Dx = {x2-x2} and

Dpx = {px2-px2}, respectively.

It has recently been demonstrated that (by an analog embodiment using paricle beams) every self-adjoint operator in a finite dimensional Hilbert space can be experimentally realized [17].

(VI) The result of any single measurement of the observable [^R] can only be one of the eigenvalues rn of the corresponding operator [^R]. As a result of the measurement, the system is in (one of) the state(s) \mid a, rn of [^R] with the associated eigenvalue rn and not in a coherent superposition. This has given rise to speculations concerning the ``collapse of the wave function (state).'' But, as has been argued recently (cf. [18]), it is possible to reconstruct coherence; i.e., to ``reverse the collapse of the wave function (state)'' if the process of measurement is reversible. After this reconstruction, no information about the measurement must be left, not even in principle. How did Schrödinger, the creator of wave mechanics, perceive the y-function? In his 1935 paper ``Die Gegenwärtige Situation in der Quantenmechanik'' (``The present situation in quantum mechanics'' [19], p. 53), Schrödinger states,8

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.

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

(VII) The average value or expectation value of an observable [^R] in the state \mid y is given by

R = y\mid R\mid y =

n,a 
rny\mid a, rna, rn\mid y =

n,a 
rn|y\mid a, rn|2   .
(24)

(VIII) The probability to find a system represented by state \mid y in some state \mid i of the orthonormalized basis is given by

|i \mid y|2       .
(25)
For the continuous case, the probability of finding the system between i and i+di is given by
|i \mid y|2 di       .
(26)

(IX) The dynamical law or equation of motion can be written in the form

\mid y(t) = ^
U
 
\mid y(t0)    ,
(27)
where [^U]f = [^U]-1, i.e., [^U][^U]f = [^U]f [^U] = 1 is a linear unitary evolution operator. So, all quantum dynamics is based on linear operations! This fact is of central importance in interferometry and, with computing being interpretable as interferometry, for the theory of quantum computability.

The Schrödinger equation

i(h/2p)
t
\mid y(t) = ^
H
 
\mid y(t)
(28)
is obtained by identifying [^U] with
^
U
 
= e-i[^H]t/(h/2p)     ,
(29)
where [^H] is a self-adjoint hamiltonian (``energy'') operator, and by differentiating (27) with respect to the time variable t and using (29); i.e.,


t
\mid y(t) = - 
i ^
H
 

(h/2p)
e-i[^H]t/(h/2p)\mid y(t0) = - 
i ^
H
 

(h/2p)
\mid y(t)    .
(30)

In terms of the set of orthonormal base vectors { \mid i\mid i \Bbb I}, the Schrödinger equation (28) can be written as

i(h/2p)
t
i \mid y(t) =

j \Bbb I 
i\mid H\mid jj\mid y(t)     ,
(31)
with i\mid H\mid j = Hij for a finite dimensional Hilbert space. Again, the sums become integrals and i\mid H\mid j = H(i,j) for continuous spectra. In the case of position base states y(x,t) = x\mid y(t), the Schrödinger equation (28) takes on the form
i(h/2p)
t
y(x,t) = ^
H
 
y(x,t) =




^
\frak p
 
^
\frak p
 

2m
+ ^
V
 
(x)




y(x,t) =

(h/2p)2
2m
2+V(x)

y(x,t)     .
(32)

(X) For stationary

\mid yn(t) = e-(i/(h/2p) )Ent \mid yn , the Schrödinger equation (28) can be brought into its time-independent form

^
H
 
\mid yn = En\mid yn     .
(33)
Here,

i(h/2p) [()/( t)] \mid yn (t) = En\mid yn (t) has been used; En and \mid yn stand for the n'th eigenvalue and eigenstate of [^H], respectively.

Usually, a physical problem is defined by the hamiltonian [^H]. The problem of finding the physically relevant states reduces to finding a complete set of eigenvalues and eigenstates of [^H]. Most elegant solutions utilize the symmetries of the problem, i.e., of [^H]. There exist two ``canonical'' examples, the 1/r-potential and the harmonic oscillator potential, which can be solved wonderfully by this methods (and they are presented over and over again in standard courses of quantum mechanics), but not many more. (See [20] for a detailed treatment of various hamiltonians [^H].)

Having now set the stage of the quantum formalism, an elementary twodimensional example of a two-state system shall be exhibited ([12], p. 8-11). Let us denote the two base states by \mid 1 and \mid 2. Any arbitrary physical state \mid y is a coherent superposition of \mid 1 and \mid 2 and can be written as

\mid y = \mid 11\mid y+\mid 22\mid y with the two coefficients 1\mid y,2\mid y \Bbb C.

Let us discuss two particular types of evolutions.

First, let us discuss the Schrödinger equation (28) with diagonal Hamilton matrix, i.e., with vanishing off-diagonal elements,

i \mid H\mid j =

E1
0
0
E2


    .
(34)
In this case, the Schrödinger equation (33) decouples and reduces to

i(h/2p)
t
1 \mid y(t) = E1 1 \mid y(t)     ,      i(h/2p)
t
2 \mid y(t) = E2 2 \mid y(t)     ,
(35)
resulting in
1 \mid y(t) = a e-iE1t/(h/2p)    ,      2 \mid y(t) = b e-iE2t/(h/2p)    ,
(36)
with a,b \Bbb C, |a|2+|b|2 = 1. These solutions correspond to stationary states which do not change in time; i.e., the probability to find the system in the two states is constant
|1 \mid y|2 = |a|2    ,      |2 \mid y|2 = |b|2    .
(37)

Second, let us discuss the Schrödinger equation (33) with with non-vanishing but equal off-diagonal elements -A and with equal diagonal elements E of the hamiltonian matrix; i.e.,

i \mid H\mid j =

E
-A
-A
E


    .
(38)
In this case, the Schrödinger equation (33) reads
i(h/2p)
t
1 \mid y(t)
=
E 1 \mid y(t) - A 2 \mid y(t)     ,
(39)
i(h/2p)
t
2 \mid y(t)
=
E 2 \mid y(t) - A 1 \mid y(t)     .
(40)
These equations can be solved in a number of ways. For example, taking the sum and the difference of the two, one obtains

i(h/2p)
t
(1 \mid y(t) +2\mid y(t) )
=
(E-A) (1 \mid y(t) + 2 \mid y(t) )    ,
(41)
i(h/2p)
t
(1 \mid y(t) -2\mid y(t))
=
(E+A) (1 \mid y(t) - 2 \mid y(t) )    .
(42)
The solution are again two stationary states
1 \mid y(t) +2 \mid y(t)
=
ae-(i/(h/2p) )(E-A)t    ,
(43)
1 \mid y(t)-2 \mid y(t)
=
be-(i/(h/2p) )(E+A)t    .
(44)
Thus,
1 \mid y(t)
=
a
2
e-(i/(h/2p) )(E-A)t+ b
2
e-(i/(h/2p) )(E+A)t    ,
(45)
2 \mid y(t)
=
a
2
e-(i/(h/2p) )(E-A)t- b
2
e-(i/(h/2p) )(E+A)t    .
(46)

Assume now that initially, i.e., at t = 0, the system was in state \mid 1 = \mid y(t = 0). This assumption corresponds to

1 \mid y(t = 0) = 1 and

2 \mid y(t = 0) = 0. What is the probability that the system will be found in the state

\mid 2 at the time t > 0, or that it will still be found in the state

\mid 1 at the time t > 0? Setting t = 0 in equations (45) and (46) yields

1 \mid y(t = 0) = a+b
2
= 1    ,      2 \mid y(t = 0) = a-b
2
= 0    ,
(47)
and thus a = b = 1. Equations (45) and (46) can now be evaluated at t > 0 by substituting 1 for a and b,

1 \mid y(t)
=
e-(i/(h/2p) )Et

e(i/(h/2p) )At+e-(i/(h/2p) )At
2


= e-(i/(h/2p) )Etcos At
(h/2p)
    ,
(48)
2 \mid y(t)
=
e-(i/(h/2p) )Et

e(i/(h/2p) )At-e-(i/(h/2p) )At
2


= i e-(i/(h/2p) )Etsin At
(h/2p)
    .
(49)
Finally, the probability that the system is in state \mid 1 and \mid 2 is
|1 \mid y(t)|2 = cos2 At
(h/2p)
    ,      |2 \mid y(t)|2 = sin2 At
(h/2p)
    ,
(50)
respectively. This results in an oscillation of the transition probabilities as depicted in Fig. 3.

 

Figure

Figure 3: The probabilities

|1 \mid y(t)|2 = cos2(At/ (h/2p) ) (solid line) and

|2 \mid y(t)|2 = sin2(At/ (h/2p) ) (dashed line) as a function of time (in units of (h/2p) /A) for a quantized system which is in state \mid 1 at t = 0.

Let us shortly mention one particular realization of a two-state system which, among many others, has been discussed in the Feynman lectures [12]. Consider an ammonia (NH3) molecule. If one fixes the plane spanned by the three hydrogen atoms, one observes two possible spatial configurations \mid 1 and \mid 2, corresponding to position of the nitrogen atom in the lower or the upper hemisphere, respectively (cf. Fig. 4). The nondiagonal elements of the hamiltonian H12 = H21 = -A correspond to a nonvanishing transition probability from one such configuration into the other.


Picture Omitted
Figure 4: The two equivalent geometric arrangements of the ammonia (NH3) molecule.

If the ammonia has been originally in state \mid 1, it will constantly swing back and forth between the two states, with a probability given by equations (50).

2.2  From single to multiple quanta - ``second'' field quantization

The quantum formalism developed so far is about single quantized objects. What if one wants to consider many such objects? Do we have to add assumptions in order to treat such multi-particle, multi-quanta systems appropriately?

The answer is yes. Experiment and theoretical reasoning (the representation theory of the Lorentz group [21] and the spin-statistics theorem [22,23,24,25]) indicate that there are (at least) two basic types of states (quanta, particles): bosonic and fermionic states. Bosonic states have what is called ``integer spin;'' i.e., sb = 0,(h/2p) ,2 (h/2p) ,3(h/2p) ,, whereas fermionic states have ``half-integer spin;'' sf = [(1(h/2p))/ 2],[(3(h/2p))/2],[(5(h/2p))/ 2]. Most important, they are characterized by the way identical copies of them can be ``brought together.'' Consider two boxes, one for identical bosons, say photons, the other one for identical fermions, say electrons. For the first, bosonic, box, the probability that another identical boson is added increases with the number of identical bosons which are already in the box. There is a tendency of bosons to ``condensate'' into the same state. The second, fermionic box, behaves quite differently. If it is already occupied by one fermion, another identical fermion cannot enter. This is expressed in the Pauli exclusion principle: A system of fermions can never occupy a configuration of individual states in which two individual states are identical.

How can the bose condensation and the Pauli exclusion principle be implemented? There are several forms of implementation (e.g., fermionic behavior via Slater-determinants), but the most compact and widely practiced form uses operator algebra. In the following we shall present this formalism in the context of quantum field theory [13,26,22,23,24,25,27].

A classical field can be represented by its Fourier transform (``*'' stands for complex conjugation)

A(x,t)
=
A(+)(x,t)+A(-)(x,t)
(51)
A(+)(x,t)
=
[A(-)(x,t)]*
(52)
A(+)(x,t)
=


ki,si 
aki,siuki,si(x)e-iwki t    ,
(53)
where n = wki/2p stands for the frequency in the field mode labelled by momentum ki and si is some observable such as spin or polarization. uki,si stands for the polarization vector (spinor) at ki,si, and, most important with regards to the quantized case, complex-valued Fourier coefficients aki,si \Bbb C.

From now on, the ki,si-mode will be abbreviated by the symbol i; i.e., 1 k1,s1, 2 k2,s2, 3 k3,s3, , i ki,si, .

In (second9) quantization, the classical Fourier coefficients ai become re-interpreted as operators, which obey the following algebraic rules (scalars would not do the trick). For bosonic fields (e.g., for the electromagnetic field), the commutator relations are (``f'' stands for self-adjointness):

[ai,ajf ]
=
ai ajf - ajf ai = dij     ,
(54)
[ai,aj]
=
[aif,ajf] = 0     .
(55)

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

{ai,ajf}
=
aiajf+ajfai = dij     ,
(56)
{ai,aj}
=
{aif,ajf} = 0     .
(57)
The anti-commutator relations, in particular

{ajf,ajf} = 2(ajf)2 = 0, are just a formal expression of the Pauli exclusion principle stating that, unlike bosons, two or more identical fermions cannot co-exist.

The operators

aif and

ai are called creation and annihilation operators, respectively. This terminology suggests itself if one introduces Fock states and the occupation number formalism.

aif and

ai are applied to Fock states to following effect.

The Fock space associated with a quantized field will be the direct product of all Hilbert spaces \frak Hi; i.e.,



i \Bbb I 
\frak Hi    ,
(58)
where \Bbb I is an index set characterizing all different field modes labeled by i. Each boson (photon) field mode is equivalent to a harmonic oscillator [27,28]; each fermion (electron, proton, neutron) field mode is equivalent to the Larmor precession of an electron spin.

In what follows, only finite-size systems are studied. The Fock states are based upon the Fock vacuum. The Fock vacuum is a direct product of states \mid 0i of the i'th Hilbert space \frak Hi characterizing mode i; i.e.,

\mid 0
=


i \Bbb I 
\mid 0 i = \mid 0 1 \mid 0 2 \mid 0 3
=
\mid

i \Bbb I 
{0i} = \mid {01,02,03,}    ,
(59)
where again \Bbb I is an index set characterizing all different field modes labeled by i. ``0i'' stands for 0 (no) quantum (particle) in the state characterized by the quantum numbers i. Likewise, more generally, ``Ni'' stands for N quanta (particles) in the state characterized by the quantum numbers i.

The annihilation operators

ai are designed to destroy one quantum (particle) in state i:

aj \mid 0 = 0    ,
(60)
aj\mid {01,02,03,,0j-1,Nj,0j+1, } =
       =   


Nj
 
\mid {01,02,03,,0j-1,(Nj-1),0j+1, }    .
(61)

The creation operators

aif are designed to create one quantum (particle) in state i:

ajf\mid 0 = \mid {01,02,03,,0j-1,1j,0j+1, }    .
(62)
More generally, Nj operators (ajf )Nj create an Nj-quanta (particles) state

(ajf )Nj\mid 0 \mid {01,02,03,,0j-1,Nj,0j+1, }    .
(63)
For fermions, Nj { 0,1} because of the Pauli exclusion principle. For bosons, Nj \Bbb N0. With proper normalization [which can motivated by the (anti-)commutator relations and by

|X\mid X|2 = 1], a state

containing

N1 quanta (particles) in mode 1,

N2 quanta (particles) in mode 2,

N3 quanta (particles) in mode 3, etc., can be generated from the Fock vacuum by

\mid

i \Bbb I 
{Ni} \mid {N1,N2,N3,} =

i \Bbb I 
(aif )Ni
  


Ni!
 
\mid 0     .
(64)

The most general quantized field configuration in the Fock basis \mid X is thus a coherent superposition of such quantum states (64) with weights f {Ni} \Bbb C; i.e.,

\mid X =

i \Bbb I { Ni}  
f i \BbbI {Ni} \mid

i \Bbb I 
{Ni}        .
(65)
Compare (65) to the classical expression (53). Classically, the most precise specification has been achieved by specifying one complex number ai \Bbb C for every field mode i. Quantum mechanically, we have to sum over a ``much larger'' set

i \Bbb I {Ni} {{01,02, 03,}, {11,02, 03,}, {01,12, 03,}, {01,02, 13,},

{11,12, 03,},

}, which results from additional (nonclassical) opportunities to occupy every boson field mode with 0,1,2,3, quanta (particles).

Even if the field would consist of only one mode k,s, for bosons, there is a countable infinite (0) set of complex coefficients { f0, f1, f2, f3,} in the field specification. (For fermions, only two coefficient { f0, f1 } would be required, corresponding to a nonfilled and a filled mode.) For such a bosonic one-mode field, the summation in (65) reduces to

\mid X =

N = 0  
fN\mid N       ,
(66)
with the normalization condition
|X\mid X |2 =

N = 0  
|fN|2 = 1    .
(67)
Thus, as has been stated by Glauber ([27], p. 64),

in quantum theory, there is an infinite set of complex numbers which specifies the state of a single mode. This is in contrast to classical theory where each mode may be described by a single complex number. This shows that there is vastly more freedom in quantum theory to invent states of the world than there is in the classical theory. We cannot think of quantum theory and classical theory in one-to-one terms at all. In quantum theory, there exist whole spaces which have no classical analogues, whatever.

2.3  Quantum interference

In what follows a few quantum interference devices will be reviewed. Thereby, we shall make use of a simple ``toolbox''-scheme of combining lossless elements of an experimental setup for the theoretical calculation [29]. The elements of this ``toolbox'' are listed in Table 1. These ``toolbox'' rules can be rigorously motivated by the full quantum optical calculations (e.g., [30,31]) but are much easier to use. In what follows, the factor i resulting from a phase shift of p/2 associated with the reflection at a mirror M is omitted. However, at a half-silvered mirror beam splitter, the relative factor i resulting from a phase shift of p/2 is kept. (A detailed calculation [32] shows that this phase shift of p/2 is an approximation which is exactly valid only for particular system parameters). T and R = [(1-T2)] are transmission and reflection coefficients. Notice that the ``generic'' beam splitter can be realized by a half-silvered mirror and a successive phase shift of

j = -p/2 in the reflected channel; i.e.,

|a(|b+i|c)/2 (|b+ie-ip/2|c)/2 (|b+|c)/2. Note also that, in the notation used, for i < j,

\mid i\mid j aif ajf \mid 0 = \mid i\mid j = \mid 01,02,03,,0i-1,1i,0i+1,, 0j-1,1j,0j+1,    .
(68)
In present-day quantum optical nonlinear devices (NL), parametric up- or down-conversion, i.e., the production of a single quant (particle) from two field quanta (particles) and the production of two field quanta (particles) from a single one occurs at the very low amplitude rate of h 10-6.

physical process symbol state transformation
reflection at mirror

|a |b = i|a


Picture Omitted
``generic'' beam splitter

|a (|b+|c)/2


Picture Omitted
transmission/reflection

|a (|b+i|c)/2

by a beam splitter |a T|b+iR|c,
(half-silvered mirror) T2+R2 = 1, T,R [0,1]

Picture Omitted
phase-shift j

|a |b = |aeij


Picture Omitted
parametric down-conversion|a h|b|c

Picture Omitted
parametric up-conversion|a\mid b h|c

Picture Omitted
amplification |Ai|a |b ;G,N

Picture Omitted

Table 1: ``Toolbox'' of lossless elements for quantum interference devices.

Let us start with a Mach-Zehnder interferometer drawn in Fig. 5.


Picture Omitted
Figure 5: Mach-Zehnder interferometer. A single quantum (photon, neutron, electron etc) is emitted in L and meets a lossless beam splitter (half-silvered mirror) S1, after which its wave function is in a coherent superposition of \mid b and \mid c. In beam path b a phase shifter shifts the phase of state \mid b by j. The two beams are then recombined at a second lossless beam splitter (half-silvered mirror) S2. The quant is detected at either D1 or D2, corresponding to the states \mid d and \mid e, respectively.

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

S1:  |a
(|b+i|c)/2    ,
(69)
P:  |b
|bei j    ,
(70)
S2:  |b
(|e+ i |d)/2    ,
(71)
S2:  |c
(|d+ i |e)/2    .
(72)
The resulting transition is.10
\mid a \mid y = i

eij +1
2


\mid d+

eij -1
2


\mid e    .
(73)
Assume that j = 0, i.e., there is no phase shift at all. Then, equation (73) reduces to \mid a i\mid d, and the emitted quant is detected only by D1. Assume that j = p. Then, equation (73) reduces to \mid a -\mid e, and the emitted quant is detected only by D2. If one varies the phase shift j, one obtains the following detection probabilities, which are identical to the probabilities drawn in Fig. 3 with the substitutions 1 d, 2 e, 2At/(h/2p) j and time phase shift.
PD1(j) = |d\mid y|2 = cos2( j
2
)    ,   PD2(j) = |e\mid y|2 = sin2( j
2
)    .
(74)

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

So far, only a single quantum (particle) at a time was involved. Could we do two-particle or multiparticle interferometry?

Fig. 6 shows an arrangement in which manipulation of one quantum (photon) can alter the interference pattern of another quantum (photon) [34,29].


Picture Omitted
Figure 6: Mandel interferometer. Manipulating one photon can alter the interference pattern of another. The arrangement can produce an interference pattern at detector D1 when the phase shifter P is varied. An entering ultraviolet photon a is split at beam splitter (half-silvered mirror) A so that both down-conversion crystals NL1 and NL2 are illuminated. One of the resulting pair of downconversion photons can reach D1 by way of beam path d or h If one could monitor beams e and k separately, one would know in which crystal the down-conversion occurred, and there would be no interference. But merging beams e and k in this configuration lets the alternative paths of the other photon interfere.

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

A:  |a
(|b+i|c)/2    ,
(75)
NL1:  |b
h|d|e    ,
(76)
NL2:  |c
h|h|k    ,
(77)
P:  |h
|hei j    ,
(78)
B:  |e
T|g+ i R|f    ,
(79)
C:  |h
(|l+ i |m)/2    ,
(80)
C:  |d
(|m+ i |l)/2    ,
(81)
|g
|k    .
(82)
The resulting transition is.11

\mid a \mid y = h
2
 { i (ej+T) \mid k\mid l-ej\mid k\mid m- R \mid f\mid l+ iR \mid f\mid m+T\mid k\mid m}
(83)
Let us first consider only those two-photon events which occur simultaneously at detectors D1 and D2; i.e., we are interested in the state \mid l\mid k. The probability for such events is given by
|l\mid k\mid y|2 = h2
4
( 1+T2+2Tcosj)    .
(84)
Let us now consider only those two-photon events which occur simultaneously at detectors D1 and D3; i.e., we are interested in the state \mid l\mid f. With the assumption that R = [(1-T2)], the probability for such events is given by
|l\mid f\mid y|2 = h2
4
R2 = h2
4
( 1-T2)    .
(85)
Both probabilities (84) and (85) combined yield the probability to detect any single photon at all in detector D1. It is given by
|l \mid y|2 = |l\mid k\mid y|2 +|l\mid f\mid y|2 = h2
2
( 1+Tcosj)    .
(86)
The ``mindboggling'' feature of the setup, as revealed by (86), is the fact that the particle detected in D1 shows an interference pattern although it did not pass the phase shifter P! The ultimate reason for this (which can be readily verified by varying T) is that it is impossible for detector D2 to discriminate between beam path k (second particle) and beam path g (first photon). By this impossibility to know, the two particles become ``entangled'' (``Verschränkung'', a word created by Schrödinger [19]).

Is it possible to use the Mandel interferometer to communicate faster-than-light; e.g., by observing changes of the probability to detect the first particle in D1 corresponding to variations of the phase shift j (at spatially separated points) in the path of the second particle? No, because in order to maintain coherence, i.e., in order not to be able to distinguish between the two particles in k and thus to make the crucial substitution |g |k, the arrangement cannot be arbitrarily spatially extended. The consistency or ``peaceful coexistince'' [35,36] between relativity theory and quantum mechanics, this second ``mindboggling'' feature of quantum mechanics, seems to be not invalidated so far [38,39,40,41,42,43].

2.4  Hilbert lattices and quantum logic

G. Birkhoff and J. von Neumann suggested [44], that, roughly speaking, the ``logic of quantum events'' - or, by another wording, quantum logic or the quantum propositional calculus - should be obtainable from the formal representation of physical properties.

Since, in this formalism, projection operators correspond to the physical properties of a quantum system, quantum logic is modelled in order to be isomorphic to the lattice of projections \frak P(\frak H) of the Hilbert space \frak H, which in turn is isomorphic to the lattice \frak C(\frak H) of the set of subspaces of a Hilbert space. I.e., by assuming the physical validity of the quantum Hilbert space formalism, the corresponding isomorphic logical structure is investigated.

In this approach, quantum theory comes first and the logical structure of the phenomena are derived by analysing the theory, this could be considered a ``top-down'' method.

The projections Pn correspond to the physical properties of a quantum system and stands for a yes/no-proposition. In J. von Neumann's words ([10], English translation, p. 249),

Apart from the physical quantities , there exists another category of concepts that are important objects of physics - namely the properties of the states of the system S. Some such properties are: that a certain quantity takes the value l - or that the value of is positive -

To each property \frak E we can assign a quantity which we define as follows: each measurement which distinguishes between the presence or absence of \frak E is considered as a measurement of this quantity, such that its value is 1 if \frak E is verified, and zero in the opposite case. This quantity which corresponds to \frak E will also be denoted by \frak E.

Such quantities take only the values of 0 and 1, and conversely, each quantity which is capable of these two values only, corresponds to a property \frak E which is evidently this: ``the value of is 0.'' The quantities \frak E that correspond to the properties are therefore characterized by this behavior.

That \frak E takes on only the values 0,1 can also be formulated as follows: Substituting \frak E into the polynomial F(l) = l-l2 makes it vanish identically. If \frak E has the operator E, then F(\frak E) has the operator F(E) = E-E2, i.e., the condition is that E-E2 = 0 or E = E2. In other words: the operator E of \frak E is a projection.

The projections E therefore correspond to the properties \frak E (through the agency of the corresponding quantities \frak E which we just defined). If we introduce, along with the projections E, the closed linear manifold \frak M, belonging to them ( E = P\frak M), then the closed linear manifolds correspond equally to the properties of \frak E.

More precisely, consider the Hilbert lattice

\frak C(\frak H) = B,0,1,,\sqcup ,\sqcap of an n-dimensional Hilbert space \frak H, with

(i)
B is the set of linear subspaces of \frak H;
(ii)
0 is the 0-dimensional subspace, 1 is the entire Hilbert space \frak H;
(iii)
a is the orthogonal complement of a; and
(iv)
a\sqcup b is the closure of the linear span of a and b; and
(v)
a\sqcap b is the intersection of a and b.

The identification of elements, relations, and operations in lattice theory with relations and operations in Hilbert space is represented in table 2.

quantum logic signHilbert space entitysign
elementary yes-noalinear subspace v(a)
proposition
falsity00-dimensional subspace v(0)
tautology1entire Hilbert space \frak H
lattice operation signHilbert space operationsign
order relation\preceq subspace relation
``meet'' \sqcap intersection of subspaces
``join'' \sqcup closure of subspace spanned by subspaces
``orthocomplement'' orthogonal subspace ^

Table 2: Identification of quantum logical entities with objects of Hilbert lattices.

\frak C(\frak H) is an orthocomplemented lattice. In general, \frak C(\frak H) is not distributive. Therefore, classical (Boolean) propositional calculus is not valid for microphysics! Let, for instance, § ,§ ,§ ^ be subsets of a Hilbert space \frak H with § §,   § § ^ , then (see Fig. 7, drawn from J. M. Jauch [45], p. 27)

§ \sqcap (§ \sqcup § ^ ) = § \sqcap \frak H
=
§ ,   whereas
(87)
\sqcap § ) \sqcup (§ \sqcap § ^ ) = 0 \sqcup 0
=
0    .
(88)


Picture Omitted
Figure 7: Demonstration of the nondistributivity of Hilbert lattices.

A finite dimensional Hilbert lattice is modular. Since Hilbert lattices are orthomodular lattices, they can be constructed by the pasting of blocks (blocks are maximal Boolean subalgebras); the blocks need not be (almost) disjoint.

2.5  Partial algebras

Partial algebras have been introduced by S. Kochen and E. P. Specker [46,48,49,50] as a variant of the classical (Boolean) propositional calculus which takes into account that pairs of propositions may be incompatible. A detailed discussion of partial algebras can be found in [51]; connections to quantum logic in [52].

As has been argued before, certain quantum physical statements are no longer simultaneously measurable (cf. compatibility, p. pageref). This can be formalized by the introduction of a binary compatibility (co-measurability) relation ``(P1,P2)''. Any order relation a b is defined if and only if the propositions P1 and P2 are simultaneously measurable. The propositions P1 and P2 can then be combined by the usual ``and'' and ``or'' operations.

More precisely, consider the partial algebra of linear subspaces of \Bbb Rn (n-dimensional real space) \frak B (\Bbb Rn) = B,,0,1,,, with

(i)
B is the set of linear subspaces of \Bbb Rn;
(ii)
(a,b) holds for subspaces a,b if and only if a and b are orthogonal in the sense of elementary geometry, i.e., if there exists an orthonormal basis of \Bbb Rn containing a basis of a and of b; (If a is a subspace of b, then (a,b) holds.)
(iii)
0 is the 0-dimensional, 1 is the n-dimensional subspace of \Bbb Rn;
(iv)
a is the orthogonal complement of a; and
(v)
ab is the linear span of a and b, defined only for those pairs a,b for which (a,b) holds.

A well-formed formula is valid if it is valid for all compatible (co-measurabile) propositions.

Given the concept of partial algebras, it is quite natural to ask whether certain statements which are classical tautologies are still valid in the domain of partial algebras. Furthermore, one may ask whether it is possible to ``enrich'' the partial algebra of quantum propositions by the introduction of new, ``hidden'' propositions such that in this enlarged domain the classical (Boolean) algebra is valid. In proving that there exist classical tautologies which are no quantum logical ones, Kochen and Specker gave a negative answer to the latter question [50] (cf. p. pageref).

3  Quantum information theory

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, quantum information is contextual. It will be argued below that a quantum bit may appear different, depending on the method by which it is inferred. Quantum bits cannot be copied or ``cloned.'' Classical tautologies are not necessarily satisfied in quantum information theory. Quantum bits obey quantum logic. They are coherent superpositions of classical information.12 Thus, in order to understand the quantum concept of information, one truely has to think ``quantics.'' It is not just a ``fuzzy extension'' of classical logic (e.g., by the introduction of continuous characteristic set function c such as c\000 + (1-c)\111). It it therefore not unreasonable to suspect that the quantum mechanical concept of information will radically (and often painfully) transform formal logic - a change induced by physics and by whatever can be considered as a reasonable physical concept of information!

3.1  Information is physical

``Information is physical'' is the theme of a recent article by Landauer [53], in which lower bounds for the heat dissipation for the processing of classical bits are reviewed. The result can be stated simply by, ``there are no unavoidable energy consumption requirements per step in a computer.'' Only irreversible deletion of classical information is penalized with an increase of entropy.

The slogan ``information is physical'' is also an often used exclamation in quantum information theory. We not only have to change classical predicate logic in order to make it applicable to (micro-) physics; we have to modify our classical concept of information, too.

Classical information theory (e.g., [54]) is based on the bit as fundamental atom. This classical bit, henceforth called cbit, is physically represented by one of two classical states of a classical physical system. It is customary to use the symbols ``0'' and ``1'' (interpretable, for instance, as ``false'' and ``true'') as the names of these states. The corresponding classical bit states are {0, 1 }.

In quantum information theory (cf. [55,56,57,58,16,59,60,61,62]), the most elementary unit of information, henceforth called qbit, may be physically represented by a coherent superposition of the two states which correspond to the symbols \000 and 1. The qbit states are the coherent superposition of the classical basis states {\mid 0, \mid 1 }. They are in the non-denumerable set

{ |a,b\mid |a,b = a|0+b|1,  |a|2+|b|2 = 1,  a,b \Bbb C }    .
(89)

3.2  Copying and cloning of qbits

Can a qbit be copied? No! - This answer amazes the classical mind.13 The reason is that any attempt to copy a coherent superposition of states results either in a state reduction, destroying coherence, or, most important of all, in the addition of noise which manifests itself as the spontaneous excitations of previously nonexisting field modes [39,40,41,42,43].

This can be seen by a simple calculation [39]. A physical realization14 of the qbit state in equation (89) is a two-mode boson field with the identifications

|a,b
=
a|0+b|1     ,
(90)
|1
=
\mid 01,12    ,
(91)
|0
=
\mid 11,02    .
(92)
The classical bit states are |01,12 and |11,02. An ideal amplifier, denoted by \mid A, should be able to copy a classical bit state; i.e., it should create an identical particle in the same mode
|Ai|01,12|Af|01,22    ,      |Ai|11,02|Af|21,02    .
(93)
Here, Ai and Af stand for the initial and the final state of the amplifier.

What about copying a true qbit; i.e., a coherent superposition of the cbits |01,12 and |11,02? According to the quantum evolution law (27), the corresponding amplification process should be representable by a linear (unitary) operator; thus

|Ai(a |01,12+b |11,02)|Af(a |01,22+b |21,02)    .
(94)

Yet, the true copy of that qbit is the state

(a |01,12+b |11,02)2 = (a  a2f +b a1f )2 \mid 0 = a2 |01,22+2ab |01,12|11,02+b2 |21,02    .
(95)
By comparing (94) with (95) it can be seen that no reasonable (linear unitary quantum mechanical evolution for an) amplifier exists which could copy a generic qbit.

A more detailed analysis (cf. [40,41], in particular [42,43]) reveals that the copying (amplification) process generates an amplification of the signal but necessarily adds noise at the same time. This noise can be interpreted as spontaneous emission of field quanta (photons) in the process of amplification.

3.3  Context dependence of qbits

Assume that in an EPR-type arrangement [63] one wants to measure the product

P = mx1mx2my1my2mz1mz2
of the direction of the spin components of each one of the two associated particles 1 and 2 along the x, y and z-axes. Assume that the operators are normalized such that |mij| = 1, i { x,y,z}, j { 1,2}. One way to determine P is measuring and, based on these measurements, ``counterfactually inferring'' [64,65] the three ``observables''

mx1my2, my1mx2 and mz1mz2. By multiplying them, one obtains +1. Another, alternative, way to determine P is measuring and, based on these measurements, ``counterfactually inferring'' the three ``observables''

mx1mx2, my1my2 and mz1mz2. By multiplying them, one obtains -1. In that way, one has obtained either P = 1 or P = -1. Associate with P = 1 the bit state zero \000 and with P = -1 the bit state \111. Then the bit is either in state zero or one, depending on the way or context it was inferred.

This kind of contextuality is deeply rooted in the non-Boolean algebraic structure of quantum propositions. Note also that the above argument relies heavily on counterfactual reasoning, because, for instance, only two of the six observables mij can actually be experimentally determined.

3.4  Classical versus quantum tautologies

I shall review the shortest example of a classical tautology which is not valid in threedimensional (real) Hilbert space that is known up-to-date [66].

Consider the propositions

d1
b2     ,
(96)
d1
b3    ,
(97)
d2
a2 b2    ,
(98)
d2
b3    ,
(99)
d3
b2    ,
(100)
d3
( a1a2 b3)    ,
(101)
d4
a2 b2    ,
(102)
d4
( a1a2 b3)    ,
(103)
(a2
c1) (b3 d1)    ,
(104)
(a2
c2) (a1 b1 d1)    ,
(105)
c1
b1 d2    ,
(106)
c2
b3 d2    ,
(107)
(a2
c1) [ (a1 a2 b3)d3]    ,
(108)
(a2
c2) (b1 d3)    ,
(109)
c2
[ (a1 a2 b3)d4]    ,
(110)
c1
(a1 b1 d4)    ,
(111)
(a1
a2)b1     .
(112)
The proposition formed by F: (96) (111)(112) is a classical tautology.

F is not valid in threedimensional (real) Hilbert space E3, provided one identifies the a's, b's, c's and d's with the following onedimensional subspaces of E3:

a1
\frak S(1,0,0)     ,
(113)
a2
\frak S(0,1,0)     ,
(114)
b1
\frak S(0,1,1)     ,
(115)
b2
\frak S(1,0,1)     ,
(116)
b3
\frak S(1,1,0)     ,
(117)
c1
\frak S(1,0,2)     ,
(118)
c2
\frak S(2,0,1)     ,
(119)
d1
\frak S(-1,1,1)    ,
(120)
d2
\frak S(1,-1,1)    ,
(121)
d3
\frak S(1,1,-1)    ,
(122)
d4
\frak S(1,1,1)     ,
(123)
where \frak S(v) = {av \mid a \Bbb R} is the subspace spanned by v.

Let the ``or'' operation be represented by \frak S(v)\frak S(w) = {av +bw\mid a,b \Bbb R} the linear span of \frak S(v) and \frak S(w).

Let the ``and'' operation be represented by \frak S(v)\frak S(w) = \frak S(v)\frak S(w) the set theoretic complement of \frak S(v) and \frak S(w).

Let the complement be represented by \frak S(v) = {w\mid v·w = 0} the orthogonal subspace of \frak S(v).

Let the ``implication'' relation be represented by

\frak S(v) \frak S(w) (\frak S(v))\frak S(w).

Then, (96), , (111) = E3 , whereas (112)

= \frak S(1,0,0) E3. Therefore, at least for states lying in the direction (1,0,0) [67], F is not a quantum tautology.

The set of eleven rays can be represented by vectors from the center of a cube to the indicated points [64], as drawn in Fig. 8.

  


Picture Omitted

Figure 8: The eleven rays in the proof of the Kochen-Specker theorem based on the construction of Schütte are obtained by connecting the center of the cube to the black dots on its faces and edges.

Appendices

A  Hilbert space

[Field] A set of scalars K or (K,+,·) is a field if

(I)
to every pair a,b of scalars there corresponds a scalar a+b in such a way that

(i)
a+b = b+a (commutativity);
(ii)
a+(b+c) = (a+b)+c (associativity);
(iii)
there exists a unique zero element 0 such that a+0 = a for all a K;
(iv)
To every scalar a there corresponds a unique scalar -a such that a+(-a) = 0.

(II)
to every pair a,b of scalars there corresponds a scalar ab, called product in such a way that

(i)
ab = ba (commutativity);
(ii)
a(bc) = (ab)c (associativity);
(iii)
there exists a unique non-zero element 1, called one, such that a1 = a for all a K;
(iv)
To every non-zero scalar a there corresponds a unique scalar a-1 such that

aa-1 = 1.

(III)
a(b+c) = ab +ac (distributivity).

Examples: The sets \Bbb Q, \Bbb R, \Bbb C of rational, real and complex numbers with the ordinary sum and scalar product operators `` +, ·'' are fields.

[Linear space] Let M be a set of objects such as vectors, functions, series et cetera. A set M is a linear space if

(I)
there exists the operation of (generalised) ``addition,'' denoted by ``+'' obeying

(i)
f+g M for all f,g M (closedness under ``addition'');
(ii)
f+g = g+f (commutativity);
(iii)
f+(g+h)=(f+g)+h=f+g+h (associativity);
(iv)
there exists a neutral element 0 for which f+0 = f for all f M;
(v)
for all f M there exists an inverse -f, defined by f+(-f) = 0;

(II)
there exists the operation of (generalised) ``scalar multiplication'' with elements of the field (K,+,·) obeying

(vi)
a K and f M then af M (closedness under ``scalar multiplication'');
(vii)
a(f+g) = af+ag and (a+b)f = af+bf (distributive laws);
(viii)
a(bf) = (ab)f = abf (associativity);
(ix)
There exists a ``scalar unit element'' 1 K for which 1f = f for all f M.

Examples:

(i) vector spaces M = \Bbb Rn with K = \Bbb R or \Bbb C;

(ii) M = l2, K = \Bbb C, the space of all infinite sequences

l2 = { f\mid f = (x1, x2,, xi,),  xi \Bbb C,   

i = 1 
|xi|2 < }    ,

(iii) the space of continuous functions, complex-valued (real-valued) functions M = C(a,b) over an open or closed interval (a,b) or [a,b] with K = \Bbb C (K = \Bbb R);

[Metric, norm, inner product] 
A metric, denoted by dist, is a binary function which associates a distance of two elements of a linear vector space and which satisfies the following properties:

(i)
dist(f,g) \Bbb R for all f,g M;
(ii)
dist(f,g) = dist(g,f) for all f,g M;
(iii)
dist(f,g) = 0 f = g;
(iv)
dist(f,g) dist(f,h)+dist(g,h) for all h M and every pair f,g M.

A norm ||·|| on a linear space M is a unary function which associates a real number to every element of M and which satisfies the following properties:

(i)
||f || 0 for all f M;
(ii)
||f|| = 0 f = 0;
(iii)
||f+g|| ||f||+||g ||;
(iv)
||af|| = |a | ||f|| for all a K and f M (homogeneity).

An inner product ·\mid · is a binary function which associates a complex number with every pair of elements of a linear space M and satisfies the following properties (* denotes complex conjugation):

(i)

f \mid g = g \mid f* for all f,g M;

(ii)

f \mid ag = a f \mid g for all f,g M and a K;

(iii)

f \mid g1 +g2 = f \mid g1 + f \mid g2 for all f,g1,g2 M;

(iv)
f\mid f 0 for all f M;
(v)
f\mid f = 0 f = 0.

Remarks:

(i) With the identifications

||f||
=
f |f1/2    ,
(124)
dist(f,g)
=
||f-g||    ,
(125)
features & structures are inherited in the following way:

M has an inner product
    \rlap/
M has a norm
    \rlap/
M has a metric.

(ii) The Schwarz inequality
|f\mid g| ||f||||g||
(126)
is satisfied.

[Separability, completeness] 
A linear space M is separable if there exists a sequence {fn \mid n \Bbb N, fn M} such that for any f M and any e > 0, there exists at least one element fi of this sequence such that

||f-fi|| < e    .
A linear space M is complete if any sequence { fn\mid n \Bbb N, fn M} with the property

lim
i,j  
||fi-fj|| = 0
defines a unique limit f M such that

lim
i  
||f-fi|| = 0    .

[Hilbert space, Banach space] 
A Hilbert space \frak H is a linear space, equipped with an inner product, which is separable & complete.

A Banach space is a linear space, equipped with a norm, which is separable & complete.

Example:

l2,\Bbb C [see linear space example (ii)] with f\mid g = i xi* yi.

[Subspace, orthogonal subspace] 
A subspace § \frak H of a Hilbert space is a subset of \frak H which is closed under scalar multiplication and addition, i.e., f,g H, a K af §,  f+g §, and which is separable and complete.

An orthogonal subspace § ^ of § is the set of all elements in the Hilbert space \frak H which are orthogonal to elements of § , i.e.,

§ ^ = { f \mid f \frak H,  f\mid g = 0, for all  g § }.

Remarks:

(i)^)^ = § ^^ = § ;

(ii) every orthogonal subspace is a subspace;

(iii) A Hilbert space can be represented as a direct sum of orthogonal subspaces.

[Linear functional] A map F:\frak H K is a linear functional on \frak H if

(i)
F(f+g) = F(f)+F(g),
(ii)
F(af) = aF(f) with f,g \frak H, a K.

A linear functional is bounded if |F(f)| a||f|| with a \Bbb R+ for all f \frak H.

[Dual Hilbert space] There exists a one-to-one map between the elements f of a Hilbert space \frak H and the elements of F of the set \frak Hf of bounded linear functionals on \frak H, such that

Ff(g) = f\mid g       .
With the operations (f,g \frak H, a K)

(i)
Ff+Fg = Ff+g,
(ii)
aFf = Fa* f,
(iii)
Ff\mid Fgf = g\mid f

\frak Hf is the dual Hilbert space of \frak H.

Remarks:

(i) \frak H = { f,g,h, } and \frak Hf = { Ff,Fg,Fh, } are isomorphic; instead of h Fh, one could write hF F;

(ii) (\frak Hf )f = \frak H.

[Isomorphism of Hilbert spaces] All separable Hilbert spaces of equal dimension with the same field K are isomorphic.

B  Mathematica code for quantum interference

B.1  Mach-Zehnder interferometer

 x=a;
 x = x/. a -> (b + I c)/Sqrt[2];
 x = x/. b -> b Exp[I p];
 x = x/. b -> (e + I d)/Sqrt[2];
 x = x/. c -> (d + I e)/Sqrt[2];
 Print[Expand[x]];

B.2  Mandel interferometer

x=a;
x = x/. a -> (b + I c)/Sqrt[2];
x = x/. b -> eta *d*e;
x = x/. c -> eta *h*k;
x = x/. h -> h Exp[I p];
x = x/. e -> (T* g + I*R*f);
x = x/. h -> (l + I m)/Sqrt[2];
x = x/. d -> (m + I l)/Sqrt[2];
x = x/. g -> k;
(*
x = x/. T -> 1;
x = x/. R -> 0;
x = x/. m -> 0;
x = x/. f -> 0;
*)
Print[Expand[x]];

References

[1]
M. Planck, Annalen der Physik 1, 69 (1900).

[2]
M. Planck, Verhandlg. dtsch. phys. Ges. 2, 202; Verhandlg. dtsch. phys. Ges. 2, 237; Annalen der Physik 4, 553 (1901).

[3]
A. Einstein, Annalen der Physik 16, 132 (1905).

[4]
M. Planck, Annalen der Physik 50, 385 (1916).

[5]
A. Sommerfeld, Atombau und Spektrallinien (Vieweg, Braunschweig, 1924).

[6]
A. Einstein, Grundzüge der Relativitätstheorie, (Vieweg, Braunschweig, 1973).

[7]
M. Jammer, The Philosophy of Quantum Mechanics (John Wiley, New York, 1974).

[8]
J. A. Wheeler and W. H. Zurek, eds.,

Quantum Theory and Measurement (Princeton University Press, Princeton, 1983).

[9]
P. A. M. Dirac, The Principles of Quantum Mechanics (Oxford University Press, Oxford, 1947).

[10]
J. von Neumann, Mathematische Grundlagen der Quantenmechanik (Springer, Berlin, 1932) [English translation: Mathematical Foundations of Quantum Mechanics (Princeton University Press, Princeton, 1955)].

[11]
A. Messiah, Quantum Mechanics, Volume I (North-Holland, Amsterdam, 1961).

[12]
R. P. Feynman, R. B. Leighton and M. Sands, The Feynman Lectures on Physics, Vol. III, Quantum Mechanics (Addison-Wesley, Reading, 1965).

[13]
E. G. Harris, A Pedestrian Approach to Quantum Field Theory (Wiley-Interscience, New York, 1971).

[14]
L. E. Ballentine, Quantum Mechanics (Prentice Hall, Englewood Cliffs, 1989); for a short expose, see also L. E. Ballentine, Rev. Mod. Phys. 42, 358 (1970).

[15]
J.-M. Lévy-Leblond and Françoise Balibar, Quantics (North-Holland, Amsterdam, 1990).

[16]
A. Peres, Phys. Rev. A32, 3266 (1985).

[17]
M. Reck, A. Zeilinger, H. J. Bernstein and P. Bertani, Phys. Rev. Lett. 73, 58 (1994).

[18]
D. B. Greenberger and A. YaSin, Foundation of Physics 19, 679 (1989).

[19]
E. Schrödinger, Naturwissenschaften 23, 807; 823; 844 (1935) [English translation in [8] p. 152].

[20]
A. S. Davydov, Quantum Mechanics (Addison-Wesley, Reading, MA, 1965).

[21]
R. U. Sexl and H. K. Urbantke, Relativität, Gruppen, Teilchen (Springer, Vienna, 1976).

[22]
J. M. Jauch, The Theory of Photons and Electrons (Addison-Wesley, Cambridge, MA, 1955).

[23]
D. Luriè, Particles and Fiels (Interscience Publishers, New York, 1968).

[24]
N. N. Bogoliubov and D. V. Shirkov, Introduction to the Theory of Quantized Fields (Wiley-Interscience, New York, 1959).

[25]
C. Itzykson and J.-B. Zuber, Quantum Field Theory (MacGraw-Hill, New York, 1980).

[26]
H. J. Lipkin, Quantum Mechanics, New Approaches to Selected Topics (North-Holland, Amsterdam, 1973).

[27]
R. J. Glauber, Quantum Theory of Coherence, in Quantum Optics: Proceedings of the Scottish Universities' Summer School in Physics, 1969 , ed. by S. M. Kay and A. Maitland (Academic Press, London, 1970).

[28]
R. Loudon and P. L. Knight, Journal of Modern Optics 34, 709 (1987).

[29]
D. B. Greenberger, M. Horne and A. Zeilinger Physics Today 46, 22 (August 1993).

[30]
B. Yurke, S. L. McCall and J. R. Clauder, Phys. Rev. A 33, 4033 (1986).

[31]
R. A. Campos, B. E. A. Saleh and M. C. Teich, Phys. Rev. A 42, 4127 (1990).

[32]
M. Born and E. Wolf, Principles of Optics: Electromagnetic Theory of Propagation, Interference and Diffraction of Light, (6th edition) (Pergamon Press, Oxford, 1993).

[33]
Ch. Bennett, Nature 371, 694 (1994).

[34]
X. Y. Zou, L. J. Wang and L. Mandel, Phys. Rev. Lett. 67, 318 (1991); Phys. Rev. A 44, 4614 (1991).

[35]
A. Shimony, Controllable and uncontrollable non-locality, in Proc. Int. Symp. Foundations of Quantum Mechanics, ed. by S. Kamefuchi et al. (Physical Society of Japan, Tokyo, 1984), reprinted in [37], p. 130.

[36]
A. Shimony, Events and Processes in the Quantum World, in Quantum Concepts in Space and Time, ed. by R. Penrose and C. I. Isham (Clarendon Press, Oxford, 1986), reprinted in [37], p. 140.

[37]
A. Shimony, Search for a Naturalistic World View, Volume II (Cambridge University Press, Cambridge, 1993).

[38]
N. Herbert, Foundation of Physics 12, 1171 (1982).

[39]
W. K. Wooters and W. H. Zurek, Nature 299, 802 (1982).

[40]
L. Mandel, Nature 304, 188 (1983).

[41]
P. W. Milonni and M. L. Hardies, Phys. Lett. 92A, 321 (1982).

[42]
R. J. Glauber, Amplifiers, Attenuators and the Quantum Theory of Measurement, in Frontiers in Quantum Optics, ed. by E. R. Pikes and S. Sarkar (Adam Hilger, Bristol 1986).

[43]
C. M. Caves, Phys. Rev. D 26, 1817 (1982).

[44]
G. Birkhoff and J. von Neumann, Annals of Mathematics 37, 823 (1936).

[45]
J. M. Jauch, Foundations of Quantum Mechanics (Addison-Wesley, Reading, Massachusetts, 1968).

[46]
E. P. Specker, Dialectica 14, 175 (1960); reprinted in [47].

[47]
E. Specker, Selecta (Birkhäuser Verlag, Basel, 1990).

[48]
S. Kochen and E. P. Specker, The calculus of partial propositional functions, in Proceedings of the 1964 International Congress for Logic, Methodology and Philosophy of Science, Jerusalem (North Holland, Amsterdam, 1965), p. 45-57; reprinted in [47].

[49]
S. Kochen and E. P. Specker, Logical Structures arising in quantum theory, in Symposium on the Theory of Models, Proceedings of the 1963 International Symposium at Berkeley (North Holland, Amsterdam, 1965), p. 177-189; reprinted in [47].

[50]
S. Kochen and E. P. Specker, Journal of Mathematics and Mechanics 17, 59 (1967); reprinted in [47].

[51]
Erna Clavadetscher-Seeberger, Eine partielle Prädikatenlogik (Dissertation, ETH-Zürich, Zürich, 1983).

[52]
J. Czelakowski, Logics based on partial Boolean s-algebras, Studia Logica 33, 371 (1974).

[53]
R. Landauer, Physics Today 44, 23 (Mai 1991).

[54]
R. W. Hamming, Coding and Information Theory, Second Edition (Prentice-Hall, Englewood Cliffs, New Jersey, 1980).

[55]
D. Z. Albert, Phys. Lett. 98A, 249 (1983).

[56]
P. Benioff, J. Stat. Phys. 29, 515 (1982); Phys. Rev. Lett. 48, 1581 (1982).

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

[58]
R. P. Feynman, Opt. News 11, 11 (1985).

[59]
P. Benioff, Annals New York Akademy of Sciences 480, 475 (1986).

[60]
N. Margolus, Annals New York Akademy of Sciences 480, 487 (1986).

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

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

[63]
A. Einstein, B. Podolsky and N. Rosen, Phys. Rev. 47, 777 (1935).

[64]
A. Peres, Quantum Theory: Concepts & Methods (Kluwer Academic Publishers, Dordrecht, 1993).

[65]
N. D. Mermin, Rev. Mod. Phys. 65, 803 (1993).

[66]
K. Schütte, letter to Professor Ernst P. Specker, dated from April 22nd, 1965; first published in [51].

[67]
R. Clifton, private communication.

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


Footnotes:

1 After some earlier proposals which failed [], Planck arrived at the assumption of a discretization of energy levels associated with a particular oscillator frequency by the careful analysis of all derivation steps leading to the experimentally obtained form of the blackbody radiation.

2 The energy spectrum is the distribution of energy over the frequencies at a fixed temperature of a ``black body.'' A ``black body'' is thereby defined as any physical object which is in internal equilibrium. Assume that absorption and reflection processes play a minor rôle. Then, depending on the temperature, but irrespective of its surface texture, a ``black body'' will appear to us truly black (room temperature), warm red (3000 Kelvin), sun-like (5500 K), blue ( > 7000 K).

3 It indeed seems to be the case that the observations of blackbody radiation, photoluminescence, the generation of cathode rays by ultraviolet light and other phenomena related to the generation and annihilation of light, would become better understandable with the assumption that the energy of light is distributed discontinuously in space. According to the assumption proposed here, the radiation energy of light from a point source is not spread out continuously over greater and greater spatial regions, but instead it consists of a finite number of energy quanta which are spatially localized, which move without division and which can only be absorbed and emitted as a whole.

4 Again it is confirmed that the quantum hypothesis is not based on energy elements but on action elements, according to the fact that the volume of phase space has the dimension hf.

5 There are good reasons to assume that nature cannot be represented by a continuous field. From quantum theory it could be inferred with certainty that a finite system with finite energy can be completely described by a finite number of (quantum) numbers. This seems not in accordance with continuum theory and has to stipulate trials to describe reality by purely algebraic means. Nobody has any idea of how one can find the basis of such a theory.

6 Thereby, `` \mid \mid = \mid ''.

7 the expressions should be intrepreted in the sense of operator equations; the operators themselves act on states.

8 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 forseen; 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 unforseen 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.

9 of course, there is only ``the one and only'' quantization, the term ``second'' often refers to operator techniques for multiqanta systems; i.e., quantum field theory

10 A Mathematica program for this computation is in appendix B.1.

11 A Mathematica program for this computation is in appendix B.1.

12 in a sense, qbits are the most elementary incarnation of the ``mysterium quanticum.''

13 Copying of qbits would allow circumvention of the Heisenberg uncertainty relation by measuring two incompatible observables on two identical qbit copies. It would also allow faster-than-light transmission of information [].

14 the most elementary realization is a one-mode field with the symbol \000 corresponding to \mid 0 (empty mode) and \111 corresponding to \mid 1 (one-quantum filled mode).


File translated from TEX by TTH, version 1.94.
On 9 Sep 1999, 13:53.