16

assume for a moment that hidden variables exist. then the measurement is fundamentally deterministic, but appears probabilistic because some degrees of freedom of the system (described by the hidden variables) are not known. to illustrate the idea, let us consider again the spin- 1 particle. suppose that the particle is prepared initially in state | ?z ) and that a hidden variable ? determines the outcome of spin measurement on that particle along any axis nˆ? characterized by the rotation angle ? about the y axis. since during the preparation stage we have no control over the hidden variable, it is reasonable to assume that ? is a random number uniformly distributed over the unit interval 0 ? ? ? 1 with the probability distribution ?(?) = const which is
normalized as ¸ 1 ?(?)d? = 1. then the spin measurement along the axis nˆ
0 ?
rotated by the angle ? yields the spin-up state | ?? ) if 0 ? ?< cos2 ? , and the
spin-down state | ?? ) if cos2 ? ? ? ? 1. for example, in the case of ? = ?/2, we have nˆ?/2 = xˆ. then the | ?x) state is obtained if 0 ? ? < 1 , while the
| ?x) state is obtained if 1 ? ? ? 1.


z
da ?a a
?y
x

pa



s
(epr pairs)

z
b ?b db
y
x

pb


fig. 8.11. schematic representation of bell’s setup: s is the source of correlated (en- tangled) particles a and b, measured by corresponding apparatuses each consisting of analyzer pi and detector di.


considering the case of two spatially separated but correlated particles, bell, however, has shown that certain statistical predictions of quantum me- chanics are incompatible with hidden variable theories based on local realism. let us outline his arguments following the treatment of clauser and horne. suppose that epr correlated (entangled) particles a and b are produced by a source of such particles, one pair at a time. the particles a and b ?y in the opposite directions towards their respective analyzer–detector appara- tuses. each apparatus has an adjustable parameter characterized by variable ?, which may denote, e.g., the angle of the analyzer de?ning the measurement

axis for spin- 1

particles or for photon polarization, as shown schematically

in fig. 8.11. for ?xed values of the parameters ?a and ?b, the probability
pab(?, ?a, ?b) of simultaneous detection of both particles is a function of a hidden variable, or a set of such, collectively denoted by ?. since the two ap- paratuses are assumed to be separated by su?ciently large distance, according to einstein’s locality constraint, the space-like separated detection events can not in?uence one another. then the joint probability pab should factorize into


the product of individual detection probabilities pa and pb, according to
pab(?, ?a, ?b)= pa(?, ?a) pb(?, ?b) . (8.43)

at the system preparation and detection stages, we can neither control nor determine the hidden variables ?. let us therefore characterize ? by some
probability distribution ?(?) normalized in the usual way ¸? ?(?)d? = 1,
where ? encompasses the complete range of possible values of ? (? ? ? ). performing many identical measurements with ?xed parameters of the system, the observed ensemble averaged probabilities are given by
¸

pa(?a)=
?
¸
pb(?b)=
?
¸
pab(?a, ?b)=
?

pa(?, ?a)?(?)d?, (8.44a)

pb(?, ?b)?(?)d?, (8.44b)

pab(?, ?a, ?b)?(?)d?. (8.44c)


below we use a theorem from number theory, stating that for any four numbers x1, x2, y1, y2, such that 0 ? x1,2, y1,2 ? 1, the inequality
?1 ? x1y1 ? x1y2 + x2y1 + x2y2 ? x2 ? y1 ? 0 (8.45)


is always satis?ed (prob. 8.4). let us denote by ?a, ?r

and ?b, ?r

four pos-

sible values of the parameters of apparatuses measuring particles a and b,
respectively. since for any ?a, ?b and ?, physically meaningful probabilities must satisfy 0 ? pa(?, ?a), pb(?, ?b) ? 1, we can use (8.45) to write
?1 ? pa(?, ?a)pb(?, ?b) ? pa(?, ?a)pb(?, ?r )
+pa(?, ?r )pb(?, ?b)+ pa(?, ?r )pb(?, ?r ) ? pa(?, ?r )+ pb(?, ?b) .

a a b

a
(8.46)


multiplying all terms of this inequality by ?(?) and integrating over ? taking into account (8.43), we obtain
?1 ? pab(?a, ?b) ? pab(?a, ?r )
+pab(?r , ?b)+ pab(?r , ?r ) ? pa(?r )+ pb(?b) . (8.47)
a a b a

if, due to, e.g., rotational invariance, the probabilities pa(?a) and pb(?b) are constant and the joint probability pab(?a, ?b) = pab(??) is a function of only the angle di?erence ?? = |?a ? ?b|, by choosing the four angles so that
1

|?a ? ?b| = |?r

? ?b| = |?r

? ?r | = 3 |?a ? ?r | = ?,

a a b b

from (8.47) we obtain the so-called bell’s inequality


s(?)=

3pab (?) ? pab(3?)
pa + pb


? 1 . (8.48)

below we show that in the cases of epr correlated spin- 1

particles and

polarization-entangled single photons, such rotational invariance is indeed sat-
is?ed and that for a certain range of angles ?, the values of function s(?) ex- ceed 1, violating bell’s inequality (8.48). this proves that any hidden variable theory based on einstein’s conviction of local realism is incompatible with cer- tain predictions of quantum mechanics, which can be tested experimentally.


violations of bell’s inequality

we outline now two physical schemes for testing bell’s inequality (8.48) against experimentally con?rmed predictions of quantum mechanics.


1
entangled spin- 2 particles
consider ?rst two spin- 1 particles a and b in the entangled state
1 a b a b
|?2) = ? ( | ?z )| ?z ) + | ?z )| ?z )) . (8.49)

in a real experiment, these particles could be, e.g., hg atoms. then the en- tangled state (8.49) could be realized in two steps: first, a hg2 molecule is
photodissociated into the singlet state 1 ( | ?z )| ?z )? | ?z )| ?z )), whose two
? a b a b
2
constituent particles (atoms) a and b ?y in opposite directions, parallel and
anti-parallel to the y axis, respectively. next, a longitudinal magnetic ?eld is applied to one of the particles to rotate its spin around the y axis by angle ?, realizing thereby the ?y transformation that results in state (8.49), to within the trivial overall phase factor ei?/2 which can be omitted.


stern?gerlach apparatus
? z
y x

fig. 8.12. spin- 1 particle passing through a stern–gerlach apparatus rotated by angle ? with respect to the z axis.


let us ?rst determine the probability of detecting a spin- 1 particle in the spin-up state | ?? ) along the axis rotated by angle ? with respect to the z


axis. such a measurement can be realized by letting the particle pass a stern– gerlach apparatus and detecting its upward de?ected component, as sketched in fig. 8.12. this amounts to projecting the state of the particle onto the state
| ?? ), which can be obtained by applying the rotation operator ry (?) to state
| ?z ) (see sect. 8.4),


| ?? ) = ry (?) | ?z ) = e?i??y /2 | ?z ) = cos


?
2 | ?z ) + sin


?
2 | ?z ) .

the probability p (?) of detecting the particle in state | ?? ) is then given by the expectation value of the projection operator ?? = | ?? )(?? | , p (?)= (?? ). if we now have a system of two spin- 1 particles a and b, each analyzed by its own stern–gerlach apparatus rotated by the corresponding angle ?a,b, the joint detection probability pab(?a, ?b) is given by the expectation value

of the product of two projection operators ? a

= | ?a

a
)(??a

| and ??b =

b b a b
| ??b )(??b | , pab(?a, ?b)= (??a ??b ).
we can now easily calculate all detection probabilities for a pair of particles in the entangled state (8.49). for pa and pb we have
1
pa(?a)= pb(?b)= 2 (8.50)
for any ?a and ?b, while for the joint detection probability pab we obtain

1
pab(?a, ?b)= 2 cos

2 . ?a ? ?b .
2


. (8.51)


equations (8.50) and (8.51) show that the rotational invariance assumed in the derivation of function s(?) is indeed satis?ed in this case. choosing the

four detection angles as ?a = 0, ?b = ?/4, ?r

= ?/2 and ?r

= 3?/4 yields

? = ?/4. from (8.48) we then obtain


s(?)=

cos2 . . cos2 . .


1.2 ¢ 1 , (8.52)

3 ? 1 3?
2 2 ? 2 2 c

which clearly violates bell’s inequality. hence, the predictions of quantum me- chanics, which have been veri?ed in many experiments, contradict and thereby invalidate the hidden variable theories based on einstein’s local realism. this leads to the inescapable conclusion that quantum mechanics is a nonlocal theory.


entangled photons

we now describe an optical scheme for testing bell’s inequality (8.48) using pairs of photons in the entangled state
1 a b a b

|?2) = ?2 ( |‡ )| ‡

) + |? )| ?

)) . (8.53)


in fact, most of the experimental tests of bell’s inequalities have been per- formed using polarization-entangled photon pairs. these include a series of pioneering experiments by aspect and coworkers, using atomic radiative cas- cade, as well as a number of experiments by several teams using nonlin- ear crystals to realize spontaneous parametric down-conversion. in the for- mer experiments, a high-e?ciency source of pairs of photons, at frequencies ?a = 2? × 7.102 × 1014 rad/s and ?b = 2? × 5.44 × 1014 rad/s, was obtained by two-photon excitation of state 4p2 1s0, via the intermediate state 3d4p 1p1, of
?a ?b
the 4p2 1s0 ?? 4s4p1p1 ?? 4s2 1s0 radiative cascade in calcium. the polariza-
tion entanglement of the photons comes about because of angular momentum conservation. since relative to photons, the atoms are massive objects, their recoil during photon emission is negligible. therefore, in addition to the polar- ization entanglement, the propagation directions of the two photons are also strongly correlated, due to energy and momentum conservation. in the experi- ments with nonlinear crystals possessing the ?(2) nonlinearity, a pump photon at frequency ?p is converted into a pair of photons (called signal and idler) with the frequencies ?s ? ?a and ?i ? ?b such that ?s +?i = ?p. here again, angular momentum conservation imposes polarization entanglement between the photons, while the phase-matching conditions result in a ?nite angle be- tween the propagation directions of the photons, which makes it possible to redirect each photon to its own measuring apparatus. the measurements in di?erent bases are realized by detecting photons that go through the usual optical polarizers rotated by the corresponding angle ?. this amounts to pro- jecting the state of each photon onto the corresponding state |?), obtained by rotating the vertical polarization state | ‡) with the rotation operator r(?) of (8.29),
|?) = r(?) | ‡) = cos ? | ‡) + sin ? | ?) .
then the individual and joint detection probabilities pa(?a) = (?a ),
pb(?b) = (?b ) and pab(?a, ?b) = (?a ?b ) are given by the expecta-
?b ?a ?b

tion values of the corresponding projection operators ? a

= |?a)(?a| and


?b b b

?a a a

?b = |?b )(?b | .
when the two photons are in the entangled state (8.53), similarly to the case of spin- 1 particles, the quantum mechanical calculation of the detection probabilities yields
1
pa(?a)= pb(?b)= 2 , (8.54)

1 2
pab(?a, ?b)= 2 cos

(?a ? ?b) . (8.55)

choosing the four detection angles as ?a = 0, ?b = ?/8, ?r

= ?/4 and

?b = 3?/8, we obtain ? = ?/8 and, correspondingly,

3
s(?)=
2


cos2(?) ?

1 cos2(?) 1.2 ¢ 1 , (8.56)
2


1.5


1


0.5


0



?0.5


0 ?/8 ?/4 3?/8 ?/2
?


fig. 8.13. variation of the function s(?) with angle ?, as given by (8.56). the dashed line represents the upper bound of bell’s inequality (8.48).


which again violates bell’s inequality, refuting any hidden variable theory based on local realism. as shown in fig. 8.13, where we plot the function s(?), inequality (8.48) is violated for the values of angle ? in the range 0 < ? < 3?/16. the strongest violation, however, is attained in the vicinity of ? c ?/8.


greenberger–horne–zeilinger equality

we have seen above that certain statistical predictions of quantum mechanics, which require averaging over a large number of measurements by repeating the experiment many times, violate bell’s inequality (8.48). in 1989 greenberger, horne and zeilinger—ghz—discovered a more powerful test of the existence of elements of reality which may be hidden from us due to our inability to control and detect them for whatever reason. in the experiment proposed by ghz, such elements of reality, if existing, would reveal themselves in just a single measurement, and in complete violation of the predictions by quantum mechanics.
following ghz, instead of the epr entangled state of two spin- 1 particles,
we consider the three particle entangled state

1 a b c


a b c

|?3) = ? ( | ?z )| ?z )| ?z )? | ?z )| ?z )| ?z )) . (8.57)

as before, let us assume that all three constituent particles a, b and c of this state are separated from each other by su?ciently large distances, so that the measurement performed at each particle site can not in?uence the other
two. consider three composite operators, s1 = ?a?b?c, s2 = ?a?b?c, and

x y y

y x y

s3 = ?a?b?c, where the superscript of each pauli operator indicates the
y y x


particle upon which that operator acts. using (8.19), it is easy to see that all three operators si (i = 1, 2, 3) mutually commute,
[s1, s2]= [s2, s3]= [s3, s1]=0 .

in addition, the ghz state (8.57) is a simultaneous eigenstate of these oper- ators, with the eigenvalue +1,
s1 |?3) = s2 |?3) = s3 |?3) = +1 |?3) . (8.58)

this means that the product of the result of three spin measurements as given by the operators si (i.e., any two spins along the y axis and the third spin along the x axis), has to be +1. consider, for example, operator s1: if the measurements on particles b and c result in the +1 eigenvalue of ?b
and ?1 eigenvalue of ?c, then measuring ?a on particle a has to yield the
y x
a b c
eigenvalue ?1, i.e., the state is | ?x )| ?y )| ?y ). other possible outcomes of the

a b c

a b c

a b c

s1 measurement are | ?z )| ?y )| ?y ), | ?z )| ?y )| ?y ), and | ?x )| ?y )| ?y ).
equivalent reasoning applies to the operators s2 and s3.
consider next the operator s4 = ?a?b?c. using the equalities ?2 = i
x x x y
and ?y ?x = ??x?y , it is easy to show that s4 = ?s1s2s3. since all three
operators s1, s2 and s3 have the eigenvalue +1, the eigenvalue of s4 is ?1,
s4 |?3) = ?1 |?3) . (8.59)
thus, all of the possible outcomes of the s4 measurement on state (8.57) are

a b c

a b c

a b c

a b c

| ?x )| ?x )| ?x ), | ?x )| ?x )| ?x ), | ?z )| ?x )| ?x ) and | ?z )| ?x )| ?x ).
let us now assign to the operators ?j and ?j (j = a,b,c) the correspond-
x y

ing “elements of reality” mj

and mj , each having the value +1 or ?1 which

is revealed by the relevant measurement. from (8.58) we have


ma b c


a b c


a b c

x my my =1 , my mx my =1 , my my mx =1 . (8.60)
multiplying the three equalities and taking into account that (mj )2 = 1, we

obtain


(mambmc)(mambmc)(mambmc)

x y y

y x y

y y x

= mambmc(ma)2(mb)2(mc)2
x x x y y y
= mambmc =1 . (8.61)
x x x
on the other hand, the quantum mechanical prediction from (8.59) is

ma b c
x mx mx = ?1 , (8.62)

which contradicts (8.61). several recent experiments by zeilinger and cowork- ers, using three- and four-photon ghz states have clearly con?rmed the quan- tum mechanical result, refuting the hypothesis of the existence of elements of reality.


8.9 entropy and information theory

a pivotal theme of information theory—both classical and quantum—is the quanti?cation of the information, produced by a source, through the smallest amount of memory needed to faithfully represent it, or the minimum amount of communication needed to reliably convey it. in classical information the- ory, this reduces to the compressibility of information characterized by a given probability distribution of its source, the measure of which is shannon’s en- tropy. in quantum information theory, it is the von neumann entropy that plays the same role. a novel feature of quantum information theory, not having a classical counterpart, is quantum entanglement, which, as we have already seen, is a vital information resource hence the necessity of verifying and quan- tifying the entanglement, which is a very active topic of current research. our aim in this section is to outline certain aspects of information theory, whose detailed discussion is beyond the scope of this book.


the shannon entropy

consider a message composed of a long string of letters x(1), x(2),..., x(n) chosen from a binary alphabet, e.g., x ? {0, 1}. assume that the letters in the message are statistically independent, with 0 appearing with probability p0 ? p and 1 with probability p1 = 1 ? p. when n is very large, a typical message would contain about np zeros and n(1 ? p) ones. the number of such
messages is given by the binomial coe?cient . n . which can be approximated

as


where the function

. n .
np


nhbin (p)
c


hbin(p)= ?p log2 p ? (1 ? p) log2(1 ? p) (8.63)

is referred to as the shannon entropy of a binary source. clearly 0 ? hbin(p) ? 1, with hbin(p) = 0 when p = 0 or 1, and hbin(p) = 1 when p = 1 . let us assign to each typical message a positive integer number, which can be repre- sented by a binary string of length nhbin(p). then, to convey a typical mes- sage between two parties, instead of sending the message itself, it is enough to sent the binary string identifying that message. that string is shorter than the original message, since hbin(p) < 1 for any p ƒ= 1 . this procedure thus yields data compression. the fact that for p = 1 , corresponding to maximum shannon entropy, the data can not be compressed points to a physical inter- pretation of these concepts: p = 1 means completely random distribution of zeros and ones in a typical message string in which the sequence of letters contains no pattern. as such, the message has to be transferred as a whole and no compression can achieve the same result. it then makes perfect sense that maximum entropy is associated with maximum information. and it is


no accidental coincidence that maximum entropy in statistical physics is also associated with complete randomness.
the above result can be generalized to the case of an alphabet containing

k ? 2 letters, i.e., x ? {x1, x2,..., xk }. assuming that each letter xj appears with the corresponding probability pj (.j pj = 1), a typical message of length
n 1 would have np1 instances of x1, np2 instances of x2, etc. the total number of permutations in such message strings is given by
n!

%j (npj )! c

2nh(x) ,



where

h(x) ? h(p1, p2,..., pk )= . ?pj log2 pj (8.64)
j


is the shannon entropy of the ensemble x = {xj , pj }. again, we can assign to each typical message a positive integer number, and send that number to the receiver using only nh(p) bits. importantly, as the length n of the message grows, the probability of having to deal with an atypical message, in which the statistical weights of various letters xj deviate from the typical ones npj , quickly approaches zero. therefore, the above procedure achieves (asymptotically as n ? ?) optimal data compression with the rate h(x), which is shannon’s noiseless coding theorem.


the von neumann entropy

generalizing now the notion of entropy to quantum ensembles, for a quantum system characterized by the density operator ?, the so-called von neumann entropy s(?) of ? is de?ned as
s(?)= ?tr(? log2 ?) . (8.65) the von neumann entropy is invariant under unitary basis transformations,
s(u ? u †) = s(?), which follows from (1.48). choosing an orthogonal basis
{ |?i)} in which ? is diagonal,
? = . ?i |?i)(?i| ,
i
where ?i are the eigenvalues of ?, we can write
s(?)= ? . ?i log2 ?i = h(y ) , (8.66)
i

which shows that the von neumann entropy s(?) reduces to the shannon entropy h(y ) for the ensemble y = { |?i), ?i}. clearly, if the system is in a pure state ? = |? )(? | , its entropy vanishes, s(?) = 0. conversely, the entropy


attains the maximum s(?)= log2 n in the case of a completely mixed state

? = 1 .i

|?i)(?i| = 1 i, where n is the dimension of the corresponding

hilbert space.
we can now outline the quantum analog of the classical data compression, which is known as schumacher’s quantum noiseless coding theorem. consider a quantum source which produces messages composed of sequences of n 1 qubits represented by, e.g., polarization states of photons. assume that the possible states of the qubits are drawn for a set of distinct pure states { |?j )}, not necessarily orthogonal to each other, with each state occurring with the
respective probability pj (.j pj = 1). thus, each qubit in a message is char-
acterized by the density operator ? = .j pj |?j )(?j | and the whole message
is described by the tensor product density operator ??n = ????••• ?? which spans an n = 2n dimensional hilbert space h(n ). we can diagonalize ??n through an appropriate unitary transformation. the corresponding orthogonal basis states will be represented by the products of eigenstates |x0) and |x1) of individual qubits, while the eigenvalues of ??n will be products of eigenvalues p0 = p and p1 = 1 ? p of ?. in this basis, the information content of ??n is essentially that of a classical source producing message strings corresponding to |x(1), x(2),..., x(n)) with probabilities p(1)p(2) ... p(n). the von neumann entropy s(?) of ? is obviously equal to the shannon entropy hbin(p) of (8.63). this means that we have about m = 2nhbin (p) orthogonal message strings, which can be encoded in a quantum system whose hilbert space h(m ) is m di- mensional. this requires only ns(?)= nhbin(p) qubits, whose product space can therefore accommodate all the typical quantum messages with high ?- delity. since hbin(p) < 1 for any p ƒ= 1 , quantum data compression is thereby achieved. only for completely random qubits ? = 1 i (p = 1 ), in which case
2 2
s(?) = 1 (hbin(p) = 1), no compression is possible (m = n ), in complete
analogy with the classical case.

entropy as a measure of entanglement
consider a two-component (bipartite) quantum system a+b in a pure state
|?). to test whether the subsystems are entangled or not, following the prescription of sect. 1.3.3, we can perform the schmidt decomposition of
|?). if this decomposition has more than one term, i.e., the schmidt num- ber is greater than one, |?) is an entangled state, and the reduced den- sity operator of one of the subsystems, say a, represents a mixed state,
?a a a
mixed = trb( |?)(?| )= .i pi |?i )(?i | . on the other hand, for a factorisable
state of the form |?) = |? a)? |? b), the schmidt number is one, while the

reduced density operator of a represents a pure state ?a

= |? a)(? a| . re-

call that the von neumann entropy of a pure state ?a

is zero, s(?a

)= 0,

while it is maximized to s(?a

)= log2

n for a mixed state ?a

with all

pi = 1/n , which results from a maximally entangled state. thus the von neu-
mann entropy is a monotonic function of entanglement between a pair of sub- systems and is invariant under local unitary transformations, which do not


a?ect the entanglement. therefore the von neumann entropy of the density matrix for either subsystem of a bipartite system can serve as a convenient measure of entanglement, and is often referred to simply as the entropy of entanglement.
considering now a two-component quantum system in a mixed state rep- resented by the density operator ?, one measure of entanglement is the so- called entanglement of formation e(?), which is the minimum average en- tropy of entanglement of an ensemble of pure states { |?)} that represents
? = .? p? |?)(?| . in general, for multistate subsystems the entanglement of
formation is di?cult to calculate, but in the simplest case of subsystems repre- sented by two-state quantum systems (qubits), e(?) can be expressed through the concurrence c(?) de?ned as c(?) = max{0, ?1 ? ?2 ? ?3 ? ?4}, where ?1,..., ?4 are the square roots of the eigenvalues of matrix ???, taken in de-
creasing order. here ?? ? ?a?b ?? ?a?b, with ?? being the complex conjugate
y y y y
of ?, and ?a,b the pauli matrices acting on the corresponding qubits. several other measures of entanglement of bipartite quantum systems have been sug- gested, including the distillable entanglement and logarithmic negativity. all of these measures reduce to the (von neumann) entropy of entanglement in the case of pure states, and they share the important property of being the entanglement monotones, i.e., they do not increase under local operations and classical communication between the parties.
quantifying entanglement of bipartite quantum systems is an important and di?cult problem attracting at present much attention. in the general case of mixed states, the various measures of entanglement are nonequivalent, lead- ing to much debate in the scienti?c community. the entanglement of three- and more-component systems represents an even more di?cult problem. usu- ally one performs the pairwise decompositions of the compound system in all possible ways and then computes the measures of bipartite entanglements. this procedure, however, is capable of characterizing only certain aspects of multiparticle entanglement and for some states even fails to detect genuine en- tanglement. the characterization of multiparticle entanglement thus requires much further research.
before closing this section, let us note that most of the experiments aimed at detecting entanglement between quantum systems employ the so-called en- tanglement witnesses. in general, entanglement witnesses are linear inequali- ties for expectation (mean) values of appropriate physical observables, which upon violating the inequalities verify the presence of entanglement in a bipar- tite system. the bell inequalities described in the previous section are perhaps the most representative examples of entanglement witnesses.


problems

verify the truth table of fig. 8.3.


show that, if perfect cloning of quantum states were possible, then two distant parties, alice and bob, sharing a pair of entangled qubits in state
|b11) = 1 ( |0a) |1b)? |1a) |0b)), could communicate information with su-
perluminal velocity. (hint: let alice measure her qubit in either { |0), |1)} or
{ |+), |?)} basis. now show that if bob could perfectly clone his qubit, he would be able, with some probability, to ?nd out alice’s basis.)

in the epr protocol for quantum cryptography, in order to eavesdroping on the private key, eve may employ the strategy of generating the three qubit entangled states |ghz) = 1 ( |000) + |111)) and then sending the ?rst qubit to alice, the second one to bob and keeping the third qubit to her own. show that when alice and bob test the ?delity of their pairs by performing measurements in jointly determined random bases, on the average in one out of four measurements the correlation between the qubit states is violated. (hint: express the |ghz) state in the { |+), |?)} basis.)

prove that for any given four positive numbers x1, x2, y1, y2, such that 0 ? x1,2, y1,2 ? 1, the inequality
?1 ? x1y1 ? x1y2 + x2y1 + x2y2 ? x2 ? y1 ? 0
is always satis?ed. (hint: see j. f. clause and m. a. horne, phys. rev. d
10, 526 (1974).)

verify expressions (8.50) and (8.51) for the individual and joint detection probabilities pa(?a), pb(?b) and pab(?a, ?b) for a pair of particles in the entangled state (8.49). also, calculate pa(?a), pb(?b) and pab(?a, ?b) for
the two-particle singlet state 1 ( | ?z )| ?z )? | ?z )| ?z )).
? a b a b
2

given a pair of qubits in the pure entangled state |?2) = ? |0a) |1b) + ? |1a) |0b), calculate the concurrence c(?) de?ned on the previous page. show that for any two-qubit pure state |?2), the concurrence is equal to
c(?2)= |(?2|??2)| , with |??2)? ?a?b |??) . (8.67)
y y 2

(hint: see w. k. wootters, phys. rev. lett. 80, 2245 (1998).)


9

principles of quantum computation











in this chapter, after an outline of the general principles of operation of a quantum computer, we present several representative quantum algorithms for data processing and error correction. as we will see, these quantum algorithms can outperform their classical counterparts. the material here also serves to motivate the discussion in the next chapter pertaining to the physical imple- mentations of quantum computation.


9.1 operation of quantum computer

in the previous chapter we have studied the building blocks of a quantum information processing devise. these are the qubits which constitute the reg- ister where quantum information is stored, and the quantum logic gates which manipulate that quantum information. we discuss now the universal set of quantum gates and the principal steps involved in quantum computation.

9.1.1 universal gates for quantum computation

the universal set of quantum gates, capable or realizing any unitary trans- formation on a multiqubit register, consists of the single-qubit rotational op-

erations, such as ry (?) and rz (?r) for spin- 1

qubits or r(?) and t (?) for

photon-polarization qubits, and the cnot two-qubit logic gate. this is to be contrasted with the reversible classical computation, where the universal logic gate—the to?oli (or fredkin) gate—involves three bits. as we show below, however, any three-qubit controlled-controlled-u operation (including the quantum to?oli gate) can be decomposed into a sequence of two-qubit operations, which in turn can be implemented using the single-qubit rotations and cnot gate.
consider a general unitary operation u on a single qubit,
. e?i? cos ? ?e?i? sin ? .

u = ei? sin ? ei? cos ?

, (9.1)


where, for simplicity, we disregard an overall phase factor ei?. from the def- inition of the rotation operators ry and rz in (8.25) and matrix multipli- cation, it follows that there exist real numbers ?1, ?2, and ?3, such that u = rz (?1)ry (?2)rz (?3). indeed, by choosing the three angles ?i accord- ing to ?1 + ?3 = 2?, ?1 ? ?3 = 2?, and ?2 = 2?, we ?nd that the product of the three rotations yields the right-hand-side of (9.1).
next, we show that for any unitary matrix u , there exist matrices a, b and c such that abc = i and axbxc = u . indeed, by choosing a = rz (?1)ry (?2/2), b = ry (??2/2)rz (?(?1 + ?3)/2), and c = rz ((?3 ? ?1)/2), we have


abc = rz (?1)ry

. ?2 .
2

. ?2 .
ry ? 2

.
rz ?

?1 + ?3 .
2

r . ?3 ? ?1 .
z 2

= rz (?1)rz (??1)= i . (9.2)
using the equalities xx = i, xry (?)x = ry (??), and xrz (?)x = rz (??), we see that

axbxc = rz (?1)ry

. ?2 .
2

xry

. ?2 .
? 2

.
rz ?

?1 + ?3 .
2

xrz

. ?3 ? ?1 .
2

= rz (?1)ry

. ?2 .
2

xry

. ?2 .
? 2

.
xxrz ?

?1 + ?3 .
2

xrz

. ?3 ? ?1 .
2

= rz (?1)ry (?2)rz (?3)= u , (9.3)
which proves the statement.
=
a b c
fig. 9.1. circuit generating the controlled-u gate.


now it is easy to see that any two-qubit controlled-u operation can be simulated by the circuit of fig. 9.1, which involves only the single-qubit op- erations a, b, and c, and the two-qubit cnot gates. indeed, if the control (upper) qubit is in state |0), then the abc = i transformation is applied to the target (lower) qubit, while if the control qubit state is |1), the target qubit undergoes the transformation axbxc = u .

it turns out that not only the cnot gate but almost any two-qubit logic gate is universal. in particular, the cz (controlled-z) and ?swap (square-root
of swap) gates are almost as good as the cnot gate, since we can easily con-

struct circuits implementing the cnot transformation w ab

between qubits

a and b through the w ab and w ab

transformations,

cz ?swap

operation of quantum computer 253

w ab b

ab b

cnot = ry (?/2) wcz ry (??/2) , (9.4a)

w ab a

b ab a

ab

cnot = rz (??) rz (?) w?swap rz (2?) w?swap , (9.4b)

where the ?swap gate, de?ned via .w ab .

= w ab , has the following

matrix representation,
? 1 0 0 0 ?

? 0 0 0 ?

1+i

1? i

i?/4

?i?/4

w ab

? 0 0 ? = 1 ? 0 e e 0 ?

?swap = ? 0 12 i

1+i ? ? ?

?i?/4

i?/4

? . (9.5)

? 2 2 0 ?

2 ? 0 e

e 0 ?

0 0 0 1

0 0 0 ?

controlled? controlled?u
=
v v ? v
fig. 9.2. circuit generating the three-qubit controlled-controlled-u gate.


consider, ?nally, multi-qubit operations. an example of the three-qubit controlled-controlled-u gate and its decomposition into a sequence of two- qubit operations is shown in fig. 9.2, where the operator v is de?ned via vv = u (see prob. 9.1). when u corresponds to the x or not gate, and therefore v = 1 (1 ? i)(i + ix), this circuit realizes the universal quantum to?oli or ccnot gate. this ccnot gate can further be used to implement multiqubit gates having any number of control and target qubits.1 in analogy with the reversible classical computer discussed in sect. 7.4, using an equiva- lent sequence of quantum logic gates, any function f (x): {0, 1}k ? {0, 1}l is
uf
computed via the transformation |x, y) ?? |x, y ?f (x)), as shown in fig. 9.3. the unitary transformation uf leaves the “data” register of k qubits contain- ing the argument x ? {0, 1}k of the function unchanged, while the value of the function is written into the “target” register of l qubits y ? {0, 1}l via the addition modulo 2 operation, |y ? f (x)).



1of course, if a particular physical system is capable of explicitly realizing unitary transformations involving more than two qubits, implementing thereby multiqubit logic gates, it is an advantageous but not a fundamental factor, since single- and two-qubit gates su?ce to construct any multiqubit transformation.


k
x x
u
l
y y f(x)

fig. 9.3. unitary transformation uf for the evaluation of function f (x). symbol “/n” is a short-hand notation for a set of n qubits.


building blocks of a quantum computer

in preparation for the discussion of the physical implementations of quan- tum information processing in the next chapter, let us list here the necessary ingredients of an envisioned quantum computer. the quantum computer is composed of (i) register containing k qubits (ii) one- and two-qubit (and possibly k(> 2)-qubit) logic gates applied to the register according to the particular algorithm and (iii) measuring apparatus applied to the desired qubits at the end of (and, possibly, during) the program execution, which projects the qubit state onto the computational basis { |0), |1)}.
the operation of the quantum computer consists of the following principal steps:

1. initialization—prepare all k qubits of the register in a well-de?ned initial state, such as, e.g., |0 ... 000).
2. input—load the input data using the logic gates.
3. computation—perform the desired unitary transformation by applying the sequence of logic gates according to the program.
4. output—measure the ?nal state of the register in the computational basis.

in the following sections we consider several representative quantum algo- rithms for data processing and error correction.


9.2 quantum algorithms

before we embark upon a detailed discussion, let us outline two general princi- ples pertaining to most of the existing quantum algorithms. the ?rst principle instructs us as to how to prepare the input state of the register, in order to make the best use of quantum parallelism. it may be formulated as follows:

(i) prepare the input state of the register in a superposition state of all pos- sible “classical” inputs x
|?in) = . cx |x) , . |cx|2 =1 . (9.6)
x x


note that many problems are intractable on classical computers simply be- cause there are too many possible inputs that should be processed and ana- lyzed by a computer before the actual problem is solved. this usually requires either an enormous amount of cpu time, if a sequential processing of the input data is performed on a single processor, or enormous number of simultane- ously working processors, to vastly parallelize the algorithm execution. on the other hand, owing to the quantum superposition principle, a single quantum register is capable of simultaneously storing and processing all of the classical inputs at once.
the second principle has to do with the measurement which should yield an intelligible result of computation, expressed in terms of classical quantities. it states:

(ii) design an algorithm in which all of the computational paths interfere with each other to yield with high probability the output state y
|?out)c cy |y) , |cy |2 c 1 , . |cyr |2 1 . (9.7)
yr ƒ=y

we thus recognize that the required output state y, containing the sought after solution of the problem, is an eigenstate of the quantum register. it is thus a classical state, since no superposition is involved, and a single measurement reveals y with almost unit probability |cy |2 c 1. if the algorithm execution is not too costly in terms of the hardware involved, we may allow for several repetitions of the algorithm, followed by the measurements, and the condition on cy can be somewhat relaxed to |cy |2 > 1/2. then if we perform say nr repetitions of the cycle (i)-(ii), all resulting in the same state y, the probability of obtaining an erroneous output perror(nr ) = (1 ? |cy |2)nr rapidly goes to zero with increasing nr .
designing good quantum algorithms is a very di?cult task requiring pro- found insight and ingenuity, particularly because we think largely in classical terms, with the quantum world often being rather counterintuitive.


deutsch algorithm

we begin with this simple algorithm, involving only two qubits, representing therefore a “toy problem”, aimed at demonstrating the power of quantum par- allelism employed in other quantum algorithms capable of performing useful tasks.
suppose we are given some boolean function f (x) : {0, 1} ? {0, 1} of a single-bit argument x and the corresponding quantum “black-box” or “oracle”
uf
uf evaluating that function via |x, y) ?? |x, y ? f (x)) (see. prob. 9.2). our aim is to determine a property of function f , i.e., whether it is constant f (0) = f (1) of balanced f (0) ƒ= f (1). on a classical computer, we would need to evaluate f (x) twice, once for x = 0 and once for x = 1, and then


0 h h
uf
1 h

fig. 9.4. circuit implementing the deutsch algorithm.


compare the results. a quantum computer, however, allows us to characterize the function by calling uf only once. this is achieved by preparing the data qubit in an equally weighted superposition state of both classical inputs x =0 and x = 1 and evaluating f (x) for both x at the same time, followed by interfering the output of uf and a single measurement that unambiguously reveals the function. the quantum circuit for doing this is shown in fig. 9.4. let us follow the states of the register through this circuit. the initial state of the two qubits is
|?2 ) = |0) |1) . (9.8)
after applying the hadamard gates to the data and target qubits, we have
(1) 1
|?2 ) = 2 ( |0) + |1))( |0)? |1)) . (9.9)
next, the uf transformation leads to
? 1


(2)
| 2 )

? ± 2 ( |0) + |1))( |0)? |1)) if f (0) = f (1)
2 ( |0)? |1))( |0)? |1)) if f (0) ƒ= f (1).


uf
realizing that |x)( |0)? |1))/ 2 ??
|?2 ) in a more compact form

(?1)f (x) |x)( |0)? |1))/?2, we can cast


(2)

(?1)f (x) |x) |0)? |1)

|?2 ) = . ?
x=0,1 2

? . (9.10)
2

finally, after applying the hadamard gate to the data qubit, we have
? ± |0) 1 ( |0)? |1)) if f (0) = f (1)
(3) ? 2
| 2 )

or, alternatively,

? ± |1) 1 ( |0)? |1)) if f (0) ƒ= f (1),

(3)

1

|?2 ) = ± |f (0) ? f (1)) ?2 ( |0)? |1)). (9.11)
thus, measurement on the data qubit yields state |f (0)?f (1)), which is |0) if f (0) = f (1) [f (0) ? f (1) = 0], and is |1) if f (0) ƒ= f (1) [f (0) ? f (1) = 1]. this illustrates the power of superposition employed in quantum computation.


deutsch–jozsa algorithm

the deutsch-jozsa algorithm is a generalization of the above algorithm to the multiqubit case. namely, suppose that a boolean function f (x) : {0, 1}k ?
{0, 1} of a k-bit argument x ? x1x2 ... xk is computed by the quantum black-
uf
box uf via |x, y) ?? |x, y ?f (x)). as before, our aim is to determine whether the function is constant f (x) = const, i.e., its value is the same for all 0 ? x < 2k , or balanced, meaning that f (x) = 0 for exactly half of all possible x, and f (x) = 1 for the other half of the values of x. we are guaranteed that f is either constant or balanced. on a classical computer, we would need to evaluate f (x) at least twice for two di?erent arguments x and xr, provided that the values of f for x and xr are di?erent, in which case we know that the function is balanced. if however, the values of f are the same, we need to call uf with yet another argument xrr ƒ= x, xr, and compare the output with the previous values of f . again, if these values are di?erent, we learn that f is balanced, otherwise we have to test more x. only after 2k /2+1 queries of the function with di?erent arguments yielding the same result we can be certain that the function is constant. the quantum circuit of fig. 9.5, however, can give a de?nite answer to that problem after only a single evaluation of f for a superposition of all x.

0 k h k h k
uf
1 h

fig. 9.5. circuit implementing the deutsch–jozsa algorithm.


let us follow the states of the register through this circuit. the data regis- ter is composed of k qubits, initially all in state |0), and the target is a single qubit, initially in state |1). thus, the initial state of the system is


|?k+1) = |0)?

|1) . (9.12)


applying the hadamard gates to the data and target qubits, we prepare the data register in the equally weighted superposition state of all possible x,



(1)

x) |0)? |1)

|?k+1) = . |
x 2k

? . (9.13)
2

since the target qubit is prepared in state ( |0)? |1))/?2, the uf transforma- tion leads to

(2)

(?1)f (x) |x) |0)? |1)

|?k+1) = . ?
x 2k

?2 . (9.14)


finally, the hadamard transformation is applied to all k qubits of the data register, which yields the state



(3)

(?1)x•z+f (x) |z) |0)? |1)

|?k+1) = . . 2k

? . (9.15)

z x 2
here we have used the multiqubit generalization of (8.7),
(?1)x1 z1 +...+xk zk |z1 ... zk )

h?k |x1 ... xk ) = .
z1 ,...,zk

?2k ,

which, in a compact form, is

x•z

h?k |x) = . (?1) |z) ,
z 2k
where x • z = x1z1 + ... + xk zk is the bitwise dot product of x and z.
the remarkable property of the ?nal state (9.15) is that the amplitude c0
of the state |z = 0) = |0)?k of the data register is given by


c0 = (?(3) |0)?

k |0)? |1)
?2

. (?1)f (x)
= 2k .
x


therefore, if the function f is constant, all 2k terms enter this sum with the same sign (“+” for f (x)=0 and “?” for f (x) = 1) and we have c0 = ±1. on the other hand, if the function f is balanced, exactly half of the terms enter this sum with the “+” sigh, and the other half enter with the “?” sign, which results in c0 = 0. thus, if the function f is constant, the measurement of the data register yields, with the probability |c0|2 = 1, the output state |0)?k , i.e., all qubits are in state |0). if, on the other hand, the measurement yields
|c0|2 = 0, i.e, at least one of qubits of the data register is found in state |1), the function f is balanced.
we have thus seen that, despite of its limited use for practical applica- tions, the deutsch–jozsa algorithm unambiguously demonstrates the poten- tial power of a quantum computer. in what follows, we describe two very use- ful quantum algorithms that can signi?cantly speed up and e?ciently solve two classes of important problems involving search/minimization and fourier transform.


grover algorithm

the quantum search algorithm was invented by grover, and it o?ers a quadratic speed-up over classical algorithms for searching an unsorted database. suppose we have a list of n = 2k elements dx stored in a computer memory. the index x, taking n di?erent integer values x = 0, 1,... ,n ? 1, identi?es