# Optimality of any pair of incompatible rank-one projective measurements for
some non-trivial Bell inequality

Gabriel Pereira Alves<EMAIL_ADDRESS>Faculty of Physics, University of
Warsaw, Pasteura 5, 02-093 Warsaw, Poland  Jędrzej Kaniewski
<EMAIL_ADDRESS>Faculty of Physics, University of Warsaw, Pasteura 5,
02-093 Warsaw, Poland

###### Abstract

Bell non-locality represents one of the most striking departures of quantum
mechanics from classical physics. It shows that correlations between space-
like separated systems allowed by quantum mechanics are stronger than those
present in any classical theory. In a recent work [Sci. Adv. 7, eabc3847
(2021)], a family of Bell functionals tailored to mutually unbiased bases
(MUBs) is proposed. For these functionals, the maximal quantum violation is
achieved if the two measurements performed by one of the parties are
constructed out of MUBs of a fixed dimension. Here, we generalize this
construction to an arbitrary incompatible pair of rank-one projective
measurements. By constructing a new family of Bell functionals, we show that
for any such pair there exists a Bell inequality that is _maximally_ violated
by this pair. Moreover, when investigating the robustness of these violations
to noise, we demonstrate that the realization which is most robust to noise is
not generated by MUBs.

## . ntroduction

The discovery of Bell non-locality lies among the most fundamental results of
twentieth-century physics. While the theoretical description was proposed by
Bell in 1964 Bell (1964), the first experimental demonstration was performed
by Freedman and Clauser Freedman and Clauser (1972), followed by the seminal
work of Aspect et al. Aspect  _et al._ (1981, 1982a, 1982b). In 2015, three
independent groups performed the Bell experiment in a loophole-free manner
Hensen  _et al._ (2015); Giustina  _et al._ (2015); Shalm  _et al._ (2015),
meaning that they managed to eliminate several issues that could falsify the
conclusions of the experiment.

In a nutshell, Bell non-locality states that correlations between spatially
separated parties allowed by quantum theory are stronger than those allowed by
local-realistic theories Bell (1964); Brunner  _et al._ (2014). It is easy to
see that entanglement Horodecki  _et al._ (2009) and incompatibility of
measurements Heinosaari  _et al._ (2016) constitute two necessary resources to
generate non-local correlations Fine (1982). Conversely, conditions sufficient
to generate non-locality are known only for a restricted class of states or
measurements. For a bipartite Bell scenario, all pure entangled states can
generate non-locality, a statement referred to as Gisin’s theorem Gisin
(1991). A result of similar generality for incompatibility of measurements was
obtained in Ref. Wolf  _et al._ (2009), in which it is proved that every
incompatible pair of projective measurements enables the violation of a Bell
inequality. Here, we continue the study of how useful a pair of measurements
is for the purpose of generating non-locality. However, our focus is not
merely on observing a Bell violation, but on producing the maximal violation
allowed by quantum mechanics.

In this work, we focus on pairs of rank-one projective measurements and
generalize a framework originally presented in Ref. Tavakoli  _et al._ (2021)
in which a family of bipartite Bell functionals is tailored to mutually
unbiased bases (MUBs) Schwinger (1960); Durt  _et al._ (2010). In other words,
in Ref. (Tavakoli  _et al._ , 2021) the maximum value obtainable by any
quantum realization of the functionals – here referred to as quantum value and
denoted by $\beta_{Q}$ – can be achieved if one of the parties implements a
pair of rank-one projective measurements with uniform overlaps. Here, we study
the same Bell scenario (shown in Fig. 1) as in Ref. Tavakoli  _et al._ (2021),
parametrized by an integer $d\geq 2$. However, our new functionals are
tailored to a more general pair of rank-one projective measurements. More
specifically, the measurement operators are constructed out of a pair of
orthonormal bases $\\{\ket{e_{j}}\\}_{j=1}^{d}$ and
$\\{\ket{f_{k}}\\}_{k=1}^{d}$ on $\mathbb{C}^{d}$ and let us denote the
resulting overlap matrix by

$\displaystyle O_{jk}:=|\braket{e_{j}}{f_{k}}|.$ (1)

The only assumption we make is that these measurements are incompatible since
this is a necessary condition for non-locality.

The family of Bell functionals introduced in this work is designed so that
both the quantum value and a realization that achieves it can be written down
explicitly. We also demonstrate that our functionals are non-trivial, meaning
that the maximum value achievable by any classical realization – referred to
as local value and denoted by $\beta_{L}$ – is strictly smaller than the
quantum value. This result is obtained by deriving a non-trivial certification
statement for the measurements performed by one of the parties. Finally, for a
wide class of functionals, we obtain a device-independent certification of the
maximally entangled state of local dimension $d$.

To make our work relevant for experiments, we investigate the robustness to
noise of the proposed optimal realizations. In the standard model of noise, in
which the state is replaced by an isotropic state, it can be shown that the
bigger the gap between $\beta_{Q}$ and $\beta_{L}$, the more robust to noise
the optimal realization is. For even $d$, we found that the largest gap is
achieved if and only if the original measurements correspond to a direct sum
of qubit MUBs, i.e. all the non-zero elements of the matrix $O$ must be equal
to $\nicefrac{{1}}{{\sqrt{2}}}$. This contradicts our initial guess that the
most noise-robust realization (in a fixed dimension) would correspond to the
one generated by MUBs. For odd $d$, we could not determine the largest
possible gap, but we have derived an upper bound on $\beta_{Q}-\beta_{L}$
which is valid for all $d\geq 3$. Furthermore, we show analytically that for
every odd $d$ there exist measurements that give rise to a realization that is
more robust to noise than the realization obtained from MUBs.

Fig. 1: A Bell scenario parametrized by $d\geq 2$. The inputs and outputs
belong to the following sets: $b,\,x_{1},\,x_{2}\in\\{1,\,...,\,d\\}$,
$y\in\\{1,\,2\\}$ and $a\in\\{1,\,2,\,\perp\\}$.

## I. family of Bell functionals

Our goal is to show that every pair of incompatible rank-one projective
measurements is optimal for some Bell functional. To achieve this, it is
convenient to first apply a simple preprocessing, which simply discards the
subspace in which the measurements are compatible (which is not useful for the
purpose of generating non-locality). Then, we introduce a bipartite Bell
scenario parametrized by an integer $d$ and construct a family of functionals
whose quantum value can be computed analytically. Lastly, we present a
realization that saturates the quantum value.

Consider a pair of orthonormal bases on $\mathbb{C}^{d^{\prime}}$, which we
denote by $\\{\ket{e_{j}}\\}_{j=1}^{d^{\prime}}$ and
$\\{\ket{f_{k}}\\}_{k=1}^{d^{\prime}}$, and let
$O_{jk}^{\prime}:=|\braket{e_{j}}{f_{k}}|$ be the overlap matrix. If the two
bases share a vector this results in a one-dimensional subspace of
$\mathbb{C}^{d^{\prime}}$ in which the measurements are compatible. We remove
all such subspaces by truncating the original Hilbert space appropriately,
which leads to a pair of rank-one projective measurements acting on
$\mathbb{C}^{d}$ for some $d\leq d^{\prime}$ (since we assume that the
original measurements are incompatible, we are guaranteed that $d\geq 2$). For
these new measurements, the overlap matrix is guaranteed to satisfy
$O_{jk}<1$. Moreover, these new measurements can be implemented by performing
the original measurements on a quantum state with appropriately chosen local
support. From now, we will assume that this process has already been performed
and we will restrict our attention to measurements acting on effective
dimension $d$ whose overlaps satisfy $O_{jk}<1$.

Now, consider a bipartite Bell scenario characterized by an integer $d\geq 2$,
whose parties are named Alice and Bob. For each $d$, Alice is given a two-
character string denoted by $x:=x_{1}x_{2}$, for
$x_{1},\,x_{2}\in\\{1,\,...,\,d\\}$ and outputs $a\in\\{1,\,2,\,\perp\\}$. Bob
has two possible inputs labeled by $y\in\\{1,\,2\\}$ and outputs
$b\in\\{1,\,...,\,d\\}$ (see Fig. 1). We are given a pair of orthonormal bases
$\\{\ket{e_{j}}\\}_{j=1}^{d}$ and $\\{\ket{f_{k}}\\}_{k=1}^{d}$ whose overlap
matrix is given by $O_{jk}:=|\braket{e_{j}}{f_{k}}|$ and satisfies $O_{jk}<1$.
We define the _correlation_ score $\mathcal{C}_{d}$ as

$\mathcal{C}_{d}:=\sum_{x_{1},x_{2}=1}^{d}\,\sum_{y=1}^{2}\lambda_{x}\left[\,p(a=y,\,b=x_{y}|x,\,y)\right.\\\
-\left.p(a=\bar{y},\,b=x_{y}|x,\,y)\right],$ (2)

where $\lambda_{x}:=\sqrt{1-O_{x_{1}x_{2}}^{2}}$ and the notation $\bar{y}$
means that the value of $y$ is flipped from 1 to 2 or vice-versa. Note that
the weights $\lambda_{x}$ depend on the overlap matrix and, as we will later
see, this ensures that the functional is tailored to the orthonormal bases
$\\{\ket{e_{j}}\\}_{j=1}^{d}$ and $\\{\ket{f_{k}}\\}_{k=1}^{d}$. The only
terms that produce a non-zero contribution to $\mathcal{C}_{d}$ correspond to
the cases when $b=x_{y}$ and $a\neq\perp$. In those cases, the score is
increased (decreased) if Alice outputs $a=y$ ($a=\bar{y}$). In order to
balance the cases where $a\in\\{1,\,2\\}$ (Alice plays the game) and $a=\perp$
(Alice does not play the game), a penalty is introduced111In the end of
Appendix A.1 there is a clarification of why this penalty is necessary.,
giving rise to our _final_ score:

$\displaystyle\mathcal{F}_{d}:=\mathcal{C}_{d}-\frac{1}{2}\sum_{x_{1},x_{2}=1}^{d}\lambda_{x}^{2}\,\left[\,p(a=1|x)+p(a=2|x)\right].$
(3)

It turns out that the quantum value of $\mathcal{F}_{d}$ does not depend on
the overlap matrix $O$, as shown in the lemma below.

######  Lemma 1.

For $d\geq 2$, the quantum value of $\mathcal{F}_{d}$ is $d-1$.

The proof of Lemma 1 consists of finding an upper bound on the value of
$\mathcal{F}_{d}$ and demonstrating that it can be saturated. Proving the
upper bound relies on many elementary steps, which we present in Appendix A.1.
For our purposes, it suffices to show how to construct a quantum realization
that saturates the quantum value of $\mathcal{F}_{d}$.

We choose the measurements of Bob corresponding to inputs $y=1$ and $y=2$ to
be $P_{x_{1}}=\ket{e_{x_{1}}}\\!\\!\bra{e_{x_{1}}}$ and
$Q_{x_{2}}=\ket{f_{x_{2}}}\\!\\!\bra{f_{x_{2}}}$, respectively.222We use
$x_{1}$ ($x_{2}$) as the subscript for $P$ ($Q$) because we only get a non-
zero contribution to the functional when $b=x_{y}$. For the measurements of
Alice, it is more convenient to work with Hermitian observables rather than
measurement operators. For every input $x$ of Alice, we express the three
measurement operators $A_{x}^{(1)}$, $A_{x}^{(2)}$ and $A_{x}^{(\perp)}$ in a
compact manner by defining the observable $A_{x}$ as

$A_{x}:=\,(+1)\times A_{x}^{(1)}+(-1)\times A_{x}^{(2)}+0\times
A_{x}^{(\perp)}\\\ =A_{x}^{(1)}-A_{x}^{(2)}.$ (4)

It is easy to see that if the measurement is projective, then the spectrum of
$A_{x}$ belongs to the set $\\{\pm 1,\,0\\}$. In addition, any Hermitian
operator whose spectrum is contained in this set can be interpreted as an
observable arising from a projective measurement, so the two representations
are equivalent. Then, let us choose $A_{x}$ as:

$\displaystyle
A_{x}=\frac{1}{\lambda_{x}}\left(P_{x_{1}}-Q_{x_{2}}\right)^{\textsf{T}},$ (5)

where $(\cdot)^{\textsf{T}}$ denotes the transposition in the computational
basis. Because $P_{x_{1}}$ and $Q_{x_{2}}$ are rank-one, the difference
$P_{x_{1}}-Q_{x_{2}}$ is a rank-two operator. With a simple calculation, it is
possible to check that the spectrum of $P_{x_{1}}-Q_{x_{2}}$ is contained in
$\\{\pm\lambda_{x},~{}0\\}$. Thus, since $O_{x_{1}x_{2}}<1$ and
$\lambda_{x}=\sqrt{1-O_{x_{1}x_{2}}^{2}}$, we have $\lambda_{x}>0$, and the
normalising factor ensures the spectrum of $A_{x}$ is contained in $\\{\pm
1,\,0\\}$.333Recall that taking the transposition does not affect the
spectrum.

Finally, we pick the shared state as the maximally entangled state belonging
to $\mathbb{C}^{d}\otimes\mathbb{C}^{d}$:

$\displaystyle\ket{\Phi_{d}^{+}}=\frac{1}{\sqrt{d}}\sum_{k=1}^{d}\ket{k,\,k}.$
(6)

Then, let us quickly verify that the resulting realization indeed achieves the
quantum value of $\mathcal{F}_{d}$. Evaluating $\mathcal{C}_{d}$ given in Eq.
(2) leads to

$\displaystyle\mathcal{C}_{d}=\sum_{x}\lambda_{x}\braket{\Phi^{+}_{d}}{\,A_{x}\otimes(P_{x_{1}}-Q_{x_{2}})\,}{\Phi^{+}_{d}},$
(7)

where the summation over $y$ has already been performed to give
$A_{x}\otimes(P_{x_{1}}-Q_{x_{2}})$. Plugging in Eq. (5) and exploiting the
fact that for any linear operator $L$ we have
$L\otimes\mathds{1}\ket{\Phi^{+}_{d}}=\mathds{1}\otimes
L^{\textsf{T}}\ket{\Phi^{+}_{d}}$, leads to

$\displaystyle\mathcal{C}_{d}=\sum_{x}\braket{\Phi^{+}_{d}}{\,\mathds{1}\otimes(P_{x_{1}}-Q_{x_{2}})^{2}\,}{\Phi^{+}_{d}}.$
(8)

Proceeding similarly for $\mathcal{F}_{d}$, we get

$\displaystyle\mathcal{F}_{d}=\mathcal{C}_{d}-\frac{1}{2}\sum_{x}\lambda_{x}^{2}\,\braket{\Phi^{+}_{d}}{\,(A_{x}^{(1)}+A_{x}^{(2)})\otimes\mathds{1}\,}{\Phi^{+}_{d}}.$
(9)

Since the measurement operators of Alice are projective, the term in
parentheses can be identified as $A_{x}^{(1)}+A_{x}^{(2)}=A_{x}^{2}$ and

$\displaystyle\mathcal{F}_{d}$
$\displaystyle=\mathcal{C}_{d}-\frac{1}{2}\sum_{x}\lambda_{x}^{2}\,\braket{\Phi^{+}_{d}}{\,A_{x}^{2}\otimes\mathds{1}\,}{\Phi^{+}_{d}}$
$\displaystyle=\frac{1}{2}\sum_{x}\braket{\Phi^{+}_{d}}{\,\mathds{1}\otimes(P_{x_{1}}-Q_{x_{2}})^{2}\,}{\Phi^{+}_{d}}.$
(10)

Finally, since $P_{x_{1}}$ and $Q_{x_{2}}$ are projectors, we can evaluate the
sum:

$\displaystyle\sum_{x}(P_{x_{1}}-Q_{x_{2}})^{2}=2(d-1)\mathds{1},$ (11)

which leads to $\mathcal{F}_{d}=d-1$ for the desired realization.

## II. haracterizing the optimal realization

Having computed the quantum value of $\mathcal{F}_{d}$, it would be natural to
determine its local value and show that our functionals are indeed non-
trivial. However, since $\beta_{L}$ does not have a closed-form expression,
let us postpone it to the next section. Fortunately, it turns out that proving
$\beta_{Q}>\beta_{L}$ is possible by characterising the realizations that
achieve $\beta_{Q}$. Therefore, to demonstrate that $\mathcal{F}_{d}$ is non-
trivial, we continue our analysis with the device-independent certification of
the measurements and the state.

######  Theorem 1.

For any $d\geq 2$ and overlap matrix satisfying $O_{x_{1}x_{2}}<1$, under the
assumption that Bob’s marginal state is full-rank, for any quantum realization
which achieves the quantum value of $\mathcal{F}_{d}$, it holds that:

  1. 1.

Bob’s measurement operators denoted by $P_{x_{1}}$ and $Q_{x_{2}}$ associated
with inputs $y=1$ and $2$, respectively, must satisfy

$\displaystyle\begin{aligned}
O_{x_{1}x_{2}}^{2}P_{x_{1}}&=P_{x_{1}}Q_{x_{2}}P_{x_{1}}\;\text{and}\\\
O_{x_{1}x_{2}}^{2}Q_{x_{2}}&=Q_{x_{2}}P_{x_{1}}Q_{x_{2}}\quad\forall~{}x_{1},~{}x_{2}.\end{aligned}$
(12)

  2. 2.

If $O$ has a row (or column) whose entries are all non-zeros, then there exist
local isometries
$V_{A}:\mathcal{H}_{A}\rightarrow\mathbb{C}^{d}\otimes\mathcal{H}_{A}$ and
$V_{B}:\mathcal{H}_{B}\rightarrow\mathbb{C}^{d}\otimes\mathcal{H}_{B}$ whose
action on the unknown state $\rho_{AB}$ yields

$\displaystyle(V_{A}\otimes V_{B})\rho_{AB}(V_{A}^{\dagger}\otimes
V_{B}^{\dagger})=\Phi_{d}^{+}\otimes\rho_{\mathrm{aux}},$ (13)

where $\Phi_{d}^{+}$ is the density matrix of $\ket{\Phi_{d}^{+}}$ and
$\rho_{\mathrm{aux}}$ corresponds to the uncharacterized part of $\rho_{AB}$.

###### Sketch of the proof.

Here we present a sketch just for the first part (see Appendix B for a
complete proof). To prove an upper bound on the quantum value of
$\mathcal{F}_{d}$ the Cauchy–Schwarz inequality is used several times.
Saturating these inequalities allows us to deduce that for all $x=x_{1}x_{2}$
the action of Alice’s and Bob’s operators on $\rho_{AB}$ satisfies the
following relation:

$\displaystyle\lambda_{x}A_{x}\otimes\mathds{1}\,\rho_{AB}=\mathds{1}\otimes(P_{x_{1}}-Q_{x_{2}})\,\rho_{AB}.$
(14)

Since our goal is to certify Bob’s measurements, we can assume that Alice’s
measurements are projective, which implies that $A_{x}^{3}=A_{x}$. Combining
this identity with Eq. (14) yields a polynomial equation in terms of operators
$P_{x_{1}}$ and $Q_{x_{2}}$ and the marginal state on Bob’s side $\rho_{B}$.
Assuming that $\rho_{B}$ is full-rank allows us to remove the state
dependence. Finally, by examining Eq. (11), we conclude that saturating the
quantum value on a state whose $\rho_{B}$ is full-rank requires the
measurements of Bob to be projective. This leads to the desired Eqs. (12). ∎

Eqs. (12) are derived purely from the fact that we observe the quantum value
of $\mathcal{F}_{d}$. To prove that the functional $\mathcal{F}_{d}$ is non-
trivial, it suffices to argue that these relations cannot be satisfied by any
deterministic strategy.

######  Theorem 2.

For any $d\geq 2$ and overlap matrix satisfying $O_{x_{1}x_{2}}<1$, the
quantum value is strictly bigger than the local value.

###### Proof.

A deterministic strategy can always be written as a quantum strategy where the
local Hilbert spaces are one-dimensional. If Bob outputs $b=u$ for $y=1$ and
$b=v$ for $y=2$, the associated projectors correspond to
$P_{x_{1}}=\delta_{x_{1}u}$ and $Q_{x_{2}}=\delta_{x_{2}v}$. If this strategy
saturates the quantum value, Eqs. (12) would imply that
$O_{x_{1}x_{2}}^{2}\delta_{x_{1}u}=\delta_{x_{1}u}\delta_{x_{2}v}\delta_{x_{1}u}$,
for all $x_{1},x_{2}$. However, choosing $x_{1}=u$ and $x_{2}=v$ leads to
$O_{uv}=1$, which is a contradiction. ∎

At this point, we can see why the assumption $O_{x_{1}x_{2}}<1$ was necessary.
It is straightforward to check that $\mathcal{F}_{d}$ can be defined for any
overlap matrix, the quantum value is always equal to $d-1$ and the conclusion
given in Eqs. (12) holds. However, without the assumption that
$O_{x_{1}x_{2}}<1$, the measurement certification statement is no longer
sufficient to deduce that the functional is non-trivial. In fact, in Appendix
C.2, we show that whenever $O_{x_{1}x_{2}}=1$ for some $x$, then there exists
a deterministic strategy achieving $\beta_{Q}$, i.e. $\beta_{L}=\beta_{Q}$.

As explained at the beginning, every pair of incompatible rank-one projective
measurements can be preprocessed to give measurements whose overlap matrix
satisfies $O_{x_{1}x_{2}}<1$ and, hence, gives rise to a non-trivial
functional. Therefore, we obtain the following corollary.

######  Corollary 1.

Every pair of incompatible rank-one projective measurements on a finite-
dimensional Hilbert space is capable of producing non-local correlations and
is optimal for some non-trivial Bell inequality.

## V. obustness against noise

To investigate how robust to noise the realizations presented above are,
consider a specific noise model in which the measurements are kept unchanged
while the state is replaced by the isotropic state

$\displaystyle\rho_{\nu}=\nu\Phi^{+}_{d}+(1-\nu)\frac{\mathds{1}\otimes\mathds{1}}{d^{2}},$
(15)

where $\nu\in[0,\,1]$ is the visibility. A simple calculation shows that
performing the optimal measurements on the isotropic state gives the value of
$(d-1)(2\nu-1)$. We can use this result to compare the noise robustness of
different functionals $\mathcal{F}_{d}$. More specifically, we are interested
in discovering which functional enables a violation for the smallest $\nu$. To
address this question, we first need to compute the local value.

For a fixed overlap matrix $O$, calculating the local value reduces to
analysing the deterministic strategies for $\mathcal{F}_{d}$. If we choose the
strategy of Bob in which he outputs $b=u$ if $y=1$ and $b=v$ if $y=2$, the
value becomes

$\displaystyle\mathcal{F}_{d}=\sum_{x}\lambda_{x}\left(\delta_{x_{1}u}-\delta_{x_{2}v}\right)A_{x}-\frac{1}{2}\sum_{x}\lambda_{x}^{2}A_{x}^{2},$
(16)

where $A_{x}\in\\{\pm 1,\,0\\}$ describes the deterministic strategy of Alice.
Let us now show that the optimal strategy of Alice can be explicitly
determined. The sum can be split into three distinct cases:
$R_{\pm}=\\{x\in[d]^{2}\,|\,(\delta_{x_{1}u}-\delta_{x_{2}v})=\pm 1\\}$ and
$R_{0}=[d]^{2}\,\backslash\,(R_{+}\cup R_{-})$. For the $R_{0}$ terms, the
optimal strategy of Alice is clearly not to play the game (this would lead to
a negative contribution), so the optimal choice is $A_{x}=0$.

For the $R_{\pm}$ terms the optimal choice is
$A_{x}=\delta_{x_{1}u}-\delta_{x_{2}v}$, which is better than
$A_{x}=-(\delta_{x_{1}u}-\delta_{x_{2}v})$ (because $\lambda_{x}>0$) and
better than $A_{x}=0$ (because $\lambda_{x}-\frac{1}{2}\lambda_{x}^{2}>0$).
Plugging in the optimal strategy of Alice into Eq. (16) leads to the following
auxiliary function:

$\displaystyle s(u,\,v):=\sum_{x\in
R_{\pm}}\left(\lambda_{x}-\frac{1}{2}\lambda_{x}^{2}\right),$ (17)

where the dependence on $u$ and $v$ is hidden inside the definitions of
$R_{\pm}$. Then, $\beta_{L}$ can be written as

$\displaystyle\beta_{L}(O)=\max_{u,\,v}\>\left[s(u,v)\right].$ (18)

The choice of coefficients of our functionals, made at the beginning, ensures
that the quantum value does not depend on the overlap matrix. It is a
convenient choice because all the dependence of $O$ is contained in the local
value. It is easy to see that in the noise model presented above, the largest
robustness corresponds to the lowest local value. Searching for highly-robust
functionals leads to the following theorem.

######  Theorem 3.

For $d\geq 2$ and any overlap matrix, $\beta_{L}(O)\geq
d+\sqrt{2}-\nicefrac{{5}}{{2}}$.

###### Sketch of the proof.

(See Appendix C.2 for details). Primarily, note that a lower bound for any
strategy $s(u,~{}v)$ is also a lower bound for $\beta_{L}(O)$. Because we can
always relabel the measurements outputs, we assume, for simplicity, that
$O_{11}$ is the largest element of $O$, i.e. $O_{11}\geq O_{uv}$,
$\forall~{}u,~{}v\in\\{1,\,...,\,d\\}$. Then, we lower bound $\beta_{L}(O)$
using the first strategy:

$\displaystyle\beta_{L}(O)=\max_{u,\,v}\>[s(u,\,v)]\geq s(1,\,1).$ (19)

Next, as $s(1,\,1)$ depends only on overlaps squared, we define a new variable
$t_{x_{1}x_{2}}:=O_{x_{1}x_{2}}^{2}$. This makes some terms in $s(1,\,1)$
strictly concave in $t_{x_{1}x_{2}}$, which allows us to obtain a lower bound
that depends only on $t_{11}$. Minimising that function concludes the proof. ∎

Although Theorem 3 provides a lower bound on $\beta_{L}(O)$, it does not say
whether this bound is achievable. Fortunately, by demanding the saturation of
the strictly concave terms of $s(1,\,1)$, we extract this information.

######  Lemma 2.

For even $d\geq 2$, the lower bound of Theorem 3 is achievable and every $O$
that saturates it corresponds to a direct sum of qubit MUBs, i.e., up to
permutations, it can be written into as

$\displaystyle
O=\bigoplus_{i=1}^{\nicefrac{{d}}{{2}}}\frac{1}{\sqrt{2}}J_{2},$ (20)

where $J_{2}$ is the $2\times 2$ matrix of ones. For odd $d\geq 3$, the lower
bound of Theorem 3 cannot be achieved by any overlap matrix.

The complete proof of Lemma 2 can be found in Appendix C.3. Let us briefly
comment on the difference between even and odd $d$. Our proof of Theorem 3 is
based solely on the fact that the rows and columns of $O$ are normalized.
However, from Eq. (1), we know that $O$ should be obtained by taking the
entry-wise absolute value of a unitary matrix, which, in general, is more
restrictive than just imposing the normalisation condition. For even $d$,
there exists a valid overlap matrix which saturates the lower bound obtained
in Theorem 3, but for odd $d$ this is not the case. For a more detailed
explanation, see Appendix C.4.

## . iscussion

In this work, we have demonstrated how to tailor a Bell functional to a
specific pair of incompatible rank-one projective measurements. More
specifically, we have shown that for every such pair there exists a non-
trivial Bell functional for which this pair is optimal. We have also proved
that for these functionals a certain degree of certification is possible. If
the quantum value of $\mathcal{F}_{d}$ is achieved, the measurements of Bob
must satisfy some simple polynomial relations and, under some additional mild
conditions, a maximally entangled state can be extracted.

We have also investigated how robust to noise these functionals are, as
quantified by the difference $\beta_{Q}-\beta_{L}$. For even $d$, the largest
robustness to noise arises when the measurements are chosen as direct sums of
qubit MUBs. For odd $d$, we have a conjecture for $d=3$, but no analytical
proof of optimality. It is worth pointing out, however, that for $d\geq 3$ the
optimal noise robustness is not achieved by $d$-dimensional MUBs.

There are several open questions arising from this work. An aspect that should
be clarified are the precise conditions under which state certification is
possible. We have shown that if the overlap matrix contains a non-null row or
column, then a maximally entangled state can be extracted. On the other
extreme, there are overlap matrices that decompose as a direct sum for which,
as proved in Appendix B.3, state certification is not possible. Hence, the
question about state certification is open for intermediate cases. Another
question concerns the optimal noise robustness for odd dimensions. Our
candidate for $d=3$ exhibits a mathematically elegant structure and it would
be interesting to see if the same happens for larger dimensions.

Lastly, it is known that all pure entangled states can generate non-locality,
and we have demonstrated that incompatible pairs of rank-one projective
measurements also do so. By assembling these results, is it possible to
achieve necessary and sufficient conditions for, at least, some limited class
of states _and_ measurements?

## I. cknowledgements

We acknowledge fruitful discussions with Máté Farkas and Nicolas Gigena. The
project “Robust certification of quantum devices” is carried out within the
HOMING programme of the Foundation for Polish Science co-financed by the
European Union under the European Regional Development Fund.

## References

  * Bell (1964) J. S. Bell, Physics Physique Fizika 1, 195 (1964).
  * Freedman and Clauser (1972) S. J. Freedman and J. F. Clauser, Phys. Rev. Lett. 28, 938 (1972).
  * Aspect  _et al._ (1981) A. Aspect, P. Grangier, and G. Roger, Phys. Rev. Lett. 47, 460 (1981).
  * Aspect  _et al._ (1982a) A. Aspect, P. Grangier, and G. Roger, Phys. Rev. Lett. 49, 91 (1982a).
  * Aspect  _et al._ (1982b) A. Aspect, J. Dalibard, and G. Roger, Phys. Rev. Lett. 49, 1804 (1982b).
  * Hensen  _et al._ (2015) B. Hensen, H. Bernien, A. E. Dréau, A. Reiserer, N. Kalb, M. S. Blok, J. Ruitenberg, R. F. L. Vermeulen, R. N. Schouten, C. Abellán, W. Amaya, V. Pruneri, M. W. Mitchell, M. Markham, D. J. Twitchen, D. Elkouss, S. Wehner, T. H. Taminiau, and R. Hanson, Nature 526, 682 (2015).
  * Giustina  _et al._ (2015) M. Giustina, M. A. M. Versteegh, S. Wengerowsky, J. Handsteiner, A. Hochrainer, K. Phelan, F. Steinlechner, J. Kofler, J.-A. Larsson, C. Abellán, W. Amaya, V. Pruneri, M. W. Mitchell, J. Beyer, T. Gerrits, A. E. Lita, L. K. Shalm, S. W. Nam, T. Scheidl, R. Ursin, B. Wittmann, and A. Zeilinger, Phys. Rev. Lett. 115, 250401 (2015).
  * Shalm  _et al._ (2015) L. K. Shalm, E. Meyer-Scott, B. G. Christensen, P. Bierhorst, M. A. Wayne, M. J. Stevens, T. Gerrits, S. Glancy, D. R. Hamel, M. S. Allman, K. J. Coakley, S. D. Dyer, C. Hodge, A. E. Lita, V. B. Verma, C. Lambrocco, E. Tortorici, A. L. Migdall, Y. Zhang, D. R. Kumor, W. H. Farr, F. Marsili, M. D. Shaw, J. A. Stern, C. Abellán, W. Amaya, V. Pruneri, T. Jennewein, M. W. Mitchell, P. G. Kwiat, J. C. Bienfang, R. P. Mirin, E. Knill, and S. W. Nam, Phys. Rev. Lett. 115, 250402 (2015).
  * Brunner  _et al._ (2014) N. Brunner, D. Cavalcanti, S. Pironio, V. Scarani, and S. Wehner, Rev. Mod. Phys. 86, 419 (2014).
  * Horodecki  _et al._ (2009) R. Horodecki, P. Horodecki, M. Horodecki, and K. Horodecki, Rev. Mod. Phys. 81, 865 (2009).
  * Heinosaari  _et al._ (2016) T. Heinosaari, T. Miyadera, and M. Ziman, J. Phys. A: Math. Theor. 49, 123001 (2016).
  * Fine (1982) A. Fine, Phys. Rev. Lett. 48, 291 (1982).
  * Gisin (1991) N. Gisin, Physics Letters A 154, 201 (1991).
  * Wolf  _et al._ (2009) M. M. Wolf, D. Perez-Garcia, and C. Fernandez, Phys. Rev. Lett. 103, 230402 (2009).
  * Tavakoli  _et al._ (2021) A. Tavakoli, M. Farkas, D. Rosset, J.-D. Bancal, and J. Kaniewski, Science Advances 7 (2021), 10.1126/sciadv.abc3847.
  * Schwinger (1960) J. Schwinger, Proceedings of the National Academy of Sciences 46, 570 (1960).
  * Durt  _et al._ (2010) T. Durt, B.-G. Englert, I. Bengtsson, and K. Życzkowski, Int. J. of Quantum Information 8, 535 (2010).
  * Colomer  _et al._ (2022) M. P. Colomer, L. Mortimer, I. Frérot, M. Farkas, and A. Acín, Quantum 6, 778 (2022), arXiv: 2203.09429 .
  * Zauner (1999) G. Zauner,  _Quantendesigns, Grundzüge einer nichtkommutativen Designtheorie_ , Ph.D. thesis, University of Vienna (1999).
  * Bengtsson  _et al._ (2005) I. Bengtsson, A. Ericsson, M. Kuś, and K. Życzkowski, Commun. Math. Phys. 259, 307–324 (2005).
  * Fedullo (1992) A. Fedullo, Nuov. Cim. B 107, 1413 (1992).

##  Appendix A The quantum value of $\mathcal{F}_{d}$

In this appendix, we provide a complete proof of Lemma 1. In the main text, we
specified a quantum realization for the functional $\mathcal{F}_{d}$ which
achieves the value $d-1$. Here, in the first part of this appendix, we provide
a matching upper bound, which shows that the quantum value of
$\mathcal{F}_{d}$ equals $d-1$. In the second part, we present a natural
extension of our functional to a set of $N>2$ rank-one projective
measurements.

### A. A.1 Proof of Lemma 1

At this point, we are only interested in deriving an upper bound, hence, we
could, without loss of generality, restrict ourselves to realizations where
the state is pure and measurements are projective. However, we will later
reuse this argument to derive some certification statements, so we do not want
to introduce unnecessary assumptions. As we are not interested in
characterizing the measurements of Alice, we will assume that they are
projective, but we make no assumptions about the measurements of Bob and the
shared state. Thus, let us represent the state by $\rho_{AB}$, an arbitrary
density matrix, and reuse the symbols $A_{x}$, $P_{x_{1}}$ and $Q_{x_{2}}$ to
denote the observables of Alice and the two measurements of Bob, respectively.

We start again by using the Born rule to rewrite $\mathcal{C}_{d}$ as

$\displaystyle\mathcal{C}_{d}=\sum_{x}\lambda_{x}\,\operatorname{tr}\left[\left(A_{x}\otimes(P_{x_{1}}-Q_{x_{2}})\right)\rho_{AB}\right].$
(21)

Taking the absolute value of every term in the summation leads to

$\displaystyle\mathcal{C}_{d}\leq\sum_{x}\left|\lambda_{x}\,\operatorname{tr}\left[\left(A_{x}\otimes(P_{x_{1}}-Q_{x_{2}})\right)\rho_{AB}\right]\right|.$
(22)

In the next step, we apply the Cauchy–Schwarz inequality. For the
Hilbert–Schmidt inner product, the Cauchy–Schwarz inequality reads
$\left|\operatorname{tr}(X^{\dagger}Y)\right|\leq\sqrt{\operatorname{tr}(X^{\dagger}X)}\,\sqrt{\operatorname{tr}(Y^{\dagger}Y)}$,
where $X$ and $Y$ are arbitrary operators acting in a given Hilbert space.
Therefore, taking
$X=\left(A_{x}\otimes\mathds{1}\right)\rho_{AB}^{\nicefrac{{1}}{{2}}}$ and
$Y=\left(\mathds{1}\otimes\left(P_{x_{1}}-Q_{x_{2}}\right)\right)\rho_{AB}^{\nicefrac{{1}}{{2}}}$,
where $\rho_{AB}^{\nicefrac{{1}}{{2}}}$ is the positive semi-definite square
root of $\rho_{AB}$, we can apply the Cauchy–Schwarz inequality to all of the
terms of $\mathcal{C}_{d}$, leading to

$\displaystyle\mathcal{C}_{d}$
$\displaystyle\leq\sum_{x}\lambda_{x}\sqrt{\operatorname{tr}\left[\left(A_{x}^{2}\otimes\mathds{1}\right)\rho_{AB}\right]}\sqrt{\operatorname{tr}\left[\left(\mathds{1}\otimes(P_{x_{1}}-Q_{x_{2}})^{2}\right)\rho_{AB}\right]}.$
(23)

The second application of Cauchy–Schwarz, now for the standard inner product
of real vectors, leads to

$\displaystyle\mathcal{C}_{d}\leq\sqrt{\sum_{x}\lambda_{x}^{2}\,\operatorname{tr}\left[\left(A_{x}^{2}\otimes\mathds{1}\right)\rho_{AB}\right]}\sqrt{\sum_{x}\operatorname{tr}\left[\left(\mathds{1}\otimes(P_{x_{1}}-Q_{x_{2}})^{2}\right)\rho_{AB}\right]}.$
(24)

Let us now compute a universal upper bound on the second factor. For any
measurement operators $P_{x_{1}}$ and $Q_{x_{2}}$, it is true that
$P_{x_{1}}^{2}\leq P_{x_{1}}$ and $Q_{x_{2}}^{2}\leq Q_{x_{2}}$ (recall that
for Hermitian operators $X,Y$ the inequality $X\geq Y$ is equivalent to
$X-Y\geq 0$). Thus,

$\displaystyle\sum_{x_{1},x_{2}}(P_{x_{1}}-Q_{x_{2}})^{2}$
$\displaystyle=\sum_{x_{1},x_{2}}(P_{x_{1}}^{2}+Q_{x_{2}}^{2}-\\{P_{x_{1}},\,Q_{x_{2}}\\})$
$\displaystyle\leq\sum_{x_{1},x_{2}}(P_{x_{1}}+Q_{x_{2}}-\\{P_{x_{1}},\,Q_{x_{2}}\\})=2(d-1)\mathds{1}.$
(25)

Therefore, the second factor is upper bounded by $\sqrt{2(d-1)}$. Using the
assumption that the measurement operators of Alice are projective, we can
rewrite the observable as $A_{x}^{2}=A_{x}^{(1)}+A_{x}^{(2)}$. Therefore,

$\displaystyle\mathcal{C}_{d}\leq\sqrt{2(d-1)\sum_{x}\lambda_{x}^{2}\,\operatorname{tr}\left[\left(\left(A_{x}^{(1)}+A_{x}^{(2)}\right)\otimes\mathds{1}\right)\rho_{AB}\right]}.$
(26)

Finally, if we define

$\displaystyle\gamma:=\sum_{x}\lambda_{x}^{2}\,\operatorname{tr}\left[\left((A_{x}^{(1)}+A_{x}^{(2)})\otimes\mathds{1}\right)\rho_{AB}\right],$
(27)

it is easy to see that $\mathcal{F}_{d}$ is upper bounded by

$\displaystyle\mathcal{F}_{d}\leq\sqrt{2(d-1)\gamma}-\frac{1}{2}\,\gamma.$
(28)

The last step is to maximize the right-hand side of Eq. (28) over
$\gamma=[0,d(d-1)]$ (it is easy to verify that the maximal value of $\gamma$
equals $\sum_{x}\lambda_{x}^{2}=d(d-1)$). Using elementary calculus we
conclude that the right-hand side is maximized only when $\gamma=2(d-1)$,
which leads to the final bound:

$\displaystyle\mathcal{F}_{d}\leq d-1.$ (29)

At this point, the reader can better appreciate why we needed to introduce a
penalty in Eq. (3). In Eq. (28), $\gamma$ is maximized over the interval
$[0,d(d-1)]$. Then, the maximal $\gamma$ can be found at $2(d-1)$, giving us
the quantum value above. Now, note that if our functional had no penalty, it
would be written as $\mathcal{F}_{d}=\mathcal{C}_{d}$ and the maximization of
$\mathcal{C}_{d}$ in terms of $\gamma$ would produce

$\displaystyle\mathcal{C}_{d}\leq\sqrt{2(d-1)\gamma}.$ (30)

In this case, $\gamma$ is maximal at $d(d-1)$, in the edge of the interval, so
$\mathcal{C}_{d}$ is upper bounded by $\sqrt{2d}(d-1)$. On the other hand, by
comparing Eqs. (8) and (11), we obtain that the realization produced by the
maximally entangled state is simply $\mathcal{C}_{d}=2(d-1)$. In a nutshell,
introducing the penalty over the outputs $a=1$ and $2$, force the realization
by the maximally entangled state the same as the upper bound for
$\mathcal{F}_{d}$ so that this state turns out to be optimal.

In addition, note that, without penalty, Alice never outputs $a=\perp$. Then,
the inclusion of a third output is justified. It allows Alice to play the game
and be penalized or not to play the game and keep the value of the realization
unchanged. Adding that a third output also guarantees that the spectrum of
$A_{x}$ is proportional to the spectrum of $P_{x_{1}}-Q_{x_{2}}$, since
$\text{spec}\,(P_{x_{1}}-Q_{x_{2}})\in\\{\pm\lambda_{x},~{}0\\}$.

### A. A.2 An extension to $N>2$ rank-one projective measurements

The original functionals tailored to MUBs in Ref. Tavakoli  _et al._ (2021)
have recently been extended to $N>2$ bases Colomer  _et al._ (2022) and it
turns out that an analogous extension can be constructed for non-MUB
measurements. In this subsection, we present this generalization.

Suppose a bipartite Bell scenario in which Alice is given a string
$x=(j,\,k)\,x_{1}x_{2}\,...\,x_{N}$, in which $x_{i}\in[d]$, for
$i=1,~{}...,~{}N$, and $(j,\,k)$ is an ordered pair such that
$j\in[N]-\\{N\\}$, $k\in[N]-\\{1\\}$ and $j<k$. Similarly to the previous
case, Alice now outputs $a\in\\{1,\,2,\,...,\,N,\,\perp\\}$. On the other
hand, the outputs of Bob are kept unchanged, while the possible inputs are
$y\in[N]$.

Fig. 2: A Bell scenario extended to a set of $N>2$ projective measurements.
Now, Alice is given a string with $N$ digits $x_{1},~{}x_{2},~{}...,~{}x_{N}$
ranging from $1$ to $d$ and an ordered pair $(j,\,k)$, such that
$j\in[N]-\\{N\\}$ and $k\in[N]-\\{1\\}$. Similarly, Alice’s now output ranges
from $1$ to $N$ and includes $\perp$. Bob takes an input $y\in[N]$ and
produces output $b\in[d]$.

Now, consider $N$ $d$-dimensional orthonormal bases
$\\{\ket{e_{x_{1}}^{(1)}}\\}_{x_{1}=1}^{d}$,
$\\{\ket{e_{x_{2}}^{(2)}}\\}_{x_{2}=1}^{d}$, …,
$\\{\ket{e_{x_{N}}^{(N)}}\\}_{x_{N}=1}^{d}$, where $d\geq 2$, and define

$\displaystyle\lambda_{x}^{(j,k)}:=\sqrt{1-|\braket{e_{x_{j}}^{(j)}}{e_{x_{k}}^{(k)}}|^{2}}.$
(31)

For a fixed pair $(j,~{}k)$, consider the following functional

$\displaystyle\mathcal{F}_{d}^{(j,k)}:=\sum_{x_{j},x_{k}=1}^{d}\,\lambda^{(j,k)}_{x}\Bigg{(}\sum_{y\in\\{j,k\\}}\left[\,p(y,\,x_{y}|x,\,y)-p(\bar{y},\,x_{y}|x,\,y)\right]-\frac{1}{2}\lambda^{(j,k)}_{x}\,\left[\,p(a=j|x)+p(a=k|x)\right]\Bigg{)},$
(32)

where $\bar{y}$ flips the value of $y$ from $j$ to $k$ and vice-versa. Then,
$\mathcal{F}_{d}$ can be generalized by considering

$\displaystyle\mathcal{F}_{d}^{N}=\sum_{j<k}^{N}\mathcal{F}_{d}^{(j,k)}.$ (33)

If written so, Eq. (33) is clearly upper bounded by

$\displaystyle\mathcal{F}_{d}^{N}\leq\frac{1}{2}N(N-1)(d-1),$ (34)

as we can simply use Eq. (29) to sum the $\binom{N}{2}$ terms of Eq. (33).

This upper bound can be saturated if the $N$ orthonormal bases
$\\{\ket{e_{x_{i}}^{(i)}}\\}_{x_{i}=1}^{d}$ in dimension $d$ are such that
$\lambda^{(j,k)}_{x}>0$, for all $j,~{}k$, $x$ and $i=1,\,2,\,...,\,N$. In
this case, we can mirror the optimal realization proposed in the main text by
taking the same state as in Eq. (6),
$P_{x_{i}}=\ket{e_{x_{i}}^{(i)}}\\!\\!\bra{e_{x_{i}}^{(i)}}$ when Bob is given
$y=i$ and

$\displaystyle
A_{x}^{(j,k)}=\frac{1}{\lambda_{x}^{(j,k)}}(P_{x_{j}}-Q_{x_{k}})^{\mathsf{T}}.$
(35)

Moreover, according to Theorem 2 the functional in Eq. (33) is non-trivial,
if, for the $N$ orthonormal bases, the condition $\lambda^{(j,k)}_{x}>0$,
$\forall~{}j,~{}k,~{}x$, is satisfied.

Lastly, an interesting problem can be posed if, instead of providing $N$
orthonormal bases, we specify $\lambda^{(j,k)}_{x}$ and try to recover the
bases. In this case, it is not clear if this problem has a solution for any
$N$ or arrangements of $\lambda^{(j,k)}_{x}$. For instance, if we consider

$\displaystyle|\braket{e_{x_{j}}^{(j)}}{e_{x_{k}}^{(k)}}|^{2}=\frac{1}{d},\quad\forall\,j,~{}k~{}\in[N]~{}\text{and}~{}x_{j},x_{k}\in[d],$
(36)

we fix the values of $\lambda^{(j,k)}_{x}$ to be uniform. The resulting
functionals are the same as the ones derived in Ref. Colomer  _et al._ (2022)
up to a factor of $\sqrt{1-\nicefrac{{1}}{{d}}}$. The numerical results of
Ref. Colomer  _et al._ (2022) confirm what is already known in the literature:
there is no more than $d+1$ MUBs in dimension $d$ and the Zauner’s conjecture
Zauner (1999) holds.

##  Appendix B Certification

In what follows, we present the proof of Theorem 1. First, we demonstrate the
device-independent certification of the measurements of Bob, based solely on
the condition that $\beta_{Q}$ is saturated. Recall that, as in Appendix A.1,
for the certification of the measurements of Bob, we can assume that the
measurements of Alice are projective since we are not interested in their
characterization. Next, we construct an isometry capable of extracting a
maximally entangled state of dimension $d$. Lastly, we discuss some
exceptional cases in which state certification cannot be achieved.

### B. B.1 Bob’s measurements (proof of the first part of Theorem 1)

If Ineq. (29) is saturated, all of the inequalities used in Appendix A.1
should be tight. This enables us to get some information about the state and
measurements capable of achieving the quantum value.

The first step we must consider is going from Eq. (21) to Ineq. (22), where
the terms of $\mathcal{C}_{d}$ are bounded by the absolute value:

$\displaystyle\mathcal{C}_{d}=\sum_{x}\lambda_{x}\,\operatorname{tr}\left[(A_{x}\otimes(P_{x_{1}}-Q_{x_{2}}))\rho_{AB}\right]\leq\sum_{x}\left|\lambda_{x}\,\operatorname{tr}\left[(A_{x}\otimes(P_{x_{1}}-Q_{x_{2}}))\rho_{AB}\right]\right|.$
(37)

If the above inequality is tight, the argument of the absolute value must be
non-negative. Since, by construction, $\lambda_{x}>0$, we conclude that
$\operatorname{tr}\left[A_{x}\otimes(P_{x_{1}}-Q_{x_{2}})\rho_{AB}\right]\geq
0$.

The saturation condition of the Cauchy–Schwarz inequality in Ineq. (23), in
turn, implies that,

$\displaystyle\lambda_{x}\,A_{x}\otimes\mathds{1}\,\rho_{AB}^{\nicefrac{{1}}{{2}}}=\mu_{x}\mathds{1}\otimes(P_{x_{1}}-Q_{x_{2}})\,\rho_{AB}^{\nicefrac{{1}}{{2}}},\quad\forall\>x=x_{1}x_{2},$
(38)

where $\mu_{x}\in\mathbb{C}$ is the proportionality constant. Right-
multiplying it by $\rho_{AB}^{\nicefrac{{1}}{{2}}}$ and left-multiplying by
$\mathds{1}\otimes(P_{x_{1}}-Q_{x_{2}})$ leads to

$\displaystyle\lambda_{x}\,A_{x}\otimes(P_{x_{1}}-Q_{x_{2}})\,\rho_{AB}=\mu_{x}\mathds{1}\otimes(P_{x_{1}}-Q_{x_{2}})^{2}\,\rho_{AB}.$
(39)

If we trace both sides of this equation and use the fact that
$\operatorname{tr}\left[A_{x}\otimes(P_{x_{1}}-Q_{x_{2}})\rho_{AB}\right]\geq
0$ (deduced above), we conclude that $\mu_{x}$ is real and non-negative.

The saturation condition of Ineq. (24) implies that

$\displaystyle\lambda_{x}^{2}\,A_{x}^{2}\otimes\mathds{1}\,\rho_{AB}=\eta\,\mathds{1}\otimes(P_{x_{1}}-Q_{x_{2}})^{2}\,\rho_{AB}\,\quad\forall\>x=x_{1},\,x_{2},$
(40)

where $\eta$ is independent of $x$ since the Cauchy–Schwarz in Ineq. (24) is
applied to the entire summation. Now, let us multiply Eq. (38) by its
Hermitian conjugate and take the trace:

$\displaystyle\lambda_{x}^{2}\,\operatorname{tr}\left[A_{x}^{2}\otimes\mathds{1}\,\rho_{AB}\right]=\mu_{x}^{2}\,\operatorname{tr}\left[\mathds{1}\otimes(P_{x_{1}}-Q_{x_{2}})^{2}\,\rho_{AB}\right]$
(41)

Comparing Eqs. (41) and (40) we conclude that $\mu_{x}=\sqrt{\eta}$, for all
$x$. So, let us drop the index of $\mu_{x}$ and use just $\mu$ from now on.

The last but not less important saturation condition is implicit in Ineq. (25)
where we upper bound the following quantity by:

$\displaystyle\sum_{x}\operatorname{tr}\left[\left(\mathds{1}\otimes(P_{x_{1}}^{2}+Q_{x_{2}}^{2}-\\{P_{x_{1}},\,Q_{x_{2}}\\})\right)\rho_{AB}\right]\leq\sum_{x}\operatorname{tr}\left[\left(\mathds{1}\otimes(P_{x_{1}}+Q_{x_{2}}-\\{P_{x_{1}},\,Q_{x_{2}}\\})\right)\rho_{AB}\right].$
(42)

After a short algebraic manipulation, we get

$\displaystyle\operatorname{tr}\left[\left(\mathds{1}\otimes\sum_{x_{1}}(P_{x_{1}}-P_{x_{1}}^{2})\right)\rho_{AB}\right]+\operatorname{tr}\left[\left(\mathds{1}\otimes\sum_{x_{2}}(Q_{x_{2}}-Q_{x_{2}}^{2})\right)\rho_{AB}\right]\geq
0.$ (43)

If we trace over Alice’s subsystem, the term-by-term saturation of the above
inequality implies

$\displaystyle\begin{aligned}
\operatorname{tr}\left[(P_{x_{1}}-P_{x_{1}}^{2})\rho_{B}\right]&=0,\quad\forall\,x_{1}\\\
\operatorname{tr}\left[(Q_{x_{2}}-Q_{x_{2}}^{2})\rho_{B}\right]&=0,\quad\forall\,x_{2}.\end{aligned}$
(44)

Since both $P_{x_{1}}-P_{x_{1}}^{2}$ (or $Q_{x_{2}}-Q_{x_{2}}^{2}$) and
$\rho_{B}$ are positive semi-definite operators and their product has a null
trace, they must be orthogonal:

$\displaystyle\begin{aligned} (P_{x_{1}}-P_{x_{1}}^{2})\rho_{B}&=0,\\\
(Q_{x_{2}}-Q_{x_{2}}^{2})\rho_{B}&=0.\end{aligned}$ (45)

Assuming that Bob’s marginal state is full rank, it is possible to eliminate
$\rho_{B}$ out of Eqs. (45) by right-multiplying it by $\rho_{B}^{-1}$. This
way, we conclude that the saturation of Ineq. (25) implies that both
measurements of Bob are projective. We can use this fact to sum Eq. (41) over
$x$ to obtain

$\displaystyle\sum_{x}\lambda_{x}^{2}\,\operatorname{tr}\left[A_{x}^{2}\otimes\mathds{1}\,\rho_{AB}\right]$
$\displaystyle=\mu^{2}\sum_{x}\operatorname{tr}\left[\mathds{1}\otimes(P_{x_{1}}-Q_{x_{2}})^{2}\right]$
(46)

Note that, if we assume the measurements of Alice to be projective, the right-
hand side of the above equation can be identified as $\gamma$, in Eq. (27). On
the other hand, the left-hand side can be summed to $2\mu^{2}(d-1)$. The only
value of $\gamma$ which allows for the quantum value in Eq. (28) is $2(d-1)$,
so we conclude that $\mu=1$.

Having obtained the value of the proportionality constants, let us right-
multiply Eq. (38) by $\rho_{AB}^{\nicefrac{{1}}{{2}}}$ and use $\mu=1$ to
rewrite the following relation:

$\displaystyle\lambda_{x}A_{x}\otimes\mathds{1}\,\rho_{AB}=\,\mathds{1}\otimes(P_{x_{1}}-Q_{x_{2}})\,\rho_{AB}.$
(47)

Again, assuming that the measurements of Alice are projective, we can use the
Eq. (4) to write $A_{x}^{3}=A_{x}$. Combining it with Eq. (47), we get

$\displaystyle\frac{1}{\lambda_{x}}\,\mathds{1}\otimes(P_{x_{1}}-Q_{x_{2}})\,\rho_{AB}=\frac{1}{\lambda_{x}^{3}}\,\mathds{1}\otimes(P_{x_{1}}-Q_{x_{2}})^{3}\,\rho_{AB}.$
(48)

Since we have eliminated Alice’s observable out of the equation, we can derive
a relation involving only Bob’s measurement operators by tracing out Alice’s
subsystem and right-multiplying by the inverse of Bob’s marginal state:

$\displaystyle\lambda_{x}^{2}(P_{x_{1}}-Q_{x_{2}})=(P_{x_{1}}-Q_{x_{2}})^{3}.$
(49)

After some algebraic manipulation,

$\displaystyle
O_{x_{1}x_{2}}^{2}(P_{x_{1}}-Q_{x_{2}})=P_{x_{1}}Q_{x_{2}}P_{x_{1}}-Q_{x_{2}}P_{x_{1}}Q_{x_{2}}.$
(50)

Now, if we sum over $x_{1}$,

$\displaystyle\sum_{x_{1}}O_{x_{1}x_{2}}^{2}P_{x_{1}}-\sum_{x_{1}}O_{x_{1}x_{2}}^{2}Q_{x_{2}}$
$\displaystyle=\sum_{x_{1}}(P_{x_{1}}Q_{x_{2}}P_{x_{1}}-Q_{x_{2}}P_{x_{1}}Q_{x_{2}})$
(51) $\displaystyle\sum_{x_{1}}O_{x_{1}x_{2}}^{2}P_{x_{1}}-Q_{x_{2}}$
$\displaystyle=\sum_{x_{1}}(P_{x_{1}}Q_{x_{2}}P_{x_{1}})-Q_{x_{2}}^{2}.$ (52)

Because $Q_{x_{2}}=Q_{x_{2}}^{2}$,

$\displaystyle\sum_{x_{1}}O_{x_{1}x_{2}}^{2}P_{x_{1}}$
$\displaystyle=\sum_{x_{1}}(P_{x_{1}}Q_{x_{2}}P_{x_{1}})$ (53)

Finally, since the $P_{x_{1}}$ projectors are orthogonal, this equality must
hold term by term:

$\displaystyle O_{x_{1}x_{2}}^{2}P_{x_{1}}=P_{x_{1}}Q_{x_{2}}P_{x_{1}}.$ (54)

The summation over $x_{2}$ gives us the complementary equation:

$\displaystyle O_{x_{1}x_{2}}^{2}Q_{x_{2}}=Q_{x_{2}}P_{x_{1}}Q_{x_{2}}.$ (55)

Lastly, let us show that these two equations are complete i.e., if for some
finite-dimensional measurements Eqs. (54) and (55) hold, then it is possible
to construct a realization that achieves the quantum value of
$\mathcal{F}_{d}$. This means that the conditions derived are, at least for
finite-dimensional measurements, necessary and sufficient, and no tighter
characterisation can be obtained.

Consider an incompatible pair of measurements $\\{P_{x_{1}}\\}_{x_{1}=1}^{d}$
and $\\{Q_{x_{2}}\\}_{x_{2}=1}^{d}$ acting on a $D$-dimensional Hilbert space,
with $D<\infty$, satisfying Eqs. (54) and (55), for some set of overlaps
$0<O_{x_{1}x_{2}}<1$. Then, both $P_{x_{1}}$ and $Q_{x_{2}}$ are projectors
and have equal traces, for all $x_{1},~{}x_{2}\in\\{1,~{}...,~{}d\\}$. The
projectivity can be demonstrated by simply summing Eqs. (54) and (55) over
$x_{1}$ and $x_{2}$ to get $P_{x_{1}}=P_{x_{1}}^{2}$ and
$Q_{x_{2}}=Q_{x_{2}}^{2}$, respectively. Showing that
$\operatorname{tr}(P_{x_{1}})=\operatorname{tr}(Q_{x_{2}})$ relies on
demonstrating that the projectors are isomorphic. Defining
$W_{x_{1}x_{2}}=\frac{1}{O_{x_{1}x_{2}}}P_{x_{1}}Q_{x_{2}}$ we can see that,
for $O_{x_{1}x_{2}}>0$,

$\displaystyle
W_{x_{1}x_{2}}W_{x_{1}x_{2}}^{\dagger}=P_{x_{1}}\quad\text{and}\quad
W_{x_{1}x_{2}}^{\dagger}W_{x_{1}x_{2}}=Q_{x_{2}}.$ (56)

For a finite-dimensional Hilbert space this implies that
$\operatorname{tr}(P_{x_{1}})=\operatorname{tr}(Q_{x_{2}})=n$, for some fixed
$n\in\mathbb{N}$. Because the dimension of the Hilbert space is finite, we
rewrite $D$ as simply

$\displaystyle
D=\operatorname{tr}\mathds{1}=\sum_{x_{1}}^{d}\operatorname{tr}P_{x_{1}}=dn.$
(57)

Then, we construct a Hermitian operator $B_{x_{1}x_{2}}=P_{x_{1}}-Q_{x_{2}}$.
By computing an explicit expression for $B_{x_{1}x_{2}}^{3}$, one can show
that it satisfies a relation analogous to Eq. (49):

$\displaystyle
B_{x_{1}x_{2}}^{3}=\lambda_{x}^{2}B_{x_{1}x_{2}},\quad\forall~{}x_{1},~{}x_{2}\in\\{1,~{}...,~{}d\\}.$
(58)

Clearly, the spectrum of $B_{x_{1}x_{2}}$ belongs to $\\{0,\pm\lambda_{x}\\}$.
Because the trace of $B_{x_{1}x_{2}}$ is null, the multiplicity of its non-
null eigenvalues must be the same. So, let us calculate

$\displaystyle\operatorname{tr}(B_{x_{1}x_{2}}^{2})$
$\displaystyle=\operatorname{tr}\left(P_{x_{1}}+Q_{x_{2}}-\\{P_{x_{1}},\,Q_{x_{2}}\\}\right)$
$\displaystyle=2n-\operatorname{tr}\left(\\{P_{x_{1}},\,Q_{x_{2}}\\}\right)$
$\displaystyle=2n-2\operatorname{tr}(P_{x_{1}}Q_{x_{2}}P_{x_{1}})=2n\lambda_{x}^{2},$
(59)

where we have used that
$\operatorname{tr}(P_{x_{1}}Q_{x_{2}})=\operatorname{tr}(P_{x_{1}}Q_{x_{2}}P_{x_{1}})$.
Thus, both $+\lambda_{x}$ and $-\lambda_{x}$ must have multiplicity $n$.

Now, let us define a realization of $\mathcal{F}_{d}$ in which the
measurements of Bob are represented by $P_{x_{1}}$ and $Q_{x_{2}}$, the
observables of Alice are given by
$A_{x}=\nicefrac{{1}}{{\lambda_{x}}}B_{x_{1}x_{2}}^{\textsf{T}}$ and the state
is the $D$-dimensional maximally entangled state $\ket{\Phi_{D}^{+}}$. Like in
Eq. (5), the spectrum of $A_{x}$ also belongs to $\\{0,\,\pm 1\\}$. Then,
evaluating the correlation score gives

$\displaystyle\mathcal{C}_{d}$
$\displaystyle=\sum_{x}\lambda_{x}\bra{\Phi_{D}^{+}}A_{x}\otimes
B_{x_{1}x_{2}}\ket{\Phi_{D}^{+}}=\sum_{x}\bra{\Phi_{D}^{+}}\mathds{1}\otimes
B_{x_{1}x_{2}}^{2}\ket{\Phi_{D}^{+}}$
$\displaystyle=\frac{1}{D}\sum_{x}\operatorname{tr}(B_{x_{1}x_{2}}^{2})=\frac{1}{dn}\sum_{x}2n\left(1-O_{x_{1}x_{2}}^{2}\right)=2(d-1),$
(60)

where we used the fact that the local state of Bob is
$\nicefrac{{\mathds{1}}}{{D}}$. For the final score, we obtain

$\displaystyle\mathcal{F}_{d}$
$\displaystyle=\mathcal{C}_{d}-\frac{1}{2}\sum_{x}\lambda_{x}^{2}\bra{\Phi_{D}^{+}}A_{x}^{2}\otimes\mathds{1}\ket{\Phi_{D}^{+}}=\mathcal{C}_{d}-\frac{1}{2}\sum_{x}\bra{\Phi_{D}^{+}}\mathds{1}\otimes
B_{x_{1}x_{2}}^{2}\ket{\Phi_{D}^{+}}=\mathcal{C}_{d}-\frac{1}{2D}\sum_{x}\operatorname{tr}(B_{x_{1}x_{2}}^{2})=d-1,$
(61)

as desired.

### B. B.2 The state (proof of the second part of Theorem 1)

Here, we present the argument for the certification of the state. We show
that, if the overlap matrix $O$ has at least one column or row whose entries
are non-zero, then for any realization that saturates the quantum value of
$\mathcal{F}_{d}$ we can construct local isometries
$V_{A}:\>\mathcal{H}_{A}\rightarrow\mathbb{C}^{d}\otimes\mathcal{H}_{A}$ and
$V_{B}:\>\mathcal{H}_{B}\rightarrow\mathbb{C}^{d}\otimes\mathcal{H}_{B}$ such
that:

$\displaystyle(V_{A}\otimes V_{B})\rho_{AB}(V_{A}^{\dagger}\otimes
V_{B}^{\dagger})=\Phi^{+}_{d}\otimes\rho_{\text{aux}},$ (62)

where
$\rho_{AB}\in\mathcal{L}\left(\mathcal{H}_{A}\otimes\mathcal{H}_{B}\right)$ is
the shared state, $\Phi^{+}_{d}$ is the $d$-dimensional maximally entangled
state, and $\rho_{\text{aux}}$ corresponds to the uncharacterized part of
$\rho_{AB}$. In particular, note that the isometries depend on the measurement
operators of Bob, as explained below.

Let us start by defining the isometry on Bob’s side. To do this, we need to
assume that the $j$-th column of $O$ is non-zero, i.e. $O_{i,j}\neq 0$, for
all $i$. Then, we introduce the isometry $V_{B}:=SR$, where
$R:\>\mathcal{H}_{B}\rightarrow\mathbb{C}^{d}\otimes\mathcal{H}_{B}$ and
$S:\>\mathbb{C}^{d}\otimes\mathcal{H}_{B}\rightarrow\mathbb{C}^{d}\otimes\mathcal{H}_{B}$
are defined by

$\displaystyle R$ $\displaystyle:=\sum_{i}\ket{i}\otimes P_{i}\quad\text{and}$
(63) $\displaystyle S$ $\displaystyle:=\sum_{k}\ket{k}\\!\\!\bra{k}\otimes
U_{k}.$ (64)

$U_{k}$ is a unitary operator defined as

$\displaystyle U_{k}:=\sum_{i}\frac{1}{O_{i,j}O_{i+k,j}}P_{i}Q_{j}P_{i+k}.$
(65)

Note that the subscripts in both $P_{i+k}$ and $O_{i+k,j}$ are taken as sum
modulo $d$, where the result is in the set $\\{1,~{}...,~{}d\\}$. Then, the
action of $U_{k}$ produces a cyclic shift on $\\{P_{i}\\}_{i=1}^{d}$:

$\displaystyle U_{k}P_{i}U_{k}^{\dagger}=P_{i-k}.$ (66)

Finally, $V_{B}$ is rewritten as

$\displaystyle V_{B}=\sum_{i}\ket{i}\otimes
U_{i}P_{i}=\frac{1}{O_{d,j}}\sum_{i}\frac{1}{O_{i,j}}\ket{i}\otimes
P_{d}Q_{j}P_{i}.$ (67)

For Alice’s side, let us first define a pair of operators whose action in
$\mathcal{H}_{A}$ is analogous to the action of $P_{x_{1}}$ and $Q_{x_{2}}$ on
Bob’s side:

$\displaystyle\begin{aligned}
\tilde{P}_{x_{1}}&:=\frac{1}{d}\bigg{(}\mathds{1}+\sum_{x_{2}}\lambda_{x}A_{x}\bigg{)},\\\
\tilde{Q}_{x_{2}}&:=\frac{1}{d}\bigg{(}\mathds{1}-\sum_{x_{1}}\lambda_{x}A_{x}\bigg{)}.\end{aligned}\qquad\forall\;x=x_{1}x_{2}$
(68)

If written as in the above equation, $\tilde{P}_{x_{1}}$ and
$\tilde{Q}_{x_{2}}$ satisfy

$\displaystyle\begin{aligned}
(\tilde{P}_{x_{1}}\otimes\mathds{1})\rho_{AB}&=(\mathds{1}\otimes
P_{x_{1}})\rho_{AB},\\\
(\tilde{Q}_{x_{2}}\otimes\mathds{1})\rho_{AB}&=(\mathds{1}\otimes
Q_{x_{2}})\rho_{AB},\end{aligned}$ (69)

for all $\rho_{AB}$, $\\{P_{x_{1}}\\}_{x_{1}=1}^{d}$ and
$\\{Q_{x_{2}}\\}_{x_{2}=1}^{d}$ that saturate the quantum value. The new
operators $\tilde{P}_{x_{1}}$ and $\tilde{Q}_{x_{2}}$ satisfy similar
algebraic relations that their counterparts on Bob’s side. By taking the
partial trace over Bob’s marginal state, we can easily verify from Eqs. (69)
that

$\displaystyle\begin{aligned}
\tilde{P}_{x_{1}}\rho_{A}&=\tilde{P}_{x_{1}}^{2}\rho_{A},\\\
\tilde{Q}_{x_{2}}\rho_{A}&=\tilde{Q}_{x_{2}}^{2}\rho_{A}.\end{aligned}$ (70)

Also, an analogous version of Eqs. (54) and (55) must be satisfied by
$\tilde{P}_{x_{1}}$ and $\tilde{Q}_{x_{2}}$:

$\displaystyle(\tilde{P}_{x_{1}}\otimes\mathds{1})\rho_{AB}$
$\displaystyle=(\mathds{1}\otimes
P_{x_{1}})\rho_{AB}=\frac{1}{O_{x_{1},x_{2}}^{2}}(\mathds{1}\otimes
P_{x_{1}}Q_{x_{2}}P_{x_{1}})\rho_{AB}=\frac{1}{O_{x_{1},x_{2}}^{2}}(\tilde{P}_{x_{1}}\tilde{Q}_{x_{2}}\tilde{P}_{x_{1}}\otimes\mathds{1})\rho_{AB},$
(71)

which leads to

$\displaystyle\begin{aligned}
O_{x_{1},x_{2}}^{2}\tilde{P}_{x_{1}}&=\tilde{P}_{x_{1}}\tilde{Q}_{x_{2}}\tilde{P}_{x_{1}}\quad\text{and}\\\
O_{x_{1},x_{2}}^{2}\tilde{Q}_{x_{1}}&=\tilde{Q}_{x_{2}}\tilde{P}_{x_{1}}\tilde{Q}_{x_{2}}.\end{aligned}$
(72)

Lastly, defining $\tilde{R}$, $\tilde{S}$ and $\tilde{U}_{k}$ analogously to
Eqs. (63), (64) and (65), respectively, by replacing
$P_{x_{1}}\rightarrow\tilde{P}_{x_{1}}$ and
$Q_{x_{2}}\rightarrow\tilde{Q}_{x_{2}}$, we get a similar expression for
$V_{A}$:

$\displaystyle V_{A}:=\sum_{i}\ket{i}\otimes\tilde{U}_{i}\tilde{P}_{i}.$ (73)

Now, let us evaluate the action of $V$ on the state. Defining
$\rho_{\text{out}}:=(V_{A}\otimes V_{B})\rho_{AB}(V_{A}^{\dagger}\otimes
V_{B}^{\dagger})$ gives

$\displaystyle\rho_{\text{out}}=\sum_{i,i^{\prime}}\sum_{j,j^{\prime}}\ket{i,i^{\prime}}\\!\\!\bra{j,j^{\prime}}\otimes(\tilde{U}_{i}\tilde{P}_{i}\otimes
U_{i^{\prime}}P_{i^{\prime}})\rho_{AB}(\tilde{P}_{j}\tilde{U}_{j}^{\dagger}\otimes
P_{j^{\prime}}U_{j^{\prime}}^{\dagger})$ (74)

and because of Eqs. (69),

$\displaystyle(\tilde{U}_{i}\tilde{P}_{i}\otimes
U_{i^{\prime}}P_{i^{\prime}})\rho_{AB}(\tilde{P}_{j}\tilde{U}_{j}^{\dagger}\otimes
P_{j^{\prime}}U_{j^{\prime}}^{\dagger})$ $\displaystyle=(\tilde{U}_{i}\otimes
U_{i^{\prime}}P_{i^{\prime}})(\tilde{P}_{i}\otimes\mathds{1})\rho_{AB}(\tilde{P}_{j}\otimes\mathds{1})(\tilde{U}_{j}^{\dagger}\otimes
P_{j^{\prime}}U_{j^{\prime}}^{\dagger})$ $\displaystyle=(\tilde{U}_{i}\otimes
U_{i^{\prime}}P_{i^{\prime}})(\mathds{1}\otimes
P_{i})\rho_{AB}(\mathds{1}\otimes P_{j})(\tilde{U}_{j}^{\dagger}\otimes
P_{j^{\prime}}U_{j^{\prime}}^{\dagger})$
$\displaystyle=\delta_{i,i^{\prime}}\delta_{j,j^{\prime}}(\tilde{U}_{i}\otimes
U_{i}P_{i})\rho_{AB}(\tilde{U}_{j}^{\dagger}\otimes P_{j}U_{j}^{\dagger}).$
(75)

Thus, $\rho_{\text{out}}$ turns to be

$\displaystyle\rho_{\text{out}}=\sum_{i,j}\ket{i,i}\\!\\!\bra{j,j}\otimes(\tilde{U}_{i}\otimes
U_{i}P_{i})\rho_{AB}(\tilde{U}_{j}^{\dagger}\otimes P_{j}U_{j}^{\dagger}).$
(76)

Using Eqs. (69) it is possible to show that

$\displaystyle(\tilde{U}_{k}\otimes\mathds{1})\rho_{AB}=(\mathds{1}\otimes
U_{k}^{\dagger})\rho_{AB},$ (77)

and

$\displaystyle\rho_{\text{out}}=\sum_{i,j}\ket{i,i}\\!\\!\bra{j,j}\otimes(\mathds{1}\otimes
U_{i}P_{i}U_{i}^{\dagger})\rho_{AB}(\mathds{1}\otimes
U_{j}P_{j}U_{j}^{\dagger})=\Phi^{+}_{d}\otimes d(\mathds{1}\otimes
P_{d})\rho_{AB}(\mathds{1}\otimes P_{d}).$ (78)

Finally, as $\rho_{\text{out}}$ must constitute a normalized state, we must
have

$\displaystyle\operatorname{tr}\left[\left(\mathds{1}\otimes
P_{d}\right)\rho_{AB}\right]=\frac{1}{d}.$ (79)

Eq. (78) leads us to two conclusions. Firstly, it is possible to certify the
shared state whenever $O$ is a matrix possessing at least one column filled
with non-zero elements, as in Eq. (65). Secondly, as $P_{d}$ is arbitrarily
labeled, the maximal violation also implies that the marginal distribution of
$\\{P_{x_{1}}\\}_{x_{1}=1}^{d}$ is uniform. In fact, replacing $U_{k}$ in Eq.
(64) by $U_{k+l}$, where $l\in\\{1,~{}...,~{}d\\}$, leads to

$\displaystyle\operatorname{tr}\left[\left(\mathds{1}\otimes
P_{x_{1}}\right)\rho_{AB}\right]=\frac{1}{d}\quad\forall\>x_{1}\in[\,1,\,...,\,d\,].$
(80)

In addition, note that $P_{i}$ and $Q_{j}$ in Eqs. (63) and (65) can be
interchanged. If one does so, the state certification can be made whenever $O$
has at least one non-zero row, and, in this case, the marginal distribution of
$\\{Q_{x_{2}}\\}_{x_{2}=1}^{d}$ is guaranteed to be uniform:

$\displaystyle\operatorname{tr}\left[\left(\mathds{1}\otimes
Q_{x_{2}}\right)\rho_{AB}\right]=\frac{1}{d}\quad\forall\>x_{2}\in[\,1,\,...,\,d\,].$
(81)

### B. B.3 Exceptional cases for state certification

The presented method for certification works for a wide class of overlap
matrices, but it still requires that $O$ must have at least one column or row
whose entries are non-zero. This case does not include, for instance, overlap
matrices as in the Eq. (20). In this section, let us provide an example of a
state different than $\ket{\Phi_{d}^{+}}$ that also achieves $\beta_{Q}$ for
such cases.

To introduce it, suppose a realization of $\mathcal{F}_{4}$ characterized by
$P_{x_{1}}=\ket{x_{1}}\\!\\!\bra{x_{1}}$ and
$Q_{x_{2}}=\ket{f_{x_{2}}}\\!\\!\bra{f_{x_{2}}}$, where
$x_{1},\,x_{2}=1,\,...,\,4$, and

$\displaystyle\begin{aligned}
\ket{f_{1}}=\frac{1}{\sqrt{2}}\left(\ket{1}+\ket{2}\right),&\quad\ket{f_{2}}=\frac{1}{\sqrt{2}}\left(\ket{1}-\ket{2}\right),\\\
\ket{f_{3}}=\frac{1}{\sqrt{2}}\left(\ket{3}+\ket{4}\right),&\;\>\text{and}\;\>\ket{f_{4}}=\frac{1}{\sqrt{2}}\left(\ket{3}-\ket{4}\right).\end{aligned}$
(82)

If considered so, the overlap matrix is given by

$\displaystyle
O=\begin{bmatrix}\nicefrac{{1}}{{\sqrt{2}}}&\nicefrac{{1}}{{\sqrt{2}}}&0&0\\\
\nicefrac{{1}}{{\sqrt{2}}}&\nicefrac{{1}}{{\sqrt{2}}}&0&0\\\
0&0&\nicefrac{{1}}{{\sqrt{2}}}&\nicefrac{{1}}{{\sqrt{2}}}\\\
0&0&\nicefrac{{1}}{{\sqrt{2}}}&\nicefrac{{1}}{{\sqrt{2}}}\end{bmatrix},$ (83)

that is, it has the form of Eq. (20), for $d=4$. In the same way as before,
the observables of Alice are defined as in Eq. (5). On the other hand, the
state is given by

$\displaystyle\rho_{AB}=\sum_{k=1}^{2}\left(\mathds{1}\otimes\Pi_{k}\right)\Phi_{4}^{+}\left(\mathds{1}\otimes\Pi_{k}\right)$
(84)

where $\Phi_{4}^{+}$ is the four-dimensional maximally entangled state and

$\displaystyle\begin{aligned}
\Pi_{1}&=\ket{1}\\!\\!\bra{1}+\ket{2}\\!\\!\bra{2}\\\
\Pi_{2}&=\ket{3}\\!\\!\bra{3}+\ket{4}\\!\\!\bra{4}.\end{aligned}$ (85)

If written in this way, it is easy to see that

$\displaystyle\Pi_{1}P_{x_{1}}\Pi_{1}=\begin{cases}P_{x_{1}}&\text{if}~{}x_{1}=1,\,2,\\\
0&\text{if}~{}x_{1}=3,\,4\end{cases}\quad\text{and}\quad\Pi_{2}P_{x_{1}}\Pi_{2}=\begin{cases}0&\text{if}~{}x_{1}=1,\,2,\\\
P_{x_{1}}&\text{if}~{}x_{1}=3,\,4,\end{cases}$ (86)

which can be generalized to both measurements of Bob and expressed in short as

$\displaystyle\sum_{k=1}^{2}\Pi_{k}P_{x_{1}}\Pi_{k}=P_{x_{1}}\;\;\text{and}\;\;\sum_{k=1}^{2}\Pi_{k}Q_{x_{2}}\Pi_{k}=Q_{x_{2}}.$
(87)

Now, note that this realization not only saturates the quantum value of
$\mathcal{F}_{4}$, but preserves the same statistics that would be produced by
substituting the four-dimensional maximally entangled state. To check it,
suppose an arbitrary observable $\Gamma$ of Alice, then

$\displaystyle\begin{aligned} \operatorname{tr}\left[\left(\Gamma\otimes
P_{x_{1}}\right)\Phi_{4}^{+}\right]&=\sum_{k}\operatorname{tr}\left[(\mathds{1}\otimes\Pi_{k})(\Gamma\otimes
P_{x_{1}})(\mathds{1}\otimes\Pi_{k})\Phi_{4}^{+}\right]\\\
&=\operatorname{tr}\left[(\Gamma\otimes
P_{x_{1}})\sum_{k}(\mathds{1}\otimes\Pi_{k})\Phi_{4}^{+}(\mathds{1}\otimes\Pi_{k})\right]=\operatorname{tr}\left[\left(\Gamma\otimes
P_{x_{1}}\right)\rho_{AB}\right],\end{aligned}$ (88)

where we just used Eq. (87) for $P_{x_{1}}$ and the cyclicity of the trace.

To verify that there is a clear difference between $\rho_{AB}$ and
$\Phi_{4}^{+}$, consider an isometry $V:=V_{A}\otimes V_{B}$ such that the
action of $V_{A}$ is defined as

$\displaystyle\begin{aligned}
V_{A}\ket{1}_{A}&=\ket{1}_{A}\ket{1}_{A^{\prime}},\\\
V_{A}\ket{2}_{A}&=\ket{1}_{A}\ket{2}_{A^{\prime}},\\\
V_{A}\ket{3}_{A}&=\ket{2}_{A}\ket{1}_{A^{\prime}}\quad\text{and}\\\
V_{A}\ket{4}_{A}&=\ket{2}_{A}\ket{2}_{A^{\prime}},\end{aligned}$ (89)

where $\ket{\cdot}_{A}$ denotes the marginal state of Alice, and
$\ket{\cdot}_{A^{\prime}}$ denotes the marginal state of an ancillary
subsystem of Alice. The action of $V_{B}$ is defined in the same way for the
marginal state of Bob and its ancillary subsystem. Then, by applying such an
isometry to $\rho_{AB}$ one gets

$\displaystyle
V\rho_{AB}V^{\dagger}=\frac{1}{2}\left(\ket{1}\\!\\!\bra{1}_{A}\otimes\ket{1}\\!\\!\bra{1}_{B}+\ket{2}\\!\\!\bra{2}_{A}\otimes\ket{2}\\!\\!\bra{2}_{B}\right)\otimes\left(\Phi_{2}^{+}\right)_{A^{\prime}B^{\prime}},$
(90)

where $\left(\Phi_{2}^{+}\right)_{A^{\prime}B^{\prime}}$ is the two-
dimensional maximally entangled state between subsystems $A^{\prime}$ and
$B^{\prime}$. In other words, one can show that, up to local isometries,
$\rho_{AB}$ is equivalent to a perfectly correlated classical random bit
combined with a single copy of
$\left(\Phi_{2}^{+}\right)_{A^{\prime}B^{\prime}}$.

One can extend this simple example to the case where the matrix of overlaps
has a block-diagonal structure with $K$ blocks of dimension $d_{k}$, where
$k=1,~{}...,~{}K$. In this case, consider the state

$\displaystyle\rho_{AB}=\sum_{k=1}^{K}\left(\mathds{1}\otimes\Pi_{k}\right)\Phi_{d}^{+}\left(\mathds{1}\otimes\Pi_{k}\right),$
(91)

where $\Pi_{k}$ projects into the $d_{k}$-dimensional subspace of the $k$-th
block of $O$. Using a proper definition of $V$, one can show that

$\displaystyle
V\rho_{AB}V^{\dagger}=\sum_{k=1}^{K}p_{k}\ket{k}\\!\\!\bra{k}_{A}\otimes\ket{k}\\!\\!\bra{k}_{B}\otimes\left(\Phi^{+}_{d_{k}}\right)_{A^{\prime}B^{\prime}},$
(92)

where $p_{k}=d_{k}/d$ and
$\left(\Phi^{+}_{d_{k}}\right)_{A^{\prime}B^{\prime}}$ is the
$d_{k}$-dimensional maximally entangled state between subsystems $A^{\prime}$
and $B^{\prime}$. That is, it is possible to show that, up to local
isometries, $\rho_{AB}$ is equivalent to a convex combination of maximally
entangled states of various dimensions, where the classical registers tell
Alice and Bob which state they share.

##  Appendix C The local value of $\mathcal{F}_{d}$

In this appendix, we proceed as follows: first, we obtain a universal lower
bound for the local value. This constitutes a proof for Theorem 3. Next, we
verify the existence of a $d$-dimensional overlap matrix that achieves this
lower bound only for the even $d$ cases. For odd $d$, we show that there is no
such a matrix.

### C. C.1 Preliminaries for Theorem 3

Before starting with the demonstration of Theorem 3, some short auxiliary
results are required. This section develops the solutions to two minimization
problems arising while in the demonstration.

####  C.1.1 The constrained probability simplex

In the proof of Theorem 3, we are required to minimize a concave function over
a polytope. In this subsection, let us characterize the extremal points of
this polytope. We start by representing the convex set by variables
$\\{t_{i}\\}_{i=1}^{n}$ such that $t_{i}\geq 0$, $\sum_{i}t_{i}=1$ and
$t_{i}\leq\tau$ for a fixed $\tau\in(0,\,1)$. The first two constraints simply
give us the probability simplex. The last one can be interpreted as
hyperplanes that cut off the vertices of this simplex. Therefore, we refer to
the resulting set as the constrained probability simplex.

Let the $n$-tuple $\mathbf{t}=(t_{1},\,t_{2},\,...,\,t_{n})$ represent a point
inside of the probability simplex. Its extremal points are given by the
deterministic distributions i.e., the permutations of

$\displaystyle\mathbf{t}=(1,\,0,\,0,\,...,\,0).$ (93)

Naturally, if we require that $t_{i}\leq\tau$, these vertices no longer belong
to the set. Then, let us show that the new extremal points of the constrained
probability simplex are given by permutations of

$\displaystyle\mathbf{t}=\bigg{(}\underbrace{\tau,\,\tau,\,...,\,\tau}_{\times\left\lfloor\frac{1}{\tau}\right\rfloor},\,1-\left\lfloor\frac{1}{\tau}\right\rfloor\times\tau,\,0,\,0,\,...,\,0\bigg{)}.$
(94)

To see that there are no other extremal points, one can wonder how many
coordinates are admitted to take a value other than zero or $\tau$. Let us
suppose that $t_{j}$ and $t_{j+1}$ are two coordinates satisfying this
condition, that is, $0<t_{j},\>t_{j+1}<\tau$. An arbitrary point
$\mathbf{t}_{\text{arb}}$ with components $t_{j}$ and $t_{j+1}$ must be, up to
permutations,

$\displaystyle\mathbf{t}_{\text{arb}}=\left(\tau,\,\tau,\,...,\,\tau,\,t_{j},\,t_{j+1},\,0,\,0,\,...,\,0\right).$
(95)

If $\mathbf{t}_{\text{arb}}$ is not extremal, it is possible to decompose it
into a convex sum. Changing this distribution for a quantity $\epsilon$, we
get

$\displaystyle\mathbf{t}_{+}=\left(\tau,\,\tau,\,...,\,\tau,\,t_{j}+\epsilon,\,t_{j+1}-\epsilon,\,0,\,0,\,...,\,0\right)$
(96)

or, in the inverse way,

$\displaystyle\mathbf{t}_{-}=\left(\tau,\,\tau,\,...,\,\tau,\,t_{j}-\epsilon,\,t_{j+1}+\epsilon,\,0,\,0,\,...,\,0\right).$
(97)

Note that, for a small enough $\epsilon$, $\mathbf{t}_{-}$ and
$\mathbf{t}_{+}$ are still valid points. However,
$\mathbf{t}_{\text{arb}}=\nicefrac{{1}}{{2}}\left(\mathbf{t}_{+}+\mathbf{t}_{-}\right)$,
so $\mathbf{t}_{\text{arb}}$ is not extremal. Thus, any extremal point must
have zero or one coordinate in the open interval $0<t_{i}<\tau$. The first
case appears only when $\nicefrac{{1}}{{\tau}}$ is an integer. Otherwise, we
find ourselves in the second case. In either case, the extremal points must
have the form of the vector $\mathbf{t}$ given in Eq. (94), up to
permutations.

Having shown that all the extremal points have the form given above, let us
argue that all those points are in fact extremal. To do so, it suffices to
show that no single point from $\mathbf{t}$ can be written as a convex
combination of the remaining points. More specifically, suppose that
$\mathbf{t}_{j}$, with $j=1,~{}...,~{}J$, are points of the form of
$\mathbf{t}$, in Eq. (94). Then, let us show that those points, in particular
$\mathbf{t}_{1}$, cannot be decomposed into a convex sum of $\mathbf{t}_{j}$,
for $j\neq 1$. Without loss of generality, assume that, for some strictly
positive weights $w_{j}$, where $\sum_{j}w_{j}=1$, $\mathbf{t}_{1}$ can be
written as a convex sum:

$\displaystyle\mathbf{t}_{1}=\sum_{j\in\mathcal{J}}w_{j}\mathbf{t}_{j},$ (98)

where $\mathcal{J}$ is the set of indexes $j$ for which $w_{j}>0$. Then,
suppose that the first component of $\mathbf{t}_{1}$ is
$[\mathbf{t}_{1}]_{1}=\tau$, so

$\displaystyle[\mathbf{t}_{1}]_{1}=\sum_{j\in\mathcal{J}}w_{j}[\mathbf{t}_{j}]_{1}=\tau.$
(99)

By hypothesis, $[\mathbf{t}_{j}]_{1}\leq\tau$, for all $j$, and

$\displaystyle[\mathbf{t}_{1}]_{1}=\sum_{j\in\mathcal{J}}w_{j}[\mathbf{t}_{j}]_{1}\leq\tau\sum_{j\in\mathcal{J}}w_{j}=\tau.$
(100)

In other words, Ineq. (100) is saturated, so $[\mathbf{t}_{j}]=\tau$, for all
$j\in\mathcal{J}$. We can repeat this same argument to all of the components
of $\mathbf{t}_{1}$ equal to $\tau$, leading to the same conclusion. In
addition, using that the components of $\mathbf{t}_{j}$ are non-negative, a
similar argument can be used to show that if $[\mathbf{t}_{1}]_{k}=0$, then
$[\mathbf{t}_{j}]_{k}=0$, for all $j\in\mathcal{J}$. The last component of
$\mathbf{t}_{1}$ equals $1-\left\lfloor\frac{1}{\tau}\right\rfloor\times\tau$,
which is fixed by normalization, and so are those of $\mathbf{t}_{j}$, for all
$j\in\mathcal{J}$. Therefore, $\mathbf{t}_{1}$ cannot be decomposed into a
convex sum of $t_{j}$, for $j\neq 1$. As $\mathbf{t}_{1}$ is an arbitrary
point among all of the $\mathbf{t}_{j}$ points, for all $j$, then all of the
points of the form of $\mathbf{t}$, in Eq. (94), are extremal.

####  C.1.2 Minimization of a specific function

In the proof of Theorem 3, we are required to find the minimum value of the
following function:

$\displaystyle
s(\tau):=2\left\lfloor\frac{1-\tau}{\tau}\right\rfloor\left(\sqrt{1-\tau}-1\right)+2\sqrt{\tau\left(1+\left\lfloor\frac{1-\tau}{\tau}\right\rfloor\right)}-\tau-2$
(101)

over $\tau\in\left(0,\,1\right]$. To do so, let us first show that $s(\tau)$
is continuous. By looking at the function in Eq. (101), it can be noted that
the possible discontinuous points are those at which $(1-\tau)/\tau$ is an
integer. So, let us evaluate the sided limits of $s(\tau)$ at points of the
form of $\tau=\nicefrac{{1}}{{n}}$, where $n$ is a positive integer:

$\displaystyle\lim_{\epsilon\rightarrow
0^{+}}\;s\left(\nicefrac{{1}}{{n}}-\epsilon\right)$
$\displaystyle=2(n-1)\left(\sqrt{1-\nicefrac{{1}}{{n}}}-1\right)-\nicefrac{{1}}{{n}}$
(102)

and

$\displaystyle\lim_{\epsilon\rightarrow
0^{+}}\;s\left(\nicefrac{{1}}{{n}}+\epsilon\right)$
$\displaystyle=2(n-2)\left(\sqrt{1-\nicefrac{{1}}{{n}}}-1\right)+2\left(\sqrt{1-\nicefrac{{1}}{{n}}}-1\right)-\nicefrac{{1}}{{n}}$
$\displaystyle=2(n-1)\left(\sqrt{1-\nicefrac{{1}}{{n}}}-1\right)-\nicefrac{{1}}{{n}}.$
(103)

Since the sided limits coincide, $s(\tau)$ is continuous w.r.t. $\tau$.

Now, note that, inside of the interval
$\tau\in\left[\frac{1}{n+1},\,\frac{1}{n}\right]$, $s(\tau)$ can be written as

$\displaystyle s(\tau)=2(n-1)(\sqrt{1-\tau}-1)+2\sqrt{n\tau}-\tau-2.$ (104)

If we treat $n$ as a fixed parameter, it is easy to see that $s(\tau)$ is a
concave function of $\tau$ (a linear combination of concave terms with non-
negative coefficients is concave). Moreover, for a single-variable concave
function defined over a closed and bounded interval, the points that minimize
this function are at the edges of the interval. In this case, we are looking
for points of the form $\tau=\nicefrac{{1}}{{n}}$. Therefore, to minimize
$s(\tau)$, we can discard the points in the interior and focus only at the
edges.

Then, let us define a function $g(n)$ whose domain is the set of positive
integers:

$\displaystyle
g(n):=s\left(\tau=\frac{1}{n}\right)=2(n-1)\left(\sqrt{1-\frac{1}{n}}-1\right)-\frac{1}{n}.$
(105)

For a moment, assume that $n$ is a continuous variable. This way, $g(n)$ can
be minimized just by evaluating its derivative:

$\displaystyle\frac{dg}{dn}=2\left(\sqrt{1-\frac{1}{n}}-1\right)+\frac{n-1}{n^{2}\sqrt{1-\nicefrac{{1}}{{n}}}}+\frac{1}{n^{2}}.$
(106)

Setting $\frac{dg}{dn}=0$ after some algebraic manipulation leads to:

$\displaystyle
n^{*2}-n^{*}-1=0\quad\Rightarrow\;\;n^{*}=\frac{1+\sqrt{5}}{2}\approx 1.62,$
(107)

which provides a single positive root for $n^{*}$. Moreover, the second
derivative, $\frac{d^{2}g}{dn^{2}}$, is positive at $n=n^{*}$ and so $n^{*}$
is indeed a minimum of $g(n)$. However, $g(n)$ is only defined for positive
integers, and we have to restrict the analysis to this set. Since $n^{*}$ is
the only critical point of $g(n)$ and $\frac{dg}{dn}$ is positive for
$n>n^{*}$ and negative for $n<n^{*}$, it suffices to check the closest
integers of $n^{*}$, i.e., $n=1$ and 2.

Then, returning to $s(\tau)$, as $s(\tau=1)=-1$ and
$s\left(\tau=\nicefrac{{1}}{{2}}\right)=\sqrt{2}-\nicefrac{{5}}{{2}}$,
$s(\tau)$ is minimized at $\tau=\nicefrac{{1}}{{2}}$.

### C. C.2 The analysis of the local value in Eq. (18)

In this section, let us show some properties that can be extracted from the
expression of the local value in Eq. (18). Firstly, suppose that $O_{ij}=1$,
for some $i,~{}j\in\\{1,~{}...,~{}d\\}$. Note that this assumption leads to
$O_{i,x_{2}}=\delta_{x_{2},j}$ and $O_{x_{1},j}=\delta_{x_{1},i}$, as the rows
and columns of $O$ are normalized. Next, Eq. (17) evaluated for the strategy
$s(i,\,j)$ of Bob leads to

$\displaystyle s(i,\,j)$ $\displaystyle=\sum_{x_{1}\neq
i}^{d}\left[\sqrt{1-O_{x_{1},j}^{2}}-\frac{1}{2}\left(1-O_{x_{1},j}^{2}\right)\right]+\sum_{x_{2}\neq
j}^{d}\left[\sqrt{1-O_{i,x_{2}}^{2}}-\frac{1}{2}\left(1-O_{i,x_{2}}^{2}\right)\right]=d-1.$
(108)

Note that this is the largest value that can be achieved by any strategy, as
the quantum value is also $d-1$. Therefore, in this case, this must be the
optimal strategy of Bob, and $\beta_{L}(O)=d-1$. This is the reason why the
assumption $O_{x_{1}x_{2}}<1$ is required for most of our analysis. If one
desires to trivialize the Bell inequalities presented in this work, it
suffices to construct $\mathcal{F}_{d}$ out of a matrix with a single overlap
equal to 1.

Now, let us show that $\beta_{L}(O)$ can be lower bounded by a clever choice
of the strategies of Bob. This constitutes a proof for Theorem 3. Without loss
of generality, let us start by identifying the largest element of $O$ as
$O_{11}$. We can always do so, as it is always possible to relabel the
outputs. Then, let us lower bound $\beta_{L}$ by restricting the set of
strategies from $u,\,v\in\\{1,~{}...,~{}d\\}$ to $u,\,v\in\\{1\\}$:

$\displaystyle\beta_{L}(O)=\underset{u,v}{\text{max}}\;\left[\,s(u,v)\,\right]\geq\underset{u,v\in\\{1\\}}{\text{max}}\;\left[\,s(u,v)\,\right]=s\left(1,\,1\right).$
(109)

In other words, we choose to bound $\beta_{L}$ by the strategy related to the
largest element of $O$, which we defined to be $O_{11}$. This particular
choice circumvents the maximization and reduces the problem of lower bounding
$\beta_{L}$ to the calculation of a single strategy. Recall that, from Eq.
(17), we are summing over the interval
$R_{\pm}=\\{x\in[d]^{2}\,|\,(\delta_{x_{1}u}-\delta_{x_{2}v})=\pm 1\\}$, which
means that the sum is performed over row $u$ and column $v$, but it excludes
the term $(u,~{}v)$, as $(\delta_{uu}-\delta_{vv})$ is, obviously, zero. Then,
by making this choice, we are lower bounding $\beta_{L}$ by the strategy that
excludes the largest term of $O$ in the sum.

The strategy $s(1,\,1)$, in turn, is given by

$\displaystyle s(1,\,1)$ $\displaystyle=\sum_{x_{1}\neq
1}^{d}\left[\sqrt{1-O_{x_{1},1}^{2}}-\frac{1}{2}\left(1-O_{x_{1},1}^{2}\right)\right]+\sum_{x_{2}\neq
1}^{d}\left[\sqrt{1-O_{1,x_{2}}^{2}}-\frac{1}{2}\left(1-O_{1,x_{2}}^{2}\right)\right].$
(110)

Defining $t_{x_{1}x_{2}}:=O_{x_{1}x_{2}}^{2}$ and using the normalization of
rows and columns of $O$, we get

$\displaystyle s(1,\,1)=\sum_{x_{1}\neq
1}^{d}\sqrt{1-t_{x_{1},1}}+\sum_{x_{2}\neq
1}^{d}\sqrt{1-t_{1,x_{2}}}-d-t_{11}+2.$ (111)

To continue, let us define an auxiliary function, $h$, such that

$\displaystyle h(t_{21},\,t_{31},\,...,\,t_{d,1})$
$\displaystyle:=\sum_{x_{1}=2}^{d}\sqrt{1-t_{x_{1},1}},$ (112)

i.e., it corresponds to the first term of Eq. (111). Note that $h$ is a Schur-
concave function w.r.t. the $d-1$ variables
$(t_{21},\,t_{31},\,...,\,t_{d,1})$. This is of particular importance because
any Schur-concave function, when minimised over a compact set, achieves its
minimum on some extremal point of this set. Thus, we can use this fact to
minimize both functions.

Then, let us express the $d-1$ variables of $h$ as a vector,
$\mathbf{t}:=(t_{21},\,t_{31},\,...,\,t_{d,1})$. For the elements of
$\mathbf{t}$, we have

$\displaystyle t_{x_{1},1}\geq 0,\quad\sum_{x_{1}\neq
1}t_{x_{1},1}=1-t_{11}\quad\text{and}\quad t_{x_{1},1}\leq t_{11}.$ (113)

The last condition comes from the fact that $O_{11}$ (and, by consequence,
$t_{11}$) is the largest element. The solution to the minimization of
$h(\mathbf{t})$ is presented in Section C.1 where the extremal points
$\mathbf{t}_{\text{ext}}$ of the set in Eqs. (113) are given by permutations
of

$\displaystyle\mathbf{t}_{\text{ext}}=\bigg{(}\underbrace{t_{11},\,...,\,t_{11}}_{\times\left\lfloor\frac{1-t_{11}}{t_{11}}\right\rfloor},1-t_{11}-\left\lfloor\frac{1-t_{11}}{t_{11}}\right\rfloor\times
t_{11},0,\,...,\,0\bigg{)}.$ (114)

An identical solution is obtained for the minimization of the second term of
Eq. (111), so $s(1,\,1)$ can be lower bounded by

$\displaystyle s(1,\,1)\geq
2\left\lfloor\frac{1-t_{11}}{t_{11}}\right\rfloor\left(\sqrt{1-t_{11}}-1\right)+2\sqrt{t_{11}\left(1+\left\lfloor\frac{1-t_{11}}{t_{11}}\right\rfloor\right)}-t_{11}+d-2.$
(115)

Now, we have a single-variable function, which can be easily minimized. This
is precisely the function analyzed in Section C.1 and the minimum is proven to
occur at $t_{11}=\nicefrac{{1}}{{2}}$. Thus,

$\displaystyle s(1,\,1)\geq d+\sqrt{2}-\frac{5}{2},$ (116)

which implies that $\beta_{L}(O)\geq d+\sqrt{2}-\nicefrac{{5}}{{2}}$, for any
$d$-dimensional $O$, with $d\geq 2$.

### C. C.3 Proof of Lemma 2

In this section, we investigate the overlap matrices that saturate the lower
bound on $\beta_{L}$. Let us start with the following lemma.

######  Lemma 3.

If a $d\times d$ matrix $O^{*}$ is such that
$\beta_{L}(O^{*})=d+\sqrt{2}-\nicefrac{{5}}{{2}}$, then a $2\times 2$ MUB
block can be separated from the remainder.

###### Proof.

Assume that $O^{*}$ is a $d\times d$ matrix such that
$\beta_{L}(O^{*})=d+\sqrt{2}-\nicefrac{{5}}{{2}}$. From the argument developed
in the last section, we start by assigning $\nicefrac{{1}}{{2}}$ to $t_{11}$,
or, in this case, assuming that $O^{*}_{11}=\nicefrac{{1}}{{\sqrt{2}}}$.
Because of the strict concavity of $h(\mathbf{t})$ in Eq. (112), Eq. (115) is
tight if and only if the vector that minimizes $h(\mathbf{t})$ is given by
permutations of

$\displaystyle\mathbf{t}_{\text{ext}}=\left(\frac{1}{2},\,0,\,...,\,0\right),$
(117)

that is, to saturate the lower bound, we take
$O^{*}_{12}=O^{*}_{21}=\nicefrac{{1}}{{\sqrt{2}}}$. Besides that, we must also
guarantee that the overlap matrix corresponds to a valid unitary. Recall that,
from the Eq. (1), the overlaps are taken as the absolute value of the inner
product between bases $\\{e_{x_{1}}\\}_{x_{1}=1}^{d}$ and
$\\{f_{x_{2}}\\}_{x_{2}=1}^{d}$. In other words, the elements of $O$ are the
absolute value of the elements of some unitary. It is easy to see that this
implies that $O^{*}_{22}=\nicefrac{{1}}{{\sqrt{2}}}$, so that the partial form
of $O^{*}$ is given by

$\displaystyle
O^{*}=\begin{bmatrix}\nicefrac{{1}}{{\sqrt{2}}}&\nicefrac{{1}}{{\sqrt{2}}}&0&...&0\\\
\nicefrac{{1}}{{\sqrt{2}}}&\nicefrac{{1}}{{\sqrt{2}}}&0&...&0\\\ 0&0&&&\\\
\vdots&\vdots&&O_{\text{rest}}&\\\ 0&0&&&\\\ \end{bmatrix},$ (118)

where $O_{\text{rest}}$ represents the uncharacterized elements of $O^{*}$. ∎

Now, to continue with the proof of Lemma 2, we have to obtain some
characterization of $\beta_{L}(O_{\text{rest}})$. In fact, we will show that

$\displaystyle\beta_{L}(O_{\text{rest}})=(d-2)+\sqrt{2}+\frac{5}{2},$ (119)

which coincides with the lower bound for dimension $d-2$.

Because $O_{\text{rest}}$ is a square matrix of dimension $d-2$, the Theorem 3
already implies that $\beta_{L}(O_{\text{rest}})$ is lower bounded by
$(d-2)+\sqrt{2}+\nicefrac{{5}}{{2}}$. On the other hand, the upper bound is a
consequence of Lemma 3. Because
$\beta_{L}(O^{*})=d+\sqrt{2}-\nicefrac{{5}}{{2}}$, all strategies of $O^{*}$
must be upper bounded by this same amount. In particular, note that for each
strategy labeled by outputs inside of the $O_{\text{rest}}$ block, in Eq.
(118), there are four zero terms, whose overall contribution is $+2$. Then,
when considering only $O_{\text{rest}}$, we have
$\beta_{L}(O_{\text{rest}})\leq(d-2)+\sqrt{2}+\nicefrac{{5}}{{2}}$.

Thus, for dimension $d-2$, the block $O_{\text{rest}}$ also fulfils the
assumptions of Lemma 3, so we can also extract a $2\times 2$ MUB block from
it. Naturally, the indefinite iteration of the above argument will lead us to
two cases: either $d$ is even and

$\displaystyle
O^{*}=\begin{bmatrix}\nicefrac{{1}}{{\sqrt{2}}}&\nicefrac{{1}}{{\sqrt{2}}}&...&0&0\\\
\nicefrac{{1}}{{\sqrt{2}}}&\nicefrac{{1}}{{\sqrt{2}}}&...&0&0\\\
\vdots&\vdots&\ddots&\vdots&\vdots\\\
0&0&...&\nicefrac{{1}}{{\sqrt{2}}}&\nicefrac{{1}}{{\sqrt{2}}}\\\
0&0&...&\nicefrac{{1}}{{\sqrt{2}}}&\nicefrac{{1}}{{\sqrt{2}}}\\\
\end{bmatrix}.$ (120)

or $d$ is odd and

$\displaystyle
O^{*}=\begin{bmatrix}\nicefrac{{1}}{{\sqrt{2}}}&\nicefrac{{1}}{{\sqrt{2}}}&0&...&0\\\
\nicefrac{{1}}{{\sqrt{2}}}&\nicefrac{{1}}{{\sqrt{2}}}&0&...&0\\\ 0&0&&&\\\
\vdots&\vdots&&\ddots\\\ 0&0&&&1\\\ \end{bmatrix},$ (121)

where the last block corresponds to the element $O^{*}_{d,d}=1$. However,
while Eq. (120) is a correct form of $O^{*}$ in the even case, for odd $d$,
this is not true. Firstly, because the matrix in Eq. (121) has one overlap
equal to one, which we discarded from our analysis. Secondly, we know, from
Appendix C.2, that this leads to $\beta_{L}(O^{*})=d-1$, which contradicts the
initial statement of Lemma 3, that
$\beta_{L}(O^{*})=d+\sqrt{2}-\nicefrac{{5}}{{2}}$. Thus, for the odd $d$ case,
there is no $O^{*}$ that saturates the lower bound in Theorem 3.

### C. C.4 Some considerations for the odd $d$ case

Finally, let us quickly explain why the lower bound derived in Theorem 3 is
not tight for odd $d$. Consider the entry-wise squared version of $O$, which
we refer to as $T$. If written so, $T$ assumes the form of a _unistochastic_
matrix i.e., if $U_{x_{1}x_{2}}$ are the elements of a unitary $U$, for
$x_{1},~{}x_{2}\in\\{1,\,...,\,d\\}$, then
$T_{x_{1}x_{2}}=|U_{x_{1}x_{2}}|^{2}$. A unistochastic matrix is also a
particular case of a _bistochastic_ matrix – a non-negative matrix whose
columns and rows add up to one. For $2\times 2$ arrays, it happens that the
bistochastic and the unistochastic sets of matrices coincide, but for larger
dimensions the unistochastic set is a proper subset of the bistochastic set.

It is clear that our original intention was to minimize $\beta_{L}(O)$ over
the set of overlap matrices. However, the proof of Theorem 3 relies only on
the fact that $T$ is bistochastic and, in fact, the derived lower bound
corresponds exactly to the lowest value achievable by a bistochastic matrix.
For even $d$, among the optimal bistochastic matrices, there exist some which
are also unistochastic and, hence, the resulting bound is tight.

For odd $d$, however, if we try to simultaneously saturate the bound and
enforce unistochasticity, we reach a contradiction, as shown in the previous
section. On the other hand, the lower bound can be saturated by a bistochastic
matrix, e.g.:

$\displaystyle
T^{*}=\begin{bmatrix}\nicefrac{{1}}{{2}}&0&0&...&0&\nicefrac{{1}}{{2}}\\\
\nicefrac{{1}}{{2}}&\nicefrac{{1}}{{2}}&0&...&0&0\\\
0&\nicefrac{{1}}{{2}}&\nicefrac{{1}}{{2}}&...&0&0\\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\
0&0&0&...&\nicefrac{{1}}{{2}}&\nicefrac{{1}}{{2}}\\\ \end{bmatrix},$ (122)

which is valid for all $d\geq 2$. However, none of the optimal bistochastic
matrices for odd $d$ happen to be unistochastic.

Now, let us focus on the case $d=3$. An aspect that makes the optimization
over the set of unistochastic matrices for $d=3$ difficult is the fact that
this set is not convex, but only star-convex. Also, the unistochastic and
bistochastic sets are both centered at $\frac{1}{3}J_{3}$, where $J_{3}$ is
the $3\times 3$ matrix of ones Bengtsson  _et al._ (2005). A proper notion of
center can be acquired if one considers a uniformly weighted convex
combination of the extremal points of the permutation matrices. The
permutation matrices are the only extremal points of the bistochastic set, and
they are also extremal for the unistochastic set.

We have numerically implemented a function that calculates the local value for
a given overlap matrix. By performing a local search over a large number of
random starting points we have reached the conjecture that the smallest value
of $\beta_{L}$ for $d=3$ is achieved for

$\displaystyle
O_{\text{conj}}=\begin{bmatrix}\nicefrac{{1}}{{3}}&\nicefrac{{2}}{{3}}&\nicefrac{{2}}{{3}}\\\
\nicefrac{{2}}{{3}}&\nicefrac{{1}}{{3}}&\nicefrac{{2}}{{3}}\\\
\nicefrac{{2}}{{3}}&\nicefrac{{2}}{{3}}&\nicefrac{{1}}{{3}}\\\ \end{bmatrix}.$
(123)

To see why this conjecture is reasonable, consider the entry-wise squared
version of $O_{\text{conj}}$, which we refer to as $T_{\text{conj}}$. An
analytic condition derived in Ref. Fedullo (1992) allows us to check that
$T_{\text{conj}}$ is not only unistochastic, but also lies at the boundary of
the unistochastic set. Furthermore, consider a permutation of the three-
dimensional matrix in Eq. (122),

$\displaystyle
T^{*}_{3}=\begin{bmatrix}0&\nicefrac{{1}}{{2}}&\nicefrac{{1}}{{2}}\\\
\nicefrac{{1}}{{2}}&0&\nicefrac{{1}}{{2}}\\\
\nicefrac{{1}}{{2}}&\nicefrac{{1}}{{2}}&0\\\ \end{bmatrix}.$ (124)

Then,

$\displaystyle
T_{\text{conj}}=\frac{1}{3}\left(\frac{1}{3}J_{3}\right)+\frac{2}{3}T^{*}_{3}.$
(125)

That is, if one considers the line segment connecting the center of the
unistochastic set and the optimal bistochastic matrix, $T_{\text{conj}}$ can
be found at the intersection of this segment with the boundary of the
unistochastic set.

Lastly, let us show that $O_{\text{conj}}$ provides a smaller local value than
MUBs. By calculating $\beta_{L}(O_{\text{conj}})$, we get

$\displaystyle\beta_{L}(O_{\text{conj}})=\frac{1}{9}\left[6\left(\sqrt{8}+\sqrt{5}\right)-13\right]\approx
1.9319.$ (126)

For $d$-dimensional MUBs, we obtain

$\displaystyle\beta_{L}\left(\frac{1}{\sqrt{d}}J_{d}\right)=2(d-1)\sqrt{\frac{d-1}{d}}-\frac{(d-1)^{2}}{d}.$
(127)

If evaluated for $d=3$, then
$\beta_{L}\left(\nicefrac{{J_{3}}}{{\sqrt{3}}}\right)=1.9327$, which is
slightly bigger than $\beta_{L}(O_{\text{conj}})$. In fact, $O_{\text{conj}}$
allows us to construct counterexamples for all odd dimensions. For odd $d\geq
3$, consider the following matrix:

$\displaystyle
O_{d}^{\oplus}=\left(\bigoplus_{i=1}^{\left\lfloor\nicefrac{{d}}{{2}}\right\rfloor-1}\frac{1}{\sqrt{2}}J_{2}\right)\oplus
O_{\text{conj}}.$ (128)

The local value obtained for $O_{d}^{\oplus}$ is given by

$\displaystyle\beta_{L}(O_{d}^{\oplus})=d-3+\frac{1}{9}\left[6\left(\sqrt{8}+\sqrt{5}\right)-13\right]\approx
d-1.0681.$ (129)

If one takes the derivative of
$\beta_{L}\left(\nicefrac{{J_{d}}}{{\sqrt{d}}}\right)-\beta_{L}(O_{d}^{\oplus})$,
by a simple analytic argument it is possible to conclude that this derivative
is positive for all odd $d\geq 3$. Because
$\beta_{L}\left(\nicefrac{{J_{d}}}{{\sqrt{d}}}\right)-\beta_{L}(O_{d}^{\oplus})$
is positive for $d=3$, then it must also be positive for all odd $d\geq 3$.
Therefore, this shows that for all odd $d\geq 3$, the realization of
$\mathcal{F}_{d}$ that is most robust to noise does not correspond to MUBs in
dimension $d$.