## Abstract

This paper studies the potential advantages of correlated answers in hypothetical tests of a simple interactive type. In these tests, an individual is presented with a question, to which he or she must respond with an answer, leading to an outcome of *pass* or *fail*. In quantum information theoretic variants of these tests, we show it is possible for an individual to correlate their answers across multiple tests in a way that produces a striking non-classical behaviour. Specifically, there exist tests for which no strategy can lead to the outcome *pass* with certainty, but where answers to multiple, independently administered tests can be correlated so that at least one test is passed with certainty. This phenomenon, which gives rise to a perfect form of *hedging* when considered in a game-theoretic setting, is quantum in nature: it is not possible in classical variants of the tests we consider.

## 1. Introduction

It is well known that quantum information theory allows for correlations among measurement outcomes that are stronger than those possible within any classical theory. Bell (1964) inequality violations provide the archetypal example within this category, where space-like separated measurements of entangled particles yield correlated measurement outcomes that are incompatible with local hidden-variable theories. This paper describes a different scenario in which this phenomenon arises, and provides an example showing a striking difference between quantum and classical theories in this scenario.

We will begin with an operational description of the scenario that we consider in the paper. The following discussion does not assume a particular choice of underlying theory, and will be later specialized to the cases of classical and quantum theory. In simple terms, we imagine that one individual subjects another individual to a *test*, and for convenience we will refer to the individual administering the test as *Alice* and to the test-taker as *Bob*. One may envision that Alice and Bob are devices rather than individuals; we only choose the later point of view for the convenience of using the names Alice and Bob. The tests under consideration are to have the following simple form.

Alice prepares a

*question*and sends it to Bob.Bob responds by sending an

*answer*to Alice.Based on Bob’s answer, as well as whatever memory she has of her own question, Alice decides whether Bob has

*passed*or*failed*the test.

In a purely classical setting, one may imagine that Alice’s behaviour is described by a probabilistic process, whereby her questions are selected according to some probability distribution and her final decision might also involve the use of randomness. In the quantum setting, Alice’s questions may take the form of quantum information—possibly entangled with quantum memory of her own—and she may expect quantum information from Bob in return. In both the classical and quantum settings, we make the assumption that Bob has a complete description of the process by which Alice operates, and is generally interested in maximizing his probability of passing the test.

In complexity theory, hypothetical tests along these lines are often studied as a tool to classify computational problems; the corresponding model is known as the *interactive proof system* model (Babai & Moran 1988; Goldwasser *et al.* 1989). Interactive proof systems that allow for interactions consisting of multiple rounds are often considered; but in our discussion, we will focus only on those interactive proof systems that consist of a single question followed by a response—or, in other words, those interactions that correspond to the scenario we consider in this paper.

In the context of interactive proof systems, the individual we have called Alice is called the *verifier* and Bob is called the *prover*. The verifier’s computational ability is limited (usually to probabilistic or quantum polynomial time) while the prover’s computational ability is unrestricted. For each input string *x* to a fixed decision problem *L*, the prover and verifier engage in an interaction wherein the prover attempts to convince (or prove to) the verifier that the string *x* should be accepted as a yes-instance of the problem *L*. To say that such a system is valid for the problem *L* means two things: one is that it must be possible for a prover to convince the verifier to accept with high probability if the input is truly a yes-instance of the problem, and the second is that the verifier must reject no-instances of the problem with high probability, regardless of the prover’s actions. The first requirement is called the *completeness* condition, and is analogous to the condition in formal logic that true statements can be proved. The second condition is called the *soundness* condition, and is analogous to the condition that false statements cannot be proved.

We will now discuss the specific questions studied in this paper. To do so, for a fixed choice for Alice’s test, we let *p* denote Bob’s *optimal probability* of passing this test. Formally speaking, without any assumptions on an underlying mathematical model, *p* may be defined to be the *supremum* of all passing probabilities for Bob, taken over all possible choices of his strategy. (In both the classical and quantum models, the supremum will always be achieved, so that it may safely be replaced by the maximum.) By assumption, Alice always makes a definitive decision about whether Bob passes or fails, so he necessarily fails the test with probability at least 1−*p*.

Now, consider that Alice instantiates two *independent* copies of her test *in parallel*: no correlations exist between the two questions that she presents to Bob, and the processes by which she determines whether Bob passes or fails are completely independent as well. There are a variety of questions that one may ask about this type of situation, including the following.

What is the optimal probability with which Bob passes

*both*tests?What is the optimal probability with which Bob passes

*at least one*of the tests?

It is natural to guess that Bob’s optimal probability to pass both tests is *p*^{2}, while his optimal probability to pass at least one test is 1−(1−*p*)^{2}. These are, of course, the optimal probabilities if he treats the two tests independently.

In the classical setting, the probabilities *p*^{2} and 1−(1−*p*)^{2} are indeed optimal over all classical strategies, including those that do not respect the independence of the two tests; Bob cannot correlate the tests to his advantage in either case. While these claims can be proved directly with little difficulty, we will see that they fall out naturally as special cases in our analysis of the quantum setting.

In the quantum setting, the natural guess is indeed correct for the first question (as we will later discuss in greater detail): if Bob aims to pass both tests, there is no advantage for him to correlate the two tests. This fact is known to those who have studied quantum interactive proof systems (Kitaev & Watrous 2000), and it is a consequence of a more general result concerning semidefinite programmes (Mittal & Szegedy 2007). For the second question, on the other hand, the natural guess turns out to be wrong. We demonstrate this by giving an example where Bob can correlate the two independent tests in such a way that he passes at least one of the two tests *with certainty*, despite the fact that *p*<1. More specifically, our example describes a test where Bob’s optimal passing probability for a single instantiation of the test is , while he *never* fails both tests if he correlates two independent instantiations in the right way.

There are other settings in which quantum effects that are not possible in the classical world have been discovered to be possible in an interaction between two parties. However, our setting differs from some of the best-known such situations, such as the CHSH game (Clauser *et al.* 1969), and the Mermin–Peres magic squares game (Mermin 1990; Peres 1990). In our setting, we do not have two parties collaborating to achieve a non-classical outcome. Instead, we have a *prover–verifier* setting, in which Bob is trying to convince Alice in order to pass a test.

Bob’s ability to correlate two independent tests in the way just described can be seen as a perfect form of *hedging*, as the following (highly fictitious) scenario illustrates. Bob is offered the opportunity to take part in two potentially lucrative but somewhat risky games of chance, run by Alice. The two games are completely independent and identical in nature: for each, he must put forth $1 million of his own money to take part, and he has approximately an 85 per cent chance to win if he plays optimally. For each game he wins, Bob receives $3 million (representing a $2 million gain over his initial $1 million investment), while he receives nothing (and loses his $1 million initial investment) if he loses. For the sake of this example, we are to consider that a $1 million or greater loss means ruin for Bob.

These are, of course, highly compelling games of chance, and many people would not hesitate to take out a $2 million loan to play both: the expected gain from each one is roughly $1 550 000, and the chance for a loss in both, if they are treated independently, is only about 2.25 per cent. Bob, however, is a highly risk-averse person: while he would enjoy being a millionaire, he cannot accept a 2.25 per cent chance of ruin. Classically speaking, Bob can do nothing to avoid a 2.25 per cent chance of ruin, so he will choose not to play. If the two games are modelled by quantum information as in our example, however, Bob can be *guaranteed* a $1 million return, and can therefore play without fear: an appropriately chosen quantum strategy allows him to hedge his bets perfectly.

## 2. Preliminaries

We assume the reader to be familiar with the basics of quantum information theory, and suggest Nielsen & Chuang (2000) to those who are not. The purpose of this section is to summarize some of the notation and basic concepts we make use of, and to highlight a couple of concepts that may be less familiar to some readers.

### (a) Basic notation, states, measurements and channels

For any finite-dimensional complex Hilbert space , we write to denote the set of linear operators acting on , we write to denote the set of Hermitian operators acting on , we write to denote the set of positive semidefinite operators acting on , we write to denote the set of positive definite operators acting on , and we write to denote the set of density operators acting on . For Hermitian operators , the notations *A*≥*B* and *B*≤*A* indicate that *A*−*B* is positive semidefinite, and the notations *A*>*B* and *B*<*A* indicate that *A*−*B* is positive definite.

Given operators , one defines the inner product between *A* and *B* as 〈*A*,*B*〉=Tr(*A***B*). For Hermitian operators , it holds that 〈*A*,*B*〉 is a real number and satisfies 〈*A*,*B*〉=〈*B*,*A*〉. For every choice of finite-dimensional complex Hilbert space and , and for a given linear mapping of the form , there is a unique mapping (known as the *adjoint* of *Φ*) that satisfies 〈*Y*,*Φ*(*X*)〉=〈*Φ**(*Y*),*X*〉, for all and .

A *register* is a hypothetical device that stores quantum information. Associated with a register X is a finite-dimensional complex Hilbert space , and each quantum state of X is described by a density operator . *Qubits* are registers for which . A *measurement* of X is described by a set of positive semidefinite operators , indexed by a finite non-empty set of measurement outcomes *Σ*, and satisfying the constraint (the identity operator on ). If such a measurement is performed on X while it is in the state *ρ*, each outcome *a*∈*Σ* results with probability 〈*P*_{a},*ρ*〉. A *quantum channel* is a completely positive and trace-preserving linear mapping of the form that describes a hypothetical physical process that transforms each state *ρ* of a register X into the state *Φ*(*ρ*) of another register Y. The set of all channels of this form is denoted . The identity channel that does nothing to a register X is denoted .

The Hilbert space corresponding to a pair of registers (X_{1},X_{2}) is the tensor product of the spaces corresponding to X_{1} and X_{2}. Independent states, measurements and channels are represented by elementary tensors in the following straightforward way.

If registers X

_{1}and X_{2}are independently prepared in states*ρ*_{1}and*ρ*_{2}, then the state of the pair (X_{1},X_{2}) is given by the density operator*ρ*_{1}⊗*ρ*_{2}.If registers X

_{1}and X_{2}are independently measured with respect to the measurements described by the collections and , the resulting measurement on the pair (X_{1},X_{2}) is described by the collection {*P*_{(a1,a2)}:(*a*_{1},*a*_{2})∈*Σ*_{1}×*Σ*_{2}}, where .If registers X

_{1}and X_{2}are independently transformed into registers Y_{1}and Y_{2}according to the channels and , respectively, then the transformation of the pair (X_{1},X_{2}) into the pair (Y_{1},Y_{2}) is described by the channel .

### (b) Linear mappings on operator spaces

Suppose and assume that a standard orthonormal basis {|1〉,…,|*n*〉} of has been selected. With respect to this basis, one defines the Choi–Jamiołkowski operator of a linear mapping as
The mapping *J* is a linear bijection from the space of mappings of the form to the operator space . It is well known that *Φ* is completely positive if and only if , and that *Φ* is trace-preserving if and only if (Jamiołkowski 1972; Choi 1975).

While the Choi–Jamiołkowski operator of a linear mapping is most commonly considered when *Φ* is a channel, the concept is useful in more general settings (as is illustrated in Gutoski & Watrous (2007) and Chiribella *et al.* (2009), for instance). The following lemma, whose proof makes use of the Choi–Jamiołkowski operator of a particular mapping, gives one technical example that will be useful later in the paper.

### Lemma 2.1

*For every operator* *, there exists a mapping* *that possesses the following property: for every mapping* *and every operator* *the equation
*
*holds. Moreover, if A is positive semidefinite, then Ψ*_{A} *is completely positive.*

### Proof.

The unique mapping for which (the entry-wise complex conjugate of *A*) possesses the required property. This fact is easily verified for operators *A* taking the form *A*=|*i*〉〈*j*|⊗|*k*〉〈*l*|, in which case *Ψ*_{A}(*Z*)=|*i*〉〈*k*|*Z*|*l*〉〈*j*|, and it follows for general operators by the conjugate-linearity/linearity of the inner product. Under the assumption that *A* is positive semidefinite, so too is , from which it follows that *Ψ*_{A} is completely positive.

### (c) Semidefinite programming

Semidefinite programming is a topic that has found several interesting applications within quantum computing and quantum information theory in recent years. It is a valuable analytic tool, as well as a computational one. Here, we provide just a brief summary of semidefinite programming that is focused on the narrow aspects of it that we use. More comprehensive discussions can be found in Vandenberghe & Boyd (1996), Lovász (2003), de Klerk (2002), Boyd & Vandenberghe (2004), for instance.

A semidefinite programme is a triple (*Φ*,*A*,*B*), where

is a Hermiticity-preserving linear mapping, and

and are Hermitian operators,

for some choice of finite-dimensional complex Hilbert spaces and . We associate with the triple (*Φ*,*A*,*B*) two optimization problems, called the *primal* and *dual* problems, as follows:

The optimal primal value *α* and optimal dual value *β* of this semidefinite programme are defined as
and
(It is to be understood that the supremum over an empty set is and the infimum over an empty set is , so *α* and *β* are well-defined values in the set . Our interest, however, will only be with semidefinite programmes for which *α* and *β* are finite.)

It always holds that *α*≤*β*, which is a fact known as *weak duality*. The condition *α*=*β*, which is known as *strong duality*, does not hold for every semidefinite programme, but there are simple conditions known under which it does hold. The following theorem provides one such condition (that has both a primal and dual form).

### Theorem 2.2 (Slater’s theorem for semidefinite programmes)

*Let* (*Φ*,*A*,*B*) *be a semidefinite programme and let* *α* *and* *β* *be its optimal primal and dual values*.

*If*.*β*is finite and there exists a positive definite operator for which*Φ*(*X*)=*B*, then*α*=*β*and there exists an operator such that*Φ**(*Y*)≥*A*and 〈*B*,*Y*〉=*β**If*.*α*is finite and there exists a Hermitian operator for which*Φ**(*Y*)>*A*, then*α*=*β*and there exists a positive semidefinite operator such that*Φ*(*X*)=*B*and 〈*A*,*X*〉=*α*

In words, the first item of this theorem states that if the dual problem is feasible and the primal problem is *strictly feasible*, then strong duality holds and the optimal dual solution is achievable. The second item is similar, with the roles of the primal and dual problems reversed.

## 3. Interactive measurements

We now discuss the scenario described in §1 in greater mathematical detail, focusing on the quantum setting. As is to be expected, the classical setting may be seen as a special case of the quantum setting.

Tests of the form described in §1 are modelled by *interactive measurements*, which are essentially measurements of quantum channels: an interactive measurement consists of a state preparation and a measurement, to be applied to a given quantum channel. More formally speaking, an interactive measurement is specified by three finite-dimensional complex Hilbert spaces , and , along with two objects defined over these spaces:

A state on the spaces and represented by a density operator .

A measurement on the spaces and .

If such an interactive measurement is applied to a given channel , the probability associated with each measurement outcome *a*∈*Σ* is given by
An interactive measurement of a channel *Φ* is illustrated in figure 1.

Suppose that an interactive measurement, specified by a state and a measurement , has been fixed. For a given measurement outcome *a*∈*Σ*, one may consider both the *maximum* and *minimum* probability with which the outcome *a* appears, over all choices of the quantum channel *Φ* upon which the interactive measurement is performed. Let us denote the maximum probability by *M*(*a*) and the minimum probability by *m*(*a*) for each *a*∈*Σ*, so that
and
(One notes that the above quantities are the maximization and minimization, respectively, of a linear function on the compact set of quantum channels . Thus, the use of the maximum and minimum rather than the supremum and infimum is justified.)

The quantities *M*(*a*) and *m*(*a*) are expressible as the optimal values of semidefinite programmes, as we now describe. For each *a*∈*Σ* we let be defined as
3.1
for *Ψ*_{ρ} being the mapping described by lemma 2.1. We then have the following equality for each *a*∈*Σ* and any choice of a channel :
It therefore holds that
The operator *J*(*Φ*) ranges over all choices of satisfying as *Φ* ranges over all channels , and therefore the following semidefinite programme has optimal primal value *M*(*a*):

A slight modification yields a semidefinite programme whose optimal primal value is *m*(*a*):

(The most straightforward way to fit this semidefinite programme to the precise formalism described in §2 is to exchange maxima and minima and replace *Q*_{a} with −*Q*_{a}, which yields a semidefinite programme for −*m*(*a*). One could alternately extend the definition of semidefinite programmes in a straightforward way to allow for minimizations in the primal problem and maximizations in the dual. The particular choice of these alternatives that one takes has no effect on our analysis.)

It is clear that strict feasibility holds for each of the problems presented: taking *X* and *Y* to be appropriately chosen scalar multiples of the identity operator suffices to observe that these properties hold. Strong duality therefore holds for both semidefinite programmes by theorem 2.2, and optimal solutions are achieved for each of the four problem formulations.

## 4. Correlations among independent interactive measurements

We now consider the situation in which two interactive measurements, described by pairs (*ρ*_{1},{*P*_{a1}:*a*_{1}∈*Σ*_{1}}) and (*ρ*_{2},{*P*_{a2}:*a*_{2}∈*Σ*_{2}}), are performed independently, as suggested in figure 2. While the interactive measurements are themselves performed independently, it is not assumed that the channel respects this independence. Indeed, it is straightforward to devise examples where some choice of the channel *Φ* causes a correlation in the outcomes produced by the two measurements. The main focus of this section is on the nature of the correlations that are possible through the selection of various channels *Φ*, especially as these correlations relate to the scenario described in §1.

Consider first the maximum output probability associated with a given pair of measurement outcomes (*a*_{1},*a*_{2})∈*Σ*_{1}×*Σ*_{2}. In the following subsection, we provide a proof that the maximum probability *M*(*a*_{1},*a*_{2}) with which this pair is output is given by *M*(*a*_{1},*a*_{2})=*M*_{1}(*a*_{1})*M*_{2}(*a*_{2}), where *M*_{1}(*a*_{1}) and *M*_{2}(*a*_{2}) denote the maximum output probabilities of *a*_{1} and *a*_{2} with respect to the individual interactive measurements with which they are associated. Thus, to maximize the probability of outputting (*a*_{1},*a*_{2}), there is absolutely no gain in choosing a channel *Φ* that correlates the two interactive measurements: the optimal probability is achieved by some choice *Φ*=*Φ*_{1}⊗*Φ*_{2} that respects the independence of the two interactive measurements.

Remarkably, a similar property does not generally hold when the maximum is replaced by the minimum: we provide an example for which , but *m*(*a*_{1},*a*_{2})=0.

### (a) Analysis for multiplicativity

To see that *M*(*a*_{1},*a*_{2})=*M*_{1}(*a*_{1})*M*_{2}(*a*_{2}), we may consider the semidefinite programme representing the optimal probability *M*(*a*_{1},*a*_{2}):

(The unitary operator *π* is defined by the action *π*(*y*_{1}⊗*y*_{2}⊗*x*_{1}⊗*x*_{2})=*y*_{1}⊗*x*_{1}⊗*y*_{2}⊗*x*_{2} for all , , , .)

One first observes that the inequality *M*(*a*_{1},*a*_{2})≥*M*_{1}(*a*_{1})*M*_{2}(*a*_{2}) is straightforward: the choice *X*=*X*_{1}⊗*X*_{2} for primal-optimal choices of *X*_{1} and *X*_{2} gives a primal feasible solution achieving the objective value *M*_{1}(*a*_{1})*M*_{2}(*a*_{2}).

Similarly, the upper bound *M*(*a*_{1},*a*_{2})≤*M*_{1}(*a*_{1})*M*_{2}(*a*_{2}) may be established by considering the dual problem. For and being dual-optimal we have Tr(*Y* _{1})=*M*(*a*_{1}) and Tr(*Y* _{2})=*M*(*a*_{2}), and thus Tr(*Y* _{1}⊗*Y* _{2})=*M*_{1}(*a*_{1})*M*_{2}(*a*_{2}). Moreover, as *Q*_{a1} and *Q*_{a2} are positive semidefinite and the constrains and hold, it follows that and are positive semidefinite. Using the fact that *A*≥*B* and *C*≥*D* implies *A*⊗*C*≥*B*⊗*D* for any choice of positive semidefinite operators *A*, *B*, *C* and *D*, we have
The operator *Y* _{1}⊗*Y* _{2} is therefore dual feasible, so it is established that *M*(*a*_{1},*a*_{2})≤*M*(*a*_{1})*M*(*a*_{2}).

We note that this is a particular instance of a semidefinite programme obeying the *product rule* considered by Mittal & Szegedy (2007), where the argument just presented is applied to a more general class of semidefinite programmes.

When the maximum is replaced by the minimum, however, the above argument breaks down. In this case, the semidefinite programme whose optimal value is *m*(*a*_{1},*a*_{2}) takes the following form:

The upper-bound *m*(*a*_{1},*a*_{2})≤*m*_{1}(*a*_{1})*m*_{2}(*a*_{2}) is easily established by once again taking *X*=*X*_{1}⊗*X*_{2} for primal optimal points *X*_{1} and *X*_{2}. For the lower-bound *m*(*a*_{1},*a*_{2})≥*m*_{1}(*a*_{1}) *m*_{2}(*a*_{2}), however, a problem arises: unlike the situation for the maximum, one may not conclude that the operators and are positive semidefinite for optimal dual solutions *Y* _{1} and *Y* _{2} (and indeed they may not be positive semidefinite in some cases). One may fail to prove that the operator *Y* =*Y* _{1}⊗*Y* _{2} is dual-feasible in this case, so that a lower-bound is not established.

### (b) An example showing non-classical behaviour

We now present our example of a quantum test that allows for a strong correlation of the sort described in §1. The test is as follows.

Alice prepares a pair of qubits (X,Z) in the state and sends X to Bob.

Bob applies any quantum channel he likes to X, obtaining a qubit Y that he sends back to Alice. As a result of his action, the pair (Y,Z) then has some particular state .

Alice measures (Y,Z) with respect to the projective measurement {

*P*_{0},*P*_{1}}, where and*P*_{1}=*vv** for The outcome 1 is to be interpreted that Bob passes the test, while the outcome 0 means that he fails.

Now, if Bob can produce a given state in step 2, it must hold that
4.1
no action that Bob performs on his registers can influence the state of Alice’s register. The probability that Alice obtains the outcome 1 is 〈*P*_{1},*σ*〉=*F*(*vv**,*σ*)^{2}, where *F*(⋅,⋅) denotes the *fidelity* function and where the equality holds by virtue of the fact that *vv** is pure. By the monotonicity of the fidelity function under partial tracing, we have
for
By a direct calculation, we determine
Alice therefore outputs 1, indicating that Bob passes the test, with probability at most .

Finally, for two instantiations of the test described above, we consider what happens when Bob applies the phase flip |00〉↦−|00〉, |01〉↦|01〉, |10〉↦|10〉, |11〉↦|11〉 on the two qubits he receives. Alice has prepared the state
and Bob’s phase flip transforms this state to
Writing
we find that
When Alice measures this state with respect to the measurement {*P*_{0},*P*_{1}}, she obtains exactly one outcome 0 and one outcome 1. Thus, it holds that *m*(0,0)=0; Bob passes exactly one of the two tests with certainty.

### (c) Analysis for the classical setting

We now observe that the behaviour exhibited in the example just described cannot happen in the classical setting.

Suppose that and describe an interactive measurement as before. As is typical in quantum information theory, the classical setting corresponds to the special case in which these operators are all diagonal (with respect to the standard basis). Note that when the density operator *ρ* and a given measurement operator *P*_{a} are diagonal, it holds that the operator defined by (3.1) is also diagonal.

Now suppose that *a*∈*Σ* is a measurement outcome for which *Q*_{a} is diagonal, and consider the semidefinite programme whose optimal primal value describes the minimum probability associated with the outcome *a* (i.e. whose optimal value is *m*(*a*)):

We will observe that there exists a dual optimal solution *Y* that is positive semidefinite. It will be helpful for this purpose to let and denote the completely dephasing channels corresponding to and , respectively. More precisely, the mapping is defined by
for 1≤*i*,*j*≤*n*, where {|1〉,…,|*n*〉} is the standard basis of , and is defined similarly with respect to the standard basis of .

Now consider an arbitrary dual optimal solution . The mapping is completely positive, so the relation implies that
The diagonal operator is therefore dual feasible. As preserves trace, achieves the same dual objective value as *Y* _{0}, and is therefore optimal as well. Finally, define
In other words, *Y* is obtained from by replacing each negative diagonal entry with 0. The inequality follows from the inequality together with the observation that each diagonal entry of *Q*_{a} is necessarily non-negative (because *Q*_{a} is positive semidefinite). As , it follows that *Y* is also dual optimal. (The reality, of course, is that *Y* =*Λ*_{X}(*Y* _{0}), for otherwise *Y* _{0} would not have been dual optimal.) Finally, consider the situation in which two classical interactive measurements, described by pairs (*ρ*_{1},{*P*_{a1}:*a*_{1}∈*Σ*_{1}}) and (*ρ*_{2},{*P*_{a2}:*a*_{2}∈*Σ*_{2}}), are performed. One finds that the equality
4.2
considered before must now hold by an analysis similar to the one for the maximum output probability case: positive semidefinite optimal dual solutions exist for the semidefinite programme described above for each operator *Q*_{a1} and *Q*_{a2}, allowing for the straightforward construction of optimal primal and dual solutions to the semidefinite programme whose optimal value is *m*(*a*_{1},*a*_{2}), thereby implying (4.2).

## 5. Conclusion

This paper has considered correlated strategies against independently administered hypothetical tests of a simple interactive type. It has been demonstrated that correlations arising in quantum information theoretic variants of these tests can exhibit a non-classical *hedging* type of behaviour.

One may, of course, consider situations in which more than two independent tests are performed, where a variety of statistics may be of interest. For example, one may consider Bob’s optimal probability to pass some threshold number *t* of some (possibly large) number *k* of independently administered tests. Based on our results, we know that a surprising behaviour exists even for the case *t*=1 and *k*=2, and it would be interesting to investigate the possible asymptotic behaviours that can arise.

Our work may have relevance in settings considered in cryptography, where certain protocols might very well be abstracted as tests of the sort we have considered. Our results demonstrate that collective quantum attacks to such protocols may exhibit striking non-classical and counterintuitive properties, reinforcing the practice of giving very careful consideration to attacks of this nature.

Another motive of this work is the problem of error reduction through *parallel repetition* for quantum interactive proof systems. Indeed, suppose that a particular verifier has been specified (for a fixed decision problem *L*) so that the following conditions hold.

For each yes-instance

*x*to*L*, it is possible for a prover to convince the verifier to accept with probability at least*α*.For each no-instance

*x*to*L*, the verifier always accepts with probability at most*β*, regardless of the prover’s actions.

It may be, for instance, that *α*=1/2+*δ* and *β*=1/2−*δ* for some small constant *δ*>0. A more desirable situation is one in which *α* is replaced by 1−*ε* and *β* is replaced by *ε* for a small value of *ε*. The process of specifying a new verifier based on the original one that meets stronger completeness and soundness conditions, such as the ones just suggested, is called *error reduction*.

In a purely algorithmic situation, the natural way to reduce error is to gather statistics from multiple independent executions of a given algorithm. For instance, if an algorithm outputs a binary value that is correct (for worst-case inputs) with a probability of at least 2/3 on any single execution of the algorithm, it is straightforward to obtain a new algorithm with a very high probability of correctness: one simply runs the original algorithm independently many times and takes the majority value as the output. A natural adaptation of this idea to interactive proof systems is to define a new verifier that independently runs many instances of the test performed by the original verifier, and accepts if and only if some suitably chosen threshold number of these independent tests would have led the original verifier to acceptance. In the situation under consideration, one is to understand that it is important for the new verifier to run these independent tests in parallel (as opposed to requiring the prover to respond sequentially to the individual tests).

It is not obvious that this works in the context of interactive proof systems for precisely the reason that has been considered in this paper: a hypothetical prover that interacts with many independent executions of an interactive proof system need not respect the independence of these executions. Nevertheless, in the classical setting it has long been known that error reduction through parallel repetition followed by a threshold value computation works perfectly^{1} for (single-prover) interactive proof systems. To say that the reduction is perfect means that if *p* is the optimal success probability for the original verifier, then the optimal probability to cause at least *t* acceptances among *k* independent executions of the original verifier is
5.1
In other words, a prover gains absolutely no advantage in trying to correlate the independent tests performed by the verifier.

In the quantum setting, however, it was not previously known if parallel repetition followed by a threshold value computation could allow for a perfect error reduction (or indeed any error reduction at all for certain values of *α* and *β*). Our results show that parallel repetition followed by a threshold value computation does not lead to a perfect reduction of error: substituting *k*=2, *t*=1 and into (5.1) yields an upper bound of approximately 0.98, which is violated by the strategy, we described in the previous section (which achieves the value 1). We note that parallel repetition does work in the case of *perfect completeness* (i.e. *α*=1), wherein the threshold value computation is replaced by the logical-AND (Kitaev & Watrous 2000), and that there is a more complicated method for error reduction (based on a logical-AND of majorities), which does allow for error reduction in the general case of the setting under consideration (Jain *et al.* 2009).

Based on the semidefinite programming formalism we have described, it is possible to prove an upper bound of
on the probability for a quantum prover to cause at least *t* acceptances among *k* independent executions as considered above. Unfortunately, this expression does not lead to a reduction of errors for a wide range of choices of *α*>*β*. This bound yields a value larger than 1 in some situations, and when the value is smaller than 1 we do not know how closely it can be approached by a valid quantum strategy.

## Acknowledgements

Abel Molina acknowledges support from QuantumWorks, MITACS, a Mike and Ophelia Lazaridis Graduate Fellowship and a David R. Cheriton Graduate Scholarship. John Watrous acknowledges support from NSERC, CIFAR, QuantumWorks and MITACS.

## Footnotes

↵1 The situation is very different for

*multi-prover*interactive proof systems, wherein the subject of parallel repetition is complicated (Raz 1998, 2008; Holenstein 2009).

- Received October 13, 2011.
- Accepted March 14, 2012.

- This journal is © 2012 The Royal Society