# On the Role of Quantum Communication and Loss in Attacks on Quantum Position
Verification

Rene Allerstorfer111Email<EMAIL_ADDRESS>QuSoft, CWI Amsterdam,
Science Park 123, 1098 XG Amsterdam, The Netherlands  Harry Buhrman222Email:
<EMAIL_ADDRESS>QuSoft, CWI Amsterdam, Science Park 123, 1098 XG
Amsterdam, The Netherlands  QuSoft, University of Amsterdam, Science Park 904,
1098 XH Amsterdam, The Netherlands  Florian Speelman333Email:
<EMAIL_ADDRESS>QuSoft, University of Amsterdam, Science Park 904, 1098 XH
Amsterdam, The Netherlands  Philip Verduyn Lunel444Email:
<EMAIL_ADDRESS>QuSoft, CWI Amsterdam, Science Park 123, 1098 XG
Amsterdam, The Netherlands

(Dated: )

###### Abstract

We study the role of quantum communication in attacks on quantum position
verification. In this work, we construct the first known example of a QPV
protocol that is provably secure against unentangled attackers restricted to
classical communication, but can be perfectly attacked by local operations and
a single round of simultaneous quantum communication indicating that allowing
for quantum communication may break security. We also show that any protocol
secure against classical communication can be transformed into a protocol
secure against quantum communication. We further show, using arguments based
on the monogamy of entanglement, that the task of Bell state discrimination
cannot be done locally with a single round of quantum communication, not even
probabilistically (when we allow attackers to say loss sometimes), making this
the first fully loss-tolerant QPV task secure against quantum communication
attacks. Finally, we observe that any multi-round QPV protocol can be attacked
with a linear amount of entanglement if the loss is high enough.

##  1 Introduction

Geographical position is an important contributor to trust—for example, a
message which provably comes from a secure location in a government
institution, has automatic credence to actually be sent by that government.
Position-based cryptography is the study of using position as a cryptographic
credential. The most basic task here is to certify someone’s position, but
this can be extended to messages that can only be read at a certain location,
or to _authenticating_ that a message came (unaltered) from a certain
location.

We will focus on the task of _position verification_ , which can be used as
the building block for tasks like position-based authentication. For
simplicity, the focus will be on the one-dimensional case, i.e. verifying
one’s position on a line, but the relevant ideas generalize readily to more
dimensions. In our case, protocols will have the form of two _verifiers_ ,
$\mathsf{V_{A}}$ and $\mathsf{V_{B}}$, attempting to verify the location of a
_prover_ $\mathsf{P}$. An adversary to a scheme will take the form of a
coalition of attackers, while the location of $\mathsf{P}$ is empty. We’ll use
$\mathsf{A}$ (or Alice) for the attacker located between $\mathsf{V_{A}}$ and
the location of $\mathsf{P}$, and $\mathsf{B}$ (or Bob) for the attacker
location between the location of $\mathsf{P}$ and $\mathsf{V_{B}}$.

It was shown by Chandran, Goyal, Moriarty, and Ostrovsky [CGMO09] that without
any additional assumptions, position verification is an impossible task to
achieve classically. The quantum study of quantum position verification (QPV)
was first initiated by Beausoleil, Kent, Munro, and Spiller resulting in a
patent published in 2006 [BKMS06]. The topic first appeared in the academic
literature in 2010 [Mal10a, Mal10b], followed by various proposals and ad-hoc
attacks [KMS11, LL11]. A general attack on quantum protocols for this task was
presented by Buhrman, Chandran, Fehr, Gelles, Goyal, Ostrovsky, and Schaffner
[BCF+11], requiring a doubly-exponential amount of entanglement. This attack
was further improved to requiring an exponential amount of entanglement by
Beigi and König [BK11] – much more efficient but still impractically large.
(See also [GLW13, Dol19] for generalizations of such attacks to different
settings, with similar entanglement scaling.)

Additionally, other protocols have been proposed [KMS11, CL15, Unr14, JKPPG21,
BCS21], that combine classical and quantum information in interesting ways,
sometimes requiring intricate methods to attack [BFSS13, Spe16, OCCG20].

In our contribution we present several results on the role of quantum
communication in QPV attacks.

##### The role of quantum communication for attacks on QPV.

Some works [BRSdW11, TFKW13, BFSS13, BCS21] attempt to lower bound the pre-
shared entanglement required from attackers that are allowed a round of
simultaneous _quantum_ communication, while other results, such as [BK11,
RG15, QS15, QLL+15, LXS+16, GC20, OCCG20] assume attackers that are restricted
to communicate only classically.

Even though quantum communication can potentially be simulated by
teleportation, it is not immediately clear how to compare bounds between these
two settings, especially in case where the exact size of the lower bound is of
interest.555For instance, the bound of [RG15] does not fully supersede
[TFKW13], and therefore finding a tight lower bound for the parallel-
repetition of the QPV${}_{\textsf{BB84}}$ protocol against attackers that have
quantum communication remains open. The simplest version of this question can
be asked for unentangled attackers: If a (quantum-question, classical-reply)
QPV protocol is secure against unentangled attackers that communicate
classically, is that protocol also secure against unentangled attackers that
are allowed to use quantum communication?

To that end, we present the following results:

  * •

First, we answer the above question in the negative: We construct a protocol
that is provably secure against unentangled attackers that can use classical
communication, but can be broken by a single round of simultaneous quantum
communication. This shows that some care has to be taken when interpreting
results that restrict to classical messages only.

  * •

Interestingly, we are additionally able to show that our counter-example is in
some sense artificial: Given a protocol that is secure against classical
messages, but insecure when quantum communication is allowed, it is always
possible to transform this protocol into one that is secure when quantum
communication is allowed.

This new protocol can be constructed from the given protocol by applying local
maps to the messages from the verifiers $\mathsf{V_{A}}$, $\mathsf{V_{B}}$,
without having to modify the output predicate. Our proof for this statement
involves a recursive argument, where we view the states after quantum
communication of a successful attack as the input messages to two new
protocols. We then recursively consider an increasing number of new possible
protocols, and use _emergent classicality_ [QR20] to show that a secure
protocol of the required form has to exist.

  * •

We proceed by considering the task of Bell state discrimination666Where the
input is a randomly chosen Bell state. and prove that this task cannot be done
perfectly with only local operations and one round of simultaneous
communication. The proof relies on new arguments based on the monogamy of
entanglement. We consider a purified version of this task in the QPV setting
(delaying the honest measurement to the end of the protocol) and show that the
squashed entanglement [CW04] of the state $\rho_{V_{A}V_{B}}$, on which the
honest Bell measurement is applied to, is upper bounded by
$E_{sq}(V_{A}:V_{B})_{\rho}\leq 1/2$. Hence attackers won’t be able to
perfectly predict the honest result. To get an explicit upper bound on the
attack success probability with quantum communication
$p_{\text{succ}}^{\text{qc}}$ we use the hashing bound from [DW05] which lower
bounds the squashed entanglement, allowing us to upper bound a parameter that
leads to $p_{\text{succ}}^{\text{qc}}\leq 0.926$. We further improve this
bound to $p_{\text{succ}}^{\text{qc}}\leq 3/4$ via a different argument based
on the no-cloning theorem.

We additionally show that even in the lossy scenario it remains that
$p_{\text{succ}}^{\text{qc}}(\eta)<1$ for any transmission rate $0<\eta\leq
1$. This makes the task of Bell state discrimination, and by implication the
QPV protocol based on the SWAP-test [ABSVL22], the first fully loss tolerant
QPV protocol that remains secure in the setting where attackers are allowed
quantum communication.

Finally, we present a result relating loss tolerance and entanglement attacks
in QPV:

  * •

We observe that in a setting with loss any multi-round QPV protocol can be
broken with only a linear amount of pre-shared entanglement if the loss rate
is high enough. In that sense, creating a fully loss tolerant QPV protocol
which requires superlinear entanglement (in the number of qubits involved) is
impossible. This follows directly from a simple observation: if there is no
limit to the loss, the adversaries can attempt quantum teleportation and guess
the teleportation corrections, claiming ‘loss’ if the guess is incorrect.

The aspects of loss and quantum communication are practically very relevant,
since in realistic settings loss rates will be high and, although attackers
are restricted to only one round of simultaneous communication due to the
timing constraints of QPV, they could in principle be able to quantum
communicate and this might give them an advantage.

###  1.1 Structure of the paper

In section 3.1 we present the first QPV protocol that is provably secure
against attackers restricted to quantum communication but broken by a single
round of quantum communication. However, in section 3.2 we show that any
protocol insecure against quantum communication but secure against classical
communication can be transformed into a protocol secure against quantum
communication. In section 3.3 we show that the task of Bell state
discrimination is secure against attackers who are allowed to use quantum
communication. Extending on this result in section 3.4 we also show that this
is strictly secure if we allow attackers to also say loss beside quantum
communication. Finally, in section 3.5 we make the observation that allowing
loss for pre-shared entangled attackers allows for any protocol with high
enough loss rate to be broken with linear entanglement.

##  2 Preliminaries

###  2.1 Notation

We denote parties in QPV protocols by letters A, B, etc. and their quantum
registers as $A_{1}\cdots A_{n}$, $B_{1}\cdots B_{n}$ and so on, respectively.
Sometimes we may refer to “all registers party $\mathsf{X}$ holds” just by X,
giving expression like $\operatorname{Pos}(\mathsf{A}\otimes\mathsf{B})$, for
example. Unless otherwise indicated, $\lVert\cdot\rVert_{p}$ is the usual
$p$-norm. The diamond norm on quantum channels is denoted by
$\lVert\cdot\rVert_{\diamond}$ and is defined as
$\lVert\mathcal{C}\rVert_{\diamond}\coloneqq\max_{\rho}\lVert(\mathcal{C}\otimes\mathbbm{1}_{k})(\rho)\rVert_{1}$
for quantum states $\rho$. Partial transposition of an operator $P$ with
respect to party $\mathsf{B}$ is denoted $P^{T_{\mathsf{B}}}$. The set of PPT-
measurements777I.e. sets of positive semi-definite operators adding up to the
identity, whose partial transposes are positive semi-definite as well. on two
subsystems held by parties A and B, respectively, is
PPT$(\mathsf{A}:\mathsf{B})$. We use the term “Local Operations and Broadcast
Communication” (LOCC) to describe the scenario of a single round of
simultaneous classical communication with local quantum operations before and
after the round of communication. Finally, the image of a function $f$ is
denoted by $\operatorname{Im}(f)$ and for a set $X$ we write $|X|$ for its
cardinality. All other notation is explained in the text.

###  2.2 Quantum position verification

For simplicity, we treat the one-dimensional case here, where all parties are
located on a line. The time needed to implement local operations is considered
negligibly short compared to the time span of the entire protocol. In order to
verify the position of an untrusted party $\mathsf{P}$, two trusted and
spatially separated verifiers $\mathsf{V_{A}},\mathsf{V_{B}}$ send quantum
inputs to $\mathsf{P}$ from each side and ask them to apply a specific quantum
operation. $\mathsf{P}$ has to apply the operation and respond immediately. In
the end the verifiers check if they received an answer in time and consistent
with the input and the demanded task. The attack model is as follows.
Attackers trying to break the protocol are not located at P but want to
convince the verifiers that they are. Two attackers888The scenario of more
attackers can be reduced to the one described above. Indeed, the attackers
closest to P could simply simulate all the other attackers themselves.
$\mathsf{A,B}$ can position themselves between $\mathsf{V_{A}},\mathsf{P}$ and
$\mathsf{V_{B}},\mathsf{P}$, respectively, and intercept the inputs, act
locally, communicate one message to each other and then act locally again
before they have to commit to answers $\tau_{A},\tau_{B}$. They hence have to
simulate the honest quantum operation using only local actions and 1 round of
simultaneous communication. In general, they could also pre-share an entangled
resource state $\eta_{AB}$ at the start of the protocol. This situation is
depicted in figure 1.

$t$$x$$\tau_{A}$$\rho_{A}$$\mathsf{V_{A}}$$\tau_{B}$$\rho_{B}$$\mathsf{V_{B}}$$\mathsf{A}$$\mathsf{P}$$\mathsf{B}$
Figure 1: Space-time diagram of a general QPV protocol. We assume all
information travels at the speed of light. For graphical simplicity we have
put $\mathsf{P}$ exactly in the middle of $\mathsf{V_{A}}$ and
$\mathsf{V_{B}}$ (which is not necessary). The attackers, not being at
position $\mathsf{P}$, would like to convince the verifiers that they are at
$\mathsf{P}$ by simulating the honest operation via local operations and one
round of simultaneous communication.

##  3 QPV and quantum communication

###  3.1 A protocol for which quantum communication gives an advantage over
LOCC

A natural question one might ask is whether there is any advantage for
attackers in QPV protocols if they are allowed to perform local operations and
quantum communication (LOQC) instead of classical communication. In what
follows we will construct an explicit example of a QPV protocol with classical
outputs where there is a finite gap in success probability for LOQC strategies
over LOCC strategies.

First, consider the protocol where two verifiers both send half of either one
randomly picked symmetric Bell state
$\\{\ket{\Phi^{+}},\ket{\Phi^{-}},\ket{\Psi^{+}}\\}$ or the antisymmetric Bell
state $\ket{\Psi^{-}}$, and ask an honest prover whether the entangled state
they have sent is symmetric or antisymmetric. An honest prover who can apply
entangling operations can answer this question with success probability $1$ by
applying a SWAP-test [BCWdW01] on the state. From the analysis of the
corresponding SDP optimized over PPT measurements it turns out that the best
LOCC strategy is upper bounded by $5/6$ (see Appendix A). The LOCC strategy of
measuring both qubits in the computational basis and answering the XOR of the
outcomes attains this success probability, so the upper bound over PPT
measurements is attained by a LOCC measurement.

Now suppose the verifiers send two parallel rounds of the previous protocol
under the condition that the two rounds are either both a random symmetric
Bell state or they are both an antisymmetric Bell state and we ask the prover
whether the input consisted of two symmetric or two antisymmetric states. An
honest prover who can apply entangling operations can still solve this
protocol with success probability $1$ by applying a SWAP-test to one of the
two pairs. Now note that attackers who have access to a quantum channel can
send half of their input state to each other such that both attackers locally
end up with a Bell state which they can perfectly determine. Thus attackers
restricted to quantum communication can attack this protocol perfectly.
Interestingly, it turns out that this is not possible for attackers restricted
to classical communication.

From the analysis of the SDP it turns out that the upper bound for two
attackers restricted to PPT measurements is $17/18$, cf. appendix A. Again
there is a LOCC strategy that makes this bound tight, namely measuring both
pairs in the computational basis and only answering “antisymmetric” if both
pairs have unequal measurement outcomes and respond “symmetric” otherwise.
This strategy is always correct on antisymmetric inputs. And it is only
incorrect on symmetric inputs if both times the state $\ket{\Psi^{+}}$ was
sent, this happens with probability $1/18$, so the total probability of
success of the LOCC protocol then becomes $17/18$. By incorporating loss in
the SDP program as done in [LXS+16] and [ABSVL22], we also find that this
protocol is loss-tolerant.

Thus we have constructed a QPV protocol where the probability of success for
attackers restricted to single round LOCC measurements is strictly lower than
attackers restricted to single round LOQC measurements. This shows that there
can be an advantage for quantum communication over classical communication,
and it could be important in the analysis of the security of QPV protocols.
However, it is clear that our construction is not a very good protocol as
there is redundant information given to the attackers and sending just one of
the two symmetric or antisymmetric states would give a seemingly better
protocol.

###  3.2 Splitting Scheme

In this section we present a procedure that distills a QPV protocol secure
against attackers using a single round of simultaneous quantum communication
from the existence of a QPV protocol that is secure against adversaries
restricted to LOCC operations. We will use that the existence of a perfect
quantum communication attack on a QPV protocol generates two new QPV
protocols, which, when applied recursively, ultimately leads to the existence
of a QPV protocol that is secure against adversaries restricted to LOCC and
cannot be perfectly attacked by adversaries using quantum communication.

Take any QPV protocol in which two verifiers $\mathsf{V_{A}},\mathsf{V_{B}}$
send states $\rho_{A},\rho_{B}$ and ask for the outcome of, say, some
entangling measurement on the joint state $\rho_{AB}$. Suppose the protocol is
secure against adversaries restricted to LOCC, i.e., there is a finite gap in
the probability of success between an honest prover and adversaries restricted
to LOCC operations, but also assume that the protocol can be broken perfectly
by adversaries using quantum communication. In the most general setting the
actions of the adversaries are as follows:

  * •

Adversaries $A,B$ receive $\rho_{A},\rho_{B}$ respectively as input states.

  * •

Apply some local channel
$\mathcal{A}(\rho_{A})=\sigma_{A_{1}A_{2}},\,\mathcal{B}(\rho_{B})=\sigma_{B_{1}B_{2}}$.

  * •

Send some share of their local outcome to the other adversary.

  * •

Apply a measurement on the new local states $\sigma_{A_{1}B_{1}}$ and
$\sigma_{A_{2}B_{2}}$.

  * •

Send the measurement outcome to their respective verifiers.

Now note that both $\sigma_{A_{1}},\sigma_{B_{1}}$ and
$\sigma_{A_{2}},\sigma_{B_{2}}$ can be used as input states to define two new
QPV protocols, where the measurement an honest prover needs to apply is equal
to the measurement the attackers would apply in the quantum communication
attack in the original protocol. Then the probability of success for the
honest verifier in the newly defined protocol is the probability of success of
the adversaries using quantum communication in the previous protocol, which we
assumed to be perfect.

Note that any LOCC attack on one of these newly arising protocols was already
a valid LOCC attack in the previous protocol with the inputs $\rho_{A}$ and
$\rho_{B}$. The attackers can simply apply the local channels
$\mathcal{A},\mathcal{B}$, discard the state they don’t use and apply their
attack. Also note that if the input states $\rho_{A},\rho_{B}$ were product
states the input states in the newly created protocol are also product states.
We have therefore split the QPV protocol into two new protocols using only the
existence of a perfect quantum communication attack.

$t$$x$$\mathsf{P}$$a$$\rho_{A}$$\sigma_{B_{1}}$$\sigma_{A_{1}}$$\mathsf{V_{A}}$$a$$\rho_{B}$$\mathsf{V_{B}}$$\sigma_{A_{2}}$$\sigma_{B_{2}}$$\mathsf{A}$$\mathsf{B}$

$\sigma_{A_{2}B_{2}}$$t$$x$$\mathsf{P}$$a$$\sigma_{A_{2}}$$\mathsf{V_{A}}$$a$$\sigma_{B_{2}}$$\mathsf{V_{B}}$$\sigma_{A_{1}B_{1}}$$t$$x$$\mathsf{P}$$a$$\sigma_{A_{1}}$$\mathsf{V_{A}}$$a$$\sigma_{B_{1}}$$\mathsf{V_{B}}$

$t$$x$$\mathsf{P}$$a$$\sigma_{A_{2}}$$\tau_{B_{3}}$$\tau_{A_{3}}$$\mathsf{V_{A}}$$a$$\sigma_{B_{2}}$$\mathsf{V_{B}}$$\tau_{A_{4}}$$\tau_{B_{4}}$$\mathsf{A}$$\mathsf{B}$$t$$x$$\mathsf{P}$$a$$\sigma_{A_{1}}$$\tau_{B_{1}}$$\tau_{A_{1}}$$\mathsf{V_{A}}$$a$$\sigma_{B_{1}}$$\mathsf{V_{B}}$$\tau_{A_{2}}$$\tau_{B_{2}}$$\mathsf{A}$$\mathsf{B}$

$\tau_{A_{4}B_{4}}$$t$$x$$\mathsf{P}$$a$$\tau_{A_{4}}$$\mathsf{V_{A}}$$a$$\tau_{B_{4}}$$\mathsf{V_{B}}$$\tau_{A_{3}B_{3}}$$t$$x$$\mathsf{P}$$a$$\tau_{A_{3}}$$\mathsf{V_{A}}$$a$$\tau_{B_{3}}$$\mathsf{V_{B}}$$\tau_{A_{2}B_{2}}$$t$$x$$\mathsf{P}$$a$$\tau_{A_{2}}$$\mathsf{V_{A}}$$a$$\tau_{B_{2}}$$\mathsf{V_{B}}$$\tau_{A_{1}B_{1}}$$t$$x$$\mathsf{P}$$a$$\tau_{A_{1}}$$\mathsf{V_{A}}$$a$$\tau_{B_{1}}$$\mathsf{V_{B}}$

Figure 2: Visual representation of splitting into two new QPV protocols from
the existence of a quantum communication attack on a single QPV protocol. Two
attackers $A,B$ receive inputs $\rho_{A},\rho_{B}$ and apply some channel
$\mathcal{A}(\rho_{A})=\sigma_{A_{1}A_{2}},\mathcal{B}(\rho_{B})=\sigma_{B_{1}B_{2}}$
and send parts of their outcome to the other party. This procedure defines two
new QPV protocols. If there again exists a perfect quantum communication
attack for both new protocols, then by the same argument we can define 4 new
QPV protocols, and so on.

Now there are two options for the newly defined protocols:

  * •

There does not exist a perfect attack using quantum communication for at least
one of the two new QPV protocols, in which case we have shown the existence of
a QPV protocol that is safe against adversaries using quantum communication
and we are done.

  * •

For both protocols there exists a perfect attack using quantum communication.
In which case we can apply our previous argument to generate 4 new QPV
protocols. See Figure 2 for a visual representation of this splitting
argument.

The previous options are true for all arising QPV protocols after splitting
and we wish to show the existence of a QPV protocol safe against quantum
communication. We therefore suppose all of the induced QPV protocols after
splitting $n$ times can be attacked perfectly using quantum communication for
any $n\geq 2$.

Note that the input states sent from verifier $\mathsf{V_{A}}$ in the induced
QPV protocols after splitting only depend on the previous input states send
from $\mathsf{V_{A}}$ and vice-versa for the input states from
$\mathsf{V_{B}}$. We can write this action as channels
$\Lambda^{A}_{n}:\mathcal{D}(A)\to\mathcal{D}(A_{1}\otimes\dots\otimes
A_{2^{n}})$, mapping $\rho_{A}\mapsto\sigma_{A_{1}\ \dots\ A_{2^{n}}}$, and
$\Lambda^{B}_{n}:\mathcal{D}(B)\to\mathcal{D}(B_{1}\otimes\dots\otimes
B_{2^{n}})$, mapping $\rho_{B}\mapsto\sigma_{B_{1}\ \dots\ B_{2^{n}}}$. The
idea of this proof is that the reduced states $\sigma_{A_{i}}$ and
$\sigma_{B_{i}}$ become approximately classical, and that attackers could
immediately measure their incoming states and share the classical measurement
outcome instead of sending some quantum message. This would lead to a
contradiction since the success probability of this procedure would be upper
bounded by the LOCC bound of the original QPV protocol, while at the same
time, by assumption, this attack should become approximately close to a
perfect one. To be more precise, we use Theorem 3.1 on the emergent
classicality of channels from [QR20].

######  Theorem 3.1 (Qi-Ranard).

Consider a quantum channel
$\Lambda:\mathcal{D}(A)\to\mathcal{D}(B_{1}\otimes...\otimes B_{n})$. For
output subsets $R\subset\\{B_{1},...,B_{n}\\}$, let
$\Lambda_{R}\equiv\operatorname{Tr}_{\bar{R}}\circ\Lambda:\mathcal{D}(A)\to\mathcal{D}(R)$
denote the reduced channel onto R, obtained by tracing out the complement
$\bar{R}$. Then for any $|Q|,|R|\in\\{1,...,n\\}$, there exists a measurement,
described by a positive-operator valued measure (POVM) $\\{M_{\alpha}\\}$, and
an “excluded” output subset $Q\subset\\{B_{1},...,B_{n}\\}$ of size $|Q|$,
such that for all output subsets $R$ of size $|R|$, disjoint from $Q$, we have

$\|\Lambda_{R}-\mathcal{E}_{R}\|_{\diamond}\leq
d^{3}_{A}\sqrt{2\ln(d_{A})\frac{|R|}{|Q|}},$ (3.1)

using a measure-and-prepare channel

$\mathcal{E}_{R}(X):=\sum_{\alpha}\operatorname{Tr}(M_{\alpha}X)\sigma_{R}^{\alpha}$
(3.2)

for some states $\\{\sigma^{\alpha}_{R}\\}_{\alpha}$ on $R$, where
$d_{A}=dim(A)$ and $\|...\|_{\diamond}$ is the diamond norm on channels. The
measurement $\\{M_{\alpha}\\}$ does not depend on the choice of $R$, while the
prepared states $\sigma_{R}^{\alpha}$ may depend on $R$.

Applying the theorem and setting the size of the excluded output set for both
channels $\Lambda_{n}^{A},\Lambda_{n}^{B}$ to $|Q_{A}|=|Q_{B}|=2^{n-1}-1$, we
have, by the pigeonhole principle, that for some index
$i\in\\{1,\dots,2^{n}\\}$ both output sets $A_{i},B_{i}$ must be in the sets
disjoint from $Q_{A}$ and $Q_{B}$. Setting the size of the reduced channels to
$|R_{A}|=|R_{B}|=1$, we see that in both cases the reduced channel
$\operatorname{Tr}_{\bar{R}}\circ\Lambda^{A/B}_{n}$ converges to a measure-
and-prepare channel in the number of splittings $n$ for any output:

$\|\operatorname{Tr}_{\bar{R}_{A/B}}\circ\Lambda^{A/B}_{n}-\mathcal{E}_{R_{A/B}}\|_{\diamond}\leq
8\sqrt{\frac{2\ln(d_{A/B})}{2^{n-1}-1}}.$ (3.3)

The theorem implies that the reduced channels that maps the input states
$\rho_{A}\mapsto\sigma_{A_{i}}$ and $\rho_{B}\mapsto\sigma_{B_{i}}$ become
approximately close to measure-and-prepare channels. Crucially, the
measurements $\\{M^{A/B}_{\alpha}\\}$ in the respective measure-and-prepare
channels do not depend on the choice of $R$. This gives rise to an LOCC attack
in the original QPV protocol from which we started. Two attackers $A,B$ simply
apply the local measure-and-prepare channels
$\mathcal{E}_{R_{A}},\mathcal{E}_{R_{B}}$ and exchange the classical
measurement outcomes $\alpha_{1},\alpha_{2}$. Both attackers then know the
state
$\sum_{\alpha_{1}}p_{\alpha_{1}}\sigma^{\alpha_{1}}_{A_{i}}\otimes\sum_{\alpha_{2}}p_{\alpha_{2}}\sigma^{\alpha_{2}}_{B_{i}}$
which is arbitrarily close to $\sigma_{A_{i}}\otimes\sigma_{B_{i}}$ in $n$.
Since for any QPV protocol the POVM measurement that the honest verifier has
to apply is publicly known, both attackers can calculate the probability
distribution of the answers of an honest prover. Using shared randomness to
generate an equal answer both attackers can now mimic the probability of
success of an honest verifier arbitrarily well.

This LOCC attack allows attackers to answer correctly with a probability of
success that converges to the honest probability of success in the number of
splittings $n$. By assumption $n$ can be arbitrarily large and thus the
attackers have an LOCC attack that performs arbitrarily well. However, since
for our protocol at the start there is a finite gap between the LOCC
probability of success and the honest probability of success, we have a
contradiction and conclude that at some level in the recursion there must
exist a QPV protocol that cannot be attacked perfectly. That protocol must
then be safe against unentangled adversaries restricted to quantum
communication arises.

###  3.3 Security of QPV${}_{\textsf{Bell}}$ against quantum communication

In this section we give the first example of a classically loss-tolerant QPV
protocol that is secure against attackers restricted to quantum communication.
Furthermore we will show that there is no perfect attack with loss in the
quantum communication setting for this protocol, making it the first example
of a protocol that is secure against lossy quantum communication attacks with
no pre-shared entanglement. We will give two different proofs that both show
security against quantum communication, one based on monogamy of entanglement
and one based off a no-cloning argument. The monogamy of entanglement gives a
worse bound, but seems to be a more protocol-agnostic approach to proving
security in the quantum communication setting, making its derivation still
useful.

The protocol we look into is the Bell state discrimination problem. Two
verifiers send as inputs the respective qubits of one of the four Bell states
($\ket{\Phi^{+}},\ket{\Phi^{-}},\ket{\Psi^{+}},\ket{\Psi^{-}}$) and ask the
prover which Bell state he receives. An honest prover can answer this task
perfectly by doing a Bell measurement. With an SDP and a similar analysis as
in [ABSVL22], we can show that this protocol is secure and loss-tolerant
against attackers restricted to classical communication. An optimal attacking
strategy turns out to measure the qubits in the computational basis, which
distinguishes $\\{\ket{\Phi^{+}},\ket{\Phi^{-}}\\}$ from
$\\{\ket{\Psi^{+}},\ket{\Psi^{-}}\\}$ and then to guess one of the two Bell
states as an answer. This has success probability $1/2$ and is optimal.

To analyze security against attackers restricted to quantum communication we
look the protocol in the following equivalent purified way.

  * •

The inputs of the protocol will be the second qubit of the maximally entangled
state $\frac{1}{\sqrt{2}}(\ket{00}+\ket{11})_{V_{A}A}$ and
$\frac{1}{\sqrt{2}}(\ket{00}+\ket{11})_{V_{B}B}$.

  * •

The honest prover has to do a Bell measurement, this is now an entanglement
swapping operation where the entanglement between the verifiers and the prover
gets swapped to entanglement between the two verifiers and entanglement
between the two qubits the prover holds. The prover then sends out his
classical measurement outcome $i$ to the verifiers.

  * •

The verifiers check whether the entanglement swapping operation was successful
by applying a Bell measurement on their joint state and check whether their
measurement outcome is the same as the answer of the prover. The probability
of successfully attacking the protocol now corresponds to the provers having
the correct Bell state as measurement outcome, averaged over all possible Bell
states, i.e.
$p_{\text{succ}}=\frac{1}{4}\sum_{i}\operatorname{Tr}[\ket{\text{Bell}_{i}}\bra{\text{Bell}_{i}}\rho_{V_{A}V_{B}}^{i}]$.

Note that from the point of prover nothing changes from the original Bell
state discrimination protocol. The honest prover still needs to perform a Bell
state measurement on his incoming qubits and send his measurement outcome to
both verifiers.

The idea of this proof is that by reformulating the QPV${}_{\textsf{Bell}}$
protocol as an entanglement swapping protocol we can use the monogamy of
entanglement property between the qubits that remain at the verifiers and the
quantum systems attackers create. Furthermore, while it is hard to say
anything about the quantum systems attackers might send to each other, the
states the verifiers keep are always in their control.

As stated in section 3.2 the most general quantum communication attack is for
attackers to split their inputs into two quantum systems. They hold on to one
and forward the other system to the other attacker. After the quantum
communication round the attackers hold the reduced states
$\rho_{A_{1}}\otimes\rho_{B_{1}}$ and $\rho_{A_{2}}\otimes\rho_{B_{2}}$,
respectively. Since there is no more further communication, for a quantum
attack to be successful in generating entanglement between the two verifiers,
it is sufficient look at only one of the two attackers locally999Attackers
have to act in a coordinated way in QPV, but in particular each attacker also
needs to have a local success probability at least as big as the global one..
We will use this fact in our proof to show that they cannot perform this task
perfectly using quantum communication.

$\mathsf{V_{A}}$$\scriptstyle{e_{A_{1}}\leq
1/2}$$\scriptstyle{e_{A_{2}}}$$\mathsf{A_{1}}$$\mathsf{V_{B}}$$\scriptstyle{e_{B_{1}}}$$\scriptstyle{e_{B_{2}}}$$\mathsf{B_{1}}$$\mathsf{A_{2}}$$\mathsf{B_{2}}$
(a) Entanglement structure when attackers measure and commit to an answer.
W.l.o.g. $e_{A_{1}}\leq 1/2$.

$\mathsf{V_{A}}$$\mathsf{A_{1}}$$\mathsf{V_{B}}$$\mathsf{B_{1}}$$\scriptstyle{e_{V_{A}V_{B}}\leq
1/2}$ (b) Measuring $\mathsf{A}_{1}\mathsf{B}_{1}$ and sending the result to
$\mathsf{V}_{\mathsf{A}}$ is an LOCC operation on
$V_{\mathsf{A}}(\mathsf{A}_{1}\mathsf{B}_{1}V_{\mathsf{B}})$.

Figure 3: Illustration of the argument based on monogamy of entanglement to
bound the entanglement $e_{V_{A}V_{B}}\leq 1/2$ as described in the main text.
Tracing out $\mathsf{A_{2}B_{2}}$, attacker $\mathsf{A}$ can only swap
$e_{V_{A}V_{B}}\leq 1/2$ ebits to
$\mathsf{V}_{\mathsf{A}}\mathsf{V}_{\mathsf{B}}$.

As an entanglement measure we will use the squashed entanglement. This measure
satisfies several properties useful for our analysis, such as monotonicity
under LOCC operations, general monogamy with no restrictions on the size of
the quantum registers, and it is lower bounded by distillable entanglement
[CW04]. Consider the sketch of the entanglement structure between all quantum
registers in figure 3. By monogamy we have that

$\displaystyle 0\leq E_{sq}(V_{A}:A_{1})_{\rho}+E_{sq}(V_{A}:A_{2})_{\rho}\leq
E_{sq}(V_{A}:A)_{\rho}=E_{sq}(\ket{\Phi^{+}}\bra{\Phi^{+}})=1$ (3.4)

Suppose without loss of generality that $E_{sq}(V_{A}:A_{1})_{\rho}\leq
E_{sq}(V_{A}:A_{2})_{\rho}$, then the inequality implies that
$E_{sq}(V_{A}:A_{1})_{\rho}\leq 1/2$. Let $\Phi$ be the LOCC operation (on
$\mathsf{V_{A}(A_{1}B_{1}V_{B})}$) of measuring the $\rho_{A_{1}B_{1}}$
register and sending the classical measurement result to $\mathsf{V_{A}}$.
Using that squashed entanglement is monotone under LOCC we get the following

$\displaystyle E_{sq}(V_{A}:V_{B})_{\Phi(\rho)}$ $\displaystyle\leq
E_{sq}(V_{A}:A_{1}B_{1}V_{B})_{\Phi(\rho)}$ $\displaystyle\leq
E_{sq}(V_{A}:A_{1}B_{1}V_{B})_{\rho}$ $\displaystyle=E_{sq}(V_{A}:A_{1})\leq
1/2.$ (3.5)

Thus, the squashed entanglement between the two verifiers after any attack
using quantum communication is upper bounded by 1/2. Recall that for an attack
to be successful, the verifiers must share the same Bell state on their
registers $\rho_{V_{A}V_{B}}$ as the answer $i$ they receive from the
attackers in this case single. Since $E_{sq}(\ket{B_{i}}\bra{B_{i}})=1$ it is
immediately clear that
$p_{\text{succ}}=\sum_{i}\operatorname{Tr}[\ket{B_{i}}\bra{B_{i}}\rho_{V_{A}V_{B}}^{i}]/4<1$
and no perfect attack is possible.

Ideally we want $p_{\text{succ}}$ to not only be strictly smaller than $1$,
but to be smaller than $1$ by some finite gap. In what follows we will show
that $E_{sq}(V_{A}:V_{B})\leq 1/2$ implies $p_{\text{succ}}\leq 0.926$, which
implies security against quantum communication. Our proof uses the hashing
bound from [DW05] which lower bounds the squashed entanglement [CW04]. The
inequality states that for any quantum state $\rho_{AB}$,

$\displaystyle S(B)_{\rho}-S(AB)_{\rho}\leq E_{sq}(A:B)_{\rho},$ (3.6)

where $\rho_{B}=\operatorname{Tr}_{A}[\rho_{AB}]$, and $S$ is the von Neumann
entropy.

The idea of this proof is to apply the Werner twirling channel $\mathcal{W}$,
where we integrate over the final two-qubit state between the verifiers. This
channel leaves the antisymmetric (qubit) state invariant, and projects the
remaining part to the symmetric subspace. Furthermore this channel is an LOCC
channel and by monotonicity of the squashed entanglement under LOCC
operations, we have

$\displaystyle 1/2\geq E_{sq}(V_{A}:V_{B})_{\Phi(\rho)}\geq
E_{sq}(V_{A}:V_{B})_{\mathcal{W}(\Phi(\rho))}.$ (3.7)

The resulting state $\mathcal{W}(\Phi(\rho)_{V_{A}V_{B}})$ can then be written
as a mixture of the antisymmetric Bell state with the maximally mixed state
characterized by some $\alpha>0$, that is,

$\displaystyle\mathcal{W}(\Phi(\rho)_{V_{A}V_{B}})=\alpha\ket{\Psi^{-}}\\!\bra{\Psi^{-}}+(1-\alpha)\frac{\mathbbm{1}_{4}}{4}.$
(3.8)

A property of Bell states is that they can be locally transformed into one
another. Therefore, verifiers can always locally change the Bell state that
they receive as an answer from the honest prover to the antisymmetric Bell
state. Therefore any successful attack can be characterized by the probability
of having measurement outcome $\ket{\Psi^{-}}$ on
$\mathcal{W}(\rho_{V_{A}V_{B}})$. Combining the entanglement bound (3.7) with
the hashing bound (3.6) we get the following numerical bound on $\alpha$:

$\displaystyle 1/2$ $\displaystyle\geq
E_{sq}(V_{A}:V_{B})_{\mathcal{W}(\Phi(\rho))}$ $\displaystyle\geq
S(B)_{\mathcal{W}(\Phi(\rho))}-S(AB)_{\mathcal{W}(\Phi(\rho))}$
$\displaystyle=1-S(AB)_{\mathcal{W}(\Phi(\rho))}$ $\displaystyle\iff\ \ \ \ \
\alpha$ $\displaystyle\leq 0.902.$ (3.9)

The probability of success is now upper bounded as follows

$\displaystyle p_{\text{succ}}$
$\displaystyle=\operatorname{Tr}\left[\ket{\Psi^{-}}\\!\bra{\Psi^{-}}\Phi(\rho)_{V_{A}V_{B}}\right]=\mathcal{F}(\ket{\Psi^{-}}\\!\bra{\Psi^{-}},\Phi(\rho)_{V_{A}V_{B}})\leq\mathcal{F}(\mathcal{W}(\ket{\Psi^{-}}\\!\bra{\Psi^{-}}),\mathcal{W}(\Phi(\rho)_{V_{A}V_{B}}))$
$\displaystyle=\operatorname{Tr}\left[\ket{\Psi^{-}}\\!\bra{\Psi^{-}}\mathcal{W}(\rho_{V_{A}V_{B}})\right]=\alpha+\frac{1-\alpha}{4}\leq
0.926,$ (3.10)

where we have used the data process inequality for the fidelity in the first
inequality. This concludes our proof and shows there is a finite gap between
the optimal attack attackers restricted to quantum communication can do and
what an honest prover can do. We suspect that this gap can be made even
larger, the upper bound that we find arises only due to restrictions on the
$A_{1}$ part, the $B_{1}$ part could be unchanged from the input state of $B$.
So our bound gives an expression for the maximal probability if you split the
$A$ part in two parts but get the full $B$ part. Also we have not yet made use
of the fact that both attackers have to answer equally. In the following
section we try to improve the bound using a different approach making use of
both the $A_{1}$ and the $A_{2}$ part.

####  3.3.1 An improved bound via no-cloning

In this section we will show that the optimal approximate cloning bound is
strong enough to give a bound that improves (3.3) in several ways. This
argument gives a bound for any local dimension $d$ of the input, has a clear
operational interpretation and improves the above derived bound for $d=2$. For
the start, assume that the attackers A, B have optimal local success
probabilities $p_{\text{succ}}^{\mathsf{A}},p_{\text{succ}}^{\mathsf{B}}$
respectively. Our argument will be that if these local success probabilities
(and thus also the global attack) were too high, we would be able to construct
a cloning procedure that violates the optimal approximate cloning bound.

In a realistic attack on QPV${}_{\textsf{Bell}}$ it is a requirement that the
answers of A and B are identical in each round. In terms of success
probabilities this means
$p_{\text{succ}}^{\mathsf{A}}=p_{\text{succ}}^{\mathsf{B}}=p_{\text{succ}}^{\mathsf{AB}}$,
the latter denoting the optimal realistic attack. Considering just the local
success probabilities is a relaxation because it in principle allows for
different responses from A and B. It is clear that

$\displaystyle
p_{\text{succ}}^{\mathsf{AB}}\leq\min\left\\{p_{\text{succ}}^{\mathsf{A}},p_{\text{succ}}^{\mathsf{B}}\right\\},$
(3.11)

and we will now proceed to upper bound
$\min\left\\{p_{\text{succ}}^{\mathsf{A}},p_{\text{succ}}^{\mathsf{B}}\right\\}$.
As previously mentioned, the structure of any attack (described at the start
of section 3.2) on QPV${}_{\textsf{Bell}}$ must lead to an entanglement
structure as drawn in Figure 3(a). In particular, the verifiers themselves (or
even just one of them) could create the situation of Figure 3(a) themselves in
their own lab because they know what the optimal success strategies are. They
could simply create the inputs and apply the optimal strategies of A, B to
registers $A,B$. This splits $A\mapsto A_{1}A_{2}$ and $B\mapsto B_{1}B_{2}$.
Imagine now that we add a third input state $\ket{\Phi_{+}}_{V_{C}C}$ in
registers $V_{C}C$ and that the optimal strategy of B is applied to register
$C$, mapping $C\mapsto C_{1}C_{2}$. Note that the state in $C_{1}C_{2}$ is
identical to the one in $B_{1}B_{2}$. This procedure creates the following
entanglement structure:

$\mathsf{V_{A}}$$\mathsf{A_{1}}$$\mathsf{V_{B}}$$\mathsf{B_{1}}$$\mathsf{V_{C}}$$\mathsf{C_{2}}$$\mathsf{A_{2}}$$\mathsf{B_{2}}$$\mathsf{C_{1}}$
Figure 4: Entanglement structure created by someone, say a trusted verifier,
who generated three inputs and applied the optimal local attacker channel
$\mathcal{A}$ of A on one and the analogous channel $\mathcal{B}$ of B on two
of the three inputs. They then apply the optimal measurement of A on registers
$A_{1}B_{1}$ and the one of B on registers $A_{2}C_{2}$.

Afterwards, the optimal measurement of A is applied to registers $A_{1}B_{1}$
and the optimal measurement of B is applied to registers $A_{2}C_{2}$. This
swaps entanglement to the registers $V_{A}V_{B}$ and $V_{A}V_{C}$,
respectively. Tracing all other registers away, we end up with the structure
depicted in Figure 5.

$\mathsf{V_{A}}$$\scriptstyle{\rho_{V_{A}V_{B}}}$$\scriptstyle{\rho_{V_{A}V_{C}}}$$\mathsf{V_{B}}$$\mathsf{V_{C}}$
Figure 5: Using the optimal attack strategies of A and B we may create this
situation.

The state $\rho_{V_{A}V_{B}}$ corresponds to the state giving A her optimal
local success probability in attacking QPV${}_{\textsf{Bell}}$. This is
because we applied the optimal split $A\mapsto A_{1}A_{2}$ and the optimal
local measurement on $A_{1}B_{1}$ in order to remotely prepare
$\rho_{V_{A}V_{B}}$. Likewise, the state $\rho_{V_{A}V_{C}}$ corresponds to
the state giving B her optimal local success probability in attacking
QPV${}_{\textsf{Bell}}$. At this stage $\mathsf{V_{A}}$ could take some state
$\ket{\phi}_{V_{A}^{\prime}}$ and attempt to use the standard teleportation
protocol to teleport it to both $\mathsf{V_{B}}$ and $\mathsf{V_{C}}$. In
general, this will result in some states $\rho_{B}^{\phi}$ and
$\rho_{C}^{\phi}$ at $\mathsf{V_{B}}$ and $\mathsf{V_{C}}$, respectively. The
average teleportation fidelity $f$ between the resultant state and the
original one depends only on the maximally entangled fraction of the resource
state $\rho$ [HHH99], and is given by

$\displaystyle
f=\frac{Fd+1}{d+1}=\frac{\braket{\Phi_{+}}{\rho}{\Phi_{+}}d+1}{d+1},$ (3.12)

for any local dimension $d$. A consequence of optimal asymmetric $1\to 2$
cloning is that the arithmetic mean of the average fidelities fulfills

$\displaystyle\frac{f_{\mathsf{V_{B}}}+f_{\mathsf{V_{C}}}}{2}\leq\frac{5}{6},$
(3.13)

no matter which resource states was used. Plugging in equation (3.12) for each
$f$ in (3.13) yields

$\displaystyle\frac{\braket{\Phi_{+}}{\rho_{V_{A}V_{B}}}{\Phi_{+}}+\braket{\Phi_{+}}{\rho_{V_{A}V_{C}}}{\Phi_{+}}}{2}\leq\frac{5}{6}-\frac{1}{6d}.$
(3.14)

This allows us to bound the average success probability
$(p_{\text{succ}}^{\mathsf{A}}+p_{\text{succ}}^{\mathsf{B}})/2$ as follows.
Note that any Bell state $\ket{B_{i}}$ can be regarded as $\ket{\Phi_{+}}$
with a suitable local unitary $\mathds{1}\otimes U_{i}$ applied to the latter.
We can thus write

$\displaystyle\frac{p_{\text{succ}}^{\mathsf{A}}+p_{\text{succ}}^{\mathsf{B}}}{2}$
$\displaystyle=\frac{1}{d^{2}}\sum_{i=0}^{d^{2}-1}\frac{\braket{\Phi_{+}}{U_{i}^{\dagger}\rho_{V_{A}V_{B}}^{i}U_{i}}{\Phi_{+}}+\braket{\Phi_{+}}{U_{i}^{\dagger}\rho_{V_{A}V_{C}}^{i}U_{i}}{\Phi_{+}}}{2}$
(3.15)
$\displaystyle\leq\frac{1}{d^{2}}\sum_{i=0}^{d^{2}-1}\left(\frac{5}{6}-\frac{1}{6d}\right)$
(3.16) $\displaystyle=\frac{5}{6}-\frac{1}{6d},$ (3.17)

where the inequality follows from the fact that (3.14) holds for any states
$\rho_{V_{A}V_{B}}$ and $\rho_{V_{A}V_{C}}$. Having an upper bound on the
average success probability of A and B also tells us that at least one of
$p_{\textsf{succ}}^{\mathsf{A}}$ and $p_{\textsf{succ}}^{\mathsf{B}}$ is upper
bounded by the same bound. Hence we arrive at our end result

$\displaystyle
p_{\text{succ}}^{\mathsf{AB}}(d)\leq\min\left\\{p_{\text{succ}}^{\mathsf{A}}(d),p_{\text{succ}}^{\mathsf{B}}(d)\right\\}\leq\frac{p_{\text{succ}}^{\mathsf{A}}(d)+p_{\text{succ}}^{\mathsf{B}}(d)}{2}\leq\frac{5}{6}-\frac{1}{6d}.$
(3.18)

We see that for $d=2$ the previously derived bound improves to
$p_{\text{succ}}^{\mathsf{AB}}(2)\leq 3/4$. In other words, if one tries to
discriminate Bell states of local dimension $d$ with only local operations and
one round of simultaneous quantum communication (without pre-shared
entanglement), the success probability is upper bounded as in (3.18).
We still suspect that this bound is not tight because we relaxed the situation
of QPV and only looked at the local success probabilities of A and B, and
their average. In reality, however, A and B are forced to respond with the
same answer. Our argument does not include this coordination101010Our argument
includes that both A and B have to answer, but their responses may differ. and
therefore we think that the realistic success probability
$p_{\text{succ}}^{\mathsf{AB}}$ is only loosely upper bounded by (3.18).

###  3.4 Lossy Quantum Communication Attack on QPV${}_{\textsf{Bell}}$

In the previous part we considered attacks where attackers were allowed to use
quantum communication but were not allowed to answer loss. Allowing attackers
to also answer loss would be the most general setting for attackers who can’t
pre-share entanglement. Unfortunately our previous proof does not hold in the
lossy case, since the operations attackers can apply to their local quantum
registers after quantum communication are not LOCC operations (between the
local attacker registers and the corresponding verifier) if attackers are
allowed to postselect, but rather SLOCC. Thus, the monotonicity of the
squashed entanglement does not hold anymore. Similarly, as already pointed out
in [HHH99], average teleportation fidelities may be higher than the bound
(3.12) if one allows post-selection. However, we still prove that there can be
no perfect lossy quantum communication attack on the Bell state discrimination
protocol, i.e. $p_{\text{succ}}(\eta)<1$ for any transmission rate
$\eta\in(0,1]$.

$\mathsf{V_{A}}$$\mathsf{A_{1}}$$\mathsf{V_{B}}$$\mathsf{B_{1}}$$\mathsf{V_{C}}$$\mathsf{C_{2}}$$\mathsf{A_{2}}$$\mathsf{B_{2}}$$\mathsf{C_{1}}$
Figure 6: Entanglement structure including a third hypothetical verifier
$\mathsf{V_{C}}$ and attacker $\mathsf{C}$ who applies an isometry $W_{C\to
C_{1}C_{2}}$ to his hypothetical input.

The argument goes as follows. Suppose there is a perfect lossy quantum
communication attack, then for any loss rate there must be some moment where
both attackers decide to play. Condition on this event taking place, and
consider the moment before both attackers measure their quantum systems.
Suppose we now perform the measurement on the $A_{1}B_{1}$ quantum system,
then by assumption we must get some Bell state $i$ (indicating the correct
one) as a measurement outcome with probability $1$, thus generating a
maximally entangled state between the verifiers $V_{A},V_{B}$. Now consider
the possibility of another verifier $V_{C}$ who also sends as an input a half
of an EPR pair, and some attacker $C$ who applies the exact same splitting
operation on her input as attacker $B$ (see figure 6), thus locally
$\rho_{B_{2}}=\rho_{C_{2}}$. By definition of a QPV protocol the measurement
outcome we get from $A_{2},B_{2}$ will be $i$ with probability $1$.

What would now happen if we apply the measurement of the attackers on the
$A_{2},C_{2}$ system? If this measurement is conclusive then it must be
correct with probability 1, thus creating a maximally entangled state between
$V_{A},V_{C}$, which would violate monogamy of entanglement since $V_{A}$ is
already maximally entangled with $V_{B}$. We conclude that the only possible
measurement outcome on the $A_{2},C_{2}$ system is an inconclusive
‘$\varnothing$’ outcome.

Crucially, the measurement on $\rho_{A_{2}B_{2}}$ will always be conclusive
while the measurement on
$\rho_{A_{2}C_{2}}=\rho_{A_{2}}\otimes\rho_{C_{2}}=\rho_{A_{2}}\otimes\rho_{B_{2}}$
will always be inconclusive. Using this fact we can perfectly distinguish the
state $\rho_{A_{2}B_{2}}$ from $\rho_{A_{2}}\otimes\rho_{B_{2}}$, by simply
applying the measurement an attacker would apply. However, the states
$\rho_{A_{2}B_{2}}$ and $\rho_{A_{2}}\otimes\rho_{B_{2}}$ are never orthogonal
to each other, thus there can be no procedure that perfectly discriminates the
two quantum states without saying loss. This contradicts our findings, because
the above is a hypothetical procedure that perfectly distinguishes the two
quantum states.

We conclude that our assumption of a perfect lossy quantum communication
attack must be wrong, which proves our claim. Thus we see that in general the
QPV${}_{\textsf{Bell}}$ cannot be perfectly attacked by unentangled attackers,
which is the strongest statement we can make if we require attackers to not
pre-share any entanglement. This argument cannot be extended to a finite gap
in the attacking probability because of the subtlety that the measurements on
$\rho_{A_{1}B_{1}}$ and $\rho_{A_{2}C_{2}}$ can be correlated. If attackers
are allowed to make some errors, then the measurements on these states can be
correlated such that they can be both conclusive but the measurement on
$\rho_{A_{2}C_{2}}$ will then just be wrong, so monogamy of entanglement may
not be violated.

###  3.5 Considerations on loss tolerance in QPV

Ideally, for QPV to become feasible, one would like to have a protocol that is
fully loss tolerant, secure against attackers being able to pre-share a
bounded amount of entanglement and to use quantum communication between them.
So far, there is no such protocol. Here we give a no-go result, based on a
simple observation. We show that no such protocol, fulfilling all three of the
above properties, can exist. However, not all is lost as in practice one may
be able to achieve good enough partial loss tolerance, for example by
increasing the quantum input dimension or the number of possible quantum
operations P can apply. For simplicity, consider the following quite general
two-verifier QPV protocol111111The result that follows can be
straightforwardly generalized to $m$ verifiers, for which a general attack
would be to teleport all quantum inputs to one fixed attacker, who then
performs the guessing attack. In that case, the probability that no
teleportation needs corrections is much lower, i.e. $1/d^{2(m-1)}$.:

  * •

Verifiers $\mathsf{V_{A}},\mathsf{V_{B}}$ send $d_{A},d_{B}$ dimensional
quantum inputs, respectively, to P. They also send classical information $x,y$
(of any size), respectively.

  * •

P computes a function $f(x,y)$ and, based on that result, applies a quantum
operation $\mathcal{Q}_{f(x,y)}$ to the inputs. This yields two outputs, one
intended for $\mathsf{V_{A}}$ and one for $\mathsf{V_{B}}$. These outputs are
forwarded to the corresponding verifier.

  * •

The verifiers check if what they received matches the specific honest protocol
and that the responses arrived in time.

We will denote this as $\text{QPV}(d_{A},d_{B},f)$ and the protocol is to be
repeated for $n$ rounds, either sequentially or in parallel. Now let
$k\coloneqq|\operatorname{Im}(f)|$ be the number of possible quantum
operations to be applied at P. It turns out that there always exists a perfect
attack consuming at most $O(n\log d)$ (qubit) EPR pairs, where
$d=\max\\{d_{A},d_{B}\\}$, as long as the loss is high enough. We make this
precise in the following statement.

######  Proposition 3.2.

Let $d=\max\\{d_{A},d_{B}\\}$ and $k=|\operatorname{Im}(f)|$. Any $n$-round
$\emph{QPV}(d_{A},d_{B},f)$ protocol can be attacked with $\tilde{O}(n)$ EPR
pairs if the fraction $\eta$ of rounds that is used for security analysis
fulfills $\eta\leq\frac{1}{kd^{2}}$.

###### Proof.

Without loss of generality, let attacker A receive classical input $x$. As
soon as A receives his quantum input, quantum teleportation [BBC+93] can be
used to teleport the state to B (consuming a $d=\max\\{d_{A},d_{B}\\}$
dimensional maximally entangled state121212Attackers do not know the dimension
of their local inputs a priori.), after which A sends to B which teleportation
corrections were to apply and the classical information $x$. With probability
$p_{00}=1/d^{2}$ there are no teleportation corrections to apply, in which
case B holds both input states locally and before the honest party P would
have received them. B can guess the value of $f(x,y)$ and immediately apply
the operation P was asked to apply, send the part (e.g. a subsystem or a
measurement result) that $\mathsf{V_{A}}$ is supposed to receive to A and keep
the part that $\mathsf{V_{B}}$ is supposed to receive. With probability $1/k$
attacker B guesses the value of $f(x,y)$ correctly. If the quantum state
picked up teleportation corrections in the first place or if it turns out that
B guessed $f(x,y)$ wrongly (of which both get to know as soon as they receive
the communication from the other attacker), attackers deny to answer and both
send the corresponding loss symbol ‘$\varnothing$’. If there were no
corrections to apply and B guessed $f(x,y)$ correctly, both send their
respective parts that the verifiers are supposed to receive to them. As they
are only required to answer $\eta\leq\frac{1}{kd^{2}}$ of all rounds, they can
simply choose those perfect rounds without teleportation corrections and a
correct guess for $f(x,y)$. Applying this strategy in each round costs them
$n\log d$ (qubit) EPR pairs. ∎

The statement shines light on another facet of loss tolerance – the attacker’s
ability to post-select on a “correct” guess after communication. They can
always do that, if they pre-share entanglement, by simply guessing the
teleportation corrections. In protocols with quantum input from one side and
classical information determining the action of P, like [KMS11, CL15, Unr14,
JKPPG21, BCS21], attackers can, even without pre-shared entanglement, do this
post-selection simply by first guessing $f(x,y)$, then applying the operation
$\mathcal{Q}_{f(x,y)}$ on the quantum input and communicating $x,y$ to each
other so that both attackers know if the initial guess was correct or not.
This is captured in the above bound, identifying all-classical input from one
side with $d=1$. In that sense, QPV protocols containing classical input
cannot be fully loss-tolerant. It is now also clearer why the protocol in
[LXS+16] and our QPV${}_{\textsf{SWAP}}$ [ABSVL22] are fully loss-tolerant if
attackers do not pre-share any entanglement. Without shared entanglement, the
attackers simply have no way of ever knowing if their guess was correct,
because there is no information about it leaving the verifiers.

We conclude that there does not exist a fully loss tolerant QPV protocol of
the above type (in particular, if a linear amount of entanglement is pre-
shared). The best we can achieve in all generality against entangled attackers
is partial loss tolerance. By increasing $k$ and/or $d$ such that
$kd^{2}>1/\eta$, however, partial loss tolerance good enough for all practical
purposes could be achieved. We will therefore need to bound both the pre-
shared entanglement of the attackers and the loss for a practical QPV
protocol.

##  4 Conclusion

We gave an explicit example of the first QPV protocol in which there is an
advantage for attackers who share no entanglement to use quantum communication
over classical communication. The protocol depends on determining whether two
states were either both symmetric or both antisymmetric. The probability of
success under LOCC operations was analytically shown to be equal to 17/18,
while attackers with access to quantum communication could attack this
protocol perfectly with a single round of simultaneous quantum communication.
This suggests that the role of quantum communication can be more important
than previously thought.

Diving into the idea that there can be an advantage to using quantum
communication over classical communication we also showed that this separation
between quantum communication and classical communication was somewhat
constructed. The existence of a quantum communication attack on a protocol
that is safe against attackers restricted to classical communication implies
the existence of a similar protocol that is safe against quantum
communication. In order to prove this we showed that for every quantum
communication attack, two new QPV protocols arise. By repeating this argument
whenever there was a quantum communication attack, we used the theorem of
emergent classicality of channels from [QR20] to show that the quantum inputs
become approximately classical, which in turn implies the existence of a
classical communication attack on the original protocol which violated the
assumption of the original being secure against classical communication. Thus,
ultimately showing that somewhere in the recursion there must have been a
protocol that was secure against attackers allowed to use a single round of
simultaneous quantum communication.

Setting out to find an explicit example of a protocol that is safe against
quantum communication, we prove that the task of Bell state discrimination
cannot have a higher success probability than $3/4$ when two attackers are
restricted to local operations and a single round of quantum communication.
This is higher than the optimal success probability of $1/2$ for attackers
restricted to classical communication. We do suspect the quantum communication
bound to be lower than $3/4$, but have been unable to make the bound tighter
just yet. Nonetheless, this is the first example of a protocol that is fully
loss-tolerant against classical communication and stays secure against
attackers using quantum communication.

The previous statement immediately brings up the question whether the protocol
is also safe against attackers allowed to use quantum communication, and
allowed to say loss. We answer this question in the affirmative and prove that
there cannot be a strategy that perfectly distinguishes all Bell states.
However, we only find a strict inequality, i.e. that
$p_{\text{succ}}^{\text{qc}}(\eta)<1$ for any transmission rate
$\eta\in(0,1]$. An interesting follow-up question is whether we can make this
bound into a finite gap, just as with the case where the attackers were not
allowed to say loss but could use quantum communication. Nonetheless, this is
the first example of a QPV protocol that remains fully loss tolerant and
secure even in the quantum communication setting. This is of interest since it
is the most general setting in the case where we do not allow attackers to
pre-share entanglement.

Extending on the idea of incorporating loss in different settings for
attackers we note that in order for QPV to become feasible, not only do we
want our protocols to be loss-tolerant against quantum communication, but we
also want our protocols to be loss-tolerant against some amount of pre-shared
entanglement among the attackers. However, we show that any QPV protocol can
be attacked by only a linear amount of entanglement in this setting, given
that the loss is high enough. This is based on the simple observation that in
such a scenario attackers can post-select on those rounds in which the
attempted quantum teleportation did not incur teleportation corrections.

In conclusion, in this paper we investigated the advantage of a single round
of simultaneous quantum communication over classical communication in QPV
attacks. We find that this advantage can be strictly better than classical
communication, but we also find that in some cases it is still strictly worse
than the best non-local operations, which proves security for those cases.

##### Acknowledgments

We would like to thank Freek Witteveen, Wolfgang Löffler and Kirsten
Kanneworff for many useful discussions. RA and HB were supported by the Dutch
Research Council (NWO/OCW), as part of the Quantum Software Consortium
programme (project number 024.003.037). PVL and HB were supported by the Dutch
Research Council (NWO/OCW), as part of the NWO Gravitation Programme Networks
(project number 024.002.003).

## References

  * [ABSVL22] Rene Allerstorfer, Harry Buhrman, Florian Speelman, and Philip Verduyn Lunel.  Towards practical and error-robust quantum position verification.  Manuscript in preparation, August 2022.
  * [BBC+93] Charles H. Bennett, Gilles Brassard, Claude Crépeau, Richard Jozsa, Asher Peres, and William K. Wootters.  Teleporting an unknown quantum state via dual classical and einstein-podolsky-rosen channels.  Phys. Rev. Lett., 70:1895–1899, Mar 1993.
  * [BCF+11] Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, and Christian Schaffner.  Position-Based Quantum Cryptography: Impossibility and Constructions.  In Phillip Rogaway, editor, Advances in Cryptology – CRYPTO 2011, pages 429–446, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg.
  * [BCS21] Andreas Bluhm, Matthias Christandl, and Florian Speelman.  Position-based cryptography: Single-qubit protocol secure against multi-qubit attacks.  arXiv preprint arXiv:2104.06301, 2021.
  * [BCWdW01] Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf.  Quantum fingerprinting.  Physical Review Letters, 87(16):167902, September 2001.  arXiv: quant-ph/0102001.
  * [BFSS13] Harry Buhrman, Serge Fehr, Christian Schaffner, and Florian Speelman.  The garden-hose model.  In Proceedings of the 4th conference on Innovations in Theoretical Computer Science, pages 145–158, 2013.
  * [BK11] Salman Beigi and Robert Koenig.  Simplified instantaneous non-local quantum computation with applications to position-based cryptography.  New Journal of Physics, 13(9):093036, September 2011.  arXiv: 1101.1065.
  * [BKMS06] Raymond G. Beausoleil, Adrian Kent, William J. Munro, and Timothy P. Spiller.  Tagging systems, US patent 7075438, 2006.
  * [BRSdW11] Harry Buhrman, Oded Regev, Giannicola Scarpa, and Ronald de Wolf.  Near-Optimal and Explicit Bell Inequality Violations.  In 2011 IEEE 26th Annual Conference on Computational Complexity, pages 157–166, San Jose, CA, USA, June 2011. IEEE.
  * [CGMO09] Nishanth Chandran, Vipul Goyal, Ryan Moriarty, and Rafail Ostrovsky.  Position Based Cryptography.  In Shai Halevi, editor, Advances in Cryptology - CRYPTO 2009, Lecture Notes in Computer Science, pages 391–407, Berlin, Heidelberg, 2009. Springer.
  * [CL15] Kaushik Chakraborty and Anthony Leverrier.  Practical Position-Based Quantum Cryptography.  Physical Review A, 92(5):052304, November 2015.  arXiv: 1507.00626.
  * [CW04] Matthias Christandl and Andreas Winter.  “squashed entanglement”: an additive entanglement measure.  Journal of mathematical physics, 45(3):829–840, 2004.
  * [Dol19] Kfir Dolev.  Constraining the doability of relativistic quantum tasks.  arXiv preprint arXiv:1909.05403, 2019.
  * [DW05] Igor Devetak and Andreas Winter.  Distillation of secret key and entanglement from quantum states.  Proceedings of the Royal Society A: Mathematical, Physical and engineering sciences, 461(2053):207–235, 2005.
  * [GC20] Alvin Gonzales and Eric Chitambar.  Bounds on Instantaneous Nonlocal Quantum Computation.  IEEE Transactions on Information Theory, 66(5):2951–2963, May 2020\.  arXiv: 1810.00994.
  * [GLW13] Fei Gao, Bin Liu, and Qiao-Yan Wen.  Enhanced no-go theorem for quantum position verification.  arXiv preprint arXiv:1305.4254, 2013.
  * [HHH99] Michał Horodecki, Paweł Horodecki, and Ryszard Horodecki.  General teleportation channel, singlet fraction, and quasidistillation.  Phys. Rev. A, 60:1888–1898, Sep 1999.
  * [JKPPG21] Marius Junge, Aleksander M Kubicki, Carlos Palazuelos, and David Pérez-García.  Geometry of banach spaces: a new route towards position based cryptography.  arXiv preprint arXiv:2103.16357, 2021.
  * [KMS11] Adrian Kent, William J. Munro, and Timothy P. Spiller.  Quantum Tagging: Authenticating Location via Quantum Information and Relativistic Signalling Constraints.  Physical Review A, 84(1):012326, July 2011.  arXiv: 1008.2147.
  * [LL11] Hoi Kwan Lau and Hoi Kwong Lo.  Insecurity of position-based quantum cryptography protocols against entanglement attacks.  Physical Review A, 83(1):012322, January 2011.  arXiv: 1009.2256.
  * [LXS+16] Charles Ci Wen Lim, Feihu Xu, George Siopsis, Eric Chitambar, Philip G. Evans, and Bing Qi.  Loss-tolerant quantum secure positioning with weak laser sources.  Physical Review A, 94(3):032315, September 2016.  arXiv: 1607.08193.
  * [Mal10a] Robert A. Malaney.  Location-dependent communications using quantum entanglement.  Phys. Rev. A, 81:042319, Apr 2010.
  * [Mal10b] Robert A. Malaney.  Quantum location verification in noisy channels.  In 2010 IEEE Global Telecommunications Conference GLOBECOM 2010, pages 1–6, 2010.
  * [OCCG20] Andrea Olivo, Ulysse Chabaud, André Chailloux, and Frédéric Grosshans.  Breaking simple quantum position verification protocols with little entanglement.  arXiv:2007.15808 [quant-ph], July 2020.  arXiv: 2007.15808.
  * [QLL+15] Bing Qi, Hoi-Kwong Lo, Charles Ci Wen Lim, George Siopsis, Eric A. Chitambar, Raphael Pooser, Philip G. Evans, and Warren Grice.  Free-space reconfigurable quantum key distribution network.  2015 IEEE International Conference on Space Optical Systems and Applications (ICSOS), pages 1–6, October 2015.  arXiv: 1510.04891.
  * [QR20] Xiao-Liang Qi and Daniel Ranard.  Emergent classicality in general multipartite states and channels.  arXiv preprint arXiv:2001.01507, 2020.
  * [QS15] Bing Qi and George Siopsis.  Loss-tolerant position-based quantum cryptography.  Physical Review A, 91(4):042337, April 2015.  arXiv: 1502.02020.
  * [RG15] Jérémy Ribeiro and Frédéric Grosshans.  A Tight Lower Bound for the BB84-states Quantum-Position-Verification Protocol.  arXiv:1504.07171 [quant-ph], June 2015.  arXiv: 1504.07171.
  * [Spe16] Florian Speelman.  Instantaneous Non-Local Computation of Low T-Depth Quantum Circuits.  In Anne Broadbent, editor, 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016), volume 61 of Leibniz International Proceedings in Informatics (LIPIcs), pages 9:1–9:24, Dagstuhl, Germany, 2016. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * [TFKW13] Marco Tomamichel, Serge Fehr, Jędrzej Kaniewski, and Stephanie Wehner.  A Monogamy-of-Entanglement Game With Applications to Device-Independent Quantum Cryptography.  New Journal of Physics, 15(10):103002, October 2013.  arXiv: 1210.4359.
  * [Unr14] Dominique Unruh.  Quantum Position Verification in the Random Oracle Model.  In Juan A. Garay and Rosario Gennaro, editors, Advances in Cryptology – CRYPTO 2014, pages 1–18, Berlin, Heidelberg, 2014. Springer Berlin Heidelberg.

##  Appendix A Optimal PPT Measurements for QPV${}_{\text{Sym/Antisym}}$

In this section we will solve the SDP program that optimizes the probability
of success for two adversaries restricted to LOCC operations of discriminating
a random symmetric state from the antisymmetric state. The SDP formulation of
this protocol is as follows:

Primal Program maximize:
$\displaystyle\frac{1}{2}\operatorname{Tr}[\Pi_{0}\rho_{0}+\Pi_{1}\rho_{1}]$
subject to: $\displaystyle\Pi_{0}+\Pi_{1}=\mathbbm{1}_{2^{2}}$
$\displaystyle\Pi_{k}\in\text{PPT}(\mathsf{A}:\mathsf{B}),\ \ \ k\in\\{0,1\\}$

Dual Program minimize: $\displaystyle\operatorname{Tr}[Y]$ subject to:
$\displaystyle Y-Q^{T_{\mathsf{B}}}_{i}-\rho_{i}/2\succeq 0,\ \ \
i\in\\{0,1\\}$ $\displaystyle Y\in\text{Herm}(\mathsf{A}\otimes\mathsf{B})$
$\displaystyle Q_{i}\in\text{Pos}(\mathsf{A},\mathsf{B}),\ \ \ i\in\\{0,1\\}.$

Where we write $\rho_{0}$ for $\rho_{\text{sym}}$ and $\rho_{1}$ for
$\rho_{\text{antisym}}$ whose respective density matrices are:

$\displaystyle\rho_{0}=\frac{1}{6}\left(\begin{matrix}2&0&0&0\\\ 0&1&1&0\\\
0&1&1&0\\\ 0&0&0&2\end{matrix}\right),$
$\displaystyle\rho_{1}=\frac{1}{2}\left(\begin{matrix}0&0&0&0\\\ 0&1&-1&0\\\
0&-1&1&0\\\ 0&0&0&0\end{matrix}\right).$

A feasible solution for the primal program, is to measure both states in the
computational basis and answering the XOR of the measurement outcomes, so
$\Pi_{0}=\ket{00}\bra{00}+\ket{11}\bra{11},\Pi_{1}=\ket{01}\bra{01}+\ket{10}\bra{10}$.
This strategy has success probability
$\frac{1}{2}\operatorname{Tr}[\Pi_{0}\rho_{0}+\Pi_{1}\rho_{1}]=5/6$. A
feasible solution to the the corresponding dual is

$\displaystyle Y=\left(\begin{matrix}\frac{1}{6}&0&0&0\\\
0&\frac{1}{4}&-\frac{1}{12}&0\\\ 0&-\frac{1}{12}&\frac{1}{4}&0\\\
0&0&0&\frac{1}{6}\end{matrix}\right),$ $\displaystyle Q_{0}=0\succeq 0,$
$\displaystyle Q_{1}=\frac{1}{6}\left(\begin{matrix}1&0&0&1\\\ 0&0&0&0\\\
0&0&0&0\\\
1&0&0&1\end{matrix}\right)=\frac{1}{3}\ket{\Phi^{+}}\bra{\Phi^{+}}\succeq 0.$

Where $\operatorname{Tr}[Y]=5/6$ is a lower bound of the success probability
of the protocol optimized over all PPT measurements. Thus we see that the
highest probability of success for adversaries restricted to LOCC operations
is $5/6$.

Now for the protocol where we double the input rounds, but restrict the inputs
to be either both symmetric or antisymmetric states we will show that there is
no perfect LOCC attack. The corresponding SDP that optimizes over all PPT
strategies looks as follows:

Primal Program maximize:
$\displaystyle\frac{1}{2}\operatorname{Tr}[\Pi_{0}(\rho_{0}\otimes\rho_{0})+\Pi_{1}(\rho_{1}\otimes\rho_{1})]$
subject to: $\displaystyle\Pi_{0}+\Pi_{1}=\mathbbm{1}_{2^{4}}$
$\displaystyle\Pi_{k}\in\text{PPT}(\mathsf{A}:\mathsf{B}),\ \ \ k\in\\{0,1\\}$

Dual Program minimize: $\displaystyle\operatorname{Tr}[Y]$ subject to:
$\displaystyle Y-Q^{T_{\mathsf{B}}}_{i}-(\rho_{i}\otimes\rho_{i})/2\succeq 0,\
\ \ i\in\\{0,1\\}$ $\displaystyle
Y\in\text{Herm}(\mathsf{A}\otimes\mathsf{B})$ $\displaystyle
Q_{i}\in\text{Pos}(\mathsf{A},\mathsf{B}),\ \ \ i\in\\{0,1\\}.$

We will show that the following is a feasible solution to the dual

$\displaystyle
Y=\frac{1}{18}\left(9(\rho_{0}\otimes\rho_{0})+8(\rho_{1}\otimes\rho_{1})\right),$
$\displaystyle Q_{0}=0\succeq 0,$ $\displaystyle
Q_{1}=\frac{1}{18}\left((3\rho_{0}^{T_{\mathsf{B}}}\otimes
3\rho_{0}^{T_{\mathsf{B}}})-(\rho_{1}^{T_{\mathsf{B}}}\otimes\rho_{1}^{T_{\mathsf{B}}})\right).$

Note that in contrast to the optimizations for QPV${}^{n}_{\text{SWAP}}$
protocols the matrix $Y$ is not equal to the identity matrix with some factor,
but nonetheless it is Hermitian. Secondly the eigenvectors of
$3\rho_{0}^{T_{\mathsf{B}}}$ and $\rho_{1}^{T_{\mathsf{B}}}$ are both the 4
Bell states with eigenvalues $\\{3/2,1/2,1/2,1/2\\}$ and
$\\{-1/2,1/2,1/2,1/2\\}$ respectively. We see for any of the 16 possible
eigenvectors of $Q_{1}$ that the corresponding eigenvalues will be
$0,\frac{1}{9}$ or $\frac{1}{18}$. We conclude that $Q_{1}\succeq 0$ since all
its eigenvalues are non-negative and it is Hermitian.

For $Q_{0}$ the first constraint in the dual program becomes:

$\displaystyle Y-Q^{T_{\mathsf{B}}}_{0}-\frac{(\rho_{0}\otimes\rho_{0})}{2}$
$\displaystyle=\frac{1}{18}\left(9(\rho_{0}\otimes\rho_{0})+8(\rho_{1}\otimes\rho_{1})\right)-\frac{(\rho_{0}\otimes\rho_{0})}{2}$
$\displaystyle=\frac{4}{9}(\rho_{1}\otimes\rho_{1})\succeq 0.$

And for $Q_{1}$ we get:

$\displaystyle Y-Q^{T_{\mathsf{B}}}_{1}-\frac{(\rho_{1}\otimes\rho_{1})}{2}$
$\displaystyle=\frac{1}{18}\left(9(\rho_{0}\otimes\rho_{0})+8(\rho_{1}\otimes\rho_{1})\right)-\frac{1}{18}\left(9(\rho_{0}\otimes\rho_{0})-(\rho_{1}\otimes\rho_{1})\right)-\frac{(\rho_{1}\otimes\rho_{1})}{2}$
$\displaystyle=0\succeq 0.$

Thus we have shown that all conditions in the dual program are met, and we get
an upper bound on the success probability over all PPT measurements of

$\displaystyle\operatorname{Tr}[Y]=\operatorname{Tr}\left[\frac{1}{18}\left(9(\rho_{0}\otimes\rho_{0})+8(\rho_{1}\otimes\rho_{1})\right)\right]=\frac{17}{18}.$

There is an LOCC strategy that attains this upper bound, namely of applying
the single rounds strategy twice, where we only answer asymmetric if both
pairs have unequal measurement. This strategy is correct on all input states
except when as an input twice the $\ket{\Psi^{+}}$ input was send. This
happens with probability 1/18. Thus the best attack for adversaries restricted
to LOCC operations has success probability $\frac{17}{18}$, in contrast to
adversaries who may use quantum communication for whom there is a perfect
attack with success probability $1$ by simply swapping the second register and
applying the SWAP test locally.