Although in general optimization over quantum strategies is
intractable, good upper bounds can often be obtained by considering convex relaxations of the set of valid quantum strategies
for the players (using e.g. semidefinite programming). Here the
game is sufficiently simple that an intuitive argument can be
given which already provides a meaningful bound.
Proof. For simplicity, we start by showing that when η = 0,
then Bob cannot guess Alice’s output with probability 1. A
more careful accounting of the parameters then provides the
claimed bound. Note that is the maximum probability
with which Alice and Bob can succeed in the augmented CHSH
game—for this to happen they must win the CHSH game with
optimal probability ω, and on inputs x = 2 and y = 0, the outputs
a and b must be equal. We assume for contradiction that Bob
can guess Alice’s output (on input x = 2) with probability 1.
We imagine repeated sequential execution of the devices,
with the same fixed inputs x and y, for some number k of
executions. Let , denote Bob’s outputs, and denote
Alice’s outputs, over these k executions. Then the condition on the augmented CHSH game implies that the players’
outputs should match when the inputs are (x, y) = ( 2, 0): .
Also by the assumption of successful guessing, on inputs
( 2, y) for any y the players’ outputs satisfy . It follows that
. The fact that Alice and Bob win the CHSH game
with probability ω implies that for any x ∈ {0, 1}, the relative Hamming distance (by the Chernoff
bound this is sharply concentrated as k grow). It follows
that .
Now suppose Alice knew Bob’s output (we will justify this
assumption later). We claim that this gives Alice an advantage in
guessing Bob’s input y thus providing a contradiction with the
elementary guessing game described at the start of the section.
Alice’s strategy is as follows: if given her input x and output ,
she guesses y = 0 if , and y = 1 otherwise,
where ε is an arbitrarily small constant (depending on k).
First note that if y = 0 then she succeeds with probability
close to 1. This is because as shown above, since ,
for any . On the other hand,
when y = 1, by the CHSH game condition it should be the
case that and . By the triangle
inequality, . It follows that and
cannot both be close to any fixed : i.e. both conditions
and cannot be
simultaneously satisfied. This means that in the case y = 1,
Alice must succeed with probability about 1/2, and therefore
overall Alice can guess Bob’s output with probability close to
3/4. Contradiction.
To justify the assumption that Alice knows Bob’s output
Bob always chooses the same secret input y. Bob select a value
uniformly at random and post-selects on those chunks
where . He communicates the indices of those chunks
to Alice. The information this leaks about y is very small, since
the marginal distribution of must match the marginal dis-
tribution obtained when DA is provided input x = 2, which
does not depend on y; as a consequence the indices of the
with a third input, labeled 2 (each input is chosen with prob-
ability 1/3). If inputs to the players are (x, y) = ( 2, 0) then their
outputs should match. Assuming the no-signaling principle
and the validity of quantum mechanics (specifically, that ω =
cos2 π/8 is the optimal bound in the CHSH game), it is easy to
see that Alice and Bob can win the augmented CHSH game
with probability , which is optimal.
Now we consider adding one more rule to the game, the
“guessing rule”: Bob should always produce a second output,
c ∈ {0, 1}. The guessing rule requires that c should match
Alice’s output a whenever her input is x = 2 (if x ∈ {0, 1} then
there is no requirement on c). We will show that Alice and Bob
cannot achieve close to the optimal probability of in the
extended CHSH game, and simultaneously satisfy the guessing
rule on Bob’s output c with probability close to 1: whatever Bob
does, he cannot collaborate with Alice to succeed in the CHSH
game, while simultaneously producing a valid guess for her output. This is a manifestation of the phenomenon of monogamy
of quantum correlations alluded to earlier. To understand the
significance of this result for the security of protocol E1, note
that it also implies that Alice’s output bit must look somewhat
random to the eavesdropper, even when provided with Alice
and Bob’s inputs. To see this, observe that any such eavesdropper could be lumped together with Bob to derive a successful
strategy in the guessing game described above.
The proof is in the form of a reduction to the following trivial
guessing game. There are two cooperating players, Alice and
Bob. At the start of the game, Bob receives a single bit y ∈ {0, 1}
chosen uniformly at random. The players are then allowed to
perform arbitrary computations, but are not allowed to communicate. At the end of the game, Alice outputs a bit a, and the
players win if a = y. Clearly, any strategy with success probability that deviates from indicates a violation of the no-signaling assumption between Alice and Bob. The idea behind
the use of guessing games is to show that any undesirable
outcome in the cryptographic protocol—such as a successful
strategy for the Eavesdropper—can be bootstrapped into a
successful strategy for Alice and Bob in the trivial guessing
game, thereby contradicting the no-signaling assumption.
Guessing lemma. Suppose that Alice and Bob succeed in
the augmented CHSH game with probability at least ,
where . Then the maximum probability with which
Bob can successfully guess Alice’s output on input x = 2 is at
most 1 − C(η0 − η), where C and η0 are universal constants.
c1
a1a0
≤ 1 − ω
≈ 0.15
≥ 2( 1 – ω) ≈ 0.7
Figure 5. The proof of the guessing lemma. Using the winning condition
for the CHSH game, wherever b1 is the distance between a0 and a1
must be at least 2( 1 – ω). This implies the balls of radius ( 1 – ω)
centered are a0 and a1 are disjoint.