{'fraction_non_alphanumeric': 0.03736208625877633, 'fraction_numerical': 0.007932889577824382, 'mean_word_length': 4.320033955857386, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Correlations in local measurements on a quantum state, and complementarity as an explanation of nonclassicality

We consider the classical correlations that two observers can extract by measurements on a bipartite quantum state, and we discuss how they are related to the quantum mutual information of the state. We show with several examples how complementarity gives rise to a gap between the quantum and the classical correlations, and we relate our quantitative finding to the so-called classical correlation locked in a quantum state. We derive upper bounds for the sum of classical correlation obtained by measurements in different mutually unbiased bases and we show that the complementarity gap is also present in the deterministic quantum computation with one quantum bit.


I. INTRODUCTION
Complementarity was identified by Niels Bohr as the fundamental underlying cause of quantum uncertainty and as an unavoidable element in our attempts to simultaneously describe different properties of physical systems [1]. Formally, complementarity is reflected by the non-commuting mathematical operators representing physical observables which prevent the general existence of joint eigenstates of these operators, and which hence leads to uncertain measurement outcomes. Complementarity is also reflected in the impossibility for any physical set-up to measure such different observables without the measurement of one observable disturbing the outcome of the other. In an attempt to challenge the complementarity view, Einstein, Podolsky and Rosen, introduced the entangled EPR-state [2] in which quantum correlations between the constituents are strong enough to suggest an existence of action-at-a-distance, when measurements on one particle seemingly force the projection of the quantum state of the other particle. This effect has been a corner stone in the discussion of the interpretation of quantum mechanics, but rather than weakening Bohr's views it served to strengthen the complementarity description, and more recently it has been incorporated as a useful paradigm and even a practical ingredient in quantum information processing tasks. The EPR state can thus be used for sharing of a secret key between remote partners [3] and for teleportation of unknown quantum states [4], and it can assist in various other communication [5,6] and precision measurement tasks [7].
With the numerous applications of such correlated states, it has been a natural goal to quantify the degree of correlation of any given state, and also to quantify to which extent the correlations are of a quantum or of a classical nature. Entanglement does not exist in classical physics, and part of this classification has therefore been related to the ability to distinguish entangled states from non-entangled states and, more ambitiously, to quantify the amount of entanglement in a given quantum state. This is a research field where considerable progress has been made, but where many open and difficult questions still remain to be solved.
Another natural approach to the characterization of the quantum correlations in a given state can be based upon the comparison of the information theoretic correlations of the quantum state with the classical correlations present in the classical detection records after measurements have taken place [8,9,10,11,12,13,14,15]. Studies have revealed that some quantum states carry more correlations than can be retrieved by separate measurements on the constituents, even if they are not entangled; they may posses powers for quantum information tasks which are not available in classical states, and by allowing a parallel classical communication one may extract or transfer more information with such states than the sum of the classical communication and the previously available information. A number of natural quantitative measures of quantumness have thus appeared, which in one way or another display the difference between the correlations present in the original quantum state, and the information retrieved by suitable schemes or protocols. In this paper we shall suggest that this difference may be ascribed to complementarity, and we quantify how different measurement strategies provide upper and lower bounds for different information characteristics.
In Sec. II, we introduce the quantum mutual information of a quantum state and the maximal mutual information between classical measurement records obtained by measurements on the quantum state. The difference between these two quantities constitutes a measure Q of the quantumness of the correlations of the quantum state, and we shall present some quantitative results obeyed by Q. In Sec. III, we discuss the role of complementarity when classical information is extracted from quantum states, and we relate our complementarity discussion and Q to the so-called locking effect. In Sec. IV, we review the properties of two other measures of non-classical correlations: the quantum discord and the measurement induced disturbance, and we establish the relationship between them and our Q. In Sec. V we present a number of examples which quantitatively illustrate our results. In Sec. VI, we discuss consequences of the complementarity on classical correlations obtained with projective measurements on mutually unbiased bases. In Sec. VII, we show how our measure of quantumness quantifies the speed-up of quantum computing in a particular model where there is no distillable entanglement present. Sec. VIII concludes the paper.

II. QUANTUM MUTUAL INFORMATION AND CLASSICAL CORRELATIONS GENERATED BY LOCAL MEASUREMENTS ON A QUANTUM STATE
Alice and Bob share a quantum state described by the density matrix ρ AB , with the marginal states denoted by ρ A ≡ Tr B (ρ AB ) and ρ B ≡ Tr A (ρ AB ). The most general operations performed by Alice and Bob without any communication between them are completely positive, local maps, in which Alice performs a general POVM measurement ( on her part of the quantum system and Bob performs a general measurement ({M B s |M B s ≥ 0, s M B s = I B }) on his part of the system, see Fig.1(a). The marginal probability denotes the probability of obtaining the ith (sth) result by Alice (Bob) regardless of the other observer's result, while the joint probability that Alice obtains the ith result and Bob obtains the sth result is given by The correlations in the two classical detection records obtained by Alice and Bob are characterized by the mutual information I{A : B}, defined by where H{p µ ; µ} ≡ − µ p µ log 2 p µ denotes the Shannon entropies for the marginal probability distribution {p µ = p i , p s } and the joint probability distribution {p µ = p is }, respectively. Without recourse to any particular measurement protocol, one defines the quantum mutual information S(A : B) of the state ρ AB in a very similar manner, but in terms of the von Neumann entropies S(ρ) = −Tr[ρlog 2 (ρ)] of ρ AB , ρ A and ρ B , The quantum mutual information S(A : B) is readily evaluated for any quantum state ρ AB , and an important contribution to its precise operational meaning is provided in Ref. [8] where it is shown that S(A : B) quantifies the minimal amount of noise to be added to a state to bring it to product form, i.e. to delete all quantum and classical correlations present in the state. Also, recent work on the so-called merging effect has identified the difference S(A : B) − S(A) as the number of maximally entangled qubit pairs that must be spent or are released upon merging of the joint quantum state of A and B at Bob, retaining their joint correlations with any ancilla degrees of freedom [9], see Fig. 1 For a pure quantum state, the density matrix can be replaced by a state vector |ψ AB , and S(ρ A ) = S(ρ B ) quantifies the entanglement of the state. S(ρ A ) is for example the asymptotic ratio K/M between the number (K) of maximally entangled qubit states, , that can be exchanged for M copies of the state |ψ AB using only local operations and classic communication (LOCC), see Fig. 1(c) [16]. S(AB) vanishes for a pure state, and hence S(A : B) = 2S(ρ A ) also becomes a quantitative measure of the entanglement of the state. For a generally mixed state ρ AB , the quantum mutual information of a n-copy broadcast state of ρ AB , i.e., a state of n copies of systems A i and B i (i = 1, · · · , n) so that the reduced density matrix for each pair (A i , B i ) is ρ AB , can also be used to classify classical, separable and entangled states. It is, e.g., shown in [17] that the minimal per-copy quantum mutual information for an infinite number of broadcast copies satisfies some properties required of an entanglement measure.
Both the merging analysis and the quantitative entanglement measure in terms of an equivalent number of maximally entangled states assume that local operations and classical communication between Alice and Bob are free of charge, i.e., they provide measures of some correlations which are of a strictly non-classical nature, but they do not properly account for the classical correlations already present in the state. By comparing S(A : B), and S(ρ A ), S(ρ B ) with I{A : B} we shall shed more light on the meaning of the quantum mutual information, and we shall, in particular investigate to what extent it limits the classical mutual information available under different measurement protocols.

Proposition 1
The classical mutual information has the following upper bound in terms of the von Neumann entropy and the quantum mutual information:  The Holevo bound [18,19,20] can be used to prove that I{A : B} ≤ S(ρ A ) and I{A : B} ≤ S(ρ B ). These inequalities are also intuitively reasonable as S(ρ A ) and S(ρ B ) by the Schumacher noiseless channel coding theorem [21] denotes the effective size of the system on Alice and Bob's side respectively. A proof of the inequality I{A : B} ≤ S(A : B) can be found in [22]. An alternative complete proof of the proposition is given in the Appendix of this paper.
We will denote by I max (ρ AB ) the maximal mutual information over all choices of local measurement strategies, as it is a property of the state ρ AB [23,24]. I max (ρ AB ) can always be achieved by local measurements with rank-one POVM elements, since a general POVM measurement can be refined to a rank-one POVM measurement via eigendecomposition of each POVM element. The original measurement can thus be considered as a two-step procedure where first, the refined rank-1 measurement is performed, and then the output is binned according to the original POVM elements. The mutual information I{A : B} cannot increase during the second step, and therefore it is sufficient to maximize over only the local measurements with rank-one POVM elements when we calculate I max (ρ AB ). I max (ρ AB ) may not always be achievable by local projective measurements, i.e., local measurements with orthonormal rank-one POVM elements(see example E in Sec. V).
We will introduce the difference between S(A : B) and I max (ρ AB ), Q(A : B) is a function of the quantum state, and we will also use the notation Q(ρ AB ). This difference was also introduced with the symbol △ CC (ρ AB ), and its vanishing for states that are locally broadcastable was shown in [25]. When ρ AB = |ψ AB ψ AB | is a pure state, S(ρ AB ) = 0 and S(ρ A ) = S(ρ B ) is the entanglement of the state.
Proposition 1 then implies that the classical mutual information is limited by the entanglement of the state S(ρ A ) = S(ρ B ) < S(A : B). When the Schmidt bases are chosen as the measuring bases for projective measurements by both observers I{A : B} actually reaches this upper bound, and Q(A : B) is equal to the entanglement of the state. For a mixed state, the relation between entanglement and I max is more complicated, as on the one hand the entanglement measure itself is not unique, and as a mixed state may contain also classical correlations. Since I max can be nonzero even for a separable state, it can be larger than the amount of entanglement, but according to proposition 1, it cannot be larger than the quantum mutual information S(A : B), which accounts for both the quantum and the classical correlations in the state.
A main objective of this paper is to address to which extent a given measurement strategy reaches the limits of Proposition 1, and in particular to identify the properties of ρ AB , that may prevent I max (ρ AB ) from actually reaching these limits. In all our examples, we will show that complementarity arguments predict whether a measurement strategy allows I{A : B} to exhaust Proposition 1 or not.

III. COMPLEMENTARITY, LOCKING EFFECT
In the previous section we defined measures of quantum correlations in quantum states and we compared them with the correlations in classical detection records. In this section we will argue that complementarity issues directly limit the available classical information. And we will show how the so-called locking effect can be interpreted in these terms.

A. Complementarity gaps
Although we will be primarily interested in the two-party situation where Alice and Bob have access to a joint quantum state, let us first consider the situation where one person wants to transmit a message by preparing and sending a quantum system to a receiver, who may perform measurements on the system. Quantum states are specified by amplitudes with arbitrary complex values, but it is well known that for example no more than a single classical bit can be transmitted by a two-level quantum system in such a protocol. The random outcome of any binary measurement on a qubit in fact gives even less information unless the sender and receiver agree on which orthogonal basis is used for the preparation and detection, and the optimal communication is therefore effectively classical.
It is interesting to see how the use of a higher dimensional quantum system and a biased alphabet, where the sender chooses states from an ensemble with average density matrix ρ, described by the von Neumann entropy S(ρ) = −Tr[ρlog 2 (ρ)], can lead to transmission of maximally S(ρ) classical bits per particle. This works if the sender uses pure states from the eigenbasis of ρ with the corresponding probabilities, and if the receiver measures in the same basis. In that case the Shannon entropy H{p i ; i} ≡ − i p i log 2 p i of the probabilities for the different outcomes equals precisely the von Neumann entropy. If we associate to the von Neumann entropy the amount of information in the quantum state, and to the Shannon entropy, the amount of information available in the detection records, we see that these two measures agree, if the same observable is used for encoding and readout of the transmitted message, while if the observable used by the receiver is complementary to the one used by the sender, the classical detection record does not exhaust the information available in the quantum state.
In the situation we are interested in, Alice and Bob share a quantum system. Any observable addressed by Alice commutes with any observable addressed by Bob, and hence complementarity does not prevent Alice and Bob from measuring any observable of their choice with any desired precision. Given the precise quantum state, however, there may be correlations referring to specific observables, for example strong correlations of the particle positions in the original EPR state or of their spin components in the later spin version due to Bohm. Experiments on the EPR states are known to violate Bell's inequality (and a number of related inequalities), revealing that measurements on the states cannot be described by local hidden variable theories. We shall here argue that complementarity arguments here also lead to inequalities that must be fulfilled by measurements on bipartite quantum states. To be a little more precise: Let Alice perform, e.g., a projective measurement of an observable A, and let the quantum state carry a correlation between this observable and an observable B, enabling Alice to infer, precisely or approximately, the outcome of a measurement of an associated observable B by Bob. Bob may, however, be interested in another observable C, which is complementary to B, and hence joint information about the formally commuting observables A and C, de facto, becomes complementary. We will now proceed to show how the possible complementarity between different observables that one would like to measure on a subsystem, or between a single observable, actually measured on a subsystem and observables inferred from measurements on the other subsystem, is decisive for the existence of a gap between the correlations present in a quantum state and the classical correlations that can be extracted by local measurements.
When ρ AB = |ψ AB ψ AB | is a pure, entangled state, S(ρ AB ) = 0 and S(ρ A ) = S(ρ B ) is the entanglement of the state. According to Proposition 1, this is also the highest possible value for the classical mutual information, and as argued above, there is no gap between this maximum and the actually achievable classical information. The maximal information is retrieved when Alice and Bob agree to use the Schmidt-bases for local projective measurements on their respective parts of the quantum system. When written in these bases, their measurements correspond to operators represented by diagonal matrices, which clearly commute, and hence there is no complementary issue in this case.
If a separable state ρ AB can be written as a convex sum of the form with {|ψ i A } and {|φ j B } fixed orthogonal bases of A and B respectively, the maximal classical information is obtained if Alice measures in the {|ψ i A } basis and Bob measures in the {|φ j B } basis, respectively. There is no issue of complementarity, and there is again no gap between the correlations in the state and the classical mutual information.
In [25] it is shown, indeed, that this is the only kind of states where Q vanishes.
Let us now assume another separable state written on the form, i denote density matrices for Bob's part of the quantum system. Even though this is a separable state, that could have been prepared by classical communication and local operations, we here observe a consequence of complementarity: if Alice performs a measurement in the |i -basis and finds the state |i 0 , Bob is in possession of the mixed state ρ B i0 . The measurement yielding the maximum information to Bob is then a projective measurement on the eigenbasis of ρ B i0 . If Bob does not know i 0 , he does not know on which eigenbasis (for which ρ B i ), he should perform his measurement, and complementarity prevents him from obtaining such measurement results for several bases simultaneously. Only if all ρ B i commute, they are diagonal in the same basis, and the optimum observables commute and are not complementary. In this limit, the gap between the correlations in the state and the classical information precisely vanishes.

B. Non-classicality and the classical correlation locked in a quantum state
It is shown in Ref. [24] that some hidden classical correlation that cannot be obtained by local measurements can, nevertheless, be "unlocked" with the help of a small amount of classical communication (see Fig. 1(d)).
As an example, the following bipartite state is considered.
Here U 0 = I is the identity operator on d-dimensional Hilbert space, and U 1 is a unitary transformation on the d-dimensional Hilbert space such that {U 1 |i } is a mutually unbiased basis with respect to {|i }. It is easily seen that ρ A = 1 2d I, ρ B = 1 d I, and we have S(A) = 1+log 2 d = S(AB), S(B) = log 2 d, S(A : B) = log 2 d. The maximal classical mutual information that can be extracted by local measurements and no classical communication is shown in [24] to be I max = 1 2 log 2 d. If, however, Alice makes a projective measurement on A 1 on the {|t = 0 , |t = 1 } basis and sends her measured value of t as one classical bit to Bob, then he will know which of the two bases {|i B } and {U 1 |i B } should be used for projective measurements in order to obtain the maximal classical mutual information. This quantity takes on the value log 2 d bits, and the net increase of the classical correlation is 1 2 log 2 d bits. Note that this effect is in accordance with our complementarity gap discussion in the previous subsection: until Bob  2 log 2 d = L(ρ AB ). As another example, we consider the following separable state.
σ AB has the marginal states, σ A = 1 2d I, σ B = 1 d I, and it is easy to show that S(A) = 1 + log 2 d = S(AB), S(B) = log 2 d, S(A : B) = log 2 d and I max = log 2 d. Hence Q = 0 for this state. If Alice measures A 1 and sends her value of t by one classical bit to Bob as in the previous example, then the maximal classical mutual information that they can obtain by measurements is still only log 2 d bits. There is no classical correlation locked in the state σ AB , i.e., L(σ AB ) = Q = 0. In this case, the same basis should be used by Bob irrespective of the value of t measured by Alice, and hence there is also no complementarity issue in this case.
Let I L (ρ AB ) denote the obtainable classical correlation, maximized for a given state, ρ AB , over all LOCC protocols, Π, while subtracting the cost, c, of the classical communication within the given protocol, I L (ρ AB ) ≡ max Π {I ′ max −c}. I.e., I ′ max denotes the maximal amount of classical correlation obtainable by the classical communication and by local measurements after exchange of c bits of classical communication.
From our definition of the maximal classical mutual information without any communication it follows that, I max ≤ I L (ρ AB ), and we obtain the maximal locking effect of the quantum state ρ AB , The examples in this section suggest a connection between Q and the locking effect, especially for states where S (A : B) is not larger than S(A) and S(B) (for example, separable states). Further studies may assess whether all or part of the information quantified by Q can be unlocked by transmission of classical information between Alice and Bob. It is proposed in [26] that the measurement-induced disturbance measure D (see its definition in the next section) is connected to the the locking effect, here we propose to use Q instead of D since Q(ρ AB ) is uniquely defined for any ρ AB and is a continuous function of ρ AB in contrast to the properties of D (see Example C in Sec. V).

IV. OTHER MEASURES OF NONCLASSICAL CORRELATIONS
To remove the need to optimize the information over different measurements, it has been proposed [27] to use a particular choice for the measurements. I e (ρ AB ) thus denotes the classical correlation obtained by local projective measurements onto the eigenbases of the reduced density matrices on both Alice's and Bob's subsystem. The difference between S(A : B) and I e (ρ AB ) is sometimes referred to as the measurement-induced disturbance measure D(ρ AB ). It is obvious that I e (ρ AB ) ≤ I max (ρ AB ), and hence, D(ρ AB ) ≥ Q(A : B).
An alternative measure, C A (ρ AB ), of the classical correlation in a given state ρ AB is proposed in [28], where is the state of B conditioned on the outcome of the i th POVM on A, which occurs with the probability p A i = T r AB (K A i ρ AB K A † i ). The quantum discord J A is now defined as the difference between the quantum mutual information and C A (ρ AB ), Equivalently, we define where the measurement is instead assumed to take place on system B, and the quantum discord J B = S(A : B) − C B (ρ AB ). The two discords J A,B may not in general be the same.
The quantum discord was originally defined in a similar manner in [13] but with a restriction to projective measurements on subsystem A or B and without the maximization over all local measurement, i.e., in a manner that depends explicitly on the measurement performed on the subsystems. It is, indeed, difficult to determine (8), and in many studies (for example, references [15,26,29]) only projective measurements are considered, and we hence denote C p A(B) (ρ AB ) the classical correlation (8) with maximization over projective measurements only, and the corresponding quantum discord (9) is denoted by , but it is not clear whether they actually coincide. Since

can be viewed as the Holevo bound on the accessible information Bob (Alice) can obtain by his (her) local measurement on the ensemble {p
where we have introduced a similar superscript p for the maximum mutual information obtainable with restriction to projective measurements by Alice and Bob. Therefore, it follows that our measure of nonclassicality is larger than or equal to the quantum discord, both when these quantities are defined with respect to general measurements, Q(A : B) ≥ J A(B) , and with respect to projective measurements, Q p (A : B) ≥ J p A(B) .
The purpose of this section is to study some examples to illustrate the practical difficulties of dealing with the different classical information measures and to display the non-trivial interplay between the different aspects of nonclassical correlations of quantum states.
A. Example: Maximum classical mutual information by projective measurements on qubits.
Consider a family of two-qubit states, where the reduced density matrices of both qubits are proportional to the identity operator. Such states can be written in terms of Pauli matrices, and can be transformed by a local unitary transformation to the following form where |r j | are the singular values of the matrix w jk . The eigenvalues of σ AB or ρ AB are given by , and λ 3 = 1+r1+r2−r3 4 . Therefore , with δ = r 1 n Ax n Bx + r 2 n Ay n By + r 3 n Az n Bz , and the mutual information of the measurement results is given by

Local projective measurements performed on A and B can be written M
The maximal mutual information is obtained when |δ| reaches its maximum. Let n T A = (n Ax , n Ay , n Az ) (similarly for B) denote a row vector and D = diag{r 1 , r 2 , r 3 } denote a diagonal matrix. We then have where r m = max{|r 1 |, |r 2 |, |r 3 |} determined by the singular values of the matrix w jk in (10). Therefore the maximal obtainable classical correlation of the family of two-qubit states in (10) by local projective measurements is given by This value is achieved when A and B are projected onto the local bases that give the singular value decomposition of w jk . With the restriction to projective measurements we thus find which happens to be equal to the quantum discord J p A(B) obtained in [15]. As noted in [15], J p A(B) , and hence Q p (A : B), are larger than the entanglement of formation for some states and smaller for others.

B.
Example: Werner states in arbitrary dimensions, non-classicality and entanglement.
Even though numerous studies suggest a strong relation between nonclassical correlations and quantum entanglement, Q is not a measure of entanglement since separable quantum states exist, for which the maximum classical mutual information obtained by measurements does not exhaust the quantum mutual information.
As an example, we consider a Werner states of a d × d dimensional system [30], where P = d i,j=1 |i j| ⊗ |j i|. For this state, a straightforward calculation yields while projective measurements in the bases {|i , |j }, used in the definition of P , yield the maximal mutual information The Werner state (17) may also be used to illustrate another property of the classical information measures based on projective measurements. The local density matrices ρ A and ρ B of the Werner state are both proportional to the identity matrices. This implies that the choice of projective measurements in the eigenbases of ρ A and ρ B is not uniquely defined, and may in fact provide a range of values for the classical mutual information of the detection records. Maximum information is obtained, as argued in the previous example, by the use of the same bases {|i , |j } on the two systems as are used in the definition of the operator P . Using that pair of eigenbases, I e = I p max . If on the other hand, Alice uses the basis {|i }, and Bob uses an eigenbasis {|j u }, which is mutually unbiased [31,32], to the basis {|j }, we obtain I e = 0. This reflects the complementarity between the information available by measurements on mutually unbiased bases (see Sec. VI and Refs. [33,34,35,36,37,38]), but it also shows that I e is not uniquely defined, when the local density matrices have degenerate eigenvalues.
Another consequence of this ambiguity is that I e and hence D become non-continuous functions of the density matrix in the vicinity of these degeneracies. We may for example add an infinitesimal term, ǫ d i=1 λ i |i i| ⊗ d j=1 δ j |j j| to the Werner state, with different λ i 's and δ j 's, to ensure that for any nonzero ǫ, the standard bases are the unique eigenstates of ρ A and ρ B . In contrast, adding a similar infinitesimal term ǫ involving the mutually unbiased basis of system B, causes the other unique choice of basis. These two choices have infinitesimally close density matrices, but they have unique values of I e ≈ log 2 ( d d−α ) + 1−α d−α log 2 (1 − α) and I e = 0, respectively.
In contrast, I max and Q(ρ AB ) (as well as I p max and Q p (ρ AB )) do not have such a problem, they are uniquely defined for any ρ AB and are continuous functions of ρ AB . D. Example: States with finite Q and vanishing quantum discord JA or JB.
Since quantum discord and our non-classicality Q both try to quantify the non-classical correlation in a quantum state, it is very interesting to know the difference between these two quantities. As shown in Sec. IV, our nonclassicality Q is always no less than quantum discord J A(B) , i.e., Q(A : B) ≥ J A(B) (and Q p (A : B) ≥ J p A(B) ) for any state ρ AB . When ρ AB is a pure state, it is easy to verify that Q(A : B) = J A(B) = S(A), namely, both our non-classicality Q and quantum discord J A(B) are equal to the amount of entanglement in the state. And when ρ AB has the form in (5), it is also obvious to show that both non-classicality Q and quantum discord J A(B) vanish. Now we show that Q is finite while J A = 0 for a family of states. It is shown in [28] that for the family of states, where {|i } is a set of orthonormal states of A, It therefore follows that the quantum discord, J A = J p A = 0 for this family of states. And it is also shown in [39] that this is the only kind of states with a vanishing J A . This is also precisely the kind of states discussed at the end of Sec. III A, illustrating the role of complementarity, when Bob attempts to extract maximal information by measurements but is faced with the problem, that the different ρ B i will generally require complementary optimal measurement strategies. If the different ρ B i s do not commute, Q > 0 for the states in (20), and the classical information cannot exhaust the quantum mutual information. The states in (20) with non-commuting ρ B i s are the only kind of states with a finite Q and vanishing J A .
However, if both J A = 0 and J B = 0 for a state ρ AB , then ρ AB must have the form in (5), and therefore, Q = 0. So there does not exist a state such that Q is finite while both J A and J B is zero.
It is generally difficult to find the optimum measurement strategy both on the general case of POVMs and when we are restricted to projective measurements. Even in the case where ρ AB is a state of two qubits, it is not clear whether local projective measurements are sufficient to extract the maximal classical correlation, i.e., whether I max (ρ AB ) = I p max (ρ AB ). One attempt to address this issue was given in [40], in connection with a different problem: a quantum binary channel is used to communicate symbols encoded in two states, and the mutual information is maximized over the receiver's measurement strategies. It is shown in [40] that projective measurements yield the same information as two-outcome POVMs. Two-outcome measurements, however, do not exhaust all POVMs, and the analysis in [40], does not rule out the possibility that, e.g., three-outcome POVMs may lead to a higher I max than projective measurements on the qubits. By contrast, it is shown in [41] that when symbols are encoded in three states, an appropriate POVM measurement yields strictly more information than any projective measurement.
Based on the analysis in [41], we can construct an example where we can prove that I p max < I max . Suppose system A is a qutrit and system B is a qubit, and with the Bloch vectors of the pure states |φ i B forming equal angles 2π 3 in the same plane. In order to extract the maximal mutual information, Alice simply projects system A onto the basis states {|i A } (see below). Now system B is in one of the three state |φ i B with an equal probability of 1/3, and Bob needs to perform an appropriate measurement in order to extract the maximal mutual information. This is exactly the situation in [41] where a certain POVM measurement with 3 elements extracts strictly more information than any projective measurement on Bob's qubit. Therefore, for the state in (22), I p max < I max . We need to show that for the state in (22), and more generally for the states in (20), in order to obtain I max , Alice should indeed simply project system A onto the basis states {|i A }. Assume that the best measurement strategy for Bob is a rank-one POVM { s K B s K B s = I}, then after Bob obtains result s, the state of system A is = I}, the joint probability that she gets j and Bob gets s is given by However, the same joint probability distribution can also be obtained if Alice first projects system A onto the basis states {|i A }, and thereafter she performs the POVM { j K A j K A j = I}. This is a Markov chain, as p(j|is) = p(j|i) = | K A j |i | 2 ; and we have the same joint probability distribution p js . Therefore the mutual information I{A : B} obtained from the joint probability distribution {p is } is larger or equal to the one obtained from {p js }. In other words, the maximal mutual information can always be obtained when Alice projects her system onto the basis states {|i A } and Bob chooses an appropriate measurement strategy.

VI. COMPLEMENTARITY OF CLASSICAL CORRELATION WITH DIFFERENT MUBS ON ONE SIDE
In this section we will quantify the consequences of complementarity by a specific analysis of projective measurements in different mutually unbiased bases, i.e., bases, where each basis vector in one basis has the same squared overlap with all basis vectors in the other bases. In the following, we suppose Bob performs a fixed POVM measurement, while Alice performs a projective measurement along one of two or more MUBs at her choice. We shall derive upper bounds of the sum of classical correlation with Alice's different choices of MUBs.
Proposition 2 Suppose Bob performs an arbitrary general measurement {M s = K B † s K B s | s M s = I} on B, while Alice performs on A a complete projective measurement onto either the basis {|i 1 > |i = 1, · · · , d A } (hence define I 1 {A : B}), or on a second basis {|i 2 > |i = 1, · · · , d A } (I 2 {A : B}) which is mutually unbiased to the first basis, then Proof. We have i|s ; i} + H{p (2) i|s ; i} .
Here p(s) = T r(M B s ρ B ) and p (m) The entropic uncertainty relation [34] implies with K = ⌊ MdA dA+M−1 ⌋; and (30) follows from (28) and the inequality [37,42] M m=1 H{p (m) Proposition 3 certainly holds true when d A is a power of a prime and M = d A + 1. However using the results from [43] 3 m=1

H{p
together with (31) this leads to the following tighter bound Proposition 4 For d A = 2 and M = 3 we have , and when d A is a power of a prime and M = d A + 1 we have We have the following upper bounds which are independent of the state.
Corollary 5 When d A is a power of a prime, and M = d A + 1, The inequality in (37) follows from (36) with the observation that T r(ρ 2 A ) ≥ 1/d A . By expansion of the logarithm, we can verify that the quantity on the right hand side of (37) is a number that lies between d A − 1 and d A , but strictly less than d A for any d A ≥ 2, hence we have (38).
It should be pointed out that, for a special case when the shared state ρ AB is a maximally entangled state, the problem considered in this section is equivalent to the problems considered in [36,38] according to the source duality [35] or the atemporal diagram approach [44].

VII. NONCLASSICAL CORRELATIONS IN QUANTUM COMPUTATION
The previous sections have all been of a formal nature and have presented examples of quantitative differences between the magnitudes of different correlation measures. In this section, we consider states whose nonclassicality is linked with their performance as resources for a specific task: speed-up of quantum computing. Entanglement is an interesting and valuable quantum resource in quantum communication and computing. But it is not indispensable, as illustrated by the paradigmatic, deterministic quantum computation with one quantum bit (DQC1) proposed in [45]. This example provides an exponential speed-up over the best known classical algorithms and yet has a limited amount of entanglement and, in some regimes, no distillable entanglement at all [46]. We shall see that the non-classicality Q defined above is closely related to the non-local resource responsible for the speed-up of the computation in the DQC1 model.
In the generalized DQC1 model [46], one attempts to estimate the normalized trace, 2 −n Tr(U n ), of a unitary operator U n acting on n qubits. One assumes that the n qubits are all prepared in the fully mixed state with equal probabilities on both qubit states |0 and |1 , while the application of the unitary operator U n is controlled by a single qubit, in the polarized initial state 1 2 (I 1 + ασ 3 ). The overall state of the n + 1 qubits after the Hadamard transformation on the control qubit and the interaction, illustrated in Fig. 3 is given by where I n and U n are, respectively, the identity and unitary operator on the Hilbert space of n qubits. This state is separable with respect to the division between the control qubit and the collection of target qubits, which is most readily seen by expanding the state on the eigenstate basis {|e i } of the unitary operator U n with eigenvalues exp(iθ i ), This equation shows how measurement of the expectation value of the σ 1 and σ 2 Pauli matrices on the single control qubit give respectively α2 −n i cos(θ i ) and α2 −n i sin(θ i ) and hence provides the normalized trace of U n , and the number of runs required to achieve a given precision is proportional to 1/α 2 but independent of the dimension 2 n of the n-qubit Hilbert space. The control qubit (system A) is completely disentangled from the n-qubit target register (system B), and the exponential speed-up of the DQC1 model over classical algorithms is hence not due to entanglement. Eq. (40) is precisely of the form (20) and it hence has Q > 0, unless all eigenvalues exp(iθ i ) are identical, and U is the identity operator (no action on the target registers). It is straightforward to calculate the quantum mutual information where β = 2 −n αTr(U n ) → 0 for a typical unitary U n . By typical, we mean it is chosen randomly according to the Haar measure on U(2 n ). For such a unitary, the eigenvalues are almost uniformly distributed on the unit circle with large probability [47]. Now we proceed to calculate the classical mutual information. Suppose system A is projected onto two basis states |1 A = {cos θ |0 + e iφ sin θ |1 } and |2 A = {sin θ |0 − e iφ cos θ |1 }, and system B is projected onto a set of basis states |s B . The joint probability p is for system A to be found in the ith state and system B to be found in the sth is given by From this joint probability distribution, we determine the classical mutual information of the measurements, and in order to calculate I p max , we need to maximize over all possible choices of the local bases for both A and B. The maximization will depend on the specific unitary U n , and is prohibitively complicated, and we will only consider typical unitaries and assume eigenvalues uniformly distributed on the unit sphere. We then get with δ s = α sin 2θRe[e −iφ s B | U n |s B ]. The maximal value of this I{A : B} is obtained when δ s → α cos 2πs 2 n , which can be achieved when θ → π/4, φ → 0 and |s B are chosen as the eigenstates of U n . Therefore, assuming also β → 0 in the evaluation of S(A : B) (41), the nonclassicality is given by with δ s = α cos 2πs 2 n . For n = 10, Q is shown in Fig. 4 as a function of the control qubit polarization α. Even though there is no entanglement between the control qubit and the other qubits at any point during the computation, Q is nonzero and increases as the polarization α increases and the DQC1 model becomes more effective. This is suggestive that Q quantifies the correlations that enable the advantage in quantum computation.
In [29], the quantum discord, and in [26,27], the measurement-induced disturbance measure have been similarly used to characterize the correlations in the DQC1 model. The behavior of Q for the DQC1 model is qualitatively similar to that of the quantum discord and of the measurement-induced disturbance.

VIII. CONCLUSION
In this paper, we have investigated the quantum and classical correlations stored in bipartite quantum states. We have suggested to quantify the classical correlations by the maximum classical information, that can be retrieved by local measurements, and shown that the difference between the quantum mutual information of the state and this I max provides a good measure of non-classicality, in the sense that it vanishes when there are no non-classical correlations, and it gives non-vanishing results for states whose non-classicality are not revealed by other measures. We have argued that the state-dependent gap between the quantum and classical mutual information is associated with the complementarity between the local observables which together characterize the properties of the system. The same gap provides a quantitative measure of the computing power in the DQC1 proposal, characterized so far by other measures, and examples suggest that a non-vanishing value for the gap also witnesses a non-vanishing locking effect.
Our measure as well as some of the alternative measures of correlations suffer from the immense difficulty of calculating their value, because they assume an optimization over all possible measurement strategies. This implies, like in the theory of entanglement, that many scattered results exist, but we do not yet have a full overview of the types of correlations that can be extracted from quantum states. We hope that our work may stimulate the search for analytical and numerical methods for the effective determination of these measures. We also find it very interesting to investigate under which circumstances classical communication in the presence of a complementarity gap may be used to partly or fully unlock the classical correlations.
Proof of proposition 1. The first part of the proof is similar to that of the Holevo bound [18,19,20]. Suppose Alice introduces an ancilla A 1 and Bob introduces B 1 , the systems A 1 , A, B, B 1 are in the following initial state, Now Alice performs the measurement {M A i } on A and stores her measurement result in A 1 , the overall state becomes, Here  where p i ρ B i = T r A (K A i ρ AB K A † i ), and ρ B = i p i ρ B i . Here the first inequality follows from the fact that the quantum mutual information does not increase by discarding a subsystem, and the second inequality follows from the fact that quantum mutual information does not increase under local operations. Similarly we can get the symmetric relation: On the other hand we also have Therefore the proposition is proved.