# Time-Constrained Local Quantum State Discrimination

Ian George<EMAIL_ADDRESS>Department of Electrical and Computer
Engineering, Coordinated Science Laboratory, University of Illinois at Urbana-
Champaign, Urbana, IL 61801, USA  Rene Allerstorfer<EMAIL_ADDRESS>QuSoft, CWI Amsterdam, The Netherlands  Philip Verduyn Lunel<EMAIL_ADDRESS>QuSoft, CWI Amsterdam, The Netherlands  Eric Chitambar<EMAIL_ADDRESS>Department of Electrical and Computer Engineering, Coordinated Science
Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL 61801, USA

###### Abstract

Inspired by protocols in relativistic quantum cryptography, we investigate
quantum state discrimination using local operations and simultaneous classical
or quantum communication (LOSCC/LOSQC). When one system is a qubit, we
identify the structure of product ensembles that can be perfectly
discriminated by LOSCC. We show these conditions fail for LOSQC and provide
the smallest-sized example in which a gap between LOSCC and LOSQC exists.
Finally, we prove an uncertainty relation that yields error bounds in LOSQC
state discrimination and noise thresholds for quantum position verification.

††preprint: APS/123-QED

##  I Introduction

Following Landauer [1], it has become a central tenet of quantum information
theory that information is physical— how information is encoded into a
physical system decides the limitations of information processing. No subfield
takes this viewpoint more seriously than (relativistic) quantum cryptography,
which uses the limitations on information processing imposed by physical laws
to construct secure cryptographic protocols. In particular, relativistic
quantum cryptography uses the assumption of no superluminal communication in
relativity along with the standard quantum mechanical formalism to determine
security.

Perhaps the most well-known relativistic quantum cryptographic protocol is
quantum position verification (QPV) [2, 3]. Abstractly, QPV combines the no-
cloning of quantum states [4] with the impossibility of superluminal
communication to make the non-local decoding of some classical information
difficult in a time-constrained environment. As depicted in Fig. 1, one class
of QPV protocols involves two verifiers, $\mathsf{V}_{A}$ and
$\mathsf{V}_{B}$, who attempt to certify that some agent is present at a
particular spacetime point $\mathbf{x}$. Classical information $k$ is encoded
into a family of bipartite orthogonal quantum states
$\\{\rho_{k}^{AB}\\}_{k}$, and with probability $p(k)$ the state
$\rho^{AB}_{k}$ is sent to location $\mathbf{x}$ at time $t_{0}$, system $A$
coming from $\mathsf{V}_{A}$ and system $B$ from $\mathsf{V}_{B}$. If there is
an agent at $\mathbf{x}$, then systems $A$ and $B$ can be jointly measured
allowing the data $k$ to be perfectly recovered. The agent can immediately
forward this data along to the verifiers, and they accept the position
$\mathbf{x}$ if they receive the correct value at time $t_{1}$, where $\Delta
t=t_{1}-t_{0}$ is the time it takes light to travel from $\mathsf{V}_{A}$ to
$\mathsf{V}_{B}$.

In the dishonest scenario, there is no acting agent at $\mathbf{x}$. Instead,
adversaries sit at other points in spacetime, and they try to spoof their
location by correctly identifying the state $\rho_{k}^{AB}$ and returning the
value $k$ within time $\Delta t$. The time constraints limit adversaries to
distributed attacks that use only one round of simultaneous communication
between them (see Fig. 1). What makes this task non-trivial is the no-cloning
theorem of quantum states, which prevents the adversaries from simply copying
their received part of $\rho_{k}^{AB}$ and sending it along to the other party
so that each of them have a copy of $\rho_{k}^{AB}$. Indeed, there are
ensembles of states $\\{\rho_{k}^{AB}\\}_{k}$ that cannot be perfectly
discriminated using local measurements with simultaneous communication [2, 3],
and we will identify even more within this paper. Such ensembles therefore
appear well-suited for use in QPV.

$t$$x$$k$$\rho^{A}_{k}$$\mathsf{V_{A}}$$k$$\rho^{B}_{k}$$\mathsf{V_{B}}$$\mathbf{x}$$\mathsf{A}$$\mathsf{B}$$t_{0}$$t_{1}$
Figure 1: Spacetime diagram of the LOSQC setting. The verifiers
$\mathsf{V_{A}}$, $\mathsf{V_{B}}$ simultaneously send $\rho^{A}_{k}$,
$\rho^{B}_{k}$ drawn from an ensemble $\\{p(k),\rho^{AB}_{k}\\}_{k}$ at time
$t_{0}$. The honest prover would be at the blue dot, the spacetime point
$\mathbf{x}$, so the whole quantum system would be jointly measurable. On the
other hand, the dishonest provers, $\mathsf{A}$ and $\mathsf{B}$, would have
to distinguish the index $k$ using only local operations and one round of
simultaneous communication. Single lines represent quantum information, double
lines classical information.

The unfortunate reality, however, is that if the adversaries have enough pre-
shared entanglement, then their ability to distinguish the states
$\\{\rho_{k}^{AB}\\}_{k}$ in time window $\Delta t$ becomes much more powerful
[3]. In fact, by performing port-based teleportation (PBT) [5, 6, 7, 8], any
nonlocal quantum operation can be implemented using one round of simultaneous
communication [3, 9]. As a result, QPV is a cryptographic task that cannot be
unconditionally secure (unlike quantum key distribution). However, the best
known QPV attacks (including PBT) require an exponential amount of
entanglement, which means that one can make the resource requirements for the
adversaries seemingly much more demanding compared to the honest prover’s. For
these reasons, much of the research on QPV now focuses on the construction of
QPV protocols that might require a great deal of entanglement to break [10,
11, 12, 13, 14]. Yet, the basic communication model and operational
capabilities when the adversaries do not share any entanglement are still not
well understood. This places an important gap in the study of QPV and
relativistic quantum cryptography in general. In this work, we make
substantial progress on closing this gap, thereby clarifying further the
interplay between cryptography, quantum communication, and locality.

Our primary objective is to identify fundamental limitations in the task of
time-constrained state discrimination when either classical or quantum
communication is employed. More precisely, we suppose that the two adversaries
in the above scenario (henceforth called Alice and Bob) are allowed to perform
local quantum operations and assisted by simultaneous communication that
exchanges either classical or quantum messages. We denote these two models by
LOSCC and LOSQC, respectively. The problem of LOSQC state discrimination has
only been previously studied for entangled states [15]. Outside this setting,
its advantage over LOSCC is unclear. To focus on the role of communication, we
primarily restrict our analysis to families of globally orthogonal product
(GOP) states, $\\{\ket{a_{k}}^{A}\ket{b_{k}}\\}^{B}$, since then any quantum
correlation in the discrimination protocol must come through the communication
and not the states themselves.

As a summary of our findings, we first consider the problem of perfect state
discrimination (i.e. zero error) via LOSCC and LOSQC. We exactly characterize
the GOP ensembles that are LOSCC discriminable in
$\mathbb{C}^{2}\otimes\mathbb{C}^{d}$ systems and further show that any set of
three GOP states is LOSCC discriminable. We explicitly construct a GOP that
can be perfectly distinguished by LOSQC but not LOSCC and show that this is
the smallest ensemble in which such a separation can exist. By iterating on
this example, we demonstrate an arbitrary gap between the power of LOSCC and
LOSQC for state discrimination. While understanding the limitations for
perfect state discrimination is fundamentally important, for practical
cryptographic applications one must determine lower bounds on the error of the
adversaries’ best strategy. In the second part of this work we derive an
uncertainty relation for discriminating pairs of bipartite states that are not
locally orthogonal, which we use to determine non-trivial lower bounds on the
minimal error guessing probability using LOSQC. This is useful for QPV, but it
should also be relevant for establishing information-theoretic security of
other relativistic quantum cryptographic protocols.

Perfect LOSCC and LOSQC State Discrimination –  Unlike traditional local
operations and classical communication (LOCC), the maps generated by both
LOSCC and LOSQC maps have a relatively simple description. For LOSQC, Alice
(resp. Bob) performs a local isometry $V:A\to A_{1}B_{2}$ (resp. $W:B\to
B_{1}A_{2}$) and sends system $B_{2}$ to Bob (resp. $A_{2}$ to Alice).
Alternatively we can say that Alice receives the outputs of quantum channels
$\mathcal{E}(\cdot)=\tr_{B_{2}}V(\cdot)V^{\dagger}$ and
$\mathcal{F}^{c}(\cdot)=\tr_{B_{1}}W(\cdot)W^{\dagger}$, while Bob receives
the outputs of their complements
$\mathcal{E}^{c}(\cdot)=\tr_{A_{1}}V(\cdot)V^{\dagger}$ and
$\mathcal{F}(\cdot)=\tr_{A_{2}}W(\cdot)W^{\dagger}$. For LOSCC, the local
isometries are replaced by local instruments $(\mathcal{A}_{x}^{A\to A})_{x}$
and $(\mathcal{B}_{y}^{B\to B})_{y}$, which are collections of completely
positive (CP) maps for which $\mathcal{A}_{x}\otimes\mathcal{B}_{y}$ describes
the joint evolution when Alice broadcasts classical message $x$ and Bob
broadcasts classical message $y$. Without loss of generality we can assume
that these are “fine-grained” instruments having the form
$\mathcal{A}_{x}(\cdot)=A_{x}(\cdot)A_{x}^{\dagger}$ and
$\mathcal{B}_{y}(\cdot)=B_{y}(\cdot)B_{y}^{\dagger}$, since the coarse-
graining of more general maps can be always be delayed until the second round
in which the local state discrimination measurement is performed. Up to
normalization, the local instrument transforms $\rho^{AB}\mapsto A_{x}\otimes
B_{y}(\rho^{AB})A_{x}^{\dagger}\otimes B_{y}^{\dagger}$ given classical
messages $(x,y)$.

The conditions for perfect state discrimination using either LOSCC and LOSQC
are intuitive to understand. Since no interactive communication is allowed,
Alice and Bob must be able to “distribute the orthogonality” of their states.
That is, the communication must transform the initial states
$\\{\rho_{k}^{AB}\\}$ in such a way that afterward the reduced states are
pairwise orthogonal for both Alice and Bob. For LOSQC, this means that

$\displaystyle\Tr[(\mathcal{E}\otimes\mathcal{F}^{c})(\rho_{k}^{AB})(\mathcal{E}\otimes\mathcal{F}^{c})(\rho_{k^{\prime}}^{AB})]$
$\displaystyle=0$
$\displaystyle\Tr[(\mathcal{E}^{c}\otimes\mathcal{F})(\rho_{k}^{AB})(\mathcal{E}^{c}\otimes\mathcal{F})(\rho_{k^{\prime}}^{AB})]$
$\displaystyle=0$

for all $k,k^{\prime}\neq k$. For LOSCC discrimination, the reduced states of
$A_{x}\otimes B_{y}(\rho_{k}^{AB})A_{x}^{\dagger}\otimes B_{y}^{\dagger}$ must
be pairwise orthogonal for $k\not=k^{\prime}$ and every pair $(x,y)$. By
defining the positive operator-valued measure (POVM) operators
$M_{x}:=A_{x}^{\dagger}A_{x}$ and $N_{y}:=B_{y}^{\dagger}B_{y}$, we
immediately obtain the following.

######  Proposition 1.

The states $\\{\rho^{AB}_{k}\\}$ can be perfectly distinguished by LOSCC if
and only if there exist POVMs $\\{M_{x}^{A}\\}_{x}$ and $\\{N_{y}^{B}\\}_{y}$
such that

$\displaystyle\Tr[\Tr_{A}[(M_{x}^{A}\otimes
N_{y}^{B})\rho^{AB}_{k}]\Tr_{A}[(M_{x}^{A}\otimes
N_{y}^{B})\rho^{AB}_{k^{\prime}}]]$ $\displaystyle=0$
$\displaystyle\Tr[\Tr_{B}[(M_{x}^{A}\otimes
N_{y}^{B})\rho^{AB}_{k}]\Tr_{B}[(M_{x}^{A}\otimes
N_{y}^{B})\rho^{AB}_{k^{\prime}}]]$ $\displaystyle=0\ .$

for all $x,y,k\neq k^{\prime}$.

We now apply Proposition 1 to the case of GOP ensembles
$\\{\ket{a_{k}}^{A}\ket{b_{k}}^{B}\\}_{k}$. Ideally one would like to have
structural conditions for when such an ensemble is perfectly distinguishable
by LOSCC. While it remains a challenging open problem to find a general
solution, we are able to obtain a solution when one of the systems is a qubit.

######  Theorem 1.

Let $A=\mathbb{C}^{2}$, $B=\mathbb{C}^{d}$. Then a GOP ensemble
$\\{\ket{a_{k}}^{A}\ket{b_{k}}^{B}\\}_{k}$ is perfectly distinguishable by
LOSCC iff (up to a local basis change) its states have the form

$\displaystyle\ket{g_{i}}^{A}\ket{i}^{B}$ $\displaystyle i$
$\displaystyle\in\\{0,...,L-1\\}$ $\displaystyle\ket{0}^{A}\ket{L+2j}^{B}$
$\displaystyle j$ $\displaystyle\in\left\\{0,...,m\right\\}$
$\displaystyle\ket{1}^{A}\ket{\varphi_{L+2j}}^{B}$ $\displaystyle j$
$\displaystyle\in\left\\{0,...,m\right\\}\ $

for some $0\leq L\leq d$, where
$\ket{\varphi_{L+2j}}=\alpha_{j}\ket{L+2j}+\beta_{j}\ket{L+2j+1}$ and the
$\ket{g_{i}}$ are arbitrary.

While the full proof is given in the Supplemental Material, it is easy to see
what is going on in the above theorem. Bob can perfectly distinguish the first
$L$ himself without disturbing the other $2(m+1)$ states. For the later
states, Bob can eliminate all but two with a single measurement by projecting
onto the two-dimensional subspaces spanned by $\\{\ket{L+2j},\ket{L+2j+1}\\}$.
Alice’s measurement in the computational basis then successfully distinguishes
between $\ket{L+2j}$ and $\ket{\varphi_{L+2j}}$. The more lengthy argument
involves proving that all LOSCC distinguishable ensembles have this form.

Below we will see that Theorem 1 does not apply for perfect discrimination by
LOSQC. But before exploring this separation, we establish special cases in
which LOSCC and LOSQC are equally powerful for product state discrimination.
Any GOP ensemble consisting of just two states is always locally
distinguishable by one of the parties due to the local orthogonality. A much
less trivial case are GOP ensembles with three states. While these cannot be
locally distinguished in general, we can show that it is possible by LOSCC.

######  Lemma 1.

Any bipartite GOP ensemble of three states is perfectly distinguishable by
LOSCC.

Lemma 1 implies that LOSCC and LOSQC are equally powerful for distinguishing
GOP ensembles with three states, regardless of the dimensions. As a corollary
of Theorem 1 and Proposition 2 below, this conclusion can be extended for two-
qubit ensembles.

######  Corollary 1.

Any GOP ensemble in $\mathbb{C}^{2}\otimes\mathbb{C}^{2}$ can be perfectly
distinguished by LOSQC if and only if it is a tensor product basis (and hence
also LOSCC distinguishable), i.e. of the form

$\\{\ket{0}\ket{0},\;\;\ket{0}\ket{1},\;\;\ket{1}\ket{0},\;\;\ket{1}\ket{1}\\}.$

Separating LOSCC and LOSQC –  It was proven in [15] that LOSQC can be more
powerful than LOSCC for discriminating certain ensembles of entangled states.
However, this might not be overly surprising given that entangled states
themselves require quantum communication to build. In contrast, here we prove
that such a separation exists for GOP ensembles.

######  Theorem 2.

The GOP ensemble

$\displaystyle\\{\ket{0}\ket{0+1},\;\ket{0}\ket{0-1},\;\ket{1}\ket{0+2},\;\ket{1}\ket{0-2}\\}$
(3)

is perfectly distinguishable by LOSQC but not LOSCC, where $\ket{i\pm
j}:=\frac{1}{\sqrt{2}}(\ket{i}+\ket{j})$.

######  Remark.

By Lemma 1 and Corollary 5, this is the smallest type of GOP ensemble that can
possibly separate LOSCC and LOSQC.

While a full proof of Theorem 2 is provided in the Supplemental Material, the
basic point is that Bob must find a POVM that always perfectly discriminates
$\\{\ket{0\pm 1}\\}$ and $\\{\ket{0\pm 2}\\}$ since Alice cannot determine
those states locally. However, due to the non-orthogonality, no such POVM
exists. On the other hand, there is an isometry such that

$\displaystyle V\ket{0+1}=\ket{0}^{\otimes 2}\quad V\ket{0-1}=\ket{1}^{\otimes
2}$ $\displaystyle\hskip 22.76219ptV\ket{0\pm 2}=\ket{0\pm 1}^{\otimes 2}\ ,$

which means that with quantum communication from Bob to Alice, they both can
locally determine the state.

This isometry $V$ is realizing a weak form of cloning. While the cloning of
non-orthogonal states is impossible in quantum mechanics [4], here we are
cloning classical information that is encoded in non-orthogonal states. Any
example of a separation between LOSQC and LOSCC for discriminating a GOP
ensemble will ultimately be exploiting some effect like this.

Theorem 2 can be amplified by an iterative direct sum construction. Namely, we
can take $k$ copies of the ensemble in Eq. (3) and embed them in $k$ disjoint
global subspaces. From Theorem 2, all $4k$ states can be perfectly
discriminated by LOSQC. However, LOSCC can only discriminate $3k$ of these
states since identifying more would imply perfect discrimination in one of the
subspaces, contradicting Theorem 2. Hence, we conclude the following.

######  Corollary 2 (Arbitrary Gap in Discriminating Power of LOSQC and LOSCC
for GOP Ensembles).

For any integer $k$, there exists an ensemble perfectly distinguishable by
LOSQC but not perfectly distinguishable by LOSCC unless $k$ states are
removed.

Constructing LOSQC discriminable ensembles from secret sharing schemes – We
close our discussion on perfect state discrimination by presenting a recipe
for building LOSQC distinguishable ensembles, which we feel might be of
independent interest. The key observation is that perfect LOSQC discrimination
can be viewed as ‘undoing’ two secret sharing schemes of the same classical
secret $k$ (see Fig. 2). This is formalized in the following construction,
with a proof given in the Supplemental Material.

######  Theorem 3.

Consider two secret sharing schemes $k\mapsto\sigma_{k}^{A_{1}B_{1}}$ and
$k\mapsto\tau_{k}^{A_{2}B_{2}}$ such that the encodings reveal no local
information about $k$. Then
$\\{\sigma_{k}^{A_{1}B_{1}}\otimes\rho_{k}^{A_{2}B_{2}}\\}$ is LOSQC
discriminable but not locally discriminable.

$t$$t$$\mathcal{M}_{1}$$\mathcal{M}_{2}$$k$$k$$\mathcal{E}_{1}$$\mathcal{E}_{2}$$k$$k$(a)
LOSQC(b) Secret Sharing Figure 2: Depiction of perfect LOSQC as secret sharing
in reverse. The $\mathcal{M}_{i}$ are the decoding measurements,
$\mathcal{E}_{i}$ are the secret sharing scheme channels.

Error bounds for product state discrimination under LOSQC – We have now
established a stronger understanding of what limits state discrimination with
LOSCC for GOP ensembles and how LOSQC can overcome this. However, in QPV, even
if the adversaries have no access to further resources, we may choose to
assume they may use unbounded quantum communication. In this case, we need
error bounds on how well the input ensemble can be perfectly discriminated
with LOSQC, i.e. we need to understand the limitations of LOSQC better.

The security proof for the original QPV protocol proof relied upon a specific
entropic uncertainty relation [3]. Later, a stronger security proof was
established using an operator inequality [16]. However, in both cases, the
proof techniques apply only to the specific BB84 QPV protocol. Instead, here
we derive an uncertainty relation for general LOSQC state discrimination,
which can then be applied to a large class of QPV protocols.

The intuition of the uncertainty relation is as follows. Suppose
$\ket{\gamma_{0}}^{AB}$ and $\ket{\gamma_{1}}^{AB}$ are two entangled states
which Alice can distinguish with high probability by just viewing subsystem
$A$. This requires the reduced density matrices $\gamma_{0}^{A}$ and
$\gamma_{1}^{A}$ to be nearly orthogonal. Consequently, tracing out Alice in
any superposition of $\ket{\gamma_{0}}^{AB}$ and $\ket{\gamma_{1}}^{AB}$ will
effectively destroy any relative phase between these states, thereby making it
difficult for Bob to distinguish between superposition states. Our uncertainty
relation captures this tradeoff. It is stated in terms of the fidelity
$F(\rho,\sigma)=\|\sqrt{\rho}\sqrt{\sigma}\|_{1}$ and trace distance
$D_{\text{tr}}(\rho,\sigma)=\tfrac{1}{2}\|\rho-\sigma\|_{1}$ of hermitian
operators [17].

######  Proposition 2 (Uncertainty Relation).

For possibly unnormalized vectors $\ket{\gamma_{0}}^{AB}$ and
$\ket{\gamma_{1}}^{AB}$, if
$\ket{\gamma_{\theta}}^{AB}=\cos(\theta/2)\ket{\gamma_{0}}^{AB}+e^{i\phi}\sin(\theta/2)\ket{\gamma_{1}}^{AB}$
and
$\ket{\gamma_{\omega}}^{AB}=\cos(\omega/2)\ket{\gamma_{0}}^{AB}+e^{i\phi^{\prime}}\sin(\omega/2)\ket{\gamma_{1}}^{AB}$,
then

$\displaystyle
D_{\text{tr}}(\gamma_{\theta}^{B},\gamma_{\omega}^{B})\leq|z_{1}|F(\gamma_{0}^{A},\gamma_{1}^{A})+|z_{2}|D_{\text{tr}}(\gamma_{0}^{B},\gamma_{1}^{B}),$
(4)

where
$z_{1}=\frac{1}{2}(\sin(\theta)e^{-i\phi}-\sin(\omega)e^{-i\phi^{\prime}})$
and $z_{2}=\frac{1}{2}(\cos(\theta)-\cos(\omega))$.

To appreciate the utility of Proposition 2, consider the case when
$\theta=\omega$ and $\phi^{\prime}=\pi+\phi$ so that Eq. (4) reads

$D_{\text{tr}}(\gamma_{\theta}^{B},\gamma_{\omega}^{B})\leq\sin(\theta)F(\gamma_{0}^{A},\gamma_{1}^{A}).$
(5)

High distinguishability of $\ket{\gamma_{0}}^{AB}$ and $\ket{\gamma_{1}}^{AB}$
for Alice (meaning that $F(\gamma_{0}^{A},\gamma_{1}^{A})\approx 0$) then
implies low distinguishability of $\ket{\gamma_{\theta}}^{AB}$ and
$\ket{\gamma_{\omega}}^{AB}$ for Bob (since
$D_{\text{tr}}(\gamma_{\theta}^{B},\gamma_{\omega}^{B})\approx 0$).
Consequently this limits how well Bob can “distribute the orthogonality” of
pairs of states through an isometry that splits the quantum information into
two parts, i.e. $\ket{b_{\lambda}}^{B}\mapsto
W\ket{b_{\lambda}}=\ket{\gamma_{\lambda}}^{A_{2}B_{1}}$ (for
$\lambda\in\\{0,1,\theta,\omega\\}$), as required in an LOSQC protocol.

The following theorem provides a more precise application of this idea.

######  Theorem 4.

Consider any ensemble containing four states of the form

$\displaystyle\ket{\psi_{0}}^{AB}$
$\displaystyle=\ket{a_{0}}^{A}\ket{b_{0}}^{B}$ (6)
$\displaystyle\ket{\psi_{1}}^{AB}$
$\displaystyle=\ket{a_{1}}^{A}\ket{b_{1}}^{B}$
$\displaystyle\ket{\psi_{2}}^{AB}$
$\displaystyle=\ket{a_{2}}^{A}(\cos(\theta/2)\ket{b_{0}}+\sin(\theta/2)e^{i\phi}\ket{b_{1}})^{B}$
$\displaystyle\ket{\psi_{3}}^{AB}$
$\displaystyle=\ket{a_{3}}^{A}(\cos(\omega/2)\ket{b_{0}}+\sin(\omega/2)e^{i\phi^{\prime}}\ket{b_{1}})^{B},$

with $\bra{a_{0}}\ket{a_{1}}>0$. Suppose Alice and Bob can identify each state
with at least probability $1-\varepsilon$ using some LOSQC protocol; i.e.
given state $\ket{\psi_{k}}^{AB}$ they both guess $k$ with probability at
least $1-\varepsilon$. Then

$\displaystyle 1<\frac{2|z_{1}|\sqrt{\varepsilon(1-\varepsilon)}}{|\langle
a_{0}|a_{1}\rangle|^{2}}$ $\displaystyle+|z_{2}|\sqrt{1-|\langle
b_{0}|b_{1}\rangle|^{2}}$ $\displaystyle+\sqrt{1-|\langle
a_{2}|a_{3}\rangle|^{2}}+2\varepsilon,$ (7)

where $z_{1}$ and $z_{2}$ are defined in Proposition 2.

Theorem 4 can be used to bound the minimum error guessing probability for many
well-known ensembles, including those that are not necessarily GOP ensembles.
We provide two examples here.

Example: An unextendible product basis (UPB). Consider the tripartite UPB
known as Shifts [18]. Combining two of the parties yields the bipartite
ensemble

$\displaystyle\ket{\psi_{0}}$ $\displaystyle=\ket{00}\ket{0},$
$\displaystyle\ket{\psi_{1}}$ $\displaystyle=\ket{+-}\ket{1},$
$\displaystyle\ket{\psi_{2}}$ $\displaystyle=\ket{-1}\ket{+},$
$\displaystyle\ket{\psi_{3}}$ $\displaystyle=\ket{1+}\ket{-}.$ (8)

If one of these is chosen with uniform probability and distributed to Alice
and Bob, their smallest possible guessing error $\varepsilon$ using LOSQC
satisfies $\varepsilon>5.52\times 10^{-4}$. Clearly this also provides a lower
bound on the tripartite error probability for Shifts under LOSQC.

Example: The “misaligned” BB84 states 111These should not be confused with the
rotated BB84 states [23], which would have the final state be
$\ket{1}(\sin(\tau)\ket{0}-\cos(\tau)\ket{1})$.. Consider the states

$\displaystyle\ket{\psi_{0}}$ $\displaystyle=\ket{0}\ket{0},$
$\displaystyle\ket{\psi_{2}}$
$\displaystyle=\ket{1}(\cos(\tau/2)\ket{0}+\sin(\tau/2)\ket{1})$
$\displaystyle\ket{\psi_{1}}$ $\displaystyle=\ket{0}\ket{1},$
$\displaystyle\ket{\psi_{3}}$
$\displaystyle=\ket{1}(\cos(\tau/2)\ket{0}-\sin(\tau/2)\ket{1})\ ,$

If one of these is chosen with uniform probability and distributed to Alice
and Bob, their smallest possible guessing error $\epsilon(\tau)$ using LOSQC
is lower bounded as

$\varepsilon(\tau)\geq\frac{1}{4}\left[\frac{1}{2}+\frac{\sqrt{7-8\cos(2\tau)+\cos(4\tau)}}{\sqrt{2}(\cos(2\tau)-3)}\right]\
.$

In the Supplemental Material, we also use Theorem 2 to lower bound the LOSQC
error probability for general two-qubit GOP ensembles.

Conclusions – Motivated by time-sensitive cryptographic protocols like QPV, we
have investigated quantum state discrimination using local operations and
simultaneous classical or quantum communication (LOSCC/LOSQC). LOSQC has been
found to be strictly more powerful than LOSCC for the task of product state
discrimination. The problem of discriminating product state ensembles has a
long history in quantum information science [20], and it has inspired ground-
breaking concepts such as teleportation [21] and nonlocality without
entanglement [22]. In this work, we have found that this problem can still
teach us lessons about quantum communication. Specifically, Theorem 2 has
shown how perfect state discrimination can be made possible only through
broadcasting classical information that is encoded in non-orthogonal states.
The last part of this letter has shifted attention to the more practical
question of minimum error discrimination by LOSQC. We have presented a general
uncertainty relation in Theorem 2 that can be used to set error thresholds in
any QPV protocol that requires the honest prover to distinguish an ensemble of
product states.

## Acknowledgments

We thank Harry Buhrman for fruitful initial discussions in the early stages of
this work. R.A. was supported by the Dutch Research Council (NWO/OCW), as part
of the Quantum Software Consortium programme (project number 024.003.037).
P.VL. was supported by the Dutch Research Council (NWO/OCW), as part of the
NWO Gravitation Programme Networks (project number 024.002.003). E.C. and I.G.
are supported by the U.S. Department of Energy Office of Science National
Quantum Information Science Research Centers.

## References

  * Landauer [1991] R. Landauer, Information is Physical, Physics Today 44, 23 (1991).
  * Kent  _et al._ [2011] A. Kent, W. J. Munro, and T. P. Spiller, Quantum tagging: Authenticating location via quantum information and relativistic signaling constraints, Physical Review A 84, 012326 (2011).
  * Buhrman  _et al._ [2014] H. Buhrman, N. Chandran, S. Fehr, R. Gelles, V. Goyal, R. Ostrovsky, and C. Schaffner, Position-based quantum cryptography: Impossibility and constructions, SIAM Journal on Computing 43, 150 (2014).
  * Wootters and Zurek [1982] W. K. Wootters and W. H. Zurek, A single quantum cannot be cloned, Nature 299, 802 (1982).
  * Ishizaka and Hiroshima [2008] S. Ishizaka and T. Hiroshima, Asymptotic teleportation scheme as a universal programmable quantum processor, Physical review letters 101, 240501 (2008).
  * Ishizaka and Hiroshima [2009] S. Ishizaka and T. Hiroshima, Quantum teleportation scheme by selecting one of multiple output ports, Physical Review A 79, 042306 (2009).
  * Beigi and König [2011] S. Beigi and R. König, Simplified instantaneous non-local quantum computation with applications to position-based cryptography, New Journal of Physics 13, 093036 (2011).
  * Christandl  _et al._ [2021] M. Christandl, F. Leditzky, C. Majenz, G. Smith, F. Speelman, and M. Walter, Asymptotic performance of port-based teleportation, Communications in Mathematical Physics 381, 379 (2021).
  * Vaidman [2003] L. Vaidman, Instantaneous measurement of nonlocal variables, Physical review letters 90, 010402 (2003).
  * Chakraborty and Leverrier [2015] K. Chakraborty and A. Leverrier, Practical position-based quantum cryptography, Physical Review A 92, 052304 (2015).
  * Unruh [2014] D. Unruh, Quantum position verification in the random oracle model, in  _Advances in Cryptology–CRYPTO 2014: 34th Annual Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2014, Proceedings, Part II 34_ (Springer, 2014) pp. 1–18.
  * Junge  _et al._ [2022] M. Junge, A. M. Kubicki, C. Palazuelos, and D. Pérez-García, Geometry of banach spaces: a new route towards position based cryptography, Communications in Mathematical Physics 394, 625 (2022).
  * Bluhm  _et al._ [2022] A. Bluhm, M. Christandl, and F. Speelman, A single-qubit position verification protocol that is secure against multi-qubit attacks, Nature Physics 18, 623 (2022).
  * Allerstorfer  _et al._ [2023] R. Allerstorfer, L. Escolà-Farràs, A. A. Ray, B. Škorić, F. Speelman, and P. V. Lunel, Security of a continuous-variable based quantum position verification protocol (2023), arXiv:2308.04166 [quant-ph] .
  * Allerstorfer  _et al._ [2022] R. Allerstorfer, H. Buhrman, F. Speelman, and P. V. Lunel, On the role of quantum communication and loss in attacks on quantum position verification (2022).
  * Tomamichel  _et al._ [2013] M. Tomamichel, S. Fehr, J. Kaniewski, and S. Wehner, A monogamy-of-entanglement game with applications to device-independent quantum cryptography, New Journal of Physics 15, 103002 (2013).
  * Nielsen and Chuang [2010] M. A. Nielsen and I. L. Chuang,  _Quantum Computation and Quantum Information_ (Cambridge University Press, 2010).
  * Bennett  _et al._ [1999a] C. H. Bennett, D. P. DiVincenzo, T. Mor, P. W. Shor, J. A. Smolin, and B. M. Terhal, Unextendible product bases and bound entanglement, Physical Review Letters 82, 5385 (1999a).
  * Note [1] These should not be confused with the rotated BB84 states [23], which would have the final state be $\ket{1}(\sin(\tau)\ket{0}-\cos(\tau)\ket{1})$.
  * Peres and Wootters [1991] A. Peres and W. K. Wootters, Optimal detection of quantum information, Phys. Rev. Lett. 66, 1119 (1991).
  * Bennett  _et al._ [1993] C. H. Bennett, G. Brassard, C. Crépeau, R. Jozsa, A. Peres, and W. K. Wootters, Teleporting an unknown quantum state via dual classical and einstein-podolsky-rosen channels, Phys. Rev. Lett. 70, 1895 (1993).
  * Bennett  _et al._ [1999b] C. H. Bennett, D. P. DiVincenzo, C. A. Fuchs, T. Mor, E. Rains, P. W. Shor, J. A. Smolin, and W. K. Wootters, Quantum nonlocality without entanglement, Phys. Rev. A 59, 1070 (1999b).
  * Groisman and Vaidman [2001] B. Groisman and L. Vaidman, Nonlocal variables with product-state eigenstates, Journal of Physics A: Mathematical and General 34, 6881 (2001).
  * Watrous [2018] J. Watrous,  _The Theory of Quantum Information_ (Cambridge University Press, 2018) https://cs.uwaterloo.ca/ watrous/TQI/ .
  * Note [2] If it was already the case, no need to relabel. If it wasn’t the case, then it must be the case $\bra{b_{0}}\ket{b_{2}}\neq 0$. Therefore swap the $0$ and $1$ label. Then $\bra{a_{0}}\ket{a_{1}}\neq 0$ still holds and now $\bra{b_{1}}\ket{b_{2}}\neq 0$.
  * Konig  _et al._ [2009] R. Konig, R. Renner, and C. Schaffner, The operational meaning of min-and max-entropy, IEEE Transactions on Information theory 55, 4337 (2009).
  * Tomamichel [2015] M. Tomamichel,  _Quantum information processing with finite resources: mathematical foundations_, Vol. 5 (Springer, 2015).

All language used in the appendix is standard and may be found in standard
textbooks such as [24].

##  Appendix A Exact Characterizations and Separations with Product Ensembles
Proofs

###### Proof of Theorem 1.

Any state $\ket{b_{k}}$ that is orthogonal to every state in
$S_{B}\setminus\\{\ket{b_{k}}\\}$ can be determined with certainty by Bob
projecting on it, so it doesn’t matter what Bob’s state is for these states.
Call this subset of Bob’s states $S_{0,B}$. Thus, what remains is the subset

$S_{1}:=\\{\ket{a_{k}}\ket{b_{k}}:\exists k^{\prime}\neq
k\bra{a_{k}}\ket{a_{k^{\prime}}}\neq 0\\}\ .$ (9)

Now if two states $\widehat{k},\widehat{k}^{\prime}$ are not orthogonal on
Bob’s side, they must be orthogonal on Alice’s side. By the necessary
conditions in Proposition 1, this means every element of Alice’s POVM must
have one of these two states in its kernel. However, since $A=\mathbb{C}^{2}$,
this means every element of Alice’s POVM is either proportional to
$\outerproduct{a_{\widehat{k}}}{a_{\widehat{k}}}$ or
$\outerproduct{a_{\widehat{k}^{\prime}}}{a_{\widehat{k}^{\prime}}}$, so if
there is a strategy, Alice’s POVM is the PVM
$\\{\outerproduct{a_{\widehat{k}}}{a_{\widehat{k}}},\outerproduct{a_{\widehat{k}^{\prime}}}{a_{\widehat{k}^{\prime}}}\\}$.
Note there can be only one pair of orthogonal states Alice needs to
distinguish as that’s the largest number of states a POVM on a two-dimensional
space can perfectly distinguish, so for there to be an LOSCC strategy, we must
be able to partition $S_{1}$ into
$S_{1,B}^{a}:=\\{\ket{b_{k}}:\ket{a_{\widehat{k}}}\ket{b_{k}}\in S_{1}\\}$ and
$S_{1,B}^{\perp}:=\\{\ket{b_{k}}:\ket{a_{\widehat{k}^{\prime}}}\ket{b_{k}}\in
S_{1}\\}$. Now both of these sets have a unique state on Alice’s side, so in
each case Bob’s states must be mutually orthogonal to be a GOP. Thus,
recalling the definition of $S_{1}$, every $\ket{b_{k}}\in S_{1,B}^{a}$ has a
unique partner $\ket{b_{k^{\prime}}}\in S_{1,B}^{\perp}$ that it overlaps. We
know it is unique as otherwise there are two indistinguishable (thus non-
orthogonal) states in $S_{1,B}^{b}$ or $S_{1,B}^{\perp}$, which contradicts
what we have already determined. This means each $\ket{b_{k^{\prime}}}\in
S_{1,B}^{\perp}$ can be written
$\ket{b_{k^{\prime}}}=\alpha\ket{b_{\widetilde{k}}}+\beta\ket{w_{k^{\prime}}}_{W_{k^{\prime}}}$
where $\ket{b_{\widetilde{k}}}\in S_{1,B}^{a}$ is unique, $\alpha\neq 0$, and
$W_{k^{\prime}}$ is a subspace orthogonal to the space
$\text{span}\left(S_{A}\setminus\left\\{\ket{a_{k^{\prime}}}\right\\}\right)$.
That is to say $W_{k^{\prime}}$ is a subspace that no states on Bob’s side has
support on except $\ket{b_{k^{\prime}}}$. Thus,
$\text{span}(\\{\ket{b_{k}},\ket{b_{k^{\prime}}}\\})$ is a subspace that
contains no possible states on Bob’s side except these two. This argument
holds for each pair. Thus, Bob’s states partition into states that are in
their own one dimensional space and two-dimensional spaces that contain two
linearly dependent vectors that are partitioned by two possible states on
Alice’s side. Therefore, one can pack the space as much as possible under this
prescription. If there are $k$ vectors that lay in their own one-dimensional
subspace on Bob’s side, then there can be at most $\lfloor(d_{B}-k)/2\rfloor$
pairs of states in the remaining subspace on Bob’s side. This completes the
proof. ∎

###### Proof of Corollary 1.

First, there can be no $\ket{g_{i}}$ as it is a two-dimensional space. Second,
$B$ is a two-dimensional space, so, following the notation of the statement of
Theorem 1, if there is $\ket{0}^{B}$ and $\ket{\varphi_{0}}^{B}$, then no
other state may be added and preserve global orthogonality, so Alice can
distinguish the two states locally. The remaining case is Alice cannot
distinguish them locally, but given that $B$ is a two dimensional space, this
means $\ket{2i+k}=\ket{\varphi_{2i+k}}$ for $i\in\\{0,1\\}$. This completes
the proof. ∎

###### Proof of Lemma 1.

If the three states are locally mutually orthogonal for one party, then they
are locally discriminable and then the other party can forward the answer to
the other. Thus, we can focus on the case where both parties can’t locally
discriminate all the states, so both parties have two states that overlap.

Without loss of generality, let $\bra{a_{0}}\ket{a_{1}}\neq 0$. This is
w.l.o.g. as two of the states must be this way, and we just label the indices
so that it is the first two. Thus, $\bra{b_{0}}\ket{b_{1}}=0$ as otherwise we
contradict being GOP. For Bob to also have overlapping states, $\ket{b_{2}}$
overlaps with at least one of the previous two states. Via another relabeling
of indices, without loss of generality $\bra{b_{1}}\ket{b_{2}}\neq 0$ 222If it
was already the case, no need to relabel. If it wasn’t the case, then it must
be the case $\bra{b_{0}}\ket{b_{2}}\neq 0$. Therefore swap the $0$ and $1$
label. Then $\bra{a_{0}}\ket{a_{1}}\neq 0$ still holds and now
$\bra{b_{1}}\ket{b_{2}}\neq 0$.. This either defines the GOP ensemble’s
overlaps or one may add the overlap $a_{0},a_{2}$ or $b_{0},b_{2}$, but not
both as then the ensemble would not be globally orthogonal. Assume
$\bra{a_{0}}\ket{a_{2}}\neq 0$. This is symmetric to the the case
$\bra{b_{0}}\ket{b_{2}}\neq 0$ and it’s more difficult than the case where
this extra overlap does not exist, so it suffices to construct a strategy for
this case. Alice uses the projection
$\\{P_{0}:=\outerproduct{a_{2}}{a_{2}},P_{1}:=\mathbbm{1}-\outerproduct{a_{2}}{a_{2}}\\}$
and Bob applies
$\\{Q_{0}:=\outerproduct{b_{0}}{b_{0}},Q_{1}:=\mathbbm{1}-\outerproduct{b_{0}}{b_{0}}\\}$.
Then we have the following partitioning of outcomes:

State | Alice Outcome | Bob Outcome
---|---|---
0 | 0/1 | 0
1 | 1 | 1
2 | 0 | 1
Table 1: State discrimination strategy outcomes partitioned.

Noting that the four possible outcomes partition across the three states
completes the proof. ∎

####  A.0.1 Constructing LOSQC Discriminable Ensembles from Secret Sharing
Schemes

To prove Theorem 3, we just need some basic points about state discrimination
and min-entropy.

######  Fact ([26, 27]).

The optimal state discrimination probability of the ensemble
$\\{p(k),\rho^{k}_{A}\\}$ given the $A$ space is
$p_{\text{g}}(K|A)=\exp(-H_{\min}(X|A)_{\rho})$ where
$H_{\min}(A|B)_{\rho_{AB}}:=\max_{\sigma_{B}\in\mathrm{D}(B)}-\log(\|\sigma_{B}^{-1/2}\rho_{AB}\sigma_{B}^{-1/2}\|_{\infty})$.

The above allows us to define a class of natural secret sharing schemes.

######  Definition 1.

Consider a map $\mathcal{E}_{K\to A^{m}_{i}}$, which may be viewed as
(ideally) a quantum secret sharing scheme. $\mathcal{E}$ is single-share
perfectly secure if

$H_{\min}(K|A_{i})_{\mathcal{E}(\pi_{K})}=\log(|K|)\quad\forall i\in[m]\ ,$

where $\pi_{K}=|K|^{-1}\sum_{k}\outerproduct{k}{k}$.

The idea is then that the type of secret share schemes given above admit the
property that if you give secret shares from different secret sharing schemes,
the secret $k$ is not suddenly locally determinable. To prove this, we need
the following lemmas which are easiest to establish in some generality and
then simply note that $H_{\min}$ is a specific case. These lemmas rely on
properties of Rényi divergences, to which we refer the reader to [27].

######  Proposition 3.

For any Rényi entropy $\mathbb{H}(\cdot)$, $\mathbb{H}(A)=\log(|A|)$ if and
only if $\rho_{A}=\pi_{A}=|A|^{-1}\mathbbm{1}_{A}$.

###### Proof.

As we are not conditioning on anything, we can treat $\rho_{A}$ as being
‘classical’ where we take the computational basis as its eigenbasis. That is,
we can focus on $\rho_{X}=p_{X}$ where $p_{X}$ is diagonal. Let
$\mathbb{H}(X)_{\rho}=-\mathbb{D}(\rho_{X}||\mathbbm{1}_{A})$ be a Rényi
entropy via $\mathbb{D}$ being a Rényi divergence. Then,

$\displaystyle\mathbb{H}(X)_{\rho}=-\mathbb{D}(p_{X}||\mathbbm{1}_{X})=-\mathbb{D}(p_{X}||\pi_{X})+\log(|X|)\
,$

where we used normalization property. By positive definiteness, one will only
equal $\log(|X|)$ if $-\mathbb{D}(p_{X}||\pi_{X})=0$, which only happens if
$p_{X}=\pi_{X}$. ∎

######  Lemma 2.

Given $\rho_{XB}$, $\mathbb{H}_{\alpha}(X|B)_{\rho}=\log(|X|)$ if and only if
$\rho_{XB}=\pi_{X}\otimes\rho_{B}$.

###### Proof.

Let
$\mathbb{H}(A|B)_{\rho}=-\mathbb{D}(\rho_{AB}||\mathbbm{1}_{A}\otimes\sigma_{B})$
be a Rényi divergence, where $\sigma_{B}$ may be optimized over.

$(\leftarrow)$ Let $\rho_{XB}=\rho_{X}\otimes\rho_{B}$. Then,

$\displaystyle\mathbb{H}(X|B)_{\rho}$ $\displaystyle=$
$\displaystyle-\mathbb{D}(\pi_{X}\otimes\rho_{B}||\mathbbm{1}_{X}\otimes\sigma_{B})$
$\displaystyle=$
$\displaystyle-\mathbb{D}(\pi_{X}\otimes\rho_{B}||\pi_{X}\otimes\sigma_{B})+\log(|X|)=\log(|X|)\
,$

where the last equality either follows from $\sigma_{B}=\rho_{B}$ or because
by positive definiteness, optimizing over $\sigma_{B}$ results in $\rho_{B}$.

($\rightarrow$) First, $\mathbb{H}(X)_{\rho}=\log(|X|)$ if and only if
$\rho_{X}=\pi_{X}$ by previous lemma. By DPI and our assumption
$\log(|X|)=H(X|B)_{\rho}\leq H(X)_{\rho}$. Thus, we many conclude
$\rho_{X}=\pi_{X}$. Thus, we have
$\rho_{XB}=|X|^{-1}\sum_{x}\outerproduct{x}{x}\otimes\rho_{B}^{x}$.

Next,

$\displaystyle\log(|X|)=$ $\displaystyle\mathbb{H}(X|B)_{\rho}$
$\displaystyle=$
$\displaystyle-\mathbb{D}(|X|^{-1}\sum_{x}\outerproduct{x}{x}\otimes\rho_{B}^{x}||\mathbbm{1}_{A}\otimes\sigma_{B})$
$\displaystyle=$
$\displaystyle-\mathbb{D}(\sum_{x}\outerproduct{x}{x}\otimes\rho^{x}_{B}||\mathbbm{1}_{A}\otimes\sigma_{B})+\log(|X|)\
.$

This implies
$\mathbb{D}(\sum_{x}\outerproduct{x}{x}\otimes\rho^{x}_{B}||\mathbbm{1}_{A}\otimes\sigma_{B})=0$.
By positive definiteness, this can only be the case if
$\sum_{x}\outerproduct{x}{x}\otimes\rho^{x}_{B}=\mathbbm{1}_{A}\otimes\sigma_{B}$.
This implies $\rho^{x}_{B}=\sigma_{B}$ for every $x$. Thus,
$\rho_{XB}=\rho_{X}\otimes\rho_{B}$ for some $\rho_{B}\in\mathrm{D}(B)$. This
completes the proof. ∎

Now having established these properties which hold for $H_{\min}(X|B)$
specifically, we can prove Theorem 3, which we restate more formally.

######  Theorem (Theorem 3 Restated).

Given any two single-share perfectly secure quantum secret sharing schemes
$\mathcal{E}^{1}_{K\to A_{1}B_{1}}$, $\mathcal{E}^{2}_{K\to A_{2}B_{2}}$, the
ensemble
$\\{|K|^{-1},\rho^{k}_{A^{2}_{1}B^{2}_{1}}:=\mathcal{E}^{1}(\outerproduct{k}{k})\otimes\mathcal{E}^{2}(\outerproduct{k}{k})\\}$,
where Alice receives $A_{1}^{2}:=A_{1}A_{2}$ and Bob receives
$B_{1}^{2}:=B_{1}B_{2}$, is locally non-discriminable, but LOSQC
discriminable.

###### Proof.

Consider the global state after the secret sharing:

$\rho_{KA_{1}B_{1}A_{2}B_{2}}=|K|^{-1}\sum_{k}\outerproduct{k}{k}\otimes\tau_{A_{1}B_{1}}^{k}\otimes\sigma_{A_{2}B_{2}}^{k}\
,$

which implies

$\displaystyle\rho_{KA_{1}A_{2}}=$
$\displaystyle|K|^{-1}\sum_{k}\outerproduct{k}{k}\tau^{k}_{A_{1}}\otimes\sigma^{k}_{A_{2}}$
(10) $\displaystyle\rho_{KB_{1}B_{2}}=$
$\displaystyle|K|^{-1}\sum_{k}\outerproduct{k}{k}\tau^{k}_{B_{1}}\otimes\sigma^{k}_{B_{2}}\
.$ (11)

By the single-share perfect security definition and Lemma 2,

$\displaystyle\rho_{KA_{1}}=\pi_{K}\otimes\omega_{A_{1}}^{1}\quad\rho_{KA_{2}}=\pi_{K}\otimes\omega_{A_{2}}^{2}$
(12)
$\displaystyle\rho_{KB_{1}}=\pi_{K}\otimes\omega_{B_{1}}^{3}\quad\rho_{KA_{2}}=\pi_{K}\otimes\omega_{B_{2}}^{4}\
,$

where each $\omega^{i}$ is in its appropriate space and does not have to be
the same as the others. Combining (10) and (12), by considering the partial
traces, it must be the case

$\displaystyle\rho_{KA_{1}A_{2}}=\pi_{K}\otimes\omega^{1}_{A_{1}}\otimes\omega^{2}_{A_{2}}$
$\displaystyle\rho_{KB_{1}B_{2}}=\pi_{K}\otimes\omega^{3}_{B_{1}}\otimes\omega^{4}_{B_{2}}\
.$

Now, applying Lemma 2, we may conclude $H_{\min}(K|A^{2}_{1})=\log(|K|)$,
$H_{\min}(K|B^{2}_{1})=\log(|K|)$ which means in fact this is still a single-
share perfectly secure QSS scheme. However, clearly if Alice sends $A_{2}$ to
Bob and Bob sends $B_{1}$ to Alice, then this defines a perfect LOSQC
strategy. ∎

###  A.1 Proof of Theorem 2

To establish Theorem 2, we need the following relatively well-known fact,
which we provide for completeness.

######  Fact (Sylvester’s Criterion for Positive Semidefinite Matrices).

Given a Hermitian matrix $H\in\mathrm{Herm}(A)$. $H\succeq 0$ if and only if
every principle minor of $H$ has non-negative determinant.

######  Corollary 3.

Let $P^{A}\succeq 0$. For any basis $\\{\ket{e_{n}}\\}_{n}$ of $A$, if
$\bra{e_{n}}P\ket{e_{n}}=0$, then
$\bra{e_{n^{\prime}}}P\ket{e_{n}}=0=\bra{e_{n}}P\ket{e_{n^{\prime}}}$ for all
$n^{\prime}$. That is, if in a given basis $P$ is zero on a diagonal element,
both the row and column are all zeroes.

###### Proof.

Proceed by contradiction, so $\bra{e_{n}}P\ket{e_{n}}=0$ and there is
$n^{\prime}$ such that $\bra{e_{n}}P\ket{e_{n^{\prime}}}=\alpha\neq 0$.
Consider the principal minor

$P^{\prime}=\begin{bmatrix}P(n,n)&P(n,n^{\prime})\\\
P(n^{\prime},n)&P(n^{\prime},n^{\prime})\end{bmatrix}=\begin{bmatrix}0&\alpha\\\
\alpha^{\ast}&P(n^{\prime},n^{\prime})\end{bmatrix}\ .$

Then $\det(P^{\prime})=0\cdot
P(n^{\prime},n^{\prime})-\alpha\cdot\alpha^{\ast}=-|\alpha|^{2}<0$ where we
have used that $\alpha\neq 0$ so $|\alpha|^{2}>0$. This contradicts
Sylvester’s criterion. ∎

###### Proof of Theorem 2.

We begin by noting the simplified form of Proposition 1 for product states
$\\{\ket{a_{k}}\ket{b_{k}}\\}$:

$\displaystyle\bra{a_{k}}M_{x}^{A}\ket{a_{k}}\bra{a_{k^{\prime}}}M_{x}^{A}\ket{a_{k^{\prime}}}|\bra{b_{k}}N_{y}^{B}\ket{b_{k^{\prime}}}|^{2}$
$\displaystyle=0$ (13)
$\displaystyle\bra{b_{k}}N_{y}^{B}\ket{b_{k}}\bra{b_{k^{\prime}}}N_{y}^{B}\ket{b_{k^{\prime}}}|\bra{a_{k}}M_{x}^{A}\ket{a_{k^{\prime}}}|^{2}$
$\displaystyle=0\ $

for all $x,y,k\neq k^{\prime}$.

We know without loss of generality Alice can determine $\ket{0},\ket{1}$, so
we focus on what states Bob must perfectly distinguish, $\\{\ket{0\pm
1},\ket{0\pm 2}\\}$. Thus, by the second constraint in (13),

$\displaystyle\bra{0+1}N_{y}^{B}\ket{0+1}\bra{0-1}N_{y}^{B}\ket{0-1}=0\quad\forall
y,$
$\displaystyle\bra{0+2}N_{y}^{B}\ket{0+2}\bra{0-2}N_{y}^{B}\ket{0-2}=0\quad\forall
y.$

Now note that this means if we write $N_{y}^{B}$ in the
$\ket{0+1},\ket{0-1},\ket{2}$ basis, $N_{y}^{B}$ must have a zero entry either
in the $\outerproduct{0+1}{0+1}$ entry or the $\outerproduct{0-1}{0-1}$ entry.
By Corollary 3, this means in the $\ket{0\pm 1}$ subspace, each $N_{y}$ is
proportional to either $\outerproduct{0+1}{0+1}$ or $\outerproduct{0-1}{0-1}$.
By the same argument with $\ket{0\pm 2}$, each POVM element needs to be
proportional to $\outerproduct{0+2}{0+2}$ or $\outerproduct{0-2}{0-2}$. These
constraints on $\\{N_{y}^{B}\\}$ cannot be satisfied at the same time due to
non-commutativity of the states being projected on, so there does not exist an
LOSCC strategy by the necessary and sufficient conditions in (13).

However, we now show there is an LOSQC strategy. For the strategy, consider
the isometry

$\displaystyle V^{B\to A^{\prime}B^{\prime}}:$
$\displaystyle\ket{0}\to\frac{1}{\sqrt{2}}\left(\ket{00}+\ket{11}\right),$
$\displaystyle\ket{1}\to\frac{1}{\sqrt{2}}\left(\ket{00}-\ket{11}\right),$
$\displaystyle\ket{2}\to\frac{1}{\sqrt{2}}\left(\ket{01}+\ket{10}\right).$

Then

$\displaystyle V\ket{0+1}=\ket{0}^{\otimes 2}\quad V\ket{0-1}=\ket{1}^{\otimes
2}$ $\displaystyle\hskip 22.76219ptV\ket{0\pm 2}=\ket{0\pm 1}^{\otimes 2}\ .$

Thus, conditioned on the classical outcome on $A$’s space which Alice can copy
and forward, these states are locally discriminable for both parties after
quantum transmission of one of the copies of the output of $V$. ∎

##  Appendix B Error Bounds for Product State Discrimination under LOSQC
Proofs

###### Proof of Theorem 2.

By direct calculation,

$\displaystyle\gamma_{\theta}=$
$\displaystyle\cos^{2}(\theta/2)\outerproduct{\gamma_{0}}{\gamma_{0}}+\sin^{2}(\theta/2)\outerproduct{\gamma_{1}}{\gamma_{1}}$
$\displaystyle\hskip
28.45274pt+\sin(\theta)/2\left[e^{-i\phi}\ket{\gamma_{0}}\bra{\gamma_{1}}+e^{i\phi}\ket{\gamma_{1}}\bra{\gamma_{0}}\right]$
$\displaystyle\gamma_{\omega}=$
$\displaystyle\cos^{2}(\omega/2)\outerproduct{\gamma_{0}}{\gamma_{0}}+\sin^{2}(\omega/2)\outerproduct{\gamma_{1}}{\gamma_{1}}$
$\displaystyle\hskip
28.45274pt+\sin(\omega)/2\left[e^{-i\phi^{\prime}}\ket{\gamma_{0}}\bra{\gamma_{1}}+e^{i\phi^{\prime}}\ket{\gamma_{1}}\bra{\gamma_{0}}\right]\
.$

Let $z_{1}=\frac{1}{2}(\cos(\theta)-\cos(\omega))$.
$z_{2}=\frac{1}{2}(\sin(\theta)e^{-i\phi}-\sin(\omega)e^{-i\phi^{\prime}})$.
Therefore,

$\displaystyle\left\|\gamma_{\theta}^{B}-\gamma_{\omega}^{B}\right\|_{1}$
$\displaystyle=$
$\displaystyle\left\|\Tr_{A}[\gamma_{\theta}^{AB}-\gamma_{\omega}^{AB}]\right\|_{1}$
$\displaystyle=$
$\displaystyle\left\|z_{1}\Tr_{A}[\gamma_{0}^{AB}-\gamma_{1}^{AB}]+\Tr_{A}\left[z_{2}\ket{\gamma_{0}}\bra{\gamma_{1}}+z_{2}^{\ast}\ket{\gamma_{1}}\bra{\gamma_{0}}\right]\right\|_{1}$
$\displaystyle\leq$
$\displaystyle\left\|z_{1}\Tr_{A}[\gamma_{0}^{AB}-\gamma_{1}^{AB}]\right\|_{1}$
$\displaystyle\hskip
28.45274pt+\left\|\Tr_{A}\left[z_{2}\ket{\gamma_{0}}\bra{\gamma_{1}}+z_{2}^{\ast}\ket{\gamma_{1}}\bra{\gamma_{0}}\right]\right\|_{1}$
$\displaystyle=$
$\displaystyle|z_{1}|\left\|\gamma_{0}^{B}-\gamma_{1}^{B}\right\|_{1}+|z_{2}|\left\|\Tr_{A}\left[\ket{\widetilde{\gamma}_{0}}\bra{\gamma_{1}}+\ket{\gamma_{1}}\bra{\widetilde{\gamma}_{0}}\right]\right\|_{1}\
,$

where $z_{2}=|z_{2}|e^{-i\overline{\phi}}$ and
$\ket{\widetilde{\gamma}_{0}}:=e^{-i\overline{\phi}}\ket{\gamma_{0}}$.

We now need to handle the cross term. Define $P_{\pm}$ be the projector onto
the $\pm$ eigenspace of
$\Tr_{A}[\ket{\widetilde{\gamma}_{0}}\bra{\gamma_{1}}+\ket{\gamma_{1}}\bra{\widetilde{\gamma}_{0}}]$.
Then by definition of trace norm,

$\displaystyle\left\|\Tr_{A}(\ket{\widetilde{\gamma}_{0}}\bra{\gamma_{1}}+\ket{\gamma_{1}}\bra{\widetilde{\gamma}_{0}})\right\|_{1}$
$\displaystyle=$ $\displaystyle\Tr[(\mathbbm{1}_{A}\otimes
P_{+}-P_{-})(\ket{\widetilde{\gamma}_{0}}\bra{\gamma_{1}}+\ket{\gamma_{1}}\bra{\widetilde{\gamma}_{0}})]$

Now,

$\displaystyle F(\gamma_{0}^{A},\gamma_{1}^{A})$ $\displaystyle=$
$\displaystyle F(\widetilde{\gamma}_{0}^{A},\gamma_{1}^{A})$ $\displaystyle=$
$\displaystyle\max_{U}\left|\Tr[(\mathbbm{1}\otimes
U)\ket{\widetilde{\gamma}_{0}}\bra{\gamma_{1}}^{AB}]\right|$ $\displaystyle=$
$\displaystyle\frac{1}{2}\Big{(}\max_{U}\left|\Tr[(\mathbbm{1}\otimes
U)(\ket{\widetilde{\gamma}_{0}}\bra{\gamma_{1}})]\right|$ $\displaystyle\hskip
28.45274pt+\max_{U}\left|\Tr[(\mathbbm{1}\otimes
U)(\ket{\gamma_{1}}\bra{\widetilde{\gamma}_{0}})]\right|\Big{)}$
$\displaystyle\geq$
$\displaystyle\frac{1}{2}\left(\max_{U}\left|\Tr[(\mathbbm{1}\otimes
U)(\ket{\widetilde{\gamma}_{0}}\bra{\gamma_{1}}+\ket{\gamma_{1}}\bra{\widetilde{\gamma}_{0}})]\right|\right)\
,$

where the first equality is noting
$\gamma_{0}=\outerproduct{\gamma_{0}}{\gamma_{0}}=\outerproduct{\widetilde{\gamma}_{0}}{\widetilde{\gamma}_{0}}$
and the second is Uhlmann’s theorem.

Choosing $U=P_{+}-P_{-}+(\mathbbm{1}^{A}-P_{+}-P_{-})$, we have

$\displaystyle F(\gamma_{0}^{A},\gamma_{1}^{A})$ $\displaystyle\geq$
$\displaystyle\frac{1}{2}\left(\max_{U}\Tr[(\mathbbm{1}\otimes
U)(\ket{\widetilde{\gamma}_{0}}\bra{\gamma_{1}}+\ket{\gamma_{1}}\bra{\widetilde{\gamma}_{0}})]\right)$
$\displaystyle\geq$
$\displaystyle\frac{1}{2}\Tr[\mathbbm{1}\otimes(P_{+}-P_{-})(\ket{\widetilde{\gamma}_{0}}\bra{\gamma_{1}}+\ket{\gamma_{1}}\bra{\widetilde{\gamma}_{0}})]$
$\displaystyle=$
$\displaystyle\frac{1}{2}\left\|\Tr_{A}\left[\ket{\widetilde{\gamma}_{0}}\bra{\gamma_{1}}+\ket{\gamma_{1}}\bra{\widetilde{\gamma}_{0}}\right]\right\|_{1}\
.$

Using our definition of $\delta$ and reordering gets us

$\left\|\gamma_{\theta}^{B}-\gamma_{\overline{\theta}}^{B}\right\|_{1}\leq|z_{1}|\left\|\gamma_{0}^{B}-\gamma_{1}^{B}\right\|_{1}+2|z_{2}||\sin(\theta)|\delta\
.$

Dividing by two gets us the trace distance and fidelity bound, (4). ∎

To establish Theorem 4, we need the following lemma.

######  Lemma 3.

If $0\leq W,X,Y,Z\leq\mathbbm{1}$, then

$\displaystyle\|W\otimes X-Y\otimes Z\|_{1}\leq\|W-Y\|_{1}+\|X-Z\|_{1}.$ (14)

###### Proof.

Let $-\mathbbm{1}\leq\tau\leq\mathbbm{1}$ be such that

$\displaystyle\|W\otimes X-Y\otimes Z\|_{1}$ $\displaystyle=$
$\displaystyle\Tr[\tau\left(W\otimes X-Y\otimes Z\right)]$ $\displaystyle=$
$\displaystyle\Tr[\tau\Big{(}W\otimes\frac{X+Z}{2}-Y\otimes\frac{X+Z}{2}$
$\displaystyle\hskip 42.67912pt+\frac{W+Y}{2}\otimes X-\frac{W+Y}{2}\otimes
Z\Big{)}\Big{]}$ $\displaystyle\leq\|W-Y\|_{1}+\|X-Z\|_{1},$

since
$-\mathbbm{1}\leq\Tr_{B}\left[\tau^{AB}\left(\mathbbm{1}\otimes\frac{X+Z}{2}\right)\right]\leq\mathbbm{1}$
and
$-\mathbbm{1}\leq\Tr_{A}\left[\tau^{AB}\left(\frac{W+Y}{2}\otimes\mathbbm{1}\right)\right]\leq\mathbbm{1}$.
∎

###### Proof of Theorem 4.

We assume that Alice and Bob apply local isometries $U^{A\to AB^{\prime}}$ and
$V^{B\to A^{\prime}B}$, respectively, on their given states. We define
$\ket{\alpha_{k}}:=U\ket{a_{k}}$ and $\ket{\beta_{k}}:=V\ket{b_{k}}$. The
simultaneous communication occurs and Alice holds systems $AA^{\prime}$ while
Bob holds systems $BB^{\prime}$. The four possible states after the isometries
have the form

$\displaystyle U\otimes V\ket{\psi_{0}}^{AB}$
$\displaystyle=\ket{\alpha_{0}}^{AB^{\prime}}\ket{\beta_{0}}^{A^{\prime}B}$
$\displaystyle U\otimes V\ket{\psi_{1}}^{AB}$
$\displaystyle=\ket{\alpha_{1}}^{AB^{\prime}}\ket{\beta_{1}}^{A^{\prime}B}$
$\displaystyle U\otimes V\ket{\psi_{\theta}}^{AB}$
$\displaystyle=\ket{\alpha_{2}}^{AB^{\prime}}\ket{\beta_{\theta}}^{A^{\prime}B}$
$\displaystyle U\otimes V\ket{\psi_{\omega}}^{AB}$
$\displaystyle=\ket{\alpha_{3}}^{AB^{\prime}}\ket{\beta_{\omega}}^{A^{\prime}B},$

where
$\ket{\beta_{\theta}}^{A^{\prime}B}=\cos(\theta/2)\ket{\beta_{0}}+\sin(\theta/2)e^{i\phi}\ket{\beta_{1}}$
and
$\ket{\beta_{\omega}}^{A^{\prime}B}=\cos(\omega/2)\ket{\beta_{0}}+\cos(\omega/2)e^{i\phi^{\prime}}\ket{\beta_{1}}$.

After the communication, POVMs $\\{P_{k}\\}^{AA^{\prime}}$ and
$\\{Q_{k}\\}^{BB^{\prime}}$ are performed by Alice and Bob, respectively. The
overall (unnormalized) success probability is given by

The completion relation demands that $\sum_{k}P_{k}=\mathbbm{1}^{AA^{\prime}}$
and $\sum_{k}Q_{k}=\mathbbm{1}^{BB^{\prime}}$. Suppose that

$\displaystyle\Tr\left[(P_{k}^{AA^{\prime}}\otimes
Q_{k}^{BB^{\prime}})\left(\alpha_{k}^{AB^{\prime}}\otimes\beta_{k}^{A^{\prime}B}\right)\right]\geq
1-\epsilon\qquad\forall k.$

From this we obtain constraints on Alice and Bob’s POVM elements:

$\displaystyle\Tr[P_{k}(\alpha_{k}^{A}\otimes\beta_{k}^{A^{\prime}})]$
$\displaystyle\geq 1-\epsilon$ (15)
$\displaystyle\Tr[Q_{k}(\alpha_{k}^{B^{\prime}}\otimes\beta_{k}^{B})]$
$\displaystyle\geq 1-\epsilon.$ (16)

Since $P_{k}\leq\mathbbm{1}-P_{j}$ and $Q_{k}\leq\mathbbm{1}-Q_{j}$ for all
$j\not=k$, we use the previous equations to obtain

$\displaystyle-\Tr[P_{k}(\alpha_{j}^{A}\otimes\beta_{j}^{A^{\prime}})]>-\epsilon$
(17)
$\displaystyle-\Tr[Q_{k}(\alpha_{j}^{B^{\prime}}\otimes\beta_{j}^{B})]>-\epsilon.$
(18)

Adding Eqns. (17)–(18) to Eqns. (15)–(16) yields

$\displaystyle 1-2\epsilon$
$\displaystyle<\Tr\left[P_{k}\left(\alpha_{k}^{A}\otimes\beta_{k}^{A^{\prime}}-\alpha_{j}^{A}\otimes\beta_{j}^{A^{\prime}}\right)\right]$
$\displaystyle<\frac{1}{2}\left\|\alpha_{k}^{A}\otimes\beta_{k}^{A^{\prime}}-\alpha_{j}^{A}\otimes\beta_{j}^{A^{\prime}}\right\|_{1}$
$\displaystyle\leq\sqrt{1-F(\alpha_{k}^{A},\alpha_{j}^{A})^{2}F(\beta_{k}^{A^{\prime}},\beta_{j}^{A^{\prime}})^{2}}$
(19) $\displaystyle 1-2\epsilon$
$\displaystyle<\Tr\left[Q_{k}\left(\alpha_{k}^{B^{\prime}}\otimes\beta_{k}^{B}-\alpha_{j}^{B^{\prime}}\otimes\beta_{j}^{B}\right)\right]$
$\displaystyle<\frac{1}{2}\left\|\alpha_{k}^{B^{\prime}}\otimes\beta_{k}^{B}-\alpha_{j}^{B^{\prime}}\otimes\beta_{j}^{B}\right\|_{1}$
$\displaystyle\leq\sqrt{1-F(\alpha_{k}^{B^{\prime}},\alpha_{j}^{B^{\prime}})^{2}F(\beta_{k}^{B},\beta_{j}^{B})^{2}}.$
(20)

This says that the isometries $U$ and $V$ must split the states
$\ket{a_{k}}\ket{b_{k}}$ and $\ket{a_{j}}\ket{b_{j}}$ into parts that are
(roughly) mutually orthogonal for both parties, for all pairs $j\not=k$.

Applying Eq. (19) on the first two states,
$\ket{\alpha_{0}}\ket{\beta_{0}},\ket{\alpha_{1}}\ket{\beta_{1}}$, yields

$\displaystyle 1-2\epsilon$
$\displaystyle\leq\sqrt{1-F(\alpha_{0}^{A},\alpha_{1}^{A})^{2}F(\beta_{0}^{A^{\prime}},\beta_{1}^{A^{\prime}})^{2}}$
$\displaystyle\leq\sqrt{1-|\innerproduct{\alpha_{0}}{\alpha_{1}}|^{2}F(\beta_{0}^{A^{\prime}},\beta_{1}^{A^{\prime}})^{2}}$
$\displaystyle=\sqrt{1-|\innerproduct{a_{0}}{a_{1}}|^{2}F(\beta_{0}^{A^{\prime}},\beta_{1}^{A^{\prime}})^{2}}\
,$

which under re-ordering means,

$\displaystyle\Rightarrow\qquad
F(\beta_{0}^{A^{\prime}},\beta_{1}^{A^{\prime}})$
$\displaystyle\leq\frac{2\sqrt{\epsilon(1-\epsilon)}}{|\innerproduct{a_{0}}{a_{1}}|^{2}}=:\delta.$
(21)

Applying (4) of Theorem 2 multiplied by two,

$\displaystyle\frac{4|x|\sqrt{\varepsilon(1-\varepsilon)}}{|\langle
a_{0}|a_{1}\rangle|^{2}}$ $\displaystyle>$
$\displaystyle\|\beta_{\theta}^{B}-\beta_{\omega}^{B}\|_{1}-|w|\|\beta_{0}^{B}-\beta_{1}^{B}\|_{1}$
$\displaystyle\geq$
$\displaystyle\|\alpha_{2}^{B^{\prime}}\otimes\beta_{\theta}^{B}-\alpha_{3}^{B^{\prime}}\otimes\beta_{\omega}^{B}\|_{1}-\|\alpha_{2}^{B^{\prime}}-\alpha_{3}^{B^{\prime}}\|_{1}$
$\displaystyle\hskip 119.50148pt-|w|\|\beta_{0}^{B}-\beta_{1}^{B}\|_{1}\ ,$
(22)

where the second inequality is by Lemma 3,
$w=\frac{1}{2}(\cos(\theta)-\cos(\omega))$, and
$x=\frac{1}{2}(\sin(\theta)e^{-i\phi}-\sin(\omega)e^{-i\phi^{\prime}})$. Note
that $\langle a_{2}|a_{3}\rangle=\langle\alpha_{2}|\alpha_{3}\rangle$ and
$\|\alpha_{2}^{B^{\prime}}-\alpha_{3}^{B^{\prime}}\|_{1}\leq
2\sqrt{1-|\langle\alpha_{2}|\alpha_{3}\rangle|^{2}}$ by Fuchs-van de Graaf
inequality, so
$\|\alpha_{2}^{B^{\prime}}-\alpha_{3}^{B^{\prime}}\|_{1}\leq\sqrt{1-|\langle
a_{2}|a_{3}\rangle|^{2}}$ and similarly
$\|\beta_{0}^{B}-\beta_{1}^{B}\|_{1}\leq
2\sqrt{1-|\bra{b_{0}}\ket{b_{1}}|^{2}}$. Then the inequality given in (22) can
be relaxed to

$\displaystyle\frac{4|x|\sqrt{\varepsilon(1-\varepsilon)}}{|\langle
a_{0}|a_{1}\rangle|^{2}}$ $\displaystyle\hskip
14.22636pt+2\left[\sqrt{1-|\langle
a_{2}|a_{3}\rangle|^{2}}+|w|\sqrt{1-|\bra{b_{0}}\ket{b_{1}}|^{2}}\right]$
$\displaystyle\geq$
$\displaystyle\|\alpha_{2}^{B^{\prime}}\otimes\beta_{+}^{B}-\alpha_{3}^{B^{\prime}}\otimes\beta_{-}^{B}\|_{1}.$

We require
$1-2\varepsilon<\frac{1}{2}\|\alpha_{2}^{B^{\prime}}\otimes\beta_{+}^{B}-\alpha_{3}^{B^{\prime}}\otimes\beta_{-}^{B}\|_{1}$.
So in total, we need

$\displaystyle\frac{2|x|\sqrt{\varepsilon(1-\varepsilon)}}{|\langle
a_{0}|a_{1}\rangle|^{2}}+\sqrt{1-|\langle
a_{2}|a_{3}\rangle|^{2}}+|w|\sqrt{1-|\langle b_{0}|b_{1}\rangle|^{2}}$
$\displaystyle>$ $\displaystyle 1-2\varepsilon.$

∎

###  B.1 Error Bounds for Two-Qubit GOPs

In this section, we provide error bounds for two-qubit GOPs. To do this, we
begin with the following structural observation.

######  Lemma 4.

Given a GOP ensemble
$\\{\ket{\alpha_{k}}\ket{\beta_{k}}\\}_{k\in\\{0,1,2,3\\}}\subset\mathbb{C}^{2}\otimes\mathbb{C}^{2}$,
it is LU-equivalent to
$\\{\ket{0}^{A}\ket{0}^{B},\ket{1}^{A}\ket{\hat{n}}^{B},\ket{0}^{A}\ket{1}^{B},\ket{1}^{A}\ket{-\hat{n}}^{A}\\}$
where $\ket{\hat{n}}=\cos(\theta/2)\ket{0}+e^{i\phi}\sin(\theta/2)\ket{1}$ and
$\bra{-\hat{n}}\ket{\hat{n}}=0$.

###### Proof.

Note that since the local spaces are qubits, there must be two states that
overlap on each side. Thus without loss of generality we may assume
$\bra{\beta_{0}}\ket{\beta_{1}}\neq 0$. This means that
$\bra{\alpha_{0}}\ket{\alpha_{1}}=0$ or else we contradict global
orthogonality. Since we are interested in LU equivalence, we can let
$\ket{\beta_{0}}^{B}=\ket{0}^{B}$, $\ket{\alpha_{0}}^{A}=\ket{0}^{A}$,
$\ket{\alpha_{1}}=\ket{1}^{A}$ w.l.o.g. since we can always find local
unitaries that do this. This means
$\ket{\beta_{1}}=b_{10}\ket{0}+b_{11}\ket{1}$ where $b_{10}\neq 0$. This gives
us some structure on the first two states.

Now, for $i\in\\{2,3\\}$, by global orthogonality conditions, if
$\ket{\beta_{i}}\neq\ket{\beta_{1}^{\perp}}$, then it must be the case
$\ket{\alpha_{i}}=\ket{0}$. Likewise, if
$\ket{\beta_{i}}=\ket{\beta_{1}^{\perp}}$ then $\ket{\alpha_{i}}=\ket{1}$. As
these are exhaustive cases, we may conclude $\alpha_{i}\in\\{0,1\\}$ for
$i\in\\{2,3\\}$. This leaves us with four cases, which we can just consider
directly:

  1. 1.

$\ket{\alpha_{2}}=\ket{0}=\ket{\alpha_{3}}$. This means states $0,2,3$ need to
be mutually orthogonal on Bob’s side, which is not possible with a qubit
space.

  2. 2.

$\ket{\alpha_{2}}=\ket{0}$, $\ket{\alpha_{3}}=\ket{1}$. Since
$\ket{\alpha_{2}}=\ket{0}$, global orthogonality requires
$\ket{\beta_{2}}=\ket{1}$. Likewise,
$\ket{\beta_{3}}=\ket{\beta_{1}^{\perp}}$.

  3. 3.

$\ket{\alpha_{2}}=\ket{1}$, $\ket{\alpha_{3}}=\ket{0}$. This is the same
argument as the previous item.

  4. 4.

$\ket{\alpha_{2}}=\ket{1}=\ket{\alpha_{3}}$. This is the same argument as item
one.

Thus, up to a choice of labeling, we have the set of states must be

$\\{\ket{0}^{A}\ket{1}^{B},\ket{1}^{A}\ket{\beta_{1}}^{B},\ket{0}^{A}\ket{1}^{B},\ket{1}^{A}\ket{\beta_{1}^{\perp}}^{B}\\}\
.$

Note that $\ket{\beta_{1}},\ket{\beta_{1}^{\perp}}$ must form a basis of
$\mathbb{C}^{2}$. This means we can parameterize them as promised in the lemma
statement. ∎

With this structure identified, we turn to establishing the error bounds. It
will be clearer to use the following immediate simplification of Theorem 2,
which just follows from trigonometric identities.

######  Corollary 4 (UR for Two Qubit GOP).

Consider possibly unnormalized vectors
$\ket{\gamma_{0}}^{AB},\ket{\gamma_{1}}^{AB}$ such that
$F(\gamma_{0}^{A},\gamma_{1}^{A})\leq\delta$. If
$\ket{\gamma_{\theta}}^{AB}=\cos(\theta/2)\ket{\gamma_{0}}^{AB}+e^{i\phi}\sin(\theta/2)\ket{\gamma_{1}}^{AB}$
and
$\ket{\gamma_{\overline{\theta}}}^{AB}=\sin(\theta/2)\ket{\gamma_{0}}^{AB}+e^{i\phi}\cos(\theta/2)\ket{\gamma_{1}}^{AB}$,
then

$\displaystyle
D_{\text{tr}}(\gamma_{\theta}^{B},\gamma_{\overline{\theta}}^{B})$
$\displaystyle\leq|\cos(\theta)|D_{\text{tr}}(\gamma_{0}^{B},\gamma_{1}^{B})$
(23) $\displaystyle\hskip
14.22636pt+|\sin(\theta)|(1-D_{\text{tr}}^{2}(\gamma_{0}^{A},\gamma_{1}^{A}))\
.$

We can now state the error bounds.

######  Theorem 5 (Error Bounds of Two Qubit GOPs).

Consider the GOP ensemble

$\left\\{\frac{p}{2}\ket{0}\ket{0},\frac{p}{2}\ket{0}\ket{1},\frac{1-p}{2}\ket{1}\ket{\hat{n}},\frac{1-p}{2}\ket{1}\ket{-\hat{n}}\right\\}\
,$

where $p\in[0,1]$ can be thought of as the probability of a basis choice.
Then,

$\displaystyle\Pr_{\text{LOSQC}}[\text{win}](p,\theta)$ $\displaystyle\leq$
$\displaystyle\begin{cases}p+(1-p)\frac{|\cos(\theta)|}{2}&p\leq\zeta(p,\theta)\\\
p\cdot\left(\frac{1}{2}+\frac{-p+\alpha(p,\theta)}{\beta(p,\theta)}\right)+(1-p)&\text{
otherwise }\ ,\end{cases}$

where $\zeta(p,\theta)=\frac{1}{2}(1-(1-p)|\cos(\theta)|)$ and

$\displaystyle\alpha(p,\theta)$
$\displaystyle=\sqrt{y^{2}(p,\theta)-4w(p,\theta)z(p,\theta)}$
$\displaystyle\beta(p,\theta)$ $\displaystyle=4(1-p)|\sin(\theta)|$
$\displaystyle w(p,\theta)$ $\displaystyle=2(1-p)|\sin(\theta)|$
$\displaystyle y(p,\theta)$ $\displaystyle=p-2(1-p)|\sin(\theta)|$
$\displaystyle z(p,\theta)$
$\displaystyle=\frac{1}{2}(1-3p-(1-p)|\cos(\theta)|)\ .$

###### Proof.

We start with our ensemble
$\\{\ket{0}^{A}\ket{0}^{B},\ket{0}^{A}\ket{1}^{B},\ket{1}^{A}\ket{\hat{n}}^{A},\ket{1}^{A}\ket{-\hat{n}}^{A}\\}$.
Then Bob applies any isometry $V^{B\to A^{\prime}B^{\prime}}$ and sends the
$A^{\prime}$ system to Alice. In the meantime, Alice sends whether her state
was $0$ or $1$ to Bob. This means, given the linearity of an isometry, the
ensemble is now

$\\{\ket{0}_{A}\ket{\gamma_{0}}_{A^{\prime}B^{\prime}},\ket{1}_{A}\ket{\gamma_{\theta}}_{A^{\prime}B^{\prime}},\ket{0}_{A}\ket{\gamma_{1}}_{A},\ket{1}_{A}\ket{\gamma_{\overline{\theta}}}_{A^{\prime}B^{\prime}}\\}\
,$

which means we have the type of vectors covered by Corollary 4. Now Alice and
Bob both know locally if they are discriminating between
$\ket{\gamma_{0}},\ket{\gamma_{1}}$ or
$\ket{\gamma_{\theta}},\ket{\gamma_{\overline{\theta}}}$. Thus, we can think
of them as each having two POVMs conditioned on the basis. Therefore w.l.o.g.,

$\displaystyle\Pr[\text{win}]$ $\displaystyle=$
$\displaystyle\max_{V}\Bigg{\\{}p\max_{\\{P^{0}_{k}\\},\\{Q^{0}_{k}\\}}\Big{(}\frac{1}{2}\Pr[P_{0}^{0}\otimes
Q^{0}_{0}\gamma_{0}]$ $\displaystyle\hskip
113.81102pt+\frac{1}{2}\Pr[P_{1}^{0}\otimes Q^{0}_{1}\psi_{1}]\Big{)}$
$\displaystyle\hskip
28.45274pt+(1-p)\max_{\\{P^{1}_{k}\\},\\{Q^{1}_{k}\\}}\Big{(}\frac{1}{2}\Pr[P_{\theta}^{1}\otimes
Q^{1}_{\theta}\psi_{\theta}]$ $\displaystyle\hskip
113.81102pt+\frac{1}{2}\Pr[P_{\overline{\theta}}^{1}\otimes
Q_{\overline{\theta}}^{1}\psi_{\overline{\theta}}]\Big{)}\Bigg{\\}}$
$\displaystyle\leq$ $\displaystyle\max_{V}\min_{i\in\\{A,B\\}}\left[p\cdot
p_{g,i}^{0,1}+(1-p)\cdot p_{g,i}^{2,3}\right]\ ,$

where $p_{g,i}^{j,k}$ is the optimal guessing probability of party $i$ to
discriminate states $j,k$ given their portion of the state (which is a
function of $V$). This just follows from the probability they both guess
correctly with the global state is upper bounded by the probability one of
them is locally correct.

Now if we had no constraints on the $p_{g,i}^{j,k}$ terms, we could only
trivially upper bound this. However, as noted $V$ results in an ensemble of
the form of the previous lemma. Now, by Holevo-Helstrom,
$p_{g,i}^{j,k}=\frac{1}{2}\left(1+D_{\text{tr}}(\gamma_{j}^{i},\gamma_{k}^{i})\right)\Leftrightarrow
D_{\text{tr}}(\gamma_{j}^{i},\gamma_{k}^{i})=2p_{g,i}^{j,k}-1$. Thus, we can
use this to re-express (23):

$\displaystyle p_{g,B}^{2,3}$
$\displaystyle\leq\frac{1}{2}\Big{[}|\cos(\theta)|\left(2p_{g,B}^{0,1}-1\right)$
$\displaystyle\hskip
42.67912pt+|\sin(\theta)|\left(1-(2p_{g,A}^{0,1}-1)^{2}\right)+1\Big{]}\ .$

This presents a constraint on these winning probabilities. Labeling the
probabilities $a=p_{g,A}^{0,1}$, $b=p_{g,A}^{2,3}$, $c=p_{g,B}^{0,1}$, and
$d=p_{g,B}^{2,3}$, one may express $\Pr[\text{win}](p,\theta)$ as following
convex optimization problem

$\displaystyle\max$ $\displaystyle\min\\{pa+(1-p)b,pc+(1-p)d\\}$ s.t.
$\displaystyle\;\;d\leq\frac{1}{2}\left[|\cos(\theta)|(2c-1)+|\sin(\theta)|(1-(2a-1)^{2})+1\right]$
$\displaystyle\;\;0\leq a,b,c,d\leq 1\ .$

Noting that the objective function monotonically increases in $d$, we can make
the inequality an equality. Now note that $d$ monotonically increases in $c$,
as does the objective function. Thus $c=1$. Similarly, the objective function
monotonically increases in $b$, so we may let $b=1$. This reduces $d$ to being
a function of $a$, so we can simplify to:

$\displaystyle\max_{a\in[0,1]}$ $\displaystyle\min\\{f(a),g(a)\\}\ ,$

where $f(a):=pa+(1-p)$ and

$g(a):=p+\frac{1-p}{2}\left[|\cos(\theta)|+|\sin(\theta)|(1-(2a-1)^{2})+1\right]\
.$

Now note $f(a)$ monotonically grows in $a$ and $g(a)$ is symmetric about
$a=1/2$. Thus, without loss of generality we can restrict to $a\in[1/2,1]$.
Now there are two cases. The first case is $f(1/2)\geq g(1/2)$, in which case
increasing $a$ will only decrease the value of $g(\cdot)$, so $g(1/2)$ is the
optimal value. Therefore, we just need to solve for when this is the case:

$\displaystyle p/2+(1-p)\geq p+\frac{1-p}{2}\left[|\cos(\theta)|+1\right]$
$\displaystyle\Leftrightarrow$
$\displaystyle\frac{1}{2}(1-(1-p)|\cos(\theta)|)\geq p\ .$

Since this is a function of two parameters, we stop here for this case.

The other case is when $f(1/2)<g(1/2)$. In this case, increasing $a$ results
in decreasing the $g(\cdot)$ value but increasing $f(\cdot)$, so we can
increase $a$ to the point $f(a^{\prime})=g(a^{\prime})$, which is then the
maximum. Therefore, we want to solve for $a$ such that $f(a)-g(a)=0$. One may
express $f(a)-g(a)=wa^{2}+ya+z$ where $w=2(1-p)|\sin(\theta)|$,
$y=p-2(1-p)|\sin(\theta)|$, and $z=\frac{1}{2}(1-3p-(1-p)|\cos(\theta)|)$. By
the quadratic formula, one gets

$\displaystyle
a_{\pm}=\frac{1}{2}+\left(4(1-p)|\sin(\theta)|\right)^{-1}\left(-p\pm\sqrt{(y^{2}-4wz)}\right)\
,$

where clearly $a_{+}\geq a_{-}$, so $a^{\star}=a_{+}$. Since attempting to
simplify $y^{2}-4wz$ makes it no simpler and will result in a very long
equation, we leave it as is in the theorem statement. ∎

We plot the bounds from Theorem 5 in Fig. 3. We note these bounds are not
tight as the analytic value of
$\Pr_{\text{LOSQC}}[\text{win}](1/2,\pi/2)=\frac{1}{2}(1+\frac{1}{\sqrt{2}})$
[3, 16], whereas our results obtain a value of $\approx 0.91$ in this setting.
This is not surprising as our proof method reduces minimizing the joint
correctness to the minimum local correctness under an uncertainty relation.

Figure 3: Plot of the winning bounds from Theorem 5.

An immediate corollary of Theorem 5 either by inspection of Fig. 3 or a
simplification of Theorem 2 is that
$\Pr_{\text{LOSQC}}[\text{win}](p,\theta)<1$ for any $\theta\neq 0$. However,
in that case LOSCC can also perfectly discriminate the states (Corollary 1).

######  Corollary 5.

The set of GOP states that are perfectly discriminable under LOSQC and LOSCC
are equivalent in $\mathbb{C}^{2}\otimes\mathbb{C}^{2}$.


* Li et al. (2020b) Li, H., Lin, Z., and Fang, Y.  Variance reduced EXTRA and DIGing and their optimal acceleration for strongly convex decentralized optimization.  _preprint arXiv:2009.04373_ , 2020b.
  * Li et al. (2020c) Li, T., Sahu, A. K., Talwalkar, A., and Smith, V.  Federated learning: Challenges, methods, and future directions.  _IEEE Signal Processing Magazine_ , 37(3):50–60, 2020c.
  * Li et al. (2019) Li, Z., Shi, W., and Yan, M.  A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates.  _IEEE Transactions on Signal Processing_ , 67(17):4494–4506, 2019.
  * Lian et al. (2017) Lian, X., Zhang, C., Zhang, H., Hsieh, C.-J., Zhang, W., and Liu, J.  Can decentralized algorithms outperform centralized algorithms? A case study for decentralized parallel stochastic gradient descent.  In _Advances in Neural Information Processing Systems (NIPS)_ , pp. 5330–5340, 2017.
  * Lin et al. (2020) Lin, Z., Li, H., and Fang, C.  _Accelerated Optimization in Machine Learning: First-Order Algorithms_.  Springer, 2020.
  * Lorenzo & Scutari (2016) Lorenzo, P. D. and Scutari, G.  NEXT: In-network nonconvex optimization.  _IEEE Transactions on Signal and Information Processing over Networks_ , 2(2):120–136, 2016.
  * Makhdoumi & Ozdaglar (2017) Makhdoumi, A. and Ozdaglar, A.  Convergence rate of distributed ADMM over networks.  _IEEE Transactions on Automatic Control_ , 62(10):5082–5095, 2017.
  * Maros & Jalden (2018) Maros, M. and Jalden, J.  PANDA: A dual linearly converging method for distributed optimization over time-varying undirected graphs.  In _IEEE Conference on Decision and Control (CDC)_ , pp. 6520–6525, 2018.
  * Maros & Jalden (2019) Maros, M. and Jalden, J.  Eco-panda: A computationally economic, geometrically converging dual optimization method on time-varying undirected graphs.  In _IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , pp. 5257–5261, 2019.
  * Nedić (2011) Nedić, A.  Asynchronous broadcast-based convex optimization over a network.  _IEEE Transactions on Automatic Control_ , 56(6):1337–1351, 2011.
  * Nedić & Olshevsky (2015) Nedić, A. and Olshevsky, A.  Distributed optimization over time-varying directed graphs.  _IEEE Transactions on Automatic Control_ , 60(3):601–615, 2015.
  * Nedić & Olshevsky (2016) Nedić, A. and Olshevsky, A.  Stochastic gradient-push for strongly convexfunctions on time-varying directed graphs.  _IEEE Transactions on Automatic Control_ , 61(12):3936–3947, 2016.
  * Nedić & Ozdaglar (2009) Nedić, A. and Ozdaglar, A.  Distributed subgradient methods for multi-agent optimization.  _IEEE Transactions on Automatic Control_ , 54(1):48–61, 2009.
  * Nedić et al. (2017) Nedić, A., Olshevsky, A., and Shi, W.  Achieving geometric convergence for distributed optimization over time-varying graphs.  _SIAM Journal on Optimization_ , 27(4):2597–2633, 2017.
  * Nesterov (2004) Nesterov, Y.  _Introductory Lectures on Convex Optimization: A Basic Course_.  Kluwer Academic, Boston, 2004.
  * Qu & Li (2018) Qu, G. and Li, N.  Harnessing smoothness to accelerate distributed optimization.  _IEEE Transactions on Control of Network Systems_ , 5(3):1245–1260, 2018.
  * Qu & Li (2020) Qu, G. and Li, N.  Accelerated distributed Nesterov gradient descent.  _IEEE Transactions on Automatic Control_ , 65(6):2566–2581, 2020.
  * Ram et al. (2010) Ram, S. S., Nedić, A., and Veeravalli, V. V.  Distributed stochastic subgradient projection algorithms for convex optimization.  _Journal of Optimization Theory and Applications_ , 147:516–545, 2010.
  * Rogozin et al. (2020) Rogozin, A., Lukoshkin, V., Gasnikov, A., Kovalev, D., and Shulgin, E.  Towards accelerated rates for distributed optimization over time-varying networks.  _preprint arXiv:2009.11069_ , 2020.
  * Rogozin et al. (2021) Rogozin, A., Bochko, M., Dvurechensky, P., Gasnikov, A., and Lukoshkin, V.  An accelerated method for decentralized distributed stochastic optimization over time-varying graphs.  _preprint arXiv:2103.15598_ , 2021.
  * Saadatniaki et al. (2020) Saadatniaki, F., Xin, R., and Khan, U. A.  Decentralized optimization over time-varying directed graphs with row and column-stochastic matrices.  _IEEE Transactions on Automatic Control_ , 65(11):4769–4780, 2020.
  * Scaman et al. (2017) Scaman, K., Bach, F., Bubeck, S., Lee, Y. T., and Massoulié, L.  Optimal algorithms for smooth and strongly convex distributed optimization in networks.  In _International Conference on Machine Learning (ICML)_ , pp. 3027–3036, 2017.
  * Scaman et al. (2018) Scaman, K., Bach, F., Bubeck, S., Lee, Y. T., and Massoulié, L.  Optimal algorithms for non-smooth distributed optimization in networks.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , pp. 2740–2749, 2018.
  * Scaman et al. (2019) Scaman, K., Bach, F., Bubeck, S., Lee, Y. T., and Massoulié, L.  Optimal convergence rates for convex distributed optimization in networks.  _Journal of Machine Learning Research_ , 20(159):1–31, 2019.
  * Scutari & Sun (2019) Scutari, G. and Sun, Y.  Distributed nonconvex constrained optimization over time-varying digraphs.  _Mathematical Programming_ , 176:497–544, 2019.
  * Shi et al. (2015a) Shi, W., Ling, Q., Wu, G., and Yin, W.  A proximal gradient algorithm for decentralized composite optimization.  _IEEE Transactions on Signal Processing_ , 63(23):6013–6023, 2015a.
  * Shi et al. (2015b) Shi, W., Ling, Q., Wu, G., and Yin, W.  EXTRA: An exact first-order algorithm for decentralized consensus optimization.  _SIAM Journal on Optimization_ , 25(2):944–966, 2015b.
  * Stich (2019) Stich, S. U.  Local SGD converges fast and communicates little.  In _International Conference on Learning Representations (ICLR)_ , 2019.
  * Terelius et al. (2011) Terelius, H., Topcu, U., and Murray, R. M.  Decentralized multi-agent optimization via dual decomposition.  _IFAC proceedings volumes_ , 44(1):11245–11251, 2011.
  * Tseng (2008) Tseng, P.  On accelerated proximal gradient methods for convex-concave optimization.  Technical report, University of Washington, Seattle, 2008.
  * Tsitsiklis et al. (1986) Tsitsiklis, J. N., Bertsekas, D. P., and Athans, M.  Distributed asynchronous deterministic and stochastic gradient optimization algorithms.  _IEEE Transaction on Automatic Control_ , 31(9):803–812, 1986.
  * Uribe et al. (2021) Uribe, C. A., Lee, S., Gasnikov, A., and Nedić, A.  A dual approach for optimal algorithms in distributed optimization over networks.  _Optimization Methods and Software_ , 36(1):171–210, 2021.
  * Xin et al. (2018) Xin, R., Khan, U. A., and Kar, S.  A linear algorithm for optimization over directed graphs with geometric convergence.  _IEEE Control Systems Letters_ , 2(3):315–320, 2018.
  * Xu et al. (2015) Xu, J., Zhu, S., Soh, Y. C., and Xie, L.  Augmented distributed gradient methods for multi-agent optimization under uncoordinated constant stepsizes.  In _IEEE Conference on Decision and Control (CDC)_ , pp. 2055–2060, 2015.
  * Xu et al. (2020) Xu, J., Tian, Y., Sun, Y., and Scutari, G.  Accelerated primal-dual algorithms for distributed smooth convex optimization over networks.  In _IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , pp. 2381–2391, 2020.
  * Ye et al. (2020a) Ye, H., Luo, L., Zhou, Z., and Zhang, T.  Multi-consensus decentralized accelerated gradient descent.  _preprint arXiv:2005.00797_ , 2020a.
  * Ye et al. (2020b) Ye, H., Zhou, Z., Luo, L., and Zhang, T.  Decentralized accelerated proximal gradient descent.  In _Advances in Neural Information Processing Systems (NIPS)_ , 2020b.
  * Yuan et al. (2016) Yuan, K., Ling, Q., and Yin, W.  On the convergence of decentralized gradient descent.  _SIAM Journal Optimization_ , 26(3):1835–1854, 2016.