# New Protocols and Ideas for Practical 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

Loss of inputs can be detrimental to the security of quantum position
verification (QPV) protocols, as it may allow attackers to not answer on all
played rounds, but only on those they perform well on. In this work, we study
loss-tolerant QPV protocols. We propose a new fully loss-tolerant protocol,
based on the SWAP test, with several desirable properties. The task of the
protocol, which can be implemented using only a single beam splitter and two
detectors, is to estimate the overlap between two input states. By formulating
possible attacks as a semi-definite program (SDP), we prove full loss
tolerance against unentangled attackers restricted to local operations and
classical communication (LOCC), and that the attack probability decays
exponentially under parallel repetition of rounds. Furthermore, the role of
loss and quantum communication attacks in QPV is investigated more generally.
We construct the first known example of a QPV protocol that is provably secure
against unentangled attackers restricted to LOCC, but can be perfectly
attacked by local operations and a single round of simultaneous quantum
communication. However, it is also shown that any protocol secure against
classical communication can be transformed into a protocol secure against
quantum communication. 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_{0}}$ and $\mathsf{V_{1}}$, 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.
Notationally, we’ll use $\mathsf{A}$ (or Alice) for the attacker located
between $\mathsf{V_{0}}$ and the location of $\mathsf{P}$, and $\mathsf{B}$
(or Bob) for the attacker location between the location of $\mathsf{P}$ and
$\mathsf{V_{1}}$.

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 Kent, Munro, and Spiller [KMS11], followed by various
proposals and ad-hoc attacks [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.)

A natural question is therefore whether some QPV protocols can be proven
secure against attackers that share a limited amount of entanglement.

Since it’s so hard to generate entanglement, it is already interesting to
study whether protocols are secure against adversaries that are very limited
in their access to pre-shared entangled states. For instance, the
QPV${}_{\text{BB84}}$ protocol [KMS11], inspired by the BB84 quantum key-
distribution protocol, involves only a single qubit sent by $\mathsf{V_{0}}$,
in the state $\ket{0}$, $\ket{1}$, $\ket{+}$, or $\ket{-}$, and the choice of
basis sent by $\mathsf{V_{1}}$. Even though this protocol is insecure against
attackers sharing a single EPR pair [LL11], security can be proven against
unentangled attackers [BCF+11], so that $\Theta({n})$ entanglement is required
to break the $n$-fold parallel repetition [TFKW13, RG15]. At the current
technological level, such protocols are very interesting to analyze, and would
already give a super-classical level of security if implemented in practice.

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, Spe16a, OCCG20].

Unfortunately, implementing any of the mentioned protocols would run into
large obstacles: the quantum information involved would have to be sent at the
speed of light, i.e., using photons, and in realistic experimental setups a
large fraction of photons will be lost. Compensating for this in the most
natural way, by ignoring rounds whenever the prover claims that a photon was
lost in transmission, lets attackers break all protocols. In our contribution,
we study the role of loss in QPV, present a new loss-tolerant protocol,
together with several results that increase our understanding of loss-tolerant
protocols for QPV.

#### Loss-tolerance in QPV.

Throughout, we will use $\eta$ as rate of transmission, i.e., the probability
that an quantum message arrives – in realistic protocols. We will distinguish
two types of loss tolerance that we might require schemes to satisfy.

The first, _partial loss tolerance_ , refers to a protocol which is secure for
some values $\eta\geq\eta_{\mathrm{threshold}}$, meaning that the honest
parties have a maximum level of allowed loss. This level of loss might be
inherent to a certain scheme, or a family of schemes could be designed with
$\eta_{\mathrm{threshold}}$ as a parameter. Security is only guaranteed in a
situation where a high enough fraction of the rounds are played. If
significantly more photons than this threshold are lost, then the protocol
will have to abort. Examples of partial loss tolerant schemes are extensions
of QPV${}_{\text{BB84}}$ to more bases [QS15, Spe16b], that are secure against
unentangled attackers in an environment with some loss.555This notion will be
satisfied to a small level even by schemes that are not designed to be loss
tolerant, simply by having some error-robustness. The basic
QPV${}_{\text{BB84}}$ scheme can directly be seen to be partially loss
tolerant for loss below $\frac{1}{2}-\frac{1}{2\sqrt{2}}$, and the simplest
attack that uses loss only works when the loss is above $\frac{1}{2}$.

_Full loss tolerance_ is achieved when a protocol is secure, irrespective of
the loss rate. In particular, the protocol stays secure when conditioning on
those rounds where the prover replied, fully ignoring rounds where a photon is
lost. The protocol by Lim, Xu, Siopsis, Chitambar, Evans, and Qi [QLL+15,
LXS+16], the first fully loss-tolerant protocol, consists of $\mathsf{V_{0}}$
and $\mathsf{V_{1}}$ both sending a qubit, and having the prover perform a
Bell measurement on both, broadcasting the measurement outcome. This protocol
is secure against unentangled attackers, no matter the loss rate.

In the current work, we advance the study of loss-tolerant QPV with the
following results:

  * •

We present a new fully-loss tolerant protocol: QPV${}_{\textsf{SWAP}}$, which
is based on the SWAP test [BCWdW01]. The new protocol compares favorably to
Lim et al.’s protocol [LXS+16] in terms of ease of implementation using linear
optics, by requiring only a single beam splitter – the Hong-Ou-Mandel effect
can be viewed as equivalent to the SWAP test [GECP13].

  * •

We prove fully loss tolerant security by formulating possible attacks as a
semi-definite program (SDP), and show that the protocol is secure against
unentangled attackers that are allowed a single round of simultaneous
(classical) communication.

Additionally, we show that the attack probability decays exponentially under
_parallel repetition_ : when attackers respond to a size $k$ subset out of $n$
parallel rounds, pretending photon loss on the other inputs, their probability
of a successful attack still decays exponentially in $k$. Such a parallel
repetition is not known for the protocol of [LXS+16], and this is the first
parallel repetition theorem for fully loss tolerant QPV.

We obtain this result by constructing an SDP formulation of the $n$-fold
parallel repetition of the problem, constructing a dual of this SDP for
variable $n$, and then finding a point in the generalized dual problem.

  * •

We also show that 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 ‘no photon’ if the guess is incorrect.

Additionally, 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] and the security proof of
QPV${}_{\textsf{SWAP}}$ in the current work, 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.666For 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?

In the current work, we answer this 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_{0}}$, $\mathsf{V_{1}}$, without having to modify the output
predicate. Our proof for this statement involves a recursive argument, where
we view the 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.

###  1.1 Structure of the paper

In Section 3 we present the protocol QPV${}_{\textsf{SWAP}}$, with primary
security analysis in Section 3.1, extension of the security analysis to the
loss-tolerant setting in Section 3.2, and an upper bound to the entanglement
required for an attack in Section 3.3. Section 4 is concerned with results
applicable to QPV in general. In subsections 4.1 and 4.2 our results relating
to quantum-communication attacks on QPV are presented, subsection 4.3 is
concerned with results about loss tolerance.

##  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. Cumulative distribution functions are written as $F_{X}$, where $X$
is either a random variable or explicitly the distribution. 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” (LOBC) 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 The SWAP test

The SWAP test was first introduced in [BCWdW01] for quantum fingerprinting as
a useful tool to determine if two unknown states are identical or not. The
quantum circuit of it is depicted in Figure 1.

Figure 1: The SWAP test, taken from [BCWdW01]. $H$ denotes the Hadamard gate.

The state to be measured in the computational basis is

$\displaystyle(H\otimes\mathbbm{1})\text{c-SWAP}(H\otimes\mathbbm{1})\ket{0}\ket{\phi}\ket{\psi}=\frac{1}{2}\ket{0}(\ket{\phi}\ket{\psi}+\ket{\psi}\ket{\phi})+\frac{1}{2}\ket{1}(\ket{\phi}\ket{\psi}-\ket{\psi}\ket{\phi}).$
(2.1)

Therefore we have the measurement statistics

$\displaystyle\mathbb{P}(0)=\frac{1+\lvert\braket{\psi}{\phi}\rvert^{2}}{2}\qquad\text{and}\qquad\mathbb{P}(1)=\frac{1-\lvert\braket{\psi}{\phi}\rvert^{2}}{2}.$
(2.2)

The output distribution only depends on the overlap
$\lvert\braket{\psi}{\phi}\rvert$ between the input states. One notable
special case is that for $\ket{\phi}=\ket{\psi}$ the SWAP operation has no
effect and we get $\mathbb{P}(0)=1$. Another advantage of the SWAP test is
that it is easily implemented experimentally with a single beam splitter and
two photon detectors [GECP13]. Its flexibility concerning input states and the
simplicity of its experimental realization make it a good candidate for QPV.

##  3 The QPV${}_{\textsf{SWAP}}$ protocol

We define the protocol QPV${}_{\textsf{SWAP}}(\beta_{1},\dots,\beta_{k})$,
depicted in the space-time diagram in Figure 2, as follows.

  1. 1.

By means of local and shared randomness or a secure private channel verifiers
$\mathsf{V_{0}}$ and $\mathsf{V_{1}}$ uniformly draw a random overlap
$\beta\in\\{\beta_{1},\dots,\beta_{k}\\}$ and agree on two uniformly random
states $\ket{\psi},\ket{\phi}$ on the Bloch sphere such that
$\lvert\braket{\psi}{\phi}\rvert=\beta$. Then $\mathsf{V_{0}}$ prepares the
state $\ket{\psi}$ and $\mathsf{V_{1}}$ prepares $\ket{\phi}$. Each verifier
sends their state to $\mathsf{P}$ such that they arrive there simultaneously.

  2. 2.

The honest party $\mathsf{P}$ applies the SWAP test on the two quantum inputs
as soon as they arrive at $\mathsf{P}$. This yields an output bit
$z\in\\{0,1,\varnothing\\}$, indicating $\mathsf{P}$’s measurement result or
possibly a “loss” event. In particular, $\mathbb{P}(z=0\mid\beta,\text{not
loss})=(1+\beta^{2})/2$ and $\mathbb{P}(z=0\mid\beta,\text{not
loss})=(1-\beta^{2})/2$. Then $\mathsf{P}$ immediately sends $z$ to both
verifiers $\mathsf{V_{0}}$ and $\mathsf{V_{1}}$.

  3. 3.

The verifiers closely monitor if they receive an answer in time and compare
what they received. If they got different bits, or if at least one of their
bits arrived too early/late, they abort and reject. Otherwise both
$\mathsf{V}_{k}$ add $z$ to their (ordered) lists of answers $L_{\beta}$.

  4. 4.

After having completed $R_{\beta}\geq R$ rounds with a conclusive answer
$z\in\\{0,1\\}$, sequentially or in parallel for each $\beta$, they abort,
check if the rate of $\varnothing$ symbols is close enough888Say a rate
$1-\eta$ is expected from P. The verifiers can apply an analogous statistical
test around $1-\eta$ as described for the conclusive answers to check for any
suspicious actions. to what is expected from P, discard any rounds with answer
$\varnothing$ and proceed to the statistical analysis on
$C_{\beta}=L_{\beta}-\\{\varnothing\\}$ for each $\beta$. They test if the
sample $\hat{p}_{\beta}=\\#\\{z\in C_{\beta}:z=0\\}/R_{\beta}$ on conclusive
answers is contained in the $(1-\alpha)$-quantile around the expected
$p_{\beta}=(1+\beta^{2})/2$.

  5. 5.

Only if they have received the same answer in time in every single round and
if the statistical test was passed on all $L_{\beta}$, they accept. Otherwise,
they reject.

$t$$x$$a$$\ket{\psi}$$\mathsf{V_{0}}$$b$$\ket{\phi}$$\mathsf{V_{1}}$$\mathsf{A}$$\mathsf{P}$$\mathsf{B}$
Figure 2: Space-time diagram of the QPV${}_{\textsf{SWAP}}$ protocol. We
assume all information, quantum (—) and classical (- - -), travels at the
speed of light. For graphical simplicity we have put $\mathsf{P}$ exactly in
the middle of $\mathsf{V_{0}}$ and $\mathsf{V_{1}}$ (which is not necessary
for the purposes of QPV). The attackers, not being at position $\mathsf{P}$,
would like to convince the verifiers that they are at $\mathsf{P}$. Note that
to have any chance of winning, attackers need to produce $a=b$.

Note that in essence the task in this protocol is to estimate the overlap
$\beta$ of the input states $\ket{\psi}$ and $\ket{\phi}$. This is independent
of the dimensionality/nature of the input states, making the protocol very
flexible. To attack this protocol, it is evident that there need to be at
least two attackers due to the timing constraint. A coalition of attackers has
to position at least one party $\mathsf{A}$ between $\mathsf{V_{0}}$ and
$\mathsf{P}$ and one party $\mathsf{B}$ between $\mathsf{P}$ and
$\mathsf{V_{1}}$. Since the SWAP test is a joint operation on two quantum
states, spatially separated attackers cannot apply the SWAP test, unless they
have access to pre-shared entanglement, as we will show. Since any QPV
protocol can be perfectly attacked if the attackers have access to enough pre-
shared entanglement [BCF+11], we assume that the attackers have no pre-shared
entanglement and we also restrict them to LOCC channels only. We further
assume that the attackers act non-adaptively, i.e., they do not base their
strategy in a given round on results from previous rounds. This does not seem
to be too restrictive, as we could simply replace $R$ in the above algorithm
by $2R$ rounds and let the verifiers choose a uniformly random subset of $R$
rounds on which they perform security analysis. That way any given round has
probability $1/2$ of being “relevant”. Together with the independent state
preparation in each round, this seems to make adaptive strategies not more
useful than non-adaptive ones. To assess the security of this protocol, we
consider the following. As the individual rounds are independent, the subsets
$L_{\beta}$ of answers given input $\rho_{\beta}$ will be a sample of a
binomial distribution with parameters $R_{\beta}$ and some $q_{\beta}$. The
verifiers can then test if what they received matches closely enough with what
they expect from an honest party. We define the statistical test to be done by
the verifiers as follows:

  1. 1.

For each overlap $\beta$, they calculate the $(1-\alpha)$-quantile999In order
to capture P with high probability, $\alpha$ can be set to a small number,
e.g. $10^{-6}$. around the ideal $p_{\beta}=(1+\beta^{2})/2$, which gives a
lower and an upper bound

$\displaystyle\begin{split}L_{\alpha,\beta}&\coloneqq
z_{\frac{\alpha}{2}}(\beta,R_{\beta})/R_{\beta}=F^{-1}_{\text{Bin}(R_{\beta},p_{\beta})}\left(\frac{\alpha}{2}\right)/R_{\beta}\\\
U_{\alpha,\beta}&\coloneqq
z_{1-\frac{\alpha}{2}}(\beta,R_{\beta})/R_{\beta}=F^{-1}_{\text{Bin}(R_{\beta},p_{\beta})}\left(1-\frac{\alpha}{2}\right)/R_{\beta},\end{split}$
(3.1)

with $F^{-1}$ being the inverse cumulative distribution function. This defines
an acceptance interval

$\displaystyle\mathsf{acc}_{\beta}(\alpha,R_{\beta})\coloneqq[L_{\alpha,\beta},U_{\alpha,\beta}].$
(3.2)

  2. 2.

For each overlap $\beta$, they check if the sample
$\hat{p}_{\beta}\in\mathsf{acc}(\alpha,R_{\beta})$. If this is the case for
all $\beta$, they accept. Otherwise, they reject.

By definition, the honest party will return a sample
$\hat{p}^{\mathsf{P}}_{\beta}\in\mathsf{acc}_{\beta}(\alpha,R_{\beta})$ with
probability $1-\alpha$ and thus the test will accept P with high probability
$(1-\alpha)^{k}=1-O(k\alpha)$. To optimize the overlap between their
distribution and the acceptance regions, the attackers will attempt to respond
as close to each $p_{\beta}$ as possible, with a binomial parameter of
$p^{\mathsf{AB}}_{\beta}=p_{\beta}-\Delta_{\beta}$, defining a vector of
differences

$\displaystyle\Delta=\begin{pmatrix}\Delta_{\beta_{1}}\\\ \vdots\\\
\Delta_{\beta_{k}}\end{pmatrix}.$ (3.3)

If rounds are run in parallel, attackers could also decide to just respond a
deterministic list with some fraction $p^{\mathsf{AB}}$ of “0” answers. They
could perfectly break the protocol if
$p^{\mathsf{AB}}\in\bigcap_{\beta}\mathsf{acc}_{\beta}(\alpha,R_{\beta})$.
This, however, we can always prevent by choosing the $R_{\beta}$’s large
enough so that the acceptance regions for different overlaps get disjoint. For
attackers responding binomially we need to evaluate

$\displaystyle\mathbb{P}(\mathsf{acc}|\mathsf{attack})\coloneqq\mathbb{P}\left(\hat{p}^{\mathsf{AB}}_{\beta}\in\mathsf{acc}_{\beta}(\alpha,R_{\beta})\quad\forall\beta\right)=\prod_{\beta}\mathbb{P}\left(\hat{p}^{\mathsf{AB}}_{\beta}\in\mathsf{acc}_{\beta}(\alpha,R_{\beta})\right)\eqqcolon\prod_{\beta}\mathbb{P}(\mathsf{acc}_{\beta}|\mathsf{attack}).$
(3.4)

Now there are several cases to consider:

  1. (1)

$\mathbf{\lVert\Delta\rVert_{1}=0.}$ Then $\Delta_{\beta}=0$ for all $\beta$
and the attackers respond with the identical distribution as P, therefore
$\mathbb{P}(\mathsf{acc}|\mathsf{attack})=(1-\alpha)^{k}=1-O(k\alpha)$.

  2. (2)

$\mathbf{p_{\boldsymbol{\beta}}\neq 1\textbf{ and
}p^{\mathsf{AB}}_{\boldsymbol{\beta}}=1}.$ Then
$\mathbb{P}(\mathsf{acc}|\mathsf{attack})=0$ as the $(1-\alpha)$-quantile
around $p_{\beta}$ will exclude the value 1 (for sufficiently large
$R_{\beta}$).

  3. (3)

$\mathbf{p_{\boldsymbol{\beta}}=1\textbf{ and
}p^{\mathsf{AB}}_{\boldsymbol{\beta}}\neq 1}.$ Then
$\mathbb{P}(\mathsf{acc}_{\beta}|\mathsf{attack})=\left(p^{\mathsf{AB}}_{\beta}\right)^{R_{\beta}}=O\left(2^{-R_{\beta}}\right).$

  4. (4)

$\mathbf{\lVert\Delta\rVert_{1}\neq 0\textbf{ and
}p_{\boldsymbol{\beta}},p^{\mathsf{AB}}_{\boldsymbol{\beta}}\in\big{[}\frac{1}{2},1\big{)}.}$
Then there exists a $\beta\in\\{\beta_{1},\dots,\beta_{k}\\}$ such that
$\Delta_{\beta}\neq 0$. By using the Gaussian approximation for the binomial
distributions (which we may apply as we can always make the number of rounds
sufficiently large), one can show (cf. appendix A.1) that

$\displaystyle\mathbb{P}(\mathsf{acc}_{\beta}|\mathsf{attack})\lesssim\frac{\sqrt{2}f_{\beta}^{\mathsf{AB}}}{\sqrt{\pi
R_{\beta}}\Delta_{\beta}}e^{-\left(\sqrt{R_{\beta}}\Delta_{\beta}-f_{\beta}^{\mathsf{P}}c_{\alpha}\right)^{2}/\left(f_{\beta}^{\mathsf{AB}}\right)^{2}}=O\left(\frac{2^{-\Delta_{\beta}^{2}R_{\beta}}}{\Delta_{\beta}\sqrt{R_{\beta}}}\right)$
(3.5)

for functions $c_{\alpha},f_{\beta}$ that are independent of $R_{\beta}$ and
$\Delta_{\beta}$. Hence in this scenario the success probability of attackers
is also exponentially suppressed.

So unless $\Delta_{\beta}=0$ for all $\beta$, we have exponential suppression
in the attacker success probability
$\mathbb{P}(\mathsf{acc}|\mathsf{attack})$. In the end, we can set a threshold
$R$ for the number of rounds and the protocol is to be run until
$R_{\beta}\geq R$ for all $\beta$. This will guarantee that any desired
security level can be achieved by increasing $R$ “uniformly” over all $\beta$.
We end up with a protocol that accepts an honest party with high probability
and rejects attackers with high probability. A sketch is depicted in Figure 3.

Figure 3: Sketch of the idea behind the statistical test. Acceptance regions
around the expected honest $p_{\beta}$’s is defined such that P will be
captured with high probability (blue). Attackers trying to spoof verifiers by
minimizing all $\Delta_{\beta}$ as well as possible (red) have exponentially
low (in $R$) probability of returning a sample contained in the acceptance
regions for all $\beta$. Here $C_{\beta,0}$ denotes the number of ‘0’ answers
among the conclusive ones in $C_{\beta}$.

The analysis also suggests that optimally attackers want to minimize all
$|\Delta_{\beta}|$ simultaneously101010Note that minimizing
$|p_{\beta}-p_{\beta}^{\mathsf{AB}}|$ also minimizes the Kullback-Leibler
divergence $D_{\text{KL}}(P\parallel Q)$ between the corresponding binomial
distributions $P$ and $Q$.. We therefore choose to minimize
$\lVert\Delta\rVert_{1}$. As LOCC $\subset$ PPT [CLM+14], the following conic
optimization program will provide a lower bound on $\lVert\Delta\rVert_{1}$
for LOCC restricted attackers. To account for imperfect quantum channel
transmittance, we include a parameter $\eta\in(0,1]$ and a third answer option
$\varnothing$ (“loss”). Then $\Delta_{\beta}$ is to be evaluated conditioned
on conclusive answers, i.e.,
$\Delta_{\beta}=p_{\beta}-\operatorname{Tr}[\Pi_{0}\rho_{\beta}]/\eta$, where

$\displaystyle\rho_{\beta}=\int_{\text{U}(2)}U\otimes
U\ket{\psi\phi}\bra{\psi\phi}U^{\dagger}\otimes
U^{\dagger}d\mu(U)=\frac{1}{3}\frac{1+\beta^{2}}{2}\Pi_{\text{sym}}+\frac{1-\beta^{2}}{2}\Pi_{\text{a-sym}}$
(3.6)

is the mixed state the verifiers produce for overlap $\beta$ [Wat18]. Here
$\Pi_{\text{sym}},\Pi_{\text{a-sym}}$ are the projectors onto the symmetric
and antisymmetric subspace, respectively, and $\mu$ is the Haar measure on the
unitary group U$(2)$. These considerations lead us to the optimization:

$\displaystyle\begin{split}\textbf{minimize: }&\lVert\Delta\rVert_{1}\\\
\textbf{subject to: }&\Pi_{0}+\Pi_{1}+\Pi_{\varnothing}=\mathbbm{1}_{4}\\\
&\Pi_{k}\in\text{PPT}(\mathsf{A}:\mathsf{B}),\qquad
k\in\\{0,1,\varnothing\\}\\\
&\operatorname{Tr}[\Pi_{\varnothing}\rho_{\beta}]=1-\eta,\qquad\beta\in\\{\beta_{1},\dots,\beta_{m}\\}.\end{split}$
(3.7)

The constraints involving $\eta$ stem from the fact that P will produce the
same inconclusive-rate on all overlaps $\beta$ and the attackers need to mimic
that. An analogous statistical test with a $(1-\alpha)$-quantile around $\eta$
can be performed to check for this and it is clear that it is optimal for
attackers to choose to reply inconclusive at the exact same rate as P would do
for each $\beta$. The above program can be solved with conventional conic
optimization libraries, e.g. MOSEK [ApS20], and any example
$\\{\beta_{1},\dots,\beta_{k}\\}$ we have tried yielded an optimal
$\lVert\Delta\rVert_{1}>0$ independent of $\eta$, indicating the loss-
tolerance of the protocol.

Unfortunately, we were not able to prove if our protocol remains secure if
attackers are allowed to use quantum communication between them. The security
in that setting remains an open problem. Moreover, the analysis of
QPV${}_{\textsf{SWAP}}(\beta_{1},\dots,\beta_{k})$ under realistic
experimental conditions is work in progress and looks promising. We will now
proceed and analyze the special case of overlaps $\\{0,1\\}$, i.e., sending
orthogonal or identical states, in more detail and show analytically that it
has desirable properties.

###  3.1 Security of QPV${}_{\textsf{SWAP}}(0,1)$ Protocol

In this setting, there is the notion of a correct answer. On equal inputs the
verifiers always expect the answer ‘0’. This allows for a SDP formulation for
maximizing the average success probability of identifying if the input states
were equal/unequal. In appendix A.2 it is shown that the relation between the
success probability $p_{\text{succ}}$ of correctly identifying
equal/orthogonal and $\lVert\Delta\rVert_{1}$ is

$\displaystyle p_{\text{succ}}\leq
u\implies\lVert\Delta\rVert_{1}\geq\frac{3}{2}-2u.$ (3.8)

It turns out that for overlaps $\\{0,1\\}$ the optimization (3.7) returns
$\Delta_{0}=0$ and $\Delta_{1}=1/4$, despite the above constraint of only
$\lVert\Delta\rVert_{1}\geq 1/6$ for $p_{\text{succ}}\leq 2/3$, as will be
shown below. However, constraining the SDP to
$\operatorname{Tr}[\Pi_{\neq}\rho_{\neq}]/\eta=x$ and placing the objective
function $\max_{\\{\Pi\\}}\operatorname{Tr}[\Pi_{=}\rho_{=}]/\eta=y$ (with PPT
constraints) allows us to see the trade-off between being correct on equal
inputs versus on orthogonal inputs. This yields

$\displaystyle y(x)=\begin{cases}1-\frac{x}{2}&0\leq x\leq\frac{2}{3}\\\
2-2x&\frac{2}{3}\leq x\leq 1\end{cases}.$ (3.9)

It is clear that $x$ should be smaller than $2/3$, but then adding an error
$\varepsilon$ to the success rate on unequal inputs only reduces the error on
equal inputs by $\varepsilon/2$. It is therefore optimal to try to achieve
$\varepsilon=0$, that is $\Delta_{0}=0$, and accept whatever error this
implies on equal inputs. Indeed, then $\Delta_{1}=1/4$, consistent with the
result of (3.7).

Having drawn the connection between $p_{\text{succ}}$ and
$\lVert\Delta\rVert_{1}$, we will now proceed to show that there is a finite
gap in the success probability of testing for equality between adversaries
restricted to LOCC operations and an honest prover who can apply entangling
measurements. Extending this single round protocol to $n$ rounds played in
parallel, we will also show that the best strategy for adversaries is to
simply apply the optimal single round strategy to every round individually,
which shows strong parallel repetition for QPV${}_{\textsf{SWAP}}(0,1)$.
Furthermore we show that in both cases there is no advantage for the attackers
if they have the ability to declare loss on rounds, i.e. the probability of
success conditioned on answering is independent of loss. The security lies in
the fact that an honest prover at his claimed position can apply entangling
operations to the two incoming qubits and has a strictly higher probability of
answering the question correctly than spatially separated adversaries who are
restricted to single round LOCC operations.

In fact, the operation that has the highest probability of generating the
correct answer is the SWAP test [MdW18] and it gives a success probability
$p_{\text{succ}}(\text{SWAP test})=3/4$. We will show that the best strategy
for LOCC adversaries gives at most probability
$p^{\text{max}}_{\text{succ}}(\text{LOCC})=2/3$. Since attackers return only a
classical bit and they discard their post-measurement state, the most general
type of measurement the attackers do is a positive-operator-valued meaure
(POVM). The attackers’ success probability for a given admissible POVM
strategy $\Pi=\\{\Pi_{0},\Pi_{1}\\}$ is then given by

$\displaystyle
p_{\text{succ}}(\Pi):=\frac{1}{2}\operatorname{Tr}[\Pi_{0}\rho_{0}+\Pi_{1}\rho_{1}].$
(3.10)

Maximizing over all two-qubit LOCC measurements $\Pi^{\text{LOCC}}$ would give
us the best probability of success of the attackers. However characterizing
and maximizing over LOCC strategies is a mathematically complex task. We
follow the method used in [LXS+16], and maximize our problem over the set of
all positive partial transpose (PPT) operations. Since PPT measurements are a
proper superset of LOCC measurements, any maximal success probability
optimized over PPT measurements immediately upper bounds the success
probability of all LOCC measurements. Furthermore, the PPT condition can be
represented by a set of linear and positive semidefinite conditions [Cos13]
which enables us to write down the maximization problem as a semidefinite
program (SDP) [VB96]. This allows us to find exact solutions to the
optimization problem if the values of the primal program and dual program
coincide. In our case the SDP 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}\otimes\mathsf{B}),\ \ \
i\in\\{0,1\\},$

Note that the primal program implies a lower bound and the dual program an
upper bound to $p^{\text{max}}_{\text{succ}}(\Pi^{\text{PPT}})$. We find that
the optimal solution to the SDP is 2/3 (see Appendix A.3), giving an upper
bound of the success probability optimized over all LOCC measurements of

$\displaystyle
p^{\text{max}}_{\text{succ}}(\Pi^{\text{LOCC}})\leq\frac{2}{3}.$ (3.11)

The input states $\rho_{0}$ and $\rho_{1}$ have the exact same mixed state
matrices as the result of uniformly choosing a mutually unbiased basis and
sending either equal or orthogonal states (from the chosen basis) to P. This
indicates a possible “good” LOCC strategy. Assume the incoming qubits are
encoded in MUB $b$, and that the attackers choose a random MUB $b^{\prime}$,
measure both incoming qubits in the basis $b^{\prime}$, send the measurement
outcome to each other, and return equal if the measurement outcomes are equal
and unequal otherwise. Then their probability of success is exactly $2/3$,
since

$\displaystyle\mathbb{P}(\text{success})=\mathbb{P}(b^{\prime}=b)\mathbb{P}(\text{success}|b^{\prime}=b)+\mathbb{P}(b^{\prime}\neq
b)\mathbb{P}(\text{success}|b^{\prime}\neq b)=\frac{1}{3}\cdot
1+\frac{2}{3}\cdot\frac{1}{2}=\frac{2}{3}.$ (3.12)

This attack strategy uses only local measurements and a single round of
communication, so it is a valid single round LOCC operation. Thus we find that
the upper bound in (3.11) over LOCC measurements is actually tight.

We have shown that probability of success for identifying if given inputs were
equal or not for the QPV${}_{\textsf{SWAP}}(0,1)$ protocol is strictly lower
for attackers restricted to LOCC measurements than for an honest verifier who
can apply entangling operations. Over sequential multi-round protocols, where
we only perform a new run of the protocol after previous is finished and
attackers act independently, the verifiers can increase the precision of
detecting LOCC attackers to any limit they desire.

A natural question to ask is whether we can extend the single round protocol
to a general $n$-round parallel protocol, where the verifiers send $n$ qubits
from both sides to form the density matrix
$\rho_{s}=\rho_{s_{0}}\otimes\rho_{s_{1}}\otimes\dots\otimes\rho_{s_{n-1}}$
for some string $s\in\\{0,1\\}^{n}$. A proof for this does not follow
trivially from the single round security proof since attackers can now in
principle take blocks of inputs and apply entangling operations on them. We
shall prove that for the QPV${}_{\textsf{SWAP}}$ protocol strong parallel
repetition does indeed hold, i.e. the probability of success of winning $n$
rounds decreases as $(2/3)^{n}$. Again we can write down the problem as a SDP
optimization task where we optimize over all PPT operations on the $2n$ qubits
the attackers receive.

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

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

As shown in Appendix A.4, there is a feasible dual solution yielding a dual
value of $(2/3)^{n}$, which bounds the probability of success under LOCC
measurements by $(2/3)^{n}$. A feasible solution to the primal problem is to
fill in the single round solution $n$ times and this has success probability
$(2/3)^{n}$. Since this strategy turns out to be the above mentioned single
round LOCC measurement applied to each $\rho_{s_{i}}$, we find that the upper
bound is again tight, and we have shown strong parallel repetition for the
QPV${}_{\textsf{SWAP}}$ protocol.

###  3.2 Loss-Tolerance of QPV${}^{n}_{\textsf{SWAP}}$ Protocol

In the previous section we have shown that the QPV${}_{\textsf{SWAP}}$
protocol is safe against attackers restricted to LOCC attackers if we require
them to always answer. However this is not always possible in practice because
of loss in the quantum channel. In order to prove security against any
coalition of attackers in the setting with channel loss we must assume that
attackers will never suffer any loss when they attack a protocol111111They
could position themselves very close to the verifiers, for example.. When
classical information is sent, such as in the QPV${}_{\text{BB84}}$ protocol
[KMS11, BCF+11], attackers may guess the classical information that is being
send. If they guess incorrectly they discard the round and declare a loss, if
they guess correctly they can continue and successfully attack the protocol
since the classical information is known to both attackers immediately. If the
loss rate is high enough, attackers can hide their incorrect guesses in the
loss declarations and the verifiers cannot distinguish the attackers from an
honest prover. Since our QPV${}_{\textsf{SWAP}}$ protocol does not send any
classical information we suspect it will be loss-tolerant. In section 4.3 we
will consider this observation again in a more general setting. To prove loss
tolerance, we can incorporate loss in the previous SDP and show that the
optimal solution is independent of the loss, in a similar fashion as in
[LXS+16].

We can relatively straightforwardly add the condition that attackers must
mimic a certain loss rate $1-\eta$ on all inputs depending on the loss of the
quantum channels. For the parallel repetition case this means that attackers
either answer conclusively on all inputs or don’t answer at all. We will later
show that, if security is retained if we allow attackers to play either all
rounds or none at all, then this implies that security is also retained if
attackers are allowed to say “loss” on any number of rounds (which means full
loss tolerance). We maximize the probability of success conditioned on a
conclusive answer $p_{\text{succ}}^{\text{max}}(n,\eta)$ by dividing through
the success rate $\eta$. Here we consider the corresponding SDP maximization
problem to the parallel repetition case with $n$-rounds right away ($n=1$
corresponds to the single round protocol). The corresponding SDP of the
maximization over all attacker strategies then becomes

Primal Program maximize:
$\displaystyle\frac{1}{2^{n}\eta}\sum_{s\in\\{0,1\\}^{n}}\operatorname{Tr}[\tilde{\Pi}_{s}\rho_{s}]$
subject to:
$\displaystyle\left(\sum_{s\in\\{0,1\\}^{n}}\tilde{\Pi}_{s}\right)+\tilde{\Pi}_{\varnothing}=\mathbbm{1}_{2^{2n}}$
$\displaystyle\operatorname{Tr}[\tilde{\Pi}_{\varnothing}\rho_{s}]=1-\eta,\ \
\ s\in\\{0,1\\}^{n}$
$\displaystyle\tilde{\Pi}_{s}\in\text{PPT}(\mathsf{A}:\mathsf{B}),\ \ \
s\in\\{0,1\\}^{n}\cup\varnothing$

Dual Program minimize:
$\displaystyle\frac{\operatorname{Tr}[\tilde{Y}]-(1-\eta)\gamma}{\eta}$
subject to:
$\displaystyle\tilde{Y}-\tilde{Q}^{T_{\mathsf{B}}}_{s}-\rho_{s}/2^{n}\succeq
0,\ \ \ s\in\\{0,1\\}^{n}$ $\displaystyle
2^{2n}(\tilde{Y}-\tilde{Q}^{T_{\mathsf{B}}}_{\varnothing})-\gamma\mathbbm{1}_{2^{2n}}\succeq
0$ $\displaystyle\tilde{Y}\in\text{Herm}(\mathsf{A}\otimes\mathsf{B})$
$\displaystyle\tilde{Q}_{s}\in\text{Pos}(\mathsf{A}\otimes\mathsf{B}),\ \ \
s\in\\{0,1\\}^{n}\cup\varnothing$ $\displaystyle\gamma\in\mathbb{R}.$

From the analysis in Appendix A.5, we see that the solution of the SDP is
again $(2/3)^{n}$, independent of $\eta$, upper bounding the attackers
restricted to LOCC measurements. The strategy in which attackers apply with
probability $\eta$ the regular $n$-round parallel repetition attack and with
probability $(1-\eta)$ discard the round again has conditional success
probability $(2/3)^{n}$ so the bound is tight. We can use the fact that for
any number of rounds $n$ the QPV${}^{n}_{\textsf{SWAP}}$ is tolerant against
loss on the whole block in order to prove that the same is also true for any
subset of rounds.

######  Proposition 3.1.

Any multi-round QPV protocol that fulfills strong parallel repetition security
against adversaries restricted to LOCC operations and is tolerant against
declaring loss on all $n$ rounds, is also tolerant against declaring loss on
any subset of rounds.

###### Proof.

Suppose we have a secure $n$-round QPV protocol with strong parallel
repetition. Then the $n$-round success probability for attackers
$p_{n}=p_{1}^{n},\forall n\in\mathbb{N}$ for some single round probability
$p_{1}\in[0,1]$. Suppose we perform $n$ rounds and we allow adversaries to
only answer on $k$ rounds and to declare a loss on the remaining $(n-k)$
rounds, and that there exists an attacking strategy $S$ restricted to LOBC
measurements that has a probability of success $p_{S}>p_{1}^{k}$ on a random
subset of size $k$. We shall show that this leads to a contradiction. Consider
a protocol like the $k$-round protocol QPV${}^{k}_{\textsf{SWAP}}$, which is
secure and loss tolerant on all rounds by assumption and has success
probability $p_{k}=p_{1}^{k}$. Since individual rounds are product states,
attackers may create $n-k$ independent extra rounds locally of which they can
forget the answer. This creates a $n$-round protocol. The attackers can now
apply their strategy $S$. With probability $1/\binom{n}{k}$ they get an answer
on their initial $k$ rounds that is correct with success probability $p_{S}$.
And with probability $1-1/\binom{n}{k}$ they receive the wrong subset of $k$
rounds, in which case the attackers declare a loss (on all rounds). This
defines an LOCC attack with a conditional winning probability
$p_{S}>p_{1}^{k}$ and loss rate of $1-1/\binom{n}{k}$, which contradicts our
assumption that the maximal success probability of being correct on the
$k$-round protocol is $p_{1}^{k}$ for any loss. Therefore, for any subset of
$k$ rounds out of the total of $n$ rounds, the maximal success probability on
this subset is again $p_{1}^{k}=p_{k}$. ∎

Thus, in particular, we have that the QPV${}^{n}_{\textsf{SWAP}}$ is tolerant
against loss on any subset of rounds.

###  3.3 Entanglement attack

It turns out that there is a perfect attack on
QPV${}_{\textsf{SWAP}}(\beta_{1},\dots,\beta_{k})$ using one pre-shared
maximally entangled state between the attackers. This gets apparent if one
looks at the purified version of the protocol. In this setting, the attackers
do not receive mixed states from the verifiers, but rather halves of the
corresponding purification. In
QPV${}_{\textsf{SWAP}}(\beta_{1},\dots,\beta_{k})$ this purification is a
maximally entangled state on each side. This does not change anything about
the input/output distributions of the attackers, as already noted in [BCF+14].
Entanglement swapping is captured in the identity

$\displaystyle\ket{\Phi_{+}}_{12}\ket{\Phi_{+}}_{34}=\frac{1}{2}\left(\ket{\Phi_{+}}_{14}\ket{\Phi_{+}}_{23}+\ket{\Phi_{-}}_{14}\ket{\Phi_{-}}_{23}+\ket{\Psi_{+}}_{14}\ket{\Psi_{+}}_{23}+\ket{\Psi_{-}}_{14}\ket{\Psi_{-}}_{23}\right).$
(3.13)

Applying a Bell state measurement (BSM) on registers (23) swaps entanglement
from registers (12) and (34) to (14) and (23). The intriguing aspect is that
registers (14) could be causally separated, yet are entangled after the BSM.
We use this to prove the following statement.

######  Theorem 3.2.

The _SWAP-_ test can be perfectly simulated using one pre-shared maximally
entangled state and one round of classical communication between $\mathsf{A}$
and $\mathsf{B}$. Thus $n$ pre-shared EPR pairs are sufficient to attack _QPV_
${}_{\mathsf{SWAP}}^{n}(\beta_{1},\dots,\beta_{k})$, and $\sim 0.103n$ pre-
shared EPR pairs are necessary to attack _QPV_ ${}_{\mathsf{SWAP}}^{n}(0,1)$.

###### Proof.

In the purified protocol, verifiers do not send out their respective mixed
states $\rho_{V_{0}},\rho_{V_{1}}$ but rather halves of the corresponding
purified pure state. Note that for a given list of overlaps
$\mathcal{O}=\\{\beta_{1},\dots,\beta_{k}\\}$ the total input state is
$\rho=\frac{1}{k}\sum_{\beta\in\mathcal{O}}\rho_{\beta}$. One can then
calculate

$\displaystyle\operatorname{Tr}_{V_{0}}[\rho]=\operatorname{Tr}_{V_{1}}[\rho]=\frac{\mathbbm{1}_{2}}{2}$

and therefore the purifications at $\mathsf{V_{0}},\mathsf{V_{1}}$ are
maximally entangled states, say $\ket{\Phi_{+}}$. The resulting entanglement
structure between the verifiers and attackers throughout the attack is as
depicted in Figure 4.

$\mathsf{V_{0}}$$\mathsf{A_{1}}\hskip 2.84526pt$$\mathsf{V_{1}}$$\hskip
5.69054pt\mathsf{B_{1}}$$\mathsf{A_{2}}\hskip 2.84526pt$$\hskip
5.69054pt\mathsf{B_{2}}$ (a) Attackers receive quantum states.

$\mathsf{V_{0}}$$\mathsf{A_{1}}\hskip 2.84526pt$$\mathsf{V_{1}}$$\hskip
5.69054pt\mathsf{B_{1}}$$\mathsf{A_{2}}\hskip 2.84526pt$$\hskip
5.69054pt\mathsf{B_{2}}$ (b) Each applies a BSM.

$\mathsf{V_{0}}$$\mathsf{A_{1}}\hskip 2.84526pt$$\mathsf{V_{1}}$$\hskip
5.69054pt\mathsf{B_{1}}$$\mathsf{A_{2}}\hskip 2.84526pt$$\hskip
5.69054pt\mathsf{B_{2}}$ (c) They communicate results.

Figure 4: Entanglement structure throughout a purified protocol.

Assume now that attackers pre-share one EPR pair, say also $\ket{\Phi_{+}}$,
in registers $A_{2}B_{2}$. Then the total input state of the protocol can be
rewritten as

$\displaystyle\ket{\Phi_{+}}_{V_{0}A_{1}}\ket{\Phi_{+}}_{V_{1}B_{1}}\ket{\Phi_{+}}_{A_{2}B_{2}}=$
$\displaystyle\frac{1}{2}\bigg{[}\ket{\Phi_{+}}_{V_{0}V_{1}}\otimes\frac{1}{2}\Big{(}\ket{\Phi_{+}}\ket{\Phi_{+}}+\ket{\Phi_{-}}\ket{\Phi_{-}}+\ket{\Psi_{+}}\ket{\Psi_{+}}+\ket{\Psi_{-}}\ket{\Psi_{-}}\Big{)}_{A_{1}A_{2}B_{1}B_{2}}$
$\displaystyle+\ket{\Phi_{-}}_{V_{0}V_{1}}\otimes\frac{1}{2}\Big{(}\ket{\Phi_{+}}\ket{\Phi_{-}}+\ket{\Phi_{-}}\ket{\Phi_{+}}+\ket{\Psi_{+}}\ket{\Psi_{-}}+\ket{\Psi_{-}}\ket{\Psi_{+}}\Big{)}_{A_{1}A_{2}B_{1}B_{2}}$
$\displaystyle+\ket{\Psi_{+}}_{V_{0}V_{1}}\otimes\frac{1}{2}\Big{(}\ket{\Phi_{+}}\ket{\Psi_{+}}-\ket{\Phi_{-}}\ket{\Psi_{-}}+\ket{\Psi_{+}}\ket{\Phi_{+}}-\ket{\Psi_{-}}\ket{\Phi_{-}}\Big{)}_{A_{1}A_{2}B_{1}B_{2}}$
$\displaystyle+\ket{\Psi_{-}}_{V_{0}V_{1}}\otimes\frac{1}{2}\Big{(}\ket{\Phi_{-}}\ket{\Psi_{+}}-\ket{\Psi_{+}}\ket{\Phi_{-}}+\ket{\Psi_{-}}\ket{\Phi_{+}}-\ket{\Phi_{+}}\ket{\Psi_{-}}\Big{)}_{A_{1}A_{2}B_{1}B_{2}}\bigg{]}.$

By separately performing a BSM on their two respective qubits in $A_{1}A_{2}$
and $B_{1}B_{2}$, the attackers will get one of the 16 measurement result
combinations in the above equation and collapse the state in $V_{0}V_{1}$ into
the corresponding Bell state. By communicating their results (classically) to
each other, they can uniquely identify the state in the verifiers’ registers
$V_{0}V_{1}$. Let them then use the following strategy: answer ‘0’, whenever
they infer that the verifiers hold a symmetric state and ‘1’, whenever it is
an anti-symmetric state. Doing so, attackers effectively perform a measurement
$\\{\Pi_{\text{sym}},\Pi_{\text{a-sym}}\\}$ on $V_{0}V_{1}$, which is
precisely what the SWAP test does. To make this argument formal, let A and B
receive registers $V_{0}$ and $V_{1}$, respectively. Inspired by the above,
define

$\displaystyle W$ $\displaystyle\coloneqq$
$\displaystyle\mathbbm{1}_{V_{0}}\otimes\text{SWAP}_{A_{2}V_{1}}\otimes\mathbbm{1}_{B_{2}}$
$\displaystyle\Pi_{0}$ $\displaystyle\coloneqq\Big{(}$
$\displaystyle\ket{\Phi_{+}\Phi_{+}}\\!\bra{\Phi_{+}\Phi_{+}}+\ket{\Phi_{-}\Phi_{-}}\\!\bra{\Phi_{-}\Phi_{-}}+\ket{\Psi_{+}\Psi_{+}}\\!\bra{\Psi_{+}\Psi_{+}}+\ket{\Psi_{-}\Psi_{-}}\\!\bra{\Psi_{-}\Psi_{-}}+$
$\displaystyle\ket{\Phi_{+}\Phi_{-}}\\!\bra{\Phi_{+}\Phi_{-}}+\ket{\Phi_{-}\Phi_{+}}\\!\bra{\Phi_{-}\Phi_{+}}+\ket{\Psi_{+}\Psi_{-}}\\!\bra{\Psi_{+}\Psi_{-}}+\ket{\Psi_{-}\Psi_{+}}\\!\bra{\Psi_{-}\Psi_{+}}+$
$\displaystyle\ket{\Phi_{+}\Psi_{+}}\\!\bra{\Phi_{+}\Psi_{+}}+\ket{\Phi_{-}\Psi_{-}}\\!\bra{\Phi_{-}\Psi_{-}}+\ket{\Psi_{+}\Phi_{+}}\\!\bra{\Psi_{+}\Phi_{+}}+\ket{\Psi_{-}\Phi_{-}}\\!\bra{\Psi_{-}\Phi_{-}}\Big{)}_{V_{0}A_{2}V_{1}B_{2}}$
$\displaystyle\Pi_{1}$ $\displaystyle\coloneqq$
$\displaystyle\Big{(}\ket{\Phi_{-}\Psi_{+}}\\!\bra{\Phi_{-}\Psi_{+}}+\ket{\Psi_{+}\Phi_{-}}\\!\bra{\Psi_{+}\Phi_{-}}+\ket{\Psi_{-}\Phi_{+}}\\!\bra{\Psi_{-}\Phi_{+}}+\ket{\Phi_{+}\Psi_{-}}\\!\bra{\Phi_{+}\Psi_{-}}\Big{)}_{V_{0}A_{2}V_{1}B_{2}}.$

Note that $\Pi_{0}$ and $\Pi_{1}$ are positive semi-definite and
$\Pi_{0}+\Pi_{1}=\mathbbm{1}$, so that $\\{\Pi_{0},\Pi_{1}\\}$ is a valid
POVM. It can then be explicitly checked that

$\displaystyle\begin{split}\Pi_{\text{sym}}^{V_{0}V_{1}}\rho_{\beta}^{V_{0}V_{1}}&=\operatorname{Tr}_{A_{2}B_{2}}\Big{[}W\Pi_{0}^{V_{0}A_{2}V_{1}B_{2}}W^{\dagger}\,\,\left(\rho_{\beta}^{V_{0}V_{1}}\otimes\ket{\Phi_{+}}\\!\bra{\Phi_{+}}^{A_{2}B_{2}}\right)\Big{]}\\\
\Pi_{\text{a-sym}}^{V_{0}V_{1}}\rho_{\beta}^{V_{0}V_{1}}&=\operatorname{Tr}_{A_{2}B_{2}}\Big{[}W\Pi_{1}^{V_{0}A_{2}V_{1}B_{2}}W^{\dagger}\,\,\left(\rho_{\beta}^{V_{0}V_{1}}\otimes\ket{\Phi_{+}}\\!\bra{\Phi_{+}}^{A_{2}B_{2}}\right)\Big{]},\end{split}$
(3.14)

for any $\beta\in[0,1]$. Equation (3.14) shows that the above attack using one
pre-shared EPR pair is exactly the same as the honest action on
$\rho_{\beta}$. In other words, the attackers can perfectly simulate the SWAP
test and thus reproduce P. To get a lower bound on the required entanglement
resource in order to break QPV${}_{\mathsf{SWAP}}(0,1)$ we can use an argument
already mentioned in Lemma V.3 in [BK11]. It says that if the attackers pre-
share a $d$-dimensional resource state $\tau_{\mathsf{AB}}$ then the success
probability (of the attackers achieving that the verifiers accept them) is
related to the success probability without a pre-shared resource in the
following way:

$\displaystyle p_{\text{succ}|\tau_{\mathsf{AB}}}\leq
dp_{\text{succ}|\emptyset}.$ (3.15)

For the $\beta\in\\{0,1\\}$ case, we argued at the beginning of section 3.1
that the optimal attack strategy is to produce no error on orthogonal inputs
and then accept whatever error that means for the identical inputs (which
turned out to be $\Delta_{1}=1/4$). Then, the probability that the verifiers
accept attackers is basically $(3/4)^{n_{=}}$, where $n_{=}$ is the number of
rounds with identical inputs. Since each overlap is chosen with probability
$1/2$ in each round, we have for $n$ rounds that $\mathbb{E}[n_{=}]=n/2$.
Hence, we expect $p_{n,\text{succ}|\tau_{\mathsf{AB}}}\leq
d\left(\frac{3}{4}\right)^{n/2}$ and thus

$\displaystyle p_{n,\text{succ}|\tau_{\mathsf{AB}}}<1\qquad\text{as long
as}\qquad d<\left(\frac{4}{3}\right)^{n/2}.$ (3.16)

If $m$ is the number of EPR pairs in $\tau_{\mathsf{AB}}$, so that $d=2^{2m}$,
it follows that, in expectation,

$\displaystyle p_{n,\text{succ}|\tau_{\mathsf{AB}}}<1\qquad\text{as long
as}\qquad m<\frac{1}{4}\log\left(\frac{4}{3}\right)n\approx 0.103n.$ (3.17)

∎

##  4 More general results concerning loss and quantum communication in QPV

###  4.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 if they are allowed to perform local operations and quantum
communication (LOQC) instead of classical. One might think that there is no
advantage in sending quantum information over classical communication when the
output messages of the attackers are classical, but this turns out the be
false. 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.

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 either symmetric or antisymmetric. An honest prover who can
apply entangling operations can answer this question with success probability
$1$ by applying a Bell measurement. 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.6). 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
tight.

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 the antisymmetric Bell state. An honest prover who
can apply entangling operations can still solve this protocol with success
probability $1$ by applying a Bell measurement to one of the two pairs. Note
that attackers who have access to a quantum channel can send half of their
input state to each other such that both attackers end up with a local Bell
state. The attackers can then both apply a Bell measurement locally and
successfully attack the protocol with success probability $1$. By analysis of
the SDP it turns out that the upper bound under PPT measurements is $17/18$,
cf. appendix A.6. 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 equal
otherwise. Again 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/9$, so the total
probability of success of the LOCC protocol becomes

$\displaystyle\mathbb{P}_{\text{succ}}=\frac{1}{2}\cdot
1+\frac{1}{2}\cdot\left(1-\frac{1}{9}\right)=\frac{17}{18}.$ (4.1)

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. Similar to the loss-
tolerance analysis of QPV${}_{\textsf{SWAP}}$, we even find that this protocol
is also loss-tolerant.

###  4.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 LOBC operations.

We show that the existence of a perfect quantum communication attack on a QPV
protocol generates two new QPV protocols, which ultimately leads to the
existence of a QPV protocol that is secure against adversaries restricted to
LOBC and cannot be perfectly attacked by adversaries using quantum
communication.

Take any QPV protocol in which two verifiers $\mathsf{V_{0}},\mathsf{V_{1}}$
send states $\rho_{A},\rho_{B}$ and ask for the outcome of, say, some
entangling measurement on the joint state $\rho_{AB}$, e.g. the SWAP test.
Suppose the protocol is secure against adversaries restricted to LOBC, i.e.,
there is a finite gap in the probability of success between an honest prover
and adversaries restricted to LOBC operations, but 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 half of their local outcome to the other adversary.

  * •

Apply a measurement on the new local states
$\sigma_{A_{1}}\otimes\sigma_{B_{1}}$ and
$\sigma_{A_{2}}\otimes\sigma_{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 LOBC attack on one of these newly arising protocols was already
a valid LOBC 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_{0}}$$a$$\rho_{B}$$\mathsf{V_{1}}$$\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_{0}}$$a$$\sigma_{B_{2}}$$\mathsf{V_{1}}$$\sigma_{A_{1}B_{1}}$$t$$x$$\mathsf{P}$$a$$\sigma_{A_{1}}$$\mathsf{V_{0}}$$a$$\sigma_{B_{1}}$$\mathsf{V_{1}}$

$t$$x$$\mathsf{P}$$a$$\sigma_{A_{2}}$$\tau_{B_{3}}$$\tau_{A_{3}}$$\mathsf{V_{0}}$$a$$\sigma_{B_{2}}$$\mathsf{V_{1}}$$\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_{0}}$$a$$\sigma_{B_{1}}$$\mathsf{V_{1}}$$\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_{0}}$$a$$\tau_{B_{4}}$$\mathsf{V_{1}}$$\tau_{A_{3}B_{3}}$$t$$x$$\mathsf{P}$$a$$\tau_{A_{3}}$$\mathsf{V_{0}}$$a$$\tau_{B_{3}}$$\mathsf{V_{1}}$$\tau_{A_{2}B_{2}}$$t$$x$$\mathsf{P}$$a$$\tau_{A_{2}}$$\mathsf{V_{0}}$$a$$\tau_{B_{2}}$$\mathsf{V_{1}}$$\tau_{A_{1}B_{1}}$$t$$x$$\mathsf{P}$$a$$\tau_{A_{1}}$$\mathsf{V_{0}}$$a$$\tau_{B_{1}}$$\mathsf{V_{1}}$

Figure 5: 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 half 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 loss-tolerant and 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 5 for a visual representation of the 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 send from verifier $\mathsf{V_{0}}$ in the induced
QPV protocols after splitting only depend on the previous input states send
from $\mathsf{V_{0}}$ and vice-versa for the input states from
$\mathsf{V_{1}}$. 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
main idea for 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. We use Theorem 1 on the emergent classicality of channels from
[QR20].

######  Theorem 4.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|}},$ (4.2)

using a measure-and-prepare channel

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

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 rounds $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(2)}{2^{n-1}-1}}.$ (4.4)

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 LOBC attack
in the original QPV protocol. 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 LOBC attack allows attackers to answer correctly with a probability of
success that converges to the perfect probability of success in the number of
splittings $n$. By assumption $n$ can be arbitrarily large and thus the
attackers have an LOBC attack that performs arbitrarily well. However, since
for our original protocol there is a finite gap between the LOBC probability
of success and the perfect probability of success, we have a contradiction and
conclude that not all of the induced QPV protocols after some $N$ splittings
can be attacked perfectly. Thus a QPV protocol arises after some amount of
splittings that must be safe against unentangled adversaries restricted to
quantum communication.

###  4.3 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 protocol121212The 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 (and when the locations of the
verifiers are not collinear), the probability that no teleportation needs
corrections is much lower, i.e. $1/d^{2(m-1)}$.:

  * •

Verifiers $\mathsf{V}_{0},\mathsf{V}_{1}$ send $d_{0},d_{1}$ 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}_{0}$ and one for $\mathsf{V}_{1}$. 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_{0},d_{1},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=\min\\{d_{0},d_{1}\\}$, as long as the loss is high enough131313We assume
that all-powerful attackers have some way of determining the dimensionality of
their inputs, so that they know who of them holds the smaller quantum input..
We make this precise in the following statement.

######  Proposition 4.2.

Let $d=\min\\{d_{0},d_{1}\\}$ and $k=|\operatorname{Im}(f)|$. Any $n$-round
_QPV_ $(d_{0},d_{1},f)$ protocol can be attacked with $O(n\log d)$ 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 the smaller quantum input
with dimension $d=\min\\{d_{0},d_{1}\\}$ and classical input $x$. As soon as A
receives his quantum input, quantum teleportation [BBC+93] can be used to
teleport the state to B, 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_{0}}$ is supposed to receive to A and keep
the part that $\mathsf{V_{1}}$ 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)$. If they can apply this attack on each round,
requiring $O(n\log d)$ ebits in total, they perfectly reproduce P. ∎

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$. It is now also clearer why the protocol in [LXS+16] and our
QPV${}_{\textsf{SWAP}}$ 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 practical fully loss tolerant QPV
protocol of the above type. The best we can achieve 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.

##  5 Conclusion

We analyzed the interplay between loss tolerance, quantum communication
attacks and QPV. Several results understanding loss tolerance in QPV better
were given including a proof that any QPV protocol can be broken with a linear
amount of EPR pair if the loss of quantum inputs is high enough. A new
protocol QPV${}_{\textsf{SWAP}}$ has been presented and we have shown that it
is fully loss tolerant against LOCC attackers with no pre-shared entanglement,
can be attacked with $\tilde{O}(n)$ pre-shared EPR pairs and that at least
$\sim 0.103n$ pre-shared EPR pairs are necessary in the $\beta\in\\{0,1\\}$
case. Moreover, it fulfills strong parallel repetition and retains the loss
tolerance even if all rounds are run in parallel. In addition, the flexibility
and simplicity of the SWAP test, both theoretically and experimentally, make
it an excellent candidate for practical QPV.

Having a loss tolerant protocol with parallel repetition, the question of
security under quantum communication attacks becomes much more
relevant141414For sequential protocols, attackers could in principle always
distribute sufficient entanglement in the first round in order to break all
subsequent rounds. If all rounds are run in parallel, they don’t have time to
do that. (We assume they don’t pre-share entanglement here.). The security of
our protocol in that setting remains an open problem. We have argued that care
has to be taken when including quantum communication attacks into QPV, as we
have presented an example for which LOCC attackers cannot break it, yet
quantum communication attackers can do so perfectly. However, using a
recursive splitting scheme and emergent classicality, we were able to show
that, starting from a protocol that can be perfectly attacked by quantum
communication attackers but not if restricted to LOCC, one can construct a QPV
protocol for which quantum communication does not allow attackers to break it
perfectly.

We suspect that our protocol is secure even if attackers are allowed to
quantum communicate and would be interested in finding a proof for it. Proofs
against quantum communication attacks have been quite elusive and there does
not seem to be a clear strategy. Formulating the problem as a non-local game,
as done in [TFKW13], does not seem to work well for protocols where both
verifiers send out quantum states. Both in [LXS+16] and our protocol the
verifiers are separable. This separable structure between $\mathsf{V}_{0}$ and
$\mathsf{V}_{1}$ makes it hard to optimize over all possible attacker
strategies, as not all states $\rho$ between the verifiers and attackers are
allowed as input to the game strategy, but the mentioned tensor product
structure must be obeyed. Recent quantum communication security proofs for
other protocols [JKPPG21, BCS21] were fairly involved.

Future work will include a detailed analysis of our protocol under realistic,
imperfect experimental conditions. This is work in progress and early results
look promising. We would also like to extend our splitting scheme to the
setting with loss, i.e. where we allow a third ‘$\varnothing$’ answer in all
protocols involved. The goal is then to show the existence of a QPV protocol
that is secure and loss tolerant, even if attackers can use quantum
communication.

In the end the goal is to find a practically feasible, yet secure, QPV
protocol. There remain a few more fundamental open questions to be solved for
that. For example, for optical fibre based QPV protocols, the speed of light
in fibre $v$ is strictly smaller than $c$, allowing attackers to cheat. Can we
overcome this issue by finding a feasible free-space protocol or one utilising
quantum repeaters? And ultimately, the gap in necessary/sufficient amount of
EPR pairs to break any QPV protocol, linear lower bound versus exponential
upper bound (in the input-size), needs to be closed. Hopefully towards an
exponential or at least superlinear lower bound.

#### Acknowledgments

We would like to thank Wolfgang Löffler, Kirsten Kanneworff and Norbert
Lütkenhaus 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

  * [ApS20] MOSEK ApS.  Mosek optimizer api for python.  Software Package, Ver, 9, 2020.
  * [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.
  * [BCF+14] Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, and Christian Schaffner.  Position-Based Quantum Cryptography: Impossibility and Constructions.  SIAM Journal on Computing, 43(1):150–178, January 2014.  arXiv: 1009.2490.
  * [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.
  * [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.
  * [CLM+14] Eric Chitambar, Debbie Leung, Laura Mančinska, Maris Ozols, and Andreas Winter.  Everything you always wanted to know about locc (but were afraid to ask).  Communications in Mathematical Physics, 328(1):303–326, 2014.
  * [Cos13] Alessandro Cosentino.  PPT-indistinguishable states via semidefinite programming.  Physical Review A, 87(1):012321, January 2013.  arXiv: 1205.1031.
  * [Dol19] Kfir Dolev.  Constraining the doability of relativistic quantum tasks.  arXiv preprint arXiv:1909.05403, 2019.
  * [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.
  * [GECP13] Juan Carlos Garcia-Escartin and Pedro Chamorro-Posada.  Swap test and hong-ou-mandel effect are equivalent.  Physical Review A, 87(5):052330, 2013.
  * [GLW13] Fei Gao, Bin Liu, and Qiao-Yan Wen.  Enhanced no-go theorem for quantum position verification.  arXiv preprint arXiv:1305.4254, 2013.
  * [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.
  * [MdW18] Ashley Montanaro and Ronald de Wolf.  A Survey of Quantum Property Testing.  arXiv:1310.2035 [quant-ph], March 2018.  arXiv: 1310.2035.
  * [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.
  * [Sim00] Rajiah Simon.  Peres-horodecki separability criterion for continuous variable systems.  Physical Review Letters, 84(12):2726, 2000.
  * [Spe16a] 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.
  * [Spe16b] Florian Speelman.  Position-based quantum cryptography and catalytic computation. PhD thesis, University of Amsterdam, Amsterdam, 2016.  OCLC: 964061686.
  * [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.
  * [VB96] Lieven Vandenberghe and Stephen Boyd.  Semidefinite programming.  SIAM review, 38(1):49–95, 1996.
  * [Wat18] John Watrous.  The Theory of Quantum Information, page 418.  Cambridge University Press, 1 edition, April 2018.

##  Appendix A QPV${}_{\textsf{SWAP}}$

###  A.1 Exponential suppression of attacker success probability

Here we provide the proof of (3.5). Let $N_{\beta}$ the binomial distributed
random variable describing the number of “0” answers of attackers in
$L_{\beta}$. Since
$p_{\beta},p^{\mathsf{AB}}_{\beta}\in\big{[}\frac{1}{2},1\big{)}$, we may
approximate the binomial distribution with a normal distribution
$\mathcal{N}(\mu,\sigma^{2})$ with $\mu=R_{\beta}p$ and
$\sigma^{2}=R_{\beta}p(1-p)$ for
$p\in\\{p_{\beta},p^{\mathsf{AB}}_{\beta}\\}$, respectively. This is valid as
long as $R_{\beta}(1-p)$ is sufficiently large, which we can always achieve by
making $R_{\beta}$ big enough. Then

$\displaystyle\mathbb{P}(\mathsf{acc}_{\beta}|\mathsf{attack})$
$\displaystyle=\mathbb{P}\left(z_{\frac{\alpha}{2}}^{\mathsf{P}}\leq
N_{\beta}\leq z_{1-\frac{\alpha}{2}}^{\mathsf{P}}\right)$
$\displaystyle=F_{N_{\beta}}\left(z_{1-\frac{\alpha}{2}}^{\mathsf{P}}\right)-F_{N_{\beta}}\left(z_{\frac{\alpha}{2}}^{\mathsf{P}}-1\right)$
$\displaystyle\approx\frac{1}{2}\left[1+\operatorname{erf}\left(\frac{z_{1-\frac{\alpha}{2}}^{\mathsf{P}}-\mu_{\beta}^{\mathsf{AB}}}{\sqrt{2}\sigma_{\beta}^{\mathsf{AB}}}\right)\right]-\frac{1}{2}\left[1+\operatorname{erf}\left(\frac{z_{\frac{\alpha}{2}}^{\mathsf{P}}-\mu_{\beta}^{\mathsf{AB}}}{\sqrt{2}\sigma_{\beta}^{\mathsf{AB}}}\right)\right].$

Now for $\mathcal{N}(\mu,\sigma^{2})$ one has
$z_{q}=F^{-1}(q)=\mu+\sqrt{2}\sigma\operatorname{erf}^{-1}(2q-1)$. Replacing
the $z_{q}$ values and defining
$c_{\alpha}\coloneqq\operatorname{erf}^{-1}(1-\alpha)$ as well as
$f_{\beta}^{\mathsf{X}}=\sqrt{2p_{\beta}^{\mathsf{X}}(1-p_{\beta}^{\mathsf{X}})}$
gives

$\displaystyle\mathbb{P}(\mathsf{acc}_{\beta}|\mathsf{attack})\approx\frac{1}{2}\operatorname{erf}\left(\frac{\sqrt{R_{\beta}}\Delta_{\beta}+f_{\beta}^{\mathsf{P}}c_{\alpha}}{f_{\beta}^{\mathsf{AB}}}\right)-\frac{1}{2}\operatorname{erf}\left(\frac{\sqrt{R_{\beta}}\Delta_{\beta}-f_{\beta}^{\mathsf{P}}c_{\alpha}}{f_{\beta}^{\mathsf{AB}}}\right).$

Using that $\operatorname{erf}(x)\approx 1-\frac{e^{-x^{2}}}{\sqrt{\pi}x}$ for
large $x$, we can write

$\displaystyle\mathbb{P}(\mathsf{acc}_{\beta}|\mathsf{attack})\approx\sqrt{\frac{2}{\pi}}f_{\beta}^{\mathsf{AB}}\left[\frac{e^{-\left(\sqrt{R_{\beta}}\Delta_{\beta}-f_{\beta}^{\mathsf{P}}c_{\alpha}\right)^{2}/\left(f_{\beta}^{\mathsf{AB}}\right)^{2}}}{\sqrt{R_{\beta}}\Delta_{\beta}-f_{\beta}^{\mathsf{AB}}c_{\alpha}}-\frac{e^{-\left(\sqrt{R_{\beta}}\Delta_{\beta}+f_{\beta}^{\mathsf{P}}c_{\alpha}\right)^{2}/\left(f_{\beta}^{\mathsf{AB}}\right)^{2}}}{\sqrt{R_{\beta}}\Delta_{\beta}+f_{\beta}^{\mathsf{AB}}c_{\alpha}}\right]$

As $p_{\beta}^{\mathsf{AB}}\neq 0$ and $p_{\beta}^{\mathsf{AB}}\neq 1$, we may
neglect the terms $f_{\beta}^{\mathsf{AB}}c_{\alpha}$ in the denominators
because we can make $R_{\beta}$ sufficiently large. Moreover, leaving out the
second exponential term gives the approximate upper bound

$\displaystyle\mathbb{P}(\mathsf{acc}_{\beta}|\mathsf{attack})\lesssim\frac{\sqrt{2}f_{\beta}^{\mathsf{AB}}}{\sqrt{\pi
R_{\beta}}\Delta_{\beta}}e^{-\left(\sqrt{R_{\beta}}\Delta_{\beta}-f_{\beta}^{\mathsf{P}}c_{\alpha}\right)^{2}/\left(f_{\beta}^{\mathsf{AB}}\right)^{2}}=O\left(\frac{2^{-\Delta_{\beta}^{2}R_{\beta}}}{\Delta_{\beta}\sqrt{R_{\beta}}}\right).$

###  A.2 Relating $p_{\text{succ}}$ to $\lVert\Delta\rVert_{1}$ for
QPV${}_{\textsf{SWAP}}(0,1)$

Relating these two quantities is fairly straigtforward and achieved by one
application of the triangle inequality. Consider

$\displaystyle
p_{\text{succ}}=\frac{1}{2}\frac{\operatorname{Tr}[\Pi_{=}\rho_{=}]}{\eta}+\frac{1}{2}\frac{\operatorname{Tr}[\Pi_{\neq}\rho_{\neq}]}{\eta}\leq
u,$

with $u\leq 3/4$. We want to massage this in order to get $\Delta_{0}$ and
$\Delta_{1}$ expressions into it. Doing so gives

$\displaystyle
1-\frac{\operatorname{Tr}[\Pi_{=}\rho_{=}]}{\eta}+\frac{1}{2}-\frac{\operatorname{Tr}[\Pi_{\neq}\rho_{\neq}]}{\eta}\geq\frac{3}{2}-2u.$

This implies

$\displaystyle\lVert\Delta\rVert_{1}=\bigg{|}1-\frac{\operatorname{Tr}[\Pi_{=}\rho_{=}]}{\eta}\bigg{|}+\bigg{|}\frac{1}{2}-\frac{\operatorname{Tr}[\Pi_{\neq}\rho_{\neq}]}{\eta}\bigg{|}\geq\bigg{|}1-\frac{\operatorname{Tr}[\Pi_{=}\rho_{=}]}{\eta}+\frac{1}{2}-\frac{\operatorname{Tr}[\Pi_{\neq}\rho_{\neq}]}{\eta}\bigg{|}\geq\frac{3}{2}-2u.$

###  A.3 Optimal PPT Measurements for QPV${}_{\textsf{SWAP}}$ Protocol

Here we shall prove the upper bound of the success probability of answering
the protocol correctly for adversaries restricted to PPT operations in
equation (3.11). For simplification we will refer to the equal case as the $0$
case and unequal as the $1$ case. The idea of the proof is to find analytical
feasible solutions to the primal and Dual programs of the SDP. In general a
feasible solution to the primal program defines a lower bound to the
maximization value, while a feasible solution to the dual program defines an
upper bound. This is the property of weak duality which holds for any SDP
[VB96]. In all of our further proofs we find feasible primal values and dual
values that coincide and thus our solutions are optimal and we have strong
duality.

From the density matrices we see that there is no difference between picking
two random equal states or picking two equal states in a random mutually
unbiased basis, see $\rho_{0}$. Similarly picking two random orthogonal states
or picking two orthogonal mutually unbiased basis (MUB) states is equal, see
$\rho_{1}$. These become151515Note that this is a slight change of notation
with respect to the main text, where we used $\rho_{\beta}$ for overlap
$\beta$. Here $\rho_{0}$ denotes the mixed state of sending identical states
and $\rho_{1}$ denotes the one sending orthogonal states.

$\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}{6}\left(\begin{matrix}1&0&0&0\\\ 0&2&-1&0\\\
0&-1&2&0\\\ 0&0&0&1\end{matrix}\right).$

It is useful to note that both density matrices $\rho_{0},\rho_{1}$ are a
mixture of unentangled states and thereby unentangled. Thus by the Peres-
Horodecki separability criterion the partial transpose of $\rho_{0}$ and
$\rho_{1}$ are positive semi-definite [Sim00]. The optimization over all
strategies of the single round protocol is written as follows in an SDP:

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\\}.$

A feasible solution for the primal program is

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

with solution
$\frac{1}{2}\operatorname{Tr}[\Pi_{0}\rho_{0}+\Pi_{1}\rho_{1}]=2/3$. Note that
these measurement projectors correspond to attackers choosing a random MUB to
measure in and returning 0 if the measurement outcomes were equal and 1
otherwise, which is also a single round LOCC strategy. This can be seen from
the fact that

$\displaystyle\frac{1}{3}(\ket{00}\bra{00}+\ket{11}\bra{11}+\ket{++}\bra{++}+\ket{--}\bra{--}+\ket{i^{+}i^{+}}\bra{i^{+}i^{+}}+\ket{i^{-}i^{-}}\bra{i^{-}i^{-}})$
$\displaystyle=\Pi_{0},$
$\displaystyle\frac{1}{3}(\ket{10}\bra{10}+\ket{01}\bra{01}+\ket{-+}\bra{-+}+\ket{+-}\bra{+-}+\ket{i^{-}i^{+}}\bra{i^{-}i^{+}}+\ket{i^{+}i^{-}}\bra{i^{+}i^{-}})$
$\displaystyle=\Pi_{1}.$

A feasible solution to the dual program is:

$\displaystyle Y=\frac{\mathbbm{1}_{4}}{6},$ $\displaystyle Q_{0}=0\succeq 0,$
$\displaystyle
Q_{1}=\frac{\mathbbm{1}_{4}}{6}-\frac{\rho_{1}^{T_{\mathsf{B}}}}{2}=\frac{1}{12}\left(\begin{matrix}1&0&0&1\\\
0&0&0&0\\\ 0&0&0&0\\\
1&0&0&1\end{matrix}\right)=\frac{1}{6}\ket{\Phi^{+}}\bra{\Phi^{+}}\succeq 0.$

Which adhere to the constraints in the Dual Program:

$\displaystyle Y-Q^{T_{\mathsf{B}}}_{0}-\frac{\rho_{0}}{2}$
$\displaystyle=\frac{\mathbbm{1}_{4}}{6}-\frac{\rho_{0}}{2}=\frac{1}{12}\left(\begin{matrix}0&0&0&0\\\
0&1&-1&0\\\ 0&-1&1&0\\\
0&0&0&0\end{matrix}\right)=\frac{1}{6}\ket{\Psi^{-}}\bra{\Psi^{-}}\succeq 0$
$\displaystyle Y-Q^{T_{\mathsf{B}}}_{1}-\frac{\rho_{1}}{2}$
$\displaystyle=\frac{\mathbbm{1}_{4}}{6}-\left(\frac{\mathbbm{1}_{4}}{6}-\frac{\rho_{1}}{2}\right)-\frac{\rho_{1}}{2}=0\succeq
0.$

Since $Y\in\text{Herm}(\mathsf{A}\otimes\mathsf{B})$ and we get a feasible
solution for the dual with value $\operatorname{Tr}[Y]=\frac{2}{3}$. Thus we
have a feasible solution of the primal and dual program that both give the
same value so we conclude that the maximal probability of success for
attackers under the PPT restriction is $2/3$.

###  A.4 Optimal PPT Measurements for QPV${}^{n}_{\textsf{SWAP}}$ Protocol

We shall prove that the optimal probability of succes for attackers in the
$n$-round parallel repetition case is $(2/3)^{n}$. The SDP of the $n$ round
parallel repetition protocol was given as:

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

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

Repeating the strategy of the single round protocol gives a feasible solution
for the primal program with success probability $(2/3)^{n}$. A feasible
solution to the dual problem would yield an upper bound to the problem, but
requires finding a general solution for the matrices $Y,Q_{s}$.

We start again with by setting $Y$ to be the identity matrix with some proper
normalization

$Y=\frac{\mathbbm{1}_{2^{2n}}}{2^{2n}}\left(\frac{2}{3}\right)^{n}=\frac{\mathbbm{1}_{2^{2n}}}{6^{n}},\text{
such that }\operatorname{Tr}[Y]=\left(\frac{2}{3}\right)^{n}.$ (A.1)

We will construct a general feasible solution for $Q_{s}$ for any string
$s\in\\{0,1\\}^{n}$ from $Q_{T(s)}$ where $T(s)$ is the reversed sorted
version of $s$. First we show a general solution for $s=0^{n}$ and $s=1^{n}$
string. Again a solution for the all-0 input case is $Q_{0^{n}}=0\succeq 0$.
The first constraint for $s=0^{n}$ in the dual program of the SDP then reduces
to

$\displaystyle\frac{\mathbbm{1}_{2^{2n}}}{6^{n}}-\frac{\rho_{0}^{\otimes
n}}{2^{n}}.$ (A.2)

Note that the eigenvectors of $\rho_{0}$ are the four Bell states
$\\{\ket{\Phi^{+}},\ket{\Phi^{-}},\ket{\Psi^{+}},\ket{\Psi^{-}}\\}$, with
respective eigenvalues $\\{1/3,1/3,1/3,0\\}$, then the eigenvalues of
$\frac{\rho_{0}^{\otimes n}}{2^{n}}$ are $1/6^{n}$ or $0$. Thus the
eigenvalues of (A.2) are either $0$ or $1/6^{n}$, and since the expression is
Hermitian (A.2) is positive. Similar to the single round protocol we have the
following solution for the $s=1^{n}$ case

$\displaystyle Q_{1^{n}}$
$\displaystyle=\frac{\mathbbm{1}_{2^{2n}}}{6^{n}}-\frac{(\rho_{1}^{T_{\mathsf{B}}})^{\otimes
n}}{2^{n}},$

the eigenvectors of $\rho_{1}^{T_{\mathsf{B}}}$ are again the Bell states,
with respective eigenvalues $\\{0,1/3,1/3,1/3\\}$. The eigenvectors of
$Q_{1^{n}}$ are all the combinations of tensor products of these four Bell
states. If one of these states is the $\ket{\Phi^{+}}$ state the corresponding
eigenvalue of $Q_{1^{n}}$ is $0$, otherwise the corresponding eigenvalue is
$(\frac{1}{6})^{n}$. Since $Q_{1^{n}}$ is Hermitian and has only non-negative
eigenvalues $Q_{1^{n}}\succeq 0$, as desired. The corresponding constraint in
the dual program of the SDP reduces to

$\displaystyle\frac{\mathbbm{1}_{2^{2n}}}{6^{n}}-\left(\frac{\mathbbm{1}_{2^{2n}}}{6^{n}}-\frac{\rho_{1}^{\otimes
n}}{2^{n}}\right)-\frac{\rho_{1}^{\otimes n}}{2^{n}}=0\succeq 0.$

Now suppose we have a valid solution $Q_{s}$ for some $s\in\\{0,1\\}^{n}$,
thus

$Y-Q^{T_{\mathsf{B}}}_{s}-\rho_{s}/2^{n}\succeq 0.$ (A.3)

And to this $n$-round protocol we add an extra round of equal inputs, we will
show that

$\displaystyle Q_{s,0}=Q_{s}\otimes\rho_{0}^{T_{\mathsf{B}}}/2,$ (A.4)

is a valid solution for the $(n+1)$-round SDP. We have already shown in
Appendix A.3 that $\rho_{0}^{T_{\mathsf{B}}}\succeq 0$. Since the tensor
product of positive semi-definite matrices is again positive semi-definite we
have that $Q_{s,0}\succeq 0$. Rewriting the first dual constraint we get

$\displaystyle\frac{\mathbbm{1}_{2^{2n+2}}}{6^{n+1}}-Q_{s,0}^{T_{\mathsf{B}}}-\frac{\rho_{s}\otimes\rho_{0}}{2^{n+1}}$
$\displaystyle=\frac{\mathbbm{1}_{2^{2n+2}}}{6^{n+1}}-Q_{s}^{T_{\mathsf{B}}}\otimes\frac{\rho_{0}}{2}-\frac{\rho_{s}\otimes\rho_{0}}{2^{n+1}}$
$\displaystyle=\frac{\mathbbm{1}_{2^{2n}}}{6^{n}}\otimes\frac{\mathbbm{1}_{4}}{6}-Q_{s}^{T_{\mathsf{B}}}\otimes\frac{\rho_{0}}{2}-\frac{\rho_{s}\otimes\rho_{0}}{2^{n+1}}$
$\displaystyle=\frac{\mathbbm{1}_{2^{2n}}}{6^{n}}\otimes\frac{\rho_{0}+\rho_{1}}{3}-Q_{s}^{T_{\mathsf{B}}}\otimes\frac{\rho_{0}}{2}-\frac{\rho_{s}\otimes\rho_{0}}{2^{n+1}}$
$\displaystyle=\underbrace{\left(\frac{\mathbbm{1}_{2^{2n}}}{6^{n}}-Q_{s}^{T_{\mathsf{B}}}-\frac{\rho_{s}}{2^{n}}\right)\otimes\frac{\rho_{0}}{2}}_{\textbf{A}}+\underbrace{\frac{\mathbbm{1}_{2^{2n}}}{6^{n}}\otimes\left(\frac{2\rho_{1}-\rho_{0}}{6}\right)}_{\textbf{B}}.$

We see that part A is a tensor product of two positive semi-definite matrices
(A.3) and $\rho_{0}/2$, so A is also positive semi-definite. For part B note
that the eigenvectors of $\frac{2\rho_{1}-\rho_{0}}{6}$ are again the Bell
states with respective eigenvalues $\\{0,0,0,1/6\\}$, so part B is positive
semi-definite. Since sums of positive semi-definite matrices are positive
semi-definite the whole constraint is positive semi-definite. Since for any
amount of rounds $n$ we have a feasible solution for the $s=1^{n}$ case, by
induction, we can repeat the previous steps to get a solution for any reversed
sorted string $1^{n}0^{k},k\in\mathbb{N}$, namely

$\displaystyle
Q_{1^{n}0^{k}}=Q_{1^{n}}\otimes\frac{(\rho_{0}^{T_{\mathsf{B}}})^{\otimes
k}}{2^{k}}.$ (A.5)

Now take some string $s\in\\{0,1\\}^{n}$, and let $P_{s}$ be a unitary
consisting only of 2-qubit SWAP operations that reverse sorts the $n$-rounds,
such that $P_{s}\rho_{s}P_{s}^{\dagger}=\rho_{T(s)}$, and
$P^{\dagger}_{s}=P_{s}$.

We can now write down the general solution of $Q_{s}$ using the corresponding
map $P_{s}$ applied to the sorted version. Let
$Q_{s}=(P_{s}Q_{T(s)}^{T_{\mathsf{B}}}P_{s})^{T_{\mathsf{B}}}$, using the fact
that P is a unitary matrix we then get for the corresponding constraint in the
dual SDP:

$\displaystyle Y-Q^{T_{\mathsf{B}}}_{s}-\rho_{s}/2^{n}\succeq 0$
$\displaystyle\Leftrightarrow
P_{s}(Y-Q^{T_{\mathsf{B}}}_{s}-\rho_{s}/2^{n})P_{s}\succeq 0$
$\displaystyle\Leftrightarrow
Y-P_{s}Q^{T_{\mathsf{B}}}_{s}P_{s}-\rho_{T(s)}/2^{n}\succeq 0$
$\displaystyle\Leftrightarrow
Y-P_{s}((P_{s}Q^{T_{\mathsf{B}}}_{T(s)}P_{s})^{T_{\mathsf{B}}})^{T_{\mathsf{B}}}P_{s}-\rho_{T(s)}/2^{n}\succeq
0$ $\displaystyle\Leftrightarrow
Y-P_{s}(P_{s}Q^{T_{\mathsf{B}}}_{T(s)}P_{s})P_{s}-\rho_{T(s)}/2^{n}\succeq 0$
$\displaystyle\Leftrightarrow
Y-Q^{T_{\mathsf{B}}}_{T(s)}-\rho_{T(s)}/2^{n}\succeq 0.$

Where the last expression is positive semi-definite by (A.5). Thus we get that
the first constraint in the dual program of the $n$-round SDP for any string
$s$ is positive semi-definite for any combination of rounds.

The final step is to show that
$Q_{s}=(P_{s}Q_{T(s)}^{T_{\mathsf{B}}}P_{s})^{T_{\mathsf{B}}}$ is positive.
Note that $P_{s}$ permutes both registers held by $\mathsf{A}$ and
$\mathsf{B}$, respectively, of the states together, since it consists only of
$2$-qubits SWAP operations. The action is thus independent of the partial
transpose on the second party $\mathsf{B}$. We therefore have
$Q_{s}=P_{s}Q_{T(s)}P_{s}$. Now, since $P_{s}$ is unitary and $Q_{T(s)}$ is
positive semi-definite we have that $Q_{s}$ is positive semi-definite.

We have shown that all the constraints in the dual program of the $n$-round
SDP are satisfied by our constructed $Q_{s}$ matrices, thus we have a feasible
solution to the dual program with value $\operatorname{Tr}[Y]=(2/3)^{n}$,
which is equal to the primal value and is attainable by a LOCC strategy. This
shows that the best attacking strategy for adversaries restricted to LOCC
operations playing $n$ rounds in parallel is to simply apply the single round
strategy $n$ times in parallel.

###  A.5 Optimal PPT Measurements for loss-tolerant
$\text{QPV}^{n}_{\textsf{SWAP}}$ Protocol

We shall now modify the solution to the parallel repetition case in Appendix
A.4 to give a solution to the maximization of conditional success probability
under LOCC restrictions. The SDP for the lossy $n$ round parallel repetition
protocol in which attackers either answer on all rounds or on none is given
as:

Primal Program maximize:
$\displaystyle\frac{1}{2^{n}\eta}\sum_{s\in\\{0,1\\}^{n}}\operatorname{Tr}[\tilde{\Pi}_{s}\rho_{s}]$
subject to:
$\displaystyle\left(\sum_{s\in\\{0,1\\}^{n}}\tilde{\Pi}_{s}\right)+\tilde{\Pi}_{\varnothing}=\mathbbm{1}_{2^{2n}}$
$\displaystyle\operatorname{Tr}[\tilde{\Pi}_{\varnothing}\rho_{s}]=1-\eta,\ \
\ s\in\\{0,1\\}^{n}$
$\displaystyle\tilde{\Pi}_{s}\in\text{PPT}(\mathsf{A}:\mathsf{B}),\ \ \
s\in\\{0,1\\}^{n}\cup\varnothing$

Dual Program minimize:
$\displaystyle\frac{\operatorname{Tr}[\tilde{Y}]-(1-\eta)\gamma}{\eta}$
subject to:
$\displaystyle\tilde{Y}-\tilde{Q}^{T_{\mathsf{B}}}_{s}-\rho_{s}/2^{n}\succeq
0,\ \ \ s\in\\{0,1\\}^{n}$ $\displaystyle
2^{2n}(\tilde{Y}-\tilde{Q}^{T_{\mathsf{B}}}_{\varnothing})-\gamma\mathbbm{1}_{2^{2n}}\succeq
0$ $\displaystyle\tilde{Y}\in\text{Herm}(\mathsf{A}\otimes\mathsf{B})$
$\displaystyle\tilde{Q}_{s}\in\text{Pos}(\mathsf{A}\otimes\mathsf{B}),\ \ \
s\in\\{0,1\\}^{n}\cup\varnothing$ $\displaystyle\gamma\in\mathbb{R}.$

We suspect our protocol is loss-tolerant, thus we want the solution to be
independent of $\eta$. It turns out multiplying the POVM elements by $\eta$
and picking $\tilde{\Pi}_{\varnothing}$ accordingly, i.e.
$\tilde{\Pi}_{s}=\eta\Pi_{s}$ for every $s\in\\{0,1\\}^{n}$ and
$\tilde{\Pi}_{\varnothing}=(1-\eta)\mathbbm{1}_{2^{2n}}$ gives a feasible
solution for the primal program with solution $(2/3)^{n}$. Note that this
strategy corresponds to only playing a random fraction $\eta$ of the
$n$-rounds and declaring a loss on the rest, which corresponds to the notion
of loss-tolerance.

For the dual program, note that if we pick

$\displaystyle\tilde{Y}=\frac{\mathbbm{1}_{2^{2n}}}{6^{n}},$
$\displaystyle\tilde{Q_{s}}=Q_{s}$ $\displaystyle\tilde{Q}_{\varnothing}=0,$
$\displaystyle\gamma=(2/3)^{n},$ (A.6)

then trivially
$Y\in\text{Herm}(\mathsf{A}\otimes\mathsf{B}),\tilde{Q}_{s}\in\text{Pos}(\mathsf{A}\otimes\mathsf{B}),\gamma\in\mathbb{R}$
and the first condition remains satisfied since we have not changed $Y,Q_{s}$
in Appendix A.4. The second constraint becomes

$\displaystyle
2^{2n}(\tilde{Y}-\tilde{Q}^{T_{\mathsf{B}}}_{\varnothing})-\gamma\mathbbm{1}_{2^{2n}}$
$\displaystyle=\mathbbm{1}_{2^{2n}}\frac{2^{n}}{3^{n}}-(2/3)^{n}\mathbbm{1}_{2^{2n}}=0\succeq
0.$ (A.7)

So all constraints in the dual are satisfied. We thus get a lower bound of

$\displaystyle\frac{\operatorname{Tr}[\tilde{Y}]-(1-\eta)\gamma}{\eta}=\frac{(2/3)^{n}-(1-\eta)(2/3)^{n}}{\eta}=\frac{\eta(2/3)^{n}}{\eta}=(2/3)^{n}.$
(A.8)

Thus we finally have $\mathbb{P}_{guess}^{max}(n,\eta)=(2/3)^{n}$. So the
$n$-round protocol is also loss tolerant for any $n$, as we see that the
probability of being correct conditioned on answering is independent of the
loss parameter $\eta$.

###  A.6 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 the same as in Appendix A.3 where only the density matrices
are now different. Here we write $\rho_{0}$ for $\rho_{\text{sym}}$ and
$\rho_{1}$ for $\rho_{\text{antisym}}$:

$\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 are met, and we get a lower
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}.$

We conclude that 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.