# The Quantum Advantage in Binary Teams and the Coordination Dilemma: Part II

Shashank A. Deshpande  Systems and Control Engineering, Indian Institute of
Technology Bombay, Mumbai 400076
Emails<EMAIL_ADDRESS><EMAIL_ADDRESS>Ankur A.
Kulkarni  Systems and Control Engineering, Indian Institute of Technology
Bombay, Mumbai 400076
Emails<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

In our previous work [1], we have shown that the use of a quantum architecture
in decentralised control allows access to a larger space of control strategies
beyond what is classically implementable through common randomness, and can
lead to an improvement in the cost – a phenomenon we called the quantum
advantage. In the previous part of this two part series, we showed, however,
that not all decision problems admit such an advantage. We identified a
decision-theoretic property of the cost called the ‘coordination dilemma’ as a
necessary condition for the quantum advantage to manifest. In this article, we
investigate the impact on the quantum advantage of a scalar parameter that
captures the extent of the coordination dilemma. We show that this parameter
can be bounded within an open interval for the quantum advantage to exist, and
for some classes, we precisely identify this range of values. This range is
found to be determined by the information of the agents.

##  I Introduction

While common randomness is a classically implementable means of generating
strategic distributions in decentralised control, it does not provide access
to all strategies allowed within the information structure of a problem [2].
We have shown that there exist implementable quantum strategies that leverage
quantum entanglement to access to some of the gap between what is
informationally allowed and what is classically implementable [1]. In
particular, we formulated _quantum_ strategies for static teams of
decentralised agents, where the agents’ actions are conditioned on outcomes of
strategically performed measurements on a shared quantum system, in addition
to their local information. This allows access of correlations beyond the
locally correlated ones and thus offers a strict cost improvement over a
classical decision set-up. For problems with static information structure, we
then portrayed that finding the quantum optimum requires an optimisation of a
linear objective over an abstractly specified convex, non-compact set of
quantum strategies.

Our idea indeed originates from the fact that the phenomenon of entanglement
in quantum mechanics allows for non-local correlations in systemic behaviour
among spatially decentralised systems. The non-locality of these correlations
is beyond what is achievable with classical systems. We refer the reader to
[3], [4] and [5] for more about non-local quantum correlations and their
applications to information processing.

Entanglement as of today, is a powerful but an expensive technological
resource. It is thus important to isolate a class of decision problems that
admit the quantum advantage. This motivates our decision-theoretic inquiry of
the origins of the quantum advantage in static teams. In the first part [6] of
this two part series of articles, we establish a decision-theoretic structure
called the _coordination dilemma_ as central to the manifestation of the
quantum advantage in a binary team superstructure. Our results thereby specify
a sharp decision theoretic boundary, problems outside which do not admit a
quantum advantage. In this article, we investigate within this boundary to
further shave-off such problems, and thus provide a bounding set containing
problems with the quantum advantage within our superstructure.

The extent of the coordination-dilemma in a problem instance is captured by a
scalar parameter $\chi$ in our superstructure. In our first result, we
identify a tight interval of values of $\chi$ corresponding to instances that
admit the no-signalling advantage. These intervals consequently contain the
entire set of instances that admit the quantum advantage, since all quantum
strategies respect the no-signalling constraints.

We also show that for the problems in our superstructure all quantum
strategies can be implemented using entangled systems with one qubit per
decision maker. This allows us to specify the set of quantum strategies
parametrically. We use this parametric set-up to investigate the quantum
advantage within a specific class of problems where both the agents record
equally informative observations of the natural state. We specify a tight
interval of values of $\chi$ which corresponds to all instances within this
class that admit a quantum advantage. We find that this interval is a strict
subset of the one that admits the no-signalling advantage, and thus the
presence of no-signalling advantage within a problem is an insufficient
condition for the quantum advantage to exist.

Our scrutiny of a binary team superstructure in this two part series of
articles thus presents some analytical insight into the association of the
quantum advantage in a control problem with its decision-theoretic character.

###  I-A Organization

This article is organised as follows. In Section II, we briefly recall the
team superstructure we work with, from Part 1, and introduce our inquisition
here. In Section III, we show sufficiency of strategies on entangled qubits
and develop a parametric characterisation for the reduced strategic space. In
Section IV, we isolate a bounded set of problem instances using the no-
signalling relaxations. In Section V, we perform an in-depth analysis of
problem instances within a problem class and deliver tight bounds on the
extent of the necessary _coordination dilemma_ for quantum advantage to appear
in this class.

##  II Problem Superstructure and the Coordination Dilemma

We briefly recollect the basic ideas from part I [6]. Our interest is in the
following superstructure of static binary team problems with agents $A,B$. For
$i\in\\{A,B\\}$, the set of actions available to agent $i$ is the ordered set
${\cal U}_{i}=(u_{i}^{0},u_{i}^{1})$ and the set of observations of the agent
is $\Xi_{i}=\\{0,1\\}$. The state of nature is specified as a tuple
$(\xi_{A},\xi_{B},\xi_{W})\in\Xi_{A}\times\Xi_{B}\times\Xi_{W}=\\{0,1\\}^{3}$
distributed according to a prior ${\mathbb{P}}\in{\cal
P}(\Xi_{A}\times\Xi_{B}\times\Xi_{W})$. Cost functions within our
superstructure are functions $\ell:{\cal U}_{A}\times{\cal
U}_{B}\times\Xi_{W}\to\\{0,-1,-\chi\\}$ constrained to obey
$\ell(u_{A},u_{B},0)\in\\{0,-1\\}$ and $\ell(u_{A},u_{B},1)\in\\{0,-\chi\\}$
for some parameter $\chi>0$. A problem instance $D$ in our superstructure can
thus be specified as a tuple $(M,N,{\mathbb{P}},{\cal U}_{A},{\cal
U}_{B},\chi)$ where $\chi>0$ is a parameter and $M,N$ are $2\times 2$ matrices
in $\\{0,-1\\}^{2\times 2}$ which capture the cost of $D$ as
$\ell(u_{A}^{i},u_{B}^{j},0)=[M]_{i+1\ j+1}$ and
$\ell(u_{A}^{i},u_{B}^{j},0)=\chi[N]_{i+1\ j+1}$. Our superstructure
partitions into $2^{8}=256$ different problem classes for different tuples
$V=(M,N)$, and we denote each such class by ${\cal C}(V)$.

A policy or a strategy $Q(.|.)\in{\cal P}({\cal U}_{A}\times{\cal
U}_{B}|\Xi_{A}\times\Xi_{B})$ is a conditional distribution of $u_{A}$,
$u_{B}$ and the space of such available distributions depends upon the class
of strategies being considered–classical ${\cal L}$, quantum ${\cal Q}$ and
no-signalling ${\cal N}{\cal S}$ are the ones relevant to most of our
discussion. A quantum advantage manifests in a problem instance if some policy
in ${\cal Q}$ attains a cost strictly lower than the optimal classical cost,
i.e. the cost of optimal policy in ${\cal L}$. A problem class is said to
admit a quantum advantage if and only if it contains a problem instance that
admits a quantum advantage. A no-signalling advantage is defined in a similar
fashion.

In our previous article [1], we demonstrated the existence of quantum
advantage in decentralised control through a decentalised estimation instance
within this superstructure. In the first part of this series [6], we
exhaustively scanned through the above superstructure and investigated the
presence of the quantum advantage in each of the problem classes. After
systematic elimination of classes that do not admit the no-signalling or the
quantum advantage, the following problem classes survive and are the centre of
our attention in this article.

1) The CAC class – ${\cal C}(V)$: $V=(M,N)=\left(\begin{pmatrix}1&0\\\
0&1\end{pmatrix},\begin{pmatrix}0&1\\\ 1&0\end{pmatrix}\right)$ and its
equivalent ${\cal C}(V^{\prime})$ where
$V^{\prime}:=(M^{\prime},N^{\prime}):=(\mathsf{R}M,\mathsf{R}N)$ for
$\mathsf{R}=\begin{pmatrix}0&1\\\ 1&0\end{pmatrix}$. We call the tuple $(M,N)$
here, the CAC form. We use the notation $V_{c}\equiv(M_{c},N_{c})$ to refer to
the CAC form throughout this article. We call the set $\\{{\cal
C}(V_{c}),{\cal C}(\mathsf{R}V_{c})\\}$ orbit of the CAC class.

2) The ${\textstyle{1\over 2}}$-CAC class – ${\cal C}(V)$:
$V=(M,N)=\begin{pmatrix}1&0\\\ 0&0\end{pmatrix},\begin{pmatrix}0&1\\\
1&0\end{pmatrix}$ and classes ${\cal C}(V^{\prime})$ for all
$V^{\prime}\in(V,\Omega)$ where

$(V,\Omega)=\\{V,\mathsf{R}V,V\mathsf{R},\mathsf{R}V\mathsf{R},\mathsf{E}V,\mathsf{R}(\mathsf{E}V),(\mathsf{E}V)\mathsf{R},\mathsf{R}(\mathsf{E}V)\mathsf{R}\\}$
(1)

for $\mathsf{R}=\begin{pmatrix}0&1\\\ 1&0\end{pmatrix}$ and
$\mathsf{E}V=\mathsf{E}(M,N)=(N,M)$. We refer to the tuple $(M,N)$ in the
${\textstyle{1\over 2}}$-CAC form with through the notation
$V_{\tiny\frac{1}{2}}=(M_{\tiny\frac{1}{2}},N_{\tiny\frac{1}{2}})$ hereafter.
The set of classes ${\cal C}((V_{\tiny\frac{1}{2}};\Omega))$ are called
classes in the orbit of the ${\textstyle{1\over 2}}$-CAC class.

Notice that the nature of the cost function in both CAC and
${\textstyle{1\over 2}}$-CAC classes makes it favourable for the agents to
concentrate the mass of their policy $Q(.|.)$ on the profiles
$\\{(u_{A}^{0},u_{B}^{0}),(u_{A}^{1},u_{B}^{1})\\}$ that correspond to the
agents matching the indices of their actions (or ‘coordinating’) when
$\xi_{W}=0$, and mismatch these indices (‘anticoordinate’) when $\xi_{W}=1$.
This feature seems to be central to an appearance of the quantum advantage for
classes in our superstructure and we refer to this feature as the coordination
dilemma. The relative importance of matching or mismatching the agents’
actions, i.e., the extent of the coordination dilemma is in some sense
captured by the cost parameter $\chi$ for each given prior on the agent’s
observations. In this article we ask the following question for each of the
two problem classes: given a prior on the agents’ observations, what values of
$\chi$ pose a coordination dilemma to the agents that is resolvable through
classical strategies just as well as the quantum strategies? Alternatively, we
seek to contain the values of $\chi$ that correspond to problem instances
which benefit from a quantum resource in each of the classes CAC and
${\textstyle{1\over 2}}$-CAC.

It is possible to simplify this structure of the set of quantum strategies in
binary teams. We present such a structural characterisation of the quantum
strategic space ${\cal Q}$ for binary teams in Section III. In particular, we
show that it is sufficient to consider strategies that correspond to
$\mathop{\hbox{\rm dim}}({\cal H}_{i})=2$ for $i=A,B$. This further allows us
to reduce the optimization problem $\inf_{Q\in{\cal Q}}J(Q;D)$ to a parametric
form.

##  III Structural characterisation of a quantum strategic space

A quantum strategy $Q$ is a conditional distribution on actions given the
observations specified by a tuple $({\cal H}_{A},{\cal H}_{B},\rho_{AB}$,
$\\{P_{u_{A}}^{A}(\xi_{A})\\},\\{P_{u_{B}}^{B}(\xi_{B})\\})$ where ${\cal
H}_{A}$ and ${\cal H}_{B}$ are finite dimensional Hilbert spaces, $\rho_{AB}$
is a positive operator on ${\cal H}:={\cal H}_{A}\otimes{\cal H}_{B}$ with
unit trace, and $P_{u_{i}}^{i}(\xi_{i})$ are projectors on ${\cal H}_{i}$ for
$i=A,B$. We refer the reader to [1] for a general treatise on the
implementation of quantum strategies in a control scenario. It is intractable
to investigate the presence and the extent of the quantum advantage in generic
teams due to the abstract, non-compact specification of the quantum strategic
space ${\cal Q}$. Naturally, the problem of characterizing the quantum infimum
and the corresponding cost $J^{*}_{\cal Q}(D):=\inf_{Q\in{\cal Q}}J(Q;D)$ is
difficult. Fortunately, in case of binary teams, as in our superstructure, we
are able to simplify this minimisation. Our main result here, greatly reduces
the difficulty of further analysis. The proofs of this section, being tedious,
have been deferrred to the appendix. Following heirarchy of strategic spaces
is an important element of our analysis in this section: ${\cal
Q}\supseteq{\cal Q}_{2}\supseteq\underline{{\cal
Q}}_{2}\supseteq\widehat{{\cal Q}}_{2}$ where
$\bullet$ ${\cal Q}_{2}$ corresponds to the class of quantum strategies where
each agent has an access to a two-dimensional quantum subsystem:

${\cal Q}_{2}:=\\{({\cal H}_{A},{\cal
H}_{B},\rho_{AB},\\{P_{u_{A}}^{(A)}(\xi_{A})\\},\\{P_{u_{B}}^{(B)}(\xi_{B})\\})\\\
|\mathop{\hbox{\rm dim}}({\cal H}_{i})|=2\ \forall i\in\\{A,B\\}\\}.$ (2)

$\bullet$ $\underline{{\cal Q}}_{2}$ corresponds to a subset of ${\cal Q}_{2}$
where the composite system shared among the agents is in a pure quantum state:

$\underline{{\cal Q}}_{2}:=\\{({\cal H}_{A},{\cal
H}_{B},\rho_{AB},\\{P_{u_{A}}^{(A)}(\xi_{A})\\},\\{P_{u_{B}}^{(B)}(\xi_{B})\\})|\\\
Q\in{\cal Q}_{2};\ \exists\ket{\psi_{AB}}\in{\cal H}_{A}\otimes{\cal
H}_{B}:\rho_{AB}=\ket{\psi_{AB}}\bra{\psi_{AB}}\\}.$ (3)

$\bullet$ $\widehat{{\cal Q}}_{2}$ is the union $\widehat{{\cal
Q}}_{2}:={\bigcup_{\alpha\in[0,\pi]}{{\cal Q}}^{\alpha}_{2}}$, where ${\cal
Q}^{\alpha}_{2}$ is the space of strategies with the composite system is in a
specific state $\rho_{AB}=\ket{\Phi^{\alpha}_{AB}}\bra{\Phi^{\alpha}_{AB}}$ as
follows:

${{\cal Q}}^{\alpha}_{2}:=\\{({\cal H}_{A},{\cal
H}_{B},\rho_{AB},\\{P_{u_{A}}^{(A)}(\xi_{A})\\},\\{P_{u_{B}}^{(B)}(\xi_{B})\\})|\\\
\mathop{\hbox{\rm dim}}{\cal H}_{A}=\mathop{\hbox{\rm dim}}{\cal H}_{B}=2;\
\rho_{AB}=\ket{\Phi^{\alpha}_{AB}}\bra{\Phi^{\alpha}_{AB}}\\},$ (4)
$\ket{\Phi^{\alpha}_{AB}}:=\cos{\nicefrac{{\alpha}}{{2}}}\ket{z^{+}_{A},z^{+}_{B}}+\sin{\nicefrac{{\alpha}}{{2}}}\ket{z^{-}_{A},z^{-}_{B}}.$
(5)

where we denote $\ket{z_{i}^{+}}:=(1,0)^{\top}$,
$\ket{z_{i}^{-}}:=(0,1)^{\top}$ and
$\ket{z_{A},z_{B}}=\ket{z_{A}}\otimes\ket{z_{B}}$.

Our main result in this section is that it suffices to optimise the expected
cost of an instance $D$ under strategy $Q$ over $\widehat{{\cal Q}}_{2}$ to
find an optimal quantum strategy, i.e.

$\inf_{Q\in{\cal Q}}J(Q;D)=\inf_{Q\in\widehat{{\cal Q}}_{2}}J(Q;D),$ (6)

for all instances $D$ in our superstructure. Consequently, we shall see that
the abstract optimization on the LHS of (6) reduces to a structured parametric
optimization on the RHS.

Recall that
$J(Q;D)=\sum_{u,\xi}{\mathbb{P}}(\xi)\ell(u,\xi_{W})Q(u|\xi_{A},\xi_{B})$ so
that $J(Q;D)$ is a linear objective in $Q$. Thus any infimum attained over a
set lies at an extreme point so that $\inf_{Q\in{\cal S}}J(Q;D)=\inf_{Q\in{\rm
conv}{\cal S}}J(Q;D)$ holds for all ${\cal S}\subset{\cal P}({\cal U}|\Xi)$.
In Theorem III.1, we establish that for binary teams the set of all quantum
strategies ${\cal Q}$ is the convex hull of qubit-implementable quantum
strategies ${\cal Q}_{2}$, i.e. ${\cal Q}={\rm conv}({\cal Q}_{2})$. Following
this in Proposition III.2, we in turn show that qubit-implementable strategies
are the convex hull of strategies implementable on pure qubit states, i.e.
${\cal Q}_{2}={\rm conv}(\underline{{\cal Q}}_{2})$ and that the equality
$\underline{{\cal Q}}_{2}=\widehat{{\cal Q}}_{2}$ holds. Equation (6) then
follows immediately.

###### Theorem III.1

Consider an instance $D=(M,N,{\mathbb{P}},{\cal U}_{A},{\cal U}_{B},\chi)$ and
let $J(Q;D)$ be the expected cost of $D$ under a strategy $Q$. Let ${\cal Q}$
be the set of all quantum strategies and ${\cal Q}_{2}\subset{\cal Q}$ as in
(2) be strategies implemented using one qubit per decision maker. We then have

  1. 1.

${\cal Q}={\rm conv}({\cal Q}_{2})$.

  2. 2.

$\inf_{Q\in{\cal Q}_{2}}J(Q;D)=\inf_{Q\in{\cal Q}}J(Q;D)$ for all instances
$D$ in our superstructure.

###### Proof:

See Appendix -A.

###### Proposition III.2

1) For the strategic spaces ${\cal Q}_{2}$, ${\rm conv}(\underline{{\cal
Q}}_{2})$ and $\widehat{{\cal Q}}_{2}$, the following two relations hold:
i) ${\cal Q}_{2}={\rm conv}(\underline{{\cal Q}}_{2})$; ii) $\underline{{\cal
Q}}_{2}=\widehat{\cal Q}_{2}$
2) It follows for an instance $D=(M,N,{\mathbb{P}},{\cal U}_{A},{\cal
U}_{B},\chi)$ that $\inf_{\widehat{{\cal Q}}_{2}}J(Q;D)=\inf_{Q\in{{\cal
Q}}}J(Q;D)$.

###### Proof:

See Appendix -B.

Proposition III.2 reduces our search for the optimal cost to $\widehat{{\cal
Q}}_{2}$ for any instance. Therefore in the subsection that follows, we
develop a parameterized specification of occupation measures
$Q(u_{A},u_{B}|\xi_{A},\xi_{B})$ corresponding to a strategy
$Q\in\widehat{\cal Q}_{2}$.

###  III-A Parametrization of strategies in $\widehat{\cal Q}_{2}$

For each $i\in\\{A,B\\}$, let $\theta_{i(\xi_{i})}$ and $\phi_{i(\xi_{i})}$ be
real parameters and define real unit vectors that correspond to them:

$\displaystyle a(\xi_{A})$
$\displaystyle=(\cos\theta_{a(\xi_{A})}\sin\phi_{a(\xi_{A})},\sin\theta_{a(\xi_{A})}\sin\phi_{a(\xi_{A})},\cos\phi_{a(\xi_{A})}),$
$\displaystyle b(\xi_{B})$
$\displaystyle=(\cos\theta_{b(\xi_{B})}\sin\phi_{b(\xi_{B})},\sin\theta_{b(\xi_{B})}\sin\phi_{b(\xi_{B})},\cos\phi_{b(\xi_{B})}).$

Now, using these real unit vectors, define corresponding orthonormal bases on
${\cal H}_{A}$ and ${\cal H}_{B}$ given by
$\\{\ket{a(\xi_{A})^{+}},\ket{a(\xi_{A})^{-}}\\}$ and
$\\{\ket{b(\xi_{B})^{+}},\ket{b(\xi_{B})^{-}}\\}$ where for $i\in\\{A,B\\}$,

$\displaystyle\ket{i(\xi_{i})^{+}}$
$\displaystyle=\cos({\nicefrac{{\phi_{i(\xi_{i})}}}{{2}}})\ket{z_{i}^{+}}+e^{\iota\theta_{i(\xi_{i})}}\sin({\nicefrac{{\phi_{i(\xi_{i})}}}{{2}}})\ket{z_{i}^{-}}$
(7) $\displaystyle\ket{i(\xi_{i})^{-}}$
$\displaystyle=-\sin({\nicefrac{{\phi_{i(\xi_{i})}}}{{2}}})\ket{z_{i}^{+}}+e^{\iota\theta_{i(\xi_{i})}}\cos({\nicefrac{{\phi_{i(\xi_{i})}}}{{2}}})\ket{z_{i}^{-}}.$

Further, define ‘action assignments’ as functions
$u^{+}_{i}(\xi_{i}),u^{-}_{i}(\xi_{i}):\Xi_{i}\to{\cal U}_{i}$. It follows
that since $|\Xi_{i}|=|{\cal U}_{i}|=2$ for $i\in\\{A,B\\}$, we have
$2^{8}=256$ distinct choices of the tuple
$(\\{u^{+}_{A}(\xi_{A}),u^{-}_{A}(\xi_{A})\\},\\{u^{+}_{B}(\xi_{B}),u^{-}_{B}(\xi_{B})\\})$
that specifes an action assignment. Further, let

$P_{u_{i}}^{(i)}(\xi_{i})=\begin{cases}\ket{i(\xi_{i})^{+}}\bra{i(\xi_{i})^{+}}&u_{i}=u_{i}^{+}(\xi_{i})\neq
u_{i}^{-}(\xi_{i})\\\
\ket{i(\xi_{i})^{-}}\bra{i(\xi_{i})^{-}}&u_{i}=u_{i}^{-}(\xi_{i})\neq
u_{i}^{+}(\xi_{i})\\\ {\bf I}&u_{i}=u_{i}^{-}(\xi_{i})=u_{i}^{+}(\xi_{i})\\\
0&\text{otherwise}\end{cases}$ (8)

so that we can specify an arbitrary strategy $Q\in\widehat{{\cal Q}}_{2}$ as a
tuple

$Q=(\alpha,\\{(\theta_{a(\xi_{A})},\phi_{a(\xi_{A})})\\},\\{(\theta_{b(\xi_{B})},\phi_{b(\xi_{B})})\\},\\\
\\{u^{+}_{A}(\xi_{A}),u^{-}_{A}(\xi_{A})\\},\\{u^{+}_{B}(\xi_{B}),u^{-}_{B}(\xi_{B})\\}).$
(9)

Notice that we have dropped the Hilbert spaces from the specification, as well
as replaced $\rho_{AB}=\ket{\Phi^{\alpha}}\bra{\Phi^{\alpha}}$ with $\alpha$.
Further through (8), the tuple
$(\\{(\theta_{a(\xi_{A})},\phi_{a(\xi_{A})})\\},\\{(\theta_{b(\xi_{B})},\phi_{b(\xi_{B})})\\},\\\
\\{u^{+}_{A}(\xi_{A}),u^{-}_{A}(\xi_{A})\\},\\{u^{+}_{B}(\xi_{B}),u^{-}_{B}(\xi_{B})\\})$
specifies the measurement strategy for $Q$. This puts us in a position to
explicitly compute the occupation measures in the following parametric form.

###### Proposition III.3

For $Q\in\widehat{\cal Q}_{2}$ specified as in (9), the conditional
probabilities $Q(u_{A}^{+}(\xi_{A}),u_{B}^{+}(\xi_{B})|\xi_{A},\xi_{B})$,
$Q(u_{A}^{+}(\xi_{A}),u_{B}^{+}(\xi_{B})|\xi_{A},\xi_{B})$,
$Q(u_{A}^{+}(\xi_{A}),u_{B}^{+}(\xi_{B})|\xi_{A},\xi_{B})$ and
$Q(u_{A}^{+}(\xi_{A}),u_{B}^{+}(\xi_{B})|\xi_{A},\xi_{B})$ are as tabulated in
the Table I below.

Occupation Measure | Parametric Form
---|---
$Q(u_{A}^{+}(\xi_{A}),u_{B}^{+}(\xi_{B})|\xi_{A},\xi_{B})$ | $\cos^{2}{\frac{\alpha}{2}}\cos^{2}{\frac{\phi_{a(\xi_{A})}}{2}}\cos^{2}\frac{\phi_{b(\xi_{B})}}{2}+\sin^{2}{\frac{\alpha}{2}}\sin^{2}{\frac{\phi_{a(\xi_{A})}}{2}}\sin^{2}\frac{\phi_{b(\xi_{B})}}{2}+\beta_{\alpha,\theta_{a(\xi_{A})},\theta_{b(\xi_{B})},\phi_{a(\xi_{A})},\phi_{b(\xi_{B})}}$
$Q(u_{A}^{+}(\xi_{A}),u_{B}^{-}(\xi_{B})|\xi_{A},\xi_{B})$ | $\cos^{2}{\frac{\alpha}{2}}\cos^{2}{\frac{\phi_{a(\xi_{A})}}{2}}\sin^{2}\frac{\phi_{b(\xi_{B})}}{2}+\sin^{2}{\frac{\alpha}{2}}\sin^{2}{\frac{\phi_{a(\xi_{A})}}{2}}\cos^{2}\frac{\phi_{b(\xi_{B})}}{2}-\beta_{\alpha,\theta_{a(\xi_{A})},\theta_{b(\xi_{B})},\phi_{a(\xi_{A})},\phi_{b(\xi_{B})}}$
$Q(u_{A}^{-}(\xi_{A}),u_{B}^{+}(\xi_{B})|\xi_{A},\xi_{B})$ | $\cos^{2}{\frac{\alpha}{2}}\sin^{2}{\frac{\phi_{a(\xi_{A})}}{2}}\cos^{2}\frac{\phi_{b(\xi_{B})}}{2}+\sin^{2}{\frac{\alpha}{2}}\cos^{2}{\frac{\phi_{a(\xi_{A})}}{2}}\sin^{2}\frac{\phi_{b(\xi_{B})}}{2}-\beta_{\alpha,\theta_{a(\xi_{A})},\theta_{b(\xi_{B})},\phi_{a(\xi_{A})},\phi_{b(\xi_{B})}}$
$Q(u_{A}^{-}(\xi_{A}),u_{B}^{-}(\xi_{B})|\xi_{A},\xi_{B})$ | $\cos^{2}{\frac{\alpha}{2}}\sin^{2}{\frac{\phi_{a(\xi_{A})}}{2}}\sin^{2}\frac{\phi_{b(\xi_{B})}}{2}+\sin^{2}{\frac{\alpha}{2}}\cos^{2}{\frac{\phi_{a(\xi_{A})}}{2}}\cos^{2}\frac{\phi_{b(\xi_{B})}}{2}+\beta_{\alpha,\theta_{a(\xi_{A})},\theta_{b(\xi_{B})},\phi_{a(\xi_{A})},\phi_{b(\xi_{B})}}$
TABLE I: Conditional Probabilities for strategy $Q\in\widehat{\cal Q}_{2}$
(Proposition III.3). Here
$\beta_{\alpha,\theta_{a(\xi_{A})},\theta_{b(\xi_{B})},\phi_{a(\xi_{A})},\phi_{b(\xi_{B})}}=\frac{1}{4}\sin\alpha\cos(\theta_{a(\xi_{A})}+\theta_{b(\xi_{B})})\sin\phi_{a(\xi_{A})}\sin\phi_{b(\xi_{B})}$

###### Proof:

Proof is by straightforward computation as we show in Appendix -C.

We will denote the set of parameters
$\alpha,\\{\theta_{i(\xi_{i})}\\},\\{\phi_{i(\xi_{i})}\\}$ as
$\alpha,\theta,\phi$ for notational brevity. Similarly we will use
$\\{u^{\pm}_{i}(\xi_{i})\\}_{i}$ to denote an action assignment. It is of some
interest to discuss a physical realization of strategies in $\widehat{\cal
Q}_{2}$ as it allows us to argue completeness of our search through a compact
range of the abovementioned parametrization. A detailed introduction to
dynamics and measurements of spin systems, along with the parametrization
provided by the Bloch sphere can be found in [7].

The spin state of an electron is described within a two-dimensional Hilbert
space. Suppose that each of the agents have access to an electron each for
respective spin measurements and that the agents share a common coordinate
system in physical space. Let the composite state of this electrons be
$\ket{\Phi_{AB}^{\alpha}}$. Then, the state $\ket{i(\xi_{i})^{+}}$ as
described by (7) represents an electron spin oriented along an axis
$i(\xi_{i})$ in the shared coordinate system on physical space of agents, and
consequently $\ket{i(\xi_{i})^{-}}$ represents an orientation along
$-i(\xi_{i})$. A measurement in the POVM
$\\{\ket{i(\xi_{i})^{+}}\bra{i(\xi_{i})^{+}},\ket{i(\xi_{i})^{-}}\bra{i(\xi_{i})^{-}}\\}$
consequently corresponds to a spin measurement by agent $i$ along the axis
$i(\xi_{i})$, while a measurement in the POVM $\\{{\bf I},0\\}$ leaves the
electron undisturbed. This realization admits an analogue for each strategy in
$\widehat{\cal Q}_{2}$. Hence, a search over $\phi\in[0,\pi]$ and
$\theta\in[0,2\pi]$ which covers all orientations or unit vectors in the
physical space is sufficient to cover all measurement bases in the two
dimensional Hilbert space. The parametrization discussed, along with the
finite number of action assignments consequently covers all possible
measurement strategies. These set of arguments render $\widehat{\cal Q}_{2}$
compact and the following proposition follows.

###### Proposition III.4

There is a strategy
$(\alpha,\\{\theta,\phi\\},\\{u^{\pm}_{i}(\xi_{i})\\})=:Q\in\widehat{{\cal
Q}}_{2}$ with $\theta\in[0,2\pi]$ and $\phi\in[0,\pi]$ that attains the
optimal quantum cost, i.e.

$J^{*}_{\cal Q}(D)=\inf_{\\{u^{\pm}_{i}(\xi_{i})\\}_{i},\
\alpha,\phi\in[0,\pi],\ \theta\in[0,2\pi]}J(Q;D)$ (10)

Further, owing to this correspondence with the discussed physical realization,
one can specialize the $z$ axis of the physical space along the axis $a(0)$
without loss of generality. Hence,

$\theta_{a0}^{*}=\phi_{a0}^{*}=0$ (11)

is an optimal solution of the problem (10). We further emphasize from (10)
that for every $\alpha\in[0,\pi],\theta,\phi\in\mathbb{R}$ that specify a
strategy $Q=(\alpha,\theta,\phi,\\{u_{i}^{\pm}(\xi_{i})\\}_{i})$, there exist
$\theta^{0}\in[0,2\pi],\phi^{0}\in[0,\pi]$ such that

$Q^{0}=(\alpha,\theta^{0},\phi^{0},\\{u^{\pm}_{i}(\xi_{i})\\})\equiv Q$ (12)

since one can always find such $\theta^{0}\in[0,2\pi],\phi^{0}\in[0,\pi]$ that
match the axial orientations of $i(\xi_{i})$ for each $i$ asserted by
$\theta,\phi\in\mathbb{R}$.

##  IV No-Signalling Advantage in CAC and ${\textstyle{1\over 2}}$-CAC orbits

We now probe the non-local advantages within the CAC and ${\textstyle{1\over
2}}$-CAC classes. In particular, notice that the parameter $\chi$ in the cost
function captures the degree of coordination dilemma faced by the decision
makers. It is natural to inquire if the existence of non-local advantage is
limited to a range of values of $\chi$. It is indeed intuitive to expect that
as $\chi\to 0$ that the players are are better of choosing a deterministic
coordination strategy $\gamma_{i}\equiv u_{i}^{0}\ (\pi^{0000})$ instead of
incurring the damage caused by randomization inherent to non-local strategies.
Similarly for $\chi\to\infty$, one intuitively expects a deterministic anti-
coordination strategy $\gamma_{A}\equiv u_{A}^{0},\gamma_{B}\equiv u_{B}^{1}\
(\pi^{0001})$ to outperform any of the no-signalling randomized strategies. In
this section, we specify explicit intervals of $\chi$ which subsume the no-
signalling advantage in CAC and 1/2-CAC problem classes

We briefly recall the strategic classes in our consideration – the local
polytope ${\cal L}$, the no-signalling polytope ${\cal N}{\cal S}$ and the
quantum ellitope ${\cal Q}$ from [6]. ${\cal L}$ is the convex hull of the set
$\Pi$ in the space of occupation-measures, where $\Pi$ is the simplex of all
deterministic strategies. ${\cal N}{\cal S}$ is specified by the set of
linear-equalities known as the no-signalling conditions that assert absence of
communication between $A$ and $B$. ${\cal Q}$ is the set of all quantum
strategies specified by states and projectors on finite dimensional Hilbert
spaces. We have this structure obeying ${\cal L}\subset{\cal Q}\subset{\cal
N}{\cal S}$. ${\cal L}$ shares all of its sixteen vertices with ${\cal N}{\cal
S}$. ${\cal N}{\cal S}$ has eight additional vertices which we call the non-
local vertices. The sixteen vertices shared by the two polytopes correspond to
local, deterministic strategies which constitute $\Pi$ and are denumerable as
(see Proposition 3.2 in [6])

$\pi^{\alpha\gamma\beta\delta}(u_{A}^{i},u_{B}^{j}|\xi_{A},\xi_{B})=\begin{cases}1&(i,j)=(\alpha\xi_{A}\oplus\beta,\gamma\xi_{B}\oplus\delta)\\\
0&\text{otherwise}\end{cases},$ (13)

where $\alpha,\beta,\gamma,\delta\in\\{0,1\\}$ and the eight non-local
vertices are denumerable as
$Q^{\alpha\beta\delta}(u_{A}^{i},u_{B}^{j}|\xi_{A},\xi_{B})=$

$\begin{cases}1/2&i\oplus
j=\xi_{A}.\xi_{B}\oplus\alpha.\xi_{A}\oplus\beta.\xi_{B}\oplus\delta\\\
0&\text{otherwise}\end{cases},$ (14)

The expected cost under a vertex $Q^{\alpha\beta\delta}$ is
$J(Q^{\alpha\beta\delta};D)=$

$-\frac{1}{2}\sum_{\xi_{A},\xi_{B},\xi_{W}}{\mathbb{P}}(\xi_{A},\xi_{B},\xi_{W})\ell(u_{A},u_{B},\xi_{W})\\\
\times(\sim\xi_{A}\cdot\xi_{B}\oplus\alpha\cdot\xi_{A}\oplus\beta\cdot\xi_{B}\oplus\delta)$
(15)

where $\alpha,\beta,\delta\in\\{0,1\\}$. We denote the expected cost of a
policy $Q$ given an instance $D$ by $J(Q;D)$. For $S\in\\{\Pi,{\cal L},{\cal
Q},{\cal N}{\cal S}\\}$, we use the notation $J_{S}^{*}(D):=\inf_{Q\in
S}J(Q;D)$. We say that the instance $D$ admits the quantum (no-signalling)
advantage if $J_{\cal Q}^{*}(D)<J_{{\cal L}}^{*}(D)$ ($J_{{\cal N}{\cal
S}}^{*}(D)<J_{{\cal L}}^{*}(D)$). Since $J(Q;D)$ is linear in $Q$, the infima
in ${\cal L}$ and ${\cal N}{\cal S}$ are attained at the vertices. Thus
$J_{{\cal L}}^{*}(D)=J_{\Pi}^{*}(D)$ and an instance $D$ admits a no-
signalling advantage if and only if
$\min_{\alpha,\beta,\delta\in\\{0,1\\}}J(Q^{\alpha\beta\delta};D)<\min_{\alpha,\gamma,\beta,\delta\in\\{0,1\\}}J(\pi^{\alpha\gamma\beta\delta};D).$
Following proposition provides the bounds on the range of values $\chi$ for
which an instance $D$ in CAC admits a no-signalling advantage. We then derive
such bounds for the other problem classes equivalent to CAC.

######  Proposition IV.1 (No-signalling advantage in CAC)

An instance $D=(M_{c},N_{c},{\mathbb{P}},{\cal U}_{A},{\cal U}_{B},\chi)$ in
CAC does not admit a no-signalling (and hence a quantum) advantage for values
of $\chi$ outside the interval $(\underline{\chi},\overline{\chi})$ where
$\underline{\chi},\overline{\chi}$ respectively are

$\min_{\alpha,\beta,\delta}\frac{\sum_{\xi_{A},\xi_{B}}{\mathbb{P}}(\xi_{A},\xi_{B},0)(\xi_{A}\cdot\xi_{B}\oplus\alpha\cdot\xi_{A}\oplus\beta\cdot\xi_{B}\oplus\delta)}{\sum_{\xi_{A},\xi_{B}}{\mathbb{P}}(\xi_{A},\xi_{B},1)(\xi_{A}\cdot\xi_{B}\oplus\alpha\cdot\xi_{A}\oplus\beta\cdot\xi_{B}\oplus\delta)},$
$\max_{\alpha,\beta,\delta}\frac{\sum_{\xi_{A},\xi_{B}}{\mathbb{P}}(\xi_{A},\xi_{B},0)(\sim\xi_{A}\cdot\xi_{B}\oplus\alpha\cdot\xi_{A}\oplus\beta\cdot\xi_{B}\oplus\delta)}{\sum_{\xi_{A},\xi_{B}}{\mathbb{P}}(\xi_{A},\xi_{B},1)(\sim\xi_{A}\cdot\xi_{B}\oplus\alpha\cdot\xi_{A}\oplus\beta\cdot\xi_{B}\oplus\delta)}.$

###### Proof:

Consider deterministic strategies $\pi^{0000}$ and $\pi^{0001}$. We have for
instance $D\in$ CAC, $\ell(u^{i}_{A},u^{j}_{B},0)=-(\sim i\oplus j)$ and
$\ell(u^{i}_{A},u^{j}_{B},1)=-\chi i\oplus j$ so that
$J(\pi^{0000};D)=-\sum_{\xi_{A},\xi_{B}}{\mathbb{P}}(\xi_{A},\xi_{B},0)$, and
$J(\pi^{0001};D)=-\chi\sum_{\xi_{A},\xi_{B}}{\mathbb{P}}(\xi_{A},\xi_{B},1)$.
It is straightforward to substitute $\ell(.)$ in (15) and conclude for all
$Q^{\alpha\beta\delta}$ that $J(\pi^{0001};D)-J(Q^{\alpha\beta\delta};D)\leq
0$ for all $\chi\geq\overline{\chi}$ and
$J(\pi^{0000};D)-J(Q^{\alpha\beta\delta})\leq 0$ for all
$\chi\leq\underline{\chi}.$

We now address the other instance in the orbit of CAC. With reference to proof
of Proposition 4.2 in [6], it has been shown that for
$D^{\prime}=(\mathsf{R}M_{c},\mathsf{R}N_{c},{\mathbb{P}},{\cal
U}^{\prime}_{A},{\cal U}_{B})$ with ${\cal
U}^{\prime}_{A}=\\{u_{A}^{1},u_{A}^{0}\\}$, $J(Q;D^{\prime})=J(Q;D)$ for all
strategies $Q$. Thus, $J_{S}^{*}(D)=J_{S}^{*}(D^{\prime})$ for $S\in\\{{\cal
L},{\cal N}{\cal S}\\}$. Consequently, $D^{\prime}$ does not admit the no-
signalling, and hence the quantum advantage outside the same interval
$(\underline{\chi},\overline{\chi})$.

We have similar bounds for instances in ${\textstyle{1\over 2}}$-CAC and the
problem classes in it’s orbit.

######  Proposition IV.2 (No-signalling advantage in ${\textstyle{1\over
2}}$-CAC)

An instance $D=(M_{\tiny\frac{1}{2}},N_{\tiny\frac{1}{2}},{\mathbb{P}},{\cal
U}_{A},{\cal U}_{B},\chi)$ in ${\textstyle{1\over 2}}$-CAC does not admit a
no-signalling (and hence a quantum) advantage outside the interval
$(\underline{\chi}_{{\tiny\frac{1}{2}}},\overline{\chi}_{{\tiny\frac{1}{2}}})$
where $\overline{\chi}_{\tiny\frac{1}{2}}=\overline{\chi}/2$ and
$\underline{\chi}_{{\tiny\frac{1}{2}}}:=$

$\min_{\alpha,\beta,\delta}\frac{\sum_{\xi_{A},\xi_{B}}{\mathbb{P}}(\xi_{A},\xi_{B},0)(1+\xi_{A}\cdot\xi_{B}\oplus\alpha\cdot\xi_{A}\oplus\beta\cdot\xi_{B}\oplus\delta)}{2\sum_{\xi_{A},\xi_{B}}{\mathbb{P}}(\xi_{A},\xi_{B},1)(\xi_{A}\cdot\xi_{B}\oplus\alpha\cdot\xi_{A}\oplus\beta\cdot\xi_{B}\oplus\delta)}$

###### Proof:

For instance $D\in$ ${\textstyle{1\over 2}}$-CAC, we have
$\ell(u^{i}_{A},u^{j}_{B},0)=-\sim(i\vee j)$ and
$\ell(u^{i}_{A},u^{j}_{B},1)=-\chi i\oplus j$. Consider deterministic
strategies
$\pi^{0000};J(\pi^{0000};D)=-\sum_{\xi_{A},\xi_{B}}{\mathbb{P}}(\xi_{A},\xi_{B},0)$
and
$\pi^{0001};J(\pi^{0001};D)=-\chi\sum_{\xi_{A},\xi_{B}}{\mathbb{P}}(\xi_{A},\xi_{B},1)$.
It is, as before, elementary to substitute $\ell(.)$ in (15) and conclude for
all $Q^{\alpha\beta\delta}$ that $J(\pi^{0001};D)-J(Q^{\alpha\beta\delta})\leq
0$ for all $\chi\geq\overline{\chi}_{{\tiny\frac{1}{2}}}$ and
$J(\pi^{0000};D)-J(Q^{\alpha\beta\delta})\leq 0$ for all
$\chi\leq\underline{\chi}_{{\tiny\frac{1}{2}}}$.

Remark:  Notice that since
$(1+\xi_{A}\cdot\xi_{B}\oplus\alpha\cdot\xi_{A}\oplus\beta\cdot\xi_{B}\oplus\delta)\geq
2\
\xi_{A}\cdot\xi_{B}\oplus\alpha\cdot\xi_{A}\oplus\beta\cdot\xi_{B}\oplus\delta$,
$\underline{\chi}_{\tiny\frac{1}{2}}\geq\underline{\chi}$, and recall
$\overline{\chi}_{\tiny\frac{1}{2}}=\overline{\chi}/2$. Thus,
$(\underline{\chi}_{\tiny\frac{1}{2}},\overline{\chi}_{\tiny\frac{1}{2}})\subset(\underline{\chi},\overline{\chi})$
and the no-signalling advantage for ${\textstyle{1\over 2}}$-CAC is subsumed
within a narrower interval than the interval that subsumes the no-signalling
advantage for CAC. $\square$

Now to attend the orbit of $V_{\tiny\frac{1}{2}}$, notice that instances
$D^{\prime}=(\mathsf{R}M_{\tiny\frac{1}{2}},\mathsf{R}N_{\tiny\frac{1}{2}},{\mathbb{P}},{\cal
U}^{\prime}_{A},{\cal U}_{B},\chi)$ and
$D^{\prime\prime}=(M_{\tiny\frac{1}{2}},N_{\tiny\frac{1}{2}},{\mathbb{P}},{\cal
U}_{A},{\cal U}^{\prime\prime}_{B},\chi)$ with ${\cal
U}_{A}^{\prime}=\\{u_{A}^{1},u_{A}^{0}\\}$ and ${\cal
U}_{B}^{\prime\prime}=\\{u_{B}^{1},u_{B}^{0}\\}$ obey
$J(Q;D^{\prime\prime})=J(Q;D^{\prime})=J(Q;D)$ with
$D=(M_{\tiny\frac{1}{2}}\mathsf{R},N_{\tiny\frac{1}{2}}\mathsf{R},{\mathbb{P}},{\cal
U}_{A},{\cal U}_{B},\chi)$ following proof of Proposition 4.2 in [6] as
before. Thus
$\mathsf{R}V_{\tiny\frac{1}{2}},V_{\tiny\frac{1}{2}}\mathsf{R},\mathsf{R}V_{\tiny\frac{1}{2}}\mathsf{R}$
do not admit the no-signalling and quantum advantage outside the interval
$(\underline{\chi}_{{\tiny\frac{1}{2}}},\overline{\chi}_{{\tiny\frac{1}{2}}})$.
Now consider ${\cal
C}(\mathsf{E}V_{\tiny\frac{1}{2}})\ni\widehat{D}=(N_{\tiny\frac{1}{2}},M_{\tiny\frac{1}{2}},\widehat{\mathbb{P}},{\cal
U}_{A},{\cal U}_{B},\widehat{\chi})$ where $\widehat{\mathbb{P}}$ is such that
$\widehat{\mathbb{P}}(\xi_{A},\xi_{B},0)={\mathbb{P}}(\xi_{A},\xi_{B},1)$,
$\widehat{\mathbb{P}}(\xi_{A},\xi_{B},1)={\mathbb{P}}(\xi_{A},\xi_{B},0)$ and
$\widehat{\chi}=1/\chi$. Notice then for any $Q$,
$\widehat{\ell}(\cdot,\cdot,0)\equiv\ell(\cdot,\cdot,1)/\chi,\widehat{\ell}(\cdot,\cdot,1)\equiv\ell(\cdot,\cdot,0)/\chi$
so that $J(Q;\widehat{D})=\frac{1}{\chi}J(Q;D)$.

Thus $\widehat{D}$ does not admit the no-signalling, and hence the quantum
advantage if $D$ does not. It follows that instances in ${\cal
C}(\mathsf{E}V_{\tiny\frac{1}{2}})$ do not admit the no signalling, and hence
quantum advantage outside interval
$({1}/{\overline{\chi}_{\tiny\frac{1}{2}}},{1}/{\underline{\chi}_{\tiny\frac{1}{2}}})$,
and so do not the instances in ${\cal
C}(\\{\mathsf{R}\mathsf{E}V_{\tiny\frac{1}{2}},\mathsf{E}V_{\tiny\frac{1}{2}}\mathsf{R},\mathsf{R}\mathsf{E}V_{\tiny\frac{1}{2}}\mathsf{R}\\})$
retracing arguments before. The intervals $(\underline{\chi},\overline{\chi})$
and $(\underline{\chi}_{\tiny\frac{1}{2}},\overline{\chi}_{\tiny\frac{1}{2}})$
provide a bounded set of instances within CAC and $\nicefrac{{1}}{{2}}$-CAC
respectively that subsume the instances which admit a quantum advantage since
$J^{*}_{{\cal N}{\cal S}}(D)=J^{*}_{{\cal L}}(D)\implies J^{*}_{{\cal
Q}}(D)=J^{*}_{{\cal L}}(D)$. We seek to exhaustively isolate instances that
admit a quantum advantage in the next section, albeit, for algebraic
simplicity,xs within a a subset of the CAC problem class.

##  V Quantum Advantage in CAC

In this section, we focus on the CAC class of instances and specialise to a
set of prior distributions that induce symmetric correlations between the
observations $\xi_{A}$ and $\xi_{B}$ and the natural state $\xi_{W}$. Notice
from (10) that, given an instance $D$, the optimization of the cost $J(Q;D)$
over the space of quantum policies has both, an element of discrete
optimization, involving an optimal choice of the action assignments
$u^{\pm}_{i}(\xi_{i})$, as well as an element of continuous optimization for
choice of the parameters $\alpha,\theta$ and $\phi$.

Our interest lies in isolation of instances $D$ where $J_{\cal
Q}^{*}(D)<J^{*}_{\cal L}(D)$. To approach such an isolation, we first resolve
the discrete element of the optimization problem in (10) in subsection below,
and obtain an optimal action assignment. This delivers a parametric form of an
optimal quantum strategy, and a minimization over the continuous space of
$\alpha,\theta,\phi$ remains. We subsequently address this and obtain
expressions for optimal $\theta$ in terms of parameters of the instance $D$,
and show, in particular, the optimality $\alpha=\pi/2$, which corresponds to a
maximally entangled state of two qubits. In the subsection that follows, we
isolate instances in the considered class of problems that admit a quantum
advantage.

###  V-A Parametric form of the Optimal Quantum Strategy

Recall from Proposition IV.1 that given a prior ${\mathbb{P}}$, the quantum
advantage for instances in CAC with values of $\chi$ is subsumed within the
interval $(\underline{\chi},\overline{\chi})$. We now specialise to the
following subclass of CAC where the agents’ observations are asymmetric but
equally informative and specify a tight interval of values for $\chi$, for
which the corresponding instances in the class admit the quantum advantage.

###### Definition V.1

We define sym-CAC as the set of all instances $D:(M,N,{\mathbb{P}},{\cal
U}_{A},{\cal U}_{B},\chi)\in$ CAC for which where the prior ${\mathbb{P}}$ is
specified through (16) for some $s,k,t\geq 0,2s+2k+4t=1;s>k$:

$\displaystyle{\mathbb{P}}(\xi,\xi,\xi)=s,\quad{\mathbb{P}}(\xi,\xi,\sim\xi)=k$
$\displaystyle{\mathbb{P}}(\xi,\sim\xi,\xi)={\mathbb{P}}(\sim\xi,\xi,\xi)=t,$
(16)

for each $\xi\in\\{0,1\\}$. This prior on states of nature corresponds to
scenarios where both agents’ observation is symmetrically correlated with the
state $\xi_{W}$ that appears in the cost function. Henceforth, we specify an
instance $D$ in sym-CAC as the tuple $(M,N,(s,k,t),{\cal U}_{A},{\cal
U}_{B},\chi)$. An important subset of instances in sym-CAC is the set of
priors that obey $s=\lambda^{2},k=(1-\lambda)^{2}$ and $t=\lambda(1-\lambda)$
for a $\lambda\in(\nicefrac{{1}}{{2}},1)$. This set represents independent,
i.i.d measurements for each agent $i\in\\{A,B\\}$ recorded according to the
probability law ${\mathbb{P}}(\xi_{i}=\xi_{W}|\xi_{W})=\lambda$. Behaviour of
the quantum advantage in this subset of instances has been numerically
investigated in [1]. It is easy to obtain by direct substitution, for any
instance in sym-CAC (or even CAC for that matter),

$\displaystyle J(Q;D)=-\chi{\mathbb{P}}(\xi_{W}=1)+$ (17)
$\displaystyle\sum_{\xi_{A},\xi_{B}}(\chi{\mathbb{P}}(\xi_{A},\xi_{B},1)-{\mathbb{P}}(\xi_{A},\xi_{B},0))Q(u_{A}=u_{B}|\xi_{A},\xi_{B})$
$\displaystyle=:-\chi{\mathbb{P}}(\xi_{W}=1)-\sum_{\xi_{A},\xi_{B}}\kappa(\xi_{A},\xi_{B})Q(u_{A}=u_{B}|\xi_{A},\xi_{B})$

where we have defined
$\kappa(\xi_{A},\xi_{B}):=\chi{\mathbb{P}}(\xi_{A},\xi_{B},1)-{\mathbb{P}}(\xi_{A},\xi_{B},0)$.
We identify the optimal classical strategies and corresponding costs for
instances in sym-CAC in the following proposition, which we prove in Appendix
-D.

###### Proposition V.1

We have for $D=(M,N,(s,k,t),{\cal U}_{A},{\cal U}_{B},\chi)\in$ sym-CAC ,

$\inf_{\pi\in\Pi}J(\pi,D)=\begin{cases}-\chi(s+k+2t)&\chi\in\left[\nicefrac{{s+t}}{{k+t}},\infty\right)\\\
-(1+\chi)(s+t)&\chi\in\left(\nicefrac{{k+t}}{{s+t}},\nicefrac{{s+t}}{{k+t}}\right)\\\
-(s+k+2t)&\chi\in(0,\nicefrac{{k+t}}{{s+t}}]\end{cases}$ (18)

where $\Pi$ is the set of all deterministic strategies.

Recall that we specify a strategy $Q\in\widehat{\cal Q}_{2}$ as a tuple as in
(9). Thus, optimisation of $J(Q;D)$ over the whole strategic space under
consideration requires (in general), search over all values of
$\alpha,\theta,\phi$ for each of the 256 action assignments in $\mathscr{U}$.
We now find an optimal action assignment for instances in sym-CAC.

###### Proposition V.2

Let
$Q_{0}(\alpha,\theta,\phi):=(\alpha,\theta,\phi,\\{v_{i}^{\pm}(\xi_{i})\\})$
denote a quantum policy with the action assignment $v_{i}^{+}(\xi_{i})\equiv
u_{i}^{0},\ v_{i}^{-}(\xi_{i})\equiv u_{i}^{1}$ for all $i=A,B$. Then the
assignment $\\{v^{\pm}_{i}(\xi_{i})\\}_{i}$ is optimal, i.e. for any instance
$D$ in CAC, and hence sym-CAC,
$\inf_{\alpha,\theta,\phi}J(Q_{0}(\alpha,\theta,\phi);D)=\inf_{Q\in\widehat{\cal
Q}}J(Q;D)$.

###### Proof:

The proof has been relegated to Appendix -E.

###### Theorem V.3

For instances $D\in$ sym-CAC, let
$(\alpha^{*},\phi^{*},\theta^{*})=\arg\inf_{(\alpha,\phi\in[0,\pi]\theta\in[0,2\pi])}J(Q_{0}^{\alpha};D)$.
Then $\alpha^{*}=\pi/2$ and $\theta^{*}_{i}(\xi_{i})$ are given by
$\theta_{a0}=0$, $\theta_{a1}=\pi$,

$\theta_{b0}=\begin{cases}0&\chi-1>0\\\
\pi&\chi-1<0\end{cases};\theta_{b1}=\begin{cases}0&s\chi-k>0\\\
\pi&s\chi-k<0.\end{cases}$ (19)

###### Proof:

Consider $J(Q_{0}^{\alpha};D)$ from (17) and notice from Table I that for all
$\xi_{A},\xi_{B}$: $Q(u_{A}=u_{B}|\xi_{A},\xi_{B})=$

$\displaystyle\cos^{2}{\nicefrac{{\phi_{a(\xi_{A})}}}{{2}}}\cos^{2}\nicefrac{{\phi_{b(\xi_{B})}}}{{2}}+\sin^{2}{\nicefrac{{\phi_{a(\xi_{A})}}}{{2}}}\sin^{2}\nicefrac{{\phi_{b(\xi_{B})}}}{{2}}$
$\displaystyle+\nicefrac{{1}}{{2}}\sin\alpha\cos(\theta_{a(\xi_{A})}+\theta_{b(\xi_{B})})\sin\phi_{a(\xi_{A})}\sin\phi_{b(\xi_{B})}$

The $\alpha,\theta$ dependence of the cost is subsumed within the term

$\frac{1}{2}\sum_{\xi_{A},\xi_{B}}\kappa(\xi_{A},\xi_{B})\sin\alpha\cos(\theta_{a(\xi_{A})}+\theta_{b(\xi_{B})})\sin\phi_{a(\xi_{A})}\sin\phi_{b(\xi_{B})}$

Since $\sin\phi_{i(\xi_{i})}>0$ for each $i$, it is now easy to notice how
$\alpha=\pi/2$ and
$\cos(\theta_{a(\xi_{A})}+\theta_{b(\xi_{B})})=-\mathop{\hbox{\rm
sign}}(\chi{\mathbb{P}}(\xi_{A},\xi_{B},1)-{\mathbb{P}}(\xi_{A},\xi_{B},0))$
are the minimising conditions. For $D\in$sym-CAC, using (16), these conditions
simplify to a solution $\theta_{a0}=0$, $\theta_{a1}=\pi$ and
$\theta_{b0},\theta_{b1}$ obeying (19) as asserted by our theorem. This
completes the proof.

###  V-B Thresholds for sym-CAC

In this section, we isolate the range of values of $\chi$ that admit a quantum
advantage for sym-CAC. Specialise to $\phi_{a0}=0$ as allowed by the
discussion around (11). For $\chi\in[1,s/k)$, notice from (19) that the
minimizing parameters are $\theta_{b0}=\theta_{b1}=0$, $\theta_{a1}=\pi$ and
$\alpha=\pi/2$ so that the cost of
$Q=Q_{0}^{\pi/2}=(\pi/2,\\{\phi,\theta\\},\\{v_{i}^{\pm}(\xi_{i})\\})$ assumes
the form (recall the optimal action assignments $v_{i}^{\pm}$ from Proposition
V.2), $\overline{J}(\chi,\phi_{a1},\phi_{b0},\phi_{b1}):=$

$\displaystyle-\chi(s+k+2t)+(\nicefrac{{\chi
t-t}}{{2}})(2+\cos\phi_{b1}+\cos(\phi_{a_{1}}+\phi_{b_{0}}))+$
$\displaystyle(\nicefrac{{\chi
s-k}}{{2}})(1+\cos(\phi_{a1}+\phi_{b1}))+(\nicefrac{{\chi
k-s}}{{2}})(1+\cos\phi_{b0})$ (20)

Similarly for $\chi\in(k/s,1)$, we have the minimizers
$\theta_{a0}=0,\theta_{a1}=\pi,\theta_{b0}=\pi$ and $\theta_{b1}=0$.
Corresponding cost $J(Q;D)$ is then of the form
$\underline{J}(\chi,\phi_{a1},\phi_{b0},\phi_{b1}):=$

$\displaystyle-\chi(s+k+2t)+(\nicefrac{{\chi
t-t}}{{2}})(2+\cos\phi_{b1}+\cos(\phi_{a_{1}}-\phi_{b_{0}}))+$
$\displaystyle(\nicefrac{{\chi
s-k}}{{2}})(1+\cos(\phi_{a1}+\phi_{b1}))+\nicefrac{{\chi
k-s}}{{2}}(1+\cos\phi_{b0})$ (21)

Thus using Theorem V.3, III.4 and V.2, we conclude $J_{{\cal Q}}^{*}(D)=$

$\min(\inf_{\phi}\overline{J}(\chi,\phi_{a1},\phi_{b0},\phi_{b1}),\inf_{\phi}\underline{J}(\chi,\phi_{a1},\phi_{b0},\phi_{b1})).$
(22)

This reduces an instance in sym-CAC to an optimization problem in three
parameters – $\phi_{a1},\phi_{b0}$ and $\phi_{b1}$. Denote the set of values
of $\chi$ for which an instance $D$ in sym-CAC admits quantum advantage by

${{\cal X}}:=\\{\chi\in\mathbb{R}^{+}|\inf_{Q\in{\cal
Q}}J(Q;D)<\inf_{\pi\in\Pi}J(\pi;D)\\}.$ (23)

By substituting (16) in Proposition IV.1, we have
$\overline{\chi}=\nicefrac{{s}}{{k}}$, $\underline{\chi}=\nicefrac{{k}}{{s}}$
whereby ${\cal X}\subset(\nicefrac{{k}}{{s}},\nicefrac{{s}}{{k}})$. In the
following Theorem, we exactly characterize ${\cal X}$.

###### Theorem V.4

An instance $D=(M,N,({s,k,t}),{\cal U}_{A},{\cal U}_{B})\in$ sym-CAC admits a
quantum advantage if and only if $\chi\in{\cal X}$. Moreover ${{\cal
X}}=(\chi_{th},\chi^{th})\setminus\\{1\\}$ and $\chi_{th}$ and $\chi^{th}$ are
given by

$\frac{s^{2}+k^{2}+(k+s)t}{2ks+(k+s)t}\mp\sqrt{\left(\frac{s^{2}+k^{2}+(k+s)t}{2ks+(k+s)t}\right)^{2}-1}.$

###### Proof:

See Appendix -F.

An important finding of Theorem V.4 is that the presence of the no-signalling
advantage does not guarantee the presence of a quantum advantage since
$\chi^{th}>\overline{\chi}$ and $\chi_{th}<\underline{\chi}$. We further note
that the Theorem V.4 analytically explains our numerical investigation in [1].
In particular, we plot Figure 2 in [1] by varying $\chi$ across instances
$D=(M,N,(s,k,t),{\cal U}_{A},{\cal U}_{B},\chi)\in$ sym-CAC with
$s=\lambda^{2},k=(1-\lambda)^{2}$ and $t=\lambda(1-\lambda)$ where
$\lambda=0.8$. We see that the quantum advantage is contained within an
interval $\chi\in(\chi_{th},\chi^{th})\equiv(0.16,6.34)$ and dissapears at
$\chi=1$.

##  VI Conclusion

We have identified, in Section IV, the necessary extent of the coordination
dilemma for a quantum advantage to manifest in the corresponding problem
instance. Further, in Section V, for a symmetric prior on the agents’
observations, a necessary and sufficient characterisation of this extent was
provided. Our results capture the coupled role of the agents’ information and
the cost function of the problem in determining the manifestation of a quantum
advantage in decentralised control.

Our analysis through this two-part series, although restricted to a binary
superstructure, offers some crucial intuition towards the nature of decision
and control problems that benefit from quantum architecture. The no-signalling
relaxation provides a generalizable approach to extract some structural
characteristics of such a nature through linear programming. The non-trivial
role of information in determining the quantum advantage is also intriguing.
We hope to further understand the same in more general setting through our
work that will follow.

## References

  * [1] Shashank A. Deshpande and Ankur A. Kulkarni.  The quantum advantage in decentralized control.  https://arxiv.org/abs/2207.12075, 2022.
  * [2] Venkat Ananthram and Vivek. Borkar.  Common randomness and distributed control: A counterexample.  Systems and Control Letters, 2007.
  * [3] Nicolas Brunner, Daniel Cavalcanti, Stefano Pironio, Valerio Scarani, and Stephanie Wehner.  Bell nonlocality.  Rev. Mod. Phys., 86:419–478, Apr 2014.
  * [4] Thew R. Gisin N.  Quantum communication.  Nature Photon, 1:165–171, 2007.
  * [5] Liao SK et al. Yin J, Li YH.  Entanglement-based secure quantum cryptography over 1,120 kilometres.  Nature, 582:501–505, 2020.
  * [6] Shashank A. Deshpande and Ankur A. Kulkarni.  Quantum advantage in binary teams and the coordination dilemma: Part I.  to be submitted, 2023.
  * [7] John Preskill.  Lecture notes for physics 229: Quantum information and computation.  California Institute of Technology, 16:37–40, 1998.
  * [8] Lluís Masanes.  Asymptotic violation of bell inequalities and distillability.  Phys. Rev. Lett., 97:050503, Aug 2006.
  * [9] Chuang Isaac L. Nielsen Michael A.  Quantum computation and quantum information.  Cambridge University Press, 2004.

###  -A Proof of Theorem III.1

Our proof borrows assistance from the following two results. The former is a
lemma in linear algebra due to Jordan, which has been proved in [8] (see lemma
on page 2). The latter is an embedding result for quantum strategies.

###### Lemma .1

(Jordan’s lemma) Let $P^{0}_{0}$, $P^{0}_{1}$, $P^{1}_{0}$ and $P^{1}_{1}$ be
projection operators on an $n$ dimensional Hilbert space ${\cal H}$ such that
$P^{0}_{0}+P^{0}_{1}=P^{1}_{0}+P^{1}_{1}={\bf I}.$ Then $P^{0}_{0}$,
$P^{0}_{1}$, $P^{1}_{0}$ and $P^{1}_{1}$ are simultaneously block
diagonalisable with each block of size at most two. i.e., there exists an
$n_{0}<n$ and an orthonormal basis
$\\{\ket{w_{j}},\ket{w_{-j}}\\}_{j=1}^{n_{0}}\cup\\{\ket{w_{j}}\\}_{j=2n_{0}+1}^{n}$
such that for each $S\in\\{P^{0}_{0},P^{0}_{1},P^{1}_{0},P^{1}_{1}\\}$, there
exist coefficients $\\{s_{qr}\\}$ such that

$S=\sum_{j=1}^{n_{0}}\sum_{q,r\in\\{-j,j\\}}s_{qr}\ket{w_{q}}\bra{w_{r}}+\sum_{j=2n_{0}+1}^{n}s_{jj}\ket{w_{j}}\bra{w_{j}}.$

######  Proposition .2 (An embedding for quantum strategies)

Let $Q=({\cal H}_{A},{\cal
H}_{B},\rho_{AB},\\{P_{u_{A}}^{(A)}(\xi_{A})\\},\\{P_{u_{B}}^{(B)}(\xi_{B})\\})$
be such that $\mathop{\hbox{\rm dim}}({\cal H}_{A})\leq m$ and
$\mathop{\hbox{\rm dim}}({\cal H}_{B})\leq n$. Then there exists a ${\cal
Q}\ni Q^{\prime}=({\cal H}^{\prime}_{A},{\cal
H}^{\prime}_{B},\rho^{\prime}_{AB},\\{P_{u_{A}}^{(A)\prime}(\xi_{A})\\},\\{P_{u_{B}}^{(B)\prime}(\xi_{B})\\})$
such that $\mathop{\hbox{\rm dim}}({\cal H}_{A})=m,\mathop{\hbox{\rm
dim}}({\cal H}_{B})=n$ and $Q\equiv Q^{\prime}$.

###### Proof:

Let $\mathop{\hbox{\rm dim}}({\cal H}_{A})=m_{0}\leq m$ and consider an
orthonormal basis $\\{\ket{w_{i}}\\}_{i=1}^{m}$ spanning ${\cal
H}_{A}^{\prime}$ with $\\{\ket{w_{i}}\\}_{i=1}^{m_{0}}$ spanning ${\cal
H}_{A}$. Similarly let $\mathop{\hbox{\rm dim}}({\cal H}_{B})=n_{0}\leq n$ and
consider an orthonormal basis $\\{\ket{v_{j}}\\}_{j=1}^{n}$ spanning ${\cal
H}_{B}^{\prime}$ with $\\{\ket{w_{j}}\\}_{j=1}^{n_{0}}$ spanning ${\cal
H}_{B}$. Let $\rho^{\prime}_{AB}\in{\cal H}_{A}^{\prime}\otimes{\cal
H}_{B}^{\prime}$ be such that
$\braket{w_{i},v_{j}}{\rho^{\prime}_{AB}}{w_{k},v_{\ell}}=\braket{w_{i},v_{j}}{\rho_{AB}}{w_{k},v_{\ell}}$
for $i,k\leq m_{0},j,\ell\leq n_{0}$ and
$\braket{w_{i},v_{j}}{\rho^{\prime}_{AB}}{w_{k},v_{\ell}}=0$ otherwise. Since
${\cal H}_{i}\subset{\cal H}_{i}^{\prime}$ for $i=A,B$, projectors
$P_{u_{i}}^{(i)}(\xi_{i})$ in ${\cal H}_{i}$ are also valid projectors in
${\cal H}_{i}^{\prime}$ so let
$P_{u_{i}}^{(i)\prime}(\xi_{i})=P_{u_{i}}^{(i)}(\xi_{i})$. It is now easy to
see that $\operatorname{Tr}(P_{u_{A}}^{(A)\prime}(\xi_{A})\otimes
P_{u_{B}}^{(B)\prime}(\xi_{B})\rho^{\prime}_{AB})=\operatorname{Tr}(P_{u_{A}}^{(A)}(\xi_{A})\otimes
P_{u_{B}}^{(B)}(\xi_{B})\rho_{AB})$ so that $Q^{\prime}\equiv Q$.

Now, we begin the proof of Theorem III.1.
1) We will show that any strategy $Q\in{\cal Q}$ can be written as a convex
combination $\sum_{j,k}a_{jk}Q^{jk}$, where $Q^{jk}\in{\cal Q}_{2}$ and
$a_{jk}\geq 0,\sum_{j,k}a_{jk}=1$.

Let $Q=({\cal H}_{A},{\cal
H}_{B},\rho_{AB},\\{P_{u_{A}}^{(A)}(\xi_{A})\\},\\{P_{u_{B}}^{(B)}(\xi_{B})\\})$
where ${\cal H}_{A}$ and ${\cal H}_{B}$ are $n$ and $m$ dimensional Hilbert
spaces respectively, $P_{u_{i}}^{i}(\xi_{i})$ are projection operators in
${\cal H}_{i}$ for each $\xi_{i}\in\\{0,1\\},i\in\\{A,B\\}$ and they satisfy
$P^{(i)}_{u_{i}^{0}}(0)+P^{(i)}_{u_{i}^{1}}(0)={\bf I}$ and
$P^{(i)}_{u_{i}^{0}}(1)+P^{(i)}_{u_{i}^{1}}(1)={\bf I}$. Define ${\cal
H}_{AB}={\cal H}_{A}\otimes{\cal H}_{B}$. We employ Lemma .1 with
$P^{\xi}_{i}\equiv P^{(A)}_{u^{i}_{A}}(\xi)$. There exists a basis
$\\{\ket{w_{j}},\ket{w_{-j}}\\}_{j=1}^{n_{0}}\cup\\{\ket{w_{j}}\\}_{j=2n_{0}+1}^{n}$
and coefficients $p_{ij}(u_{A},\xi_{A})$ such that with the specification
$p_{j-j}(u_{A},\xi_{A})=p_{-jj}(u_{A},\xi_{A})=p_{-j-j}(u_{A},\xi_{A})\equiv
0$ for $j>n_{0}$. Define $\ket{w_{-j}}=0$ for $j>2n_{0}$ and
$P_{u_{A}}^{A(j)}(\xi_{A}):=$

$\displaystyle
p_{jj}(u_{A},\xi_{A})\ket{w_{j}}\bra{w_{j}}+p_{j-j}(u_{A},\xi_{A})\ket{w_{j}}\bra{w_{-j}}$
(24)
$\displaystyle+p_{-jj}(u_{A},\xi_{A})\ket{w_{-j}}\bra{w_{j}}+p_{-j-j}(u_{A},\xi_{A})\ket{w_{-j}}\bra{w_{-j}}.$

Now for $N_{0}:=\\{1,...,n_{0}\\}\cup\\{2n_{0}+1,...,n\\}$, we express

$P_{u_{A}}^{A}(\xi_{A})=\sum_{j\in N_{0}}P_{u_{A}}^{A(j)}(\xi_{A}).$ (25)

Correspondingly for $m$ dimensional ${\cal H}_{B}$, one has a similar block-
diagonalizing orthonormal basis
$\\{\ket{v_{k}},\ket{v_{-k}}\\}_{k=1}^{m_{0}}\cup\\{\ket{v_{k}}\\}_{k=2m_{0}+1}^{m}$
so that there exist coefficients $q_{ij}(u_{B},\xi_{B})$ such that from Lemma
.1, with
$q_{k-k}(u_{B},\xi_{B})=q_{-kk}(u_{B},\xi_{B})=q_{-k-k}(u_{B},\xi_{B})\equiv
0$ for $k>m_{0}$. Now let $\ket{v_{-k}}=0$ for $k>2m_{0}$ and

$\displaystyle
P_{u_{B}}^{B(k)}(\xi_{B}):=q_{kk}(u_{B},\xi_{B})\ket{v_{k}}\bra{v_{k}}+q_{k-k}(u_{B},\xi_{B})\ket{v_{k}}\bra{v_{-k}}$
$\displaystyle+q_{-kk}(u_{B},\xi_{B})\ket{v_{-k}}\bra{v_{k}}+q_{-k-k}(u_{B},\xi_{B})\ket{v_{-k}}\bra{v_{-k}}.$
(26)

Defining $M_{0}:=\\{1,...,m_{0}\\}\cup\\{2m_{0}+1,...,m\\}$ allows us the
expression

$P_{u_{B}}^{B}(\xi_{B})=\sum_{k\in M_{0}}P_{u_{B}}^{B(k)}(\xi_{B}).$ (27)

$\rho_{AB}$ can be expressed as

$\rho_{AB}=\sum_{j\in N_{0}}\sum_{k\in M_{0}}r_{AB}^{jk}$ (28)

where $r_{AB}^{jk}$ denotes an operator of the form

$r_{AB}^{jk}=\sum_{i,p=\pm j}\sum_{l,q=\pm
k}r(i,l,p,q)\ket{w_{i},v_{l}}\bra{w_{p},v_{q}}.$

Since $\rho_{AB}\succeq 0$ we have $\operatorname{Tr}(r^{jk}_{AB})\geq 0$ for
all $j\in N_{0},k\in M_{0}$ as we have $\braket{w_{\pm j},v_{\pm
k}}{\rho_{AB}}{w_{\pm j},v_{\pm k}}=\braket{w_{\pm j},v_{\pm
k}}{r^{jk}_{AB}}{w_{\pm j},v_{\pm k}}\geq 0$. Let ${\cal H}_{A}^{j}=\mbox{\rm
span}\\{\ket{w_{j}},\ket{w_{-j}}\\}$ and ${\cal H}_{B}^{k}=\mbox{\rm
span}\\{\ket{v_{k}},\ket{v_{-k}}\\}$. Define an operator $\rho_{AB}^{jk}$ on
${\cal H}^{j}_{A}\times{\cal H}_{B}^{k}$ given by

$\rho_{AB}^{jk}:=\begin{cases}\operatorname{Tr}(r_{AB}^{jk})^{-1}r_{AB}^{jk}&r^{jk}_{AB}\neq
0\\\ 0&r^{jk}_{AB}=0\end{cases}$ (29)

We claim that $\rho_{AB}^{jk}$ is a density operator when $r^{jk}_{AB}\neq 0$.
Notice that $\operatorname{Tr}(\rho_{AB}^{jk})=1$ by definition and
$r^{*}(p,q,i,l)=r(i,l,p,q)$ for all $i,l,p,q$ since $\rho_{AB}$ in (28) is
Hermitian so that $\rho^{jk\dagger}_{AB}=\rho^{jk}_{AB}$. Finally,
$\rho_{AB}\succeq 0$ since $r^{jk}_{AB}\succeq 0$ and
$\operatorname{Tr}(r^{jk}_{AB})\geq 0$. Further, as defined by (24) and (26),
consider projectors $P_{u_{A}}^{A(j)}(\xi_{A})$ and
$P_{u_{B}}^{B(k)}(\xi_{B})$ in spaces ${\cal H}_{A}^{j}$ and ${\cal
H}_{B}^{k}$ respectively. Recall (25) and (27) and specify strategies
$Q^{jk}:=({\cal H}_{A}^{j},{\cal
H}_{B}^{k},\rho_{AB}^{jk},P_{u_{A}}^{A(j)}(\xi_{A}),P_{u_{B}}^{B(k)}(\xi_{B}))$
for $j\in N_{0},k\in M_{0}$. Now $1\leq\mathop{\hbox{\rm dim}}({\cal
H}_{A}^{j})=\mathop{\hbox{\rm dim}}({\cal H}^{k}_{B})\leq 2$ by construction
so from Proposition, we have $Q^{jk}\in{\cal Q}_{2}$, and notice from (25),
(27), (28) and (29) that
$Q(u_{A},u_{B}|\xi_{A},\xi_{B})=\operatorname{Tr}(P_{u_{A}}^{A}(\xi_{A})\otimes
P_{u_{B}}^{B}(\xi_{B})\rho_{AB})=$

$\displaystyle=\sum_{j,k}\operatorname{Tr}(P_{u_{A}}^{A(j)}(\xi_{A})\otimes
P_{u_{B}}^{B(k)}(\xi_{B})r^{jk}_{AB})$
$\displaystyle=\sum_{j,k}\operatorname{Tr}(r^{jk}_{AB})\operatorname{Tr}(P_{u_{A}}^{A(j)}(\xi_{A})\otimes
P_{u_{B}}^{B(k)}(\xi_{B})\rho^{jk}_{AB})$
$\displaystyle=\sum_{j,k}\operatorname{Tr}(r^{jk}_{AB})Q^{jk}(u_{A},u_{B}|\xi_{A},\xi_{B})$
(30)

Now $\operatorname{Tr}(r^{jk}_{AB})\geq 0$ and
$\sum_{jk}\operatorname{Tr}(r^{jk}_{AB})=\operatorname{Tr}(\rho_{AB})=1$
whereby $Q$ is a convex combination of strategies $Q^{jk}\in{\cal Q}_{2}$.
This completes the proof of the first part of the theorem.
2) First, note that the inequality $\inf_{Q\in{\cal
Q}_{2}}J(Q;D)\geq\inf_{Q\in{\cal Q}}J(Q;D)$ holds since ${\cal
Q}_{2}\subset{\cal Q}$. Suppose that the inequality is strict so that
$\inf_{Q\in{\cal Q}_{2}}J(Q;D)=\inf_{Q\in{\cal Q}}J(Q;D)+\delta$ where
$\delta>0$. But $\exists Q\in{\cal Q}$ such that $J(Q;D)\leq\inf_{Q\in{\cal
Q}}J(Q;D)+\delta/2$ by definition of an infimum. Expected cost is a linear
function of $Q$ so that from part 1) we have $Q$, $\exists a_{jk}>0,\sum
a_{jk}=1,Q^{jk}\in{\cal Q}_{2}$ such that
$J(Q;D)=\sum_{j,k}a_{jk}\sum_{\xi}\sum_{u}J(u,\xi)Q^{jk}(u|\xi)$. It follows
that $\min_{j,k}J(Q^{jk};D)\leq\inf_{Q\in{\cal
Q}}J(Q;D)+\delta/2<\inf_{Q\in{\cal Q}_{2}}J(Q;D)$ which is a contradiction. We
hereby conclude our proof of the Theorem III.1.

###  -B Proof of Proposition III.2

1) Let us attend our first claim: i) ${\cal Q}_{2}={\rm conv}(\underline{{\cal
Q}}_{2})$. Consider an arbitrary $Q=({\cal H}_{A},{\cal
H}_{B},\rho_{AB},\\{P_{u_{A}}^{(A)}(\xi_{A})\\},\\{P_{u_{B}}^{(B)}(\xi_{B})\\})\in{\cal
Q}_{2}$. Then there exist finitely many states (which we index by $i$ in some
finite range) $\ket{\psi_{i}}\in{\cal H}_{A}\otimes{\cal H}_{B}$ and
corresponding probabilities $p_{i}\geq 0,\sum p_{i}=1$ such that
$\rho_{AB}=\sum_{i}p_{i}\ket{\psi_{i}}\bra{\psi_{i}}.$ Now define

$Q_{i}:=({\cal H}_{A},{\cal
H}_{B},\ket{\psi_{i}}\bra{\psi_{i}},\\{P_{u_{A}}^{(A)}(\xi_{A})\\},\\{P_{u_{B}}^{(B)}(\xi_{B})\\})\in\underline{{\cal
Q}}_{2}.$

From the linearity of trace, $Q$ satisifies $Q(u_{A},u_{B}|\xi_{A},\xi_{B})=$

$\displaystyle\operatorname{Tr}\left(\rho_{AB}P_{u_{A}}^{(A)}(\xi_{A})P_{u_{B}}^{(B)}(\xi_{B})\right)=\sum_{i}p_{i}Q_{i}(u_{A},u_{B}|\xi_{A},\xi_{B}).$

Hence, $Q\in{\rm conv}(\underline{{\cal Q}}_{2})$ holds. The claim ${\cal
Q}_{2}={\rm conv}(\underline{{\cal Q}}_{2})$ follows since $Q$ was arbitrarily
chosen.
Towards ii) $\underline{{\cal Q}}_{2}=\widehat{\cal Q}_{2}$, consider any
$Q\in\underline{{\cal Q}}_{2}$:

$Q=({\cal H}_{A},{\cal
H}_{B},\ket{\psi_{AB}}\bra{\psi_{AB}},\\{P_{u_{A}}^{(A)}(\xi_{A})\\},\\{P_{u_{B}}^{(B)}(\xi_{B})\\})$

such that $\ket{\psi_{AB}}\in{\cal H}_{A}\otimes{\cal H}_{B}$. Let
$\\{\ket{z^{+}_{i}},\ket{z^{-}_{i}}\\}$ denote an orthonormal basis of ${\cal
H}_{i}$ for $i=A,B$. We can then express $\ket{\psi_{AB}}\in{\cal
H}_{A}\otimes{\cal H}_{B}$ as a unit vector in the basis
$\\{\ket{z^{+}_{A},z^{+}_{B}},\ket{z^{+}_{A},z^{-}_{B}},\ket{z^{-}_{A},z^{+}_{B}},\ket{z^{-}_{A},z^{-}_{B}}\\}$.
Let such an expression be

$\ket{\psi_{AB}}=c_{1}\ket{z^{+}_{A},z^{+}_{B}}+c_{2}\ket{z^{+}_{A},z^{-}_{B}}+c_{3}\ket{z^{-}_{A},z^{+}_{B}}+c_{4}\ket{z^{-}_{A},z^{-}_{B}}$

for some coefficients $c_{1},c_{2},c_{3},c_{4}\in\mathbb{C}$. It is well known
that each such $\ket{\psi_{AB}}$ admits a Schmidt decomposition [9], i.e., for
each (normalized) tuple $(c_{1},c_{2},c_{3},c_{4})$ there exists an
$a\in[0,1]$ and orthonormal bases (also known as the Schmidt bases),
$\\{\ket{s^{+}_{A}},\ket{s^{-}_{A}}\\}$ and
$\\{\ket{t^{+}_{B}},\ket{t^{-}_{B}}\\}$ of $\mathcal{H}_{A}$ and
$\mathcal{H}_{B}$ such that

$\ket{\psi_{AB}}:=a\ket{s^{+}_{A},t^{+}_{B}}+\sqrt{1-a^{2}}\ket{s^{-}_{A},t^{-}_{B}}.$
(31)

Take $\alpha=2\arccos(a)$. Further, we can find unitary operators
$\sf{U}_{i}\in{\cal B}({\cal H}_{i})$, $i\in\\{A,B\\}$ that provide
transformations among the given basis vectors
$\\{\ket{z^{+}_{i}},\ket{z^{-}_{i}}\\},i=A,B$ and the Schmidt bases as
follows:
$\mathsf{U}_{A}\ket{z^{+}_{A}}=\ket{t^{+}_{A}},\mathsf{U}_{A}\ket{z^{-}_{A}}=\ket{t^{-}_{A}},\mathsf{U}_{B}\ket{z^{+}_{B}}=\ket{s^{+}_{B}},\mathsf{U}_{B}\ket{z^{-}_{B}}=\ket{s^{-}_{A}}.$
Notice that then
$\mathsf{U}_{A}\otimes\mathsf{U}_{B}\ket{\Phi^{\alpha}_{AB}}=\ket{\psi_{AB}}$
where we recall our notation $\ket{\Phi^{\alpha}_{AB}}$ from (5). Define
$K_{u_{A}}^{(A)}(\xi_{A})=\mathsf{U}_{A}^{\dagger}P_{u_{A}}^{(A)}(\xi_{A})\mathsf{U}_{A},K_{u_{B}}^{(B)}(\xi_{B})=\mathsf{U}_{B}^{\dagger}P_{u_{B}}^{(B)}(\xi_{B})\mathsf{U}_{B},$
and notice that $K_{u_{i}}^{(i)}(\xi_{i})^{\dagger}=K_{u_{i}}^{(i)}(\xi_{i})$,
$K_{u_{i}}^{(i)}(\xi_{i})K_{u_{i}}^{(i)}(\xi_{i})=K_{u_{i}}^{(i)}(\xi_{i})$ so
that they are valid projection operators. Define,
$\widehat{Q}:=({\cal H}_{A},{\cal
H}_{B},\ket{\Phi^{\alpha}_{AB}}\bra{\Phi^{\alpha}_{AB}},\\{K_{u_{A}}^{(A)}(\xi_{A})\\},\\{K_{u_{B}}^{(B)}(\xi_{B})\\}).$
Clearly $\widehat{Q}\in{\cal Q}^{\alpha}_{2}$. Further notice that
$\widehat{Q}(u_{A},u_{B}|\xi_{A},\xi_{B})=\operatorname{Tr}(K_{u_{A}}^{(A)}(\xi_{A})\otimes
K_{u_{B}}^{(B)}(\xi_{B})\ket{\Phi^{\alpha}_{AB}}\bra{\Phi^{\alpha}_{AB}})$.
Substituting $K_{u_{A}}^{(A)}(\xi_{A})$ and $K_{u_{B}}^{(B)}(\xi_{B})$ and
using the unitarity of $\mathsf{U}_{A},\mathsf{U}_{B}$, it follows that
$\widehat{Q}(u_{A},u_{B}|\xi_{A},\xi_{B})=$

$\displaystyle\operatorname{Tr}(P_{u_{A}}^{(A)}(\xi_{A})\otimes
P_{u_{B}}^{(B)}(\xi_{B})\ket{\psi_{AB}}\bra{\psi_{AB}})=Q(u_{A},u_{B}|\xi_{A},\xi_{B}).$

The claimed equality $\underline{{\cal Q}}_{2}=\widehat{\cal Q}_{2}$ follows
since $Q$ was arbitrary.
2) Recall that $\inf_{Q\in{\cal Q}}J(Q;D)=\inf_{Q\in{\cal Q}_{2}}J(Q;D)$ holds
from Theorem III.1. On the other hand, since $\underline{{\cal
Q}}_{2}=\widehat{\cal Q}_{2}$, $\inf_{Q\in\widehat{\cal
Q}_{2}}J(Q;D)=\inf_{Q\in\underline{{\cal Q}}_{2}}J(Q;D)$ follows. It remains
to show that $\inf_{Q\in{\cal Q}_{2}}J(Q;D)=\inf_{Q\in\underline{{\cal
Q}}_{2}}J(Q;D)$ so suppose otherwise, i.e., $\inf_{Q\in\underline{{\cal
Q}}_{2}}J(Q;D)-\inf_{Q\in{\cal Q}_{2}}J(Q;D)=\delta>0$. Recall that ${\cal
Q}_{2}={\rm conv}(\underline{{\cal Q}}_{2})$. By definition of an infimum, we
have a $Q\in{\cal Q}_{2}$ such that $J(Q;D)<\inf_{Q\in{\cal
Q}_{2}}J(Q;D)+\delta/2$. Now for some set of $p_{i}\geq 0,\sum_{i}p_{i}=1$, we
have $Q=\sum_{i}p_{i}Q_{i}$ where $Q_{i}\in\underline{{\cal Q}}_{2}$. It
follows that $\min_{i}J(Q_{i};D)\leq\inf_{Q\in{\cal Q}_{2}}J(Q;D)+\delta/2$
which contradicts the supposition. Thus $\inf_{Q\in\underline{{\cal
Q}}_{2}}=\inf_{Q\in{\cal Q}_{2}}J(Q;D)$. This finishes off our proof of
Proposition III.2.

###  -C Parametric specification of ${\cal Q}^{\alpha}_{2}$

We will drop the subscripts $i(\xi_{i})$ in the kets and on parameters that
refer to players and observations for now, for their presence is apparent. So
let

$a:=(\cos{\theta_{a}}\sin{\phi_{a}},\sin{\theta_{a}}\sin{\phi_{a}},\cos{\phi_{a}});\
A:=\\{\ket{a^{+}},\ket{a^{-}}\\}$
$b:=(\cos{\theta_{b}}\sin{\phi_{b}},\sin{\theta_{b}}\sin{\phi_{b}},\cos{\phi_{b}});\
B:=\\{\ket{b^{+}},\ket{b^{-}}\\}$ $\displaystyle
Q(u_{A}^{+},u^{+}_{B})=|\braket{a^{+},b^{+}}{\Phi^{\alpha}}|^{2}$
$\displaystyle=|\cos\nicefrac{{\alpha}}{{2}}\braket{a^{+},b^{+}}{z^{+},z^{+}}+\sin\nicefrac{{\alpha}}{{2}}\braket{a^{+},b^{+}}{z^{-},z^{-}}|^{2}$

Now using Bloch representation [9] for qubit states, we have for $i=a,b$:

$\displaystyle\ket{i^{+}}=\cos\nicefrac{{\phi_{i}}}{{2}}\ket{z^{+}}+e^{\iota\theta_{i}}\sin\nicefrac{{\phi_{i}}}{{2}}$
$\displaystyle\implies\braket{i^{+}}{z^{+}}=\cos\nicefrac{{\phi_{i}}}{{2}},\braket{i^{+}}{z^{-}}=e^{\iota\theta_{i}}\sin\nicefrac{{\phi_{i}}}{{2}}$
$\displaystyle\ket{i^{-}}=-e^{-\iota\theta_{i}}\sin\nicefrac{{\phi_{i}}}{{2}}\ket{z^{+}}+\cos\nicefrac{{\phi_{i}}}{{2}}\ket{z^{-}}$
$\displaystyle\implies\braket{i^{-}}{z^{+}}=-e^{-\iota\theta_{i}}\sin\nicefrac{{\phi_{i}}}{{2}},\braket{i^{-}}{z^{-}}=\cos\nicefrac{{\phi_{i}}}{{2}}$

Indeed then,

$\displaystyle
Q(u_{A}^{+},u_{B}^{+})=+\sin^{2}{(\theta_{a}+\theta_{b})}\sin^{2}\nicefrac{{\alpha}}{{2}}\sin^{2}\nicefrac{{\phi_{a}}}{{2}}\sin^{2}\nicefrac{{\phi_{b}}}{{2}}$
$\displaystyle|\cos\nicefrac{{\alpha}}{{2}}\cos\nicefrac{{\phi_{a}}}{{2}}\cos\nicefrac{{\phi_{b}}}{{2}}+e^{-\iota(\theta_{a}+\theta_{b})}\sin\nicefrac{{\alpha}}{{2}}\sin\nicefrac{{\phi_{a}}}{{2}}\sin\nicefrac{{\phi_{b}}}{{2}}|^{2}$
$\displaystyle=\cos^{2}\nicefrac{{\alpha}}{{2}}\cos^{2}\nicefrac{{\phi_{a}}}{{2}}\cos^{2}\nicefrac{{\phi_{b}}}{{2}}+\sin^{2}\nicefrac{{\alpha}}{{2}}\sin^{2}\nicefrac{{\phi_{a}}}{{2}}\sin^{2}\nicefrac{{\phi_{b}}}{{2}}$
$\displaystyle\qquad+\nicefrac{{1}}{{4}}\sin\alpha\cos{(\theta_{a}+\theta_{b})}\sin{\phi_{a}}\sin{\phi_{b}}$

Other entries in Table I can be similarly computed.

###  -D Proof of Proposition V.1

We have, from the simplification in Equation (17)

$\displaystyle J(\pi;D)$
$\displaystyle=-\sum{\mathbb{P}}(\xi_{A},\xi_{B},0)\pi(u_{A}=u_{B}|\xi_{A},\xi_{B})$
$\displaystyle-\chi\sum{\mathbb{P}}(\xi_{A},\xi_{B},1)\pi(u_{A}\neq
u_{B}|\xi_{A},\xi_{B})$

It is straightforward to compute that

$\displaystyle J(\pi^{0000};D)$ $\displaystyle=J(\pi^{0010};D)=-k-s-2t;$
$\displaystyle J(\pi^{0011};D)$ $\displaystyle=J(\pi^{0011};D)=-\chi(s+k+2t);$
$\displaystyle J(\pi^{1100};D)$ $\displaystyle=J(\pi^{1110};D)=-k-s-2\chi t;$
$\displaystyle J(\pi^{1101};D)$ $\displaystyle=J(\pi^{1110};D)=-\chi(k+s)-2t,$

$J(\pi;D)=-(1+\chi)(s+t)$ for
$\pi\in\\{\pi^{0100},\pi^{1000},\pi^{0110},\pi^{1010}\\}$ and
$J(\pi;D)=-(1+\chi)(k+t)$ for
$\pi\in\\{\pi^{1001},\pi^{1011},\pi^{0101},\pi^{0111}\\}$. Proposition V.1 now
follows trivially.

###  -E Proof of Proposition V.2

We will require repeated reference to Table II throughout this proof.

No. | Assignment Case $(j=-i)$ | $Q(u_{i}=u_{j}|\xi_{i},\xi_{j})$
---|---|---
I | $u_{i}^{+}(\xi_{i})=u_{i}^{-}(\xi_{i})=u_{j}^{+}(\xi_{j})=u_{j}^{-}(\xi_{j})$ | $\delta(u_{i},u_{i}^{+}(\xi_{i}))\delta(u_{j},u_{j}^{+}(\xi_{j}))$
II | $u_{i}^{+}(\xi_{i})=u_{i}^{-}(\xi_{i})=u_{j}^{+}(\xi_{j})\neq u_{j}^{-}(\xi_{j})$ | $\cos^{2}({\alpha}/{2})\cos^{2}({\phi_{j(\xi_{j})}}/{2})+\sin^{2}({\alpha}/{2})\sin^{2}({\phi_{j(\xi_{j})}}/{2})$
III | $u_{i}^{+}(\xi_{i})=u_{i}^{-}(\xi_{i})=u_{j}^{-}(\xi_{j})\neq u_{j}^{+}(\xi_{j})$ | $\cos^{2}({\alpha}/{2})\sin^{2}({\phi_{j(\xi_{j})}}/{2})+\sin^{2}({\alpha}/{2})\cos^{2}({\phi_{j(\xi_{j})}}/{2})$
IV | $u_{i}^{+}(\xi_{i})\neq u_{i}^{-}(\xi_{i})=u_{j}^{-}(\xi_{j})\neq u_{j}^{+}(\xi_{j})$ | $\cos^{2}\frac{\phi_{i(\xi_{i})}}{2}\cos^{2}\frac{\phi_{j(\xi_{j})}}{2}+\sin^{2}\frac{\phi_{i(\xi_{i})}}{2}\sin^{2}\frac{\phi_{j(\xi_{j})}}{2}+2\beta_{\alpha,\theta_{i(\xi_{i})},\theta_{j(\xi_{j})},\phi_{i(\xi_{i})},\phi_{j(\xi_{j})}}$
V | $u_{i}^{+}(\xi_{i})\neq u_{i}^{-}(\xi_{i})=u_{j}^{+}(\xi_{j})\neq u_{j}^{-}(\xi_{j})$ | $\cos^{2}\frac{\phi_{i(\xi_{i})}}{2}\sin^{2}\frac{\phi_{j(\xi_{j})}}{2}+\sin^{2}\frac{\phi_{i(\xi_{i})}}{2}\cos^{2}\frac{\phi_{j(\xi_{j})}}{2}-2\beta_{\alpha,\theta_{i(\xi_{i})},\theta_{j(\xi_{j})},\phi_{i(\xi_{i})},\phi_{j(\xi_{j})}}$
TABLE II: Probability of equal actions over different assignment cases. Here
$\beta_{\alpha,\theta_{a(\xi_{A})},\theta_{b(\xi_{B})},\phi_{a(\xi_{A})},\phi_{b(\xi_{B})}}=(1/4)\sin\alpha\cos(\theta_{a(\xi_{A})}+\theta_{b(\xi_{B})})\sin\phi_{a(\xi_{A})}\sin\phi_{b(\xi_{B})}$

We prove this proposition by establishing the existence of a tuple
$\alpha^{0},\theta^{0},\phi^{0}$ for each $Q\in\widehat{Q}$ such that
$Q_{0}:=(\alpha^{0},\theta^{0},\phi^{0},\\{v_{i}^{\pm}(\xi_{i})\\})$ satisfies
$J(Q_{0};D)\leq J(Q;D)$. Let
$Q=(\alpha,\theta,\phi,\\{u^{\pm}_{i}(\xi_{i})\\}_{i})\in\widehat{{\cal Q}}$
be arbitrary. Pertaining to this arbitrary choice of $Q$, we attend to the
list of cases that soon follow.
First, we introduce some notation we utilise extensively through this proof,
and sparsely later in this article.

  * •

We denote $J(Q^{\prime};D)-J(Q;D)=:\Lambda(Q^{\prime},Q)$ while the instance
$D$ is fixed by context.

  * •

Recall from (17) that
$\kappa(\xi_{A},\xi_{B})=\chi{\mathbb{P}}(\xi_{A},\xi_{B},1)-{\mathbb{P}}(\xi_{A},\xi_{B},0)$.

  * •

Denote
$d(Q^{\prime},Q|\xi_{A},\xi_{B}):=Q^{\prime}(u_{A}=u_{B}|\xi_{A},\xi_{B})-Q(u_{A}=u_{B}|\xi_{A},\xi_{B})$.
It is then clear from (17) that
$\Lambda(Q^{\prime},Q)=\sum_{\xi_{A},\xi_{B}}\kappa(\xi_{A},\xi_{B})d(Q^{\prime},Q|\xi_{A},\xi_{B})$.

  * •

Let $Q=(\alpha,\theta,\phi,\\{u^{\pm}_{i}(\xi_{i})\\}_{i})$. Then if the
assignment $u$ obeys conditions of row $X$ of Table II, we denote
$Q(u_{A}=u_{B}|\xi_{A},\xi_{B})$ by $Q^{X}(u_{A}=u_{B}|\xi_{A},\xi_{B})$.

  * •

$C_{i}$ denotes the set of assignments encapsulated by a Case $i$ below.

Case 1: $C_{1}:=\\{u|u^{+}_{i}(\xi_{i})\neq u^{-}_{i}(\xi_{i})\forall
i\in\\{A,B\\},\xi_{i}\in\\{0,1\\}\\}$. $|C_{1}|=16$ (two choices for each of
$u_{A}^{+}(0),u_{A}^{+}(1),u_{B}^{+}(0),u_{B}^{+}(1)$), and
$\\{v_{i}^{\pm}(\xi_{i})\\}_{i}$ which is particular to the our parameterised
$Q_{0}(\alpha,\theta,\phi)$ obeys $v\in C_{1}$. The key strategic ingredient
that goes in the cost is $Q(u_{A}=u_{B}|\xi_{A},\xi_{B})$ computed for each
case in Table II. For strategies that resort to Case 1, the relevant
computation is given by the rows IV and V in the table. Clearly, the
assignment $\\{v_{i}^{\pm}(\xi_{i})\\}_{i}$ corresponding to $Q_{0}$ obeys
conditions of row IV. We show that $\alpha^{0},\theta^{0}$ and $\phi^{0}$ can
be tuned so appropriately for $Q_{0}$ to match any $Q$. So let
$\alpha^{0}=\alpha,$

$\theta^{0}_{i(\xi_{i})}=\begin{cases}\theta_{i(\xi_{i})}&u_{i}^{0}=u_{i}^{+}(\xi_{i})\\\
\pi+\theta(\xi_{i})+2m(\xi_{i})\pi&\text{otherwise},\end{cases}$ (32)

where $m(\xi_{i})\in\\{0,-1\\}$ is set to ensure
$\theta^{\prime}_{i(\xi_{i})}\in[0,2\pi)$ and

$\phi^{0}_{i(\xi_{i})}=\begin{cases}\phi(\xi_{i})&u_{i}^{0}=u_{i}^{+}(\xi_{i})\\\
\pi-\phi(\xi_{i})+2n(\xi_{i})\pi&\text{otherwise}.\end{cases}$ (33)

where similarly $n(\xi_{i})\in\\{0,-1\\}$ is set so that
$\phi^{\prime}\in[0,2\pi)$. It is now clear by an inspection of Table II that
$Q_{0}^{IV}(u_{A}=u_{B}|\xi_{A},\xi_{B})\equiv
Q^{V}(u_{A}=u_{B}|\xi_{A},\xi_{B})$ so that $J(Q_{0};D)=J(Q;D)$. We quickly
illustrate one such inspection for the reader’s clarity. Suppose that the
assignment corresponding to our arbitrary $Q$ obeys
$u^{+}_{A}(\xi_{A})=u_{A}^{1}$ and $u^{+}_{B}(\xi_{B})=u_{B}^{0}$ for a
particular tuple $\xi_{A},\xi_{B}$ which pertains to row V. Our transformation
(32), (33) then ensures
$\cos^{2}\nicefrac{{\phi_{a(\xi_{A})}^{0}}}{{2}}=\sin^{2}\nicefrac{{\phi_{a(\xi_{A})}}}{{2}}$
and $\beta(\alpha^{0},\theta^{0},\phi^{0})=-\beta(\alpha,\theta,\phi)$ so that
$Q^{IV}_{0}(u_{A}=u_{B}|\xi_{A},\xi_{B})=Q^{V}(u_{A}=u_{B}|\xi_{A},\xi_{B})$.
Case 2: $C_{2}=\\{u^{+}_{j}(\xi_{j}^{*})=u^{-}_{j}(\xi_{j}^{*})$ for a unique
pair $(j,\xi_{j}^{*})\in\\{A,B\\}\times\\{0,1\\}\\}$. We have $|C_{2}|=64$ and
$v\notin C_{2}$. Let
$Q^{\prime}:=(\alpha^{\prime},\theta^{\prime},\phi^{\prime},\\{w^{\pm}_{i}\\}_{i})\in\widehat{\cal
Q}$ where $w\in C_{1}$. Use $\alpha^{\prime}=\alpha$,
$w^{+}_{j}(\xi^{*}_{A})=u^{+}_{j}(\xi^{*}_{j})\neq w^{-}_{j}(\xi^{*}_{j})$ and
$w^{\pm}_{i}(\xi_{i})\equiv u^{\pm}_{i}(\xi_{i})$ for $i\neq j$. We specialise
to $j=A,i=B$ as the argument for $j=B,i=A$ will then similarly follow. We have
two subcases within case 2.
Case 2a: $w^{+}_{B}(\xi_{B})=w^{+}_{A}(\xi_{A}^{*})$ so that
$Q^{\prime}(u_{A}=u_{B}|\xi_{A}^{*},\xi_{B})=Q^{\prime
IV}(u_{A}=u_{B}|\xi_{A}^{*},\xi_{B})$ and
$Q(u_{A}=u_{B}|\xi_{A},\xi_{B})=Q^{II}(u_{A}=u_{B}|\xi_{A},\xi_{B})$. Set
$\phi^{\prime}_{a(\xi_{A}^{*})}\equiv\alpha$ and
$\phi^{\prime}_{b(\xi_{B})}\equiv\phi_{b(\xi_{B})}$. Then,
$\Lambda(Q,Q^{\prime})=\sum_{\xi_{A},\xi_{B}}\kappa(\xi_{A},\xi_{B})d(Q^{\prime},Q|\xi_{A},\xi_{B})=$

$\frac{-\sin\alpha}{2}\sin\phi_{a(\xi_{A}^{*})}\sum_{\xi_{B}}\kappa(\xi_{A}^{*},\xi_{B})\sin\phi_{b(\xi_{B})}\cos(\theta^{\prime}_{a(\xi_{A}^{*})}+\theta^{\prime}_{b(\xi_{B})}).$

Case 2b: $w^{-}_{B}(\xi_{B})=w^{+}_{A}(\xi_{A}^{*})$ so that
$Q^{\prime}(u_{A}=u_{B}|\xi_{A}^{*},\xi_{B})=Q^{\prime
V}(u_{A}=u_{B}|\xi_{A}^{*},\xi_{B})$ and
$Q(u_{A}=u_{B}|\xi_{A},\xi_{B})=Q^{III}(u_{A}=u_{B}|\xi_{A},\xi_{B})$.
Similarly set $\phi^{\prime}_{a(\xi_{A}^{*})}\equiv\alpha$ and
$\phi^{\prime}_{b(\xi_{B})}\equiv\phi_{b(\xi_{B})}$. Then,
$\Lambda(Q,Q^{\prime})=\sum_{\xi_{A},\xi_{B}}\kappa(\xi_{A},\xi_{B})d(Q^{\prime},Q|\xi_{A},\xi_{B})$

$=\frac{\sin\alpha}{2}\sin\phi_{a(\xi_{A}^{*})}\sum_{\xi_{B}}\kappa(\xi_{A}^{*},\xi_{B})\sin\phi_{b(\xi_{B})}\cos(\theta^{\prime}_{a(\xi_{A}^{*})}+\theta^{\prime}_{b(\xi_{B})}).$

For each of the above two cases, notice that the transformation
$\theta^{\prime}_{a(\xi_{A}^{*})}\to\theta^{\prime}_{a(\xi_{A}^{*})}\pm\pi$
takes $\Lambda(Q^{\prime},Q)\to-\Lambda(Q^{\prime},Q)$ so $\exists\
\theta^{\prime}_{a(\xi_{A}^{*})}$ such that $\Lambda(Q,Q^{\prime})\leq 0$.
This provides the construction of a $Q^{\prime}$ for every $Q$ such that
$J(Q^{\prime};D)\leq J(Q;D)$. Since $Q^{\prime}$ pertains to case 1 of our
proof, it follows that $\exists$ a $Q_{0}(\alpha^{0},\theta^{0},\phi^{0})$
obeying $J(Q_{0}(\alpha^{0},\theta^{0},\phi^{0});D)\leq J(Q^{\prime};D)\leq
J(Q;D)$.

Case 3: $C_{3}=\\{\exists\ (\xi_{A}^{*},\xi_{B}^{*})\in\\{0,1\\}^{2}$ such
that $u_{i}^{+}(\xi^{*}_{i})=u_{i}^{-}(\xi^{*}_{i})$ and
$u_{i}^{+}(\xi^{\prime}_{i})\neq u_{i}^{-}(\xi^{\prime}_{i})$ for each
$i\in\\{A,B\\}$ where $\xi^{\prime}_{i}:=\sim\xi_{i}^{*}\\}$. $|C_{3}|=64$.
Consider a $Q^{\prime}:=(\alpha,\theta,\phi^{\prime},\\{w^{\pm}_{i}\\}_{i})$
with $w\in C_{1}$ and
$w_{i}^{\pm}(\xi^{\prime}_{i})=u_{i}^{\pm}(\xi^{\prime}_{i})$ for each $i$.
Indeed then, $\Lambda(Q^{\prime},Q)=J(Q;D)-J(Q^{\prime};D)$

$\displaystyle=\kappa(\xi_{A}^{*},\xi_{B}^{*})d(Q^{\prime},Q|\xi_{A}^{*},\xi_{B}^{*})+\kappa(\xi_{A}^{*},\xi_{B}^{\prime})d(Q^{\prime},Q|\xi_{A}^{*},\xi_{B}^{\prime})$
$\displaystyle+\kappa(\xi_{A}^{\prime},\xi_{B}^{*})d(Q^{\prime},Q|\xi_{A}^{\prime},\xi_{B}^{*})$

We have the following two sub-cases.
Case 3a: $u_{A}^{+}(\xi_{A}^{*})=u_{B}^{+}(\xi^{\prime}_{B})$ so that
$Q(u_{A}=u_{B}|\xi_{A}^{*},\xi_{B}^{*})=Q^{I}(u_{A}=u_{B}|\xi_{A}^{*},\xi_{B}^{*})$,
$Q(u_{A}=u_{B}|\xi_{A}^{*},\xi_{B}^{\prime})=Q^{II}(u_{A}=u_{B}|\xi_{A}^{*},\xi_{B}^{\prime})$
and
$Q(u_{A}=u_{B}|\xi_{A}^{\prime},\xi_{B}^{*})=Q^{II}(u_{A}=u_{B}|\xi_{A}^{\prime},\xi_{B}^{*})$.
Set
$w_{A}^{+}(\xi^{*}_{A})=w_{B}^{+}(\xi_{B}^{\prime})=u_{B}^{+}(\xi_{B}^{\prime})$
and $\phi^{\prime}_{i(\xi_{i}^{\prime})}\equiv\phi_{i(\xi_{i})}$. Now if
$\phi_{a(\xi_{A}^{*})}=\phi_{b(\xi_{B}^{*})}=0$, we find upon straightforward
evaluation that $\Lambda(Q^{\prime},Q)=$

$-\sin^{2}\nicefrac{{\alpha}}{{2}}(\kappa(\xi_{A}^{*},\xi_{B}^{\prime})\cos\phi_{b(\xi_{B}^{\prime})}+\kappa(\xi_{A}^{\prime},\xi_{B}^{*})\cos\phi_{a(\xi_{A}^{\prime})})$

and that if $\phi_{a(\xi_{A}^{*})}=\phi_{b(\xi_{B}^{*})}=\pi$,
$\Lambda(Q^{\prime},Q)=$

$\cos^{2}\nicefrac{{\alpha}}{{2}}(\kappa(\xi_{A}^{*},\xi_{B}^{\prime})\cos\phi_{b(\xi_{B}^{\prime})}+\kappa(\xi_{A}^{\prime},\xi_{B}^{*})\cos\phi_{a(\xi_{A}^{\prime})})$

so one of the above two ensure $\Lambda\leq 0$.
Case 3b: $u_{A}^{+}(\xi_{A}^{*})\neq u_{B}^{+}(\xi_{B}^{\prime})$ in which
case,
$Q(u_{A}=u_{B}|\xi_{A}^{*},\xi_{B}^{*})=Q^{I}(u_{A}=u_{B}|\xi_{A}^{*},\xi_{B}^{*})$,
$Q(u_{A}=u_{B}|\xi_{A}^{*},\xi_{B}^{\prime})=Q^{III}(u_{A}=u_{B}|\xi_{A}^{*},\xi_{B}^{\prime})$
and
$Q(u_{A}=u_{B}|\xi_{A}^{\prime},\xi_{B}^{*})=Q^{III}(u_{A}=u_{B}|\xi_{A}^{\prime},\xi_{B}^{*})$.
Again set
$w_{A}^{+}(\xi^{*}_{A})=w_{B}^{+}(\xi_{B}^{\prime})=u_{B}^{+}(\xi_{B}^{\prime})$
and $\phi^{\prime}_{i(\xi_{i}^{\prime})}\equiv\phi_{i(\xi_{i})}$. Now if
$\phi_{a(\xi_{A}^{*})}=0,\phi_{b(\xi_{B}^{*})}=\pi$, we find upon
straightforward evaluation that $\Lambda(Q^{\prime},Q)=$

$-\cos^{2}\nicefrac{{\alpha}}{{2}}(\kappa(\xi_{A}^{*},\xi_{B}^{\prime})\cos\phi_{b(\xi_{B}^{\prime})}+\kappa(\xi_{A}^{\prime},\xi_{B}^{*})\cos\phi_{a(\xi_{A}^{\prime})})$

and that if $\phi_{a(\xi_{A}^{*})}=\pi,\phi_{b(\xi_{B}^{*})}=0$,
$\Lambda(Q^{\prime},Q)=$

$\sin^{2}\nicefrac{{\alpha}}{{2}}(\kappa(\xi_{A}^{*},\xi_{B}^{\prime})\cos\phi_{b(\xi_{B}^{\prime})}+\kappa(\xi_{A}^{\prime},\xi_{B}^{*})\cos\phi_{a(\xi_{A}^{\prime})})$

so one of the above two ensure $\Lambda\leq 0$.

Now note that $Q^{\prime}\in C_{1}$ in both the sub-cases. Hence, there exists
a $Q_{0}(\alpha^{0},\theta^{0},\phi^{0})$ can be found, as follows from the
proof of Case 1. This completes the proof for Case 3.

Case 4: $\\{\exists$ a unique $j\in\\{A,B\\}$ such that
$u_{j}^{+}(\xi_{j})=u_{j}^{-}(\xi_{j})$ $\forall\ \xi_{j}$ and
$u_{i}^{+}(\xi_{i})\neq u_{i}^{-}(\xi_{i})\ \forall\xi_{i}$, for $i\neq j\\}$,
$|C_{4}|=112$. We argue for $j=A$, and $j=B$ similarly follows. We have
$u_{A}^{+}(\xi_{A})=u_{A}^{-}(\xi_{A})=u(\xi_{A})\ \forall\xi_{A}$ then notice
from Table I (Proposition III.3)

$\displaystyle Q(u_{A},u^{+}_{B}(\xi_{B})|\xi_{A},\xi_{B})$
$\displaystyle=\left(\cos^{2}\nicefrac{{\alpha}}{{2}}\cos^{2}\nicefrac{{\phi_{b(\xi_{B})}}}{{2}}+\sin^{2}\nicefrac{{\alpha}}{{2}}\sin^{2}\nicefrac{{\phi_{b(\xi_{B})}}}{{2}}\right)\delta_{u_{A}u(\xi_{A})}$
$Q(u_{A},u^{-}_{B}(\xi_{B})|\xi_{A},\xi_{B})\\\
=\left(\cos^{2}\nicefrac{{\alpha}}{{2}}\sin^{2}\nicefrac{{\phi_{b(\xi_{B})}}}{{2}}+\sin^{2}\nicefrac{{\alpha}}{{2}}\cos^{2}\nicefrac{{\phi_{b(\xi_{B})}}}{{2}}\right)\delta_{u_{A}u(\xi_{A})}$

Now consider a
$Q^{\prime}=(0,\theta^{\prime},\phi^{\prime},\\{w_{i}^{\pm}(\xi_{i})\\}_{i})$
where $\theta^{\prime}_{i(\xi_{i})}=\theta_{i(\xi_{i})}\ \forall\ i$,
$\phi_{a(\xi_{A})}\equiv 0$, $w\in C_{1}$, $w^{+}_{A}(\xi_{A})=u(\xi_{A})\neq
w^{-}_{A}(\xi_{A})$, $w_{B}^{\pm}(\xi_{B})\equiv u^{\pm}_{B}(\xi_{B})$ and
$\phi^{\prime}_{b(\xi_{B})}$ is set by the equation

$\cos^{2}\phi^{\prime}_{b(\xi_{B})}=\left(\cos^{2}\nicefrac{{\alpha}}{{2}}\cos^{2}\nicefrac{{\phi_{b(\xi_{B})}}}{{2}}+\sin^{2}\nicefrac{{\alpha}}{{2}}\sin^{2}\nicefrac{{\phi_{b(\xi_{B})}}}{{2}}\right).$

The existence of such a $\phi^{\prime}$ is guaranteed since RHS in above
equation is in $[0,1]$. It is then immediate by inspection (again using Table
I) that $Q^{\prime}\equiv Q\implies
J(Q^{\prime};D)=J(Q;D)\implies\Lambda(Q^{\prime},Q)\leq 0$. Again, since
$Q^{\prime}\in C_{1}$, the required $Q_{0}(\alpha^{0},\theta^{0},\phi^{0})$
can be found to settle case 4. This completes our proof.

###  -F Proof of Theorem V.4

Define, $\Delta^{*}(\chi):=\inf_{Q\in{\cal
Q}}J(Q;D)-\inf_{\pi\in\Pi}J(\pi;D)\\}.$ Then from (18) and (22), we have
$\Delta^{*}(\chi)\leq\Delta(\chi,\phi)$ for all $\chi>0,\phi$ where we define
$\Delta(\chi,\phi):=$

$\begin{cases}\underline{J}(\chi,\phi_{a1},\phi_{b0},\phi_{b1})+(s+k+2t)&\chi\in\left(0,\nicefrac{{k+t}}{{s+t}}\right]\\\
\overline{J}(\chi,\phi_{a1},\phi_{b0},\phi_{b1})+(1+\chi)(s+t)&\chi\in\left(\frac{k+t}{s+t},\frac{s+t}{k+t}\right)\\\
\overline{J}(\chi,\phi_{a1},\phi_{b0},\phi_{b1})+\chi(s+k+2t)&\chi\in\left[\nicefrac{{s+t}}{{k+t}},\infty\right)\end{cases}$

where $\overline{J}(\chi,\phi_{a1},\phi_{b0},\phi_{b1})$ and
$\underline{J}(\chi,\phi_{a1},\phi_{b0},\phi_{b1})$ are given by (20) and (21)
respectively. The proof idea is as follows.

  * •

We show existence of a $\phi$ such that $\Delta(\chi,\phi)<0$ which implies
$\Delta^{*}(\chi)<0$ corresponding to the presence of quantum advantage at
$\chi$, for all $\chi\in{\cal X}$.

  * •

We show $\Delta(\chi,\phi)\geq 0\forall\ \phi\in[0,\pi],\chi\in{\cal X}^{c}$
which asserts the absence of quantum advantage for all $\chi\in{\cal X}^{c}$
(Recall from Corollary III.4 and (22) that $\Delta^{*}(\chi)$ is attained by a
tuple $\phi\in[0,\pi]$).

1) Consider the interval
$\chi\in\left(\nicefrac{{k+t}}{{s+t}},\nicefrac{{s+t}}{{k+t}}\right)$.
$\Delta^{*}(\chi)\leq\Delta(\chi,\phi_{a1},\phi_{b0},\phi_{b1}):=\overline{J}(\chi,\phi_{a1},\phi_{b0},\phi_{b1})+(1+\chi)(s+t)=$

$\displaystyle\left(\nicefrac{{-\chi
k+s}}{{2}}\right)\left(1-\cos{\phi_{b0}}\right)+\nicefrac{{t(\chi-1)}}{{2}}\left(\cos{\phi_{b1}}+\cos{(\phi_{a1}+\phi_{b0})}\right)$
$\displaystyle+\left(\nicefrac{{\chi
s-k}}{{2}}\right)\left(1+\cos{(\phi_{a1}+\phi_{b1})}\right)$

Notice $\Delta(\chi,\pi,0,0)=\nabla_{\phi}\Delta(\chi,\pi,0,0)=0\ \forall\chi$
and consider the Hessian evaluated at this point is

$\begin{pmatrix}\nicefrac{{-\chi
k+s+t(\chi-1)}}{{2}}&\nicefrac{{t(\chi-1)}}{{2}}&0\\\
\nicefrac{{t(\chi-1)}}{{2}}&\nicefrac{{t(\chi-1)+(\chi
s-k)}}{{2}}&\nicefrac{{(\chi s-k)}}{{2}}\\\ 0&\nicefrac{{(\chi
s-k)}}{{2}}&\nicefrac{{(\chi s-k)+t(\chi-1)}}{{2}}\end{pmatrix}$

.
The determinant of the Hessian evaluates to
$\nicefrac{{1}}{{8}}(-1+\chi)^{2}(1+\chi)(k-s)t^{2}$ which is negative for all
$\chi$ except $\chi=1$ since $s>k$. Thus, the point $(\chi,\pi,0,0)$ is not a
local minimum and by Taylor’s theorem, $\exists(\chi,\phi^{*})$ such that
$\Delta(\chi,\phi^{*})<0$ so that
$\forall\chi\in\left(\nicefrac{{k+t}}{{s+t}},\nicefrac{{s+t}}{{k+t}}\right)\setminus\\{1\\}\implies\Delta^{*}(\chi)<0$.
To show that $\Delta^{*}(1)\geq 0$, notice that
$\Delta(1,\phi_{a1},\phi_{b0},\phi_{b1})=((s-k)/2)(2-\cos\phi_{b0}+\cos(\phi_{a1}+\phi_{b1}))\geq
0\forall\phi$. We have shown that $D$ admits a quantum advantage for all
$\chi\in\left(k+t/s+t,s+t/k+t\right)\setminus\\{1\\}=:{\cal X}_{1}$.

2) Now for the interval $\chi\in\left[\nicefrac{{s+t}}{{k+t}},\infty\right)$
where
$\Delta^{*}(\chi)\leq\Delta(\chi,\phi_{a1},\phi_{b0},\phi_{b1})=\overline{J}(\chi,\phi_{a1},\phi_{b0},\phi_{b1})+\chi(k+s+2t):=$

$\displaystyle\left(\nicefrac{{\chi
k-s}}{{2}}\right)\left(1+\cos{\phi_{b0}}\right)+\left(\nicefrac{{\chi
s-k}}{{2}}\right)\left(1+\cos{(\phi_{a1}+\phi_{b1})}\right)$
$\displaystyle+\nicefrac{{t(\chi-1)}}{{2}}\left(2+\cos{\phi_{b1}}+\cos{(\phi_{a1}+\phi_{b0})}\right)$
(34)

Notice that
$\Delta(\chi,0,\pi,\pi)=\nabla_{\phi}\Delta(\chi,0,\pi,\pi)=0\forall\chi$.
Further the Hessian evaluated at this point is

$\begin{pmatrix}\nicefrac{{\chi
k-s+t(\chi-1)}}{{2}}&\nicefrac{{t(\chi-1)}}{{2}}&0\\\
\nicefrac{{t(\chi-1)}}{{2}}&\nicefrac{{t(\chi-1)+(\chi
s-k)}}{{2}}&\nicefrac{{(\chi s-k)}}{{2}}\\\ 0&\nicefrac{{(\chi
s-k)}}{{2}}&\nicefrac{{t(\chi-1)+(\chi s-k)}}{{2}}\end{pmatrix}$

and its determinant given by

$(\nicefrac{{1}}{{8}})(\chi-1)t(2(\chi k-s)(\chi s-k)+(-1+\chi)^{2}(k+s)t).$

Since $s>k$, $\chi>1$, the Hessian has a negative determinant for all $\chi$
satisfying

$\overline{f}(\chi):=(2(\chi k-s)(\chi s-k)+(-1+\chi)^{2}(k+s)t)<0.$ (35)

This translates to $\chi<\chi^{th}$ since $\chi^{th}$ is the larger root of
the quadratic $\overline{f}(\chi)$. and we thus have existence of a
$(\chi,\phi^{*})$ such that $\Delta(\chi,\phi^{*})<0$ so that
$\forall\chi\in\left[\nicefrac{{s+t}}{{k+t}},\chi^{th}\right),\Delta^{*}(\chi)<0$.
Next, we show that $\Delta^{*}(\chi)\geq 0$ $\forall\chi>\chi^{th}$. In
Proposition .3 below, we have shown that the global minimum of
$\Delta(\chi^{th},\phi)$ in the cube $\phi\in[0,\pi]^{3}$ occurs at one of the
vertices. Substituting each of the vertices in (34) and using the fact that
$\chi^{th}>\frac{s+t}{k+t}>1>\frac{k+t}{s+t}$ reveals that the global minimum
is attained at $\phi=(0,\pi,\pi)$ i.e. $\Delta(\chi^{th},0,\pi,\pi)=0$. We
skip the explicit evaluations due to paucity of space.

This establishes $\Delta^{*}(\chi)=0$ for all $\chi\geq\chi^{th}$ since for
any $\phi$,
$\partial_{\chi}\Delta(\chi,\phi)=\frac{1}{2}(k(1+\cos\phi_{b0})+t(2+\cos\phi_{b1}+\cos(\phi_{a1}+\phi_{b0}))\\\
s(1+\cos(\phi_{a1}+\phi_{b1})))\geq 0\forall\phi$. Our arguments have thus
shown that quantum advantage is present for $\chi\in[s+t/k+t,\chi^{th})=:{\cal
X}_{2}$ and absent for $\chi>\chi^{th}$.

3) Finally for the interval $\left(0,\nicefrac{{k+t}}{{s+t}}\right)$,
$\Delta^{*}(\chi)\leq\Delta(\chi,\phi_{a1},\phi_{b0},\phi_{b1})=$

$\displaystyle(\nicefrac{{\chi k-s}}{{2}})(1+\cos\phi_{b0})+(\nicefrac{{\chi
t-t}}{{2}})(2+\cos\phi_{b1}+\cos(\phi_{a_{1}}-\phi_{b_{0}}))$
$\displaystyle+(\nicefrac{{\chi
s-k}}{{2}})(1+\cos(\phi_{a1}+\phi_{b1}))-(\chi-1)(s+k+2t)$ (36)

Again, $\Delta(\chi,0,0,0)=\nabla_{\phi}\Delta(\chi,0,0,0)=0$. Further,
Hessian evaluated at this point is

$\begin{pmatrix}\frac{\chi
k-s}{2}+\frac{t(\chi-1)}{2}&\frac{t(\chi-1)}{2}&0\\\
\nicefrac{{t(\chi-1)}}{{2}}&\frac{t(\chi-1)}{2}+\frac{(\chi
s-k)}{2}&\frac{(\chi s-k)}{2}\\\ 0&\nicefrac{{(\chi
s-k)}}{{2}}&\nicefrac{{t(\chi-1)}}{{2}}+\nicefrac{{(\chi
s-k)}}{{2}}\end{pmatrix}$

and has the determinant

$(\nicefrac{{1}}{{8}})(1-\chi)t(2(\chi k-s)(\chi s-k)+(-1+\chi)^{2}(k+s)t).$

Thus, the Hessian has a negative eigenvalue for $\overline{f}(\chi)<0.$ This
translates to $\chi>\chi_{th}$ since $\chi_{th}$ is the smaller root of
$\overline{f}(\chi)$. Rest follows as before and we have $\Delta^{*}(\chi)<0$
for $\chi\in(\chi_{th},1)$. For $\chi<\chi_{th}$, the point $(\chi,0,0,0)$
turns into a global minimum, and quantum advantage is lost for
$\chi\leq\chi_{th}$. Our arguments that show this mirror those in part 2). We
have shown in Proposition .3 below that the global minimum of
$\Delta(\chi_{th},\phi)$ occurs on one of the vertices of the cube
$\phi\in[0,\pi]^{3}$. We again find using
$\chi_{th}<\nicefrac{{k+t}}{{s+t}}<1<\nicefrac{{s+t}}{{k+t}}$ and substituting
each vertex in (36) that the global minimum occurs at the $\phi=0,0,0$ and
$\Delta^{*}(\chi_{th})=0$.

Now we can conclude $\Delta^{*}(\chi)=0$ for all $\chi\leq\chi_{th}$ since
$\partial_{\chi}\Delta(\chi,\phi)=\frac{1}{2}(k(-1+\cos\phi_{b0})+t(-2+\cos\phi_{a1}-\cos\phi_{b0}+\cos\phi_{b1})+s(-1+\cos\phi_{a1}+\phi_{b1}))\leq
0\ \forall\phi$. This demonstrates that the quantum advantage is present for
$\chi\in(\chi_{th},k+t/s+t]$ and absent for all $\chi<\chi_{th}$.

###### Proposition .3

  1. 1.

Suppose $\Delta(\chi^{th},\phi)$ as defined in (34) attains a global minimum
at $\phi^{*}\in[0,\pi]^{3}$. Then $\phi^{*}$ is a vertex of the cube
$[0,\pi]^{3}$.

  2. 2.

Suppose $\Delta(\chi_{th},\phi)$ as defined in (36) attains a global minimum
at $\phi^{*}\in[0,\pi]^{3}$. Then $\phi^{*}$ is a vertex of the cube
$[0,\pi]^{3}$.

###### Proof:

1) It is easy to check $\overline{f}(s/k)>0$ which implies $s/k>\chi^{th}$ so
let $\alpha^{2}=-{(\chi^{th}k-s)}/{2}$, $\beta^{2}=t(\chi^{th}-1)/2$ and
$\delta^{2}=(\chi^{th}s-k)/2$. We then have (for brevity we change notation to
$\Delta(\phi):=\Delta(\chi^{th},\phi)$) the system $\nabla_{\phi}\Delta(\phi)$
given by,

$\displaystyle\partial_{\phi_{b0}}\Delta=\alpha^{2}\sin{\phi_{b0}}-\beta^{2}\sin(\phi_{a1}+\phi_{b0})=0$
(37)
$\displaystyle\partial_{\phi_{a1}}\Delta=-\beta^{2}\sin(\phi_{a1}+\phi_{b0})-\delta^{2}\sin(\phi_{a1}+\phi_{b1})=0$
(38)
$\displaystyle\partial_{\phi_{b1}}\Delta=-\beta^{2}\sin(\phi_{b1})-\delta^{2}\sin(\phi_{a1}+\phi_{b1})=0$
(39)

We now find all solutions on $C:=[0,\pi]^{3}$. It is easy to notice that each
vertex of $C$ is a solution. Further we also notice that the vertices are the
only solution on each of the faces of $C$. To check this, notice how
$\phi_{a1}\in\\{0,\pi\\}$ forces $\phi_{b0},\phi_{b1}\in\\{0,\pi\\}$ from (37)
and (39) and repeat this argument for other faces.

Now, from $\eqref{eq:sys1}$, notice that

$\sin\phi_{b0}\geq 0\implies\sin(\phi_{a1}+\phi_{b0})\geq
0\implies\phi_{a1}+\phi_{b0}\in[0,\pi]$

Comparing (38) and (39), we obtain $\sin\phi_{b1}=\sin(\phi_{a1}+\phi_{b0})$
so that $\phi_{b1}\in\\{\phi_{a1}+\phi_{b0},\pi-(\phi_{a1}+\phi_{b0})\\}$.
Suppose that $\phi_{b1}=\pi-(\phi_{a1}+\phi_{b0})$ and substitute so in (38)
to obtain $\sin\phi_{b0}/\sin(\phi_{a1}+\phi_{b0})<0$ which contradicts (37).
Thus $\phi_{b1}=\phi_{a1}+\phi_{b0}$, so substitute in (38) and using
$b^{2}=\beta^{2}/\alpha^{2}$ and $d^{2}=\delta^{2}/\beta^{2}$ , rewrite (37)
and (38) respectively as $\sin\phi_{b0}=b^{2}\sin(\phi_{a1}+\phi_{b0}),$
$\sin(\phi_{a1}+\phi_{b0})+d^{2}\sin(2\phi_{a1}+\phi_{b0})=0.$ from where it
follows that

$\sin\phi_{b0}=-b^{2}d^{2}\sin{(\phi_{b0}+\phi_{a1})}.$ (40)

We now show there is no simultaneous solution to (37), (38) and (39) in
$(0,\pi)^{3}$. Suppose there is one. Expanding sinusoidal sums in (40) and
division by $\sin\phi_{b0}$ recovers
$b^{2}(\cos\phi_{a1}+\cot{\phi_{b0}}\sin{\phi_{a1}})=1$. This allows the
following simplification.

$\displaystyle-b^{2}d^{2}(\cos 2\phi_{a1}+\cot{\phi_{b0}}\sin{2\phi_{a1}})=1$
$\displaystyle-b^{2}d^{2}(-1+2\cos{\phi_{a1}}(\cos\phi_{a1}+\cot\phi_{b0}\sin\phi_{a1}))=1$
$\displaystyle\cos\phi_{a1}=\nicefrac{{1}}{{2}}(b^{2}-1/d^{2})=\nicefrac{{1}}{{2}}\left(\nicefrac{{\beta^{2}}}{{\alpha^{2}}}-\nicefrac{{\beta^{2}}}{{\delta^{2}}}\right)$

Now recall $\overline{f}(\chi)$ from (35) and observe
$\overline{f}(\chi^{th})=0$ that asserts the following train of calculations,
using substitutions for $\alpha^{2},\beta^{2}$ and $\delta^{2}$

$\displaystyle(2(\chi k-s)(\chi s-k)+(-1+\chi)^{2}(k+s)t)=0$
$\displaystyle\frac{t(\chi-1)^{2}(s+k)}{2(s-\chi k)(\chi s-k)}=1$
/12$(b^{2}-1/d^{2})=\cos\phi_{a1}=1\implies\phi_{a1}=0.$

This contradicts $\phi\in(0,\pi)^{3}$. We have thus shown that the solution
set to $\nabla_{\phi}\Delta(\phi)=0$ is precisely the set of vertices of $C$.
Extreme value theorem thus dictates that a global minimum of $\Delta(\phi)$ is
attained on the boundary of $C$. Now similar arguments can be repeated on a
face of $C$ to push the location of the global minimizer to the edges, and
subsequently the vertices. We show one such example and the rest follows
similarly. So look at the face $\phi_{a1}=0$, let
$\Delta(0,\phi_{b0},\phi_{b1})=\delta(\phi)$. Then substituting $\phi_{a1}$ in
(37) and (39) forces the solution to $\nabla_{\phi}\delta=0$ on a vertex.
Thus, $\delta$ attains a minimum on one of the edges of the face
$\phi_{a1}=0$. So to look at the edge $\phi_{a1}=0,\phi_{b1}=0$, substitute
this in (37) and notice that $\Delta(\chi^{th},0,\phi_{b0},0)$ attains a
minimum on a vertex of C. It is straightforward to repeat this argument for
all faces and edges which will establish the proposition.

2) The proof scheme is exactly the same. We prove the less trivial part again,
i.e. to show that $\nabla_{\phi}\Delta(\chi_{th},\phi)=0$ has no solution in
the interior of $C$. Note that $\overline{f}(k/s)<0$ so
$1>\frac{k+t}{s+t}>\chi_{th}>k/s$ and let $\alpha^{2}=-{(\chi_{th}k-s)}/{2}$,
$\beta^{2}=-t(\chi_{th}-1)/2$ and $\delta^{2}=(\chi_{th}s-k)/2$.Then (with the
notation $\Delta(\phi):=\Delta(\chi_{th},\phi)$) the system
$\nabla_{\phi}\Delta(\phi)$ given by,

$\partial_{\phi_{b0}}\Delta=\alpha^{2}\sin{\phi_{b0}}-\beta^{2}\sin(\phi_{a1}-\phi_{b0})=0$
(41)
$\partial_{\phi_{a1}}\Delta=\beta^{2}\sin(\phi_{a1}-\phi_{b0})-\delta^{2}\sin(\phi_{a1}+\phi_{b1})=0$
(42)
$\partial_{\phi_{b1}}\Delta=\beta^{2}\sin(\phi_{b1})-\delta^{2}\sin(\phi_{a1}+\phi_{b1})=0$
(43)

As before, all vertices of $C$ are solutions to the system and vertices are
the complete set of solutions on the boundary. As before, we argue
$\phi_{b1}=\phi_{a1}-\phi_{b0}$ and arrive at
$\sin\phi_{b0}=b^{2}\sin{\phi_{a1}-\phi_{b0}}$ and
$\sin\phi_{b0}=b^{2}d^{2}\sin(2\phi_{a1}-\phi_{b0})$. Following manipulations
similar to before, one can show that this forces $\phi$ to vertex. Maintaining
rest of the proof scheme completes the proof of part 2.

|  Shashank Aniruddha Deshpande was born in Buldhana, India, in 2000. He is
currently an undergraduate senior in the Department of Physics, and, the
Department of Systems and Control Engineering at IIT Bombay, India. His
research interests are in the control and optimization of stochastic and
networked systems.
---|---
|  Ankur A. Kulkarni is the Kelkar Family Chair Associate Professor with the
Systems and Control Engineering group at the Indian Institute of Technology
Bombay (IITB). He received his B.Tech. from IITB in 2006, followed by M.S. in
2008 and Ph.D. in 2010, both from the University of Illinois at Urbana-
Champaign (UIUC). From 2010-2012 he was a post-doctoral researcher at the
Coordinated Science Laboratory at UIUC. He was an Associate (from 2015–2018)
of the Indian Academy of Sciences, a recipient of the INSPIRE Faculty Award of
the Dept of Science and Technology Govt of India in 2013. He has won several
best paper awards at conferences, the Excellence in Teaching Award in 2018 at
IITB, and the William A. Chittenden Award in 2008 at UIUC. He has been a
consultant to the Securities and Exchange Board of India (SEBI), the HDFC Life
Insurance Company, Kotak Mahindra Bank Ltd and Bank of Baroda. He presently
serves on the IT-Project Advisory Board of SEBI, as Research Advisor to the
Tata Consultancy Services, and as Program Chair of the Indian Control
Conference. He has been a visitor to MIT in USA, University of Cambridge in
UK, NUS in Singapore, IISc in Bangalore and KTH in Sweden.
---|---