Quantum Bio-informatics IV: From Quantum Information to Bio-informatics (Qp-Pq: Quantum Probability and White Noise Analysis)

--+

0 corresponding to l

(27)

= In it is

One can interpret this Vrp (m), which is usually finite on m > 0, as a free energy coinciding in first order with the total energy

=

lr.

The Legendre-Fenchel

transform

VZ,rp (w)

:=

sup {Vz,rp (m) - w (m) : m = m* EM},

(29)

m

of the classically evaluated Vz,rp and analytically extended to noncommuting cp and m, say, by (27) or (28) for I = lr and I = In, defines implicitly the informational divergence of a new, thermodynamical type C.

76

One can also take a sharper divergence V(C) (w;
= i~,f {w (m) + V(C) (w;
(1)

= 1}

and can be equivalently defined as V(C) = (

= inf {S (m;
(30)

where S(m;
evaluated for all iIi commuting with rp by the constraint transform of the entropy siC) written with the help of Lagrangian multiplier, as SI(C)

(m;
+, } .

(31)

'U7

and analytically extended to any m E M for which it makes sense, otherwise = 00. Thus, the reduced lr-divergence vi~) of type C is defined as the transform (25) of the constraint REmyi energy

VI(C) (m;
vi~~ (m;
(e- m)

(32)

coincides in the first order with the mean energy

3.6. Other new entropy types D&E Unlike in the case of types A and B the optimal state w~C) resolving the variational problem (26) for divergence of the type C can be found explicitly

77

even for noncommuting Indeed, it is given as &(e) - 1 free -

1

o

rp and iii at least in the logarithmic case l I n . (e) _

e (8-1) 'Pe -8md s, 'W nor A

A

-

e

r-111

e

(8-1)

'Pe A

-8md

s

o by solving the dual problem (25) respectively for free (28) or constraint (32) by normalization logarithmic energy using the ordering index method for noncommuting variation 8m of m. This implicitly defines the entropic function hi:) (& : rp) of C-type relative density for the state 'W with respect to 'P presenting the solution

Sl~e) ('W; 'P) =

e (rp ~ hi:) (& : rp) 'P ~)

=

'P

(hi:) (& : rp)) .

(33)

of the variational problem (30) coinciding on ('3 with unreduced logarithmic relative entropy S

rp ~ hr;:) (& : rp) rp ~ = iii - ,1 in terms of the variational derivative hr;:) (& : rp) = 8hi:) (& : rp) /8& resolving (31) for (33). Similarly we can define another two interesting logarithmic relative entropies of type D and E in the form

Sl~) ('W; 'P) = e (rp ~ hf;! (& : rp) 'P ~) =

'P ( hf;! (& : rp))

.

They are determined respectively by the logarithmic entropic functions hCJ;) (& : rp) and h~) (& : rp) as the solutions of the stationarity differential equation equations

rp~h~(&:rp)rp~ =iii-,1 defined by the variational derivatives h~ (& : rp) = 8hf;! (& : rp) /8& in terms of the RN derivative &SD) = &

= exp [In & -lnrp] (E-type):

rp~hCJ;) (&: rp) rp~

=

h' (&SD)), &SD)

=

rp-~&rp-~,

rp~ h~) (& : rp) rp~ = h' (&SE)) = h' (exp [In & -lnrp]). Here h' (p) = -In p -1 is the derivative of the logarithmic entropic function h (p) = -plnp. Unfortunately, the free (28) or constraint (32) logarithmic energy of types D and E in general is difficult to evaluated explicitly if rp does not

78

commute with ill, however the optimal states resolving the corresponding minimization problems (25) can be easily found from the stationarity differential equation with I = 1 for the free case and I = r for the normalized case:

,(E) _

W free -

eIn ",,-iii ,

,(El _

W nor -

er-lln",,-iii e .

4. Quantum Mutual Information and Encodings 4.1. Entangled mutual information Here we define symmetric mutual information m a quantum compound state W achieved by an entanglement 7f : lBl ---7 AT' or, equivalently, by 7fT : A ---7 lBlT' as the general information divergence of the entangled state W with respect to the product state cp = 12 Q9 C; on M = A Q9 lBl:

(34)

I.t,k

vU

In particular, (7f) = (Wi 12 Q9 c;) is the usual logarithmic quantum mutual information of a particular type.

Theorem 4.1. Let A : lBl ---7 A~ be an entanglement of the state c;(b) = (1go,A(b)) on lBl to (AO, 12°) with AO <;;; 8(gO) as a CP map such as?/ = A(1~), and 7f = KT 0 A be the entanglement to the state 12 = (!oK on A <;;; 8 (g) defined as the composition of A through a channel KT : A~ ---7 AT as the predual to a normal UCP map K : A ---7 A0 • Then the following monotonicity holds

I A('l() ,IE 7f

~

(.) IE () I Ao , A .

(35)

Proof: This simply follows from the monotonicity of V. It is interesting to compute and compare the different types of entangled mutual informations Vz (Wi 12 Q9 c;) for the particular types of the contrast function l. In particular, to compute the RE'myi and the usual logarithmic informations (Wi 12 Q9 c;) for the special, say quantum Gaussian entangled states wand to compare them with the wellknown Gaussian entangled information of the type A.

vU

4.2. The proper quantum entropies Applying the monotonicity property for the standard entanglement A = 7fJ == a of C; to 12° = ~ decomposing every 7fT by the Theorem 1 as 7fT = aoK

79

we obtain immediately the explicit solution A = optimization problem sup IA,lIl\(1T) = IlIl\,j(a-)

iffi, 1TT

=

a- := 1T~ to the

== 7-{lIl\(C;).

(36)

7r:/-L07r=c;

Definition 4.1. The maximal quantum information

I lIl\,lIl\~(1T <; ) = 7-{lIl\(c;)

= I~

7-{e·) = Ie·) lIl\,lIl\ (1T~) <;, In In

(37)

over all entanglements 1TT E Kq(c;) of any (A,a) to (lffi,c;), achieved on 2ae/ 2 == a- (a), A 0 = iffi by the standard quantum entanglement 1T T (a) = is named as entangled, or proper quantum entropy of the state c;. The positive difference

e/

(38) is called the conditional proper quantum entropy 7-{lIl\IA = 7-{lIl\ - IA,lIl\ of the entanglement 1T : lffi ---> AT . The semiclassical entropy SlIl\ (c;) is defined the solution of the extremum problem (36) under the additional constraint 1T T E Kc (c;) that A is an Abelian (the diagonal) algebra A = C (I) indexed by a discrete set:I : sup

{IA,lIl\(1T): A

=

C (I)}

== SlIl\(c;).

7r:V07r=C;

It is achieved on a classical state a (a) = L aipi such that /W1T = L PiC;i = C; is given by pure optimal states C;i on lffi. If 1T T E Kc (c;), then, obviously,

(39) otherwise this semiclassical conditional entropy can be negative if 1TT does not satisfy the semiclassical constraint Kc (c;). Naturally, 7-{lIl\ (c;) 2- SlIl\ (c;) and 7-{lIl\IA (1T) 2- SlIl\lA (1T). Note that SI~A) (c;) is the usual von Neumann entropy

which is achieved as the solution of the semiclassical extremum problem (39) at any decomposition C; = LPiC;i into the pure states C;i as

st)(c;) = S(c;)

+

sup voc;1.=l

I:>iV [~i ln~il = S(c;)

Thus, 7-{}:) 2- S( c;), in particular, 7-{}:) algebra lffi

= 2S in the case of full matrix

= B (f)). It is interesting also to compare the entropies

SL) of the other types.

7-{J') r

and

80

4.3. Quantum noisy and noiseless channels Definition 4.2. A quantum channel is described on the output algebra of Bob, lE, by a linear normal unital completely positive map (UCP) A : lE ----+ lEO into the same or another input algebra lEo <:;; B(~O). The algebra lEo in the input state <;0 should not be identified with the "Alice" algebra A in a state f2 but rather with the transposed algebra lEO = A which can be the same as A but with the opposite products a*a to aa* E A and the transposed state <;0 = 72. Every channel A admits the Kraus decomposition

A(b) = LVkbV~ E lEo Vb E lE, k

where Vk are contractions ~ ----+ ~o, Lk VkV~ = 1~o and is dual A = A:~ to map AT IlE~ == AT on the predual space lE~ into lET decomposed as

ATW) = LVk~oV; V~o E lE~, k

where Vk = J~ V~J~o = Vk. For example, quantum noiseless channel in the case lE = B(~), lEo = B(~O) is described by any single coisometry V : ~ ----+ ~o, VV* = 1~o, as A(b) = VbV*. A noisy quantum channel sends input pure states f20 = <;0 on the algebra lEo = B(~O) into mixed states <; = <;0 A described by the output densities ~ = AT (~O) given by the predual map AT = AT IlE~ to the mixed normal UCP map A : lE ----+ lEo. It can always be written as A(b) = Trf+ [VbV*], where V is a stochastic coisometry, i.e. a linear operator ~ ----+ ~o Q9 f+ with the partial trace Trf+ [VV*] = 1~o on a separable Hilbert space f+ of quantum noise in the channel. Each input state <;0 is transmitted into an output state <; = <;0 A given for any ~o E lE~ by the density operator

4.4. Entanglement as quantum encoding Definition 4.3. A quantum encoding ofthe input state <;0 for the channel A with an alphabet, or Alice probe algebra A is any generalized entangling CP map K : A ----+ lEO normalized as K( 1p) = ~o. The proper quantum encodings correspond to the proper entanglements, while the semi-quantum encodings are described by the commutative (classical) alphabet algebras A = c (A).

81

The set of all quantum encodings is convex, denoted by Kq, or Kq (<;0) if the normalization <;0 is fixed. It includes the standard entanglements (J0 (a) = RaR, corresponding to AO = llllo, as pure quantum encodings, while the convex subset of all semi-quantum encodings, denoted respectively by K c, or Kc( <;0), excludes all proper entanglements. Every encoding K, E Kq (<;0) is a composition K, = (J0 0 K of the pure quantum encoding (J0 an~ normal UCP map K : A ----> AO into the sufficient alphabet algebra AO = llllo antiisomorphic to llllo. The transposed CP map K, T = KT 0 pO represents quantum encoding as a transmission process by KT : A~ ----> AT inducing the alphabet state e = K,T (1~) from the transposed input state eO = ¢o E A~ maximally entangled by (JOT = pO to the input state <;0 on the antipode llllO of the algebra A° . Each encoding K, E Kq (<;0) induces a compound state wO(a@bO):= Trf_[vo*(a@bO)vO]

== (a@bO,wO).

given on the input-probe algebra A@llllo by the density operator WO = vO*vo of the encoding K,(a) = ,1[(a@ l~o)wO]. 5. Quantum Channel Capacities and their Additivity

5.1. The quantum and semiclassical capacities The channel A transmits the probe-input encoding K, into the probe-output encoding AT K, entangling the output state via this channel to = 1T( 1~) by K, TA = 1T = KT A. The mutual entangled information, transmitted via the channel for quantum encoding K" is therefore

e

(41)

where A = pO A is the standard maximal input entanglement #b # transmitted via the channel A. Definition 5.1. Given a channel A : llll ----> llllO and a subset K channel information capacity is defined by

<;;;;

pO

(b) =

K q , the

(42) The channelled semiclassical and the proper quantum information capacities are defined respectively as

(43)

82

(44) Lemma 5.1. Let A(b) = VbV* be a unital completely positive map A: lBl lBlo (Noiseless channel.) Then

--->

Jq(C;0, A) = Hrrdc;O), Jc(C;°, A) = SlIdc;O) andC(A) = lndim~o, Q(A) = lndimlBlO for the logarithmic capacities of any type I12,lffi = Il~) ,

5.2. The true quantum capacity Theorem 5.1. The channelled entangled information achieves the value (45)

where A = 'ir 0 A is given by the optimal input entanglement 'ir 0 pO of the channel input state C;O to the transposed state (/ = ~ induced on the minimal sufficient alphabet A~ = lBl~ , Proof. Use the monotonicity of IA,lffi(KTA) with respect to KT and the commutativity of the following diagrams 0

Note that we have explicitly three types of such channeled information ~:j (C;O , A) for each contrast function l and obviously, ~:~) (C;O , A) :S

~:~)(c;O,A), QjA) (A):S QjB) (A), where

Qj') (A)

=

sup

{Ii',~o (AT

0

'ir,o) :

C;O E (3 (lBlO)} ,

It is interesting to compute and compare the Renyi and the usual logarithmic informations ~:j(c;O,A), ~:;(c;O,A) and the capacities Qj')(A),

cF) (A)

for the particular types for some special, say the quantum Gaussian channel A and input states c;o,

5.3. Block encoding for quantum product channels Here we consider the products Q~n) = ®i=l c;i and transposed states c;~n) = (j~n) respectively on the tensor products A~n) = ®i=l lBli and lBl~n) = A~n) and for the notational simplicity we implement the convention A~ = lBli, n) = ,® is the product f)i = ,""2 0 and A ® = A (n) f)® = t:O f)(n) such that ,-C t::o 0 0 , t::'o -:'0 ":to state on the transposed input algebra lBl~n) = lBl~ defining the standard

83

entanglement (J@ = "<:Yt=l /O,n (Ji0 of the input state ~o n(n) o the probe product state ~~ = (j~ on lE~ = A~. Let A@ = 0;'=1 Ai denote the product channel.

=

n@

t:o

on A 0(n)

= A@ to 0

Definition 5.2. A quantum block-encoding is a normal CP map f£(n) : A(n) ---+ A~T on an alphabet algebra A(n) such that f£(n) (l(n)) = 0~1~~ for the given states ~i E lEiT. Obviously, the compound density w~n) E A~n) 0 A~T for the product block encoding f£@ = 0;'=f£i is the product w~ = 0;'=1 Woi of the densities for the input compound states Woi = wi, each entangled by tri = f£I on Ai 0lEi. However, in general it may not be true, despite of f£(n) (1 (n)) = ?!~, since the input entangled state win) on A(n) o Ain ) may not be the product 0;'=1 wi even if A (n) is the product alphabet algebra A@ = 0~1 Ai as is A~n) = A~ but f£(n) (a@) i- 0;'=1 f£i (ai) for some a@ = 0;'=1 ai E A@. This is due to one-to-one correspondence w~n) f--t f£(n) :

5.4. The additivity problem for quantum capacities In the normalized case 'P (1) = 1 = w (1) the informational divergence = -Sl~) as negaentropy of any type has the multiplicative additivity property

vf;!

with respect to every finite product reference 'P@ = 0;'=1 'Pi. It was shown for (A) and (B) types entropy in (24), and for the type (C) it comes from em = 0emi and 'P = 0'Pi in the transform (29) with m = 2: 1@(i-1) 0 mi 0 l@(n-i).

The logarithmic informations I'JJ.,p, (7r(n)) are additive iff 7r(n) : 93 ---+ mT is product entanglement 7r@ : lE@ ---+ A~, and the logarithmic capacities :ftc

((}~n), A@ ), including

Hk) ((}~n)) =

sup ",(n)

Il~ ,'JJ.

(f£(n))

= :f~.) ((}~n), Id@)

Etc (e~n»)

are additive iff they are achieved on product encodings f£(n) = f£@. The latter holds if the constraint K on f£ is appropriate, or, as we will prove below, if there is no additional constraint on the set Kq ( (}~n)). On the other

84

hand, the semiclassical constraint K = Kc ((}~n)) in the case of noncommutative Ao seams inappropriate, although it is known that this constraint is appropriate for the logarithmic capacities of type A in the category of the commutative Ao, in which it trivial constraint. In particular, the semiclassical Holevo constraint K = Kc is not appropriate for the true quantum channels since as it is now known, the logarithmic capacities J}A) ({}~, A0 ) and C(A) (A0 ), known as the Holevo bounds 15, are not additive for the general quantum channels A.

5.5.

Optimal true quantum block encoding

The following Lemma is valid for any type of quantum entangled information, and in particular, for any Renyi information.

Lemma 5.2. Let A~ : A~T

---+

E~, (}~n) =

0i=1 {}~ == {}~ .

Then

Proof. Take AiT : EiT ---+ EiT and ~~ E EiT with Ei = A~ and c:;i = {}~ evaluating the densities ~i of the output states C:;i = {}~Ai as AiT ((}~). Due to Theorem 1 we can decompose the quantum block encodings ",en) : A en) ---+ A0 as ",(n) = p00 K(n)' where K(n) .• A(n) ---+ A,.0 is a normal UCP map and OT 0

p~ (b~)

=

0i=1/?lb~/?l is

the standard entanglement on

A,.~

:3

b~

to

(}~n) = 0~ 1{}~. Note that although the range of K(n) is product algebra A,.0 A0 with r0 = t:'o' n o , the domain A(n) is any algebra . For H(n) = K(n)o-0 T 0 "'!I

we maximize the information quantum encodings Kq Jq

({}~n)):

((}~n), A0 ) = sup

Ja® (H(n))

IA( n)

{I21

over the maximal convex set of

' ,'l:l

(K~n)o-~ A0 ) : K~n) 0 o-~ E Kq}

.

Since ~~ = l!~n) is fixed , the supremum should be taken only over all channels K~n) with fixed domain A,.~T but arbitrary range A~n). Thus, the required result (46) follows by monotonicity argument (Theorem 2) for any type of quantum channelled l-information J q ({}~, AO). D

5.6.

The additivity of true quantum capacities

Theorem 5.2. The logarithmic q-informations Jq(.) are additive, Jq(·)({}~, A0 )

= LJq(-)({}~,Ai)

85

and so is the logarithmic proper quantum capacity Q(')

(A 0 ) = sup J q(') ((/t!, A0) = eo

L

Q( ' )

(Ai) .

Proof. Follows immediately from Lemma 3 by additivity argument of the logarithmic function l = In . 0

Note that this proof does not work for any type of the logarithmic semiquantum information J e(') (Q~, A0) and the capacity C(·) (A 0) which have obviously the semiadditivity property

The lower bound achieved on the product encodings ",(n) = "'0 might not maximize I~:'13 (K~n) a~ A under the constraint that A (n) must be com-

0)

mutative for the semiclassical encodings satisfying

",(n)

(1 (n»)

= Q~.

But the above semiclassical capacities Je(A) and C(A) are appropriate for semiclassical channels A corresponding to the commutative input algebra Ao = lEo. The logarithmic capacities for such channels of the type A where first introduced by Levitin under the name of the defect of entropy Je(A)

(Qo, A) = SE (QoA) -

SEIA

(",~A),

C(A)

(A) = sup Je(A) (Qo, A), eo

where S EIA (",~A) and SE (QoA) are conditional and unconditional vonNeumann semiclassical entropies corresponding to the standard classical input encoding

In general, these capacities are smaller than the logarithmic semiclassical capacities

J}B) (Qo,A) =

e [goAT In (A~l~)J

C(B)

(A) =

SUPJ}B)

(Qo,A)

eo

of the type B. Here AT is the contravariant v-density v (AT b) = A (b) of the semiclassical channel AT : go f-+ J-l (goAT) mapping the classical J-l-desities go into the quantum v-densities ~ = AT (g), and = J-l Q9 v is the semiclassical trace on lB~ ®lET.

e

86

6. Conclusion

Quantum channel capacities can have several different formulations when considering to send classical information or quantum information, one-way or two-way communication, prior or via entanglement, etc., however they all can be considered as the capacities achieved under the different constraints on the encoding class of true quantum entangling codes K q . Anyway, the operational quantum channel capacity and its asymptotical equivalence with the additive quantum capacities under the appropriate constraints is still a big open and challenging research problem in quantum information theory. Another natural problem in this direction is to compare proper quantum entropies and additive capacities of different type in quantity for some interesting quantum channels, such as Gaussian channels, and other smaller capacities of different types under the well known constraints, such as semiclassical constraint, entanglement-assistant capacity, etc., and find for which class of channels they assymptotically coincide. Generally how to access those capacities, using physically implement able operations for encodings and decodings, such as quantum channel capacity for one-way communication via entanglement, is of course an important open problem in quantum information and quantum computation. All those problems wait forthcoming papers in the future. 7. Appendix: The standard pairing

Let lL and M be complex linear spaces put in duality via bilinear form (-,.; : M x lL ---> C. Let M be closed with respect to an associative but generally non-commutative binary operation M2 :3 (x, z) f--+ XZ E M (e.g. pointwise function or matrix mUltiplication) and involution * as a selfinverse antilinear map reversing the multiplication order, (x*z)* = z*x, so that M is a *-algebra with the positive cone of x*x generating M. Not that, if M has the imaginary unit i = - i *, then it the case as any x E M is the linear combination of four positive elements (x + i n)*(x + in) for n = 0,1,2,3. However, we do not require that M is unital but will assume that lL has the identity 1* = 1 defining a reference weight rJ (x) = (x,l; as a strictly positive rJ (x*x) > 0 for all nonzero x E M linear functional on M. Let the pairing be regular such that for any left multiplication x f--+ zx on M there exist an transposed operator y f--+ z'y on lL defined by (zx, y; >= (x, z'y;, and that lL is closed under the transposed involution denoted also by *: (x, y*; = (x*, y; * (Every separating pairing on finite dimensional M and lL is obviously regular.) Then the following theorem hold:

87

Theorem 7.1. The dual space lL of M with respect to the regular pairing is left module with respect to the transposed left action of M on lL such that (xz)' = z' x', and it is also the right module with respect to the right transposed action of M on lL given by y 1-+ yz*'*, where (x, yz *'*) := (* x ,z *, y *) * = (* z x * ,y *) * =- (xz, y ) .

Moreover, if Y = y* is positive element of lL in the sense that (x*x, y) 2: 0 for all x E M, then z*'yz'* is also positive for every z E M. The positive maps y 1-+ z*'yz'* in fact are completely positive (CP) in the sense that for every semipositive matrix Y = [Yi,k] in the sense

(x*x, Y)

:=

L

(X;Xk' yi ,k) 2: 0 VXj E M,j = 1,2, ... ,

i,k:;::l the matrix z*'Yz'* = [z*' I: yi,k z '*] remains semipositive. The pairing is called central, or tracial, if the left and right transpositions act identically on 1: z*'1 == z == 1z'* for all z E M such that f)

(zz*) = (z, 1z'*) = (z, z*'1) = f) (z*z) z E M .

The antilinear invertibe map z 1-+ Z, intertwining the invo~utions in M and lL, represents the *-algebra M in lL as the opposite algebra M with respect to the induced product z*z = z*z such that z = z*_becomes the transposition z*z = z*z of M onto the weakly dense domain M in lL. Moreover, the dual space lL becomes two-sided *-module over Mby identifying with left and right transpositions as z'* = z = z*' which adds the identity 1 E lL to ~. Note that if lL is taken as minimal predual MT completing the *-algebra M with respect to the dual to C*-algebra norm on M, then lL may not have the identity as the density of a not finite trace f), but then the identity can be added to M to represent the norm-trace (y) = (1, y) on lL = MT uniquely extending the transposed trace (x) = (1, x) = f) (x) from M. The basic example of such central pairing, called tilde-tracial pairing, is given by the standard trace

z

e

e

(x, y) := Tr (xy)

==

T

(yx) ,

or by any other trace e on lL as the linear positive functional e(y) = (1, y) such that e (xy) = e(yx). Note that the standard symmetric tracial pairing (x . z) = T (x . z) identifies the dual space of M with the complex conjugation M* = j[ of the predual space lL = M T. In this preadjoint space M* the left multiplication

88

z

z' is identified not with the left multiplication by but with the right multiplication by z. The preadjoint space is obviously two-sided M-module containing the algebra M itself as~a dense subspace, which, of course, coincides with M if M is symmetric, M = M.

Acknowledgment This work was supported by QBIC grant of Japanese Ministry of High Education and by British Council PMI-2 grant for UK-Korea collaboration. The author would like to thank for warm hospitality of Professor Ohya at the Science University of Tokyo and of Professors So Young Kim from Korean Institute for Advanced Studies and Un Cig Ji from Chungbuk National University for their encouragement to prepare these lecture notes for publication.

References 1. V. P. Belavkin. On entangled information and quantum capacity. Open Sys. and Information Dyn., 8:1-18, 2001. 2. V. P. Belavkin. On entangled quantum capacity. In Tombesi and Hirota, editors, Quantum Communication, Computing and Measurement, pages 325333. Kluwer /Plenum, 2001. 3. V. P. Belavkin. Quantum sex and mutual information. In New Development of Infinite-Dimensional Analysis and Quantum Probability, pages 61-82, Kyoto, 2001. Research Institute of Mathematical Sciences. 4. V. P. Belavkin. Contravariant densities, complete distances and relative fidelities for quantum channels. Report in Mathematical Physics, 55:61 - 77, 2005. 5. V. P. Belavkin and x .. Dai. An operational algebraic approach to quantum channel capacity. International Journal of Quantum Information, 6:357-374, 2008. 6. V. P. Belavkin and S. Hammersley. Information divergence for quantum channels. In Quantum Probability and Infinite Dimensional Analysis, volume 29, pages 149 - 167. World Scientific, 2006. 7. V. P. Belavkin and M. Ohya. Quantum entropy and information in discrete entangled states. Infimite- Dimensional Analysis, Quantum Probability and Related Topics, 4(2):137-160, 2001. 8. V. P. Belavkin and M. Ohya. Entanglement, quantum entropy and mutual information. Proc. R. Soc. Lond. A, 458:209-231, 2002. 9. V. P. Belavkin and R. Stratonovich. On optimisation of processing of quantum signals by information criterion. Radio Eng Electron Physics, 18(9):1839-1844,1973. 10. V. P. Belavkin and A. Vantsian. On sufficient conditions of optimality of

89

11.

12. 13. 14. 15.

16. 17. 18. 19. 20. 21. 22. 23. 24. 25.

quantum signal processing. Radio Eng Electron Physics, 19(7):1391- 1395 , 1974. J. A . Smolin C. H. Bennett, P. W. Shor and A. V. Thapliyal. Entanglement assisted classical capacity of noisy quantum channels. Phys. Rev. Lett., 83:3081- 3084, 1999. N. Cerf and G. Adami. Von neumann capacity of noisy quantum channels. Phys. Rev, A 56:3470- 3483, 1997. M. B. Hastings. A counterexample to additivity of minimum output entropy. Nature Physics, 5:255, 2009. P . Hayden and A. Winter. Counterexample to the maximal p-norm multiplicativity conjecture for all p > . arXiv.org: 0807.4753 , 2008. A. S. Holevo. Bounds for the quantity of information transmitted by a quantum communication channel. Problems of Information Transmission, 9:177183, 1973. C . King and M. B. Ruskai. Minimal entropy of states emerging from noisy quantum channels. IEEE Trans . Inf. Thy., 47:192-209, 2001. D. S. Lebedev and L. B. Levitin. Information transmission by electromagnetic field. Information and Control, pages 1- 22, 1966. A. Lesniewski and M . Ruskai. Monotone riemanian metrics and relative entropy of non-commutative probability spaces. math-ph/9808016, 1998. D . Petz. Quasi-entropies for finite quantum systems . Reports on Mathematical Physics, 23:57- 65, 1984. B. Schumacher. Sending entanglement through noisy quantum channels. Phys. Rev. A , 54:2614- 2628, 1996. C . E. Shannon. A mathematical theory of communication. Bell Syst. Tech . Jour., 27:379- 423, 1948. P. W. Shor. Equivalence of additivity question in quantum information theory. Comm. Math. Phys., 246:453-472, 2004. R. L. Stratonivich. On mutual information and the capacity of quantum channels. Izvestia Vuzov: Radiophysics, 4:15-24, 1965. R. L. Stratonovich. Mutial infromation of quantum gaussian variables. Izvestia Vuzov: Radiophysics, 8:116; 129, 1965. R . L. Stratonovich. On transmition of information via quantum channels. Problems of Information Transmitian, 45:150-160, 1966.

This page intentionally left blank

Quantum Bio-Informatics IV eds. L. Accardi, W. Freudenberg and M . Ohya © 2011 World Scientific Publishing Co. (pp. 91- 99)

NON-MARKOVIAN DYNAMICS OF QUANTUM SYSTEMS DARIUSZ CHRU8CIl\[SKI and ANDRZEJ KOSSAKOWSKI

Institute of Physics, Nicolaus Copernicus University, Grudzig,dzka 5/7, 87-100 Toru'Ti, Poland

We analyze a local approach to the non-Markovian evolution of open quantum systems. It turns out that any dynamical map representing evolution of such a system may be described either by non-loca l master equation with memory kernel or equivalently by equation which is local in time. The price one pays for the local approach is that the corresponding generator might be highly singular and it keeps the memory about the starting point 'to' . Remarkably, singularities of generator may lead to interesting physical phenomena like revival of coherence or sudden death and revival of entanglement.

Keywords: Open systems; quantum dynamics; non-Markovian evolution.

1. Introduction

The non-Markovian dynamics of open quantum systems attracts nowadays increasing attention. 1 It is very much connected to the growing interest in controlling quantum systems and applications in modern quantum technologies such as quantum communication, cryptography and computation. 2 It turns out that the popular Markovian approximation which does not take into account memory effects is not sufficient for modern applications and to days technology calls for truly non-Markovian approach. Non-Markovian dynamics was recently studied in Refs. 3- 18. The usual approach to the dynamics of an open quantum system consists in applying the Markovian approximation, that leads to the following local master equation d

dtP(t) = .eMP(t) ,

p(to) = Po,

(1)

where p(t) is the density matrix ofthe system investigated and.e M the timeindependent generator of the dynamical semigroup possessing the following 91

92

well known representation

19 ,20,21

LMP= -i[H,p]

+ L (VaPVd -

~{VdVa,p})

(2)

'" The above structure of LM guaranties that dynamical map A(t, to), defined by p(t) = A(t, to)Po, is completely positive and trace preserving for t 2: to· Note that A(t, to) itself satisfies Markovian master equation d

dt A(t, to) = LM A(t, to),

A(to,to) = ] ,

(3)

and the solution for A(t, to) is given by

A(t, to) =

e(t - tO)LM ,

(4)

which implies that A(t, to) depends only upon the difference 't - to' and hence A(t) := A(t,O) defines a I-parameter semi group (t 2: 0) satisfying homogeneous composition law

(5) for t1, t2 2: O. In general the external conditions which influence the dynamics of an open system may very in time. The natural generalization of the Markovian master equation (1) involves time-dependent generator LM(t) which has exactly the same representation as in (2) with time-dependent Hamiltonian H(t) and time-dependent Lindblad operators V",(t). Therefore one gets the following master equation for the dynamical map A(t, to) d

dt A(t, to) = LM(t) A(t, to),

A(to, to) = ] ,

(6)

which leads to the following solution

A(t, to) = T exp

(1:

LM(T)dT) ,

(7)

where T stands for the chronological operator. Clearly, A(t, to) no longer depends upon 't - to' but it still satisfies inhomogeneous composition law

A(t,s)·A(s,to) = A(t, to) ,

(8)

for t 2: s 2: to. We stress that (6) although time-dependent is perfectly Markovian. Note, that the solution (7) has only a formal meaning since the evaluation of T-product is in general not feasible. In this paper we analyze a non-Markovian dynamics A(t, to) which does not satisfy the composition law - this is the essence of non-Markovianity.

93

In the next section we present a general strategy to the description of nonMarkovian evolution based on the local in time generator, and in section 3 we present simple examples to illustrate a general approach. Final remarks are collected in section 4. 2. Local vs. non-local approach The standard approach to the dynamics of open system uses the NakajimaZwanzig projection operator technique 22 (see also Refs. 1, 21) which shows that under fairly general conditions, the master equation for the reduced density matrix pet) takes the form of the following non-local equation d pet) = -d t

it

K(t - u)p(u) du ,

to

p(to) = Po ,

(9)

in which quantum memory effects are taken into account through the introduction of the memory kernel K(t): this simply means that the rate of change of the state pet) at time t depends on its history (starting at t = to). Equivalently, one has the following nonlocal equation for the dynamical map d A(t, to) -d

=

t

it

Ket - u)A(u, to) du ,

A(to, to) =

to

n.

(10)

Let us observe that homogeneity of K (it depends upon the difference 't-u') implies that the corresponding solution A(t, to) is homogeneous as well. This property enables one to rewrite (10) as follows

t

d

dt A(t) = Jo Ket - u)A(u) du ,

A(O) =

n,

(11)

where A(t) := A(t + to, to). This form is usually studied in the literature 1. Note, however, that there is no need to provide the initial condition at to = o. Equation (10) allows to take completely arbitrary to. Unfortunately, we do not know condition for the memory kernel K(t) which guarantee that the corresponding dynamical map A(t, to) is a legitimate quantum evolution, i.e. it is completely positive and trace preserving. Therefore, instead of non-local approach we propose to analyze much simpler approach which is based on the local in time Master Equation (this approach is usually called time-convolutionless (TCL)1,23). Note, that each solution A(t) of (11) satisfies the following local in time equation 18

d

dt A(t, to)

=

L(t - to)A(t, to), A(to, to)

=

n,

(12)

94

where the time-dependent generator £(t) is defined by the following logarithmic derivative of the dynamical map

(13) and A(t) := A(t + to, to). Let us observe that Eq. (12) is local in time but its generator does remember about the starting point 'to'. This is the most important difference with the time-dependent Markovian equation (6). The appearance of 'to' in the generator £(t-t o) implies that £ is effectively nonlocal in time, that is, it contains a memory. Therefore, the local equation (12) is non-Markovian contrary to the local equation (6) which does does not keep any memory about to. Note, that solution to (12) is given by

A(t, to) = T exp

(fat-to £(T) dT)

.

(14)

It shows that A(t, to) is indeed homogeneous in time (depends on 't - to'). However, contrary to (7), it does not satisfy the composition law. Again, this is a clear sign for the memory effect. Now comes the natural question: how to construct non-Markovian generator £(t) which does guarantee legitimate quantum dynamics. The general answer is not known but one may easily propose special constructions. Let £M be a Markovian generator defined by (2) and define £(t) = a(t)£M' It is clear that if J~ a(u)du :2: 0 for t :2: 0, then

A(t) = exp(J~ a(u)du£M) defines completely positive non-Markovian dynamics. This construction may be generalized as follows: consider N mutually commuting Markovian generators £~), ... ,£r/) and N real functions ak(t) satisfying J~ ak(u)du :2: O. Then r( t ) J..-

=

r(1) a1 ( t ) J..-M

rCN) + ... + aN ( t ) J..-M

,

(15)

serves as a generator of non-Markovian evolution. Let £(t) (t :2: 0) be a commuting family of superoperators, i.e. [£(t),£(s)] = O. If the integral J~ £(u)du defines for each t :2: 0 a legitimate Lindblad generator, then £(t) generates legitimate non-Markovian evolution. If the family £(t) (t :2: 0) is non-commuting then the problem of necessary and sufficient condition for £ (t) is still open. 3. Examples

To illustrate our approach let us consider the following simple examples. Throughout this section we put A(t) := A(t, 0) and define the initial value problem at to.

95

Example 3.1. Consider the pure decoherence model defined by the following Hamiltonian

(16) where HR is the reservoir Hamiltonian, Hs system Hamiltonian and

= Ln EnPn (Pn = In nl) the (17)

the interaction part, Bn = B~ being reservoirs operators. Hence, the total Hamiltonian has the following structure

(18) n

where

(19) are reservoir operators. The initial product state p ® W R evolves according to the unitary evolution e- iHt (p ® WR)e iHt and by partial tracing with respect to the reservoir degrees of freedom one finds for the evolved system density matrix

n,m where cmn(t) = Tr(e-iz=twReiZnt). Note that the matrix cmn(t) is semipositive definite and hence

(20) n,m defines the Kraus representation of the completely positive map A(t). The solution of the pure de coherence model can therefore be found without explicitly writing down the underlying master equation. Our method, however, enables one to find the corresponding generator L(t). It is given by the following formula (21) n,m where the functions amn(T) are defined by a mn = cmn/cmn . We stress that this example belongs to the commutative class, that is, [L(t), L(s)] = O.

96

Example 3.2. Consider the dynamical map for a qudit (d-Ievel quantum system) given by

A(t) = F(t)ll + [1 - F(t)]1' ,

(22)

where l' : B(C d ) ------- B(C d ) denotes completely positive trace preserving projection, and F(t) is a real function such that

F(O) = 1 .

F(t) E (0,1],

(23)

For example take a fixed qudit state wand define l' by the following formula l' P = w Trp. Another example of a completely positive projection is the following: let Pn = In nl and define 1'p = 2:n PnpPn . For example for d = 2 one obtains the following formula for the evolution of p(t):

P(t)-(

Pu(O)

-

P21 (O)F( t)

P12(0)F(t)) P22 (0) .

(24)

Clearly, A(t) being a convex combination of II and l' is completely positive trace preserving map and hence it defines legal quantum dynamics of a qudit. One easily finds for the corresponding generator

.c(t)

=

a(t).c o ,

(25)

a(t)

= -

F(t) F(t) ,

(26)

where

and

.co = II -1' ,

(27)

is a legitimate Markovian generator. Note that if F(t) = e-,t , then a(t) = " and hence .c(t) = ,.co defines Markovian generator. Note, that we may perfectly regular dynamics A(t) which is generated by highly singular generator .c(t). Take for example F(t) = cost. One obtains therefore the oscillation of the qubit coherence P12(t) = P12(0) cos t. However, the corresponding (25) is defined by a(t) = tan t, which displays an infinite number of singularities. Example 3.3. The previous example may be easily generalized to bipartite systems. Consider for example a 2-qubit system and let l' be a projector

97

onto the diagonal part with respect to the product basis 1m (9 n in ((:2 (9 ((:2. Let us take as an initial density matrix so called X -state 24 represented by

Po

=

(P~l P~2 P~3 P~4) o

.

P32 P33 0 P41 0 0 P44

(28)

It is easy to see that A(t) defined by (22) does preserve the structure of X-state, that is, p(t) has exactly the same form as in (28) with t-dependent Pmn . Let

F(t) = 1

-lot

f(u)du .

(29)

It is clear that the t diagonal elements are time independent Pkk(t) = Pk~' and Pkl(t) = (1- fa f(u)du)Pkl' for k =1-1. The entanglement of the 2-qublt X-state p(t) is uniquely determined by the concurrence

C (t) := 2 max { Cl (t), C2 (t), O} ,

(30)

where Cl(t)

=

Ip23(t)l- VPllP44 , C2(t)

= IP14(t)l- VP22P33 ,

(31)

that is, p( t) is entangled if and only if Cl (t) > 0 or C2 (t) > O. Let us observe that the function f(t) controls the evolution of quantum entanglement. Consider for example f(t) = qe-,t, with 'Y > 0 and E E (0,1]. One finds from (26) the following formula a(t) = q[(l - E)e l t + E]-l. Note, that for E = 1 it reduces to a(t) = 'Y, that is, it corresponds to the purely Markovian case. Hence, the parameter '1 - E' measures the non-Markovianity of the dynamics. Suppose now that Po is entangled. The entanglement of the asymptotic state is governed by C(oo) = 2max{cdoo), C2(00), O} with Cl(oo) = (1- E)lp231- VPllP44 , C2(00) = (1 - E)lp141- VP22P33 . It is clear that in the Markovian case (E = 1) the asymptotic state is always separable (C(oo) = 0). However, for sufficiently small 'E' (i.e. sufficiently big non-Markovianity parameter '1 - E') one may have Cl (00) > 0 or C2(00) > 0, that is, the asymptotic state might be entangled. This example proves the crucial difference between Markovian and non-Markovian dynamics of composed systems. In particular controlling 'E' we may avoid sudden death of entanglement 24.

98

4. Conclusions In conclusion, any non-Markovian quantum evolution may be described either by the non-local equation (9) or by a time-local equation (12). Local approach is more simple and well suited for practical purposes. The price we pay for the local approach is that in general the corresponding generator may be highly singular (for example £(t) = tan t £3) and it keeps a memory about the starting point 'to'. Our examples show the power of this approach - one is able to provide (possibly singular) local generator but the construction of the corresponding memory kernel K(t) is not feasible. We stress that the problem of necessary and sufficient condition for the local generator which do guarantee that the corresponding dynamical map gives rise to the legitimate quantum evolution is still open and it deserves further studies.

Acknowledgments This work was partially supported by the Polish Ministry of Science and Higher Education Grant No 3004/B/H03/2007/33.

References 1. H.-P. Breuer and F. Petruccione, The Theory of Open Quantum Systems (Oxford Univ. Press, Oxford, 2007). 2. M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information (Cambridge Univ. Press, Cambridge, 2000). 3. J. Wilkie, Phys. Rev. E 62, 8808 (2000); J. Wilkie and Yin Mei Wong, J. Phys. A: Math. Theor. 42, 015006 (2009). 4. A. A. Budini, Phys. Rev. A 69, 042107 (2004); ibid. 74, 053815 (2006). 5. H.-P. Breuer, Phys. Rev. A 69 022115 (2004); ibid. 70,012106 (2004). 6. S. Daffer et al. Phys. Rev. A 70, 010304 (2004). 7. A. Shabani and D.A. Lidar, Phys. Rev. A 71, 020101(R) (2005). 8. S. Maniscalco, Phys. Rev. A 72, 024103 (2005). 9. S. Maniscalco and F. Petruccione, Phys. Rev. A 73, 012111 (2006). 10. J. Piilo, K. Harkonen, S. Maniscalco, K.-A. Suominen, Phys. Rev. Lett. 100, 180402 (2008); Phys. Rev. A 79, 062112 (2009). 11. E. Andersson, J. D. Cresser and M. J. W. Hall, J. Mod. Opt. 54, 1695 (2007). 12. A. Kossakowski and R. Rebolledo, Open Syst. Inf. Dyn. 14, 265 (2007); ibid. 15, 135 (2008). 13. A. Kossakowski and R. Rebolledo, Open Syst. Inf. Dyn. 16, 259 (2009). 14. H.-P. Breuer and B. Vacchini, Phys. Rev. Lett. 101 (2008) 140402; Phys. Rev. E 79, 041147 (2009). 15. M. Moodley and F. Petruccione, Phys. Rev. A 79, 042103 (2009). 16. B. Vacchini and H.-P. Breuer, Phys. Rev. A 81, 042103 (2010).

99

17. D. Chruscinski, A. Kossakowski, and S. Pascazio, Phys. Rev. A 81, 032101 (2010) 18. D. Chruscinski and A. Kossakowski, Phys. Rev. Lett . 104,070406 (2010) . 19. G. Lindblad, Comm. Math. Phys. 48, 119 (1976). 20. V. Gorini, A. Kossakowski, and E.C.G . Sudarshan, J. Math. Phys. 17, 821 (1976). 21. R . Alicki and K. Lendi, Quantum Dynamical Semigroups and Applications (Springer , Berlin, 1987). 22. S. Nakajima, Prog. Theor. Phys. 20 , 948 (1958); R. Zwanzig, J. Chern. Phys. 33, 1338 (1960). 23. H.-P. Breuer, B. Kappler and F. Petruccione, Phys. Rev. A 59,1633 (1999). 24. T. Yu and J. H. Eberly, Opt. Comm . 264 , 393 (2006) ; Q. Inf. Comp . 7, 459 (2007); Phys. Rev. Lett. 97, 140403 (2006); ibid. 93 , 140404 (2004).

This page intentionally left blank

Quantum Bio-Informatics IV eds. L. Accardi, W. Freudenberg and M. Ohya © 2011 World Scientific Publishing Co. (pp. 101-115)

SELF-COLLAPSES OF QUANTUM SYSTEMS AND BRAIN ACTIVITIES

K.-H. FICHTNER Unversity lena, Institute of Applied Mathematics, 01143 lena, Germany E-mail: [email protected]

L. FICHTNER Unversity lena, Institute of Psychology, 01143 lena, Germany E-Mail: [email protected]

w.

FREUDENBERG

Techn. University Cottbus, Dep. of Mathematics, 03013 Cottbus, Germany E-mail: [email protected]

M.OHYA Department of Information Science and Quantum Bio-Informatic Center, Tokyo University of Science, Noda City, Chiba 218-8510, lapan E-Mail: [email protected] We explain the relation between the quantum statistical model of the recognition process developed in the last years in a series of papers (cf. [7, 9, 10, 11, 12]) and a certain process of self-collapses. This process will be modeled by a classical homogenous Markov chain.

1. Introduction

Physicists as R. Penrose or H. P. Stapp (cf. [25, 38, 39]) but also at an increasing rate specialists of modern brain research (cf. [35, 36, 34, 37]) are convinced that information processing in the brain cannot be described appropriately by models based on classical physics or classical stochastics. So for instance H. P. Stapp argues in [38] that "classical physics cannot explain consciousness because it cannot explain how the whole can be more than the part. " A first attempt to explain the process of recognition in terms of quantum statistics was given in [7]. The procedure ofrecognition can be described as 101

102

follows: There is a set of complex signals stored in the memory. Choosing one of these signals may be interpreted as generating a hypothesis concerning an "expected view of the world". Then the brain compares a signal arising from our senses with the signal chosen from the memory leading to a change of the state of both signals. Furthermore, measurements of that procedure like EEG or MEG are based on the fact that recognition of signals causes a certain loss of excited neurons, i.e. the neurons change their state from excited to non-excited. As it was pointed out by R. Penrose [25] this change that comes along with recognition of a signal can be identified with a process of self-collapses. A quantum statistical model of the recognition process should reflect the change of the signals and the loss of excited neurons. In a (still incomplete) series of papers the procedures of creation of signals from the memory, amplification, accumulation and transformation of input signals, and measurements like EEG and MEG are treated in detail (cf. [17, 8, 9, 10, 11, 12, 14, 13, 22]). In the present note we will not present this approach in detail and in full mathematical strength. A few of the basic ideas and structures of the proposed model of the recognition process will be sketched and we will explain the relation between this model and a certain process of self-collapses. In Section 2 we will collect some biological facts and experiments described in [26]. Moreover, we will cite some opinions given by R. Penrose, W. Singer and others allowing to formulate some basic postulates and requirements each brain model has to fulfill. Our model seems to be appropriate and in accordance with the experimental results. The subsequent section contains the basic mathematical notions. We introduce the underlying Hilbert space representing the space of signals and the basic operators acting on the signal space. In the sequel we explain the basic ingredients of our model of the recognition process. For simplicity we will restrict our considerations to the case of interaction of two signals one coming from our senses and the other one created from our memory. In Section 4 the single steps of the process of recognition will be modelled by a Markov chain with discrete time.

2. Some biological facts and experiments In this section we want to present some biological facts and experiments. Each mathematical model describing certain aspects of brain activities should be in accordance with these experimentally proven facts. Firstly, using EEG measurements one gets information on the densities of excited neurons located in the regions of the brain. These densities depend on time.

103

The curves are of the following type:

no activity

no activity

activity ... time

The behaviour of that curve shows two types of periods: periods of oscillations interpreted by specialists as phases of no activity, and periods interpreted as phase of special activity in the considered region of the brain. As an example we mention some experiments described in [26]. All regions of the cortex seem to have their own electromagnetic rhythms. For example, the so-called p.,- rhythm which is produced in certain parts of the cortex that process tactile stimuli and control movement, consists of two main frequency components, one around 10 Hz and the other around 20 Hz. The 20 Hz component of the p.,-rhythm seems to be closely related to motor functions, while the other one is linked more to the sense of touch. "What exactly causes the oscillation is still a big puzzle" [26]. The experiments show that the functional state of the cortex can be monitored by measuring changes in the 20 Hz rhythm in that area of the brain [26]. Using MEG one could show that this rhythm is significantly suppressed if the subject moves his fingers, thereby activating the motor cortex. Interestingly, a similar suppression occurs when the subject merely imagines making such movements or just views someone else moving their finger. Similar effects were observed by G. Rizzolatti (University of Parma/Italy), who used needle electrodes to measure the response of neurons in the brain of a monkey. It was observed that the neurons discharge both when the monkey picks a

104

raisin and when it sees the experimenter make the same movement. The conclusion is that one has to unravel the significance (or unimportance) of the cortical rhythms during the periods of recognition of signals or other actions of the brain. Summarizing one can state that there are periods of no activity in certain regions indicated by the rhythms mentioned above, and there are periods of action where the rhythms are suppressed. Considering a quantum model of the brain the periods of no activity in certain regions of the brain should be represented by a unitary evolution (the quantum system resp. a part of the system remains isolated from the enviroment), i. e. it is a process of type 2 in the sense of J. v. Neumann [40]. Now, if there will be a signal arising from the senses the process of recognition starts. That process represents a rapid sequence of "trials" checking whether the signal from the senses and the signal created by the brain (at least partially) coincide. Let us mention still Stapp (cf. [39]) who uses the second quantization of harmonic oscillators to explain the observed oscillations. Stapp identifies these trials with measurements performed by a mysterious "observer" in the brain what seems to be non-realistic. In our model of recognition these trials are not represented by a process of measurements. Nevertheless, the results of the trials are represented by projections like in the case of measurements. Now, the experimentally verified quantum Zeno effect tells us that a rapid repetition of a certain measurement will suppress the unitary evolution of the system, i. e. the effects of the measurements dominate the evolution of the system. We will see that the quantum model proposed by us enables one to explain the different phases of the curves obtained as the outcomes of EEG measurements using the quantum Zeno effect. Hameroff and Penrose discuss in [25] the concept of quantum theory related to some biological aspects of brain activities. Especially, they deal with the problem how recognition of signals is connected with a process of selfcollapses. We would like to mention some basic statements taken from their paper [25]: - As long as a quantum system remains isolated from its enviroment, it can be satisfactorily described in terms of a deterministic, unitarily evolving process. That process is computable, non-random, and reversible. - The conventional quantum theory view is that the quantum state reduces by enviroment entanglement, measurement or observation (subjective reduction). The mesurement process is non-computable, random, and irreversible, and it is known in various contexs as collapse of the wave function.

105

- A number of physicists have argued in support of special models in which the rules of standard quantum mechanics are modified by the inclusion of some additional procedure according to which the reduction of the state becomes an objectively real process (objective reduction) the system abruptly self-collapses. That would give a new non-computable theory, i. e. they are convinced that processes of self-collapses cannot be described in terms of the conventional quantum mechanics it requires additional postulates (relations to Gadel's incompleteness theorem ?) - Consciousness, it is argued, requires non-computability. The only readily available apparent source of non-computability are self-collapses. The self-collapse, irreversible in time, creates an instantanoues "now" event. Sequences of such events create a flow of time, and consciousness. As it was mentioned in Section 1 in a series of papers we developed a quantum statistical model describing certain aspects of the recognition process. In the sequel we will present now certain aspects of this model. We will argue that the model is in accordance with the experimental results and the opinions cited above. The paper is focussed on the relation between the process of recognition and a certain process of self-collapses. 3. The Space of Signals In the present section we introduce briefly notions and notations needed in the sequel. For interpretation and motivation of the introduced notions we refer to the above mentioned papers. Starting point will be a set G representing the space where the process of recognition and processing of the signals takes place. For the mathematical model it is irrelevant what is the concrete structure of G. So let G be an arbitrary complete separable metric space equipped with a fixed finite diffuse measure on the a-algebra of Borel sets of G. The elements of the Hilbert space L2 (G, fJ) can be interpreted as functions of the excited neurons. We assume that G decomposes into disjoint regions G I , ... , Gn being responsible for different tasks. So L2(G k ) represents the space of the excited neurons in the region G k . Now, let r(L2(G)) denote the symmetric Fock space over L2(G):

Incoming signals are identified with states on the symmetric Fock space 1{ = r(L2(G)). Why do we choose this Fock space as signal space? The main reason is the possibility to identify the Fock space over L2 (G) with

106

the tensor product of the Fock spaces over L 2 (Gd, ... , L2(G n ):

r(L2(G l U ... U G n )) = r(L2(Gd)0 ... 0r(L2(G n )). The signal decomposes according to the decomposition of the space. Now, we assume that the decomposition is fixed and maximal (very fine) in that sense that each region G r is responsible only for one simple task represented by an E L2(G r ), Ilrll = 1, r::; n. For each r E {I, ... ,n}, k ~ 1 define functions fl E r(L2(G r )) by

r

{VkT.fIr(Xj),X=(Xl, ... ,Xk)EGk ,

r-

fk (x)

:=

]=1

r-

,

o

fo (x)

_

:=

1I0(X),

elsewhere

Observe that for each r E {I, ... , n} UIh'2o gives an orthonormal system in r(L2(G r )). We denote by H~ig c r(L2(G r )) the Hilbert space with basis UIh'2o and interpret this space as space of signals of type r. An especially important class of functions in the Fock space are the so-called exponential vectors. Exponential vectors in H~ig are given by 00

exp{a· r} =

L k=O

k

~fI

(a E C).

v k!

Observe that

m d exp{t· fr} I dtm t=O

and

= ~ . frm' m > O.

One easily concludes that the linear span of the exponential vectors is dense in H~ig, i. e. H~ig

= Lin{exp{a· tr}:

a E IC},

r E {I, ... , n}.

The space '1.Isig . IL

.

=

'1.I si g,o, ILl

,o,'1.Isig

we will call the space of regular signals. States on signals. The states Wg

:=

(1)

'U • • . 'U1Ln

Hsig

are called regular

e-llgl12 . (exp{g},· exp{g})

are called coherent states on H~ig if g E L2(G r ) resp. on Hsig if g E L2(G). Hereby, (,.) denotes the scalar product in the corresponding Hilbert space. Roughly speaking, coherent states describe states of systems of quantum particles where each particle is in the same one-particle state. Furthermore, Wo = (exp{O}, . exp{O}) is called the vacuum state.

J07

4. The Process of Recognition The recognition process is based on a comparison of signals: one signal will be the input signal coming from our senses, the other one is taken from the memory. Both signals are modeled by the Hilbert space Hsig introduced above. The memory space Hmem is a further Hilbert space the structure of which we will not discuss in the present paper. Also we will not describe here the mechanism how the signal is taken out from memory. A detailed discussion and interpretation one can find in [7] and [8, 14, 15]. The whole processing procedure will take place step by step on the space

The comparison procedure between the two mentioned signals is done with the aid of operators (proj ections) on H := Hsig®Hsig , and we concentrate our considerations to these first two spaces of the tensor product space. Basic for our considerations will be the symmetric beam splitter being a well-known operator in quantum optics describing the splitting of coherent light into two beams. Definition 4.1. Let r E {I, ... ,n} be fixed. The linear operator

Vr(exp{f}®exp{g}) := exp

{~. (j + g)} ®exp {~. (j -

g)}

(2)

we call symmetric beam splitter in the region r. It is well-known that tensor products of exponential vectors are total in r(L2(G r )) ®r(L2(G r )). So the symmetric beam splitter Vr is fully characterized by formula (2). Proposition 4.1. (Properties of the symmetric beam splitter) For r E

{I, ... ,n} the symmetric beam splitter Vr is unitary and self-adjoint: V; = Vr and V; =

][r(£2(G r ))0r(L2(G r

))

(][

denoting the identical opera-

108

tor). Moreover, jor all j, g E L2(G r

and a, (3 E C

)

Vr (exp{aj}0exp{(3j}) = exp

{a+(3} v'2 j 0exp {a-(3} v'2 j

(4)

Vr (exp{j}0exp{j}) = exp{ v2j}0exp{O} 1

1

Vr(exp{ O}0exp{j}) = exp{ v'2 j}0exp{ 1

(3)

v'2 j}

(5)

1

Vr (exp{j}0exp{ O}) = exp {v'2 j}0exp {v'2 j}

(6)

V; (exp{J}0exp{g} ) = exp{J}0exp{g}.

(7)

A good survey on properties of general (usually non-selfadjoint) beam splitting operators with an arbitrary number of in- and outputs is given in [24]. In the sequel Prw := (\{f, .)\{f denotes the projection onto (the subspace generated by) \{f. For r E {I, ... , n} define projections T[, T[, To, To on H~ig0H~ig by

T[ := Vr(1I1t~ig0Prexp{O})Vr, = 1I1t~ig01I1t~ig =:

To

:=

V;

IT)

To

:= Vr(Ir -1I1t~ig0Prexp{O})Vr = Ir -

T[

= Ir -

T[

Observe that T[ has the property

T[ (exp{ar}0exP{br}) = exp {~(a + b)r} 0exp {~(a + b)r}. So, T[ corresponds to a projection onto the subspace of H~ig 0H~ig with equal first and second factor of the tensor product. T[ is interpreted as recognition in the r-th region whereas To = Ir - T[ indicates that there was no recognition in the area r. Now we join together these operators T[ and fg of partial recognition resp. "no" recognition in the single areas to operators on the whole tensor product signal space H := Hsig0Hsig. We put

n := {O, I}n =

{E

(EI,'"

=

, En):

E {O, I}, k::; n}

n

n

'i

to.Tr

'= '6'

(£1 , . .. ,E n ) ·

r=l

Ek

r=l

Er '

109

Because of notational convenience we have put in the above definition T[ := T[ (however To =I- ~) This assembly of the operat ors in the single areas was possible because of

Now we want to sketch the process of recognition. Starting point will be a state {}o on H representing a pair of signals the first arisen from the senses the second one created from the brain. Now, there is chosen a certain element ;Sl = (cL ... ,E~) E n indicating what happens in the first step of recognition: - EX:

= 1 indicates recognition in the k-th region,

- EX:

= 0 means there

is no recognition in the k-th region.

The corresponding event will be identified with the projection TCcL ... ,e;). Like in the case of measurements the probability of the event (EL ... , E~) is given by

tr ( (}o . TCci ,... ,e;)) where tr( ·) denote the usual trace of an operator. Together with the probability tr({}o . TE" ) representing the subjective reduction of the state {} caused by the measurement according to TE" we can consider the following transformation of the state {}o representing objective reduction caused by the self-collapse indicated by ;Sl:

K E'l ((}o ) .._- TE'l {}o TE" tr({}o . TE") provided tr({}o . TE") > O. So for each given sequence (EL ... , E~) we get a channel mapping the initial state {}o into the new state KE" ({}o) where partial recognition appears in all regions k with EX: = 1. Starting point for the second step of recognition will be {}l := KE" ({}o) and a second sequence ;S2 E n. Applying the same procedure replacing {}o by {}l the probability of the event indicated by ;S2 will be

110

and caused by the self-collapse indicated by E'2 the state 01 be transformed to

= KE'l (00) will

provided tr(Ol . TE'2) > O. This procedure can be repeated arbitrarily often - given an initial state 00 and a sequence (E'k)k=l one obtains this way a sequence (Ok)k=O of states on 1i and a sequence (tr(Ok _ l . TE'k ))~l of probabilities of the events (E'k)k=l provided these expressions exist (i. e. if tr(Ok_l . TE'k) > 0 for k ~ 1). A necessary condition for this to hold is that the sequence (E'k)~l has to be in some sense increasing. More precisely, we require

(rE{l, ... ,n})

(8)

for all kEN. The relation (8) defines a semi-ordering of the elements in

n.

We write E'k ~ E'k+l to indicate relation (8). This property is in accordance with the requirements our model should fulfill. If once partial recognition in the area r occurs there will be no change for this region in the future, only further zeros may be transformed into 1. The full recognition of the signal would be obtained if for some kEN we have E'k = (1, .. . ,1). The sequence (Ok)~O is in accordance with this relation. Especially, we have if E'k - l ~ E'k

does not hold,

(9)

and 1'f

-k-l <8 E _ -k E .

(10)

The above identities are based on the following properties of the introduced projection the easy proof of which we will omit.

Proposition 4.2.

T~T~ = T~T~ = T~, LTE' = ][H

T~T[ = T[T~ = T[,

(E'l ::; E'2) implies

= TE'2 TE'l = T max{E'l ,E'2} TE'l TE'2 = TE'2 TE'l = TE'2 TE'l TE'2

E'l ::; E'2 (E'l, E'2 E n) (E'l ::; E'2)

T~T[ = T~T[ = 0

111

Summarizing we state that recognition process is characterised by an mcreasing sequence (Ek) k'=l with corresponding sequence of states

en

Unfortunately, this sequence (Ek) k'= l is unknown and seems to be noncomputable. Only in the case the sequences (Ek) ~ l would be known one can identify the process of recognition with the sequence (Ok)~O of states. The way out of this dilemma is to consider the vectors Ek as random and to consider a classical Markov chain describing this process of recognition.

5. A Markov Chain with Discrete Time Since the sequence (Ek)k'=l is not known we replace this sequence by a sequence of random vectors (Xk)~l' Hereby, X k has values in 0 and is interpreted as the random outcome in the k-th step of the recogntion process. The sequence (Ok)k'=O) of states we replace by a new sequence (f3k)~O of states on H given by

f3 k(-)

;=

L P(Xk =

E) . tr(Ke(Oo)(-))

(k 2: 1).

(11)

e Efl

Hereby, P(Xo = (0, ... ,0)) = 1 and f3 0 = 00 is the initial state on H. Following the above arguments the sequence (Xk)~O should form a classical Markov chain with initial distribution PXo = 15(0 , .. . ,0 ) and with transition probabilities

(k 2: 0)

(12)

where EO = (0, ... ,0). These probabilities represent conditional probabilities of passing in the k-th step to Ek starting from Ek - l. We conclude and summarize the above considerations with the following theorem the proof of which we will omit. Theorem 5.1. Let 0 be a state on H (0 is the initial state).

(a) Th ere exists exactly one probability measure P e on ON (equipped with the canonical O"-algebra) with finite-dim ensional distributions

112

P;: given by m -0 -m -0 rrm tr({!TC'k-l TC'k) Pe(E, ... ,E )=b(O, ... ,O)({E})k=l tr({!TC'k-l)

() 13

if tr({!TC'l) .... · tr({!TC'=-l) > 0 Pem (-0 E,

-m) = ... ,E

0

otherwise.

(14)

(b) The sequence (Xk)k=O of random vectors is increasing, z. e.

(k ;:::: 0). (c) The sequence (Xk)k=O is a homogenous Markov chain with initial distribution 15(0, ... ,0) and with transition probabilities -1 -2)

( pEE ,

= tr({!TC'2) tr ({!TC'l )

(15)

(d) The m-steps transition probabilities are given by

(16) (e) (m;:::: 1, E EO).

(17)

Since 0 is a finite set and the sequence (Xk)k=O is increasing it definitely reaches its maximum Xmax indicating the final result of the recognition s

process. This vector Xmax <:::: (1, ... ,1) may be non-random. Further, one may introduce the random number 7] of steps one needs to achieve X max . One has 7] = 1 + max {k: X k < X max}. In a more refined model one has to pass over in a sense of a scaling limit from this discrete Markov chain to a homogenous Markov chain with continuous time. This will be useful since based on the measuring device one cannot measure what is going on in the single (very short) steps of the recognition process. We will deal with this problem in a forthcoming paper.

113

References 1. L. Accardi and M. Ohya. Compound channels, transition expectations and liftings. Applied Mathematics EJ Optimization, 39(1):33- 59, jun 1999. 2. L. Accardi and M. Ohya. Teleportation of general quantum states. In Quantum information (Nagoya, 1997), pages 59-70, Singapore , 1999. World Scientific. 3. A. K. Engel and W. Singer. Temporal binding and the neural correlates of sensoryawarenes. Trends in Cogn. Sci., 5(1):16-25, 2001. 4. J. W . Philips et al. Imaging neural activity using MEG and EEG. IEEE Engineering in Medicine and Biology, pages 34-42, May/June 1997. 5. Akinori Nakamura et.al. Somatosensory homunculus as drawn by meg. Neurolmage, 7(4):377- 386, 1998. 6. Annette Sterr et.al. Perceptual correlates of changes in cortical representation of fingers in blind multi finger braille readers. The Journal of Neuroscience, 18(11):4417, 1998. 7. K.-H. Fichtner and L. Fichtner. Bosons and a quantum model of the brain. Jenaer Schriften zur Mathematik und Informatik Math/ Inf/ 08/ 05, FSU Jena, Faculty of Mathematics and Informatics, Jena, 2005. 27 pages. 8. K.-H. Fichtner and L. Fichtner. Quantum markov chains and the process of recognition. Jenaer Schriften zur Mathematik und Informatik Math/Inf/02/07, FSU Jena, Faculty of Mathematics and Informatics, Jena, 2007. 24 pages. 9. K.-H. Fichtner and L. Fichtner. Quantum models of brain activities I. Recognition of signals. In J .C. Garcia, R. Quezada, and S.B. Sontz, editors, Quantum Probability and Related Topics, volume XXIII of QP-PQ: Quantum Probability and White Noise Analysis, pages 135 - 144, New Jersey London Singapore, 2008. World Scientifc. 10. K.-H. Fichtner, L. Fichtner, W. Freudenberg, and M. Ohya. On a mathematical model of brain activities. In Quantum Theory, Reconsideration of Foundations - 4, volume 962 of AlP Conference Proceedings, pages 85 - 90, Melville, New York, 2007. American Institute of Physics. 11. K.-H. Fichtner, L. Fichtner, W. Freudenberg, and M. Ohya. On a quantum model of the recognition process. In L. Accardi, W. Freudenberg, and M.Ohya , editors, Quantum Bio-Informatics, volume XXI of QP- PQ: Quantum Probability and White Noise Analysis, pages 64 - 84, New Jersey London Singapore , 2008. World Scientifc. 12. K.-H. Fichtner, L. Fichtner, W. Freudenberg, and M. Ohya. On a quantum model of the brain activities. In L. Accardi, W. Freudenberg, and M.Ohya, editors , Quantum Bio-Informatics III, volume XXVI of QP-PQ: Quantum Probability and White Nois e Analysis, pages 81-92, New J ersey London Singapore, 2010. World Scientifc. 13. K.-H. Fichtner, L. Fichtner , W. Freudenberg , and M. Ohya. Quantum models of the recognition process - mathematical prerequisites. Technical report, 2010. 44 pages. 14. K.-H. Fichtner, L. Fichtner , W. Freudenberg , and M. Ohya. Quantum mod-

114

15.

16.

17.

18.

19.

20. 2l. 22.

23.

24.

25.

26. 27.

els of the recognition process - on a convergence theorem. Open Systems 8 Information Dynamics, 17 (2):161-187, 2010. K.-H. Fichtner and W. Freudenberg. The compound Fock space and its application to brain models. In L. Accardi, W. Freudenberg, and M. Ohya, editors, Quantum Bio-Informatics II, volume XXIV of QP-PQ: Quantum Probability and White Noise Analysis, pages 55 - 67, New Jersey London Singapore, 2009. World Scientifc. K.-H. Fichtner, W. Freudenberg, and V. Liebscher. Time Evolution and Invariance of Boson Systems Given by Beam Splittings. Infinite Dimensional Analysis, Quantum Probability and Related Topics, 1(4):511 - 531, 1998. K.-H. Fichtner, W. Freudenberg, and M. Ohya. Recognition and teleportation. In W. Freudenberg, editor, Quantum Probability and Infinite Dimensional Analysis, volume XV of QP-PQ: Quantum Probability and White Noise Analysis, pages 85-105, New Jersey London Singapore, 2003. World Scientific. K.-H. Fichtner, W. Freudenberg, and M. Ohya. Teleportation schemes in infinite dimensional Hilbert spaces. Journal of Mathematical Physics, 46(10):102103, 2005. K.-H. Fichtner, V. Liebscher, and M.Ohya. A limit theorem for conditionally independent beam splittings. In M. Schiirmann and U. Franz, editors, Quantum Probability and Infinite Dimensional Analysis. From Foundations to Applications, volume XVIII of QP-PQ: Quantum Probability and White Noise Analysis, pages 227 -236, New Jersey London Singapore, 2005. World Scientific. K.-H. Fichtner and M. Ohya. Quantum teleportation with entangled states given by beam splittings. Comm. Math. Phys., 222:229-247, 200l. K.-H. Fichtner and M. Ohya. Quantum teleportation and beam splitting. Comm. Math. Phys., 225:67-89, 2002. L. Fichtner and M. Gabler. Characterisation of beam splitters. In L. Accardi, W. Freudenberg, and M. Ohya, editors, Quantum Bio-Informatics II, volume XXIV of QP-PQ: Quantum Probability and White Noise Analysis, pages 68 - 80, New Jersey London Singapore, 2009. World Scientifc. W. Freudenberg, M. Ohya, and N. Watanabe. On quantum logical gates on a general Fock space. In M. Schiirmann and U. Franz, editors, Quantum Probability and Infinite Dimensional Analysis. From Foundations to Applications, volume XVIII of QP-PQ: Quantum Probability and White Noise Analysis, pages 252 - 268, New Jersey London Singapore, 2005. World Scientific. Markus Gabler. Fock Space, Factorisation and beam Splitting: Characterisation and Applications in the Natural Sciences. PhD thesis, 2010. University Cottbus. Stuart Hameroff and Roger Penrose. Orchestrated objective reduction of quantum coherence in brain microtubules: the" orch or" model for consciousness. Mathematics and Computer Simulation, 40:453-480, 1996. R. Hari and O. V. Lounasmaa. Neuromagnetism: tracking the dynamics of the brain. Physical World, pages 33-38, May 2000. A. Nummenmaa, T. Auroanen, and M. S. Hamalainen. Hierarchical bayesian

115

estimates of distributed meg sources. N euroImage, 35:669- 685, 2007. 28. M. Ohya. Mathematical Foundation of Quantum Computer. Mazuren Publ. Comp., 1999. 29. M. Ohya. Complexity in quantum system and its application to brain function. In T. Hida and K. Saito, editors, Quantum Information II, pages 149160, Singapore, 2000. World Scientific. 30. M . Ohya, K.-H . Fichtner, and W. Freudenberg. Recognition and teleportation. In T . Hida and K. Sa ito, editors, Quantum Information V, pages 1- 17, New Jersey London Singapore , 2006. World Scientific. 31. J. W. Phillips, R. M. Leahy, and J. C. Mosher. Imaging neural activity using meg and eeg. IEEE Engineering in M edi cine and Biology, 16(3):34- 42, 1997. 32. P. R. R oelfsema and W. Singer. Det ecting connectedness. Cerebral Cortex, 8:385- 396, 1998. 33. J. M. Schwartz , H. P . Stapp , and M. Beauregard. Quantum physics in neuroscience and psychology. Phil. Trans . Royal Soc, B360( (1458)) , 2005. 34. Wolf Singer. Consciousness and the structure of neuronal representations. Phil. Trans . R. Soc . Lond. , B 353:1829- 1840, 1998. 35. Wolf Singer . Neuronal synchrony: a versatile code for the definition of relations? N euron, 24:49-65 , 1999. 36. Wolf Singer. Sriving for coherence. News and views. Nature, 397:391- 393, 1999. 37. Wolf Singer. Der Beobachter im Gehirn. Essays zur Hirnforschung. Suhrkamp Verlag, Frankfurt a.M., 2002. 38. H . P. Stapp. Mind, Malt er and Quantum Mechanics. Springer , Berlin Heidelberg, 2nd edition, 2003. 39. H. P . Stapp. A model of the quantum-classical and mind-brain connections, and the role of the quantum zeno effect in the physical implementation of conscious. arXiv, 0803.1633v1 (physics.gen-ph), 11 March 2008. 40. John von Neumann. Mathematis che Grundlagen der Quantenmechanik. Springer, Berlin, 1 edition, 1932.

This page intentionally left blank

Quantum Bio-Informatics IV eds. L. Accardi, W. Freudenberg and M. Ohya © 2011 World Scientific Publishing Co. (pp. 117-128)

STATISTICAL ANALYSIS OF RANDOM NUMBER GENERATORS

LUIGI ACCARDI Universita di Roma Tor Vergata, Centro Interdipartimentale Vito Volterra, Via Columbia 2, 00133 Roma, Italy, E-Mail: [email protected]

MARKUS GABLER Brandenburg Technical University Cottbus, Department of Mathematics, PO box 101344, 03013 Cottbus, Germany, E-Mail: [email protected]

In many a pplications, for example cryptogra phy and Monte Carlo simulation, there is need for random numb ers . Any procedure , algorithm or device which is intended to produce such is called a random number generator (RNG). What makes a good RNG? This paper gives an overview on empirical testing of the statistical prop erties of the sequences produced by RNGs and special software packages designed for that purpose . We also present the results of applying a particular test suite-TestU01to a family of RNGs currently being develop ed at the Centro Interdipartimentale Vito Volterra (CIVV) , Roma, Italy.

1. Introduction

Assume Xl, ... , X N is a random binary sequence, i.e. for all 1 ::; k ::; N X k is a Bernoulli random variable with P(Xk = 1) = Pk E (0,1) . Such a sequence is called purely random, if Xl"'" X N are independent and identically distributed (i.i.d.) with Pk = P = 1/2. In many applications, for example cryptography and Monte Carlo simulation, there is need for random numbers. Using binary expansion and transformation methods any such random numbers can be constructed from purely random binary sequences to an arbitrary precision, ignoring numerical difficulties for the moment. So many ways have been invented to produce, or at least simulate, realizations Xl, . . . , X N of such sequences. Repeated flipping of a "fair" coin and recording "0" for "heads" and "I" for "tails" would be one way, but surely too timeconsuming, if you needed, say, 10 18 exponential random numbers for some extensive stochastic simulation. Using randomness in physical quantities like noise in an electrical 117

118

circuit or the timing of strokes at a user keyboard would be another. Or even manipulation of a definitely deterministic process (like a small computer programm) in a way that the outcomes appear to be purely random might serve just as well. Any such procedure, algorithm or device which is intended to produce realizations of random sequences, we call a random number generator (RNG). Deterministic RNGs are also sometimes called pseudo-random number generators (PRNG) or algorithmic RNGs. But no matter what the nature of a particular RNG is, the question arises whether the sequences it produces can be distinguished from the ones coming from the purely random theoretical ideal. This paper only deals with the statistical properties of binary sequences (viewed as realizations of random binary sequences). But while good statistical properties are necessary, there are, of course, other important quality criteria, including: Efficiency with respect to time and memory. Sufficiently large period: The internal state of a deterministic RNG runs over a finite set and is therefore periodic, so running through a significant portion of the whole cycle should be beyond reach in practice. Repeatability: the ability to reproduce the same sequence as many times as needed. Non-deterministic RNGs are not repeatable. Portability: independence from software and hardware environment. Unpredictability: The next output bit of an RNG is not to be predicted from knowing preceding ones any better than by "tossing a fair coin". For a deterministic RNG this means that it should not be possible to find the internal state and/or the transition law from knowing the output sequence, at least not in reasonable time employing a reasonable amount of resources. The importance of these criteria mostly depends on the application the RNG is intended for. So while for some uses in cryptography nothing less than an unpredictable RNG will do, for simulational purposes the main emphasis might be on high efficiency and repeatability. Not all RNGs are designed to produce binary (bit) sequences. Besides bit generators, i.i.d. Uniform{O, ... , 2m - I} and i.i.d. Uniform[O, 1) generators are also very common. The former produce m-bit-integers, where 31 and 32 bits are used quite frequently, the latter approximate reals, also only up to a certain precision (float, double, etc.), of course. These different outcomes can be transformed one into the other quite easily, though. Di-

119

viding a bit sequence into m-bit-blocks yields the binary representation of a sequence of m-bit-integers. An m-bit-integer divided by 2m is a [0,1) real. The converse works just as well. In addition, a random binary sequence is purely random if and only if the corresponding m-bit-integer sequence is i.i.d. Uniform{O, ... , 2m - I}. Thus, even though some tests need bit sequences and others, say, 32-bit-integers as input, they can be applied to any RNG, as long as the output of the RNG is transformed to the right format. Section 2 deals with statistical tests and special software packages designed for testing RNGs. Then, in section 3, the results of applying a particular test suite - TestUOl - to a family of RNGs currently being developed at the Centro Interdipartimentale Vito Volterra (CIVV) at the Universita degli studi di Roma Tor Vergata, Italy, are presented. 2. Statistical Testing of RNGs Bad RNGs are those that fail simple tests, whereas good RNGs fail only complicated tests that are hard to find and run. P. L'Ecuyer

2.1. Historical Development Over the years many statistical tests for testing random number generators have been proposed. One of the first collections was found in earlier editions of Knuth [1]. These tests, plus a few others designed for testing parallel generators, were implemented in SPRNG: a scalable library for pseudorandom number generation by Mascagni and Srinivasan [2]. New and more stringent a tests, compared to the ones from the just mentioned Knuth [1], were introduced by Marsaglia in 1985 [3]. Most of these tests were later implemented in DIEHARD: A Battery of Tests of Randomness by Marsaglia in 1995 [4], probably the best-known software package for RNG testing. Because of its very unflexible setup its usefulness has become rather limited, though, by now. First of all, the sample sizes (as well as other parameters) are fixed in the package and not very large by modern standards, which makes the test results unreliable for many of todays applications. Second the sequence must be provided to the package a A test Tl is considered more stringent than another test T2, if a generator passing Tl is also likely to pass T2.

120

in the form of 32-bit-integers in a binary file, rather than just passing the RNG function to the package, which then in turn produces the numbers "on demand". This also makes any generator having an accuracy less than 32 bits fail DIEHARD. The National Institute of Standards and Technology (NIST), USA, developed the NIST Statistical Test Suite by Rukhin et. al. [5] for the evaluation of the Advanced Encryption Standard (AES) candidate algorithms. The state-of-the-art library for testing RNGs today is TestU01: A C Library for Empirical Testing of Random Number Generators introduced in 2007 by L'Ecuyer and Simard [6]. It implements: 1) a large variety of different RNGs proposed in the literature and/or used in software packages or operating systems, 2) most of the statistical tests from DIEHARD, the NIST package, the Knuth collection, other tests found in the literature and some original ones, 3) predefined test batteries and 4) tools for investigating dependence of the period length of a generator within a whole family of RNGs and the length of a sequence when this generator begins to fail a given test systematically. Many of the statistical tests proposed for testing random numbers are easily passed while other tests seem to be quite difficult to pass. So what makes a good test? In the last years some efforts have been undertaken which, eventually, might lead to something like a "hierarchy of tests". For example, Tsang et. al. [7] define the so-called "Stringency level" of a test, in order to optimize the choice of parameters for the Collision Test. The results of testing a wide range of generators against some difficult-to-pass tests of randomness by Marsaglia and Tsang [8] as well as against other test suits, including DIEHARD, NIST and Knuth's collection are found in [9]. According to their results, applying these three difficult-to-pass tests seems to "reduce the volume and concentrate the essence" of many of the statistical tests in use today. However, through empirical investigations on our part, we have found generators, that do pass these three tests, but fail others quite badly. More details on these results are reported in section 3.

2.2. General Setup of a Statistical Test What is the basic setup of a statistical test? Let Xl, ... , xN be a sequence of real numbers considered as realisations ofrandom variables Xl' ... ' X N over a common probability space (Sl, F, P) where P is unknown. Denoting with Po the set of all probability measures fulfilling certain given requirements about the common distribution of X I, ... ,XN , the statement Ho : P E Po

121

is called null hypothesis. Whether Ho holds or not is unknown and the object of a test is to gather information from the sequence Xl, ... , X N in order to either reject Ho or not. For the testing of binary sequences the null hypothesis throughout this paper will be given by Po = {P: XI, . . . ,XN is a truly random binary sequence}, i.e.

Ho : Xl , "" X N i.i.d., P(Xk

=

1)

= P(Xk = 0) =

1/2, k

=

1, ... , N.

(1) Definition 1. The random number Y := t(X I , ... , XN) , where t is a realvalued measurable map, is called statistic. A statistic T taking only the values and 1 is called a test. Thereby, the events {T = I} and {T = O} are interpreted as "reject Ho" and "do not reject Ho", respectively. If the probability of rejecting H o, even though it was true, is less than 0; E (0,1), i.e. Po (T = 1) :s; 0; for all Po E Po, the test is called significance test at level 0;.

°

Remark 2. Let T = t(X I , ... ,XN (1) For a given realization

)

be a significance test at level 0;.

Xl, ... ,XN

Ho is rejected , if t(Xl,""

XN)

=

l.

(2) Common choices for 0; are 0.05,0.01 or O.OOL (3) Rejecting Ho at level, say, 0; = 0.001, does not mean that it is not true. It just means that it is very unlikely to be true, because if it was true, Ho would only be rejected less than once in a thousand test runs, on average. It does happen nonetheless. On the other hand, not rejecting Ho does not mean it is true. The sequence was just "not bad enough" to be rejected. Now consider a statistic Y where to have a distribution function Fy(y) called p-value of the statistic Y. If F y distribution (under Ho). In this sense, statistics. Moreover

Po (0;/ 2 :s; U :s; 1 - 0;/ 2)

=

the distribution under Ho is known := Po(Y :s; y). Then U := Fy(Y) is is continuous, U has a Uniform[O, IJ p-values can be seen as standardized

0;

(0; E (0, 1), Po E Po) ,

(2)

l.e.

T := {01

0;/2:S; U :s; 1 - 0;/2 otherwise

(3)

122

defines a significance test at level 0:. Thus, Ho is rejected if the p-value U is close to 0 or 1. For general F y define a left and a right p-value of Y by

UL

:=

U

=

Fy(Y)

(4)

and

respectively, where F{J(y) := Po(Y 2: y) = 1 - Fy(y) + Po(Y = y). Then reject H o, if any of the left or right p-value is close to 0 (see L'Ecuyer and Simard [6]). Example: The X2-goodness-of-fit test

Let Xl, ... ,XN be a sequence of i.i.d. copies of a random variable X and Ho : P = Po the null hypothesis to be tested. For 1 ::; k ::; K define Pk := Po(X E A k ), where AI, ... ,AK is a finite partition of lR and let N

Ck

:=

L

(1 ::; k ::; K)

n{XnEAd

(5)

n=l

be the number of times the Xn fall into A k , where nB represents the indicator function of the event B. Then, under H o, C k follows a binomial distribution B(N,Pk) and Y :=

t

k=l

(Ck - EC k )2 ECk

=

t

k=l

(Ck - NPk)2 NPk

(6)

is approximately X2-distributed with K - 1 degrees of freedom (as N ---+ 00). Thus Ho is rejected, if the p-value U := FX2(K -1) (Y) is really close to 0 or 1, where Fx2(r) denotes the (continuous) distribution function of the X2 -distribution with r degrees of freedom. 2.3. Specialties for Testing of RNGs

As seen in the previous subsection, any statistic Y, whose distribution under Ho is known, at least approximately, can be used to define a test. Hence it will be called as a test statistic. In fact, for the testing of RNGs, a test can still be defined, even though the distribution of Y might not be (approximately) known. A number of generators may be used to estimate the distribution. And if these estimates are consistent across a variety of different and "presumably good" generators, the estimate may serve as Ho target distribution. In essence, statistical testing of RNGs is nothing but a particular kind of Monte Carlo simulation. Conversely, when testing an RNG for suitability

123

with respect to a particular Monte Carlo problem, running the simulation with a related but simplified model, that is, one where the distribution of the result can be attained theoretically, may serve as a test. Even if the distribution is not known, the results of the designated RNG can still be compared to the ones produced by a few other "good" generators of quite different designs. Most statistical tests for RNGs utilize the concept of a p-value. P-values of single tests should not only be in the proper range (not too close to 0 or 1), but should also be uniformly distributed on [0,1). Therefore, it might be useful to run the same test many times independently, i.e. on different parts of the original sequence. A number of independent first-level p-values can then be assessed by a second-level uniformity test resulting in an overall p-value. For example, while none of the single values of a sequence of supposedly independent p-values, say 0.24,0.26,0.23,0.21, gives any reason to question H a, the whole sequence does reveal a very non-uniform and/ or non-independent behaviour, though. This second-level test of uniformity could be the above-mentioned X2-goodness-of-fit test but usually an Anderson-Darling or a Kuiper version of the Kolmogorov-Smirnov test is applied. Very often RNGs are tested against whole batteries of tests and therefore p-values close to 0 or 1 are not too uncommon even for good (including perfect) generators. Therefore, the choice of a could be somewhat different from the ones for usual statistical testing mentioned earlier. If the final (first- or second-level) p-value of a test is really close to 0 or 1, the RNG is said to fail the test. If the p-value is suspicious, the t est is repeated and/ or the sample size is increased and often things will then clarify. Otherwise the RNG is said to have passed the test. But remember that this does not mean that the null hypotheses is true. The meaning of really close and suspicious should be made clear before running the test, of course. Test batteries usually have some suggested values for that purpose. For some applications there is the need for assessing much larger sequences than feasible due to memory limitations. These can be overcome by performing the same test many times on different subsequences and then somehow combining the results. One way is the above mentioned second-level uniformity t est. But there is another useful approach. For most statistical tests the target (Ha-) distribution of the test statistic Y is either a normal or a X2- or a Poisson distribution. Thus, instead of calculating a p-value for each test and then performing a second-level test, all the single Y 's could be added, the sum again being normal, X2 or Poisson,

124

respectively. This sum statistic could then, in turn, be used to give the final p-value, see [lOJ.

Example: The Birthday Spacings Test This test was introduced by George Marsaglia in 1984 [3J and uses the fact that (for large n) the number of collisions among the spacings induced by the order statistics of m independent uniform {O, ... , n - I} random variables is approximately Poisson with mean A = m 3/ (4n). The proof of the corresponding limit theorem (Theorem 3 below) was never published, though. A different proof was provided by Klykova in 2002 [11J . Let VIm (the birthdays) be independent and uniformly distributed on {O, ... , n - I} (the year),

o =: UCO)

:S U(1) :S ... :S UCm ) :S UCm+l)

:= n - 1

(7)

the corresponding order statistics, Slm+ 1 the induced spacings, i.e. Sk := UCk ) - UCk - l ) and C the number of collisions among those spacings, i.e. m

C :=

L

ll{S(k+l)=S(k)}'

(8)

k=l

where llA stands for the indicator function of the event A and SCI), ... , SCm+1) are the order statistics of the spacings Slm+l. The distribution of C we call birthday spacings collision distribution and we write C "-' BSC(m, n). Theorem 3. IfCn "-' BSC(mn,n) for all n E N such that m~/(4n) A then

P(Cn = k)

----+ n->oo

(k ;:::: 0).

----+ n->oo

(9)

• How does the test work? In [8J Marsaglia and Tsang suggest the following version of the Birthday Spacings Test. Choose m = 212 = 4096, n = 232 and therefore A = 4. Let the RNG generate 4096 32-bit-integers, sort them and take differences to get the spacings. Then sort the spacings and count how many times adjacent spacings are equal. This gives the number of collisions. Repeat this process 5000 times to get a realization of a sequence of supposedly independent Poisson random variables with mean A = 4. Then perform a X2-goodness-of-fit-test as follows: For k = 0, ... ,g let Nk be the number of times there were k collisions among the 5000 runs

125

and let NlO be the number of times there were more than 9 collisions. Also let Ek := 5000Pk be the expected number of Nk (under H o ), where Pk := ~~ e-.\ (k = 0, ... ,9) is the probability of a Poisson random variable taking the value k, PIa := 1 - I:~=o Pk respectively. Then

y.= .

L

10 (

Nk-Ek k=O Ek

)2

(10)

follows approximately a X2-distribution with 10 degrees of freedom. Therefore the test is failed if the p-value U := Fx2(10)(Y) is really close to 0 or 1, where Fx2 (r) denotes the (continuous) distribution function of the X2 -distribution with r degrees of freedom. Instead of performing a X2 -goodness-of-fit test on those 5000 collision counts, they could also be added, the sum being Poisson with mean 4 * 5000 = 20000. Even though it might not be feasible to calculate the corresponding p-value directly, this could be done by a normal approximation. In [10], L'Ecuyer and Simard design birthday spacings tests for testing uniformity in d dimensions by dividing the corresponding d-dimensional hypercube into hyper boxes of equal size and then enumerating them in the natural order. This kind of tests is implemented in TestU01 [6]. 3. Test Results

Good statistical properties of the sequences it produces being not sufficient, but certainly necessary, any RNG aspiring to be called good has to undergo some intensive and extensive empirical testing. In this section we present the results of applying the test batteries from the RNG software package TestUOl to a family of generators first introduced by Abundo, Accardi and Auricchi [12] and currently further being developed at the Centro Interdipartimentale Vito Volterra (CIVV) in Roma, Italy. They are also compared to the results of a few other popular generators, namely, the Wichmann-Hillgenerator [13] used in Microsoft Excel 2003, CombLec88 - a combination of two linear congruential generators used in RANLIB, CERNLIB, Boost, Octave and Scilab proposed by L'Ecuyer [14], KISS99 - a combination of four different generators designed by Marsaglia [15], the 2002 version of the Mersenne Twister generator and ISAAC, proposed by Jenkins for use in cryptography [16]. The MT19937 _ 2002 generator is described in [17], has good statistical properties and has become quite popular in software for numerical simulation (like MATLAB, for example). It is not unpredictable, though, and thus not recommended for cryptographical purposes.

126

Table 1.

Results of the test battery Crush (software package TestUOl 1.2.1).

It produces 144 p-values from 96 independent tests, thereby sampling

around 128 GByte of random bits (> 15 double layer DVDs).

I

Generator

I

Clear failures

I Suspect

(of which failed)

I

Total failed

QPdyn QPdyn-s

0 6

3 (0) 12(8)

0 14

MSExcel - 2003 CombLec88 Kiss99 MT19937 2002 ISAAC

12 1 0 2 0

7 5 2 4 3

12* 2 0 2 0

(*) (1) (0) (0) (0)

I

Note: * no follow-up testing done

Table 1 shows the results of applying the test battery Crush from the RNG software package TestUOl to QPdyn and QPdyn-s. Each test from the battery results in (at least) one p--value, a number in [0, 1]. It is interpreted according to table 2.

Table 2.

II

I Interpretation

p-value 0.01 < p < 0.99: p or (1 - p) < 10- 1 Otherwise:

Interpretion of p-values.

°:

Clear passed Clear failure Suspect behaviour, repeat test 3 times independently, if test continues to show suspect results, it is considered as failed, otherwise passed

As mentioned in section 2, Marsaglia and Tsang [8, 9] proposed three tests, that they consider to be a concentration of DIEHARD and other statistical tests used today. However, the generator QPdyn-s passes these three tests, but at the same time fails the test battery Crush quite badly, as can be seen from table 1. So this might be a starting point for comparing this Marsaglia-and-Tsang-three-tests-battery with the battery Crush for many different generators, to decide which is more stringent. Or, more likely, they will be found to be somewhat complementary in the sense that both batteries are specialized in finding certain deficiencies, which the other one does not detect. In this case an appropriate combination of both batteries should be considered.

127

4. Summary and Outlook The software package Test UOI should be considered THE STANDARD for testing RNGs. The particular version of QP-Dyn tested in the previous section passes all of the tests. But this is only the beginning. Eventually, QP-Dyn is intended to become an algorithm that automatically but somewhat randomly chooses parameters to generate not random numbers but random number generators. The idea of using computers to find good parameters for families of generators is also mentioned in section 3.7 of [18]. In a forthcoming paper we will study how to condense statistical testing in order to test QP-Dyn considered as a random RNG generator. Acknowledgements This work was supported by the Centro Interdipartimentale Vito Volterra at the Universita degli studi di Roma Tor Vergata, Italy and the European Union Research Training Network "Quantum Probability with Applications to Physics, Information Theory and Biology" . References 1. Donald E. Knuth. The art of computer programming. Vol. 2: Seminumerical algorithms. 3rd ed. Bonn: Addison-Wesley. xiii, 762 p. , 1998. 2. Michael Mascagni and Ashok Srinivasan. Algorithm 806: SPRNG: a scalable library for pseudorandom number generation. ACM Transactions on Mathematical Software, 26(3):436~461, September 2000. See correction 19. 3. George Marsaglia. A current view of random number generators. In L. Billard, editor, Computational Science and Statistics: The Interface, pages 3~ 10, Amsterdam, 1985. Elsevier Press. 4. George Marsaglia. DIEHARD: A battery of tests of randomness, 1996. 5. A. Rukhin et. al. A statistical test suite for random and pseudorandom number generators for cryptographic applications. NIST Special Publication 80022, National Institute of Standards and Technology (NIST), Gaithersburg, Maryland, USA, 2001. 6. Pierre L'Ecuyer and Richard Simard. TestU01: A C library for empirical testing of random number generators. ACM Transactions on Mathematical Software, 2007. 7. W. W. Tsang, L. C. K. Hui, K. P. Chow, C. F. Chong, and C. W. Tso. Tuning the collision test for power. In ACSC '04: Proceedings of the 27th Australasian conference on Computer science, pages 23~30, Darlinghurst, Australia, Australia, 2004. Australian Computer Society, Inc. 8. George Marsaglia and Wai Wan Tsang. Some difficult-to-pass tests of randomness. Journal of Statistical Software, 7(3):1~8, January 2002. 9. Wai Wan Tsang. Development of cryptographic random number generators.

128

10.

11. 12. 13.

14.

15. 16.

17.

18.

19.

Technical report, The University of Hong Kong, Department of Computer Science and Information Systems, August 2003. Pierre L'Ecuyer and Richard Simard. On the performance of birthday spacings tests with certain families of random number generators. Math. Comput. Simul., 55(1-3) :131-137, 2001. N. V. Klykova. Limit distribution of a number of coinciding intervals. Theory Probab. Appl., 47(1):151-156, 2002. M. Abundo, Luigi Accardi, and A. Auricchio. Hyperbolic automorphisms of tori and pseudo-random sequences. Calcolo, 29(3-4):213-240, 1992. B. A. Wichmann and 1. D. Hill. An efficient and portable pseudo-random number generator. Applied Statistics, 31:188-190, 1982. See also corrections and remarks in the same journal by Wichmann and Hill, 33 (1984) 123; McLeod 34 (1985) 198-200; Zeisel 35 (1986) 89. P. L'Ecuyer. Efficient and portable combined random number generators. Communications of the ACM, 31(6):742-749 and 774, 1988. See also the correspondence in the same journal, 32, 8 (1989) 1019-1024. G. Marsaglia. Random numbers for C: The END? Posted to the electronic billboard sci.crypt.random-numbers, January 20 1999. B. Jenkins. ISAAC. In Dieter Gollmann, editor, Fast Software Encryption, Proceedings of the Third International Workshop, Cambridge, UK, volume 1039 of Lecture Notes in Computer Science, pages 41-49. Springer-Verlag, 1996. http://burtleburtle.net/bob/rand/isaacafa.html. Makoto Matsumoto and Takuji Nishimura. Mersenne twister: a 623dimensionally equidistributed uniform pseudo-random number generator. ACM Trans. Model. Comput. Simul., 8(1):3-30, 1998. P. L'Ecuyer. Uniform random number generation. In S. G. Henderson and B. L. Nelson, editors, Simulation, Handbooks in Operations Research and Management Science, chapter Chapter 3, pages 55-81. Elsevier, Amsterdam, The Netherlands, 2006. Michael Mascagni and Ashok Srinivasan. Corrigendum: Algorithm 806: SPRNG: a scalable library for pseudorandom number generation. ACM Transactions on Mathematical Software, 26(4):618-619, December 2000. See 2

Quantum Bio-Informatics IV eds. L. Accardi, W. Freudenberg and M. Ohya © 2011 World Scientific Publishing Co. (pp. 129- 135)

ENTANGLED EFFECTS OF TWO CONSECUTIVE PAIRS IN RESIDUES AND ITS USE IN ALIGNMENT TOSHIHIDE HARA*, KEIKO SATO and MASANORI OHYA

Department of Information Sciences, Tokyo University of Science, 2641 Yamazaki, Noda City, Chiba, Japan * E-mail: [email protected]. tus.ac.jp In the previous paper,l we showed the significant improvement of sequence alignment can be done by considering the entanglement between two consecutive pairs of residues, in which we introduced a new measure defined on compound systems of two sequences which taking entanglement. In this paper, we explain the advantage of our new measure compared with the "sum of pairs" measure as the measure often-used, and we also show the performance evaluation of our algorithm against other six alignment methods. Our alignment is available at our webpage .. http://www.rs.noda.tus.ac.jp/%7Eohya-m/ ...

Keywords: Sequence analysis; Sequence alignment; Entanglement; Transition probability.

1. Introduction

According to Anfinsen's dogma,2 for a small globular protein, its threedimensional structure is determined by the amino acid sequence of the protein. There may exist intersite correlations at least for two consecutive pairs of residues. Gonnet et al. considered this possibility.3 We could improve alignment accuracy by taking into account information of the intersite correlations. In the papers,1,4 we developed the alignment method called MTRAP based on such concept. For aligning the sequences, general methods find a path that gives the minimum value to the sum of difference (the maximum value to the sum of similarity) for each residue pair between two sequences. Our method is to change the way defining the difference (so, the sum) above by introducing entanglement of two consecutive pairs of residues. We explain the advantage of our new measure compared with the "sum of pairs" measure as the measure often-used, and we also show 129

130

the performance evaluation of our algorithm against other six alignment methods. 2. A new measure taking entangled effects of two consecutive pairs in residues

First, let us establish some notations. Let [2 be the set of all amino acids, and [2* be the [2 with the indel (gap) "*": [2* == [2 u {*}. Let [[2*] be the set of all sequences of the elements in [2*. We call an element of [2 a residue and an element of [2* a symbol. In addition, let f == [2 x [2 be the direct product of two [2s and f* == [2* x [2*. Consider two arranged sequences, A = ala2 · ·· an and B = bl b2 · .. bn , both of length n, where ai, bj E[2* . We also denote the sequences by UI U2··· Un, where Ui = (ai, bi ) E f*, and we call Ui a site in the following discussion. In general, the relative likelihood that the sequences are related as opposed to being unrelated is known as the "odds ratio":

p(A;B) R(A,B) = p(A)p(B)

p(al,a2,··· ,an ;b l ,b2,··· ,bn ) p (aI, a2,··· ,an) p (b l , b2,··· ,bn )"

(1)

Here, p (a) is the occurrence probability of the given segment and p (a; b) is the joint probability that the two segments occur. In order to arrive at an additive scoring system, Equation (1) is typically simplified by assuming that the substitutions are independent of the location and there is no intersite correlations; namely, p (A) = TIp (a), p (B) = TIp (b) and p (A, B) = TIp (a, b). Thus the logarithm of Equation (1), known as the log-odds ratio, is now a sum of independent parts:

(2) where p (a; b) s (a, b) = log p (a) p (b)

(3)

is the log likelihood ratio of the symbol pair (a , b) occurring as an aligned pair to that occurring as an unaligned pair. The s (a, b) is called a score and S = (s (a, b)) is called a substitution matrix. These quantities (Equation (2) and (3)) are used to define a measure for pairwise sequence alignment 5. Here, we define a normalized substitution matrix (i.e., every element in S takes the value between 0 and 1) and define a difference of A and B.

131

Let fs :

[8 m in,8 max

l

f--+

R be a normalizing function: 8max -

fs ( x) ==

X

, 0::; fs (x) ::; 1,

(4)

8 max

== max {max{s (un, gap cost}, uEr

(5)

8 m in

== min{min{S(u n , gap cost}. uEr

(6)

Smax -

Bmin

where

Let put s (a, b) == f (8 (a, b)) for a, b E O. This s (a, b) is a normalized expression of the score 8 (a, b). By using this quantity, we define a normalized substitution matrix as M = (s (a, b)). Then a difference of A and B is defined by

(7) When the sequence A is equal to B the difference dsub (A, B) has a minimum value O. One of the essential assumption for the above approach (using a sum of independent parts as a difference of A and B) was the induction of the occurring probability. We could take more informative approach by including the intersite correlations. Crooks et al. tried one of such an approach 6. They introduced a measure for two sequences based on a multivariate probability approximated by using the intersite relative likelihood. But, they concluded that their approach is statistically indistinguishable from the standard algorithm. We feel that their measure (equation (4) in their paper) is different from ours. To introduce their measure, they defined a type of joint probability. However it can not be a probability, because their quantity is the multiplication of likelihood "ratios", so it goes beyond more than 1. Moreover, we think that the intersite relative likelihood may not describe the difference of sequence A and B. Under an assumption that each site of the sequences has Markov property, we propose a new measure for two sequences by adding a transition effect and its weight E (a degree of mixture):

Rour (A, B)

= R (A, B)l-c R t (A, Bt ,

(8)

where n-l

Rt(A, B) ==

II P (Ui+1 \ Ui). i=l

(9)

132

Here we introduce a normalized transition i (Ui' UH1) called "Transition Quantity", in order to simplify the equation. Let i (Ui' uHd be a normalized transition defined as

where

it (x; u)

i (Ui' uHd == it (t (Ui' uHd ; Ui) ,

(10)

t (Ui' Ui+l) == logp (Ui+l \ Ui) ,

(11)

is a normalizing function:

it (x; u) = {

-x if x> 0 maxvEr* {-t (u, v)}' 1, otherwise

(12)

By using the above quantity, a difference of A and B representing the "intersite transition" is defined as n-1

dtrans (A, B)

=

L

i (Ui' Ui+l) .

(13)

i=l

Consequently, we define a difference measure for two sequences by combination of two differences dsub and dtrans: dMTRAP

(A, B)

=

(1 - c)

d sub

(A, B)

+ cdtrans (A, B).

The mathematical details can be found in the paper

(14)

4.

3. Evaluation We compared the performance of MTRAP to those of the most often used six methods: ClustalW2, MAFFT, TCoffee, DIALIGN, MUSCLE and Probcons. The details of these nine methods are: (1) ClustalW2 7 ,8, a typical progressive multiple alignment method; (2) MAFFT ver. 6 9, a fast method with Fourier transform algorithm; (3) TCoffee ver. 5.31 10, a heuristic consistency-based method that combines global and local alignments; (4) DIALIGN ver. 2.2 11 , a method with segment-segment approach; (5) MUSCLE ver. 3.7 12, a method with Log-Expectation algorithm and (6) Probcons ver. 1.12 13, a probabilistic consistency-based method. These programs without MAFFT used their default parameters and MAFFT used "L-IN-i" strategy mode. To measure the accuracy of each method, we used three different databases: HOMSTRAD (version November 1, 2008) 14,15, PREFAB 4.0 12 and BAliBASE 3.0 16. These are the databases of structure-based alignments

133

for homologous families. We used the all 630 pairwise alignments obtained from the HOMSTRAD for pairwise alignment tests , and used the all 1031 multiple alignments obtained from this database for multiple alignment tests. We also used the all 1682 protein pairs obtained from the PREFAB 4.0 for pairwise alignment tests. The BAliBASE 3.0 contains 5 different reference sets of alignment for testing multiple sequence alignment methods. We used the BBS sets included in the references 1,2,3 and 5. The BBS sets are described as being trimmed to homologous regions. In order to avoid using the same dataset for training and test, We estimated the transition quantity by using the superfamilies subset from the dataset SABmark, which is described in the section "Estimation of the Transition Quantity" . We also used this dataset for optimizing the parameters Alignment accuracy was calculated with the Q (quality) score 12. The Q score is defined as the ratio of the number of correctly aligned residue pairs in the test alignment (i.e., the alignment obtained by a specified algorithm such as MTRAP, Needle, etc.) to the total number of aligned residue pairs in the reference alignment. When all pairs are correctly aligned, the score have a maximum value 1, and when no-pairs are aligned the score have a minimum value o. This score has previously been called the SPS (Sum of Pairs Score) 17 or the developer score 18. Let us redefined this score in our notations. Let Ai (i = 1, ... , N) indicates the ith sequence of the reference alignment with length L, and let aik E [2* indicates the kth symbol in the sequence A i . When aik =I- *, it is important to find the number of the site in the test sequence corresponding to the symbol aik, whose numbers are denoted by nik. When aik = *, put n i k = 0 (i = 1, ··· , N). Then the Q score is given as N-l

L

Q score

=

N

= ,Y

L:l.a i k,aJk8nik ,n j k

i=1 j=i+l k=1 --:'N=----I--:-N=------::-L-----

L

L:l. x

L

L L

{I,

L L

L:l.aik , a j k

i=l j=i + l k = l

x 0, x

=I- * and y =I- * . = * or y = *

4. Results

We compared MTRAP with six different alignment methods by using all 1682 protein pairs of PREFAB 4.0 and all 630 protein pairs of HOMSTRAD. We used GONNET250 matrix with the MTRAP. The similar-

134

ity between the test alignment (sequence alignment by each method) and the reference alignment (obtained from PREFAB 4.0 or HOMSTRAD) was measured with the Q score. Suppose as usual that the reference alignment is the optimal alignment, the results of PREFAB 4.0 (Table 1) and those of HOMSTRAD (Table 2) indicate that our method works well compared with other methods. Our method achieves the highest ranking compared with all other methods except only one range 30-45%. Especially for the identity range 0-15%, MTRAP is 4 cv 5% accurate than the 2nd ranking method. For the identity range 30-45% of HOMSTRAD, Probcons performs slightly better (cv 1%). Table 1.

Average Q scores on the PREFAB 4.0 database

Method 0-15%(212) 0.248 0.170 0.133 0.205 0.199 0.204 0.198

MTRApa MAFFT DIALIGNb MUSCLE ClustalW2 Probcons TCoffee

PREFAB 4.0 15-30%(458) 30-45%(74) 0.674 0.877 0.860 0.671 0.556 0.814 0.867 0.632 0.859 0.644 0.647 0.875 0.642 0.872

All(1682) 0.615 0.568 0.518 0.581 0.586 0.590 0.585

CPU 120 200 100 35 70 120 180

Note: The average Q scores of four testing datasets with different identity ranges on PREFAB 4.0 are shown. The number in parentheses denotes the number of alignments in each sequence identity range. For each sequence identity range, the best scores are in bold. CPU is the total computing time for all alignments in seconds. aMTRAP uses GONNET250 substitution matrix. bDIALIGN reported critical errors for some testing data. Therefore, the scores of DIALIGN were calculated by the partial testing data.

Table 2.

Average Q scores on the HOMSTRAD database (Pairwise only)

Method MTRApa MAFFT DIALIGN b MUSCLE ClustalW2 Probcons TCoffee

0-15%(25) 0.412 0.309 0.216 0.337 0.313 0.344 0.341

HOMSTRAD (Pairwise only) 15-30% (207) 30-45%(173) All(630) 0.659 0.879 0.819 0.610 0.863 0.796 0.760 0.546 0.825 0.625 0.868 0.802 0.619 0.867 0.800 0.650 0.884 0.816 0.634 0.872 0.809

CPU 45 60 35 15 25 50 70

Note: The average Q scores offour testing datasets with different identity ranges on HOMSTRAD are shown. The notations are the same as Table 1.

135

5. Conclusion We indicated that the alignment implementing our new measure, introducing entangled effects of two consecutive pairs in residues, leads to a significant increase in alignment accuracy to other six methods, and this is especially apparent in low identity range. We will apply our new technique to several methods studying life from sequences, such as multiple alignment, motif finding and phylogenetic analysis, where it is considered that the residue substitutions in a sequence are independent of the location.

References 1. T. Hara, K. Sato and M. Ohya, QP-PQ: Quantum Probability and White Noise Analysis (Quantum Bio-Informatics III) 26, 443 (2010). 2. C. B. Anfinsen, Science 181, 223(Jul 1973). 3. G. Gonnet, M. Cohen and S. Benner, Biochemical and Biophysical Research Communications 199, 489 (1994). 4. T. Hara, K. Sato and M. Ohya, BMC Bioinformatics 11, p. 235 (2010). 5. S. Altschul, 1. Mol. Bioi. 219, 555 (1991). 6. G. Crooks, R. Green and S. Brenner, Bioinformatics 21, p. 3704 (2005). 7. J. D. Thompson, D. G. Higgins and T. J. Gibson, Nucleic Acids Res. 22, 4673(Nov 1994). 8. M. A. Larkin, G. Blackshields, N. P. Brown, R. Chenna, P. A. McGettigan, H. McWilliam, F. Valentin, 1. M. Wallace, A. Wilm, R. Lopez, J. D. Thompson, T. J. Gibson and D. G. Higgins, Bioinformatics 23, 2947(Nov 2007). 9. K. Katoh, K. Misawa, K. Kuma and T. Miyata, Nucleic Acids Res. 30, 3059(Ju12002). 10. C. Notredame, D. G. Higgins and J. Heringa, 1. Mol. Bioi. 302, 205(Sep 2000). 11. B. Morgenstern, Bioinformatics 15, 211(Mar 1999). 12. R. C. Edgar, Nucleic Acids Res. 32, 1792 (2004). 13. C. Do, M. Mahabhashyam, M. Brudno and S. Batzoglou, Genome Research 15, p. 330 (2005). 14. K. Mizuguchi, C. M. Deane, T. L. Blundell and J. P. Overington, Protein Sci. 7, 2469(Nov 1998). 15. L. Stebbings and K. Mizuguchi, Nucleic acids research 32, p. D203 (2004). 16. J. D. Thompson, P. Koehl, R. Ripp and O. Poch, Proteins 61, 127(Oct 2005). 17. J. Thompson, F. Plewniak and O. Poch, Nucleic Acids Res 27,2682 (1999). 18. J. Sauder, J. Arthur and R. Dunbrack Jr, Proteins Structure Function and Genetics 40, 6 (2000).

This page intentionally left blank

Quantum Bio-Informatics IV eds. L. Accardi, W. Freudenberg and M. Ohya © 2011 World Scientific Publishing Co. (pp. 137-143)

THE PASSAGE FROM DIGITAL TO ANALOGUE IN WHITE NOISE ANALYSIS AND APPLICATIONS

TAKEYUKI HIDA Professor Emeritus of Nagoya University and Meijo University

AMS 2000 Subject Classification: 60H40 White Noise Theory

1. Prologue One of the basic idea of white noise analysis is Reduction of random phenomena (cf. [7]), so that the given system is made to be a function of idealized elemental random variables (abbr. i.e.r.v.), for example

B(t), white noise and

Fu, elemental Poisson system. More precisely, we may say that it would be fine if random complex phenomena can be express as a function of elemental random variables, so that they are ready to be analyzed and that the theory would be developed in line with stochastic analysis. As soon as we come to applications of the theory to actual problems, we need to approximate the i.e.r.v. by a system of ordinary independent random variables. Naturally follows approximation of the analysis.

Motivations Examples of the motivation of our study. i) Biological phenomena. There is involved fluctuation which is considered to be Gaussian. Behind it, we see a Gaussian process that can be reduced to white noise. 137

138

ii) We often meet probability distributions which have long tailor fat tail, sometimes called fractional power distribution. They are not considered to be Gaussian. Such a distribution may appear as that of a stable stochastic process evaluated at some instant. The process admits the Levy decomposition, or the Levy-Ito decomposition, theoretically. Each component is an infinitesimal Poisson process and even it is elemental. In each case, efficient method of application requires suitable method of approximations. Before we come to actual methods, we shall provide some considerations on a system of independent random variables which come from the effect of reduction. iii) The third motivation has somewhat different flavor. Good examples are stable distributions with some exponent. It appears as a distribution of a stable stochastic process evaluated at some instant. There a duality between time and Poisson components via the Levy decomposition of a stable process.

2. An i.i.d. random variables as a representation of parameter set Probabilistic properties of a sequence of i.i.d. (independent identically distributed) random variables may be discussed under the understanding that the sequence is a representation of the parameter set used as index of a sequence of independent random variables. We assume the sequence of i.i.d. random variables is Gaussian.

Case 1. Digital We have X = {Xn' n E N}, where N is the set of positive integers. The probability distribution m is the direct product of count ably many standard Gaussian distributions. The complex Hilbert space L2 = L 2(ROO, m) involving square integrable functions of the form f(X n , n E N) is separable, where Hermite polynomials in X~s form a complete orthonormal base of L2. Differential operators an is defined as follows:

akf(Xn,n

E

a

N) = -a f(xn,n Xk

E

N)lxn=x n

·

It is a derivation and, in fact, it is an annihilation operator. Its adjoint operator can be defined in the usual manner. The polynomials in the

az

139

annihilation and creation operators are defined. In particular, the Levy Laplacian ~i acting on L2 is given as follows: 1 L...l.L =hm N Ad.

N ""::>2

LUk' 1

Its domain is dense in L2.

Case II. Analogue II. 1) Analogue and separable

Gaussian case The time parameter space is taken to be T = [0, 1] to fix the idea. Let B(t), t E T, be a Brownian motion from which white noise 13(t) is defined, Formally speaking the 13(t)'s are independent system of idealized random variables. The probability distribution JL is introduced on the measurable space (E*, B), where E* is a space of generalized functions on R1 and where B is the sigma-field generated by the cylinder subsets of E*. Proposition 2.1. The measure space (E*, B, JL) is an (abstract) Lebesgue space where the calculus can be done. As a result, we have the Hilbert space (L2) = L2(E*, JL) which is, of course, separable and on which analysis can be carried on. Functionals in (L2) that we shall be concerned with are of the form

cp(13(t), t

E

(1)

T),

which will be simply written by cp(13). Approximations can be done as follows: Take a partition ~n = {~k = [k/2 n , (k + 1)/2 n ]}, k = 0 ~ k ~ 2n Then, we have two ways for the approximation to white noise. tends to 13 (t) as ~ nk ----+ t in linear white noise functionals. ii) Use of c"B ~ i)

c"B c,,~

Hel-1)'

-

I}.

the space of generalized

Poisson case The parameter set is taken to be (0, 00 ). For each u we associate an infinitesimal Poisson process Fu , u ETa, where To = (0, (0). As for the case of 13(t), Fu itself is not an ordinary random variable, but it can be a generalized random variable as is discussed in the next section.

140

II. 2) Analogue and non separable,

Let X = {Xt, t E Rl} be a system i.i.d. ordinary random variables, each of which is subject to the standard Gaussian distribution N(O, 1). Then, the probability distribution v = IItERlLt, where ILt is the distribution N(O, 1). Proposition 2.2. The probability measure space (RR, IItBt , v) is not an abstract Lebesgue space . With this property we see that the space L2(RR, v) is quite different from a white noise space, and it is not useful in the calculus of random functionals. 3. Poisson noise i) Background. We are going to propose a new direction of the treatment of random functions which are expressed as functionals of Poisson noise, As was briefly mentioned in the motivation, we are asked to introduce a method of analyzing functionals of Poisson noise. An urgent request has come from the study of random phenomena the probability distribution of which is of fractional power or of long (fat) tail. Standard distribution of this kind is the stable distribution. Suppose we are suggested to approximate the given fractional power distribution by a stable distribution. Then the next step is to determine the power CY, which is one of the significant characteristics of the distribution. To this end, one may think of the least square method in statistics. But it is not recommended by many important reasons. Here we do not go into details on this problem. A reasonable method uses the evaluation of the area given by the histogram of the data over intervals far from O. Even the power CY is obtained, we can not investigate the structure of the given random phenomena. In reality, we have determined only onedimensional distribution, it does not provide enough information for the determination of the random phenomena in question. ii) What we can do is that we try to discover the history of the phenomena, together with its environment. A favorable case is that the given stable distribution can be regarded as what is evaluated at some instant from a stable stochastic process. One may think that because of the circumstance of the environment, the observed data might have come from the accumulation of independent data

141

obtained in the past. Such a case, we say that the observed data can be embedded in a stable stochastic process. One may think it is too favorable, but we know actual data has such a history. iii) Steps of the analysis. Once we can find favorable stable process, which is a Levy process. We therefore know the famous Levy decomposition. In the present case, there is no Gaussian component and constant term can be ignored. We, therefore have compound Poisson processes. To come to the next stage, we must make a few important remarks. a) The Levy decomposition says that the stable process just determined is consisting of many (actually, continuously many) independent Poisson type processes. (We call Poisson type process, if the process has the same distribution as a Poisson process up to constant), although they are infinitesimal. We need numerical technique of discriminating those Poisson type processes according to different jumps. In other words, we need suitable method of approximation to come to the actual stsps. b) Having obtained a single component of Poisson type process, we must fix the time, say t = 1, to have a system of idealized elemental random variables. After that we can imitate the steps of Gaussian case in order to discuss nonli9near functionals of them. c) Each component of the stable process is a Poisson type process which is parametrized by u the amount of the jump. If the jump is different, then they are mutually independent. We are now given a so-called generalized stochastic process with independent values at every point in the sense of Gel'fand. d) The self-similarity of a stable stochastic process may be rephrased as the duality between the time t and the amount u of the jump. In the analysis of Poisson noise functionals, this fact should be taken into account. 4. Calculus of Poisson noise functionals Noise, in this section, does not mean the time derivative, but means derivative in u the space parameter of Poisson type processes. The parameter u denotes the amount of jump.

142

We are going to show the steps of the calculus in question, rather quickly. Details with proofs will be reported in the separate paper [6]. (1) We restrict the time interval to a finite interval I = [E, K]. A Poisson type process with jump as high as u, with u E I, is denoted by Pu(t), the intensity of which is denoted by >.(u) > O. The characteristic function of Pu (1) is given by

The sum of independent PUk (1), k function of the form

= 1,2"" ,n, has the characteristic

Finally we come to the expression of the form

cp(z) = exp[j (e izu

l)>.(u)du].

-

More generally, we may replace >.(u)du with a measure d>.(u). Now we must assume a condition on the intensity measure d>.(u) so that the integral converges and has meaning. Namely, we assume

j

d>.(u) <

00.

(2) Probability measure on u-space. Consider the characteristic function

cp(z)

=

exp[j (e izu

-

l)d>.(u)].

The integral in the above expression is expressed in the form

143

1

eiZUd)"(u)

+ canst,

Z

E RI.

Noting that Z can vary in RI arbitrarily, we can make the intensity measure to be the delta measure, say bUD. This means that one can pick up an elemental (atomic) Poisson process with jump uo, let it be denoted by

F'(uo) (3) The last question is how to carryon approximation. It is now the time to remind the notion of (t, u)-set introduced by P. Levy [9] and also a formal expression of a compound Poisson process lim

1

p->oo p>lul>l/p

(F'(u) -

~ )dn(u), 1

+u

where dn(u) is the Levy measure. See [1] Section 3.2. In the present setup, the approximation of single Poisson component does correspond to the approximation of the delta measure on u-space. It is in line with the passage from digital to analogue.

References 1. T. Hida, Stationary stochastic processes. Princeton University Press. 1970. 2. T. Hida, Analysis of Brownian functionals. Carleton Math. Lecture Notes no. 13, Carleton University, 1975. 3. T. Hida, Brownian motion. Springer-Verlag. 1980. 4. T. Hida and Si Si, An innovation approach to random fields. Application of white noise theory. World Scientific Pub. Co. 2004. 5. T. Hida and Si Si, Lectures on white noise functionals. World. Sci. Pub. Co. 2008. 6. T. Hida, Si Si and Win Win Htay, A noise of Poisson type and its gdneralized functionals, preprint (submitted). 7. J.L. Lions, The earth, planet, the role of mathematics and supercomputers. (original in Spanish). Spanish Inst. 1990. 8. Si Si, Effective determination of Poisson noise. IDAQP 6 (2003), 609-617. 9. P. Levy, Theorie de l'addition des variables aleatoires. Gauthier-Villars, 1937, 10. P. Levy, Processus stochastiques et mouvement brownien. Gauthier-Villars. 1948. 2eme ed. with supplement 1965. 11. P. Levy, Problemes concrets d'analyse fonctionnelle. Gauthier-Villars. 1951. 12. W. Feller, An introduction to probability theory and its applications. vol.1. Wiley, 1950. Chapt. in particular Chapt. III. 13. I. Ojima, Levy process and innovation theory in the context of Micro-Macro duality, Proc. The 5th Nagoya Levy Seminar. 2006. 65-69.

This page intentionally left blank

Quantum Bio-Informatics IV eds. L. Accardi, W. Freudenberg and M. Ohya © 2011 World Scientific Publishing Co. (pp. 145-156)

REMARKS ON THE DEGREE OF ENTANGLEMENT

DARIUSZ CHRUSCINSKIl, YUJI HIROTA 2 , TAKASHI MATSUOKA 3 AND MASANORI OHYA 4 1 Institute of Physics, Nicolaus Copernicus University 2 Quantum Bio-Informatics Center, Tokyo University of Science, 3 Department of Business Administration and Information, Tokyo University of Science, Suwa, 4 Department of Information Science, Tokyo University of Science We analyze a measure of quantum entanglement called degree of entanglement (DEN). It is shown how DEN behaves for well known classes of bipartite states. Moreover, we compare DEN for quantum states having the same marginals. Contrary to naive expectation it is shown that separable state might possesses stronger correlation (measured by DEN) than an entangled state. Keywords: Quantum entanglement, Quantum entropy

1. Introduction

In recent years, due to the rapid development of quantum information theory 1 the necessity of classifying entangled states as a physical resource is of primary importance. It is well known that it is extremely hard to check whether a given density matrix describing a quantum state of the composite system is separable or entangled. There are several operational criteria which enable one to detect quantum entanglement (see e.g. 2 for the recent review). The most famous Peres-Horodecki criterion is based on the partial transposition: if a state p is separable then its partial transposition pr = (ll ® T)p is positive. States which are positive under partial transposition are called PPT states. Clearly each separable state is necessarily PPT but the converse is not true. We stress that it is easy to test wether a given state is PPT, however, there is no general methods to construct PPT states. There are several measure of entanglement 2. However, there is no universal measure which shows that the problem of quantifying quantum entanglement can not be reduced to computing a single quantity. Moreover, 145

146

various measures are not compatible: if EI and E2 are two measures, then one can find two states p and pi such that EI (p) < EI (pi) but E2 (p) > E2(p'). It shows that various measures shows different aspects of quantum correlations. In the present paper we analyze a particular measure called degree of entanglement (DEN) and based on the mutual entropy.1O,1l,18 As other measures DEN uniquely characterized the entanglement of pure states. However, it gives only a partial answer for mixed states. This paper is organized as follows: in Section 2 we introduce basic properties of DEN. Sections 3 and 4 provide several examples of quantum states for which one easily compute DEN. Moreover, since they possess the same marginal states (maximally mixed) one can compare the corresponding degree of entanglement. Surprisingly, it turned out that separable state can have stronger correlation (with respect to DEN) than an entangled state. Final conclusions are collected in the last section.

2. The Degree of Entanglement We begin our discussion by recalling the definition of quantum entanglement. Throughout this paper, Hilbert spaces are assumed to be finite dimensional. If is the state on the Hilbert space HI ® H 2 , then Tr1i2e denotes the partial trace of with regard to H 2 .

e

e

Definition 2.1. Let H be a tensor product Hilbert space of two Hilbert spaces HI and H2 and B(H) the set of bounded operators on H.

e

(1) A state

on B(H) is said to be separable if there exist finite sequences of density operators {pJt'-,1 C B(Hd and {O'dt'-,l C B(H 2) such that

(1) with

"\,,N ~2

(2) A state

A2 = 1 and A > 0 (Vi = 1 ... N) 1,

-

" .

e on B(H) is said to be entangled if it is not separable.

The classical example of an entangled pure state is given by w el - el ® eo) - Bell state of two qubits.

=

Jz (eo ®

Definition 2.2. Let HI, H2 be Hilbert spaces and e a density operator on HI ® H2 with marginal states p = Tr1i2e and 0' = Tr1il e. The DEN for e

147

with regards to p, a is defined by the following formula 1

D(() : p, a) = 2{S(P)

+ S(a)} - Ie(p, a),

where Ie (p, a) is the mutual entropy for () : Ie(p, a)

(2)

= tr()(log () -log p (>9 a).

In terms of von Neumann entropy, Ie (p, a) can be rewritten in the form + S(a) - S(()). Therefore, one obtains finally

Ie(p,a) = S(p)

1

D(() : p, a) = S(()) - 2{S(P)

+ S(a)}.

(3)

We will often use this form to calculate DEN in this and all subsequent sections. As an example let us calculate DEN for the singlet state w. The marginal states WI = W2 = ~h and hence one finds D(w : Wl,W2) = -log2 < O. Actually, one has the following Theorem 2.1. M. Ohya and T. Matsuoka 18 Let () be a pure state with marginal states p, a. Then, we have the following classification:

(1) () is separable if and only if D(() : p, a) = 0; (2) () is entangled if and only if D(() : p, a) < O. According to the above theorem, DEN gives us the necessary and sufficient condition for the separability of pure states. For mixed states one has 3 ,10,1l Theorem 2.2. Assume that the compound state () is a mixed state. If () is separable, then D(() : p, a) > O. Now, we compare quantum bipartite states with respect to DEN. Definition 2.3. Let ()1, ()2 be states which have common marginal states p, a. The state ()1 possesses stronger correlations than ()2 if the following inequality holds:

D(()l : p,a) < D(()2 : p,a).

(4)

The less value of DEN one gets, the stronger correlations one has. Here a natural question arises: Problem Let ()1 and ()2 be compound states having the common marginal states p, a. Assume that D(()l : p, a) < D(()2 : p, a). If ()2 is entangled, is ()1 entangled as well? In what follows we show that it is not the case.

148

3. DEN for 2-qudit states 3.1. Circulant states We start this section by recalling the definition of circulant state. 12 (see also Refs. [13, 14]). Consider the finite-dimensional Hilbert space Cd (d E N) with the standard basis {eo, el, ... ,ed-d. Let ~o be the subspace of Cd 0 Cd generated by ei 0 ei (i = 0, 1, ... , d - 1) : ~o

= span{ eo 0 eo, el 0 el, ... ,ed-l 0 ed-I}.

(5)

For any non-negative integer 0:, we define the operator sa on Cd by

ek

f---+

ek+a(mod d),

(k = 0,1, ... , d -1),

and denote by ~a the image of ~o by Id 0 sa : ~a = (Id 0 sa)~o. It turns out that ~a and ~;3 (0: =I- {3) are orthogonal to each other and

Cd 0 Cd ~ ~o EB ~l EB ... EB ~d-l.

(6)

This decomposition is called the circulant decomposition. Let Po, PI' ... , Pd-l be positive d x d matrices with entries in C which satisfy

tr(po For each matrix Pa (0: p~ on (C d )®2 as

+ ... + Pd-l) = 1.

(7)

= 0,1,··· ,d - 1), we define the new linear operator d-l

p~ =

L

(ei' Paej leij 0 sa eij (S")*,

(8)

i,j=O where eij means leil(ejl. Since Skeij(Sk)* be also written as

= ei+k,j+k, we note that

p~ can

d-l

p~

=

L

(ei' p"ej leij 0 eHa,j+a·

(9)

i,j=O One can easily check that the sum of these operators d-l

p" = LP~

(10)

,,=0

defines a density matrix on (C d )®2. For further details of circulant states we refer to Ref. 12.

149

Let us consider a particular example of a circulant state for d

= 3:

1 (111) Po = A lII , 111 where

(12) and

E

> o. It can easily be checked that tr(po + PI + P2)

ti Po

1

= A

100010001 000000000 000000000 000000000 100010001 000000000 000000000 000000000 100010001

,

ti _ E PI - A

= 1. One finds

000000000 010000000 000000000 000000000 000000000 000001000 000000100 000000000 000000000

(13)

and

ti _ liE P2-A

000 000 000 000 000 000 001 000 000 000 100 000 000 000 000 000 000 000 000 000 000 000 000 010 000 000 000

(14)

Finally, one obtains the following family of circulant states

10 0 0 00 liE 00 0 10 0 00 0 00 0 00 0 10 0

oE

0 100 0 1 0 000 0 0 o 000 0 0 liE 0 0 0 0 0 o 100 0 1 0 OEO 0 0 0 00 E 0 0 0 00 o liE 0 0 10 001

(15)

150

0.8

0.7

0.6 0.5

0.4

0.3

0.2

0.1

x Figure 1.

The graph of D EN for

(/1 (x)

The marginal states p, (J of 8 1 (c:) can be calculated as

p = (J =

1

3 (eoo + ell + e22)

(16)

Therefore, we have

D (81 (c:): p,(J )

=

-A3

[ 3 1 3/c: +log3 J , log A + clog 3c: j[ + ~logA

(17)

with A defined in (12). Actually, one can classify the state of 8 1 (c:) by the value of c: (see Ref. 17). Theorem 3.1.

(1) 81 (c:) is separable iff c: = 1; (2) 81 (c:) is both PPT and entangled for c:

cJ l.

The corresponding graph of DEN for 81 (c:) is shown in Fig. 1. The maximal value corresponds to c: = 1 and is given by D (8 1 (1) : p, (J) = ~ log 3 ~ 0.7324.

151

3.2. Horodecki state

Let us consider another example of circulant states introduced in Refs. 15, 16: (0 ~ 0: ~ 5),

(18)

where

1/J= 8+

1 J3(eo0eo

+

e10 e 1

+ e20 e2),

(19)

1

= "3 (eoo 0 ell + ell 0 e22 + e22 0 eoo),

8- =

1

"3 (ell 0

eoo

+

e22 0 ell

+

eoo 0 e22) ,

(20) (21)

and hence 0 0

0 0 0

2 21

0 <> 0 21 0 0 5-<> 0 0 ----:2l 0 0 5-<> 0 0 0 ----:2l 0 0 2 2 0 0 21 0 21 0 <> 0 0 0 0 0 21 0 0 0 0 0 0 0 0 0 0 0 0 2 2 0 0 0 21 21 0 221

0

0 0 0 0 0 0

0 0 0 0 0 0 0

2 21

0 0 0 2 21

(22)

0 <> 0 21 5-a 0 ----:2l 0 2 0 0 21

The marginal states p and (J are the same as (16). The von Neumann entropy of 82 (0:) is calculated to be 2 2 0: 0: 5-0: 5-0: 8(8 2 (0:)) = -7 log 7 -7 log 7 - -7- log -7-

5

+ 7 log 3.

(23)

Therefore, we have

D(8 2 (0:): p,(J)

=

2 2 0: 0: 5-0: 5-0: 2 -7 log 7 -7log7 - -7-log-7- -7log3.

(24)

As in the case of the circulant state 8 1 (E), it is known that the state 82 (0:) can be classified by the values of 0: (see Refs. [15, 16]). Theorem 3.2.

(1) 82 (0:) is separable if and only if 0: E [2,3]; (2) 82 (0:) is both entangled and PPT if and only if 0: E [1,2) U (3,4]; (3) 82 (0:) is not PPT if and only if 0: E [0,1) U (4,5].

152

0.8

0.75 0.7

1:::

1;' 0.65

'" g;

0.6

~

i

0.55

C')

OJ o

~

0.5

c:: 0.45 X .;,

f

0.4

X

0.

0.35

OJ o

~

~

C>

o

0.3 0.25

2

3

2.5

~

4

3.5

4.5

5

x

Figure 2.

The graph of DEN for (l2(X)

Now, since 81(10) and 82 (a) have common marginal states, we can compare DEN for them. One has for example

D(8 1 (1) : p,O") ~ 0.7324 < D(8 2 (3.1) : p,O") ~ 0.7587.

(25)

Note, however, that 81 (1) is separable while 82 (3.1) is entangled. This example gives negative answer to our original question. The corresponding graph of DEN for 82 (a) is shown in Fig. 2. 4. Bell diagonal states

In this section, we analyze Bell diagonal states for d = 3 (see Refs. [4, 5, 6, 7, 8, 9]). Consider the Hilbert space 1t =

re 3

with the standard basis

{eo, e1, e2 }. We set

(26) and define flk,e for any k, C (0 :S k, C :S 2) as

flk ,e = (Wk ,e ® 13)flo,o ,

(27)

153

where Wk,e means the circle action given by

(i=0,1,2).

(28)

Finally, we define

e( a, p) =

P( 0

l-a-p 9 I3 0 I3 + aIOo,o) (0 0 ,0 1 + 2"

1 1,0) (0 1 ,01

+ 10 2,0) (0 2 ,0 1) (29)

Note that e( a, p) can be written in the form 1+2(0:+(3) 9

0 O 0 20:-(3 -6-

0

0 0

1-0:-(3 -g-

1-0:-(3

0 0

0

0 0

0 0

0 0

20:-(3 -6-

0

0 0

0 0 0 0

Note that tr e(a, p)

=

20:-(3 -6-

20:-(3 -6-

0 0 0

0 0 0 0

0 0 0

0 0 0

0

0

1+2(0:+(3) 9

0

0

0 0

200-(3 -6-

0 1-00-(3 -g-

0 0

0

1+2(00+(3) 9

0

1-00-(3

0 0

0 0

0

0

200-(3 -6-

0

0

0 0 0 0

1 and the eigenvalues of e(a, p) are given by

l-a-p 9

-2a + 7p + 2 18

8a -

p+ 1

(30)

9

Therefore, e(a, p) defines a state if and only if the parameters a, p satisfy

a+p:::; 1,

2a -7p:::; 2,

-8a + p:::; 1.

(31)

On the other hand, let us ask for the condition when e(a, p) can be positive under partial transpose. The partial transpose Te(a, p) of e(a, p) is given by 1+2(00+(3) 9

0

0

0

1-00-(3 -g-

0

20:-(3 -6-

0

1-0:-(3 -g-

0

006

0

1-00-g-

0 0 0

0 0 0 0

0 0

O

0

0

0 0

O O

0 0 0 0

0 0 0 0

0 0 200-(3

0 0

1+2(0:+(3) 9

0

0

0 0 0

0

0 0 0 0

0 0 0 0

0

1-00-(3

20:-(3

0 0

200-(3 -6-

1-00-(3 -g-

0 0 0 0

0

0

0

1+ 2(00+(3) 9

0

154

From this one can check that the trace is equal to 1 and the eigenvalues are

1+2(a+,8)

-8a +,8 + 2

9

18

4a - 5,8 + 2 18

(32)

Hence, the PPT condition holds for a, ,8 such that

a

1

+ ,8 ?: -"2'

8a - ,8 ::; 2,

-4a + 5,8 ::; 2.

(33)

On the set which consists of a, ,8 satisfying both (31) and (33), the state is either separable or bound entangled. However, it was shown 7 that for this class all PPT states are separable. Let us consider for example the line ,8 = 3/ 5. One has: B(a , 3/ 5) is entangled if and only if

a E [0,1/4) U (13/40,2/5] ,

(34)

and it is separable iff

a

E

[1 / 4,13/ 40] .

(35)

The marginal states p and a are calculated to be the same as (16). Hence we obtain DEN for e(a, 3/5)

(2 - 5a)_ 31 - 10a l (31-lOa) / 5 ) .. p, a ) -_ lOa-4 ( ( DBa,3 15 l og 45 45 og 90 - 40a + 2 1og (40a + 2) - 1og 3 . 45 45

(36)

By a simple calculation, it easily be verified that D(e(a, 3/5) p, a) is monotonically decreasing if a E [1/20, 2/5). Hence, the values of DEN for a E [1 / 20,1/4) are greater than the ones for a E (1 / 4,13/40) (see Fig. 3). This gives also the negative answer to our original question. 5. Conclusions We provided several examples of bipartite quantum states for which one can easily compute DEN. Moreover, since they possess the same marginal states (maximally mixed) one can compare the corresponding degree of entanglement. It turned out that separable state can have stronger correlation (with respect to DEN) than an entangled state. This observation is inconsistent with the conventional understanding of quantum entanglement. Consequently, we propose that the meaning of DEN should be changed to express the intensity not of entanglement but of correlation. The details will be discussed in the forthcoming paper 19.

155

0.7 0.6 0.5 0.4 0.3 0.2 0.1

0 ·0.1

0

0.05

0.1

0.15

0.2

0.25

0.3

0.35

0.4

x Figure 3.

The graph of DEN for B(x, 3/5)

Acknowledgments

This work was partially supported by the Polish Ministry of Science and Higher Education Grant No 3004/B/H03/2007/33.

References 1. M. A. Nielsen and I. L. Chuang, Quantum computation and quantum infor· mation, Cambridge University Press, Cambridge, 2000. 2. R. Horodecki, P. Horodecki, M. Horodecki and K. Horodecki: Quantum en· tanglement, Rev. Mod. Phys. 81 (2009). pp 865-942. 3. L. Accardi, T. Matsuoka, M. Ohya:Entangled Markov chains are indeed en· tangled, Infin. Dimens. Anal. Quantum Probab. Relat. Top., Vol. 9 (2006), pp 379-390. 4. R. A. Bertlmann, and Ph. Krammer: Simplex of bound entangled multipartite qubit states, Phys. Rev. A 78(2008), 10pp. 5. R. A. Bertlmann, and Ph. Krammer: Geometric entanglement witnesses and bound entanglement, Phys. Rev. A 77, 024303 (2008), 4pp. 6. B. Baumgartner, B. Hiesmayr, and H. Narnhofer: State space for two qutrits has a phase space structure in its cone, Phys. Rev. A 74 (2006), l4pp.

156

7. B. Baumgartner, B. Hiesmayr, and H. Narnhofer: A special simplex in the state space for entangled qudits, J. Phys. A: Math. Theor. 40, 7919 (2007). 8. B. Baumgartner, B.C. Hiesmayr and H. Narnhofer: The geometry of biparticle qutrits including bound entanglement, Physics Letters A, 372 (2008), pp 2190-2195. 9. D. Chruscinski, A. Kossakowski, T. Matsuoka, K. Mlodawski, A class of Bell diagonal states and entanglement witnesses, to apper in Open Systems and Inf. Dynamics 10. V. P. Belavkin and M. Ohya: Quantum entropy and information in discrete entangled state, Infin. Dimens. Anal. Quantum Probab. Relat. Top., Vol. 4 (2001), pp 137-160. 11. V. P. Belavkin and M. Ohya: Entanglement, quantum entropy and mutual information, Proc. R. Soc. London A 458 (2002), pp 209-231. 12. D. Chruscinski and A. Kossakowski: Circulant states with positive partial transpose, Physical Review A 76 (2007), 14 pp. 13. D. Chrusciilski and A. Pittenger: Generalized Circulant Densities and a Sufficient Condition for Separabil ity, J. Phys. A: Math. Theor. 41 (2008) 385301. 14. D. Chruscinski and A. Kossakowski, Multipartite Circulant States with Positive Partial Transpose, Open Sys. Information Dyn. 15 (2008) pp 189-212. 15. P. Horodecki, M. Horodecki, and R. Horodecki: Bound entanglement can be activated, Phys. Rev. Lett. 82, (1999), pp 1056-1059. 16. M. Horodecki, P. Horodecki and R. Horodecki: Mixed state entanglement and quantum condition, In Quantum Information, Springer Tracts in Modern Physics 173 (2001), pp 151-195. 17. J. Jurkowski, D. Chrusciilski and A. Rutkowski: A class of bound entangled states of two qutrits, Open Syst. Inf. Dyn., 16 (2009), no 2-3, pp 235-242. 18. M. Ohya and T. Matsuoka: Quantum entangled state and its characterization, Found. Probab. Phys. no 3, 750 (2005), pp 298-306. 19. D. Chrusciilski, Y. Hirota, T. Matsuoka and M. Ohya: Quantum correlation and essential q-entanglement, in preparation.

Quantum Bio-Informatics IV eds. L. Accardi, W. Freudenberg and M. Ohya © 2011 World Scientific Publishing Co. (pp. 157-171)

A COMPLETELY DISCRETE PARTICLE MODEL DERIVED FROM A STOCHASTIC PARTIAL DIFFERENTIAL EQUATION BY POINT SYSTEMS

KARL-HEINZ FICHTNER\ KEI INOUE 2 AND MASANORI OHYA 3 1 Friedrich-Schiller- Universitiit Jena, Fakultiit fur Mathematik und Informatik, Institut fur Angewandte Mathematik, 07737 Jena, Germany. E-mail: [email protected] 2 Department of Electrical Engineering, Tokyo University of Science, Yamaguchi, Sanyo-Onoda, Yamaguchi 756-0884, Japan. E-mail: [email protected] 3 Department of Information Sciences, Tokyo University of Science, Noda City, Chiba 278-8510, Japan. [email protected]

Several scientific and technical problems can be described by a stochastic partial differential equation. The solution of the equation could be considered as the limit of a suitable discrete particle model. The existence of such a kind of approximation was discussed in 5. A completely discrete particle model, which is constructed to simulate by computer, is considered in 3. In this paper we give proofs of some lemmas which are used to prove the main theorem in 3.

1. Introduction

Several scientific and technical problems can be described by partial differential equations of the type

av

1

at

2

-=-~v+f.

(1)

A more precise model is to take into account stochastic disturbances, i.e., to the right hand of (1) there have to be added corresponding source terms. Often this disturbance occurs as the so-called white noise. So we regard the stochastic partial differential equation

av at (x, t) =

1

2~v(x,

t)

+ f(x, t) + O"(x, t) ~(x, t). 157

(2)

158

Note that (2) is connected with the idea of diffusion and generation of particles in random spatial-temporal points. Therefore the solution of (2) could be considered as the limit of a suitable discrete particle model. The existence of such a kind of approximation was discussed in 5, and the related problems were considered in 4,6. In 3 we construct a completely discrete particle model approximating a continuous system being different from the limit considered in 5. In this paper we give proofs of some lemmas which are used to prove the main theorem in 3.

2. Basic notations

The Poisson process Following 7, we introduce the notions and notations in this section. Let G be a Polish space, i.e., a separable topological space for which there is a complete metric. We denote the (I-algebra of the Borel sets in G by ® and the ring of the bounded Borel sets of ® by .e. In the case G = R d we use notations ® = ®d, .e = .ed . Further, M denotes the set of all integervalued measures on ® being finite on.e. Let 9Jt be the smallest (I-algebra of M-subsets which makes the function

f---+

(X),

E M

measurable for each X from.e. A measurable mapping from a probability space [n, F, P] into [M,9Jt] is called a random point system in G, the distribution on [M,9Jt] generated by such a random point system is said to be a point process with the phase space G. To each measure H on [M,9Jt], a measure PH on ®, called the intensity measure of H, is assigned by PH(X):=

J

(X)H(d
X E ®.

Let Xl" '" Xm be elements of ®. The measurable mapping

f---+

[(Xd, ... , (Xm)]

from Minto Nm transforms each measure H on [M,9Jt] with H({: (Xi ) = oo}) = 0,

i = 1, . .. ,m

into a measure Hx,oo.x= on [Nm ,')'(Nm)]. If H is a point process, the measures Hx,.oox= are called the finite dimensional distributions of H.

159

To any 'c-finite measure f.L on ® we can associate the Poisson process Pep) with an intensity measure f.L characterized by p(p)X, ... x=

= xz;,(7rp(Xi)

for all finite sequences (Xi)~l of pairwise disjoint sets from'c. Here 11")" A > 0 denotes the Poisson distribution with expectation A. For all 'c-finite measure f.L on ® it holds (p(p)t *

where

(p(p)t*

= p(np)

is the n-th convolution-power of

(3) p(J-t)

(cf. 7).

l7-additive processes

Definition 2.1. A random process 7] = (7](B); BE ,c) on [n, F, Pl is called a-additive if for all sequences (Bi)~l of pairwise disjoint elements from ,c such that U~l Bi E ,c, we have

Definition 2.2. A a-additive process 7] = (7](B); B E ,c) is called decomposable if for all finite sequences (Bi)~l of pairwise disjoint bounded measurable sets the random variables 7](Bd, ... , 7](Bm) are independent

(cf. 2). If \fF is a random point system in G then the family \II := (\fF(B); B E ,c) represents a a-additive process. Moreover, if the distribution of \fF is a Poisson process then \II is a decomposable process. The white noise based on the Lebesgue measure on [Rd, ®dl as well as the so-called generalized Brownian motion represents a decomposable process in this sense (cf. 8). Here U is called to be a generalized Brownian motion on G with noise intensity measure f.L if

(i) each random variable U(B) has law N(O, f.L(B)) , (ii) the variables U(B 1 ), ... , U(Bm) are independent B 1 , ... ,Bm are pairwise disjoint.

whenever

Definition 2.3. For each n E N let 7](n) and 7] be a-additive processes on [n, F, Pl. The sequence 7](n) is said to converge toward 7] if for every finite sequence (Bi)~l of elements from ,C the random vector

160

[7)(n) (Bd, ... ,7)(n) (Bm)] converges in distribution ( i.e. , weakly convergence of the probability distribution) to the random vector [7)(B 1 ), . . . , 7)(Bm)]. 3. A Special Type of a Stochastic Partial Differential Equation We consider the stochastic partial differential equation

av at (x, t) =

1

2~v(x, t)

+ f(x, t) + (J"(x, t)

~(x,

t)

(4)

with initial value v(x,O) = 0) or negative(f(x, t) < 0) charged particles are added. Finally, a stochastic source term describing the stochastic disturbance is added. (J"2(x, t) is the intensity of the noise. It must be noted that in the higher dimensional case (x E R d, d > 1) the mathematical concept symbolized by (4) is not quite clear.

A Partially Discrete Particle Model A treatment of this case was discussed in 5. Firstly let us explain the main idea of the model. Let

0, be the stochastic kernel on [Rd, Qjd] given by

K)..(q,·) = N(q,)..1,·) Here I denotes the identity matrix and N(q, ),,1,') denotes the normal distribution with the expectation vector q and the diagonal matrix I as covariance matrix. Then

(5) describes how the charge present at initial time zero diffuses until the time

t. Here Zd denotes the Lebesgue measure on [Rd, Qjd]. The discretization of the process corresponding to the source term f occurs as follows: Let f be a bounded measurable function defined on R d X R +. We define functions f+, f - putting

f+

:= max{O,

f}, f-:= max{O, - f} .

161

f-L1 denotes the measure on R d+ 1 X f-L1(B x {I}) f-L1(B x {-I})

{

-1,1} characterized by

J =J =

j+(XhB(X) Zd+1(dx), BE £d+1,

j-(X)XB(x) Zd+l(dx), BE £d+1.

(j?n denotes a random point system in Rd+1 x {-I, I} with distribution P(nJ.Ll)' Thus (j?n describes the_ configuration of charge points which are added spatially-temporally. If {(In{[x, S, I]) = 1 then a charge unit of the amount l/n is added. If (j?n{[x, s, -I]) = 1 then a charge unit of the amount -1/ n is added. After occurring a particle, it diffuses. Thus the contribution of this source process to the charge density until t > 0 is given by

D~n)O = ~

J

C

(Kt-s(x, ')X(O,t)(s)

+ 8xOX{t}(s)) (j?n(d[x, s, c]).

(6)

Here XB denotes the indicator function of a set B. The disturbance term is transformed similarly. Let IJ be a bounded measurable function defined on R d X R +. 1J2 is considered as the density of a measure f-L2 on [Rd+l, Qjd+1]. We define a measure f-L on Rd+1 x {-I, I} by f-L := f-L2 x

1

2" (8 1 + L d·

Let {(In be a random point system in R d+1 X { -1, I} with distribution p(nJ.L)' Analogously to (j?n the random point system {(In describes the configuration of charge points which are added spatially-temporally with mean intensity nIJ 2 including the "sign" of the unit charges. Differently to the effect of the first source process individual charges of the value 1/ Vn are generated. Thus the contribution of this second source process to the charge density until t > 0 is given by c;n) 0

=

In J

c (Kt-s(x,.) X(O,t)(s)

+ 8xOX{t}(s)) {(In (d[x, s, c]).

(7)

Each particle should give a contribution to the entire charge and evaluate independently on the other ones. These requirements do not follow from the properties of the Poisson process. Therefore, we assume that (j?n and {(In are independent. Consequently the entire process can be defined as the sum of independent random variables

(8)

162

By the normalization lin, respectively lifo, the "potential" of one generated particle decreases when n increases, whereas the average number of the particle increases, i.e., the produced charge is "smeared over" in a certain manner. From theorem 1.3.6 in 5 we can conclude: Theorem 3.1. Let be t > O. Then it holds

(a) The sequence of the (J"-additive processes u~n) = (u~n) (B); B E £d) converges (in the sense of definition 2.3) to a (J"-additive process Ut = (ut(B); BE £d). (b) For each finite sequence (Bi)'~l from £d the random vector [ut(BI), ... , ut(Bm)] is normally distributed. The distribution is characterized by the expectation values

and by the covariances

Let us note that the processes (Ut)t>o can be interpreted as the solution of the integral equation corresponding to (4) (cf. 5).

A Completely Discrete Particle Model In 3 a completely discrete particle model is considered, i.e., in addition to the source term j and the diffusion term (J"2 the initial condition cp has to be discretized. Furthermore the particles of the considered system are moving according to a Brownian motion. In the following we assume that cp(x) is an integrable function on Rd. Furthermore we assume that for all t > 0 the functions j(x,s)x(O,t)(s) , (J"2(x,s)X(0,t)(s) are integrable. Those conditions insure that the considered random point systems are always finite. In principle one can consider the case that cp, j, (J"2 are bounded measurable functions like in 5. Now the initial condition cp will be discretized as follows: /-to denotes the measure on R d+ 1 X {-1, I} characterized by

J =J

/-to(B x {I}) = /-to(B x {-I})

cp+ (X)xB (x) ld(dx), BE £d, CP- (X)XB(X) ld(dx), BE £d.

163

Let ~n be a Poisson random point system on R d X { -1, I} with distribution p(nl-'o)' ~n describes the configuration of charge points. Further ((wx(t))t>O)xERd denotes a family of independent standard Wiener processes on Rd. A charge point starts from x at initial time 0 and moves to x + wx(t) at time t. The contribution of this diffusion process to the charge density until t > 0 is given by

(9) We have already discretized the source term f and the diffusion term J2, i.e., we already have the point configurations of ~n and q,n. A charge point occurring at time s on position x moves to x + Wx (t - s) at time t. The contributions of these source processes to the charge density until t > 0 are given by

D-en) t (-)

11 In 1

=;

c;n)(-) =

-

c X(O,t)(s) Dx+wx(t-s)(-) q,n(d[x, s, c]), C

X(O,t)(S) Dx+wx(t-s)(-) q,n(d[x, s, c]).

(10) (11)

Furthermore we assume that ((w x (t))t2:0)XERd, ~n, ~n, q,n are independent. The entire process can be defined as the sum of independent random variables

(12) Similarly as the partially discrete particle model, the discrete system Ut(n) should approximate a continuous system. The following theorem makes that more precise 3. Theorem 3.2. Let be t given by

Vt(B) = At(B) at(B)

=

1

> 0, B

+

E £d. Further let Vb at measures on Rd

1

Kt-s(x, B)f(x, S)x(O,t)(S) ld+l(d[x, s])

Kt-s(x, B)J 2(x, S)x(O,t)(S) 1d+1(d[x, s]).

We assume that "\it is a generalized Brownian motion with noise intensity measure at. Then the sequence of the J-additive processes (Ut(n))nEN converges to a decomposable process Ut given by the following equation

164

Remark 3.1. This theorem means that the completely discrete particle model approximates a continuous system being different from the limit considered in 5, i.e., the limit of the completely discrete model has the same expectation values but different covariances, compared with the limit considered in 5. 4. Some Lemmas

For the proof of the main theorem in necessary to use the following lemmas.

3

(theorem 3.2 in this paper) it is

Lemma 4.1. Let \[Tn be a Poisson random point system with intensity measure nf.1 where f.1 is a locally finite measure on G and n E N. u(n) denotes the CT-additive process defined by u(n) := ~ \[Tn. Then the sequence (u(n) )nEN converges to the (trivial) CT-additive process f.1, i. e., AUCn) (g) -+ exp{ifg(x)f.1(dx)} (n-++oo).

Lemma 4.2. Let <pr,
Now let kt(x , y) be the density of the transition probability of the ddimensional standard Wiener process, i.e., d

kt(x,y)

=

(_1_)"2 exp (-~llx _ Y112) 27rt 2t

(t> Q,x,y

ER

d ).

Lemma 4.3. Let

Q

165

Lemma 4.4. Let 1> be a Poisson random point system in Rd x R+ with finite intensity measure f-L, i.e., f-L(R d x (0, +(0)) < +00, being absolutely continuous w. r. t. the Lebesgue measure. h denotes its density. Further let ((wx(t))t:"O)xERd be a family of independent standard Wiener processes in Rd being independent from 1>. Then for each t > 0 1>t := J 1>(d[x, s])Ox+wx(t-s)X(O,t)(s) becomes a Poisson random point system in R d with finite intensity measure f-Lt being absolutely continuous w. r. t. the Lebesgue measure with density

5. Proof

In this section we give the proofs of the lemmas in section 4. Using the lemmas the proof of theorem 3.2 is given in 3. Proof of Lemma 4.1 Let us consider the characteristic functional Cu(n) (g) of u(n). Firstly m

= Lc~m)XB("') with pairwise disjoint

we consider the special case gem)

k

k=l

subsets Bi m), ... , B~m). Then we have

J

gCm)(x)du(n)(x) =

fc~m)u(n) k=l

(Bkm)) =

~ fc~m)wn (Bkm)).

(13)

k=l

From (13) we obtain Cu(n) (g(m))

=

Eexp

(i Jg(m) (x)du(n) (x))

(i~ ~c~m)wn (Bkm))) +00 +00 ((m)) = L ... L II exp iC~ lk =

Eexp

m

h=O

lk=O k=l

xPr{wn(Bim)) =h,'" ,Wn(B~m)) =lm}

= fL~ exp

(iC~) lk) Pr {w

n

(Bkm)) =

lk}'

(14)

166

Since
Using the Maclaurin expansion of exponential functional we have

From (15),(16) we obtain

=exp{i~c~m)j.L(Bkm)) } = exp

{i Jg(m) (x)j.L(dx) }.

(17)

Finally let us approximate a general function g by the sequence i.e.

(g(m))mEN,

From (17), (18) we get CU(n)

(g)

~ exp

{i Jg(X)j.L(dX)}

(n

Proof of Lemma 4.2 Let us consider the characteristic functional

--+

+00) . •

Cu(n)

(g) of

u(n).

Firstly

m

we consider the special case gem) = Lc~m)XB(=) with pairwise disjoint k

k=l

167

subsets

Bim), ... ,B~m). Then we have

J

g(m) (x)du(n) (x)

=

f

ckm)u(n)

(Bk

m ))

k=l

(m)

m

= ~ ~ {<1>7 (Bkm))

- <1>~ (Bkm))}.

(19)

From (19) we obtain

=

IT

exp

n

[n~ (Bkm)) {exp «~) -I}]

x eX+M (Bjm)) {ex =

IT

exp

p

(-i$;)

I}]

[n~(Bkm)) {exp «~) +exp (-ij;) -2}]

(20b)

where the equality (20a) is obtained from the independence of <1>f and <1>2. Using Maclaurin expansion of exponential function we have

n~ (Bkm)) {exp (ij;) +exp (-ij;) -2} = _ (Ck:))2 ~ (Bkm )) + 0 (~). (21)

168

From (20b),(21) we get

From (22) we obtain

Gu(n) (g(rn))

-----+

exp

[-~

J

{g(rnl(x)}2 fL (dX)] (n

----+

+00).

(23)

Similarly as (18) let us approximate a general function g by the sequence (g(rn) )rnEN. Then it holds from (23)

Gu(n) (g)

-----+

exp

[-~

J

{g(X)}2 fL (dX)] (n

----+

+00) . •

Proof of Lemma 4.3 Let us consider the characteristic functional Gt of Firstly we consider the special case g(rn) = EZ'=l c~rn) Bkrn ) with pairwise disjoint subsets B 1(rn) , ... , B(rn) rn· Then we h ave

t.

J

g(rn) (x)dt(x) =

f>~m)t (Bkm)) k=l

=

f>~m)

J

(dx)8x+wx (t) (Bk m))

k=l

= L g(m)(x + wx(t)).

(24)

xE

From (24) we obtain

Gt(g(m)) = Eexp

(i Jg(m) (X)dt(X))

= EexP{Lig(ml(X+wx(t))} xE

=E

II exp {ig(m)(X + Wx(t))}. xE

(25)

169

Using the independence of ((wx(t)k~O)xERd and
G'Pt(g(m»)

=

J

PJ-L(d
= exp

II Eexp {i9(m)(X +wx(t))} xE'P

(J J-l(dx) [Eexp{ig(m)(x+wx(t))} -1]).

(26)

Further it holds

E exp {ig(m)(x

+ Wx(t))} =

J

exp {ig(m)(y)} kt(x, y)dy. (27)

From (26),(27) we obtain

G'Pt(g(m») = exp

= exp

(J J-l(dx) [J {ig(m)(y)} kt(x,y)dy -1]) (J {J h(x)kt(x, Y)dX} {i9(m)(y)} - dY) exp

[exp

1]

(28) Setting h t as

ht(y)

:=

J

h(x)kt (x, y)dx,

we obtain from (28)

G'P t (g(m»)

=

exp

= exp

(J ht(y) (J J-lt(dy)

[exp {i9(m)(y)}

-1] dY)

{exp {i9(m)(y)}

-I}) .

(29)

Similarly as (18) let us approximate a general function 9 by the sequence (g(m»)mEN. Then it holds from (29)

G'Pt(g) = exp

(J J-lt(dy) [exp{ig(y)} -IJ).

That proves lemma 4.3 . • Proof of Lemma 4.4 Let us consider the characteristic functional G'P t of
ci Bk

170 B 1(m) , ... , B(m) m·

Then we have

/ g(m) (x)diJ>t(x) =

f>~m)iJ>t (Bk m)) k=l

=

f>~m) / k=l

iJ>(d[x, s])X(O,t) (s )Ox+wx(t-s) (

L

Bkm))

g(ml(x + wx(t - s)).

(30)

[x,sjE,O<s
From (30) we obtain

Ct(g(m)) = Eexp

(i / g(m) (X)diJ>t(X)) L

= Eexp {

g(m)(x

+ wx(t - S))}

[x,sjE,O<s
II

=E

exp{ig(m)(x+wx(t-s))}.

[x,sjE , O<s
II

P,,(diJ»

= /

Eexp{ig(m)(x+wx(t-s))}

[x,sjE,O<s
= exp ( / f.l(d[x, s])X(O,t)(s) [E exp {ig(m)(x + wx(t - s))} - 1]) (31) where

the

equality

((wx(t))t>O)xERd and

(31)

iJ>.

is

obtained

from

the

independence

of

Further it holds

Eexp{ig(m)(x+wx(t-s))} = / exp {ig(m)(y)} kt-s(x,y)dy.

(32)

From (31),(32) we obtain

Ct (g(m)) =

exp ( / f.l(d[x, s]h(o,t) (s) [/ exp {ii m)(y) } kt-s(x , y)dy - 1])

= exp ( / { / / h(x, s )X(O,t) (s )kt-s(x, y)dxds } [ex p {ig(m) (y) } - 1] dY) . (33)

171

Setting h t as

ht(y)

:= /

/

h(x, s)X(O,t)(s)kt-s(x, y)dxds,

we obtain from (33)

CiPt(g(m)) = exp ( / ht(y) [exp {ig(m)(y)} -1] dY)

= exp ( / ILt(dy)

J) .

[exp {ig(m)(y)} - 1

(34)

Similarly as (18) let us approximate a general function g by the sequence (g(m))mEN. Then it holds from (34)

CiPt(g)

=

exp ( / ILt(dy) [exp{ig(y)} - l l)

.

That proves lemma 4.4 . •

References 1. L. Breiman, Probability, Reading, Mass., 1968. 2. J. Feldman, Decomposable processes and continuous products of probability spaces, J. Function. Analysis, 8, I-51, 1971. 3. K.-H. Fichtner, K. Inoue, M. Ohya, Approximative approaches to a stochastic partial differential equation by point systems, Preprint. 4. K.-H. Fichtner, R. Manthey, Weak approximation of stochastic equations, Stochastics and Stochastics Reports, 43, 139-160, 1993. 5. K.-H. Fichtner, M. Schmidt, Approximation of a continuous system by point systems, SERDIeA, 13, 396-402, 1987. 6. K.-H. Fichtner, G. Winkler, Generalized Brownian motion, point processes and stochastic calculus for random fields, Math. Nachr. 161, 291-307, 1993. 7. K. Matthes, J. Kerstan, J. Mecke, Infinitely divisible point processes, J.Wiley, New York, 1978. 8. J.B. Walsh, A stochastic model of neural response, Adv.Appl.Probability, 13, 231-281, 1981. 9. H. Zessin, The method of moments for random measure, Z. Wahrsch. Verw. Gebiete 62, 395-409, 1983.

This page intentionally left blank

Quantum Bio-Informatics IV eds. L. Accardi, W. Freudenberg and M. Ohya © 2011 World Scientific Publishing Co. (pp. 173- 183)

ON QUANTUM ALGORITHM FOR EXPTIME PROBLEM S. IRIYAMA AND M. OHYA

Department of Information Sciences , Tokyo University of Science 2641, Yamazaki, Noda City, Chiba, Japan There exists a quantum algorithm with chaos dynamics solving an NP-complete problem in polynomial time, called OMV SAT algorithm . The language class EXPTIME is larger class than NP, there is no classical algorithm to solve it in polynomial time. In this paper we propose a quantum algorithm for one of the problems in EXPTIME, Pebble Game, and compare the computational complexity of it with the classical one. We show that a quantum algorithm with Oracle solves it in polynomial time while a classical algorithm with same Oracle does in exponential time.

1. Introduction

We have studied on quantum algorithm for several years. Ohya, and Volovich discovered the quantum algorithm with chaos dynamics called the OMV quantum algorithm which can solve NP complete problem in polynomial time. We applied this quantum algorithm to the other problems, multiple alignment of amino acid sequence, Hamilton closed path problem, protein folding problem and EXPTIME problem. Therefore we found that OMV quantum algorithm is useful for searching problems, i.e., to search the objects which satisfy the given conditions. In the field of Bio-Information there exist many searching problems, and we can apply our quantum algorithm to them. In this paper, we show a quantum algorithm for EXPTIME problem, Pebble Game. Then we discuss the computational complexity of it.

2. Quantum Algorithm A quantum algorithm is constructed by the following steps: (1) Prepare a Hilbert space (2) Construct an initial state (3) Construct unitary operators to solve the problem 173

174

(4) Apply them for the initial state and obtain a result state (5) If necessary, amplify the probability of correct result (6) Measure an observable with the result state In the first step, we define the Hilbert space depending on the problem. Let

((:2

be a Hilbert space spanned by 10)

=

(~)

and 11)

=

(~),

a

normalized vector 1'If!) = a 10) + (311) on this space is called a qubit. Since we can use a superposition of 10) and 11) as an initial state vector, the quantum algorithm is more effective than classical one. One can apply Hadamard transformation H __ 1 (1 1 )

- y'2

1-1

to create a superposition. For 10) and 11), it works as H 10)

1

1

= y'210) + y'211)

1 1 H 11) = -10) - -11) .

y'2

y'2

Hadamard transformation has a very important role in a quantum algorithm. Here we introduce logical gates, which are NOT gate, C-NOT gate and CC-NOT gate. We call these gates fundamental gates. We can also construct AND and OR gate by considering the product of fundamental gates and some imprementations. The NOT gate UNOT is defined on a Hilbert space ((:2 as UNO T =

11) (01

+ 10) (11·

It works for an arbitrary qubit as

C-NOT UCN gate and CC-NOT Hilbert space as UCN

UCCN

are given on two and three qubit

= 10) (01 ® I + 11) (11 ® UNO T

UCCN =

10) (01 ® I ® I

+ 11) (11 ® 10) (01

®I

+ 11) (11 ® 11) (11 ® UNO T ,

respectively. The unitary operator to solve the problem is constructed by these fundamental gates.

175

3. OMV SAT Algorithm In this section, we explain OMV(Ohya-Masuda-Volovich) quantum algorithm which contains two part, that are unitary computation and chaos amplification process. It is discussed precisely in the papers l ,2,4,9. Let X == {Xl, ... ,xn},n E N be a set. Xk and its negation Xk (k = 1, ... , n) are called literals. Let X == {Xl, .. " Xn} be a set, then the set of all literals is denoted by X' == X UX = {Xl, ... , X n , Xl,"" X n }. The set of all subsets of X' is denoted by :F (X') and an element G E :F (X') is called a clause. We take a truth assignment t to all variables Xk. If we can assign the truth value to at least one element of G, then G is called satisfiable. Let L = {O, I} be a Boolean lattice with usual join V and meet 1\, and t (x) be the truth value of a literal X in X. Then the truth value of a clause G is written as t(G) == VxEct(x). Moreover the set C of all clauses Gj (j = 1,2,'" ,m) is called satisfiable iff t (C) == I\'j=l t (Gj ) = 1. Thus the SAT problem is written as follows: [SAT problem] Given a Boolean set X == {Xl,'" ,xn}and a set C = {Gl ,'" ,Gm } of clauses, determine whether C is satisfiable or not. That is, this problem is to ask whether there exists a truth assignment to make C satisfiable. It is known that we can check the satisfiability in polynomial time when a specific truth assignment is given, however we do not determine it in polynomial time when an assignment is not specified. We first calculate the total number of qubits, and show that this number depends on the input data. This calculation is done in polynomial time of input size. Since the total number of qubit required the quantum algorithm, we decide the Hilbert space and the initial state vector on it. Let C {Gl , ... ,Gm } be a set of clauses on X' {Xl, ... ,X n , Xl, ... ,x n }. The computational basis of this algorithm is on the Hilbert space H = (C 2)'l9 n +I-'+l where f.L is a number of dust qubits, it is shown that f.L is less than 2mn g. Let

be an initial state vector. For X we put

where

Cl, C2, ... ,Cn

E

=

{Xl, ... ,x n }

and a truth assignment t,

{O, I} , and we write t as a sequence of binary sym-

176

boIs:

A unitary operator Uc : 1i follows

-t

1i computes t (C) for all truth assignment as

where

Id P )

lei)

leI, e2, ... ,en) is a binary representation of t. Accardi and Sabbadini

=

is dust qubits denoted by p, strings of binary symbols, and

pointed out that OMV SAT algorithm is combinatorial 6 . Theorem 3.1. (l) For a set of clauses C = {Gl , ... , Gm } on X' == {Xl, ... ,X n , Xl,···, xn}, the number p, of dust qubits for algorithm of SAT

problem is p,::::: 2nm

For a set of clauses C = {Gl , ... , Gm }, we can construct the unitary operator Uc to calculate the truth value of C as

Uc ==

m- l

m

i=l

j=l

II UAND (i) IIUoR (j) H (n)

where, H (k) is a unitary operator to apply Hadamard transformation to first k qubits, that is

The computational complexity of quantum computation depends on the number of unitary operator in the quantum circuit. Let U be the unitary operator, it is written as

where Un,· .. ,Ul are fundamental gates. The computational complexity T (U) is considered as n.

177

We need to combine some fundamental gates such as UNOT, UCN and UCCN to construct the quantum circuit in fact. UAN D and UOR can be written as a combination of fundamental gates. Here we obtain the computational complexity T (Uc) of SAT algorithm by the number of UNOT, UAN D and UOR. Theorem 3.2. f) For a set of clauses C = {G 1 , ... , Gm {X1, ... ,X n ,X1, ... ,X n }, T(Uc) is

}

and literal X'

=

m

T (Uc) = m - 1 +

L

(IGkl

+ 2i~ -

1)

k-1

:::; 4mn-l

3.1. Chaos Amplifier

Here we will briefly review how chaos can playa constructive role in computation (see 1,2 for the details). Consider the so called logistic map which is given by the equation

The properties of the map depend on the parameter a. If we take, for example, a = 3.71, then the Lyapunov exponent is positive, the trajectory is very sensitive to the initial value and one has the chaotic behavior 2. It is important to notice that if the initial value Xo = 0, then Xn = for all n. The state 1'IjJ) of the previous subsection is transformed into the density matrix of the form

°

where PI and Po are projectors to the state vectors 11) and 10) . One has to notice that PI and Po generate an Abelian algebra which can be considered as a classical system. The following theorems is proven in 1,2,3. Theorem 3.3. For the logistic map Xn+1 = aXn (1 - Xn) with a E [0,4] and Xo E [0, 1], let Xo be 2~ and a set J be {O, 1,2, ... , n , ... , 2n}. If a is 3.71, then there exists an integer k in J satisfying Xk > ~. Theorem 3.4. Let a and n be the same in above theorem. If there exists

k in J such that Xk > ~, then k > log2~~A - 1.

178

Theorem 3.5. Let It (C)I be the cardinality of these assignments, if Xo ==

.{n with r = It (C)I and there exists k in J such that exists k satisfying the following inequality if C is SAT.

- 13.71 -log2 r] [nlog2 - 1

< k < [-45

-

-

Xk

>

~, then there

(n _1)]

From these theorems, for all k, it holds k (2) g3.71 q

{=>

0 0

iff C is not SAT iff C is SAT

Ohya and Volovich proposed quantum algorithm to calculate truth function by unitary operators and mentioned that it is necessary to use some amplification processes to detect the result in case of very small probability. Then they discovered that one can construct this process by using chaos dynamics. The computational complexity of OMV SAT algorithm is discussed precisely in the papers 10 ,9,1l

4. Language Classes

There exist several classical language classes defined by a deterministic Turing machine. Definition 4.1. Let M be a deterministic Turing machine such that halts for all input. For a length n of input, let f (n) be a maximum length of tape cell of M. We define a space complexity of M as

f.

Definition 4.2. PSPACE is the language class which is recognized by a deterministic Turing machine in a polynomial space. Definition 4.3. NPSPACE is the language class which is recognized by a non-deterministic Turing machine in a polynomial space. Definition 4.4. EXPTIME is the language class which is recognized by a deterministic Turing machine in an exponential time . The following relation is known:

P

~

NP

~

PSPACE

= NPSPACE

~

EXPTIME

179

5. Pebble Game Pebble Game is the two players game using a play board and stones(pebbles). Players move one stone at a time along a given rule alternatively. A player wins when he moves a stone to the winning position on the board given by the rule, or he loses when he cannot move any stones. We want to know whether there exist strategies such that a first mover can win every time. The computational complexity of this problem is obviously very large, and in some cases depending on a size of board and rule it belongs to EXPTIME. Then we propose a quantum algorithm for Pebble Game. First, we explain a representation of game and a definition of Pebble Game.

5.1. Representation of a Game Let I be a set of players, M a set of moves (or strategies) available to those players, and P a set of payments for each combination of moves. A game G is given a triplet (I, M, P). The set of moves is given by a rule of the game. Players choice their move in their turn alternatively, so then these choices are described by a sequence of moves. We denote this by a position Pi where a player i E I has the move. A set of ordered pair (pi, Pj) where Pi and Pj are positions such that Pi -7 Pj is a feasible move implies the rule of the game. The game is finished when there does not exist any moves in someone's turn. When the game is finished, the payments are given to players by a function of the position. In this study we assume that the game must be finished so that the length of position is finite. We say a player A wins if the payments of A is greater than a player B in two players game. Then we consider the following problem: [Game Probleml] Does there exist a way such that a player A wins independently of how a player B plays? To answer this, a winning position of A was introduced by Konig.as a set of positions where A wins in finite moves in spite of moves of B. A set of winning positions of A is constructed inductively from a set of positions where A wins by only one move. Let P is a winning position, q is also a winning position if there exists a move r A of A such that for all moves rB of B, it holds

180

Therefore, the Problem 1 is equivalent as the following: [Game Problem2] Determine whether an initial position of the game is in a winning position of A?

5.2. Pebble Game Let n be a positive finite integer denoted by a size of Pebble Game. n- Pebble Game is given by a triplet G Pebble = (I, M, P) where I =

{A,B}, M = {r=(r l ,r 2 ,r3)E{1, ... ,n}3;risanavailablemove} and P = {f: Mk -> {O, I}}. M is a set of available moves depending on a situation of the board and positions of stones. The rule of Pebble Game is the following: • Prepare n lattices denoted by a board and put m ( < n) stones on nodes. Each nodes has a unique number i = 1, ... n. • Players move one of stones alternatively if the stone so chosen can jump the neighbor stone. • If a player puts a stone on the node n, he wins. If a player can not move any stones, he loses. Let x = (Xl, X2, ... , xn) be a vector of Boolean variables denoted by a situation of board, where Xi has one to one correspondence with a node i: Xi

=

{O no stone on a node i 1 node i has a stone

We prepare m stones on the board Xs arbitrary and call it an initial situation. And we call a finished situation X f if there are no available moves. A move ri (i E {A, B}) for a player i is represented by (rl, r2, r3) E {I , ... , n} 3 where rl indicates a position of stone, r2 the neighbor and r3 a position of destination. If there is a stone on rl and r2 and there is not a stone on r3 , the move ri = (rl,r2,r3) is available. After one move, the situation of board is changed by

_ {Xi i = rl or i = r3

Xi -

Xi

otherwise

we denote ri (x) by a situation of board after a move rio If there no moves available or he can move a stone to the node n, the game is finished. Then we have a sequence of moves. For a sequence of moves Pi (i E {A, B}) = (r1, r§, ... , rf) a payment for a player A is given

181

by a function fA E P:

and for a player B is by fB E P: fB (Pi)

=

{ o1 ii == BA

Let us define the following problem: [Pebble Probleml] Does there exist a way such that a player A wins independently of how a player B plays in n-Pebble Game? This problem belongs to EXPTIME if m is not fixed 8 . We check whether an initial situation is a winning position of A for all number m of stones. Then the Pebble Problem1 is translated to the following problem: [Pebble Problem2] For all finished situations xf determine whether there exists k such that 3r~\lr~-1 ... 3d \lr13r~ (xs)

= xf

where Xs is an initial situation. We propose a quantum algorithm with Oracle to solve the Pebble Problem2, and show that even if we assume an Oracle, a classical algorithm is still an exponential time.

5.3. Computational Complexity of a Classical Algorithm for Pebble Game In order to discuss a relative computational complexity between classcal and quantum algorithm, we assume the following Oracle Mo:

Mo : {x; x is a situation} ---; N U {O} For a finished situation x f' Mo cutputs the time of it immediately, just one step. If a situation x is not a final situation, Mo outputs o. A classical algorithm to solve Pebble Problem2 is the following. Step1 For all situations, we do: Step2 Calculate time k (x) for a situation x Step3 If x is a final situation, construct a set Wi (i = 1,2, ... , k (x))of winning situations: Wi

where Wo Step4 Check Xs

= {y; 3r~, \lrB, 3r A, r~rBr AY E Wi-I}

= {x}

= Wk(x).

182

The number of all situations 2n , and the upper bound of number of available moves is 4n since a player can move one pebble into four directions at most. Therefore the computational complexity of a classical algorithm Tc (n) is

Tc (n)

rv

(4n)3 x 2n

rv

exp (n)

Even if we assume the Oracle, this problem belongs to EXPTIME.

6. Quantum Algorithm for Pebble Game As we assume the Oracle Mo, we use a quantum Oracle UMo which works as same as Mo. Here, we construct the following quantum algorithm: Step 1 Step2 Step3 Step4

Create a superposition of all situations. For the superposition, apply Oracle UMo. We construct Wi (i = 1,2, ... k (xf)) for the superposition. If Xs E Wk(x), make the final qubit 11).

All situations are represented by a binary form, so then we can create a superposition of them using Hadamard transformation. Step3 is achieved by a product of unitary gates. In Step4, AND operation is constructed by unitary gates 9 . If final qubit of superposition is 11), there exists a way of winning. Using the chaos amplifier, we obtain the result.

7. Computational Complexity Here, we calculate the computational complexity of the quantum algorithm as the total number of fundamental gates. The Step 1 is constructed by n Hadamard gates. The Step2 is done by only one Oracle UMo. The computational complexity of Step3 has the same order as the classical algorithm. In the Step4 AND operation requires n gates for n qubit. The upper bound of IWk(x) I is (~) where m is the number of pebbles. Therefore, computational complexity TQ (n) of quantum algorithm of Pebble Problem2 is

TQ (n)

rv

{n

+ 1 + (4n)3 + (:) }

x

[~(n

-1)]

rv

poly (n)

where [~( n - 1)] is for chaos amplification to obtain the correct result.

183

8. Conclusion

The computational complexity Tc (n) of a classical algorithm for n-Pebble Game with Oracle is

Tc (n) ~ (4n)3 x 2n ~ exp (n) This is a exponential time of input size n. We constructed a quantum algorithm for this, the computational complexity TQ (n) is

TQ (n)

cv {

n+

1+ (4n)

3

+ (:) }

x

[~( n -

1)]

cv

poly (n)

In this study, we assume the Oracle Mo and the unitary operator UMo which works as Mo. Even if we use this Oracle, the computational complexity of the classical algorithm for Pebble game is an exponential time while it of the quantum algorithm is a polynomial of n.

References 1. M.Ohya and I.V.Volovich, Quantum computing and chaotic amplification, J. opt. B, 5 ,No.6 639-642, 2003. 2. M .Ohya and I.V.Volovich , New quantum algorithm for studying NP-complete problems, Rep.Math.Phys. , 52 , No.l,25-33 2003. 3. M.Ohya and I.V.Volovich, Mathematical Foundation of Quantum Computers, Teleportations and Cryptography, to be published. 4. M.Ohya and N.Masuda, NP problem in Quantum Algorithm, Open Systems and Information Dynamics, 7 No.1 33-39 , 2000 . 5. L. Accardi and M.Ohya, A Stochastic limit approach to the SAT problem, Open systems and Information Dynamics, 11-3, 219-233 , 2004 6. L.Accardi and R.Sabbadini, On the Ohya- Masuda quantum SAT Algorithm, Preprint Volterra, N. 432, 2000. 7. E.Bernstein and U.Vazirani, Quantum Complexity Theory, In Proc. 25th ACM Symp. on Theory of Computation, 11-20, 1993. 8. T.Kasai, A. Adachi , S. Iwata, Classes of Pebble Games and Complete Problems,SIAM J. Comput. Volume 8, Issue 4, pp. 574-586 (1979) 9. S.Iriyama and M.Ohya, Rigorous Estimate for OMV SAT Algorithm, Open Systems & Information Dynamics, 15, 2, 173-187, 2008 10. S.Iriyama, M.Ohya and I.V.Volovich (2006) Generalized Quantum Turing Machine and its Application to the SAT Chaos Algorithm, QP-PQ:Quantum Prob. White Noise Anal., Quantum Information and Computing, 19, World Sci. Publishing, 204-225 11. S.Iriyama and M.Ohya (2008) Language Classes Defined by Generalized Quantum Turing Machine, Open System and Information Dynamics 15:4, 383-396. 12. S.Iriyama and M.Ohya (2009) The problem to construct Unitary Quantum Turing Machine for compute partial recursive function , TUS preprint. 13. S.Iriyama and M.Ohya (2010) Quantum Algorithm for Pebble Game and Its Computational Complexity, TUS preprint.

This page intentionally left blank

Quantum Bio-Informatics IV eds. L. Accardi, W. Freudenberg and M. Ohya © 2011 World Scientific Publishing Co. (pp. 185-197)

ON SUFFICIENT ALGEBRAIC CONDITIONS FOR IDENTIFICATION OF QUANTUM STATES

ANDRZEJ JAMIOLKOWSKI Institute of Physics, Nicholas Copernicus University, 87- 100 Torun, Poland E-mail: [email protected] The aim of this paper is to discuss the relationship between some problems of the identification of quantum states by geometric methods used in stroboscopic tomography and, on the other hand , by a lgebraic approach typical for the quantum generalization of classical sufficient statistics. Some examp les of necessary and sufficient conditions which must be fulfilled by generators of algebras in order to estimate states of quantum systems are discussed.

Keywords: algebras of observables; stroboscopic tomography; generators of subalgebras.

1. Introduction

One of the basic purpose of physical theories, in both classical and quantum sectors, is to describe events that are observed in Nature or in experiments conducted in laboratories. Usually, we have a physical system under investigation, and we try to obtain information about it by making some experiments. As results, measurement outcomes are registered. In fact, in many situations in classical systems, and in all cases in the quantum regime, we can not predict the individual measurement outcomes and we obtain only some probabilities of results. In other words, we obtain, as the outputs of experiments, only probability distributions on a set of possible measurement outcomes. The statistical theory of classical systems is based on classical probability theory. However, atoms and molecules obey the statistical laws of quantum mechanics and one has to develop a parallel theory based on quantum probability (noncommutative probability), which is an essential generalization of classical probability theory. In classical statistical physics we consider probability distributions as natural representation of states and random variables as representation of observables (physical quantities). In the description of microsystems it 185

186

is natural to start with the idea of observables as a quantum analogue of random variables and to define states as a derived concept. This means that we introduce quantum states through the concept of algebra of observables, taking the states to belong to the dual space. The algebra, furnished with the operation of conjugation (*-operation) is postulated to be a C*-algebra with identity. It can be considered as a natural generalization of the algebra of classical functions with *-operation given by complex conjugation, and whose real random variables are self-adjoint elements. A nice discussion of these issues is given by W. Thirring in his lecture notes 1. From the physical point of view, by a state we understand the description of statistical properties of a system when prepared repeatedly in the same way. In other words, one of the basic assumptions of quantum mechanics is based on the observation that determination of a completely unknown state can be achieved by appropriate measurements only if we have at our disposal a set of identically prepared copies of the system in question. From the mathematical point of view, we say that a state on a C*- algebra of observables is an assignment of a number (the expectation value) for every element of the algebra. This assignment should obey the natural laws of linearity and positivity. Thus, if we denote by A a C*algebra with identity (a set of observables) then a state on A is a linear map (1)

such that P(C"1Q1 + a2Q2) = a1P(Qd + a2P(Q2) for all a1, a2 in C and Q1,Q2 in A , and p(Q) ~ 0 for all positive Q E A. Usually, we also assume that p(lI) = 1. Moreover, to set up an effective approach to the above problem of state determination, one has to identify a collection of observables, a quorum 2 , such that their expectation values contain complete information about the state of the system under consideration. In the standard formulation of quantum mechanics, usually we introduce a Hilbert space H associated with a given microsystem and we identify an algebra of observables A with the set of hermitian elements of the Hilbert-Schmidt space B(H). For any normalized vector Iw) E H the formula

p,p(Q) =

(wIQlw)

(2)

defines a state on A. Such a state is called vector state. In general, the expectation values are given by convex combinations of some vector states

187

and we have the following equality

f5(Q)

=

Tr(pQ) ,

(3)

where p denotes a state of the system in question. The problems of state determination have gained new relevance in recent years , following the realization that quantum systems and their evolutions can perform tasks such as teleportation , secure communication or dense coding (c.f. e.g. 3,4). It is important to realize that if we identify the quorum of observables, then we also have a possibility to determine the expectation values of physical quantities (observables) for which no measuring apparatuses are available 5. The idea of stroboscopic tomography for open quantum systems appeared for the first time in the beginning of 1980 's (although it was expressed in different terms 6 ,7 from the ones used presently). In particular, the question of the minimal number of observables Ql, . .. , Q", for which quantum states can be (Ql , . . . , Q",)-reconstructible was discussed. Simultaneously, it was shown that reconstructibility of states in a finite dimensional systems can be achieved if a sequence of the so-called K rylov subspaces which are defined by

(4) where Q is a fixed observable and lL is a generator of time evolution of the system in question, span the Hilbert-Schmidt space B(H) (cf. below Sect. 3). That is, more precisely, if the following equality is satisfied

(5) In the above equality I-" denotes the degree of the minimal polynomial of the superoperator lL and Ql, ... , Qr represent fixed observables. The symbol ffi denotes the Minkowski sum of subspaces (5) (cf. e.g. 8). We recall that for two subspaces Kl and K2 of the vector space H, by Kl ffi K2 one understands the smallest subspace of H which contains both Kl and.K2 . It is well known that the Krylov subspaces Kk(lL, Q) for k = 1,2, ... form a nested sequence of subspaces of increasing dimensions that eventually become invariant under lL. Hence for a given Q, there exists an index I-" = 1-"( Q) , often called the grade of Q with respect to lL, for which Kl(lL,Q) <;; ... <;; KJJ-(lL,Q) = KJJ-+l(lL,Q) = KJJ-+2(lL,Q)... .

(6)

It is easy to see, that for a given operator Q, the natural number I-"(Q) is equal to the degree of the minimal polynomial of lL with respect of Q.

188

Clearly, p,( Q) :::; p,(lL) where p,(lL) denotes the degree of the minimal polynomial of the superoperator lL (cf. e.g. 9). Now, let us observe that even if the observables Q1, ... , Qr are linearly independent, the Krylov subspaces JCk(lL, Qi) for i = 1, ... , r can have nonempty intersections. When during one of the previous QBIC meetings the author presented the main ideas of the stroboscopic tomography, in response, Prof. M. Ohya immediately suggested an operator algebra approach to these problems and proposed to study the case of some subalgebras of the set of all observables, instead of Krylov subspaces. The main aim of this paper is to discuss properties of sub algebras which allow us for identification of quantum states and to analyse the minimal number of generators of these algebras. The organization of the paper is as follows: In Section 2 we formulate some questions connected with problems of estimation and discrimination of quantum states; Section 3 presents the main ideas of the stroboscopic tomography. Then, in Section 4, we discuss an algebraic approach to the problem of identification of quantum states. We conclude the paper in Section 5 by discussing some examples of algebraic methods in low dimensional systems. 2. Identification of quantum states

In the statistical description of physical systems the main role of observables is to statistically identify states, or some of their properties. A typical goal of an experiment can be to decide among various alternatives or hypothesis about states. As a very good reference on such type of problems we recommend the review book 10. The details of a particular identification problem depend on our prior knowledge and the properties we want to discuss. One can say that owing to both the a priori knowledge about states and the knowledge of our technical possibilities we define the alternatives that we should experimentally verify. In general, depending whether the set of alternatives is finite or not, one makes a distinction between discrimination and estimation problems. One can introduce three different types of problems: 1) State estimation problem. In its most general form, one wants to identify the state of a system assuming that no additional (prior) knowledge is available. In other words, the whole state space of a system constitutes the set of possible hypotheses. 2) Sufficient statistics for families of states. In this case we are interested in considering only a subset of the whole set of states. We

189

encode prior knowledge about the preparation of states in a multiparameter family of states and consider them as a possible set of hypotheses. For example, we can assume that one considers states which are vector states or have a particular block-diagonal form. 3) State discrimination problem. A particular case of the problem 2). One assumes that we want to identify the state which belongs to a finite set {PI"'" Pr} and our aim is to distinguish among these r possibilities. It is an obvious observation that in this case the set of observables used for identification can be restricted in an essential way. All above problems create very interesting particular questions and we will discuss them in separate publications. The problem 2) is discussed in details in our paper "Wandering subalgebras, sufficiency and stroboscopic tomography" 11. 3. Stroboscopic tomography of open quantum systems

Quantum theory - as a description of properties of microsystems - was born more then a hundred years ago. But for a long time it was merely a theory of isolated systems. Only around fifty years ago the theory of quantum systems was generalized. The so-called theory of open quantum systems (systems interacting with their environments) was established, and the main sources of inspiration for it were quantum optics and the theory of lasers. This led to the generalization of states (now density operators are considered as natural representation of quantum states), and to generalized description of their time evolution. At that time the concept of so-called quantum master equations - which preserve positive semi-definiteness of density operators - and the idea of a quantum communication channel were born, cf. e.g. 4,3,12. On the mathematical level, this approach initiated the study of semi groups of completely positive maps and their generators. Now, for the comfort of the Readers, we summarize the main ideas and methods of description of open quantum systems and the so-called stroboscopic tomography. The time evolution of a quantum system of finitely many degrees of freedom (a qudit), coupled with an infinite quantum system, usually called a reservoir, can be described, under certain limiting conditions, by a oneparameter semigroup of maps (cf. e.g. 13,14). Let 7i be the Hilbert space of the first system (dim 7i = d) and let

(7)

190

be a dynamical semigroup, where B*(Ji) denotes the real vector space of all self-adjoint operators on Ji . If one introduces the scalar product of operators A, B by the formula (A, B) = Tr(A* B), then B* (Ji) can be considered as yet another inner product space, namely the so-called Hilbert-Schmidt space with the norm defined by II p 112= Tr(p*p). States of the system are described by density operators p E S(Ji), where S(Ji) := {p E B*(Ji); p 2: 0, Tr p = I}.

(8)

Usually one assumes that the family of linear superoperators (t) satisfies

(1) (t) is trace preserving, t E ~~, (2) II (t)p II ::; II p II for all p E B*(Ji) , (3) (h) 0 (t2) = (h + t2), for all t1, t2 in ~~, and ift -+ 0, then lim (t) = If. Since such defined (t) is a contraction, it follows from the Hille-Yosida theorem that there exists a linear superoperator lK : B*(Ji) -+ B*(Ji) such that (t) = exp(tlK) for all t 2: 0 and

dp(t) dt

=1V

()

!R.p t ,

(9)

where p(t) = (t)p(O). One should stress that the above conditions for semigroup (t) imply preservation of positivity of density operators, p(O) 2: o =? p(t) = (t)p(O) 2: 0 for all t E ~~. Now, the equation (9) (usually called the master equation) defines an assignment (the trajectory of p(O)) ~~ :3 t

t--->

p(t) E S(Ji) ,

(10)

provided that we know the initial state of the system p(O) E S(Ji). The fundamental question of the stroboscopic tomography reads: What can we say about the trajectories (initial state p(O)) if the only information about the system in question is given by the mean values (11) of, say, r linearly independent self-adjoint operators Q1, ... , Qr at some instants t1, ... , t p , where r < d2 - 1 and tj E [0, TJ for j = 1, ... ,p, T> O. In other words, the problem of the stroboscopic tomography consists in the reconstruction of the initial state p(O), or a current state p(t), for any t E ~~, from known expectation values (11). To be more precise we introduce the following description. Suppose that we can prepare a quantum system repeatedly in the same initial state and we make a series of experiments such that we know the expectation values EQ(tj) = Tr(Qp(tj)) for a fixed

191

set of observables Q1,'" ,Qr at different time instants h < t2 < ... < tp' The basic question is: Can we find the expectation value of any other operator Q E B*(7t), that is any other observable from B*(7t) , knowing the set of measured outcomes of a given set Q1,"" Qr at t1, ... , t p, i.e. knowing Ej(tk) for j = 1, ... , r and where 0 S t1 < t2 < ... < tp S T, for an interval [0, T]? If the problem under consideration is static, then the state of ad-level open quantum system (a qudit) can be uniquely determined only if r = d2 - 1 expectation values of linearly independent observables are at our disposal. However, if we assume that we know the dynamics of our system i.e. we know the generator lK or lL := (lK)* (in the Heisenberg picture) of the time evolution, then we can use the stroboscopic approach based on a discrete set of times t 1, ... , tp' In general, we use the term "statetomography" to denote any kind of state-reconstruction method. With reference to the terminology used in system theory, we introduce the following definition: A d-level open quantum system § is said to be (Q1, ... ,Qr )-reconstructible on the interval [0, T], if for every two trajectories defined by the equation (9) there exists at least one instant £ E [0, T] and at least one operator Qk E {Q1,"" Qr} such that (12)

The above definition is equivalent to the following statement. A d-level open quantum system § is (Q1, ... , Qr )-reconstructible on the interval [0, T], iff there exists at least one set of time instants 0 < t1 < ... < tp S T such that the state trajectory can be uniquely determined by the correspondence

(13) for i = 1, ... , rand j = 1, ... ,p. Let us observe that in the above definition of reconstructibility we discuss the problem of verifying whether the accessible information about the system in question is sufficient to determine the state uniquely and we do not insist on determining it explicitly. The positive dynamical semi group {(t), t E ~~} is determined by the generator lK : B*(7t) ---> B*(7t) (the Schrodinger picture) and it is related to the generator lL of the semigroup in the Heisenberg picture by the duality relation

Tr[Q(lKp)] = Tr[(lLQ)p].

(14)

192

For a given set of observables Ql,"" Qr, the subspace spanned on the operators Qi, lLQi, ... , (lL)k-lQi, will be denoted by

(15) as the Krylov subspace in the Hilbert-Schmidt space B*(H). If k = JL, where JL is the degree of the minimal polynomial of the generator lL, then the subspace JCI-'(lL, Qi) is an invariant subspace of the superoperator lL with respect to Qi' It can be easily seen that the subspace JCI-'(lL, Qi) is essentially spanned on all operators of the form (lL)kQi' where k = 0, 1, .... Furthermore, it is the smallest invariant subspace of the superoperator lL containing Qi (i.e. the common part of all invariant subspaces of the operator lL containing Qi)' One can now formulate the sufficient conditions for the reconstructibility of a d-level open quantum system (c.f. 6,7). Let § be a d-level open quantum system with the evolution governed by an equation of the form Q(t) = lLQ(t) (the Heisenberg picture), where lL is the generator of the dynamical semigroup \f!(t) = exp(tlL). Suppose that, by performing measurements, the correspondence

(16) can be established for fixed observables Ql, ... ,Qr at selected time instants t l , ... , tp. The system § is (Ql,"" Qr)-reconstructible if

(17) The above condition has been obtained by using the polynomial representation of the semigroup \f!(t). Indeed, if JL(A, lL) denotes the minimal polynomial of the generator lL and JL = degJL(A,lL), then \f!(t) = exp(tlL) can be represented in the form 1-'-1

\f!(t) =

L Qk(t)lL k,

(18)

k=O

where the functions Qk(t) for k = 0, ... , JL - 1 are particular solutions of the scalar linear differential equation with characteristic polynomial JL(A, lL). Since the functions Qk(t) are mutually independent, therefore for arbitrary T > there exists at least one set of moments t l , ... ,tl-' (JL = deg JL(A, lL)) such that

°

(19)

193

and det[ak(tj)] -=I O. Taking into account these conditions one finds that the state p(O) can be determined uniquely if operators of the form (20) for l = 1, ... , rand k = 0,1, ... span the space B*(1t). In other words, we can say that p(O) can be determined if vectors (20) constitute a frame in Hilbert-Schmidt space B*(1t) or, equivalently, if Krylov subspaces K!l(lL, Qz) for l = 1, ... ,r constitute a fusion frame in B*(1t) 15. The question of an obvious physical interest is to find the minimal number of observables Ql,"" Qry for which a d-level quantum system § with a fixed generator lL can be (Ql , "" Qry)-reconstructible. It can be shown that for an d-level generator there always exists a set of observables Ql,"" Qry, where TJ:= max {dim Ker().IT -lLn, AEa(lL)

(21)

such that the system is (Ql, ... ,Qry)-reconstructible 9. Moreover, if we have another set of observables Ql, ... ,Qry such that the system is (Ql, ... ,Qry)reconstructible, then TJ· The number TJ defined by (21) is called the index of cyclicity of the quantum open system § 9. The symbol (j(lL) in (21) denotes the spectrum of the superoperator lL.

r; ;: :

4. Algebraic approach to identification problems In this section we will discuss some problems of estimation of quantum states when the Krylov subspaces playing such an important role in the stroboscopic tomography are replaced by some sub algebras of the HilbertSchmidt space B*(1t). Just as the fundamental theorem of algebra ensures that every linear operator acting on a finite dimensional complex Hilbert space has a nontrivial invariant subspace, the fundamental theorem of noncommutative algebra asserts the existence of invariant subspaces of 1t for some families of operators from B*(1t). It is an obvious observation that an algebra generated by any fixed operator Q and the identity on 1t can not be equal to B*(1t). This statement is based on the Hamilton-Cayley theorem. However, already for two operators Ql, Q2 and the identity we can have Alg(I, Ql, Q2) =B(1t) (for details cf. below and the next section). In general, the famous Burnside's theorem states that an operator algebra on a finite-dimensional vector space with no nontrivial subspaces must be the algebra of all linear operators. In the sequel we will use the following version of this theorem:

194

Fundamental theorem of noncommutative algebras. If A is a proper subalgebra of B*(H) containing identity, and the dimension of the Hilbert space H is greater or equal to 2, then A has a proper nonzero invariant subspace in H (i.e., the subspace is invariant for all members Q of A). We will apply the above theorem for the following problem. Given a set F = {Q1, ... , Qr} of observables, we would like to establish conditions, when the operators Q1, ... , Qr generate the whole algebra B(H) . In other words, we want to determine whether every element in B(H) can be represented in the form 7f(Q1, ... , Qr), where 7f is a noncommutative polynomial. Let us observe that according to the fundamental theorem if A is a sub algebra of the full complex algebra B(H), then a nontrivial invariant subspace in H exists if and only if dimA

< dimB(H).

(22)

If a set of generators of A is known, then the above inequality can be verified by a finite number of arithmetic operations. The procedures possessing such property are called effective. A very important example of an effective procedure can be formulated when we discuss the problem of the existence a common one-dimensional invariant subspace for a pair of operators Q1, Q2. In other words, we ask about a common eigenvector for two operators Q1, Q2. An answer to this question is given by the following procedure. Let the symbol [Q1, Q2J denote, as usual, the commutator of the operators Q1, Q2. Then a common eigenvector for Q1 and Q2 exists, if and only if, the subspace K of H defined by

n

d-1

K :=

Ker[Q{, Q~J

(23)

j=l k=l

where d = dim H, satisfies the condition dim K > 0 (this is the so-called Shemesh criterion). A short proof of this condition is possible. First of all, let us observe that if J'Ij!) is a common eigenvector of the operators Q1 and Q2, i.e.,

(24) then J'Ij!) belongs to Ker[Q{, Q~J for all j, k greater then 1. This fact and the inequality dim K > 0 means that the gist of the She mesh condition is in observation that the subspace K is invariant under Q1 and Q2. Indeed, if J'Ij!) belongs to K, then by the definition of subs paces Ker[Q{, Q~J one can check that Q1J'Ij!) E K and Q2J'Ij!) E K. Now, let us choose a basis for K and

195

extend it to a basis in H. We then observe that there exists a nonsingular matrix S such that matrices SQlS-l and SQ2S-l have block-triangular forms and the submatrices which correspond to subspace JC commute. This means that these submatrices have a common eigenvector and therefore the same is true for Ql and Q2. D. Shemesh 16 has observed that the condition dim JC > 0 is equivalent to the singularity of the matrix d-l

M:= 2)Q{,Q~l*[Q{,Q~]'

(25)

j=l k=l

where * denotes complex conjugate transpose. For our purposes, on the basis of Burnside's theorem, more interesting is the case when matrices Ql, Q2 do not have common eigenvectors and the algebra A(Ql, Q2) generated by them coincides with B(H). This situation may be expressed by the following inequality detM>O,

(26)

which can be checked by an effective procedure, that is, by a finite number of arithmetic operations. It is obvious, that the matrix M is in general semipositive definite, and the above condition means the strict positivity ofM.

5. Examples. Low dimensional cases Now, in order to illustrate algebraic methods in estimation problems, we will discuss some algebraic procedures in low dimensional cases. For quantum systems of qubits and qutrits one can formulate an explicit form of some conditions in a matrix form which is sometimes more transparent then the general operator form. We will use the so-called vee operator procedure which transforms a matrix into a vector by stacking its columns one underneath the other. It is well known, that the tensor product of matrices and the vec operator are intimately connected. If A denotes a d x d matrix and aj its j-th column, then vec A is the d 2 -dimensional vector constructed from aI, ... , ad. Moreover if A, B, C are three matrices such that the matrix product ABC is well defined, then

vec(ABC)

=

(C T ® A) vec B.

(27)

In the above formula C T denotes the transposition of the matrix C. In particular we have

196

vec A

= (IT 0

A) vec IT

=

(AT

o IT) vec IT.

(28)

Let us agree that when we say that a set of matrices generates the set B(H), we are thinking about B(H) as an algebra, while when we say that a set of matrices forms a basis for B(H) , we are talking about B(H) as a vector space. For qubits, that is for two-dimensional Hilbert space, one can show by a direct computation that det(vec IT, vec Q1, vec Q2, vec(Q1Q2)) = det([Q1, Q2]), det(veclI, vec Q1 , vec Q2 , vec[Q1 ' Q2])

= 2 det([Q1, Q2]),

and

(29)

where on the left hand side we have the determinants of the 4 x 4 matrices and on the right hand sides [Q1, Q2] denotes the commutator of the two 2 x 2 matrices. From the last equality it follows , that if matrices IT, Q1, Q2 and [Q1 , Q2] are linearly independent, then the algebra which is spanned by them has the dimension 4, so Q1, Q2 and IT generate B(H). In other words, two operators Q1 ,Q2 and the identity generate B(H) if and only if the matrix [Q1 ,Q2] has the determinant different from zero. In a similar way one can show that the matrices QI, Q2, Q3, such that no two of them generate B(H), can generate B(H) if and only if the double commutator [Q1, [Q2, Q3ll is invertible. In general, the matrices Q1, ... , Qr generate B(H) iff at least one of the commutators [Qi, Qj] or double commutators [Qi, [Qj, Qkll is invertible 17. In the case of qutrits, that is for a three-dimensional Hilbert space, one can show by direct calculation that if [Q1, Q2] is invertible and W([Q1 ,Q2]) =1= 0, where for Q E B(H) the symbol w(Q) denotes the linear term in the characteristic polynomial of Q, then one can construct an explicit basis for B(H). Indeed, if Q1, Q2 belong to B(H), and (dim H) = 3, then the determinant of the 9-dimensional matrix n build from vec transformations oflI, Q1, Q2, Qi , Q~, Q1Q2, Q2Q1, [Q1, [Q1, Q2 ll , [Q2, [Q2, Q1ll satisfies the equality

(30) That is, if det([Q1, Q2]) =1= 0 and w(Q) =1= 0, then the columns of the matrix correspond to a basis for B(H). Of course, one can also use the Shemesh criterion to characterize pairs of generators for B(H), where dim H = 3.

n

197

References 1. W. Thirring, Quantum Mathematical Physics, (Springer, 2001). 2. W. Band, J. L. Park, Am. J. Phys. 47, 188 (1979). 3. M. A. Nielsen, 1. Chuang, Quantum Computation and Quantum Information, (Cambridge Univ. Press ., 2000). 4. K. Kraus, Ann. Phys. 64 , 119 (1971). 5. S. Weigert , in New Insight in Quantum Mechanics Eds. H.-D. Doebner et al. (Singapore: World Scientific, 2000). 6. A. Jamiolkowski, Rep. Math. Phys. 5, 415 (1975). 7. A. Jamiolkowski, Internat. J. Theoret. Phys. 22, 369 (1983). 8. R. T. Farouki et al., Geometriae Dedicata 85, 283 (2001). 9. A. Jamiolkowski, in Quantum Bio-Informatics III, Eds. L. Accardi et al. (Singapore: World Scientific, 2010). 10. M. Paris, J. Rahecek, eds., Quantum State Estimation, vol. 649 of Lecture Notes in Physics, (Springer, 2004). 11. A. Jamiolkowski, M. Ohya, N. Watanabe, T. Matsuoka, in preparation. 12. A . S. Holevo, Statistical Structure of Quantum Theory (Springer, Berlin, 2001). 13. V. Gorini et al., J. Math. Phys. 17, 149 (1976). 14. G. Lindblad, Comm. Math. Phys. 48, 119 (1976). 15. A. Jamiolkowski, J. Phys. Conf. Series 213, 012002 (2010). 16. D. Shemesh , Lin. Algebra Appl. 62, 11 (1984). 17. H . Aslaksen, A. B. Sletsj0e Lin. Algebra Appl. 430, 1 (2009).

This page intentionally left blank

Quantum Bio-Informatics IV eds. L. Accardi, W. Freudenberg and M. Ohya © 2011 World Scientific Publishing Co. (pp. 199- 208)

CONCURRENCE AND ITS ESTIMATIONS BY ENTANGLEMENT WITNESSES

JACEK JURKOWSKI Institute of Physics, Nicolaus Copernicus University, Grudzigdzka 5/7, 87- 100 Torun, Poland

The notion of concurrence and its role as a measure of quantum correlations for both pure and mixed states is recalled. However, for mixed states concurrence is hard to compute and some estimations of it are necessary. It has been demonstrated how to use entanglement witnesses in this procedure. In particular, it has been shown that each entanglement witness detecting given bipartite entangled state provides an estimation of its concurrence. The results are illustrated by several examples .

1. Introduction

The phenomenon of entanglement between components of a quantum system remains still at the heart of many investigations in quantum information theory 1,2. The notion of entanglement was introduced to characterize non-classical correlations between systems appearing in quantum theory. Although a great progress in quantum information theory has been achieved some problems concerning detecting and quantifying entanglement are still open 3,4,5. In particular, there is still no general algorithm which enables to decide if a given mixed quantum composite state is entangled or not. Concerning quantifying entanglement, there were introduced various measures 6,7,8 ,9,10, 11,12 but these which fulfill some reasonable conditions are hard to compute for mixed states and multipartite systems. Hence, there is a place for methods which give estimations of entanglement measures 13,14,15,16,17,18. The most welcome are procedures which for a given family of states parametrized by x allow to construct estimations as analytical functions of x. In the paper, we focus on some particular method of estimation based on the notion of an entanglement witness (EW) 1,2 and we use it to estimate a measure of entanglement called concurrence 8. We show that EWs can be used not only to detect entanglement but to quantify it as well. We 199

200

illustrate our investigations with several examples.

2. Detecting and measuring entanglement In this paper, we focus ourselves on bipartite entanglement which describes a sort of quantum correlations between two quantum systems defined in their m-dimensional Hilbert spaces HA and HE, respectively. The pure bipartite state 1'1/1 E HA (>9 HE of the composite system is called separable if it can be written in a product form

in terms of two pure states I¢ A and l

m

k=l

k=l

(1) where Mk are Schmidt coefficients. Hence, a pure state 1'1/1 is entangled if and only if at least two Schmidt coefficients are nonzero. Moreover, using decomposition (1) we can introduce the following two measures of entanglement: • entropy of a reduced system PA

= Tr E (1'1/1 ('1/1 I)

defined as

and • concurrence

[(1'1/1 ) and its generalization to mixed states called entanglement of formation (EOF) is considered as the most natural measure but it is hard to compute and even to estimate for most mixed states. Therefore, it is more convenient to use concurrence even if it has no direct connection with entropy. For pure states both measures are simple functions of Schmidt

201

coefficients,

E(I1/J )

= -

L f.tk log2 f.tk , k

C(I1/J) =

2 L

f.tkf.tZ·

k,l#k For mixed states the situation is much more complicated. Let us recall that a mixed state P is entangled if it cannot be written as a convex combination of product mixed states of the subsystems, i.e.

Pk > 0 ,

P= LPkPkA ) 0 PkB ) , k

LPk = 1 , k

where PkA ) and PkB ) are some mixed states of subsystems A and B, respectively. There is still no universal method of detecting entanglement for any mixed state. In particular, entanglement in so-called positive partially transposed (PPT) states (for m 2': 3) is hard to recognized. Entanglement if detected should also be quantified. One expects that a measure M(p) should fulfill at least the following requirements:

(1) M(p) 2': 0 and M(p) = 0 for separable P (sometimes M(Pmax ) = 1 for maximally entangled state Pmax),

(2) invariance with respect to local unitary operation, (3) convex function with respect to convex combination of mixed states, M( LkPkPk)

~

LkPkM(Pk)·

A method extending measures initially defined for pure states to a mixed state setting and which guarantees fulfilling (1)-(3) is the convex roof construction. The procedure consists in a decomposition of P into a convex combination of I-dimensional projectors

P = LPkl1/Jk (1/Jkl, k

LPk = l. k

and then taking infimum over all such decompositions , i.e. one defines

C(p)

=

E(p) =

inf

{P k.!1f k}

inf

{Pk.!1fk}

LPkC(I1/Jk) ' k

LPkE(I1/Jk)' k

as concurrence and EOF for mixed states, respectively.

(2)

202

The problem arises when carrying out the extremalisation procedure in

(2) - exact results are known only in very limited cases. The most famous of them are two-qubit systems and states exhibiting some symmetry (like isotropic or Werner states). In particular, for two qubits there has been shown long ago 8 that (3)

),2 ~ ),3 ~ ),4 are singular values of a matrix Tkl = (Vk 100y 181 with IVk denoting eigenvectors of p, and 0" y stands for the Pauli matrix. Simultaneously, EOF is a function of concurrence, where

0" Y

)'1 ~

Ivi

where S2(X) = -x log2 X - (x -1) log2(x -1) is the binary entropy function. For isotropic states indexed by a fidelity f E [0, 1] and defined as

where 1'ljJ+ is the maximally entangled state, it is well-known 21 that

C(Pf) =

{~ m(m - ~

(mf-1),

1

-
1

f:::; 11m.

EOF is also known 22 but the relation is much more complicated. Unfortunately, the general algorithm of calculating concurrence, EOF and other measures based on the convex roof construction is still missing. Therefore, in what follows we will focus ourself on methods leading to estimations of concurrence.

3. Estimations of concurrence

There are several methods of estimating concurrence. In fact, almost every criterion of entanglement can be reformulated in such a way that it can serve as a source for appropriate estimation of concurrence. Let us recall here the methods based on trace norms of a realigned matrix or partially transposed matrix of the state 19, on local uncertainty relations, on geometrical methods 20 and others. We focus here on the following Breuer results 24:

203

Proposition 3.1. Let f(p) be a convex functional of the state p obeying

L .Jf-tkf-tl

f(l 1/! (1/! I) ~

k#l

for every pure state I1/! described by Schmidt coefficients yTik. Then C(p) ::::

J

m(m2 _ 1) f(p)·

In what follows, we are going to define f(p) in terms of the EW detecting p. Let us recall that a hermitian operator W is called an entanglement

witness (EW) for a state p, if Tr(pW) < 0 while Tr(aW) :::: 0 for all separable states a. There are many examples 25 of entanglement measures M (p) (concurrence, negativity, robustness, etc.), which can be related to the expectation value of some entanglement witness. In the case of concurrence one has the following proposition due to Breuer 24 Proposition 3.2. Let W be an entanglement witness such that

-(1/!IWI1/! ~

L

.Jf-tif-tj

(4)

i ,jf.i

for every pure state (1). Then for an arbitrary mixed state p detected by the witness W C(p) ::::

J

m(:: _ 1) ITr(pW)I·

(5)

Proposition 3.2 is a simple consequence of Proposition 3.1 if one chooses f(p) = -Tr(pW). 4. Main result

Proposition 3.2 distinguishes a class of witnesses satisfying condition Suppose now that W does not satisfy this co~dition. Clearly, for any a the rescaled operator a - I W still defines an EW. Does a-I W satisfy To answer this question let us observe that for I1/! = L::1 $ilai, bi expectation value of W reads as follows (1/! IWI 1/! =

L

.Jf-tkf-tIA~"'()(1/!) ,

(4). >0 (4)? the

(6)

k,l

where the 1/!-dependent matrix A~"'() is defined by

A~"'( ) (1/!) = Re (ak ' bk IWlal, bl

(7)

204

Note, that A kk (W) states, hence

(ak' bk IWlak, bk is a mean value of W on separable

(8) It is clear that Ak~) (1/J) encodes the entire information about W. Moreover, the condition (4) is equivalent to

(9) k,l Let us observe that the space of normalized vectors defines a compact set and hence one may define a positive number )'(W) by the following procedure

-)'(W) := min min A(W\1/J) . 1jJ k#l kl

(10)

It provides a new characteristics of W. Now, comes the main result Theorem 4.1. For any a ;:: )'(W) the rescaled entanglement witness does satisfy (4).

a-I W

The proof is almost trivial. One has

k,l

k

+

L

v'J-LkJ-Ll(Ak~)(1/J) + 1)

k,l#k ;:: 1 +

L

v'J-LkJ-LI(Ak~)(1/J) + 1)

,

k,l#k where we have used (8). As a consequence, if

A(W)(ol,) kl 'f/ -> -1

,

(11)

for all k, l, k -I- l and every normalized 1/J, then W does satisfy (9), hence (4). Suppose now that the above condition is not satisfied. It is therefore clear that for the rescaled witness We< := a - I W with a ;:: ),(W), one has (12) which proves our theorem. It should be stressed that the best estimation is provided by the witness corresponding to a = ),(W), because in this case we achieve equality in (12) at least for some k, l.

205

Summing up, we propose the following simple procedure which provides the estimation of concurrence of P if there is some EW W detecting p: W

------t

A k~)

------t

).

(W)

------t

WA

------t

Tr (WA p)

------t

C (p ) .

Tr (WAP) gives the estimation for concurrence

C(p) 2: -

~(2) Tr(WAP) .

V~

5. Examples Example 5.1. Let HA

= HB = em

and consider the flip operator

m

p

L

=

Ii (j I 0 1j (i I

i,j=l

where {Ii} is the computational basis in

Akf) = Now, evidently Ak~)

em.

Simple calculation gives

(ak' bk IFlal, bl = (ak Ibl)(bk lal).

= I(ak Ibk) 12 2: 0 and

Akf) =

for k -=I- l

Re((aklbl )(bklal)) > -1

according to orthonormality of both basis. Example 5.2. Let us consider isotropic states in

em 0 em (13)

and let us consider a EW

26

(14) satisfying Tr[WiSOpjl

= ~ - f, m

that is, W i so detects isotropic state with fidelity ~ pTA the previous example implies for i -=I- j (W iSO )

A 2J

1

> - m' -

f > 11m. Since l'lfi+('lfi+ I =

206

which shows that ,\,(Wiso) = 11m. As a consequence, the optimal W iso , in the sense of (12), is W iso = mWiso. Now,

(15) and it turns out that the estimation (5) gives an exact result,

V

2m m-1

Example 5.3. In 0 (C3

23

(1 - ~) = C(Pf)· m

we have investigated an E-family (10 > 0) of states in

(C3

(16)

where P3+ denotes a maximally entangled state, 1

di,i+l = 10,

di,i+2 = - ,

(mod 3)

10

and the normalization factor 1 Ne;=-----=1 +E+ C 1

It turns out that p(E) is entangled if and only if 10 i= 1. entanglement is detected by the entanglement witness

1 ... -1

Moreover, its

. -1

1 ..

-1

. -1

1 1

1.

-1

.. -1

1

(17)

207

for E < 1 and

-1· .

1

-1

.1 1

W2

-1·

-1·

1

-1

(18)

.. 1 -1· .. 1

for E > 1. To make pictures more transparent we replaced all zeros by dots. Interestingly, WI corresponds to the celebrated Choi positive indecomposable map and W 2 to its dual. Numerical calculations show that indeed A~ii)(1jJ);::: -1 for i = 1,2. Hence one obtains the following estimation for concurrence based on the above EWs E(E-l)

C( (E)) > _ ~ { 1 + E + E2 P

-

J3

l-E

1 + E + E2

O<E<1

(19) E>1

We stress, however, that this estimation is weaker than the one obtained from the trace norm of realigned matrix (see Fig. 1). c

Figure 1. Two estimations of concurrence as a function of c. The dashed line is for the estimation based on IIR(p(c))lll' The solid line is for the estimation based on (19).

208

References 1. M. A. Nielsen and I. L. Chuang, Quantum computation and quantum information, Cambridge University Press, Cambridge, 2000. 2. R. Horodecki, P. Horodecki, M. Horodecki, K. Horodecki, Rev. Mod. Phys. 81, 865-942 (2009). 3. O. Guhne, G. Toth, Phys. Reports 474,1-75 (2009). 4. O. Guhne, M. Reimpell, R.F. Werner, Phys. Rev. Lett. 98, 110502 (2007). 5. J. Eisert, F. G. S. L. Brandao, K. M. R. Audenaert, New J. Phys. 9, 46 (2007). 6. V. Vedral, M. B. Plenio, M. A. Rippin, and P. L. Knight, Phys. Rev. Lett. 78, 2275 (1998). 7. C. H. Bennett, D. P. DiVincenzo, J. A. Smolin, W. K. Wootters, Phys. Rev. A 54, 3824 (1996). 8. W. K. Wootters, Phys. Rev. Lett. 80, 2245 (1998). 9. G. Vidal and R. Tarrach, Phys. Rev. A 59 141 (1999). 10. M. Steiner, Phys. Rev. A 67, 054305 (2003). 11. H. Barnum and N. Linden, J. Phys. A: Math. Gen. 34, 6787 (2001). 12. T.-C. Wei and P. M. Goldbart, Phys. Rev. A 68, 042307 (2003). 13. A. Datta, S. T. Flammia, A. Shaji, C. M. Caves, Phys. Rev. A 75, 062117 (2007). 14. O. Guhne, M. Reimpell, R.F. Werner, Phys. Rev. A 77, 052317 (2008). 15. R. Augusiak, M. Lewenstein, Quantum Information Processing 8, 493-521 (2009). 16. Zhihao Ma, Fu-Lin Zhang, Dong-Ling Deng, Jing-Ling Chen, Phys. Lett. A 373,1616-1620 (2009). 17. J.I. de Vicente, Phys. Rev. A. 75, 052320 (2007). 18. F. Mintert, M. Kus, A. Buchleitner, Phys. Rev. Lett. 92, 167902, (2004). 19. Kai Chen, S. Albeverio, Shao-Ming Fei, Phys. Rev. Lett. 95, 040504 (2005). 20. Cheng-Jie Zhang, Yong-Sheng Zhang, Shun Zhang, Guang-Can Guo, Phys. Rev. A 76, 21. P. Rungta, C. M. Caves, Phys. Rev. A 67, 012307 (2003). 22. B. M. Terhal, K. G. H. Vollbrecht, Phys. Rev. Lett. 85, 2625 (2000) 23. J. Jurkowski, D. Chruscinski, A. Rutkowski, Open Sys. Information Dyn. 16, 235 (2009). 24. H.-P. Breuer, J. Phys. A: Math. Gen. 39, 11847 (2006). 25. F. G. S. L. Brandao, Phys. Rev. A 72, 022310 (2005). 26. B.M. Terhal, P. Horodecki, Phys. Rev. A 61, 040301 (2000).

Quantum Bio-Informatics IV eds. L. Accardi, W. Freudenberg and M. Ohya © 2011 World Scientific Publishing Co. (pp. 209- 222)

CLASSICAL WAVE MODEL OF QUANTUM-LIKE PROCESSING IN BRAIN

A. KHRENNIKOV International Center for Mathematical Modelling in Physics and Cognitive Sciences Linnaeus University, S-35195, Viixjo, Sweden

We discuss the conjecture on quantum-like (QL) processing of information in the brain. It is not based on the physical quantum brain (e.g., Penrose) - quantum physical carriers of informat ion. In our approach the brain created the QL representation (QLR) of information in Hilb ert space . It uses quantum information rules in decision making. The existence of such QLR was (at least preliminary) confirmed by experimental data from cognitive psychology. The violation of the law of total probability in these experiments is an important sign of nonclassicality of data. In so called "constructive wave function approach" such data can be represented by complex amplitudes. We presented 1,2 the QL model of decision making. In this paper we speculate on a possible physical realization of QLR in the brain: a classical wave model producing QLR . It is based on variety of time scales in the brain . Each pair of scales (fine - the background fluctuations of electromagnetic field and rough - the cognitive image scale) induces the QL representation . The background field plays the crucial role in creation of "superstrong QL correlations " in the brain.

1. Introduction

Many authors (e.g., Roger Penrose and Stuart Homeroff) advertized the model of the quantum brain, i.e., quantumness of the brain is a consequence of its composition of quantum systems. Of course, such a brain is a processor of quantum information. This approach induces numerous complicated questions on physics of such brain, e.g., "Is the brain too hot to be quantum?" Therefore, although we do not deny completely this interesting model, we do not couple our mathematical model of quantum information processing in the brain to the "physical quantum brain." In 2001 I pointed 3 ,4 to coupling between violation of the law of total probability (LTP) and interference of probabilities in quantum mechanics, e.g., in the fundamental two slits experiment. Interference (both classical and quantum) implies the violation of LTPi moreover, violation of LTP 209

210

induces the wave-like representation of probabilistic data by complex (and more general) amplitudes - the constructive wave function approach4. LTP plays the fundamental role in decision making; its violation implies a new strategy in decision making - nonclassical decision making 5 . We point out that LTP is violated in some experiments of cognitive psychology, e.g., games of the Prisoner's Dilemma (PD) type or recognition of ambiguous figures 1 ,6 for detailed presentation. The violation of LTP in these experiments is an important sign of nonclassicality of cognitive data. In the constructive wave function approach that such data can be represented by complex probability amplitudes 6 . This is an important motivation to look for QL models of information processing in the brain. In previous works 1 ,2 we presented quantum information models of decision making in games of the PD-type. This is a model of how the brain using QLR of information might work. Thus, on one hand, we have experimental data which support the hypothesis of QL processing of information in the brain and, on the other hand, we have a theoretical model of such processing. In this paper we are looking for models of physical realization of QLR in the brain. We propose a classical (!) wave model which reproduces probabilistic effects of quantum information theory. Why do we appeal to classical electromagnetic fields in the brain and not to quantum phenomena? In neurophysiological and cognitive studies we see numerous classical electromagnetic waves in the brain. Our conjecture is that these waves are carriers of mental information which is processed in the framework of quantum information theory. In the quantum community there is a general opinion that quantum effects can not be described by classical wave models (however, cf. Schrodinger). Even those who agree that the classical and quantum interferences are similar emphasize the role of quantum entanglement and its irreducibility to classical correlations (however, cf. Einstein-PodolskyRosen). It is well known that entanglement is crucial in quantum information theory. Although some authors emphasize the role of quantum parallelism in quantum computing, i.e., superposition and interference, experts know well that without entanglement the quantum computer is not able to beat the classical digital computer. Recently I propose a classical wave model reproducing all probabilistic predictions of quantum mechanics, including correlations of entangled systems, so called prequantum classical statistical field theory (PCSFT) 7,8 and see paper9 for the recent model for composite systems. It seems that,

211

in spite of mentioned common opinion, the classical wave description of quantum phenomena is still possible. In this paper we apply PCSFT to model QL processing of information in the brain on the basis of classical electromagnetic fields. This model is based on the presence of various time scales in the brain. Roughly speaking each pair of time scales, one of them is fine - the background fluctuations of electromagnetic (classical) field in the brain, and another is rough - the cognitive image scale, can be used for creation of QLR in the brain. The background field (background rhythms in the brain) which is an important part of our model plays the crucial role in the creation of "superstrong QL correlations" in the brain. These mental correlations are nonlocal due to the background field. These correlations might provide a solution of the binding problem. Each such a pair of time scales, (fine, rough), induces QLR of information. As a consequence of variety of time-scales in the brain, we get a variety of QL representations serving for various psychological functions. This QL model of brain's work was originated in author's paper 10 . The main improvement of the "old model" is due to a new possibility achieved recently by PCSFT: to represent the quantum correlations for entangled systems as the correlations of the classical random field, so to say prequantum field. This recent development has also highlighted the role of the background field, vacuum fluctuations. We now transfer this mathematical construction designed for quantum physics to the brain science. Of course, it is a little bit naive model, since we do not know the the correspondence between images and probability distributions of random electromagnetic fields in the brain. 2. The role of the law of total probability

2.1. LTP and classical decision making We recall the classical LTP: The prior probability to obtain the result, e.g., b = + 1 for the random variable b is equal to the prior expected value of the posterior probability of b = + 1 under conditions a = + 1 and a = - 1;

P(b = j) = P(a = +1)P(b = jJa = +1) +P(a = -1)P(b = jJa = -1), (1) where j = +1 or j = -l. LTP gives a possibility to predict the probabilities for the b-variable on the basis of conditional probabilities and the a-probabilities. The main idea behind applications of LTP is to split in general complex condition,

212

say C, preceding the decision making for the b-variable into a family of (disjoint) conditions, in our case C+ = {a = +1} and C~ = {a = -I}, which are less complex. Then one estimate in some way (subjectively or on the basis of available statistical data) the probabilities under these simple conditions: P(b = ±Ia = ±1) and the probabilities P(a = ±1) of realization of conditions Cj;. On the basis of these data LTP provides the value of the probability P(b = j) for j = ±1. If, e.g., P(b = +1) is larger than P(b = -1), it is reasonable to make the decision b = +1, say yes. Typically decision making is based on two thresholds for probabilities (assigned depending a problem): 0 ::::: c_ ::::: c+ ::::: 1. If the probability P(b = +1) ~ c+, the decision b = +1 should be done. If the probability P(b = +1) ::::: c _ , i.e., P(b = -1) ~ 1 - c, the decision b = -1 should be done. If c < P(b = +1) < c+, then an additional analysis should be performed. My basic conjecture was that cognitive systems developed the ability to use nonclassical LTP for decision making:

P(b

= ±lIC) =

P(a

= +lIC)P(b = ±lla = +1) + P(a = -lIC)P(b = ±Ia = -1) + 2 cos B± jI4,

where II± = P(a = +lIC)P(b = ±Ia = +l)P(a = -lIC)P(b = ±Ia = -1). This formula (the classical LTP perturbed by so called interference term) can be easily derived in the formalism of quantum mechanics where observabIes a and b are represented by self-adjoint operators ll . We can derive 4 it without appealing to the Hilbert space formalism, namely, by controlling contextual dependence of probabilities. We recall that mathematically contextuality of probabilities is equivalent to non-Kolmogorovness of probabilistic data.

2.2. Violation of LTP from contextuality of probabilities In particular, LTP is violated in quantum physics, in the two slit experiment. The b-observable gives the position of photon on the registration screen. If one likes to couple coming considerations to the decision making, she can consider the problem of prediction of the position of photon's registration: to predict the probability that photon hits a selected domain on the registration screen.

213

To make the b-variable discrete, we split the registration screen into two domains say B+ and B_ and if a photon makes the black dot in B+, we set b = +1, and in the same way we define the result b = -l. The a-variable describes the slit which is used by a particle; say a = +1 the upper slit and a = -1 the lower slit. For simplicity, we set P( a = + 1) = P(a = -1) = 1/2, so the source is placed symmetrically with respect to slits. Consider three different experimental contexts: C : both slits are open. We can find P(b = +1) and P(b = -1) from the experiment as the frequencies of photons hitting the domains B+ and B_, respectively. C+' : only one slit, labeled by a = +1, is open. We can find P(b = jla = ±1, the frequencies of photon hitting B+ and B_, respectively.

=

+l),j

: only one slit, labelled by a = -1, is open. We can find P(b = jla = ±1, the frequencies of photon hitting B+ and B_, respectively. If we put these frequency-probabilities, collected in the three real experiment, we see that LTP is violated. The classical LTP cannot be used to predict, e.g., the probability P(b = +1) that photon hits B+ under the context C (both slits are open) on the basis of probabilities P(b = jla = ±1), that photon hits B+ under contexts (only one respective slit is open). C~

-l),j

=

C±

2.3. Violation of LTP in cognitive science Data obtained in experiments of cognitive psychology (Tversky-Shafir, Croson, see book l for details) demonstrated violation of LTP. As in the above analysis of the two slit experiment, incompatible contextual structures can be easy found in all these cognitive experiments. We emphasize that here violation of LTP is even more general than described by the Dirac-von Neumann formalism of the standard quantum mechanics (as, e.g., in the two slit experiment). Thus processing of information in cognitive systems is even more nonclassical than in quantum physics. One of possibilities to proceed is to use quantum Markov chains, see L. Accardi, A. Khrennikov, and M. Ohya l2 : a concrete quantum Markov chain reproducing data from Tversky-Shafir experiment was constructed. We also mention experiments on recognition of ambiguous figures l , which were designed on the basis of the author's paper 6 . It seems that their results also can be reproduced on the basis of quantum Markov chains. Recently M. Asano, A. Khrennikov, and M. Ohya 2 proposed a generalized quantum model based on so called liftings of density operators modeling the process of decision making in the PD-type games.

214

2.4. Wave representation of information in the brain? One may come with the conjecture that decision making with nonclassical LTP is based on a kind of the wave representation of information in the brain. The brain is full of classical electromagnetic radiation. May be the brain was able to create QLR of information via classical electromagnetic signals, cf. K.-H. Fichtner, L. Fichtner, W. Freudenberg and M. Ohya 13 . Classical waves produce superposition and violate LTP. However, quantum information processing is based not only on superposition, but also on ENTANGLEMENT. It is the source of superstrong nonlocal correlations. Correlations are really superstrong - violation of Bell's inequality. Can entanglement be produced by classical signals? Can quantum information processing be reproduced by using classical waves? The answer is positive. The crucial element of coming wave model is the presence of the random background field (in physics fluctuations of vacuum, in the cognitive model- background fluctuations of the brain). Such a random background increases essentially correlations between different mental functions, generates nonlocal presentation of information. We might couple these nonlocal representation of information to the binding problem: "How the unity of conscious perception is brought about by the distributed activities of the central nervous system. "

3. Prequantum classical statistical field theory: noncomposite systems

Quantum mechanics (QM) is a statistical theory. It cannot tell us anything about an individual quantum system, e.g. , electron or photon. It predicts only probabilities for results of measurements for ensembles of quantum systems. Classical statistical mechanics (CSM) does the same. Why are QM and CSM based on different probability models? In CSM averages are given by integrals with respect to probability measures and in QM by traces. In CSM we have:

(f)Jl-

=

1M f(¢)djL(¢),

where M is the state space. In probabilistic terms: there is given a random vector ¢(w) taking values in M. Then (f)", = Ef(¢(w)) = (f)w In QM the average is given by the operator trace-formula:

(A)p = TrpA.

215

This formal mathematical difference induces the prejudance on fundamental difference between classical and quantum worlds. Our aim is to show that, in spite of the common opinion, quantum averages can be easily represented as classical averages and, moreover, even correlations between entangled systems can be expressed as classical correlations (with respect to fluctuations of classical random fields).

Einstein's dreams: Albert Einstein did not believe in irreducible randomness, completeness of QM. He dreamed of a better, so to say "prequantum", model 14 : 1) Dream 1. A mathematical model reducing quantum randomness to classical. 2) Dream 2. Renaissance of causal description. 3) Dream 3. Instead of particles, classical fields will provide the complete description of reality - reality of fields : "But the division into matter and field is, after the recognition of the equivalence of mass and energy, something artificial and not clearly defined. Could we not reject the concept of matter and build a pure field physics? What impresses our senses as matter is really a great concentration of energy into a comparatively small space. We could regard matter as the regions in space where the field is extremely strong. In this way a new philosophical background could be created. 11 The real trouble of the prequantum wave model (in the spirit of early Schrodinger) are not various NO-GO theorems (e.g., the Bell inequality 4,11,15), but the problem which was recognized already by Schrodinger. In fact, he gave up with his wave quantum mechanics, because of this problem: A composite quantum system cannot be described by waves on physical space! Two electrons are described by the wave function on R6 and not by two wave on R3. Einstein also recognized this problem 14 : "For one elementary particle, electron or photon, we have probability waves in a three-dimensional continuum, characterizing the statistical behavior of the system if the experiments are often repeated. But what about the case of not one but two interacting particles, for instance, two electrons, electron and photon, or electron and nucleus? We cannot treat them separately and describe each of them through a probability wave in three dimensions ... "

PCSFT: Einstein's Dreams 1 and 3 came true in PCSFT (but not Dream 2!) - a version of CSM in which fields play the role of particles. In particular, composite systems can be described by vector random fields,

216

i.e., by the Cartesian product of state spaces of subsystems and not the tensor product. The basic postulate of PCSFT can be formulated in the following way: A quantum particle is the symbolic representation of a "prequantum" classical field fluctuating on the time scale which is essentially finer than the time scale of measurements. The prequantum state space M = L 2 (R 3 ), states are fields ¢ : R3 -7 R; "electronic filed", "neutronic field", "photonic field" - classical electromagnetic field. An ensembles of "quantum particles" is represented by an ensemble of classical fields, probability measure Jt on M = L 2 (R 3 ), or random field ¢( x, w) taking values in M = L2 (R 3 ). For each fixed value of the random parameter w = wo, X -7 ¢(x, wo) is a classical field on physical space. Density operator = covariance operator: Each measure (or random field) has the covariance operator, say D. It describes correlations between various degrees of freedom. The map p f---+ D = p is one-to-one between density operators and the covariance operators of the corresponding prequantum random fields in the case of noncomposite quantum systems. In the case of composite systems this correspondence is really tricky. Thus each quantum state (an element of the QM formalism) is represented by the classical random field in PCSFT. The covariance operator of this field is determined by the density operator. We also postulate that the prequantum random field has zero mean value. These two conditions determine uniquely Gaussian random fields. We restrict our model to such fields. Thus by PCSFT quantum systems are Gaussian random fields. Quantum observable = quadratic form: The map A -7 fA (¢) = (A¢, ¢) establishes one-to-one correspondence between quantum observabIes (self-adjoint operators) and classical physical variables (quadratic functionals of the prequantum field). Coincidence of averages: It is easy to prove that following equality holds:

In particular, for a pure quantum state 7/J, consider the Gaussian measure with zero mean value and the covariance operator p = 7/J07/J (the orthogonal projector on the vector 7/J), then

217

This mathematical formula coupling integral of a quadratic form and the corresponding trace is well known in measure theory. Our main contribution is coupling of this mathematical formula with quantum physics. This is the end of the story for quantum noncomposite systems, e.g., a single electron or photon 7,8. Beyond QM: In fact, PCSFT not only reproduces quantum averages, but it also provides a possibility to go beyond QM. Suppose that not all prequantum physical variables are given by QUADRATIC forms, consider more general model, all smooth functionals f (¢) of classical fields. We only have the illusion of representation of all quantum observables by self-adjoint operators. The map f f-* A = 1"(0)/2 projects smooth functionals of the prequantum field (physical variables in PCSFT ) on self-adjoint operators (quantum observables). Then quantum and classical (prequantum) averages do not coincide precisely, but only approximately:

1M fA (¢)dfJ(¢)

=

TrpA

+ O(t/T),

where T is the time scale of measurements and t the time scale of fluctuations of prequantum field. The main problem is that PCSFT does not provide a quantative estimate of the time scale of fluctuations of the prequantum field. If this scale is too fine, e.g., the Planck scale, then QM is "too good approximation of PCSFT", i.e., it would be really impossible to distinguish them experimentally. However, even a possibility to represent QM as the classical wave mechanics can have important theoretical and practical applications. And in the present paper we shall use the mathematical formalism of PCSFT to model brain's functioning. Although even in this case the choice of the scale of fluctuations is a complicated problem, we know that it is not extremely fine; so the model can be experimentally verified (in contrast to Roger Penrose we are not looking for cognition at the Planck scale!).

4. Composite systems In CSM a composite system 8 = (81 ,82 ) is mathematically described by the Cartesian product of state spaces of its parts 8 1 and 8 2 . In QM it is described by the tensor product. Majority of researchers working in quantum foundations and, especially quantum information theory, consider this difference in the mathematical representation as crucial. In particular, entanglement which is a consequence of the tensor space representation is

218

considered as totally nonclassical phenomenon. However, we recall that Einstein considered the EPR-states as exhibitions of classical correlations due to the common preparation. PCSFT will realize Einstein's dream on entanglement. Let S = (SI, S2), where Si has the state space Hi ~ complex Hilbert space. Then by CSM the state space of S is HI X H 2. By extending PCSFT to composite systems we should describe ensembles of composite systems by probability distributions on this Cartesian product, or by a random field

¢(x,w)

=

(¢I(X,W),¢I(X,W)) E HI

X

H2·

In our approach each quantum system is described by its own random field: Si by ¢i(X, w), i = 1,2. However, these fields are CORRELATED ~ in completely classical sense. Correlation at the initial instant of time t = to propagates in time in the complete accordance with laws of QM. There is no action at the distance. It is a purely classical dynamics of two stochastic processes which were correlated at the beginning. (In fact, the situation is more complex: there is also the common random background, vacuum fluctuations; we shall come back to this question a little bit later). Operator realization of wave function: Consider now the QMmodel, take a pure state case: I]i E HI @ H 2 . Can one peacefully connect the QM and PCSFT formalisms? Yes! But I]i should be interpreted in completely different way than in the conventional QM. The main mathematical point: I]i is not vector! It is an operator! It is, in fact, the non-diagonal block of the covariance operator of the corresponding prequantum random field: ¢(x, w) E HI X H 2. The wave function I]i(x, y) of a composite system determines the integral operator:

W¢(x) =

J

I]i(x, y)¢(y)dy.

We keep now to the finite-dimensional case. Any vector I]i E HI @ H2 can be represented in the form I]i = 'L,';=1 'l/Jj @ Xj, 'l/Jj E HI, Xj E H 2, and it determines a linear operator from H2 to HI m

W¢

= ~)¢'Xj)'l/Jj,

¢ E H2·

(2)

j=1

I]i* acts from HI to H2 : W*'I/J = WW* : HI --+ HI and W*W : H2 --+ H2

Its adjoint operator

'L,';=I('I/J,'l/Jj)Xj,'I/J

E

HI. Of course, and these operators are self-adjoint and positively defined. Consider the density operator corresponding to a pure quantum state, p = I]i @ I]i. Then the operators of the partial traces p(1) == TrH 2 P = WW* and p(2) == TrH,p = W*W.

219

Basic equality: Let \II EE H~® H2 be normalized by 1. Then, for any pair of linear bounded operators A j : Hj ---> Hj , j = 1, 2, we have:

(3) This is a mathematical theorem 9 ; it will playa fundamental role in further considerations. Coupling of classical and quantum correlations: In PCSFT a composite system 8 = (81,82) is mathematically represented by the random field ¢(w) = (¢l(W), ¢2(W)) E H1 x H 2. Its covariance operator D has the block structure

where Dii : Hi ---> Hi, Dij : Hj ---> Hi . The covariance operator is selfadjoint. Hence D;i = D ii , and Di2 = D 21 . Here by the definition: (DijUj , Vi ) = E(Uj, ¢j(W))(Vi, ¢i(W)) , Ui E Hi, Vj E Hj . For any Gaussian random vector ¢( w) = (¢1 (w), ¢2 (w )) having zero average and any pair of operators Ai E L s(Hi ), i = 1,2, the following equality takes place: (fA " fA 2 )q, == EfA , (¢ 1(W))fA 2 (¢2(W)) = (TrDllAd(TrD22A2) + TrD12A2D21A1. We remark that TrDiiAi = EfAi (¢i(W)) , i = 1,2. Thus we have fAlfA2 = EfAl EfA2 +TrD12A2D21A1. Consider a Gaussian vector random field such that D12 = \ii :

or, for covariance of two classical random vectors f A, , f A 2 , we have: cov (fA " fA 2 ) = (A1 ® A 2)w. We have the following equality for averages of quadratic forms of coordinates of the prequantum random field describing the state of a composite system: EfA,(¢i)(W)) = TrDiiAi. We want to construct a random field such that these averages will match those given by QM. For the latter, we have: (A 1)w = (A1 ®h\Il, \II) = Tr(\II\II*)A1; (A2)W = (h®A2\I1, \II) = Tr(\ii*\ii)k :r::r:oI:a::::e:th(e

\ii}n:t~o~er)a~o:~:=~r: ~hi~' :~:::sr i:s :Oo~l:o:;ti:::~ \II* \II*\II

defined! It could not determine any probability distribution on the space of classical fields. We modify it to obtain a positively defined operator. Originally this modification had purely mathematical reasons, but there are deep physical grounds for it.

220

The operator D

-

w-

+ Ef W ) ( WW* W* W*\[r + Ef

is positively defined if

E

>

o is large enough.

Hence, it determines uniquely the Gaussian measure on the space of classical fields. Suppose now that ¢(w) is a random vector with the covariance operator Dw. Then

(5) This relation for averages and relation (4) provide coupling between PCSFT and QM. Quantum statistical quantities can be obtained from corresponding quantities for classical random field: "irreducible quantum randomness /I is reduced to randomness of classical prequantum fields. Vacuum fluctuations: The additional term given by the unit operator in the diagonal blocks of the covariance operator of the prequantum vector field corresponds to the field of the white noise type. Such a field can be considered as vacuum fluctuations, vacuum field. PCSFT induces the following picture of reality: Fluctuations of the vacuum field are combined with random fields representing quantum systems. Since we cannot separate, e.g., electron from the vacuum field, we cannot separate totally any two quantum systems. Thus all quantum systems are "entangled" via the vacuum field. WHITE NOISE is the basis of everything in Nature - Hida's Dream.

QM as renormalization formalism: Averages given by the mathematical formalism of traditional QM are obtained as renormalizations of classical averages, see (5). Thus the QM-formalism can be considered as a method of renormalization of averages with respect to vacuum fluctuations: it cancels the contribution of the vacuum field. Such a renormalization is especially important in the case of observables of the nontrace class. Here the contribution of the background field is infinite. Thus it should be subtracted from the classical average, cf. with renormalization procedures of QFT. Superstrong quantum correlations: In PCSFT such correlations (violating Bell's inequality) are due to the presence of the vacuum field. The off-diagonal term Wcan be so large only if the diagonal terms are completed by the contribution of the vacuum filed. Mathematics tells us this. Thus they are so strong, because the vacuum field really couple any two systems; they are in the same fluctuating space. Space is a huge random wave; quantum systems are spikes on this wave;

221

they are correlated via this space-wave. Thus quantum correlations have two contributions: 1) initial preparation; 2) coupling via the vacuum field. The picture is pure classical... In this model the vacuum field is the source of additional correlations. It seems that this classical vacuum field is an additional (purely classical) quantum computational resource. 5. QL processing in the brain Consider two time scales (te, t pe ) : tpe « t e , cognitive and precognitive. Take a signal in the brain oscillating on the time scale tpe' We speculate that the brain has an integration device integrating these fluctuations over the interval te. The result of such integration is considered as a cognitive image. In this paper we do not present a concrete procedure of integration and, hence, creation of cognitive images from random fluctuations.

5.1. Multiplicity of time scales in brain and cognitive QLR The main lesson from the experimental and theoretical investigations on the temporal structure of processes in brain is that there are various time scales. They correspond to (or least they are coupled with) various aspects of cognition. Therefore we are not able to determine once and for ever the cognitive time scale te ("psychological time"). There are a few such scales. We shall discuss some evident possibilities. It is well known that there are well established time scales corresponding to the alpha, beta, gamma, delta, and theta waves. Let us consider these time scales as different cognitive scales. For the alpha waves we choose its upper limit frequency, 12 Hz , and hence the te,a ~ 0.083 sec. For the beta waves we consider (by taking upper bounds of frequency ranges) three different time scales: 15 Hz, t e ,(3, low ~ 0.067 sec. - low beta waves, 18Hz, t e ,(3 ~ 0.056 sec. - beta waves, 23 Hz t e ,(3, high ~ 0.043 sec. - high beta waves. For gamma waves we take the characteristic frequency 40 Hz and hence the time scale t e " ~ 0.025 sec.

5.2. Precognitive time scale Our choice of the precognitive (very fine) time scale tpe will be motivated by so called Taxonomic Quantum Model, see proposed by Geissler et aI, see, e.g., paper 16 , for representation of cognitive processes in the brain (which was developed on the basis of the huge experimental research on time-mind relation. They found that information processing in cognitive

222

tasks is based on time scales Qq = q x Qo. where spc = Qo = 4.6ms. We choose Qo as the unit of the precognitive time scale. This corresponds to frequencies ~ 220 Hz. Under such an assumption about the precognitive scale we can find the measure of QL-ness for different EEG bands. For the alpha scale, we have "'a. = tQo ~ 0.055. For the beta scales, we have: "'c f3 low ,

=

Qot

' c,j3, low

~ 0.069;

"'c f3 '

~,atQo ~ 0.082; c,/3

"'c f3 high '

,

=

Qot C,{3,h lgh

~ 0.107.

For the gamma scale we have: "', = tQo ~ 1.84. Smaller '" correspond to c,-, larger integration time in the process of creation of cognitive images; less images can be created and processed. "Thinking through the alpha waves" is essentially less advanced than, e.g., "thinking through the gamma waves" I would like to thank M. Ohya, L. Accardi, M. Asano, K.-H.Fichtner, W.Freudenberg for fruitful discussions. References 1. A. Khrennikov, Ubiquitous quantum structure: from psychology to finance, Springer, Heidelberg- Berlin-New York, 2010. 2. M. Asano, A. Khrennikov , M. Ohya, Foundations of Physics, to be published 2010. 3. A. Khrennikov, J. Phys.A: Math. Gen. 349965-9981 (2001). 4. A. Khrennikov, Contextual approach to quantum formalism (Fundamental Theories of Physics). Springer, Heidelberg- Berlin-New York, 2009. 5. A. Khrennikov, BioSystems 84, 225- 241 (2006). 6. A. Khrennikov, Open Systems and Information Dynamics 11 (3), 267-275 (2004) . 7. A. Khrennikov, J. Phys. A: Math. Gen. 38, 9051-9073 , 2005. 8. A. Khrennikov, Physics Letters A , 372 , 6588-6592 (2008). 9. A. Khrennikov, Europhysics Letters 88, 40005 (2009). 10. A. Khrennikov, J. Consciousness Studies 15, 10-25 (2009). 11. A. Khrennikov, Interpretations of probability, VSP International Science Publishers, Utrecht (1999); second addition (completed) De Gruyter, Berlin, 2009. 12. L. Accardi, A. Khrennikov , M. Ohya, Open Systems and Information Dynamics, 16, 441-443 (2009). 13. K.-H.Fichtner, L.Fichtner, W.Freudenberg and M.Ohya, On a quantum model of the recognition process. QP-PQ:Quantum Prob. White Nois e Analysis 21, 64-84 (2008). 14. A . Einstein and L. Infeld , Evolution of Physics: The Growth of Ideas from Early Concepts to Relativity and Quanta, Simon and Schuster, 1961. 15. A. Khrennikov, Theoretical and Mathematical Physics 157, 1448-1460 (2008). 16. B. Schack, N. Vath, H. Petsche, H. -G. Geissler, E. Mller, Int. J. Psychophysiology 44, 143-163 (2002).

Quantum Bio-Informatics IV eds. L. Accardi, W. Freudenberg and M. Ohya © 2011 World Scientific Publishing Co. (pp. 223-236)

ENTANGLEMENT MAPPING VS. QUANTUM CONDITIONAL PROBABILITY OPERATOR

DARIUSZ CHRUSCINSKI, ANDRZEJ KOSSAKOWSKI

Institute of Physics, Nicolaus Copernicus University Grudziadzka 5/7, 87-100 Torun, Poland TAKASHI MATSUOKA

Faculty of Management of Administration and Information Tokyo University of Science, Suwa Toyohira 5000-1, Chino City, Nagano 391-0292, Japan MASANORIOHYA

Department of Information Science, Tokyo University of Science Yamazaki 2641, Noda City, Chiba 278-8501, Japan The relation between two methods which construct the density operator on composite system is shown. One of them is called an entanglement mapping and another one is called a quantum conditional probability operator. On the base of this relation we discuss the quantum correlation by means of some typ es of quantum entropy.

1. Introduction

In quantum information theory it is crucial to make clear the following two problems. The first one concerns the study of classifying quantum states of composite systems. In classical description of a physical compound system its correlation can be represented by a joint probability measure or a conditional probability measure. In quantum case a quantum state of a composite system, i.e. a compound state describes a correlation between its marginal states. However, in quantum system, it is known that the joint probability and the conditional probability do not generally exist, which is an essential difference from classical system 20 ,22. The typical example of such difference is the existence of entangled states in quantum system. The difference means that one have to deal more carefully not only with the correlation of entangled state but also that of separable one. From 223

224

this point of view to give the proper classification of quantum states is of primary importance. Hence, one needs an appropriate measure of quantum correlations. We start with notions of positivity: the so-called complete positivity (CP) and complete co-positivity (CCP). Let A and B be C*-algebras (with a unit). A linear map X : A 1-+ B is CP if and only if

(1) is positive for all n. Here Mn (A) stands for n x n matrices with entries from A. A linear map X : A 1-+ B is CCP if and only if

(2) is positive for all n. Every n-co-positive map is positive but not necessarily complete positive even if it is complete co-positive, unless B is Abelian, in which case a positive map is both complete positive and complete copositive. Belavkin and Ohya gave a rigorous construction of quantum compound states by means of a CCP map called entanglement mapping4 ,5. We can construct a compound state by applying the entanglement mapping to Jamiolkowski's isomorphism. On the other hand Kossakowski et al. introduced the notion of quantum conditional probability operator, QCPO for short, by means of a CP mapl. If one of marginal states is given, then we can also construct the compound state by operating the marginal state by QCPO. In the present paper we show the relation between the entanglement mapping and QCPO, i.e. the relation between the CCP map and the CP map. This paper is organized as follows: In sections 2 and 3 the definition of entanglement mapping and QCPO are reviewed. In the middle of 1990s Horodecki family and Peres gave a classification of compound states by introducing the criteria so called a PPT (Partial Positive Transpose) condition l2 ,2l. Here we also review the relation between the entanglement mapping and PPT condition l5 ,l8, and the relation between QCPO and PPT condition 1 . The section 4 gives the relation of such two methods. We show that the compound state by entanglement mapping is related to QCPO via the similar equation to classical Bayesian relation. In the section 5 we review the two types of quantum entropies, so called the quantum mutual entropy and the quantum conditional entropy, and such entropies are applied to some examples of entanglement mapping. Finally, from the observation

225

of the above computational examples the meaning of such entropies are discussed on the base of quantum Bayesian relation. The above argument can be formulated at general C* -algebraic setting 4 ,5,15,17,18. However, for simplicity, only the finite-dimensional case will be considered here.

2. Entanglement mapping and its classification Let us consider two quantum systems (Hk, A k , S (A k )h=I,2 where Hk is a Hilbert space given by Hk = (Cn, Ak = B (Hk) stands for the algebra of complex k x k matrices and S (Ak) stands for the set of all states on A k . Then the composite system (H, A, S) is given by

H

=:0

HI 0H2, A

=:0

B (HI 0H2) = Al 0 A 2, S

=:0

S (A) = S (AI 0 A 2) .

Notice that

S

::J conv

(S (Ad 0 S (A 2 ))

.

It was mentioned that conv(S (Ad 0 S (A 2 )) are called separable states and the subset of states S\conv(S (Ad 0 S (A 2 )) is called the set of entangled states, i.e. S = Sent U Ssep' We are interested in the special subset of S,

SpPT=:O{WES;w o (10T) ES},

(3)

where T is stands for transposition. Such states are called partial positive transposition (PPT) states I2 ,21. Clearly S ::J SPPT ::J Ssep.

In this section we will review how to construct the compound state by means of entanglement mapping and we will show that the entanglement mapping gives the same classification of states with PPT condition. For a normal state w E S there exist a density matrix B such that

w(a0b) = Tr(a0b)B,a E AI,b E A 2 .

(4)

The state w can be written as

(5) where ¢ is a linear map from A2 to Al given by ¢ (b) =:oTr 2 (10 b) BE AI, and its dual map ¢* from Al to A2 given by ¢* (a) =:oTrI (a 01) B E A 2 • In (5) the partial trace with respect to Hk is denoted by Trk (.). It is clear that the marginal densities of B are given by

(6)

226

Belavkin and Ohya revealed that such maps can be reconstructed by Hilbert-Schmidt operator, which is called the entangling operator, and they showed that both ¢ and ¢* are complete co-positive, but not always complete positive on general C* -algebraic setting4 ,5. For example, if w is a pure entangled state, then its entanglement mappings are not CPo Here we recall the necessary and sufficient condition of CP and CCP in the case of finite dimension. Let Mn denote the algebra of complex n x n matrices and let I: [Mn, MmJ be the complex space of linear maps from Mn to Mm. We recall the isomorphism W : I: [Mn, MmJ f-> Mn 0 Mm 8,16 ,24: For each linear map X E I: [Mn, MmJ one defines n

WIP'+ (X) = "L)ek) (ezl 0 X (Iek) (ezl) = (1 0 X) lP' +

(7)

k,l and n

WJJ (X) = ~) ek ) (e11 0 X (leI) (ekl) = (1 0 X)Jf k,l

(8)

where {Iek) (ell} is an orthonormal base of Mn. The map (7) is called n

the Choi's isomorphism8 with lP' + =

L

k,l

lek) (ezl 0 lek) (ell which gives the

maximally entanglement state (not normalized), and the map (8) is called n

the Jamiolkowski isomorphism 14 with Jf =

L

leI) (ekI 0 Iek) (ezl.

k,l

One has the following Lemma 2.1.

8 ,16,24

For X

E

I: [Mn, MmJ the following statements hold:

(1) X is CP iff WIP'+ (X) 2: (2) X is CCP iff WJJ (X) 2:

o. o.

We apply Lemma 2.1 to entanglement mapping ¢ and its dual ¢*. The density matrix () in (4) can be represented by matrix elements as n

()=

L

eij :a(3 lei)(ejI 0

I!a)(f(3 1

(9)

i ,j ,a ,/3 = l

where{l ei) (ejl} (resp. {Ifa) (f(3 I} ) is a standard base of A1 (resp.A 2 ) , and e ij :a(3 is given by e ij :a(3 = (e i 0 fa , eej 0 f (3 ). Using this representation ¢

227

and ¢* are given by

¢ (b) = Trd1 ® b) e n

L eij:a(3 U(3, bfa} lei} (ej I,

=

(10)

a,(3=l and

= Trda ® 1) e

¢* (a)

n

=

L

eij :a(3 (ej,aei) Ifa} U(3I·

(11)

i,j=l So that we have n

L

W.Jf (¢*) =

(Iek) (ell) ® ¢* (lei) (ekl)

k.l=l n

L

eij:a(3l ei} (ejl ® Ifa) U(31 = e

(12)

i,j,a,(3=l

e

Namely the entanglement ¢* reconstructs its density matrix via the Jamiolkowski isomorphism. This fact means that ¢* is always CCP. In the similar way we can show also the complete co-positivity of ¢. On the other hand we apply ¢ to the Choi's isomorphism. Then we have n

k.l=l n

L eij:a(3l ei} (ejl ® If(3) Ual = (1 ® T) e

(13)

i,j,a,(3=l The positivity of WIP'+ (¢) is equivalent to the complete positivity of ¢ and it is also equivalent to the PPT condition of

e.

Theorem 2.1.

e E SPPT

if and only if the map ¢* is CF.

Remark 2.1. Theorem 2.1 was proved at C*-algebraic general setting 15 ,18. If an entanglement mapping ¢*, i.e. a normalized CCP map, is given, then one can construct a compound state as

e¢

n

n

k.l=l

k.l=l

228

3. Quantum conditional probability operator and its classification

In this section we review another construction of compound state by Kossakowski et all. For a given () E S with p =Tr 2 () one can define the operator

(15) which has the following properties 7r1! ~

(16)

0,

(17) and we assume that p > 0, that is, p represents a faithful state. It follows from (16) and (17) that the operator 7r1! is the quantum analogue of a classical conditional probability. Indeed, in the case A is an Abelian algebra, 7r1! coincides with a classical conditional probability. Definition 3.1. An operator 7r E A is called a quantum conditional probability operator (QCPO) if 7r satisfies condition (16) and (17).

One easily finds the following formula n

7r
L

=

'P (Ifk)

Ull) ® Ilk) Ull

(18)

k.l=l

where 'P is a CP unital map from A2 to A 1 , i.e. , 'P (1) = 11. Using Lemma 2.1 and unitality of'P it is easy to check that 7r

()
=

L

p~ 'P (lfk ) Ull) p~ ® Ifk ) Ull·

(19)

k .l= l

Then we apply Lemma 2.1 (2) to the map A (-) == p ~ 'P (.) p~: n

W.dA) =

L

p ~ 'P (lfk ) Uti) p~ ®

1M (Ik I =

(1 ® T) ()
k.l = l

Hence Corollary 3.1.

1()

if and only if the map 'P is CCP.

(20)

229

4. The relation between entanglement mapping and QCPO Belavkin and Dai6 gave the following decomposition of an entanglement mapping.

Lemma 4.1. Every entanglement mapping ¢ with ¢ (1) position

= P has a decom(21)

where zp is a OP unital map to be found as a unique solution to

zpC) = p-!¢OT(')p-!,

(22)

Now we can show the following

Theorem 4.1. If a compound state e given by (14) has a marginal state P = Tr2 e , then e is represented by

(23)

Proof. We apply the decomposition (21) to e. Then n

e

=

L

¢ (Ifk) (!II)

o IfI) Ukl

k.l=l n

=

L p!zp

T (I!h) (11) p!

0

o liz) Ukl

k.l=l n

=

L

p!zp(lfl) Ukl)p!

o

IfI) (!hI

k.l=l

In the opposite direction we have

(p!

(1)

n

1f
(p!

(1) = L

p!zp(lfk) (11)p! 0lfk) Ull

k.l=l k.l=l n

=

L

k.l=l

¢ (liz) Ukl) 0lfk) Ull = e.

o

230

The relation (23) can be regarded as the quantum analogue of classical Bayesian relation. In the next section we extend classical information theory to quantum system on the base of the quantum Bayesian relation (23).

5. Mutual entropy and conditional entropy vs. quantum entanglement In classical description of a physical compound system its correlation can be represented by a joint probability measure or a conditional probability measure. In classical information theory we have proper criteria to estimate such correlation, which are so-called the mutual entropy and the conditional entropy given by Shannon. The mutual entropy is given as the relative entropy of correlated joint probability and non-correlated one. This means that it represents the correlation included in the joint probability Tij as the distance from the non correlated product joint probability Piqj, where Pi and qj are marginal probabilities, in the sense of relative entropy. In other words, the mutual entropy means the common information included in marginal random variables X and Y. On the other hand, the conditional entropy is given by the average of the entropy of conditional probability which means the uncertainty still remaining in X (resp. Y) after observing Y (resp. X). We extend the classical entropies to a quantum system.

Definition 5.1. Let ¢ be an entanglement mapping with p 0" = ¢* (1) . One defines 4 ,5

= ¢ (1) and

1¢(p, 0") == 8(8¢, p ® O")

= Tr8 ¢ (log 8¢ -

log p ® 0")

(24)

where 8 (', .) is the Araki-Umegaki relative entropy. One calls 1¢ (p, 0") the quantum mutual entropy. 7, 10. The quantum mutual entropy can be computed as follows: 1¢ (p, 0") = Tr8¢ (log8¢ -logp ® 0")

= Tr8 ¢ (log 8¢ -

log p ® 1 - log 1 ® 0")

= -8 (8¢) - Tr 2 8¢ log p ® 1 - Tr 1 8¢ log 1 ® 0" =8(p)+8(0")-8(8¢) .

(25)

231

By using the quantum mutual entropy one also defines the quantum conditional entropies 4 ,5:

S (alp) == S (a) - I (p, a) = S (8
(26)

= S (8
(27)

S (pia) == S (p) - I (p, a)

Remark 5.1. The above quantities are discussed also by Cerf and Adami 7 , Horodeckisll, Henderson and Vedral 13 , Groisman et al. 10. Example 5.1. (Product state). pTr2ab, ¢* (a) = aTr1pa, we have 8

=

For entanglement mappings ¢ (b)

p 0 a.

Then

I (p , a)

= S (p) + S (a) - S (8
S (alp) = S (a) , S (pia) = S (p) .

(28)

(29)

The above result clearly means that the product state has no correlation between its marginal states. The quantum mutual entropy I (p, a) measures the distance (correlation) between the correlated state and the product state. In quantum system we have two types of correlated states. The first one is a separable correlated state, and second one is an entangled correlated state. Example 5.2. (Separable correlated state). For entanglement mappings ¢ (b) = '2:. Pi Pi Traib, ¢* (a) = '2:.PWiTrpia , where Pi ~ 0, '2:.Pi = 1, we have

(30) with p = ¢ (1) = '2:.PiPi' ¢* (1) = '2:.PWi. Then we have the following inequalities3 ,4, 5

0::; I (p, a) ::; min {S (p) , S (a)} ,

(31)

S (alp) > 0, S (p ia) > 0.

(32)

232

Example 5.3. (Separable perfect correlated state). For entanglement mappings ¢(b) = LPi lei) (eil (fi,bii ), ¢* (a) = LPi 1M (fil (ei,aei) we have

8¢ = I>i lei) (eil 0 I!i) (fil with p

= ¢ (1) = LPi lei) (eil, (J = 1¢ (p, (J) = 5 (p)

= LPi 1M (fil. Then.

¢* (1)

+ 5 ((J)

- 5 (8¢) = 5 (p),

(33)

where 5 (p) = 5 ((J) = 5 (8¢) = - LPi logpi. This correlation corresponds to a perfect correlation in the classical scheme. Example 5.4. (Pure entangled correlated state). tanglement mappings ¢(b) LAi"Xj lei) (ejl (fj,bM, 2 LAiAj 1M (fJl (ej,aei) , where Ai E C, L IAil = 1, we have

8¢ =

L Ai"Xj lei) (ej I 0

For en¢* (a)

Iii) (fJ I = IW) (WI,

where IW) = L Aiei 0 k and its marginal states are given by p L IAil 2 lei) (eil, (J = ¢* (1) = L IAil 2 lii) (fil. Then

1¢ (p, (J) = 5 (p)

+ 5 ((J)

= ¢ (1) =

- 5 (8¢)

= 25 (p), 5¢ ((Jlp) = 5¢ (pl(J) = -5 (p) , where 5 (p)

(35)

= 5 ((J) = - L IAil2log IAil2 .

In classical system the mutual entropy is always smaller than its marginal entropies, and the conditional entropy is always positive. So that the correlation of pure entangled state has a non-classical property. We introduce another criterion to measure the correlation of compound states. Definition 5.2. For an entanglement mapping ¢ with p ¢* (1), we defines 1

D¢ (pp) == 1¢ (p, (J) - "2 (5 (p) 1

+ 5 ((J))

= "2 (5 (p) + 5 ((J)) - 5 (8 ¢)

= ¢ (1), (J = (36)

(37)

233

Remark 5.2. Actually,

DEN(B; p, a)

:=

-Dq,(p, a)

was called degree of entanglement 4 ,5,19. Suppose now that we have two entanglement mappings rP1 and rP2 such that p = rPk (1) and a = rP~ (1) (for k = 1,2). Definition 5.3. One says that rP1 has stronger correlation than rP2 if

Dq" (p,a) > Dq,2 (p,a).

(38)

One shows Proposition 5.1. hold:

2,19 If

Bq, is a pure state, then the following statements

(1) Bq, is a pure entangled state iff Dq, (p,a) > O. (2) Bq, is a pure separable state iff Dq, (p,a) = O. It is well known 23 that if B is PPT, then

S(B) - S(p)

~

0,

S(B) - S(a)

~

O.

where p and a are the marginal states of B. Proposition 5.2. If Bq, is a mixed PPT state, then

Remark 5.3. Interestingly, there exist quantum entangled states with weaker correlations than some separable states in the sense of Definition 5.3 (see Hirota et al. in this proceedings). Remark 5.4. Let X = {Xi}i=l,. .. ,n and Y = {Yj}j=l, ... ,m be random variables with probability distributions P = (Pi) and Q = (qj), and let (X x Y = {(Xi, Yj)} , R = (r ij)) be their compound system. Then the definition of mutual entropy I (X, Y) is given by

(39) Now the joint probability rij is represented as rij =p(jli)Pi

(40)

234

where P (ilJ) is a transition probability, Using this classical Bayesian relation the mutual entropy I (X, Y) can be represented by r· .

I (X, Y)

= Lrij log ---2.L ·. ' ,J

Piqj

" ('I = '~P J Z') Pi 1og p(jli)pi ·. ',J

Piqj

" ( 'I·) 1 p(jli) = '~P J Z Pi og '" ('Ik) · . ~P J Pk ' ,J

= I(P ;A*) ,

(41)

k

where we denote a transition probability matrix (p (j Ii)) by A*, and we call it a channel. In this scheme we call the probability distribution P as an input state, and call the probability distribution Q as an output state given by ( 42)

and this mutual entropy I (P; A*) can be regarded as a measure of transmitted information through the channel A* from an input P to an output Q = A* P, The important property of this measure is the following inequality:

0::; I(P;A*)::; min{S(P) , S(A*P)},

(43)

We can also represent the quantum mutual entropy by channel representation, If a QCPO 7f is given, then we can define a channel A * for any input state p by

(44) In this scheme we can call I4> (p, 0')

7f

as the channel density, Then we have

= Tre4> (log e4> -log p 0 0') = Tr (p~ 01) 7f

7f
(p ~ 0 1) - log p 0 A~ (p) )

=I4> (p; A~) , where

A~ (p) =Tr 1 (p ~

0 1)

7f
(p ~ 0 1) , However this mutual entropy

I4> (p; A~) does not always satisfy the following inequality (see Example

235

5.4):

o ::; Iq, (p; A~) ::; min { S (p) , S

(A~ (p))) .

(45)

From this point of view the quantum mutual entropy 1q, (p, 0') is not a proper measure of transmitted information through the channel. Hence, a further study of this problem is needed. 6. Summary In this paper we showed that the quantum Bayesian relation holds between the compound state given by means of a CCP map (an entanglement mapping) and the quantum conditional probability operator i.e. QCPO given by means of a CP map. We discussed the role of quantum mutual entropy, conditional entropy and its relation with quantum entanglement.

References 1. M. Asorey, A. Kossakowski, G. Marmo, E.C.G. Sudarshan, "Relation between quantum maps and quantum state", Open. Syst. Info. Dyn. 12, 319329 (2006). 2. L. Accardi, T. Matsuoka, M. Ohya, "Entangled Markov chaines are indeed entangled", Infin. Dim. Anal. Quantum Probab. Top. 9, 379-390 (2006). 3. L.Accardi, T. Matsuoka, M. Ohya, "Entangled Markov chain satisfying entanglement condition", RIMS 1658, 84-94 (2009) 4. V. P. Belavkin, M. Ohya, "Quantum entropy and information in discrete entangled state", Infin. Dim. Anal. Quantum Probab. Top. 4, 33-59 (2001). 5. V. P. Belavkin, M. Ohya, "Entanglement, quantum entropy and mutual information", Proc. R. Soc. London A 458, 209-231 (2002). 6. V. P. Belavkin, X. Dai, "An operational algebraic approach to quantum channel capacity", Int. J. Quantum Inf. 6, 981 (2008). 7. N. J. Cerf and C. Adami, "Negative entropy and information in quantum mechanics", Phys. Rev. Lett. 79, 5194-5197 (1997). 8. M. D. Choi, "Completely positive maps on complex matrix", Lin. Alg. Appl., 10, 285 (1975). 9. D. Chrusciiiski, Y. Hirota, T. Matsuoka and M. Ohya, "Remarks on the degree of entanglement" in this proceedings. 10. B. Groisman, S. Popescu and A. Winter, "Quantum, classical, and total amount of correlations in a quantum state" Phys. Rev A 72, 0323187 (2005). 11. M. Horodecki and R. Horodecki, "Information-theoretical aspect of quantum inseparability of mixed states", Phys. Rev. A 54,1838-1843 (1996). 12. M. Horodecki, P. Horodecki and R. Horodecki, Phy. Lett., A 223, 1 (1996). 13. Henderson and V. Vedral, "Classical, quantum and total correlation", J. Phys. A 34 6913 (2001)

236

14. A. Jamiolkowski, "Linear transformation which preserve trace and positive semidefiniteness of oprators", Rep. Math. Phys. 3 , 275 (1072). 15. A. Jamiolkowski, T. Matsuoka and M. Ohya, "Entangling operator and PPT condition" , TUS preprint (2007). 16. G. Kimura, A. Kossakowski, "A note on positive maps and classification on states", Open Sys. & Information Dyn. 12, 1 (2005) . 17. T. Matsuoka, "On generalized entanglement" , QP- PQ Quantum Probab. & White Noise Anal. 21 , 170-180 (2007). 18. W. A. Majewski, T. Matsuoka and M . Ohya, "Characterization of partial positive transposition states and measures of entanglement", J. Math. Phys. 50, 113509 (2009). 19. T. Matsuoka, M. Ohya, "Quantum entangled state and its characterization", Foud. Probab. Phys. 3 750 , 298-306 (2005). 20. M. Ohya, 1. V. Volovich, Mathematical Foundation of Quantum Information and Computation ( to be pabulished by Springer, New Youk) 21. A. Peres, Phys.Rev.Lett., 77, 1413 (1996). 22. K. Urbanik, "Joint probability distribution of observables in quantum mechanics" , Stud. Math. T. 21,317-323 (1961) . 23. K.G .H . Vollbrecht, M.M. Wolf, "Conditional entropies and their relation to entanglement criteria" , e-print arXiv: quant-ph/0202058v1. 24. S. L. Woronowicz, "Positive maps of low dimensional matrix algebra", Rep. Math. Phys., 10, 165 (1976)

Quantum Bio-Informatics IV eds. 1. Accardi, W. Freudenberg and M. Ohya © 2011 World Scientific Publishing Co. (pp. 237- 254)

CONSTRUCTING MULTIPARTITE ENTANGLEMENT WITNESSES

MHOSZ MICHALSKI Institute of Physics, Nicolaus Copernicus University Grudzir;,dzka 5, 87-100 Torun, Poland E-mail: [email protected] The method of transforming a hamiltonian of a composite quantum system into an entanglement witness , explored in an earlier paper l , is extended to the multipartite case. The witness can be made not only to detect general entanglement but also to discriminate among its various multipartite types. Partial knowledge of the lowest part of energy spectrum is sufficient for approximate witness construction. As an example, we carry out analytic calculations with the hamiltonian of a I-dim ensional Heisenberg XXZ model.

Keywords: Multipartite entanglement, entanglement witness, quantum spin chains, Heisenberg models

1. Introduction

Multipartite entanglement is a generic property of quantum states of interacting many-body systems. However, already the simplest examples indicate that it cannot be understood and described solely in terms of more elementary bipartite entanglement. In particular, as counterintuitive as it may seem, in a system of 3 qubits there are pure states which are separable against any bipartite split, yet they are not fully separable2 ,4. It means that there exists genuinely 3-partite entanglement which is not the sum of any bipartite constituents. Moreover, there are inequivalent brands of 3-partite entanglement 5 , as exemplified, for instance, by the famous IW ) and IGHZ) states,

IW)

=

~ (1100) + 1010) + 1001)) ,

IG H Z) =

~ (1000) + 1111)).

(1)

Namely, it is easy to verify that tracing out one of the qubits reduces the GHZ state to a separable mixture, while the W state is more robust - the resulting 2-qubit state remains entangled. Already this distinction suggests 237

238

that there is no straightforward generalization of the Schmidt decomposition for the 3-partite case,

Indeed, any such I'lj!), and IGHZ) in particular, becomes a separable mixture under one-party reduction, while the W state does not - hence it cannot be cast in such a "Schmidt form" by a choice of local bases. This picture unfolds into an even more complex one with the increase of the number of subsystems. Distinguishing entangled and separable states of bipartite systems remains to be one of the most challenging open problems in quantum information theory. The discrimination among various genres of multipartite entanglement appears a still harder task. In experiments, Bell inequalities are among commonly used tools to detect entanglement both in bi- and multipartite settings. Yet Bell inequalities prove to be a faulty detector in general: on the one hand , even in the bipartite case, there are entangled states not violating the inequalities, on the other hand the degree of violation of Bell inequalities is not sufficiently "monotone" when going from "weaker" entangled biseparable states to fully entangled multipartite ones6,3. Consequently, it is not an adequate tool for the classification of various multipartite entanglement patterns. An alternative technique, recognized to be quite fruitful both theoretically as well as experimentally, is the use of entanglement witnesses 1 ,5,6,7,8,9,1O. While originally7,9, entanglement witnesses were defined to distinguish bipartite entanglement from separability, they proved to be equally useful for the discrimination among various types of multipartite entanglement l l ,5,6, or even as simple entanglement measures a . Actually, there is a number of interesting relations between specific witnesses and standard entanglement measures, the former providing various useful bounds for the latter 12. In the present paper, we are going to focus on a special method of constructing entanglement witness using a physical observable whose spectrum is partially known 10. In [1] we have discussed an application of such a method to construct entanglement witness out of the Hamiltonian of a I-dimensional isotropic Heisenberg model. We have demonstrated the aStrictly speaking every witness W gives rise to a pseudo-measure of entanglement Ew (p) = max{O, - Tr(W p)} rather than a true measure , for in general it yields zero value for some entangled states.

239

usefulness of this approach with analytic calculation of the respective entanglement indicator for a class of thermal equilibrium states of the model. Presently, we extend the results to the case of an anisotropic XXZ Heisenberg chain immersed in a uniform magnetic field. Varying the control parameters - the anisotropy constant and the strength of magnetic field produces different types of multipartite entanglement in the ground state. This in turn is used as the basis of construction of witnesses detecting these specific entanglement brands. The paper is organized as follows. Section 2, for convenience of the readers, introduces definitions and basic facts on multipartite entanglement. Section 3 outlines the general methods of witness construction and presents our procedure of obtaining multipartite witnesses of specific type out of an observable. Section 4 describes the results of analytic calculations performed for the Heisenberg model. 2. Multipartite entanglement

We begin this section with a review of basic facts on multipartite entanglement of pure states. For a more detailed exposition the reader is referred e.g. to [13, 14]. As it is well known, in bipartite case H = HA @ HB entanglement of pure states can be completely classified using Schmidt normal form , d

I?p)

= L Ai l
l77i)

i=1

where l?Pi) E HA , l77i ) E HB are orthonormal systems of vectors and d ::::; min{dimHA, dimHB}' The numbers Al ~ A2 ~ ... ~ Ad ~ 0, L i A; = 1, characterize the entanglement of I?p) entirely, giving rise to a natural entanglement measure,

called the entropy of entanglement. If d = 1 (i.e. Al = 1), the state I?p) is separable. Observe that the Schmidt form for I?p) is obtained by an appropriate choice of bases in HA and HB . In other words, I?p) is locally unitarily (LU) equivalent to any state with similar Schmidt coefficients Ai. In particular, any state of the system of two qubits can be brought by appropriate local unitary transformations to the form sinBIOO) + cosBlll), where the real o : : ; B ::::; ~ parameterizes all distinct entanglement classes.

240

The above observation indicates one way to progress with classification of mulipratitie states: different entanglement patterns are represented by equivalence classes of pure states related by local unitary actions. However, already in the case of a tripartite system, even in its simplest version consisting of 3 qubits, the classification turns out to be much more complex l5 ,16 than the bipartite one: local unitary equivalence yields the following state prototypes

e : :;

with Ai ~ 0, L: A; = 1, a :::; 1r. A general scheme yielding similar "normal forms" for arbitrary multipartite systems is known l9 , minimizing the number of summands from a product orthonormal basis, yet the number of free parameters grows considerably with the number of parties. This substantial increase of normal form complexity suggests the replacement of local unitary equivalence with another, more crude classification scheme. It can be realized by the so-called stochastic LOCC (SLOCC) equivalence 20 where, roughly speaking, local unitary transformations are replaced with local invertible ones. It is the SLOCC classification that splits the set of 3-qubit pure states into the well-known six categories: separable states represented by 1000),3 types of biseparable ones, A-BC represented up to normalization by 10) Q9 (100) + 111)) and similarly for AB-C and AC-B, the W-states and , finally, the GHZ type states represented by (1). However, the passage to a 4-qubit system reveals again the whole continuum of SLOCC equivalence classes, just like in the LV classification scheme: one can distinguish 9 structural types of pure state entanglement yet the complete SLOCC classification involves also 4 independent complex parameters21. Natural convex structure of mixed state sets yields still different and much simpler classification scheme, based on partitions of the set of constituents of the system. An approach of such type has been developed in detail e.g. in [22]. Suppose that the parties constituting a compound quantum system are labeled by AI"'" An, that is H = HA, ... An ' Any partition of this set of labels, say {A~, ... , A;,,} U ... U {Af, ... , A~k}' corresponds to a specific "coarse-grained" way of looking at the entire system,

i.e. here a k-partite one. A pure state I'lj!) E H is called k-separable iff there

241

Figure 1.

The structure of mixed states of a 3-qubit system 5 .

exists a partition as above such that

with l?,bi) E Ji Ai ".A~j , j = 1, ... , k. It is obvious that k-separable states are automatically l-separable for l < k, with respect to appropriate coarser partitions. Next the notion of k-separability is extended to mixed states by the usual convexity construction:

Definition 2.1. A mixed state p is k-sepamble, in short p E 'L.k(Ji), iff it can be represented as a convex combination of pure projections on kseparable vectors,

m

Let us stress that k-separability of individual l?,bm) above refers in general to different partitions of the system constituents. The above notion of k-separability yields the convex filtration in the set of states 'L.(Ji),

'L.(Ji) .

242

The simplicity of such partition-based approach should not overshadow some of its obvious deficiencies, especially the fact that it misses important structural features of states singled out e.g. in the SLOCC equivalence scheme. Going back to the 3-qubit example, one can reveal 5 a finer convex structure distinguishing the W-type states and GHZ-type states among the 3-partite entangled ones, cf. Fig. 1. The W-type states are those which can be expressed as convex sums of projectors on separable, biseparable and W-type vectors, GHZ-type ones being the complement in the set of all states. It should be stressed, however, that in practice one is often interested only in gross entanglement features, e.g. in the distinction between genuinely n-partite entangled and biseparable states, or between biseparable and triseparable ones, etc., when the partition-based approach offers sufficient means. In the following sections we shall describe in detail the construction of an entanglement witness based on the system Hamiltonian which detects genuinely entangled mixed states vs. biseparable ones. 3. Construction of entanglement witnesses An entanglement witness is a versatile tool which allows one to detect entangled states of a compound quantum system 17. Let us recall its original definition in the bipartite setting7 •9 . Definition 3.1. A self-adjoint operator W E BCHAB) is an entanglement witness iff Tr(W 0") ~ 0 for all separable mixed states 0", while Tr(W [!) < 0 for some nonseparable [! (equivalently, Tr(W . ) is nonnegative on separable states, yet the spectrum of W contains a negative eigenvalue). W is then said to detect the entanglement of [!. Entanglement witnesses are directly related via the Jamiolkowski isomorphism 18 to positive but not completely positive maps which are basic for the characterization of entanglement l l . Although entanglement detection criteria based on positive maps (e.g. the famous Peres-Horodecki partial transpose criterion) are formally stronger than the witness-based ones, yet globally they are equivalent in the sense that for deciding separability of a given state it takes in general all possible witness-based tests and likewise all positive map-based ones. The main advantage of witness-based detection is its operational simplicity, namely it is realized by measuring W in the tested state [!. Therefore, if W has some direct physical meaning, such a procedure becomes experimentally feasible.

243

Figure 2.

The idea of a

~C-witness.

It should be noted that the witness technique can be immediately reformulated to detect not the entanglement but any other property of quantum states defining a convex subset of~. Let D. c ~ be such a subset. We will then call an observable W the D.c-witness b iff Th(W . ) is nonnegative on D. and Th(W Q) < 0 for some Q ¢ D.. After all, the witness technique is just a simple application of the geometric formulation of Hahn-Banach theorem: the null-space of Tr(W . ) separates the convex set D. and the external point Q, cf. Fig. 2. Now, suppose that we work with a multipartite system. One can use the set of k-separable states ~k in place of D., to define a witness detecting the related entanglement category of states (i.e. non-k-separability). Of basic interest are witnesses detecting the genuine n-fold entanglement, i.e. filtering out all biseparable states. We will focus on constructing such witnesses below. Examples of witnesses of similar type exist in literature 5 ,6,23, and the general method of their construction proceeds as follows. Let I~ ) be a fixed entangled multipartite state. The witness is defined by

v

= a II: - : I~)(~I ,

(2)

where a = maxl ¢) EiJ.1 (~ I
244

Figure 3.

3-qubit witnesses of different types.

a witness. However, in practice such a is difficult - if at all possible - to compute. The above construction is self-explanatory: any 12 which is a convex combination of projections on elements of D. yields Tr(V 12) 2: 0, while 12 = I~,(~I gives the negative expectation of V. Some well-known examples for the 3-qubit system using the IW, and IGHZ, states in place of I~, are 5 ,23 (see Fig. 3):

• VI = ~][ - IW,(WI with D. = ~Sep, detecting nonseparable states; • V2 = ~][ - IW,(WI with D. = ~Bisep, detecting nonbiseparable states, i.e. genuinely tripartite entangled; • V3 = ~][ - IGHZ,(GHZI with D. = ~w, discriminating between W- and GHZ-type states. Despite its simplicity, this schema does not automatically settle the important question of practical detection of entanglement in laboratory, because the V operators do not have immediate physical meaning. In order to apply them in experiment one has first to express them in terms of physically manageable observables, like e.g. spin operators. Such decompositions have in fact been constructed for three and four qubit systems6 and they turn out to be technically quite demanding. First, it is not easy to find them and to assess their optimality, second - to actually realize them

245

in laboratory: in the cases discussed the experimental setup required 5-15 local measurement settings. We are going now to explore a slightly different approach, where the witness construction begins with a true physical observable that is easy to measure 24 ,25,10. Let A be such an observable. Then the b..c -witness is constructed as WA

=

A:-:o:[,

(3)

where 0: = inf l¢)E.6. (¢IAI¢). Just like in the case of schema (2), finding the exact value of 0: may be a difficult task. Note, however, that once 0: is known, it suffices to measure the observable A in a state g, an easily manageable task, and compare the resulting value Tr(Ag) with 0:: if the measurement outcome is less then 0:, g has the desired property b..c . To analyze the present method closer, let us write A in its spectral decomposition form,

with Ai and l1/'i) being its eigenvalues and eigenvectors, respectively. Then

(4) For a fixed I¢) the sum in (4) is simply a weighted mean of eigenvalues. Let us plot the range of these mean values (i.e. the image of b..) against the spectrum of A, cf. Fig. 4.

a

Figure 4.

The image of t. against the spectrum of A.

We can see now that in order for W A to be a witness one must have 0: or, in other words, at least the ground state 11/'1) of A must not belong to b... W A is then suitable to detect the type of entanglement present in 11/'1) and possibly also in other lowest eigenvectors 11/'2)' ... as long as they are not of b.. type.

Al <

246

As it has been said above, the main difficulty is usually hidden in the computation of a. It is both the structure of the set of states ~ and symmetry properties of A that determine how hard this task will eventually be. Heuristically, one can expect that determination of a will be less difficult in the cases when ~ is simply the set of separable states and A is sufficiently symmetric with respect to relabeling of the system components. A relatively large class of analytically tractable examples is provided by spin lattice models with regular interaction patterns, where the respective hamiltonian H plays the role of the observable A 10. The problem of finding a may be simplified considerably if instead of its exact value one uses a reasonable lower bound a ::; a in the witness construction. The resulting WA will not be optimal in the sense that in general it will detect less states than the exact witness WA: obviously we will have Tr(WAO) ~ Tr(WAO) for any 0, which is the price to pay for the simplification of determining a. We will outline one such approximation procedure below. Recall that a is given by (4). Let ILl = SUPI¢)E~ 1(7Pll¢)1 2. Since by assumption l7Pl) tf- ~, we have 0 ::; ILl < 1. An immediate lower bound to a is then

(5) Indeed, it is the least possible mean of eigenvalues (4) realized only if for some ¢ E ~ there is a coincidence of null overlaps (7Pi I ¢) = 0 for all i ~ 3. An improvement of this approximation may still be possible and it depends on the actual value of maximal squared overlap of 17P2) with states in ~. Let IL2 = SUPI¢)E~ 1(7P21 ¢) 12. If now IL2 < 1- ILl' the improved lower bound to a is given by

(6) One can continue this procedure finding subsequently IL3' ... etc. as long as the obtained values satisfy ILk < 1 - ILl - ... - ILk-l at each step. In [1] we have applied the exact witness construction method based on (3) to a I-dimensional isotropic Heisenberg ring of n spins immersed in a uniform magnetic field of controllable strength B. ~ was chosen to be the set of fully separable states. The resulting witness was then applied to thermal equilibrium states of the system, detecting correctly their entanglement for a range of field and temperature values. In the next section, we will analyze the anisotropic case and we will show how one can find a

247

lower bound of a with the procedure just described when biseparable states.

~

is the set of

4. Example: Anisotropic Heisenberg spin chains In the present section we will work with the I-dimensional Heisenberg XXZ model with hamiltonian given by N

H =

L o-ko-k+1 + 0-%0-%+1 + (1 + D)a-ko-k+1 + Bo- k ,

(7)

k=l

Here D and B denote, respectively, the nonisotropy parameter and the strength of external magnetic field. The coupling constant J is set equal to 1 for simplicity (antiferromagnetic case). The Hilbert space of the model is 1i = (C 2 )®N and we have used the abbreviated notation o-k = 1IQ9·· .Q9o-xQ9 ... Q91I, where the spin operator o-X appears at the k-th slot, and similarly for 0-% and o-k. Moreover, the index value k = N + 1 is identified with 1, dosing the chain in a periodic manner. Suppose first that we want to use H for the construction of an ordinary entanglement witness, that is, we take ~ to be the set of fully separable N-qubit states I¢) = 1¢1) Q9 ... Q91¢N)· The k-th term of (¢IHI¢) evaluates to

(¢klo-XI¢k) (¢k+110- x l¢k+1)

+

+

(¢klo-YI¢k) (¢k+llo- YI¢k+1) (1 + D)(¢klo-ZI¢k) (¢k+110- z l¢k+1) + B(¢klo-ZI¢k).

(8)

Since I¢k) vary independently on their respective Bloch spheres, recall 1 ,10 that we can rewrite the above using independent real variables Xh, Yk and Zk in place of the expectations of o-x, o-y and o-z,

(9) with additional constraints k= 1, ... ,N.

(10)

Minimizing (¢IHI¢) over ~ amounts to finding the conditional minimum of the polynomial in 3N real variables composed of terms (9) subject to the constraints (10). As it was argued in [1, 10], such a minimization can be performed termwise with a slight modification of the "B" part in (9),

h

=

Xk Xk+1

+ YkYk+1 +

(1

Zk + Zk+l + D)ZkZk+1 + B 2

'

248

Figure 5.

The sectors in the (B,D)-plane corresponding to distinct minh values.

using the Lagrange multipliers method. It yields -I-D

. mm h =

{

for B2

-1 - 4(2

+ D)

l-IBI +D

(11)

for

for D < @l_ 2 2

and the corresponding "phase diagram" in the (B, D)-plane is shown in Fig. 5. This way, the respective entanglement witness has the forme W

= H - (Nminh)lI.

(12)

To complete the analysis one has to look closely at the structure of the spectrum of H to find regions in the parameter plane where the ground state is entangled: only then W is an entanglement witness. We will perform such analysis for the case of N = 4 (for other values of N it is formally similar). The spectrum of a 4-spin model (7), i.e. its lowest part, is the following

Al

=

-2 - 2D - 2D' ,

A2

=

-4 - 2B,

A3 = 4 - 4B

+ 4D ,

eN min h is the exact minimum of (4)IHI4>) if N is even, otherwise it may be slightly smaller than the minimum 1.

249

Figure 6. The sectors in (B, D) plane where the respective Ai are the lowest energy levels, marked with different shades of gray. The dashed line is the boundary between the regions I and II of Fig. 5 and it corresponds to the switch of minh value, (11).

where D' = VD2 malization, are

+ 2D + 9 and the corresponding eigenvectors,

up to nor-

1'1/>1) = 10011) + l+D4_DI 10101) + 10110) + 11001) - 1+~+D/1101O) + 11100) and

1'1/>2) = 11110) -11101)

+ 11011) -

10111),

The states 1'1/>1) and 1'1/>2) are entangled. We have restricted here the analysis to the B 2 halfplane; the image for negative B is fully analogous, the respective eigenvectors are obtained from the current ones by spin flipping. The corresponding level-crossing diagram, showing regions in the parameter plane where different Ai become the lowest energy levels, is presented in Fig. 6. Thus 1'1/>3) is the ground state in the region below the A2 = A3 line which is D = ~ - 2; it coincides with sector III of Fig. 5. As 1'1/>3) is separable, no entanglement detection by means of (12) is possible in this domain. Above the D = ~ - 2 line the ground state changes to 1'1/>2) and for still larger values of D - to 1'1/>1). Both these domains have nonempty intersections with sectors I and II of Fig. 5 (cf. the dashed parabola in Fig. 6 corresponding to the I-II border). This data allows one to complete the detailed construction of the entanglement witness based on H as prescribed in (12). We have conducted the

°

250

construction analytically with the use of Mathematica and we have applied the witness W to a family of equilibrium states of (7),

(} (f3 ,

B D) = exp(f3H) , Z'

f3

1

=

kT'

Z

=

Trexp(-f3H) ,

(13)

for a range of positive temperatures. For T close to 0 the mixture (} is dominated by the terms corresponding to the lowest energies, say >'1 < A2 < ... , (14) and so (} inherits mostly the entanglement of l?,I;l)' Therefore, it is detected by W which, by construction, is most sensitive precisely to the entanglement of l?,I;l) type. However, one type of entanglement often present in thermal equilibrium states cannot be detected by witnesses of this kind. The separability of the ground state l?,I;l) of H, while making our witness construction faulty, does not exclude that the state (13) can nevertheless be entangled for a range of positive temperatures. This phenomenon, called thermally induced entanglement, happens when the first excited eigenstate 1?,I;2) is entangled and its admixture shows up in (} via the second term in (14) for certain T> Tmin. In Fig. 7 we collect the results of our tests of W H. The plots (left column) show the value max { -Tr(WH

(}) ,

o} .

for a range of Band T parameters. Separate plots correspond to different values of D, see also Fig. 8 for the location of these values on the eigenvalue level crossing diagram. We shall describe now how H can be used in the construction of a genuine entanglement witness. In this case, b. is the set of biseparable states. The argument that has previously led us to the simplification (910) of the extremalization problem for H is no longer valid, for the local components l
251

Figure 7. Left column: positive values of - Tr(WHe) plotted for a range of Band f3 = k~ for several fixed D values (see also Fig. 8). Right column: similarly, for the genuine entanglement witness WHo

Specifically, we have the following ordering of eigenvalues

III

the sectors

252

Figure 8. The refinement of the level crossing diagram of Fig. 6 for 3 lowest energies of H (d. (15) and the surrounding text). Horizontal dashed lines correspond to the values of D used in the plots of Fig. 7.

(a)-(e):

(a) (b)

(c) (d)

(d') (e)

A2 A2 A2 Al Al Al

< < < < <

<

A3 Al Al A2 A2 A4

< < < < <

<

AI, A3, A4, A4, A3, A2,

(15)

where the eigenvalue A4 = -4 - 4D corresponds to the GHZ-type state 11{>4) = 11010) -10101). In order to find as in (5), we need to estimate the maximal overlap of the ground state 11{>2), and respectively 11{>1) in sectors (d)-(e), with biseparable vectors. This is done by considering all bipartite splits of the entire system: 1- 234, 2 -134, ... , 12 - 34, 13 - 24, ... etc. and, in each case, writing down the Schmidt form of 11{>2) with respect to this split. Then the square of the largest among all Schmidt coefficients obtained in this process is the desired value of a. For example, the normalized state 11{>2) can be

a

253

written as

with respect to the 1 - 234 split. On the other hand, taking the splitting 12 - 34, we have

Now, using the matrices A

= [aij] and B = [bij] as above,

[ 00000 0 O-~] 000 12 0 _12 12 0 '

[

o0 00 o0 o -~

0 0

O-~

1

0 12 ~ 0

the respective squared Schmidt coefficients are the nonzero eigenvalues of A* A and B* B, i.e. {~, and {~, ~}. It is easy to see that due to the symmetry of 11J'!2) other bipartite splittings of the system space yield precisely the same Schmidt coefficients. Hence, we can take as the first approximation (i = + in the region (a) and (i = ~A2 + tAl in (b)-(c). Let us analyze whether this estimate can be improved by (6). Since 11J'!3) is separable, its maximal overlap with biesparable states in ~ is 1, so (i cannot be improved any further in the region (a). Similarly, the maximal squared Schmidt coefficient over all biesparable expansions of 11J'!1) is

t}

P'2 t>'3

,= 1 +D2D'+ D' where D' = JD2 + 2D + 9. Since, > t for D ~ -2, also in the region (b) - (c) no improvement of (i is possible. In (d) and (d') our approximation reads (i = ,AI + (1-,)A2 and in (e) (i = ,AI + (1 -,)A4' Again the fact that, > for D ~ -2 excludes any improvement of (i in (d) or (d'). Finally, as the maximal squared overlap of 11J'!4) with states in ~ is ~ and , ~ ~ in (e), no better (i can be found as well in this case. Fig. 7 summarizes our computational results. Its left column, as mentioned earlier, contains plots of -Tr(WHI?) for the entanglement witness W H, and the right column - plots for the approximate genuine entanglement witness W H just constructed. The exemplary D values used are 1.0,0.25,0.0, -0.5. The reader may relate these plots with the location of D values on the level crossing diagram of Fig. 8: edges in the plots correspond to transitions between different sectors (a) - (e) with the change of B value.

t

254

Acknowledgment The author is greatly indebted to Professor Masanori Ohya and the QBIC Centre for support and hospitality during his visit at Tokyo University of Science in March 2010.

References 1. Michalski M., [in :] Quantum Bio-Informatics III, L. Accardi, W. Freudenberg, M. Ohya, eds., Quantum Probability and White Noise Analysis XXVI, p. 217, World Scientific, 2009. 2. Bennett Ch., et al., Phys. Rev. Lett. 82, 5385 (1999). 3. Collins D., et al., Phys. Rev. Lett. 88, 170405 (2002). 4. Diir W., J. 1. Cirac, R. Tarrach, Phys. Rev. Lett. 83, 3562 (1999). 5. Acin A., et al. , Phys. Rev. Lett. 87, 040401-1 (2001). 6. Bourennane M., et al., Phys. Rev. Lett. 92, 087902-1 (2004). 7. Horodecki M., P. Horodecki, R. Horodecki, Phys. Lett. A 223 , 1 (1996). 8. Lewenstein M., B. Kraus, J. 1. Cirac, P. Horodecki, Phys. Rev. A 62, 052310 (2000). 9. Terhal B., Phys. Lett. A 271 , 319 (2000). 10. T6th G. , Phys. Rev. A 71 , 010301(R) (2005). 11. Horodecki M., P. Horodecki, R. Horodrecki, Phys. Lett. A 283 ,1 (2001). 12. Eisert J., F. G. S. L. Brandao, K. M. Audenaert, New J. Phys. 9 , 46 (2007). 13. Eisert J., D. Gross, Multi-partite entanglement, [in] Lectures on quantum information, D. Bruss and G. Leuchs Eds., Wiley-VCH, Weinheim, 2006. 14. Horodecki R., P. Horodecki, M. Horodecki, K. Horodecki, Rev. Mod. Phys. 81, 865 (2009). 15. Acin A. , et al. , Phys. Rev. Lett . 85, 1560 (2000); quant-ph/0003050. 16. Acin A., A. Andrianov, E. Jane, R. Tarrach, J. Phys. A: Math. Gen. 34, 6725 (2001); quant-ph/0009107. 17. Michalski M., [in:] Quantum Bio-Informatics III, L. Accardi, W. Freudenberg, M. Ohya, eds., Quantum Probability and White Noise Analysis XXVI, p. 231, World Scientific, 2009. 18. Jamiolkowski A., Rep. Math. Phys. 3 , 275 (1972). 19. Carteret H. A., A. Higuchi, A. Sudbery, J. Math. Phys. 41 , 7932 (2000). 20. Verstraete F., J. Dehaene, B. De Moor, Phys. Rev. A 68, 012103 (2003). 21. Verstraete F., J. Dehaene, B. De Moor, H. Verschelde, Phys. Rev. A 65 , 052112 (2002). 22. Diir W., J. 1. Cirac, Phys. Rev. A 61, 042314 (2000). 23. Zhao M.-J., Z.-X. Wang, Rep. Math. Phys. 63 , 409 (2009). 24. Brukner C., V. Vedral, arXiv:quant-ph/0406040v1 (2004). 25. Vedral V., Open Sys. Information Dyn. 16, 287 (2009).

Quantum Bio-Informatics IV eds. L. Accardi, W. Freudenberg and M. Ohya © 2011 World Scientific Publishing Co. (pp. 255-265)

ON KADISON-SCHWARZ PROPERTY OF QUANTUM QUADRATIC OPERATORS ON M 2 (C)

FARRUKH MUKHAMEDOY*

ABDUAZIZ ABDUGANIEY+

Department of Computational €3 Theoretical Sciences Faculty of Science, International Islamic University Malaysia P.O. Box, 141, 25710, Kuantan Pahang, Malaysia * E-mail: [email protected];[email protected] +E-mail: [email protected] In the present paper we first describe quantum quadratic operators (q.q.o) acting on the algebra of 2 x 2 matrices M2(1C). Moreover, we provide necessary conditions for q.q.o. with Haar to satisfy Kadison-Schwarz condition. By means of such a description we give an example of q.q.o. which is not the Kadision-Schwarz operator. Keywords: quantum quadratic operators; Kadison-Schwartz operator.

1. Introduction

It is known that one of the main problems of quantum information is characterization of positive and completely positive maps on C* -algebras. There are many papers devoted to this problem (see for example 4,10,18,19). In the literature the most tractable maps, the completely positive ones, have proved to be of great importance in the structure theory of C*algebras. However, general positive (order-preserving) linear maps are very intractable 1o ,12. It is therefore of interest to study conditions stronger than positivity, but weaker than complete positivity. Such a condition is called Kadison-Schwarz property, i.e a map ¢ satisfies the Kadison-Schwarz property if ¢(a)*¢(a) :0::: ¢(a*a) holds for every a. Note that every unital completely positive map satisfies this inequality, and a famous result of Kadison states that any positive unital map satisfies the inequality for self-adjoint elements a. In 17 relations between n-positivity of a map ¢ and the KadisonSchwarz property of certain map is established. Some a nice property of the Kadison-Schwarz maps were investigated in 16. The present paper is devoted to the Kadison-Schwarz property of certain 255

256

class of operators on M2(C), It is known that the theory of Markov processes is a rapidly developing field with numerous applications to many branches of mathematics and physics. However, there are physical systems that can not be described by Markov processes. One of such systems is given by quadratic stochastic operators (see 2), which relates to population genetics. The problem of studying the behavior of trajectories of quadratic stochastic operators was stated in 20. The limit behavior and ergodic properties of trajectories of quadratic stochastic operators were studied in 7,8,9. However, such kind of operators do not cover the case of quantum systems. Therefore, in 5,6 quantum quadratic operators acting on a von Neumann algebra were defined and studied. Certain ergodic properties of such operators were studied in 13,14. In the present paper we are going to study quantum quadratic operators (q.q.o.) with the Kadison-Schwarz property. Note that operators with this property no need to be completely positive. Aim of the paper is to find some necessary conditions for the trace-preserving quadratic operators to be the Kadison-Schwarz ones. Since trace-preserving maps arise naturally in quantum information theory (see e.g. 15) and other situations in which one wishes to restrict attention to a quantum system that should properly be considered a subsystem of a larger system with which it interacts. Therefore, in Section 3 we describe q.q.o. with Haar state (invariant with respect to trace), namely certain characterizations of q.q.o, the KadisonSchwarz operators are given. By means of such a description in Section 4, we shall provide an example of q.q.o. which is not a Kadision-Schwarz operator. It is worth to mention that characterizations of positive and completely positive maps defined on M2 (C) were considered in 10,11,19 and 18, respectively.

2. Preliminaries In what follows, by M 2 (C) we denote an algebra of 2 x 2 matrices over complex filed C. By M 2(C) 0 M 2(C) we mean tensor product of M 2(C) into itself. We note that such a product can be considered as an algebra of 4 x 4 matrices M 4 (C) over C. In the sequel II means an identity matrix,

i.e.

n=

(~~).

By S(M 2 (C)) we denote the set of all states (i.e. linear

positive functionals which take value 1 at ll) defined on M2(C)'

Definition 2.1. A linear operator

~

: M 2(C)

----+

M 2(C) 0 M 2(C) is said

257

to be (a) - a quantum quadratic operator (q. q. 0.) if it satisfies the following conditions: (i) unital, i.e. ~ll = II ® ll; (ii) ~ is positive, i.e. ~x ~ 0 whenever x ~ 0; (b) - a K adison-Schwarz operator (KS) if it satisfies ~(x*x) ~ ~(x*)~(x)

for all x E M2(C)'

(1)

Note that if ~ is unital and KS operator, then it is a q.q.o. A state hE S(M 2 (C)) is called a Haar state for a q.q.o. ~ if for every x E M 2 (C) one has

(h ® id)

0

~(x)

= (id ® h)

0

~(x)

= h(x)ll.

(2)

Remark 2.1. Let U : M 2(C) ® M 2(C) --+ M 2(C) ® M 2(C) be a linear operator such that U(x ® y) = y ® x for all x, y E M2(C)' If a q.q.o. ~ satisfies U ~ = ~, then ~ is called a quantum quadratic stochastic operator. Such a kind of operators were studied and investigated in 13,14.

3. Quantum quadratic operators with Kadison-Schwarz property on M 2 (C)

In this section we are going to describe quantum quadratic operators on M 2 (C) as well as find necessary conditions for such operators to satisfy the Kadison-Schwarz property. Recall 3 that the identity and Pauli matrices {ll, 0"1,0"2, 0"3} form a basis for M 2 (C), where

0"1

=

(1001)

0"2

=

(0 -i) 0 i

0"3

=

(10-10) .

In this basis every matrix x E M 2 (C) can be written as x = woll + wa with Wo E C, w = (WI, W2, W3) E C 3 , here WO" = WIO"I + W20"2 + W30"3· Lemma 3.1.

18

The following assertions hold true:

(a) x is self-adjoint iffwo,w are reals; (b) Tr( x) = 1 iff Wo = 0.5, here Tr is the trace of a matrix x; (c) x > 0 iff Ilwll ::; wo, where Ilwll = JIW112 + IW212 + IW312.

258

Note that any state t.p E S(M 2 (C)) can be represented by

t.p(woll + wO") = Wo

+ (w, f),

(3)

where f = (11,12, h) E IR3 with Ilfll :; 1. Here as before (-,.) stands for the scalar product in CC 3 . Therefore, in the sequel we will identify a state t.p with a vector f E IR3. In what follows by T we denote a normalized trace, i.e. T(X) = ~ Tr(x), x E M2(C)' Let ~ : M 2(C) -+ M 2 (C) 0 M 2 (C) be a q.q.o. with a Haar state T. Let us write the operator ~ in terms of a basis in M 2 (C) 0 M 2 (C) formed by the Pauli matrices. Namely, ~ll =

ll 0 ll; 3 3 3

L

~(O"i) = bi(ll 0 ll) + 2:);;)(ll 0 O"j) + :2);;)(O"j 0 ll) + j=l

j=l

bml,i(O"m 00"d,

m ,l=l

where i = 1,2,3. By means of the Haar equality with T (see (2)) we find that bi = 0, el) -- b(2) ..J E {I " 2 3} . bij ij -- 0 f or every z, Positivity of ~ implies that all numbers {bij,d are real ones. Hence, one can prove the following ~ : M 2 (C) -+ M 2 (C) 0 M 2 (C) be a g.g.o. with a Haar then it has the following form:

Theorem 3.1. Let

state

T,

3

L

~(x) = woll 0 II +

(4)

(b m1 , w)a-m 0 0"1,

m,l=l where x

= Wo + WO", b m1 = (bm1,1, bml,2, bm1 ,3).

Let us turn to the positivity of~. Given vector f

= (11 ,12, h)

E IR3

put 3

(3(f)ij

=

L

(5)

bki,jfk.

k=l Define a matrix JB(f) = ((3(f)ij)rj=l. By IIJB(f) II we denote a norm of the matrix JB(f) associated with Euclidean norm in CC 3 . Put

S = {p = (Pl,P2,P3)

E IR3:

pi + p~

+ p~

:;

I}

259

and denote

111lH\111 = sup 11lH\(f) II· fES

Now given a state cp by E