# Certification of qubits in the prepare-and-measure scenario with large input
alphabet and connections with the Grothendieck constant

Péter Diviánszky<EMAIL_ADDRESS>MTA Atomki Lendület Quantum Correlations
Research Group, Institute for Nuclear Research, P.O. Box 51, H-4001 Debrecen,
Hungary  István Márton<EMAIL_ADDRESS>MTA Atomki Lendület Quantum
Correlations Research Group, Institute for Nuclear Research, P.O. Box 51,
H-4001 Debrecen, Hungary  Erika Bene<EMAIL_ADDRESS>MTA Atomki Lendület
Quantum Correlations Research Group, Institute for Nuclear Research, P.O. Box
51, H-4001 Debrecen, Hungary  Tamás Vértesi<EMAIL_ADDRESS>MTA Atomki
Lendület Quantum Correlations Research Group, Institute for Nuclear Research,
P.O. Box 51, H-4001 Debrecen, Hungary

###### Abstract

We address the problem of testing the quantumness of two-dimensional systems
in the prepare-and-measure (PM) scenario, using a large number of preparations
and a large number of measurement settings, with binary outcome measurements.
In this scenario, we introduce constants, which we relate to the Grothendieck
constant of order 3. We associate them with the white noise resistance of the
prepared qubits and to the critical detection efficiency of the measurements
performed. Large-scale numerical tools are used to bound the constants. This
allows us to obtain new bounds on the minimum detection efficiency that a
setup with 70 preparations and 70 measurement settings can tolerate.

##  I Introduction

Quantum theory reveals interesting and counter-intuitive phenomena in even the
simplest physical systems. Paradigmatic examples are Bell nonlocality [1, 2]
and Einstein-Podolsky-Rosen (EPR) steering [3, 4, 5, 6]. These nonlocal
phenomena appear as strong correlations between the outcomes of spatially
separated measurements performed by independent observers. These correlations
enable us to distinguish the classical and quantum origins of the experiments.
Recently, a similar split between classical and quantum features was found in
a setup closely related to quantum communication tasks, the so-called prepare-
and-measure (PM) scenario [7]. This scenario can be viewed as a communication
game between two parties, Alice (the sender) and Bob (the receiver), where the
dimension of the classical (versus quantum) system communicated from Alice to
Bob is bounded from above.

The PM game is described as follows (see panel (a) of Fig. 1). Upon receiving
an input $x=(1,\ldots,n)$, a preparation device (controlled by Alice) emits a
physical system in a quantum state $\rho_{x}$. We assume
$\rho_{x}\in\mathcal{L}(\mathbb{C}^{d})$ for a given $d\geq 2$. In the
following, however, we will focus explicitly on $d=2$, that is, we assume that
two-dimensional quantum systems (qubits) or classical systems (bits) are
transmitted from Alice to Bob. The state $\rho_{x}$ is passed to a measurement
device which, upon receiving an input $y=(1,\ldots,m)$ performs a measurement
and obtains an outcome $b=(1,\ldots,o)$. In this paper we will focus on the
smallest, nontrivial case of $o=2$, i.e., measurements with two outcomes, in
which case we denote the outcomes by $b=\pm 1$.

Our goal in this scenario is to compare the power of qubits with classical
bits. This scenario has been discussed in some extent for a small number of
preparations $n$ and measurements $m$ (see e.g. Refs. [7, 8, 9, 10, 11, 12].
However, in this paper we would like to turn our attention to the case of
large $n$ and $m$ (i.e. in the range of 70). We will see that the main
bottleneck of the study is the computation of the relevant quantities
associated with the classical bit case for which we develop large scale
numerical tools in this paper. We first concentrate on the qubit case, and
then we will elaborate on the classical bit case.

Figure 1: The prepare-and-measure setup for (a) qubit communication and (b) a
classical model using one bit of communication. In (a) upon receiving the
input settings $\vec{a}$ and $\vec{b}$, Alice sends to Bob a qubit in the
quantum state $\rho_{\vec{a}}$. Then Bob performs a projective measurement
$M_{b|\vec{b}}=(\leavevmode\hbox{\small
1\normalsize\kern-3.30002pt1}+b\vec{b}\cdot\sigma)/2$, where the two outcomes
are labelled by $b=\pm 1$. As a result, the expectation value of Bob’s $\pm 1$
outcome becomes $E(\vec{a},\vec{b})=\vec{a}\cdot\vec{b}$ (see equation (5)).
In (b) the classical one bit Gisin-Gisin protocol [13] is as follows. The
shared randomness $\vec{\lambda}$ is distributed between the two parties,
where the unit vector $\vec{\lambda}\in S^{2}$ is chosen uniformly at random
from the sphere. After obtaining the settings $\vec{a}$ and $\vec{b}$, Alice
communicates to Bob the classical binary message
$c=\text{sgn}(c\vec{a}\cdot\vec{\lambda})$. Then Bob outputs
$b=\text{sgn}(c\vec{b}\cdot\vec{\lambda})$ with probability
$|\vec{b}\cdot\vec{\lambda}|$, and $b=0$ with probability
$1-|\vec{b}\cdot\vec{\lambda}|$. Finally, Bob performs a coarse graining on
his outputs by grouping $b=0$ with $b=1$ and identifying both of them with
outcome $b=1$. As a result, as it is shown in Sec. III.4, the expectation
value of Bob’s $b=\pm 1$ outcome becomes
$E(\vec{a},\vec{b})=(\vec{a}\cdot\vec{b}+1)/2$.

Qubit case.—In the qubit binary outcome ($o=2$) case, the measurement is
described by two positive operators $\\{\Pi_{b|y}\\}$, $b=\pm 1$ acting on
$\mathbb{C}^{2}$ which sum to the identity
$\Pi_{b=+1|y}+\Pi_{b=-1|y}=\leavevmode\hbox{\small
1\normalsize\kern-3.30002pt1}$ for each $y$, where 11 denotes the $2\times 2$
identity matrix. The statistics of the experiment are then given by the
formula

$P(b|x,y)=\operatorname{Tr}(\rho_{x}\Pi_{b|y}).$ (1)

It is important to note that both the preparations and the measurements are
unknown to the observer, up to the fact that the dimension of the transmitted
system is two. Since we have binary outcomes $b=\\{+1,-1\\}$ it becomes
convenient to use expectation values

$E_{x,y}=P(b=+1|x,y)-P(b=-1|x,y).$ (2)

Note that $E_{x,y}$ can take up the values in $\left[-1,+1\right]$ for all
$x,y$. However, if the Hilbert space dimension of the communicated particle is
bounded, then in general not all expectation values $E_{x,y}$ in
$\left[-1,+1\right]$ become possible. The simplest scenario that shows this
effect appears already for $n=3$, $m=2$ and $o=2$ (see [7] for an example).

With respect to the measurement operators $M_{b|y}$, one case, namely the set
of projective rank-1 measurements, is of particular interest to us. In this
case, we have

$\Pi_{b|y}=\frac{\leavevmode\hbox{\small
1\normalsize\kern-3.30002pt1}_{2}+b\vec{b}_{y}\cdot\vec{\sigma}}{2},$ (3)

where $\vec{b}_{y}\in S^{2}$, $b=\pm 1$ and
$\vec{\sigma}=(\sigma_{x},\sigma_{y},\sigma_{z})$ is the vector of Hermitian
$2\times 2$ Pauli matrices. On the other hand, let us set

$\rho_{x}=\frac{\leavevmode\hbox{\small
1\normalsize\kern-3.30002pt1}+\vec{a}_{x}\cdot\vec{\sigma}}{2},$ (4)

where $\vec{a}_{x}\in S^{2}$. This density matrix corresponds to a pure state
with Bloch vector $\vec{a}_{x}$. Note that in this case, the above equations
give us

$E_{x,y}=\vec{a}_{x}\cdot\vec{b}_{y},$ (5)

where $\vec{a}_{x},\vec{b}_{y}\in S^{2}$.

Limits on the set of possible distributions in dimension two can be captured
by the following expression

$W=\sum_{x=1}^{n}\sum_{y=1}^{m}M_{x,y}E_{x,y},$ (6)

where $M_{x,y}$ are coefficients of a real witness matrix $M$ of dimension
$n\times m$. Let us then define the quantity

$Q(M)=\max\sum_{x=1}^{n}\sum_{y=1}^{m}M_{x,y}E_{x,y},$ (7)

where $E_{x,y}$ is of the form (2), and where we maximize the expression over
Bob’s measurements $\\{M_{b|y}\\}$ and the qubit state $\rho_{x}$ in Eq. (1).
Thus, $Q(M)$ is the value that is achievable with the most general two-
dimensional quantum resources in our PM setup. We further define the quantity

$q(M)=\max\sum_{x=1}^{n}\sum_{y=1}^{m}M_{x,y}E_{x,y},$ (8)

where $E_{x,y}=\vec{a}_{x}\cdot\vec{b}_{y}$ and we maximize over the unit
vectors $\vec{a}_{x}$ and $\vec{b}_{y}$ in the three-dimensional Euclidean
space. It turns out that $Q(M)$ can be obtained with pure qubit states and
projective measurements [10]. However, the optimal projective measurements are
in general not of rank-1, they can be of rank-2 as well. Indeed, there are
example matrices $M$ (even in the simple $n=m=3$, $o=2$ case) for which
$Q(M)>q(M)$. Note that $q(M)$ corresponds to projective qubit measurements of
rank 1, in which case $E_{x,y}=\vec{a}_{x}\cdot\vec{b}_{y}$ (see equation
(5)). Yet, as we will see, the set $\\{E_{x,y}\\}_{x,y}$ obtained by rank-1
projective measurements is a significant subset of the set
$\\{E_{x,y}\\}_{x,y}$ corresponding to the most general qubit measurements.
The tools for computing the value $Q(M)$ can be found in Refs. [14, 15].

Importantly, the value of $Q(M)$ can serve as a dimension witness in the
prepare-and-measure scenario [7]. Indeed, if $W>Q(M)$ for some $M$ (where the
witness $W$ is defined by equation (6)), this implies that the set of states
$\\{\rho_{x}\\}_{x=1}^{n}$ transmitted to Bob must have contained at least one
state $\rho_{x=x^{\prime}}$ of at least three dimensions (that is qutrit).

Classical bit versus qubit case.—It turns out that the witness $W$ can also
serve as a quantumness witness. To this end, let us discuss the classical bit
case. That is, we want to bound the expression (6) if Alice can only prepare
classical two-dimensional systems (i.e. bits). Let us denote the bound on (6)
by $L_{2}(M)$, which corresponds to this situation. If $W>L_{2}(M)$, this
certifies that some of the measurements performed by Bob are true
(incompatible) quantum measurements acting on true qubit states [7, 16].
Mathematically, the classical bit case is equivalent to the qubit case
discussed above, with the restriction that all qubits are sent in the same
basis, and all measurements of Bob are carried out in the very same basis.
That is, if we want to maximize (6) for correlations $E_{x,y}$ arising from
classical two-dimensional systems, the maximum can be attained with pure
states

$\rho_{x}=\frac{\leavevmode\hbox{\small
1\normalsize\kern-3.30002pt1}_{2}+a_{x}\cdot\sigma_{z}}{2},$ (9)

where $a_{x}=\pm 1$, and observables $B_{y}=\Pi_{0|y}-\Pi_{1|y}$ which have
the form

$B_{y}=b_{y}^{+}|0\rangle\langle 0|+b_{y}^{-}|1\rangle\langle 1|,$ (10)

where $\sigma_{z}$ is the standard Pauli matrix

$\displaystyle\sigma_{z}=\begin{pmatrix}[r]1&0\\\ 0&-1\end{pmatrix}$

and both $b_{y}^{+}$, $b_{y}^{-}$ are $\pm 1$ variables. Inserting these
values into (2) we obtain

$E_{x,y}=\frac{(1+a_{x})b_{y}^{+}+(1-a_{x})b_{y}^{-}}{2}.$ (11)

Since we have binary variables $a_{x}=\pm 1$, they translate to
$E_{x,y}=b_{y}^{+}$ if $a_{x}=1$ and $E_{x,y}=b_{y}^{-}$ if $a_{x}=-1$. Then
the classical one-bit bound $L_{2}(M)$ is given by

$L_{2}(M)=\max\sum_{x=1}^{n}\sum_{y=1}^{m}M_{x,y}E_{x,y},$ (12)

where $E_{x,y}$ is defined by (11) and we maximize over all binary variables
$a_{x},b^{+}_{y},b^{-}_{y}\in\\{-1,+1\\}$. In words, the expression (11)
corresponds to the following deterministic protocol. Alice, depending on $x$,
prepares a bit $a_{x}=\pm 1$, which she sends to Bob, who outputs $b=\pm 1$
depending on the value of $a_{x}$ and the measurement setting $y$. That is,
Bob’s output is a deterministic function $b=f(a_{x},y)$, where the output
assumes $b=\pm 1$. We can write

$\displaystyle L_{2}(M)$
$\displaystyle=\max\left(\sum_{x:a_{x}=+1}\sum_{y=1}^{m}M_{xy}b^{+}_{y}+\sum_{x:a_{x}=-1}\sum_{y=1}^{m}M_{xy}b^{-}_{y}\right),$
(13)

where the maximum is taken over all binary $a_{x}$, $b_{y}^{+}$ and
$b_{y}^{-}$ variables $\pm 1$. We can eliminate the variables $b^{+}_{y}$ and
$b^{-}_{y}$ from the above expression and get the following formula for
$L_{2}(M)$:

$L_{2}(M)=\max_{a_{x}=\pm
1}\left(\left\|\sum_{x:a_{x}=+1}M_{x}\right\|_{1}+\left\|\sum_{x:a_{x}=-1}M_{x}\right\|_{1}\right),$
(14)

which only consists of maximization over the binary variables $a_{x}=\pm 1$.
In the above formula, $M_{x}$ denotes the $x$th row of the real $n\times m$
matrix $M$, where $\|v\|_{1}$ denotes the Manhattan norm of the real vector
$v$, i.e., $\|v\|_{1}=\sum_{x}|v_{x}|$. We prove several interesting
properties of $L_{2}(M)$ in the Methods section III.1. In particular, $L_{2}$
is proven to be a matrix norm. Let us recall that $L_{2}(M)$ is a key quantity
in our study, as it enables witnessing both quantumness of preparations and
quantumness of measurements. Indeed, $W>L_{2}(M)$, where $W$ is defined in
equation (6), certifies incompatible quantum measurements acting on true qubit
states. That is, not all the performed measurements and not all prepared
states originate from the same basis [7]. In section III.1 we do not restrict
our study to the properties of the $L_{2}$ norm but generalize $L_{2}(M)$ to
$L_{k}(M)$ for any $k>2$ and prove that $L_{k}$ is a norm as well, moreover
$L_{k}(M)$ is a monotonic increasing function of $k$. Furthermore, in section
III.2 we give tips for an efficient implementation of the branch-and-bound
algorithm [17] for computing the $L_{k}(M)$ bound for $k=2$ and for $k>2$ as
well.

Introducing the constants $K_{\text{PM}}$ and $K_{\text{D}}$.—We define two
quantities $K_{\text{PM}}$ and $K_{\text{D}}$ which are related to $L_{2}(M)$
and $q(M)$, and are defined as follows. Let us first introduce
$K_{\text{PM}}$, in which case we ask for the maximum ratio between $q(M)$ and
$L_{2}(M)$. That is, we are interested in the value

$K_{\text{PM}}=\max_{M}\frac{q(M)}{L_{2}(M)},$ (15)

where the maximization is taken over all possible real $n\times m$ matrices
$M$, where $q(M)$ is defined by (8) and $L_{2}(M)$ is defined by (12).

Let us now recall the Grothendieck constant of order 3 [18, 19, 20, 21, 22],
which is given by

$K_{G}(3)=\max_{M}\frac{q(M)}{L(M)},$ (16)

where the maximization is taken over real matrices $M$ of arbitrary dimensions
$n\times m$, $q(M)$ is defined by (8) and $L(M)$ is defined as follows

$L(M)=\max\sum_{x=1}^{n}\sum_{y=1}^{m}M_{x,y}a_{x}b_{y},$ (17)

where the maximum is taken over all $a_{x},b_{y}\in\\{-1,+1\\}$. According to
the literature, the value of $K_{G}(3)$ in (16) is bounded by

$1.4359870\leq K_{G}(3)\leq 1.4643558,$ (18)

where the lower bound is due to Ref. [23] and the upper bound is due to Ref.
[24]. Note that the upper bound is an improved version of the bound in Ref.
[25]. We prove that $K_{\text{PM}}=K_{G}(3)$, which will be given in the
Results section II.1.

We are interested in $K_{\text{D}}$ as well, a quantity similar to
$K_{\text{PM}}$. We define this quantity as follows

$K_{\text{D}}=\max_{M}\frac{q(M)-S(M)}{L_{2}(M)-S(M)},$ (19)

where

$S(M)=\sum_{x=1}^{n}\sum_{y=1}^{m}M_{x,y}.$ (20)

Note the relation

$\frac{q(M)-S(M)}{L_{2}(M)-S(M)}\geq\frac{q(M)}{L_{2}(M)},$ (21)

whenever $L_{2}(M)>S(M)$ (also note that $q(M)\geq L_{2}(M)$), therefore we
have $K_{\text{D}}\geq K_{\text{PM}}=K_{G}(3)$. From this we immediately
obtain the lower bound $K_{\text{D}}\geq 1.4359$. In this paper, we give
efficient large-scale numerical methods to obtain even better lower bounds on
the above quantity. Namely, we prove the lower bound $K_{\text{D}}\geq
1.5682$. We also prove an upper bound of 2 on this quantity, so putting all
together we have the following interval

$1.5682\leq K_{\text{D}}\leq 2$ (22)

for the constant $K_{\text{D}}$. It is an open problem to close or at least
reduce the gap between the lower and upper limits.

We next present the Results section, which contains our main findings in three
subsections.

##  II Results

###  II.1 Proof of the relation $K_{\text{PM}}=K_{G}(3)$

To prove our claim, we relate $L(M^{\prime})$ to $L_{2}(M^{\prime})$, where
$M^{\prime}$ is given by the following matrix (see also (74))

where

M$isareal$n×m$matrix.Denoteby$M_x$the$x$-throwofthematrix$M$.Notethataccordingtotheabovedefinition$M’$hassize$2n×m$and$M’$hasrowssuchthat$M’_x=M_x$and$M’_x+n=-M_x$forall$x=1,…,n$.Thenthefollowinglemmaholds.\par\begin{lemma}$L_{2}(M^{\prime})=L(M^{\prime})=2L(M)$foranymatrix$M^{\prime}$oftheform(\ref{Mvv}),where$L_{2}$isthe$L_{2}$normgivenbythedefinition(\ref{L2M})and$L$isthelocalboundgivenby(\ref{LMdef},\ref{LDef}).\end{lemma}TheproofofthislemmaisgiveninMethodssection~{}\ref{sec:LL2Mp}.Thenweneedtoprovethefollowinglemma.\par\begin{lemma}$K_{\text{P}M}\leq
K_{G}(3)$.\end{lemma}Foranarbitrarymatrix$M$,wehave$L_2(M)≥L(M)$.ThishasbeenprovedinMethodssection~{}\ref{sec:L2proofs}.Thenthelemmafollowsfromthedefinitions~{}(\ref{KG3})and(\ref{KPM}).Ournextlemmareads\begin{lemma}$K_{\text{P}M}\geq
K_{G}(3)$.\end{lemma}\par{\noindent\it
Proof.}Toprovethis,itsufficestoshowthatforanarbitraryrealmatrix$M$,thereexiststhematrix$M’$definedby(\ref{Mvv})suchthat$q(M’)=2q(M)$and$L_2(M’)=2L(M)$.Thefirstrelationfollowsfromthespecialstructureof$M’$.ThesecondrelationhasbeenshowninLemma~{}\ref{L2L}.Therefore,$K_PM$cannotbelessthan$K_G(3)$,whichprovesourclaim.$$\hfill\blacksquare$$\par\begin{corollary}AsacorollaryoftheaboveLemmas~{}\ref{lemma_eq1}and~{}\ref{lemma_eq2}weobtain$K_{\text{PM}}=K_{G}(3)$.\end{corollary}\par
Hencewehavethesamebounds$1.4359≤K_PM≤1.4644$asfor$K_G(3)$(see~{}(\ref{KG3bounds})).Fromthecorollaryabove,wehaveamatrix$M’$ofsize$48×24$with$q(M’)/L_2(M’)>2$.Indeed,theconstructionisbasedonamatrix$M$ofsize$24×24$,whichprovides$q(M)/L(M)>2$~{}\cite[cite]{[\@@bibref{Number}{Gilb66}{}{}]}.Tothebestofourknowledge,thisisthesmallest$M$matrixthathastheproperty$q(M)/L(M)>2$.Thenthe$48$-by-$24$matrix$M’$followsfrom~{}(\ref{Mvv}).Ontheotherhand,$q(M)/L(M)=2$isalreadyattainedwitha$2×2$matrix$M$intheCHSH-
form~{}\cite[cite]{[\@@bibref{Number}{chsh69}{}{}]}:\begin{aligned}
M=\begin{pmatrix}[r]1&1\\\
1&-1\end{pmatrix}.\end{aligned}Itremainsanopenquestiontoshowthat$K_PM>2$withamatrixsizesmallerthan$48×24$,whichmightuseadifferentconstructionthantheoneabove.\par$

###  II.2 Proof of the bounds $1.5682\leq K_{\text{D}}\leq 2$

Upper bound.—We first prove the upper bound. Translating the Gisin-Gisin model
[13] from the Bell nonlocality [1, 2] to the PM scenario [7], we find that the
following statistics can be obtained in the PM scenario with 1 bit of
classical communication:

$E(\vec{a},\vec{b})=\frac{\vec{a}\cdot\vec{b}+1}{2},$ (23)

where $\vec{a}\in S^{2}$ denotes the preparation vector and $\vec{b}\in S^{2}$
denotes the measurement Bloch vector. We give the proof of this formula in the
Methods section III.4 and we show panel (b) in figure 1 for the description of
the classical one-bit model. On one hand, due to the above Gisin-Gisin one-bit
model, we have for an arbitrary $n\times m$ matrix $M$:

$\max\sum_{x=1}^{n}\sum_{y=1}^{m}M_{x,y}E_{x,y}\leq L_{2}(M),$ (24)

where $E_{x,y}$ has the form (23) and we maximized over the unit vectors
$\vec{a}_{x}$ and $\vec{b}_{y}$ in the three-dimensional Euclidean space. On
the other hand, substituting $E_{x,y}:=E(\vec{a}_{x},\vec{b}_{y})$ in the
formula (23) into (24) we find

$\displaystyle\max\sum_{x=1}^{n}\sum_{y=1}^{m}M_{x,y}E_{x,y}$
$\displaystyle=\frac{\max\sum_{xy}M_{xy}\left(\vec{a}_{x}\cdot\vec{b}_{y}+1\right)}{2}$
$\displaystyle=\frac{q(M)+S(M)}{2},$ (25)

where maximization is over the unit vectors $\vec{a}_{x}$ and $\vec{b}_{y}$ in
the three-dimensional Euclidean space, and we also used the definition of
$q(M)$ in (8) and the definition of $S(M)$ in (20). Comparing the right-hand
side of (24) with (25), we have

$\frac{q(M)-S(M)}{L_{2}(M)-S(M)}\leq 2,$ (26)

where the left-hand side of (19) is just $K_{\text{D}}$, which proves the
upper bound $K_{\text{D}}\leq 2$. $\hfill\blacksquare$

Lower bound.—In the following, we prove the lower bound using large-scale
numerical tools. Note, however, that the resulting bound is rigorous and in
particular the final result is due to exact computations. The steps are as
follows.

Given a fixed setup with Alice’s Bloch vectors $\vec{a}_{x}$, $x=(1,\ldots,n)$
and Bob’s Bloch vectors $\vec{b}_{y}$, $y=(1,\ldots,m)$ the method is the
following. We define the $(n\times m)$-dimensional one-parameter family of
matrices $E_{xy}(\eta)$ with entries

$E_{x,y}(\eta)=\eta E_{x,y}+(1-\eta),$ (27)

where $E_{x,y}=\vec{a}_{x}\cdot\vec{b}_{y}$. We wish to show that for some
$\eta\in\left[0,1\right]$, the distribution (27) in the PM scenario cannot be
simulated with one bit of classical communication. In fact, due to the
expectation value (23) of the Gisin-Gisin model, it is enough to consider the
interval $\eta\in\left[1/2,1\right]$. To show quantumness, we therefore need
to find a matrix $M$ of certain size $n\times m$ and a given
$\eta\in\left[1/2,1\right]$ such that

$\sum_{x=1}^{n}\sum_{y=1}^{m}M_{xy}E_{xy}(\eta)>L_{2}(M)$ (28)

for $E_{xy}(\eta)$ defined by (27), and $L_{2}(M)$ is defined by (12). The
above problem, i.e., finding a suitable $M$ with the smallest possible $\eta$
in (28), can be solved by a modified version [26] of the original Gilbert
algorithm [28], a popular collision detection method used, for example, in the
video game industry.

The algorithm is iterative, and the procedure adapted to our problem is given
in Sec. III.5. Indeed, using the algorithm of Gilbert, we find the value

$\eta^{*}=0.6377$ (29)

and a corresponding $70\times 70$ matrix $M$ and $E_{xy}(\eta^{*})$ in the
form (27) which satisfies inequality (28). We will give more technical details
of the input parameters and the implementation of the algorithm in Section
III.6. Then, rearranging (28) and making use of equation (27), we find the
bound

$\frac{\sum_{xy}M_{xy}E_{xy}-S(M)}{L_{2}(M)-S(M)}>\frac{1}{\eta^{*}},$ (30)

where due to the definitions (8,19) the lower bound

$K_{\text{D}}>(1/\eta^{*})\simeq 1.5682$ (31)

on $K_{\text{D}}$ follows.

###  II.3 Physical meaning of the constants $K_{\text{PM}}$ and $K_{\text{D}}$

The role of $K_{\text{PM}}$ in the PM scenario.—The value of $K_{\text{PM}}$
is interesting from a physical point of view as well, since it is related to
the critical noise resistance of the experimental setup if the transmitted
$\rho_{x}$ goes through a noisy, fully depolarizing channel. That is,
$1-p_{\text{crit}}=1-(1/K_{\text{PM}})$ gives the amount $(1-p_{\text{crit}})$
of critical white noise $\leavevmode\hbox{\small
1\normalsize\kern-3.30002pt1}/2$ that the PM experiment with rank-1 projective
qubit measurements can maximally tolerate while still being able to detect
quantumness. Namely, for a fully depolarizing channel with visibility
parameter $p$ the qubits $\rho_{x}$ emitted by Alice’s turn into
$p\rho_{x}+(1-p)\leavevmode\hbox{\small 1\normalsize\kern-3.30002pt1}/2$, and
the expectation value (5) becomes

$E_{xy}=p\vec{a}_{x}\cdot\vec{b}_{y},$ (32)

where $\\{\vec{a}_{x}\\}_{x}$ are the Bloch vectors of Alice’s qubits, whereas
$\\{\vec{b}_{y}\\}_{y}$ are the Bloch vectors of Bob’s measurements. To
witness quantumness, there must exist expectation values $E_{xy}$ in (32) and
a matrix $M$ of arbitrary size such that

$\sum_{xy}M_{xy}E_{xy}>L_{2}(M).$ (33)

Inserting (32) into (33) and making use of (8), we obtain

$p_{\text{crit}}=\min_{M}\frac{L_{2}(M)}{q(M)}=\frac{1}{K_{\text{PM}}}=\frac{1}{K_{G}(3)}.$
(34)

for the critical noise tolerance. In fact, the value of $K_{G}(3)$ appears in
the studies [20, 29, 24] of the Bell nonlocality of two-qubit Werner states
[30]. Note that a recent approach in Ref. [31], based on the simulability of
Werner states with local models, yields the same relation (34) between
$p_{\text{crit}}$ and $1/K_{G}(3)$ .

From the upper and lower bounds on $K_{\text{PM}}$, the following bounds on
the amount $(1-p_{\text{crit}})$ of critical white noise follow:

$0.3036\leq(1-p_{\text{crit}})\leq 0.3172.$ (35)

The role of $K_{\text{D}}$ in the PM scenario.—In section II.2 we proved the
lower bound of $K_{\text{D}}\geq 1.5682$. Below we prove that this bound is
related to the finite detection efficiency threshold of Bob’s measurements. To
this end, we assume that Bob’s detectors are not perfect and only fire with
probability $\eta$. Assume that when the measurement $y$ fails to detect, Bob
outputs $b_{y}=1$ (due to possible relabelings there is no loss of
generality). Assume further that the probability of detection $\eta$ is the
same for all $y$. This is the problem of symmetric detection efficiency. A
review of this problem in the Bell scenario can be found in Ref. [32]. On the
other hand, the same problem in the PM scenario has been elaborated in Refs.
[33, 34] and the upper bound of $1/\sqrt{2}$ on the critical value of the
symmetric detection efficiency was found.

Since $\eta$ does not depend on $y$, the expectation value $E_{x,y}$ becomes
$E_{x,y}(\eta)=\eta E_{x,y}+(1-\eta)$ for all $x$ and $y$. Hence, the witness
matrix $M$ detects quantumness with finite detection efficiency $\eta$
(assuming optimal preparation states and measurements) whenever we have

$\eta q(M)+(1-\eta)\sum_{x,y}M_{x,y}>L_{2}(M).$ (36)

Recalling $S(M)=\sum_{x,y}M_{x,y}$, solving the above relation for $\eta$, and
optimizing over all $M$ witness matrices, we obtain the critical detection
efficiency $\eta_{\text{crit}}$:

$\eta_{\text{crit}}=\min_{M}{\frac{L_{2}(M)-S(M)}{q(M)-S(M)}}=\frac{1}{K_{\text{D}}},$
(37)

where $K_{\text{D}}$ is defined by (19). In particular using the lower bound
value $K_{\text{D}}\geq 1.5682$, we obtain the improved upper bound $0.6377$
on $\eta_{\text{crit}}$.

It should be noted, however, that the above is not the most general detection
efficiency model. Rather than outputting $b_{y}=1$, Bob can output a third
result, which could potentially give a lower detection efficiency threshold.
An open problem is whether this third outcome can lower the detection
efficiency threshold. In the above, we also assumed that Bob’s qubit
measurements are rank-1 projectors that can achieve $q(M)$. However, it is
known that the true qubit maximum $Q(M)$ (in (7)) can be larger than $q(M)$
(in (8)) for a given $M$. Hence, we can say that the most general symmetric
detection efficiency threshold is upper bounded by $1/K_{\text{D}}$, and it is
an open problem whether this upper bound is tight or not.

##  III Methods

###  III.1 Properties of the $L_{2}$ and $L_{k}$, $k>2$ norm

Notations.—We first introduce notation used throughout this subsection. Let
$A^{n},n=0,1,2,\dots$ be the set of $n$ dimensional vectors over the set $A$.
Let $v_{i}$ denote the $i$th element of $v\in A^{n}$ ($i=1,2,\dots,n$). Let
$\\_;\\_:A^{n}\times A^{m}\rightarrow A^{n+m}$ denote the concatenation of
vectors. Let $()$ the singleton element of $A^{0}$. Further let $(a)\in A^{1}$
if $a\in A$. The parenthesis may be omitted so
$(1);(2);(3)=1;2;3\in\mathbb{R}^{3}$, for example. Let
$\overline{a}^{n}=a;a;...;a\in A^{n}$ where $a\in A$. We write $\overline{a}$
instead of $\overline{a}^{n}$ if $n$ can be inferred from the context. We
define $\mathcal{M}_{n,m}$ as the set of real $n\times m$ matrices. Matrices
are represented as vectors of their row vectors, i.e.
$\mathcal{M}_{n,m}=(\mathbb{R}^{m})^{n}$. Let $M^{\top}\in\mathcal{M}_{m,n}$
be the transposition of $M\in\mathcal{M}_{n,m}$ and let
$\mathbb{I}^{m}\in\mathcal{M}_{m,m}$ denote the $m\times m$ identity matrix.
Further, it is convenient to define by
$\mathcal{W}_{n,k}=\\{\mathbb{I}^{k}_{j}\,|\,j=1,2,\dots,k\\}^{n}\subset\mathcal{M}_{n,k}$
the set of matrices whose rows are all $0$s, but exactly one is $1$. Let
$\mathcal{P}_{n}\subset\mathcal{M}_{n,n}$ denote the set of permutation
matrices. Let $\left\|M\right\|_{1}=\sum_{i=1}^{n}\left\|M_{i}\right\|_{1}$
denote the Manhattan norm of the matrix $M\in\mathcal{M}_{n,m}$.

Definition of $L_{k}$.—We first give the definition of $L_{k}$. Let
$k\in\mathbb{N}^{+}.$

$\displaystyle L_{k}:\mathcal{M}_{n,m}\rightarrow\mathbb{R}$ (38)
$\displaystyle
L_{k}(M)=\max_{W\in\mathcal{W}_{n,k}}\left\|W^{\top}M\right\|_{1}.$

Note that $W$ is defined above in Notations and $W^{\top}$ denotes the
transposed matrix of $W$. We prove below that Eq. (38) corresponds to Eq. (14)
in the case of $k=2$. The proof is as follows

$\displaystyle\max_{a_{x}\in\\{\pm 1\\}}$
$\displaystyle\left(\left\|\sum_{x:a_{x}=+1}M_{x}\right\|_{1}+\left\|\sum_{x:a_{x}=-1}M_{x}\right\|_{1}\right)$
$\displaystyle=\max_{W\in\mathcal{W}_{n,2}}\left(\left\|W^{\top}_{1}M\right\|_{1}+\left\|W^{\top}_{2}M\right\|_{1}\right)$
$\displaystyle=\max_{W\in\mathcal{W}_{n,2}}\left\|W^{\top}M\right\|_{1}$
$\displaystyle=L_{2}(M).$

Properties of $L_{k}$.—We prove several interesting properties of $L_{k}$.
Note that our focus in the main text is on $k=2$. However, the general case
$k\geq 2$ is of interest for its own sake. Moreover, it is also motivated
physically, corresponding to classical communication beyond bits [7, 35].
First we prove that $L_{k}$ is a norm for any $k\geq 2$. To this end, we prove
its homogeneity, positive definiteness and subadditivity properties.

######  Lemma III.1.

$L_{k}$ is a norm.

Homogeneity:

$\displaystyle L_{k}(tM)$
$\displaystyle=\max_{W\in\mathcal{W}_{n,k}}\left\|W^{\top}(tM)\right\|_{1}$
$\displaystyle=\max_{W\in\mathcal{W}_{n,k}}|t|\left\|W^{\top}M\right\|_{1}$
$\displaystyle=|t|\max_{W\in\mathcal{W}_{n,k}}\left\|W^{\top}M\right\|_{1}$
$\displaystyle=|t|L_{k}(M),$

where $|t|$ denotes the absolute value of the scalar $t$ and $L_{k}$ is
defined by (38).

Positive definiteness:

$\displaystyle L_{k}(M)$ $\displaystyle=0$
$\displaystyle\Rightarrow\max_{W\in\mathcal{W}_{n,k}}\left\|W^{\top}M\right\|_{1}=0$
$\displaystyle\Rightarrow\forall
W\in\mathcal{W}_{n,k}:\left\|W^{\top}M\right\|_{1}=0$
$\displaystyle\Rightarrow\forall
W\in\mathcal{W}_{n,k}:W^{\top}M=\overline{\overline{0}}$
$\displaystyle\Rightarrow\forall i:M_{i}=\overline{0}$
$\displaystyle\Rightarrow M=\overline{\overline{0}}.$

Triangle inequality:

$\displaystyle
L_{k}(M+N)=\max_{W\in\mathcal{W}_{n,k}}\left\|W^{\top}(M+N)\right\|_{1}$
$\displaystyle\leq\max_{W\in\mathcal{W}_{n,k}}(\left\|W^{\top}M\right\|_{1}+\left\|W^{\top}N\right\|_{1})$
$\displaystyle\leq\max_{W\in\mathcal{W}_{n,k}}\left\|W^{\top}M\right\|_{1}+\max_{W\in\mathcal{W}_{n,k}}\left\|W^{\top}N\right\|_{1}$
$\displaystyle=L_{k}(M)+L_{k}(N).$

$\hfill\blacksquare$

Let us define $L(M)$ as follows

$L(M)=\max_{v\in\\{-1,+1\\}^{n}}\left\|vM\right\|_{1}.$ (39)

The above definition is consistent with the one given in (17). $L(M)$ is the
local or classical bound of correlation Bell inequalities [36] defined by the
correlation matrix $M$ in (39). The $L(M)$ quantity also appears in computer
science literature under the name of $K_{m,n}$-quadratic programming [37]. Let
us note that recently an efficient computation of $L(M)$ has been proposed in
Ref. [23] along with the code [38].

First we prove the basic property that $L_{2}(M)\geq L(M)$ for any $M$. Next
we prove that $L_{k}(M)\leq L_{k+1}(M)$ for $k\geq 2$. Then we bound
$L_{k}(M)$ from above by the value of $L(M)$ multiplied by $k$. However, we do
not know whether the bound can be saturated or not. The lemma stating our
first claim is as follows

######  Lemma III.2.

$L(M)\leq L_{2}(M),$ (40)

where the proof is given as the following chain of equations plus a single
inequality invoked in the fourth line

$\displaystyle L(M)$
$\displaystyle=\max_{v\in\\{-1,+1\\}^{n}}\left\|vM\right\|_{1}$
$\displaystyle=\max_{v\in\\{-1,+1\\}^{n}}\left\|\frac{1}{2}(\overline{1}+v)M-\frac{1}{2}(\overline{1}-v)M\right\|_{1}$
$\displaystyle=\max_{W\in\mathcal{W}_{n,2}}\left\|W^{\top}_{1}M-W^{\top}_{2}M\right\|_{1}$
$\displaystyle\leq\max_{W\in\mathcal{W}_{n,2}}(\left\|W^{\top}_{1}M\right\|_{1}+\left\|W^{\top}_{2}M\right\|_{1})$
$\displaystyle=\max_{W\in\mathcal{W}_{n,2}}\left\|W^{\top}M\right\|_{1}$
$\displaystyle=L_{2}(M).$

$\hfill\blacksquare$

Our next lemma proves that $L_{k}(M)$ is monotone increasing with $k$.

######  Lemma III.3.

$L_{k}(M)\leq L_{k+1}(M).$ (41)

The proof is given below as the following chain:

$\displaystyle L_{k}(M)$
$\displaystyle=\max_{W\in\mathcal{W}_{n,k}}\left\|W^{\top}M\right\|_{1}$
$\displaystyle=\max_{W\in\mathcal{W}_{n,k}}\sum_{i=1}^{k}\left\|(W^{\top}M)_{i}\right\|_{1}$
$\displaystyle=\max_{W\in\mathcal{W}_{n,k}}(\sum_{i=1}^{k}\left\|(W^{\top}M)_{i}\right\|_{1}+\left\|\overline{0}M\right\|_{1})$
$\displaystyle=\max_{W\in\mathcal{W}_{n,k}}\sum_{i=1}^{k+1}\left\|((W^{\top};\overline{0})M)_{i}\right\|_{1}$
$\displaystyle=\max_{W\in\mathcal{W}_{n,k}}\left\|(W^{\top};\overline{0})M\right\|_{1}$
$\displaystyle\leq\max_{W\in\mathcal{W}_{k+1,n}}\left\|W^{\top}M\right\|_{1}$
$\displaystyle=L_{k+1}(M).$

$\hfill\blacksquare$

Finally, we prove an upper bound on $L_{k}(M)$. Our lemma reads as follows

######  Lemma III.4.

$L_{k}(M)\leq kL(M)$ (42)

Proof.

$\displaystyle L_{k}(M)$
$\displaystyle=\max_{W\in\mathcal{W}_{n,k}}\left\|W^{\top}M\right\|_{1}$
$\displaystyle=\max_{W\in\mathcal{W}_{n,k}}\sum_{i=1}^{k}\left\|(W^{\top}M)_{i}\right\|_{1}$
$\displaystyle=\max_{W\in\mathcal{W}_{n,k}}\sum_{i=1}^{k}\left\|W^{\top}_{i}M\right\|_{1}$
$\displaystyle=\max_{W\in\mathcal{W}_{n,k}}\sum_{i=1}^{k}\frac{1}{2}\left\|(2W^{\top}_{i}-\overline{1})M+\overline{1}M\right\|_{1}$
$\displaystyle\leq\max_{W\in\mathcal{W}_{n,k}}\sum_{i=1}^{k}\frac{1}{2}(\left\|(2W^{\top}_{i}-\overline{1})M\right\|_{1}+\left\|\overline{1}M\right\|_{1})$
$\displaystyle\leq\max_{W\in\mathcal{W}_{n,k}}\sum_{i=1}^{k}\frac{1}{2}(L(M)+L(M))$
$\displaystyle=\max_{W\in\mathcal{W}_{n,k}}\sum_{i=1}^{k}L(M)$
$\displaystyle=\max_{W\in\mathcal{W}_{n,k}}kL(M)$ $\displaystyle=kL(M).$

To arrive at the sixth line, we invoked the definition (39).
$\hfill\blacksquare$

It is an open question whether Lemma 42 is tight or not. However, we can find
a family of matrices $M^{(k)}$, $k\geq 2$ such that the ratio
$L_{k}(M^{(k)})/L(M^{(k)})$ tends to infinity with increasing $k$. More
formally we have

######  Lemma III.5.

For all $\varepsilon>0$ there exists a matrix $M$ and $k>1$ such that

$\frac{L(M)}{L_{k}(M)}<\varepsilon.$ (43)

The proof is based on an explicit construction of matrices $M^{k}$,
$k=(2,\ldots,\infty)$ defined in Ref. [39]. See also Refs. [40, 41].

Proof. Let $M^{k}\in\mathcal{M}_{k,2^{k-1}}$, $k=(1,2,\dots,\infty)$ be a
family of matrices such that [39]

$M^{k}_{i,j}=(-1)^{\left\lfloor\frac{j}{2^{k-i-1}}\right\rfloor}.$ (44)

For example,

$M^{4}=\left(\begin{array}[]{rrrrrrrr}1&1&1&1&1&1&1&1\\\
1&1&1&1&-1&-1&-1&-1\\\ 1&1&-1&-1&1&1&-1&-1\\\
1&-1&1&-1&1&-1&1&-1\end{array}\right).$ (45)

Now by explicit calculations we find

$\frac{L(M^{k})}{L_{k}(M^{k})}=\frac{k\left(\begin{array}[]{c}k-1\\\
\left\lfloor\frac{k-1}{2}\right\rfloor\end{array}\right)}{k2^{k-1}}\sim\sqrt{\frac{2}{\pi
k}}.$ (46)

$\hfill\blacksquare$

Note that in the particular case of $k=2$ the matrix $M^{(k)}$ is the CHSH
expression [27], in which case $L(M^{(2)})=2$ and $L_{2}(M^{(2)})=4$. Hence,
for $k=2$ the upper bound in Lemma 42 is tight. We conjecture that the bound
is not tight for greater values of $k$.

Finally, we show how $L_{2}$ and in general $L_{k}$ behaves with the
concatenation $(A;B)$ of two matrices $A$ and $B$, where we defined

$(A;B)=\left[\begin{array}[]{r}A\\\ B\end{array}\right].$ (47)

######  Lemma III.6.

Let $A\in\mathcal{M}_{i,m},\;B\in\mathcal{M}_{j,m}$. Then we have

$L_{k}(A;B)\leq L_{k}(A)+L_{k}(B).$ (48)

Proof.

$\displaystyle L_{k}(A;B)$
$\displaystyle=\max_{W\in\mathcal{W}_{i+j,k}}\left\|W^{\top}(A;B)\right\|_{1}$
$\displaystyle=\max_{S\in\mathcal{W}_{i,k}}\max_{T\in\mathcal{W}_{j,k}}\left\|(S;T)^{\top}(A;B)\right\|_{1}$
$\displaystyle=\max_{S\in\mathcal{W}_{i,k}}\max_{T\in\mathcal{W}_{j,k}}\left\|S^{\top}A+T^{\top}B\right\|_{1}$
$\displaystyle\leq\max_{S\in\mathcal{W}_{i,k}}\max_{T\in\mathcal{W}_{j,k}}(\left\|S^{\top}A\right\|_{1}+\left\|T^{\top}B\right\|_{1})$
$\displaystyle\leq\max_{S\in\mathcal{W}_{i,k}}\left\|S^{\top}A\right\|_{1}+\max_{T\in\mathcal{W}_{j,k}}\left\|T^{\top}B\right\|_{1}$
$\displaystyle=L_{k}(A)+L_{k}(B).$

$\hfill\blacksquare$

Note that $L_{k}(A)\leq L_{k}(A;B)$ does not hold in general. For example, let
us have

$A=\left(\begin{array}[]{rr}1&1\\\ 1&-1\end{array}\right)$ (49)

and

$B=\left(\begin{array}[]{rr}-1&0\end{array}\right).$ (50)

Then by explicit calculation we obtain

$4\\!=\\!L_{2}(A)>L_{2}(A;B)\\!=\\!3.$ (51)

Finally, it is shown that $L_{k}$ relates to the cut norm $C$, a matrix norm
introduced by Frieze and Kannan in Ref. [42] (see also [43] for several
applications in graph theory). This norm is defined as follows:

$C(M)=\max\sum_{x=1}^{n}\sum_{y=1}^{m}M_{x,y}a_{x}b_{y},$ (52)

where the maximum is taken over all $a_{x},b_{y}\in\\{0,1\\}$. Note the
similarity in the definition with the $L(M)$ norm (17) which is equivalent to
(39). It has been shown that $C(M)$ is related to $L(M)$ as follows [42, 44]:

$C(M)\leq L(M)\leq 4C(M).$ (53)

Using the above relation (53) along with Lemma 42, we find that

$C(M)\leq L_{k}(M)\leq 4kC(M),$ (54)

and for the special case of $L_{2}$ we have the following lower and upper
bounds:

$C(M)\leq L_{2}(M)\leq 8C(M).$ (55)

Generalization of the $L_{k}$ norm.—Below we generalize the norm $L_{k}(M)$ to
$F_{M}$, which extension will prove to be a key property in the Branch-and-
Bound [17] implementation of the $L_{k}$ algorithm. To do so, first we define
the following function

######  Definition III.7.

$\displaystyle F_{M}:\mathcal{W}_{i,k}\rightarrow\mathbb{R}$ (56)
$\displaystyle
F_{M}(P)=\max_{W\in\mathcal{W}_{n-i,k}}\left\|(P;W)^{\top}M\right\|_{1}$

where $i=(0,1,2,\dots,n$) and $M\in\mathcal{M}_{n,m}$.

In other words, $F_{M}(P)$ is the maximum of $\left\|W^{\top}M\right\|_{1}$
where $W\in\mathcal{W}_{k,n}$ and the prefix of $W$ is $P$. $F_{M}$ can be
considered as a generalization of $L_{k}(M)$. The following lemma introduces a
key property which is made use of in the Branch-and-Bound method.

######  Lemma III.8.

$F_{A;B}(P)\leq\left\|P^{\top}M\right\|_{1}+L_{k}(B)$ (57)

Proof.

$\displaystyle F_{A;B}(P)$
$\displaystyle=\max_{W\in\mathcal{W}_{n-i,k}}\left\|(P;W)^{\top}(A;B)\right\|_{1}$
$\displaystyle=\max_{W\in\mathcal{W}_{n-i,k}}\left\|(P^{\top}A+W^{\top}B)\right\|_{1}$
$\displaystyle\leq\max_{W\in\mathcal{W}_{n-i,k}}(\left\|P^{\top}A\right\|_{1}+\left\|W^{\top}B\right\|_{1})$
$\displaystyle=\left\|P^{\top}A\right\|_{1}+\max_{W\in\mathcal{W}_{n-i,k}}\left\|W^{\top}B\right\|_{1}$
$\displaystyle=\left\|P^{\top}A\right\|_{1}+L_{k}(B).$

$\hfill\blacksquare$

Let us now give the following definition further generalizing $F_{M}(P)$:

######  Definition III.9.

$f_{M}(P)(c)=\max(F_{M}(P),c)$ (58)

The computation of $f_{M}$ can be optimized such that for big enough $c$
values $f_{M}(P)(c)$ returns $c$ without computing $F_{M}(P)$. This is
expressed by the following lemma.

######  Lemma III.10.

$\displaystyle f_{M}(P)(c)$
$\displaystyle=\left\\{\begin{array}[]{l}\max(\left\|P^{\top}M\right\|_{1},c)\quad\quad\quad\quad\quad\quad\;\;\text{if
}P\in\mathcal{W}_{n,k},\\\ c\quad\text{if
}\left\|P^{\top}A\right\|_{1}+L_{k}(B)\leq c,\quad\;\;\;A;B=M,\\\
(f_{M}(P;\mathbb{I}^{k}_{0})\circ\dots\circ
f_{M}(P;\mathbb{I}^{k}_{k}))(c)\;\;\,\text{otherwise}\end{array}\right.$ (62)

The proof given below is split into three cases. Case 1: if
$P\in\mathcal{W}_{n,k}$, then

$\displaystyle f_{M}(P)(c)$
$\displaystyle=\max\left(\max_{W\in\mathcal{W}_{n-n,k}}\left\|(P;W)^{\top}M\right\|_{1},c\right)\quad\text{by}\;(\ref{KDef})\,\text{and}\,(\ref{KPrimeDef})$
$\displaystyle=\max(\left\|(P;())^{\top}M\right\|_{1},c)$
$\displaystyle=\max(\left\|P^{\top}M\right\|_{1},c).$

Case 2:

$\displaystyle\left\|P^{\top}A\right\|_{1}$ $\displaystyle+L_{k}(B)\leq c$
$\displaystyle\Rightarrow F_{M}(P)\leq c\quad\text{by}\;(\ref{FfL2})$
$\displaystyle\Rightarrow\max(F_{M}(P),c)=c$ $\displaystyle\Rightarrow
f_{M}(P)(c)=c\quad\text{by}\;(\ref{KPrimeDef})$

Case 3:

$\displaystyle f_{M}(P)(c)$
$\displaystyle=\max\left(\max_{W\in\mathcal{W}_{n-i,k}}\left\|(P;W)^{\top}M\right\|_{1},c\right)\quad\text{by}\;(\ref{KDef},\ref{KPrimeDef})$
$\displaystyle=\max\left(\max_{S\in\mathcal{W}_{1,k},W\in\mathcal{W}_{n-i-1,k}}\left\|(P;S;W)^{\top}M\right\|_{1},c\right)$
$\displaystyle=\max\left(\max_{j}\max_{W\in\mathcal{W}_{n-i-1,k}}\left\|(P;\mathbb{I}^{k}_{j};W)^{\top}M\right\|_{1},c\right)$
$\displaystyle=\max(\max_{j}F_{M}(P;\mathbb{I}^{k}_{j}),c)$
$\displaystyle=\max(F_{M}(P;\mathbb{I}^{k}_{0}),\max(F_{M}(P;\mathbb{I}^{k}_{1}),\max(...,c)))$
$\displaystyle=(f_{M}(P;\mathbb{I}^{k}_{0})\circ\dots\circ
f_{M}(P;\mathbb{I}^{k}_{k}))(c).$

$\hfill\blacksquare$

Our last lemma in this subsection reads

######  Lemma III.11.

$L_{k}(M)=f_{M}(())(0)$ (63)

and it can be proved as follows:

$\displaystyle f_{M}(())(0)$
$\displaystyle=\max\left(\max_{W\in\mathcal{W}_{n,k}}\left\|(();W)^{\top}M\right\|_{1},0\right)\quad\text{by}\,(\ref{KDef},\ref{KPrimeDef})$
$\displaystyle=\max_{W\in\mathcal{W}_{n,k}}\left\|W^{\top}M\right\|_{1}$
$\displaystyle=L_{k}(M)$

$\hfill\blacksquare$

###  III.2 Programming tips for the efficient implementation of the $L_{2}$
and $L_{k}$ codes

In this subsection, we give programming tips for the branch-and-bound [17]
implementation of the exact computation of $L_{k}(M)$ for any $k\geq 2$. For
$k=2$ and $k=3$ our algorithms are even faster than the $L_{k}$ solver for
general $k$ due to specialization which we detail below. First, we remind the
reader of the notation defined in Sec. III.1. The Haskell code can be
downloaded from Github [45]. Instructions installing and using the code
(including parallel execution and using guessed results) can also be found
there.

Branch-and-bound calculation of $L_{k}$.—The norm $L_{k}(M)$ for $k\geq 2$ can
be calculated using the following definition and the following lemma.

######  Definition III.12.

For all $M\in\mathcal{M}_{n,m},\,0\leq i\leq n$ let

$\displaystyle
f_{M}:\mathcal{W}_{i,k}\rightarrow(\mathbb{R}\rightarrow\mathbb{R})$
$\displaystyle f_{M}(P)(c)$ (64)
$\displaystyle=\left\\{\begin{array}[]{l}\max(\left\|P^{\top}M\right\|_{1},c)\quad\quad\quad\quad\quad\quad\quad\text{if
}P\in\mathcal{W}_{n,k},\\\ c\quad\text{if
}\left\|P^{\top}A\right\|_{1}+L_{k}(B)\leq c,\quad\quad\;A;B=M,\\\
(f_{M}(P;\mathbb{I}^{k}_{0})\circ\dots\circ
f_{M}(P;\mathbb{I}^{k}_{k}))(c)\;\;\,\,\text{otherwise.}\end{array}\right.$
(66)

The function $f_{M}$ recursively calls itself with larger and larger $P$
prefixes until the prefix size reaches $n$. The middle case is a conditional
exit from the recursion, which speeds up the computation crucially.

######  Lemma III.13.

$L_{k}(M)=f_{M}(())(0).$ (67)

Reducing cost by sharing sub-calculations.—In the definition III.12, the most
expensive calculations are $L_{k}(B)$, $\left\|P^{\top}M\right\|_{1}$ and
$\left\|P^{\top}A\right\|_{1}$. We show how to reduce the cost of these
calculations. The cost of $L_{k}(B)$ can be reduced by memoizing the
previously computed $L_{k}$ values in a table.

If $M=(v_{1};v_{2};v_{3};\dots;v_{n})$ then $L_{k}(M)$ depends on
$L_{k}(v_{i};v_{i+1};\dots;v_{n})$, where $i=2,3,4,\dots,n$. Note that
$L_{k}(v_{i};v_{i+1};\dots;v_{n})$ itself depends on
$L_{k}(v_{j};v_{j+1};\dots;v_{n})$, where $j=i+1,i+2,\dots,n$. If we take into
account all dependencies, the correct order of calculating $L_{k}$ values is
$L_{k}(v_{n})$, $L_{k}(v_{n-1},v_{n})$, $L_{k}(v_{n-2},v_{n-1},v_{n})$, …,
$L_{k}(v_{2},v_{3},\dots,v_{n})$.

There is an option to skip the $\left\|P^{\top}A\right\|_{1}+L_{k}(B)\leq c$
test for large $B$ matrices. This means that $L_{k}(B)$ should not be
calculated, and the trade-off is that we miss opportunities for exiting
recursion. In our experience, skipping the test for
$B\in\mathcal{M}_{k,m},k\geq(3n/4)$ results in about $2\times$ speedup.

The cost of calculating $\left\|P^{\top}A\right\|_{1}$ is $O(km)$ if
$A\in\mathcal{M}_{k,m}$. Note that

$(P;Q)^{\top}(A;B)=P^{\top}A+Q^{\top}B.$ (68)

$P^{\top}A$ is already computed by the time when
$(P;\mathbb{I}^{k}_{i})^{\top}(A;v)$ is needed, so the cost of
$\left\|P^{\top}A\right\|_{1}$ can be reduced to $O(m)$ by (68). The cost of
$P^{\top}M$ can be reduced in the same way. This implies a considerable
speedup; for example, for $M\in\mathcal{M}_{70,70}$ the calculation of
$L_{2}(M)$ can be made nearly 70 times faster by this optimization.

The cost of $\left\|P^{\top}A\right\|_{1}$ can be further reduced by caching
the previously calculated Manhattan norms of the rows of the matrix
$P^{\top}A$.

Reducing cost by symmetries.—For all $S\in\mathcal{P}_{k}$ permutation
matrices

$\left\|W^{\top}M\right\|_{1}=\left\|(WS)^{\top}M\right\|_{1}.$ (69)

The cost of $L_{2}$ can be halved by (69) as follows. Let

$S=\left(\begin{array}[]{rr}0&1\\\ 1&0\end{array}\right)\in\mathcal{P}_{2}.$
(70)

From
$\left\|(\mathbb{I}^{2}_{2};W)^{\top}M\right\|_{1}=\left\|(\mathbb{I}^{2}_{1};WS)^{\top}M\right\|_{1}$
it follows that $f_{M}(\mathbb{I}^{2}_{2},c)=f_{M}(\mathbb{I}^{2}_{1},c)$.
This means that we can skip the calculation of $f_{M}(\mathbb{I}^{2}_{2},c)$
for all $c$, thus $L_{2}(M)=f_{M}((\mathbb{I}^{2}_{1}),0)$, i.e., we start the
calculation with a non-empty prefix which saves work.

Harnessing (69) in the general $L_{k}$ case is a bit more complex. First we
define the set of canonical prefixes. A prefix
$P=\mathbb{I}^{k}_{i_{1}};\mathbb{I}^{k}_{i_{2}};\dots\mathbb{I}^{k}_{i_{j}}$
is canonical if the first occurrences of the numbers in the indices
$i_{1},i_{2},\dots,i_{j}$ is the sequence $1,2,3,\dots$. For example, the
prefix
$\mathbb{I}^{k}_{1};\mathbb{I}^{k}_{2};\mathbb{I}^{k}_{1};\mathbb{I}^{k}_{3}$
is canonical but
$\mathbb{I}^{k}_{1};\mathbb{I}^{k}_{3};\mathbb{I}^{k}_{1};\mathbb{I}^{k}_{2}$
is non-canonical. For each prefix $P$, there exists a permutation $S$ such
that $PS$ is canonical, so that, $f_{M}(P,c)=f_{M}(PS,c)$, which means that it
is enough to examine only the canonical prefixes to compute $L_{k}$.

Parallel and concurrent execution.—For parallel execution one can use the
following equation:

$f_{M}(P)(c)=\max_{i\in\\{1,\dots,k\\}}f_{M}(P;\mathbb{I}^{k}_{i})(c)$ (73)

We used Eq. (73) for $P\in\mathcal{W}_{i,k},i<d$, where $d$ is a “parallel
depth” for fine-tuning the execution for different architectures. Higher depth
is better for more cores.

Parallel execution may miss opportunities of exiting recursion because there
is no communication between threads about the best known $L_{k}$ values at a
certain point of time. Therefore we implemented concurrent execution where
threads share the best known $L_{k}$ values.

Reducing cost by guessed $L_{k}$ values.—Optionally, the computation can be
sped up by providing a guessed $L_{k}(M)$ value by the user. This value will
be used instead of $0$ in Eq. (67). The guessed value may be lower than
$L_{k}(M)$. Higher guessed values are better, unless the guessed value is
higher than $L_{k}(M)$, in which case $f_{M}$ returns the guessed value. We
compared the result of $f_{M}$ with the witness $W$ of the maximal
$\left\|W^{\top}M\right\|_{1}$ value, to be able to detect whether the guessed
value was too high or not.

###  III.3 $L$-norm and $L_{2}$-norm are the same for a special family of
matrices $M^{\prime}$

We relate $L(M^{\prime})$ to $L_{2}(M^{\prime})$, where $M^{\prime}$ is given
by the following matrix

$\displaystyle M^{\prime}=\begin{pmatrix}&M\\\ -&M\end{pmatrix},$ (74)

where $M$ is a matrix of size $n\times m$ with arbitrary real entries. Note
that $M^{\prime}$ has size $2n\times m$ and $M^{\prime}$ has rows such that
$M^{\prime}_{x}=M_{x}$ and $M^{\prime}_{x+m}=-M_{x}$ for all $x=1,\ldots,m$.
Then the following lemma holds.

######  Lemma III.14.

$L_{2}(M^{\prime})=L(M^{\prime})=2L(M)$ for any matrix $M^{\prime}$ of the
form (74), where $L_{2}$ is the $L_{2}$ norm given by the definition (14) and
$L$ is the local bound given by (39). Note that $L_{k}$ is defined by (38),
where the case $k=2$ corresponds to the definition of $L_{2}$ in (14).

Proof. We fix a matrix $M$ of dimension $n\times m$ which specifies
$M^{\prime}$ by the virtue of (74). Let $a_{x}\in\\{-1,1\\}$, $x=1,\ldots,n$
and $b_{y}\in\\{-1,1\\}$, $y=1,\ldots,m$ be the optimal vectors giving $L(M)$
in (39). Note that these values are not unique in general, different optimal
configurations may exist, however, we choose one such optimal vectors $a_{x}$
and $b_{y}$. We then choose $a_{x+n}=-a_{x}$ for $x=1,\ldots,n$, and
$b_{y}^{+}=b_{y}^{-}=b_{y}$ for $y=1,\ldots,m$. With these values, we obtain
the lower bound $L_{2}(M^{\prime})\geq 2L(M)$ on $L_{2}(M^{\prime})$ in (12).
Now we show the upper bound $L_{2}(M^{\prime})\leq 2L(M)$, which implies
$L_{2}(M^{\prime})=2L(M)$.

As a contradiction of the lemma, assume that $L_{2}(M^{\prime})>2L(M)$. Then,
not all $a_{x}$ vectors corresponding to the $L_{2}(M^{\prime})$ value have
the property $a_{x+m}=-a_{x}$ for each $x$. That is, there exists at least one
$x$, call it $x^{\prime}$, for which $a_{x}^{\prime}=a_{x^{\prime}+n}$.
Suppose that there is one such an $x^{\prime}$ (the proof for multiple
$x^{\prime}$ indices for which $a_{x}^{\prime}=a_{x^{\prime}+n}$ is very
similar). Then in the formula (14) for $L_{2}(M^{\prime})$ the two rows
$x^{\prime}$ and $x^{\prime}+n$ in question will appear within the same norm
(either in the first or second norm, depending on whether
$a_{x}^{\prime}=a_{x^{\prime}+n}$ takes the value $+1$ or $-1$). However, in
both cases they cancel each other from the norm in question. As a result, two
rows of $M^{\prime}$ in (74) are eliminated, one from the matrix $M$ and one
from the matrix $-M$. However, any matrix $\pm M$ from which one row has been
eliminated cannot have a local bound greater than $L(M)$. The same applies to
a matrix $\pm M$ from which we have removed several rows. Therefore,
$L_{2}(M^{\prime})>2L(M)$ cannot be true either. Thus we arrived at a
contradiction. $\hfill\blacksquare$

###  III.4 Adapting the Gisin-Gisin model to the PM scenario

We now adapt the LHV model of Ref. [13] which exploits the finite efficiency
of the detectors to reproduce the quantum correlations of the singlet state
exactly. We show that the LHV model in Ref. [13] can be adapted to the PM
communication scenario to produce the expectation value:

$E(\vec{a},\vec{b})=P(b=+1|\vec{a},\vec{b})-P(b=-1|\vec{a},\vec{b})=\frac{\vec{a}\cdot\vec{b}+1}{2},$
(75)

where $\vec{a}\in S^{2}$ denotes the preparation Bloch vector and $\vec{b}\in
S^{2}$ denotes the measurement Bloch vector. First we show that the outcomes
$b=\pm 1$ giving the expectation value

$E(\vec{a},\vec{b})=P(b=+1|\vec{a},\vec{b})-P(b=-1|\vec{a},\vec{b})=\vec{a}\cdot\vec{b}$
(76)

can be obtained with probability $(1/2)$ and $b=0$ outcome with probability
$(1/2)$. Then by coarse-graining the above distribution by grouping $b=0$
outcome with $b=+1$, we obtain the expectation value (75).

The classical model, using one bit of classical communication from Alice to
Bob, is as follows.

Protocol: Alice and Bob share a classical variable, which is in the form of a
unit vector $\vec{\lambda}$, chosen uniformly at random from the unit sphere
$S^{2}$.

  * •

(Alice) Alice sends a binary message $c=\text{sgn}(\vec{a}\cdot\vec{\lambda})$
to Bob. That is, $c=+1$ if $\vec{a}\cdot\vec{\lambda}\leq 0$ and $c=-1$ if
$\vec{a}\cdot\vec{\lambda}>0$.

  * •

(Bob) Bob outputs $b=\text{sgn}(c\vec{b}\cdot\vec{\lambda})$ with probability
$|\vec{b}\cdot\vec{\lambda}|$ (corresponding to the detection event $b=\pm 1$)
and Bob outputs $b=0$ with probability $1-|\vec{b}\cdot\vec{\lambda}|$
(corresponding to the non-detection event).

Our claim is as follows. The above protocol yields the correlations
$E(\vec{a},\vec{b})=\vec{a}\cdot\vec{b}$, that is, it reproduces the
correlations in Eq. (76) with probability $1/2$ and returns $b=0$ in the other
cases.

Proof.—We need to calculate the expectation value
$E(\vec{a},\vec{b})=P(b=+1|\vec{a},\vec{b})-P(b=-1|\vec{a},\vec{b})$ which
according to the above protocol in the detection events $b=\pm 1$ is given by
[13])

$E(\vec{a},\vec{b})=\int_{S^{2}}d\vec{\lambda}q(\vec{\lambda}|b=\pm
1)\text{sgn}(\vec{a}\cdot\vec{\lambda})\text{sgn}(\vec{b}\cdot\vec{\lambda}),$
(77)

where $q(\vec{\lambda}|b=\pm 1)$ is the conditional density probability
distribution of choosing $\vec{\lambda}$ given a detection event (either
output $b=+1$ or $b=-1$). This function can be calculated from

$q(\vec{\lambda}|b=\pm 1)=\frac{q(\vec{\lambda}\text{ and }b=\pm 1)}{p(b=\pm
1)},$ (78)

where the detection efficiency is $\eta=p(b=\pm 1)$ and the probability of
detection failure is $1-\eta=p(b=0)$. The value of $\eta$ is given by

$\eta=p(b=\pm
1)=\int_{S^{2}}\frac{d\vec{\lambda}}{4\pi}|\vec{b}\cdot\lambda|=\frac{1}{2},$
(79)

as stated and the protocol gives the density probability distribution
$q(\lambda\text{ and }b=\pm 1)=(\vec{b}\cdot\vec{\lambda})/(4\pi)$. Inserting
these values into (78) gives $q(\lambda|b=\pm
1)=(\vec{b}\cdot\vec{\lambda})/(2\pi)$, which in turn is inserted into (77) to
obtain the integral [13]:

$E(\vec{a},\vec{b})=\frac{1}{2\pi}\int_{S^{2}}d\vec{\lambda}(\vec{b}\cdot\vec{\lambda})\text{sgn}(\vec{a}\cdot\vec{\lambda}).$
(80)

The above integral can be calculated using spherical symmetries. In
particular, one can choose w.l.o.g. the vectors

$\displaystyle\vec{a}$ $\displaystyle=(0,0,1)$ $\displaystyle\vec{b}$
$\displaystyle=(\sin\alpha,0,\cos\alpha)$

as in Ref. [13], and then obtain

$E(\vec{a},\vec{b})=\cos\alpha=\vec{a}\cdot\vec{b}$ (81)

with probability (1/2), which we wanted to prove. $\hfill\blacksquare$

###  III.5 The modified Gilbert algorithm adapted to the PM scenario

For a given $\eta\in\left[1/2,1\right]$ and correlation matrix $E(\eta)$
defined by (27), the algorithm yields the following matrix $M$ satisfying

$\sum_{x=1}^{n}\sum_{y=1}^{m}M_{xy}E_{xy}(\eta)>L_{2}(M).$ (82)

Algorithm:

Input: The number of preparations $n$ and the number of measurement settings
$m$ that define the setup. The unit vectors $\\{\vec{a}_{x}\\}_{x=1}^{n}$
(i.e., the Bloch vectors of Alice’s prepared states) and
$\\{\vec{b_{y}}\\}_{y=1}^{m}$ (i.e., the Bloch vectors of Bob’s projective
rank-1 measurements). The $(n\times m)$-dimensional matrix $E(\eta)$ given by
the entries $E_{xy}(\eta)$ in (27). The values of $\epsilon$ and
$i_{\text{max}}$ that define the stopping criteria.

Output: The matrix $M$ of size $n\times m$.

  1. 1.

Set $i=0$ and set $E^{(i)}$ the $n\times m$ zero matrix.

  2. 2.

Given a matrix $E^{(i)}$ and the matrix $E(\eta)$, run a heuristic oracle that
maximizes the overlap
$\sum_{xy}(E_{xy}(\eta)-E_{xy}^{(i)})E_{xy}^{\text{det}}$ over all
deterministic one-bit correlations $E_{xy}^{\text{det}}$ in (11). The
description of this heuristic (see-saw) oracle is given in Sec. III.7. Denote
the point $E_{xy}^{\text{det}}$ returned by the oracle by
$E_{xy}^{\text{det,i}}$.

  3. 3.

Find the convex combination $E^{(i+1)}$ of $E^{(i)}$ and
$E_{xy}^{\text{det,i}}$ that minimizes the distance
$\sqrt{\sum_{xy}\left(E_{xy}(\eta)-E_{xy}^{(i)}\right)^{2}}$. Let us denote
this distance by $\text{dist}(i)$.

  4. 4.

Let $i=i+1$ and go to Step 2 until $\text{dist}(i)\leq\epsilon$ or
$i=i_{\text{max}}$.

  5. 5.

Return the matrix $M$ with coordinates $M_{xy}=E_{xy}(\eta)-E_{xy}^{(i)}$.

Note that $\text{dist}(i)$ is a decreasing function of $i$. Since maximizing
the overlap of $\sum_{xy}(E_{xy}(\eta)-E_{xy}^{(i)})E_{xy}^{\text{det}}$ over
all deterministic one-bit correlations vectors is an NP-hard problem, in Step
2 we use a heuristic method to do it, which we describe in Sec. III.7. On the
other hand, the description of an exact branch-and-bound type algorithm can be
found in Sec. III.2. We use the exact method, which is generally more time-
consuming than the see-saw method to check that the output matrix $M$
satisfies the condition (82) with the chosen parameter $\eta$. If this is
true, then it implies the lower bound $K_{\text{D}}\geq(1/\eta)$, as proved in
Sec. II.2. It should also be noted that the branch-and-bound-type algorithm is
much faster than the brute force algorithm (the implemented algorithm using
parallelism can be found in [45]). On a multi-core desktop computer, it can
solve problems in range $n=m=70$ in a day, while the brute force algorithm is
limited to about $n=m=40$ settings.

###  III.6 Parameters and implementation of Gilbert algorithm

Here we specify the explicit parameters that are used to obtain the lower
bound $K_{\text{D}}\leq 1.5682$. On the three-dimensional unit sphere, we
choose the vectors $\\{\vec{a}_{x}\\}_{x=1}^{n}$ and
$\\{\vec{b}_{y}\\}_{y=1}^{m}$ to be equal to each other,
$\vec{v}_{i}=\vec{a}_{i}=\vec{b}_{i}$ for $i=1,\ldots,n$, where $n=m=70$. The
70 unit vectors chosen define the optimal packing configuration in the
Grassmannian space which can be downloaded from Neil Sloane’s database [46].
The advantage of this type of packing is that the points and their antipodal
points are located as far apart as possible on the three-dimensional unit
sphere.

We implemented the modified Gilbert algorithm (of section III.5) in Matlab
with and without a memory buffer (see more details on the memory buffer in
Ref. [26]). In the case of using memory buffer, the step 3 is modified in the
algorithm so that instead of calculating the convex combination of the points
$E^{(i)}$ and $E_{xy}^{\text{det,i}}$ (see section III.5), we compute the
convex combination of $E^{(i)}$ and the points $E_{xy}^{\text{det,i-j}}$,
$j=0,\ldots,m-1$, where $m$ is the size of the memory buffer. In our explicit
computations, we use a buffer size $m=40$ and a stopping condition of
$k=2\times 10^{5}$ with $\eta=0.665$. Details on the performance of this
modification can be found in Ref. [26]. In step 2 of the Gilbert algorithm,
the oracle uses the see-saw heuristic described in Sec. III.7 to obtain a good
(typically tight) lower bound to $L_{2}(M)$. On the other hand, we used the
branch-and-bound-type algorithm described in Sec. III.2 to calculate
$L_{2}(M)$ exactly for integer $M$. The algorithm was implemented in Haskell.
See the GitHub site [45] for the downloadable version.

The Matlab file `eta_70.m`, which can also be downloaded from GitHub [45]
(located in the subdirectory `L2_eta_70`) gives detailed results on the input
parameters and the output matrix $M$. In particular, it gives the integer
matrix $M$, the unit vectors $\vec{a}_{i}=\vec{b}_{i}=\vec{v}_{i}$, the lower
bound
$\sum_{xy}M_{xy}\vec{a}_{x}\cdot\vec{b}_{y}=\sum_{xy}M_{xy}\vec{v}_{x}\cdot\vec{v}_{y}$
to $q(M)$ and the value $L_{2}(M)$. The running time of the Gilbert algorithm
(in Sec. III.5) implemented in Matlab was about one week. Note, however, that
most of the computation time was spent on the oracle (the see-saw part)
described in Sec. III.7. On the other hand, the Haskell code to compute the
exact $L_{2}(M)$ value of the $70\times 70$ witness matrix $M$ took about 8
hours to run on a HP Z8 workstation using 56 physical cores. The memory usage
of the computation was negligible.

The Matlab `eta_70.m` routine defines the $70\times 70$ matrix $M$, and gives
the $\vec{v}_{i}:=\vec{a}_{i}=\vec{b}_{i}$ the unit vectors from Sloane’s
database [46] for all $i=1,\ldots,70$. Note that $M$ is integer (by
multiplying the output $M$ matrix in the Gilbert algorithm by $1000$ and
truncating the non-integer part). This calculation yields
$S(M)=\sum_{x,y}M_{x,y}=194369$ and
$Q(M)=\sum_{x,y}M_{x,y}\vec{a}_{x}\cdot\vec{b}_{y}\simeq 5.3672235\times
10^{5}$. On the other hand, the branch-and-bound-type Haskell code [45] gives
the exact value $L_{2}(M)=412667$, which is matched by the see-saw search (in
Sec. III.7). From these numbers we then obtain

$K_{\text{D}}\geq\frac{Q(M)-S(M)}{L_{2}(M)-S(M)}>\frac{342353}{218298}=1.5682+\varepsilon$
(83)

and $1/K_{\text{D}}=0.6377-\varepsilon^{\prime}$ is the upper bound to the
critical detection efficiency $\eta_{\text{crit}}$, where $\varepsilon$ and
$\varepsilon^{\prime}$ are small positive numbers.

###  III.7 Lower bound to $L_{2}(M)$ using the see-saw iterative algorithm

Below we give an iterative algorithm based on see-saw heuristics to compute
$L_{2}(M)$. This algorithm forms the oracle part of step 2 of the Gilbert
algorithm, which is described in Sec. III.5.

Algorithm:

Input: Integer matrix $M$ of size $n\times m$.

Output: Lower bound $l_{2}(M)$ to $L_{2}(M)$ defined by formula (12).

  1. 1.

Let $l_{2}=0$.

  2. 2.

Choose random assignments $a_{x}=\pm 1$: That is, $a_{x}$ are (random)
elements of a vector $a$ of size $n$. Its elements are binary having value +1
or -1 only.

  3. 3.

Set $b^{+}=\text{sgn}(aM)$,where sgn denotes the (modified) sign function:
$\text{sgn}(x)=+1$ if $x\geq 0$ and $-1$ otherwise. Let us transpose $b^{+}$.

  4. 4.

Set $b^{-}=\text{sgn}(aM)$. Let us transpose $b^{-}$.

  5. 5.

Form the column vector $s^{+}=Mb^{+}$ of size $n$.

  6. 6.

Form the column vector $s^{-}=Mb^{-}$ of size $n$.

  7. 7.

Form the column vector $s=\max(s^{+},s^{-})$ of size $n$. That is,
$s_{x}=\max(s_{x}^{+},s_{x}^{-})$ for all $x=1,\ldots,n$.

  8. 8.

Form the $\pm 1$-valued column vector $a$ as follows: Let $a_{x}=+1$ if
$s_{x}^{+}\geq s_{x}^{-}$, otherwise let $a_{x}=-1$ for all $x=1,\ldots,n$.

  9. 9.

Let $l_{2}=\sum_{x=1}^{n}s_{x}$.

  10. 10.

With the new vector $a$, return to point 3. Repeat the algorithm until two
values of $l_{2}$ are equal in two consecutive iterations.

Note that at each iteration step, objective value $l_{2}(M)$ is guaranteed not
to decrease. Therefore, the output of the algorithm is a heuristic lower bound
on the exact value of $L_{2}(M)$.

##  IV Discussion

We have tested the quantumness of two-dimensional systems in the prepare-and-
measure (PM) scenario, with $n$ preparations and $m$ binary-outcome
measurement settings, where $n$ and $m$ fall well into the range of 70. In the
one-qubit PM scenario, a two-level system is transmitted from the sender to
the receiver. In this setup, a real $n\times m$ matrix $M$ defines the
coefficients of a linear witness. We denote by $L_{2}(M)$ the exact value of
the one-bit bound associated with matrix $M$. We found efficient numerical
algorithms for computing $L_{2}(M)$. If this bound is exceeded, we can detect
both the quantumness of the prepared qubits and the quantumness (i.e.
incompatibility) of the measurements.

We introduced new constants $K_{\text{M}}$ and $K_{\text{D}}$ which are
related to the Grothendieck constant of order 3. Our large-scale tools are
crucial for the efficient bounding of $L_{2}(M)$ and hence for bounding of the
constants $K_{\text{M}}$ and $K_{\text{D}}$. We further relate these new
constants to the white noise resistance of the prepared qubits and the
critical detection efficiency of the measurements performed.

For large $M$ matrices, we have given two algorithms for computing $L_{2}(M)$:
a simple iterative see-saw-type algorithm and a branch-and-bound-type
algorithm. The former is a heuristic algorithm that usually gives a tight
lower bound on $L_{2}(M)$. However, sometimes it fails to find the exact value
of $L_{2}(M)$. This happens more and more often as the size of the matrix $M$
gets larger and larger. In contrast, the latter branch-and-bound-type
algorithm gives the exact value of $L_{2}(M)$ and can be used to compute
$L_{2}(M)$ for matrix sizes as large as $70\times 70$. As an application of
the algorithms, we established the bounds $1.5682\leq K_{\text{D}}\leq 2$ on
the new constant and an upper bound of $\eta_{\text{crit}}\leq 0.6377$ on the
critical detection efficiency of qubit measurements in the PM scenario.

##  V Acknowledgements

We thank Mátyás Barczy, Emmanuel Zambrini Cruzeiro and Armin Tavakoli for
valuable discussions. We are particularly indebted to Mátyás Barczy for
pointers to the literature regarding the cut norm. T. V. acknowledges the
support of the EU (QuantERA eDICT) and the National Research, Development and
Innovation Office NKFIH (No. 2019-2.1.7-ERA-NET-2020-00003).

## References

  * [1] J. S. Bell, “On the Einstein-Poldolsky-Rosen paradox,” Physics 1, 195–200 (1964).
  * [2] N. Brunner, D. Cavalcanti, S. Pironio, V. Scarani, and S. Wehner, “Bell nonlocality,” Rev. Mod. Phys. 86, 419–478 (2014).
  * [3] H. M. Wiseman, S. J. Jones, and A. C. Doherty, “Steering, Entanglement, Nonlocality, and the Einstein-Podolsky-Rosen Paradox,” Phys. Rev. Lett. 98, 140402 (2007).
  * [4] J. Bowles, T. Vértesi, M. T. Quintino, and N. Brunner, “One-way Einstein-Podolsky-Rosen Steering,” Phys. Rev. Lett. 112, 200402 (2014).
  * [5] S. Jevtic, M. J. W. Hall, M. R. Anderson, M. Zwierz, and H. M. Wiseman, “Einstein-Podolsky-Rosen steering and the steering ellipsoid,” JOSA B 32, A40 (2015).
  * [6] R. Uola, A.C.S. Costa, H.C. Nguyen, O. Gühne, “Quantum steering,” Rev. Mod. Phys. 92, 015001 (2020).
  * [7] R. Gallego, N. Brunner, C. Hadley, A. Acín, “Device-independent tests of classical and quantum dimensions,” Phys. Rev. Lett. 105, 230501 (2010).
  * [8] J Ahrens, P Badziag, A Cabello, M Bourennane, “Experimental device-independent tests of classical and quantum dimensions,” Nat. Phys. 8, 592-595 (2012).
  * [9] M. Hendrych, R. Gallego, M. Mičuda, N. Brunner, A. Acín, J.P. Torres, “Experimental estimation of the dimension of classical and quantum systems”, Nat. Phys. 8, 588-591 (2012).
  * [10] J. Ahrens, P. Badziąg, M. Pawłowski, M. Żukowski, M. Bourennane, “Experimental tests of classical and quantum dimensionality”, Phys. Rev. Lett. 112, 140401 (2014).
  * [11] D. Poderini, S. Brito, R. Nery, F. Sciarrino, R. Chaves, “Criteria for nonclassicality in the prepare-and-measure scenario”, Phys. Rev. Res. 2, 043106 (2020).
  * [12] C. de Gois, G. Moreno, R. Nery, S. Brito, R. Chaves, R. Rabelo “General Method for Classicality Certification in the Prepare and Measure Scenario”, PRX Quantum 2, 030311 (2021).
  * [13] N. Gisin and B. Gisin, “A local hidden variable model of quantum correlation exploiting the detection loophole,” Phys. Lett. A260, 323 (1999).
  * [14] M. Navascués, T. Vértesi, Tamás, “Bounding the set of finite dimensional quantum correlations”, Phys. Rev. Lett. 115, 020501 (2015).
  * [15] A. Tavakoli, D. Rosset, M-O. Renou, “Enabling computation of correlation bounds for finite-dimensional quantum systems via symmetrization”, Phys. Rev. Lett. 122, 070501 (2019).
  * [16] A. Tavakoli, J. Kaniewski, T. Vértesi, D. Rosset, and N. Brunner, “Self-testing quantum states and measurements in the prepare-and-measure scenario,” Phys. Rev. A 98, 062307 (2018).
  * [17] A. H. Land and A. G. Doig, “An automatic method of solving discrete programming problems”, Econometrica 28, 497 (1960).
  * [18] A. Grothendieck, “Résumé de la théorie métrique des produits tensoriels topologiques,” Bol. Soc. Mat. São Paulo 8, 1 (1953).
  * [19] J. Krivine, “Constantes de Grothendieck et fonctions de type positif sur les spheres,” Adv. Math. 31, 16 – 30 (1979).
  * [20] A. Acín, N. Gisin, and B. Toner, “Grothendieck’s constant and local models for noisy entangled quantum states,” Phys. Rev. A 73, 062105 (2006).
  * [21] G. Pisier, “Grothendieck’s Theorem, past and present,” Bull. Amer. Math. Soc. 49, 237–323 (2012).
  * [22] B. Hua, M. Li, T. Zhang, C. Zhou, X. Li-Jost, S.M. Fei, “Towards Grothendieck constants and LHV models in quantum mechanics,”,J. Phys. A: Math. Theor. 48, 065302 (2015).
  * [23] P. Diviánszky, E. Bene, and T. Vértesi, “Qutrit witness from the Grothendieck constant of order four,” Phys. Rev. A 96, 012113 (2017).
  * [24] F. Hirsch, M. T. Quintino, T. Vértesi, M. Navascués, and N. Brunner, “Better local hidden variable models for two-qubit Werner states and an upper bound on the Grothendieck constant $K_{G}(3)$,” Quantum 1, 3 (2017).
  * [25] S. R. Finch, Mathematical constants.  Cambridge University Press, 2003.  http://www.cambridge.org/catalogue/catalogue.asp?isbn=0521818052.
  * [26] S. Brierley, M. Navascues, and T. Vertesi, “Convex separation from convex optimization for large-scale problems,” ArXiv e-prints (2016), arXiv:1609.05011 [quant-ph].
  * [27] J. F. Clauser, M. A. Horne, A. Shimony, R. A. Holt, “Proposed experiment to test local hidden-variable theories”, Phys. Rev. Lett. 23, 15 (1969).
  * [28] E. G. Gilbert, “An iterative procedure for computing the minimum of a quadratic form on a convex set,” SIAM Journal on Control 4, 61–80 (1966).
  * [29] T. Vértesi, “More efficient Bell inequalities for Werner states,” Phys. Rev. A 78, 032112 (2008).
  * [30] R. F. Werner, “Quantum states with Einstein-Podolsky-Rosen correlations admitting a hidden-variable model,” Phys. Rev. A 40, 4277–4281 (1989).
  * [31] J. Bowles, N. Brunner, M. Pawlowski, “Testing dimension and nonclassicality in communication networks,” Phys. Rev. A 92, 022351 (2015).
  * [32] J. A. Larsson, “Loopholes in Bell inequality tests of local realism,” J. Phys. A: Math. Theor. 47 424003 (2014).
  * [33] M. Dall’Arno, E. Passaro, R. Gallego, A. Acin, “Robustness of device-independent dimension witnesses,” Phys. Rev. A 8, 042312 (2012).
  * [34] H.-W. Li, Z.-Q. Yin, M. Pawłowski, G.-C. Guo, and Z.-F. Han, “Detection efficiency and noise in a semi-device-independent randomness-extraction protocol,” Phys. Rev. A 91, 032305 (2015).
  * [35] N. Brunner, M. Navascués, T. Vértesi, “Dimension witnesses and quantum state discrimination,” Phys. Rev. Lett. 110, 150501 (2013).
  * [36] B. S. Tsirelson, “Some results and problems on quantum Bell-type inequalities,” Hadronic J. Suppl. 8, 329–345 (1993). https://www.tau.ac.il/ tsirel/download/hadron.pdf.
  * [37] P. Raghavendra and D. Steurer, “Towards computing the Grothendieck constant,” In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 525 (2009).
  * [38] P. Diviánszky, https://github.com/divipp/kmn-programming (2017).
  * [39] T. Vértesi and K. F. Pál, “Generalized Clauser-Horne-Shimony-Holt inequalities maximally violated by higher-dimensional systems,” Phys. Rev. A 77, 042106 (2008).
  * [40] M. Epping, H. Kampermann, D. Bruß, “Designing Bell inequalities from a Tsirelson bound,” Phys. Rev. Lett. 111, 240404 (2013).
  * [41] M. Epping, H. Kampermann, D. Bruß, “Optimization of Bell inequalities with invariant Tsirelson bound,” J. Phys. A 47, 424015 (2014).
  * [42] A Frieze, R Kannan, “Quick approximation to matrices and applications,” Combinatorica 19, 175–220 (1997).
  * [43] C. Borgs, J. T. Chayes, L. Lovász, V. T. Sós, K. Vesztergombi, “Convergent sequences of dense graphs. I. Subgraph frequencies, metric properties and testing,” Adv. Math. 219, 1801–1851 (2008).
  * [44] N. Alon and A. Naor, “Approximating the cut-norm via Grothendieck’s inequality,” In Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, 2004.
  * [45] P. Diviánszky, https://github.com/divipp/l2-norm (2022).
  * [46] N.J.A. Sloane, http://neilsloane.com/grass/.