# Graph-theoretic approach to Bell experiments with low detection efficiency

Zhen-Peng Xu  School of Physics and Optoelectronics Engineering, Anhui
University, 230601 Hefei, People’s Republic of China  Naturwissenschaftlich-
Technische Fakultät, Universität Siegen, Walter-Flex-Straße 3, 57068 Siegen,
Germany  Jonathan Steinberg  Naturwissenschaftlich-Technische Fakultät,
Universität Siegen, Walter-Flex-Straße 3, 57068 Siegen, Germany  Jaskaran
Singh  Departamento de Física Aplicada II, Universidad de Sevilla, E-41012
Sevilla, Spain  Antonio J. López-Tarrida  Departamento de Física Aplicada II,
Universidad de Sevilla, E-41012 Sevilla, Spain  José R. Portillo  Departamento
de Matemática Aplicada I, Universidad de Sevilla, E-41012 Sevilla, Spain
Instituto Universitario de Investigación de Matemáticas Antonio de Castro
Brzezicki, Universidad de Sevilla, E-41012 Sevilla, Spain  Adán Cabello
<EMAIL_ADDRESS>Departamento de Física Aplicada II, Universidad de Sevilla, E-41012
Sevilla, Spain  Instituto Carlos I de Física Teórica y Computacional,
Universidad de Sevilla, E-41012 Sevilla, Spain

###### Abstract

Bell inequality tests where the detection efficiency is below a certain
threshold $\eta_{\rm{crit}}$ can be simulated with local hidden-variable
models. Here, we introduce a method to identify Bell tests requiring low
$\eta_{\rm{crit}}$ and relatively low dimension $d$ of the local quantum
systems. The method has two steps. First, we show a family of bipartite Bell
inequalities for which, for correlations produced by maximally entangled
states, $\eta_{\rm{crit}}$ can be upper bounded by a function of some
invariants of graphs, and use it to identify correlations that require small
$\eta_{\rm{crit}}$. We present examples in which, for maximally entangled
states, $\eta_{\rm{crit}}\leq 0.516$ for $d=16$, $\eta_{\rm{crit}}\leq 0.407$
for $d=28$, and $\eta_{\rm{crit}}\leq 0.326$ for $d=32$. We also show evidence
that the upper bound for $\eta_{\rm{crit}}$ can be lowered down to $0.415$ for
$d=16$ and present a method to make the upper bound of $\eta_{\rm{crit}}$
arbitrarily small by increasing the dimension and the number of settings. All
these upper bounds for $\eta_{\rm{crit}}$ are valid (as it is the case in the
literature) assuming no noise. The second step is based on the observation
that, using the initial state and measurement settings identified in the first
step, we can construct Bell inequalities with smaller $\eta_{\rm{crit}}$ and
better noise robustness. For that, we use a modified version of Gilbert’s
algorithm that takes advantage of the automorphisms of the graphs used in the
first step. We illustrate its power by explicitly developing an example in
which $\eta_{\rm{crit}}$ is $12.38\%$ lower and the required visibility is
$14.62\%$ lower than the upper bounds obtained in the first step. The tools
presented here may allow for developing high-dimensional loophole-free Bell
tests and loophole-free Bell nonlocality over long distances.

##  1 Introduction

Bell nonlocality [1, 2], that is, the violation of inequalities satisfied by
any local hidden-variable (LHV) model, called Bell inequalities, is one of the
most fascinating features of quantum mechanics and a crucial mean to
accomplish tasks that are impossible with classical resources.

The detection efficiency $\eta$ in an experimental test of a Bell inequality
is the ratio between the number of systems detected by one party and the
number of pairs emitted by the source. $\eta$ depends not only on the
efficiency of the detectors, but also on all the losses occurring during the
distribution of the state. Pearle [3] and Wigner [4] noticed that experimental
correlations in Bell inequality tests where the detection efficiency is below
a certain threshold $\eta_{\rm{crit}}$ can be simulated by LHV models.
Therefore, if $\eta$ is not high enough, the quantum advantage in many Bell
inequality-based protocols (e.g., for randomness expansion [5, 6, 8, 7] and
secure key distribution [9, 10, 11, 12, 13]) vanishes. Avoiding this so-called
“detection loophole” requires surpassing $\eta_{\rm{crit}}$. However,
$\eta_{\rm{crit}}$ depends on the quantum correlations (i.e., the state
prepared and the measurements performed) and the targeted Bell inequality.

In this work, we identify quantum correlations and Bell inequalities requiring
the smallest $\eta_{\rm{crit}}$ reported, to our knowledge, in the literature
for symmetric Bell tests (i.e., those in which all detectors have the same
detection efficiency). The correlations are produced by maximally entangled
states of experimentally accessible dimensions (e.g., $d=16$) and two-outcome
measurements. In addition, we describe a method that provides arbitrarily
small $\eta_{\rm{crit}}$ but requires higher dimensions.

The importance of these results lies on the fact that they pave the way to
extend the groundbreaking loophole-free Bell tests performed on quantum
systems of dimension $d=2$ (i.e., qubits) and distances between $60$ and
$1300$ m [17, 14, 15, 16] to quantum systems of higher dimensions and longer
distances.

###  1.1 Structure of the paper

In Sec. 2, we collect the smallest values of $\eta_{\rm{crit}}$ reported in
the literature and explain how they have been obtained. We also recall a
standard form of expressing Bell functionals that will be used in several
places.

Finding states, measurements, and Bell inequalities leading to small values of
$\eta_{\rm{crit}}$ is difficult. One of the reasons is that, as we will see,
these values occur for Bell inequalities with many settings for which
computing the local bound is, in general, intractable [18]. Another reason is
the difficulty of, given a Bell inequality, finding the state and measurements
producing maximal quantum violations.

In Sec. 3, we introduce a method that overcomes both problems, as it connects
the local bound of a family of bipartite Bell inequalities to the independence
number of a graph, and quantum realizations that maximally violate the Bell
inequalities to orthogonal representations of the graph. This allows us to
identify examples of quantum correlations and Bell inequalities with
unprecedentedly low $\eta_{\rm{crit}}$.

In Sec. 4, we present a method based on graph theory to obtain explicit states
and measurements making $\eta_{\rm{crit}}$ arbitrarily close to zero.

There are, however, two problems that make the examples obtained up to that
point not useful in practice. One is that, in some cases, they require too
many settings. In Sec. 5, we present a method for searching for examples with
low $\eta_{\rm{crit}}$ and smaller number of settings.

The other problem is that, by construction, the quantum violations of the
graph-based Bell inequalities are very sensitive to noise. In Sec. 6, we
explain why and present a method to address this problem. The method applies
to any of the (highly-symmetric) examples identified with the techniques in
Sec. 3 and produces a Bell inequality for the same correlations (i.e., the
same state and measurements) with smaller $\eta_{\rm{crit}}$ and higher
resistance to noise.

Finally, in Sec. 7, we discuss how the different methods presented in this
work can help us to design loophole-free Bell tests between high-dimensional
quantum systems and achieve loophole-free Bell nonlocality over longer
distances.

##  2 Previous works

###  2.1 Existing values of $\eta_{\rm{crit}}$

For symmetric Bell tests and perfect visibility (as defined later),
$\eta_{\rm{crit}}=0.828$ using maximally entangled states [19] for the
simplest Bell inequality (the one with two dichotomic settings per party): the
Clauser-Horne-Shimony-Holt (CHSH) inequality [20]. Eberhard [21] noticed that
$\eta_{\rm{crit}}$ can be further reduced using nonmaximally entangled states
and, in particular, that it can be lowered down to $0.667$ for the Clauser-
Horne (CH) inequality [22].

For Bell inequalities with four settings and maximally entangled states,
$\eta_{\rm{crit}}$ is not better than for CHSH (with one exception that allows
a slightly lower value; $\eta_{\rm{crit}}=0.821$) [23, 24].

Although loophole-free Bell tests [17, 14, 15, 16] have proven that it is
possible to produce correlations between local quantum systems of dimension
$d=2$ that do not admit LHV models, the value of $\eta_{\rm{crit}}$ required
in these experiments ($\geq 0.720$ due to the noise) prevents real-life
applications and, in particular, applications outside laboratories with well
controlled losses, or involving longer distances (e.g., $>5$ km). It is in
this sense that the requirement of $\eta_{\rm{crit}}>0.667$ (without noise,
$\eta_{\rm{crit}}>0.720$ with noise) acts as a bottleneck that blocks many
real-life applications.

Massar [25] discovered that high-dimensional systems can tolerate a detection
efficiency that decreases with the dimension $d$ of the local quantum system.
However, he only found an improvement over the qubit case for $d>1600$.
Vértesi, Pironio, and Brunner [26] lowered $\eta_{\rm{crit}}$ down to $0.770$
for maximally entangled states and to $0.618$ for nonmaximally entangled
states using $d=4$.

Márton, Bene, and Vértesi [27] have studied the case of $N$ copies of the two-
qubit maximally entangled state and local Pauli measurements which act in the
corresponding qubit subsystems. They obtained the following upper bounds for
$\eta_{\rm{crit}}$: $0.809$ for $N=2$ (which is equivalent to $d=4$), $0.740$
for $N=3$ (which is equivalent to $d=8$), and $0.693$ for $N=4$ (which is
equivalent to $d=16$). More recently, Miklin et al. have reported a method
that allows us to reduce $\eta_{\rm{crit}}$ down to $\approx 0.469$ for
$d=512$ [28].

In this article, we focus on the case of two parties and symmetric detection
efficiency, since we see it as the closest one for realistic applications.
However, it should be mentioned that another way of obtaining low
$\eta_{\rm{crit}}$ is by considering Bell experiments involving $\geq 3$
spatially separated parties [29, 30, 31]. Still, the difficulty for preparing
and distributing the required states makes the resulting values
$\eta_{\rm{crit}}$ unpractical for actual applications. In addition, it should
also be pointed out that $\eta_{\rm{crit}}$ can be reduced for some detectors
at the expense of requiring $\eta_{\rm{crit}}\approx 1$ for other detectors
[32, 33, 34, 35].

###  2.2 Calculating $\eta_{\rm{crit}}$

Here, we summarize the different ways for calculating $\eta_{\rm{crit}}$ that
can be found in the literature for the case that the propagation losses and
detection inefficiencies are the same for all the detectors. For a more
detailed discussion, see Ref. [36].

In an ideal Bell test, every run would end up with the two particles emitted
by the source being detected, one at one party’s site and the other at the
other party’s. However, in a real Bell test this may not be the case. As
pointed out before, reasons for that are the existence of propagation losses
and the imperfection of the detectors. Consequently, a detection at one site
may not be accompanied with a detection at the other site and also, in some
runs, both particles may be undetected.

In some cases, in addition to the local losses and imperfect detectors, the
particles are not emitted at well-known times, then the number of emitted
pairs, and thus the number of runs of the Bell test, will be unknown.

Below we summarize how $\eta_{\rm{crit}}$ can be calculated in each case.

Case I. The number of runs is known. This is the case in event-ready
experiments [37, 17, 16] and in the proposals [38, 39, 40, 41] and experiments
[42] with heralded detection.

Case I. Strategy I. We can associate the no-detection with a new outcome of
the measurement and find a new Bell inequality with the same number of
settings but one more outcome per setting than in the original Bell
inequality. Then, the experiment will be free of the detection loophole as
soon as the new inequality is violated. The problem is that finding this new
Bell inequality may be difficult.

For example, if we add a new outcome to all the measurements in the $(2,m,2)$
Bell scenario (i.e., the one with $2$ parties, $m$ settings per party, and $2$
outcomes), then we end up in the $(2,m,3)$ Bell scenario. Then, the number of
deterministic LHV assignments changes from $2^{2m}$ to $3^{2m}$. Meanwhile,
the dimension of the LHV assignments changes from $2m+m^{2}$ to $4m+4m^{2}$.
To make clear the difficulties that finding such Bell inequalities involve,
notice that, so far, we do not know the Bell inequalities for any $(2,m,3)$
Bell scenario.

Case I. Strategy II. We can associate the no-detection with one of the
outcomes of each measurement and use the original Bell inequality. Then, the
experiment will be loophole-free as soon as the original Bell inequality is
violated.

To obtain $\eta_{\rm crit}$ in this case, we can act as follows. In an ideal
Bell test in which we could achieve the maximum quantum value $Q$ of a Bell
expression $I$ whose bound for LHV models is $C$, and in which the
experimental detection efficiency is $\eta$, the experimental value of $I$
would be

$I_{\rm exp}=\eta^{2}Q+\eta(1-\eta)(Q_{A}+Q_{B})+(1-\eta)^{2}X,$ (1)

where $Q_{A}$ is the value of $I$ resulting of what the parties output when
Alice has detected the particle but not Bob (and similarly $Q_{B}$), and $X$
is the value that the parties output when both Alice and Bob have not detected
the particles. Usually, the outputs are chosen such that $X=C$. The critical
detection efficiency using this strategy is

$\eta_{\rm crit}=\frac{2C-Q_{A}-Q_{B}}{C+Q-Q_{A}-Q_{B}}.$ (2)

This is the strategy used to obtain all the values previously reported except
the ones in [21, 26]. This will also be the strategy used in this paper.

Case II. The number of runs is not known. This is the case in existing
photonic Bell tests with high detection efficiency [43, 44, 45, 46, 47, 48,
49, 50, 51, 52, 53, 54].

Case II. Strategy III. This strategy works for the CH Bell inequality [22],
for inequalities that can be written in terms of the CH functional [26], and
for some Bell inequalities that can be rewritten similarly [55]. The CH
functional has a peculiarity that makes it useful. It only contains joint and
marginal probabilities of one of the outcomes. Then, there is no need to
modify the bound for LHV models when $\eta$ is not $1$. Instead, a lower
$\eta$ makes that the probabilities become lower so that the value of the Bell
expression decreases. The joint probabilities decrease faster than the
marginal probabilities. This strategy uses the expected values of $\eta$ and
the noise for choosing the nonmaximally entangled state that maximizes the
violation [21].

This is the strategy used in [21, 26] and adopted in the photonic loophole-
free Bell tests [14, 15].

Case II. Other strategies. These strategies compute $\eta_{\rm crit}$ under
extra assumptions on the distribution of nondetections. See, e.g., [19]. We do
not enter into details here, as the need of extra assumptions is considered a
weak point [56, 36].

###  2.3 Collins-Gisin parametrization

Following the idea introduced in Ref. [57], we will sometimes use a matrix to
specify the functional $I$ associated to a Bell inequality $I\leq C$ (where
$C$ is the bound for LHV models) as

$\displaystyle I=$ (3)
$\displaystyle\left(\begin{tabular}[]{c|ccc}&$c(\Pi_{1}^{A}\\!=\\!1)$&\ldots&$c(\Pi_{m}^{A}\\!=\\!1)$\\\
\hline\cr$c(\Pi_{1}^{B}\\!=\\!1)$&$c(\Pi_{1}^{A}\\!=\\!\Pi_{1}^{B}\\!=1)$&$\dots$&$c(\Pi_{m}^{A}\\!=\\!\Pi_{1}^{B}\\!=\\!1)$\\\
$\vdots$&$\vdots$&$\ddots$&$\vdots$\\\
$c(\Pi_{m}^{B}\\!=\\!1)$&$c(\Pi_{1}^{A}\\!=\\!\Pi_{m}^{B}\\!=\\!1)$&$\dots$&$c(\Pi_{m}^{A}\\!=\\!\Pi_{m}^{B}\\!=\\!1)$\\\
\end{tabular}\right),$

where the entries are coefficients for different terms that appear in $I$,
which is assumed to contain only two-outcome ($0$ and $1$) measurements. As an
example, $c(\Pi_{1}^{A}=1)$ indicates the coefficient that multiplies
$P(\Pi_{1}^{A}=1)$ and $c(\Pi_{1}^{A}=\Pi_{1}^{B}=1)$ the coefficient that
multiplies $P(\Pi_{1}^{A}=\Pi_{1}^{B}=1)$.

This technique allows us to write any Bell functional (even those with
measurements with more than two outcomes) as a linear combination of joint and
marginal probabilities, but without including one of the outcomes of each
measurement. The coefficients of the probabilities involving this outcome can
be computed from the normalization and no-signalling conditions.

##  3 Graph-theoretic approach to Bell nonlocality with low detection
efficiency

###  3.1 General results

Here, we first introduce a family of bipartite Bell inequalities, in which
each inequality is associated to a graph $G$, such that the number of settings
of each party coincides with the number of vertices of $G$ and the number of
outcomes is two. The first interesting point about this family is that the LHV
bound of each inequality coincides with the independence number of $G$.
Therefore, we can take advantage of the vast literature on independence
numbers of countless families of graphs to write Bell inequalities whose local
bounds would be difficult to compute otherwise.

######  Definition 1 (Independent set).

An independent set [58] of a graph $G$ is a subset of vertices where any two
vertices are nonadjacent.

Hereafter, $u\sim v$ will indicate that $u$ and $v$ are adjacent.

######  Definition 2 (Independence number).

The independence number [58] of a graph $G$, denoted by $\alpha$, is the
largest cardinality of any independent set of $G$.

######  Definition 3 (Xi number).

The xi number of a graph $G$ is

$\displaystyle\Xi=\min_{S\in\mathcal{S}_{\alpha+1}}\Xi(S),$ (4)

where $\mathcal{S}_{\alpha+1}$ is the set of all subsets of $(\alpha+1)$
vertices of $G$, where $\alpha$ is the independence number of $G$, and

$\displaystyle\Xi(S):=\max_{v\in S}\left|\\{u|u\sim v,u\in S\\}\right|.$ (5)

For example, $\Xi=2$ for the circulant graph $Ci_{10}(2,3)$, i.e., the
$10$-vertex graph in which vertex $i$ is adjacent to vertices $i+2$ and $i+3$.

######  Definition 4 (Circulant graph).

A graph with vertices $1,\ldots,|V|$ is circulant if the cyclic permutation
$(1,\ldots,|V|)$ is a graph automorphism.

######  Definition 5 (Graph automorphism).

An automorphism of a graph $G$ is a permutation $\sigma$ of the vertex set of
$G$, such that the pair of vertices $(i,j)$ is adjacent (i.e., forms an edge)
if and only if the pair $(\sigma(i),\sigma(j))$ is adjacent.

By definition, if $S_{1}\subseteq S_{2}$, then

$\displaystyle\Xi(S_{1})\leq\Xi(S_{2}).$ (6)

This implies that, if $S$ contains no fewer than $(\alpha+1)$ vertices, then

$\displaystyle\Xi(S)\geq\Xi.$ (7)

In addition, $\Xi\geq 1$, since there is at least one edge among any set of
$(\alpha+1)$ vertices, given that $\alpha$ is the independence number.

######  Theorem 1.

Given a graph $G$ with vertex set $V$, edge set $E$, independence number
$\alpha$, and xi number $\Xi$, the following is a Bell inequality:

$\displaystyle I$ $\displaystyle=\sum_{i\in V}P(\Pi^{A}_{i}=\Pi^{B}_{i}=1)-$
$\displaystyle\ \ \sum_{(i,j)\in
E}\\!\frac{1}{2\Xi}\\!\left[P(\Pi^{A}_{i}\\!=\\!\Pi^{B}_{j}\\!=\\!1)\\!+\\!P(\Pi^{A}_{j}\\!=\\!\Pi^{B}_{i}\\!=\\!1)\right]$
$\displaystyle\overset{\rm LHV}{\leq}\alpha,$ (8)

where $P(\Pi^{A}_{i}=\Pi^{B}_{j}=1)$ is the probability that Alice obtains the
outcome $1$ and Bob obtains the outcome $1$ when Alice measures the observable
$\Pi^{A}_{i}$ (with possible outcomes $0$ and $1$) and Bob measures the
observable $\Pi^{B}_{j}$ (with possible outcomes $0$ and $1$).

###### Proof.

To obtain the upper bound of $I$ for LHV models, we only need to consider
deterministic probability assignments. From the definition of $I$, it is easy
to see that the bound cannot be less than $\alpha$. Therefore, the bound can
only be obtained when the events $[\Pi^{A}_{i}=\Pi^{B}_{i}=1]$ have been
assigned the value $1$ for any $i\in S$, where $S$ contains no fewer than
$\alpha$ vertices.

Let us assume that $S$ contains no fewer than $\alpha+1$ vertices and let us
call $v$ the vertex in $S$ such that

$\left|\\{u|u\sim v,u\in S\\}\right|=\Xi(S).$ (9)

By changing the assignment of the event $[\Pi^{A}_{v}=\Pi^{B}_{v}=1]$ to be
$0$, the increment of $I$ is $-1+\frac{\Xi(S)}{\Xi}$. This is because $\forall
i,j\in S$,

$\displaystyle P(\Pi^{A}_{i}=\Pi^{B}_{j}=1)=P(\Pi^{A}_{j}=\Pi^{B}_{i}=1)=1$
(10)

with our current assignment, especially for $i=v$ or $j=v$.

Therefore, in the case that $S$ contains no fewer than $(\alpha+1)$ vertices,
we can always set the assignment of one event $[\Pi^{A}_{v}=\Pi^{B}_{v}=1]$ to
be $0$, such that the value of $I$ does not decrease. This implies that the
upper bound can be obtained in the case that $S$ contains exactly $\alpha$
vertices, which implies that the upper bound can be no more than $\alpha$.
Consequently, the upper bound for LHV models is exactly $\alpha$. ∎

There is a second reason why the Bell inequalities (1) are interesting for us.
The reason is that they allow us to establish a one-to-one connection between
a quantum value for $I$ and another graph invariant of $G$. Moreover, this
connection also gives us the initial state and the local observables that
provide the quantum value for $I$.

######  Definition 6 (Orthonormal representation).

An orthonormal representation in $\mathbb{C}^{d}$ of a graph $G$ with vertex
set $V$ is an assignment of a nonzero unit vector
$|v_{i}\rangle\in\mathbb{C}^{d}$ to each $i\in V$ satisfying that $\langle
v_{i}|v_{j}\rangle=0$ for all pairs $i,j$ of adjacent vertices. Such an
assignment does not require that different vertices are assigned different
vectors, nor that nonadjacent vertices correspond to nonorthogonal vectors.

An additional unit vector $|\psi\rangle\in\mathbb{C}^{d}$, called handle, is
sometimes specified together with the orthonormal representation.

Notice that in many works in graph theory the usual definition of orthonormal
representation assigns orthogonal vectors to nonadjacent —instead of adjacent—
vertices.

######  Definition 7 (Orthogonal rank).

The orthogonal rank [59] of a graph $G$, denoted $\xi$, is the smallest
positive integer $d$ for which there is an orthonormal representation in
$\mathbb{C}^{d}$ of $G$.

Quantum pure states are represented by rays. Therefore, $\xi$ is also the
minimum dimension a quantum system must have so adjacent vertices in $G$ can
be assigned orthogonal quantum states (or orthogonal rank-one projectors).
However, it can be the case that the same ray is assigned to different
vertices.

######  Definition 8 (Graph of orthogonality).

Given a set of vectors $S$, the graph of orthogonality of $S$ is the graph in
which each vector is represented by a vertex and two vertices are adjacent if
and only if their corresponding vectors are mutually orthogonal.

######  Theorem 2.

For any graph $G$, the maximum quantum value of $I$, defined in Eq. (1), is

$Q\geq\frac{|V|}{\xi},$ (11)

where $|V|$ is the number of vertices of $G$ and $\xi$ is the orthogonal rank
of $G$. The value $I=\frac{|V|}{\xi}$ is achieved by preparing the maximally
entangled state

$|\psi\rangle=\frac{1}{\sqrt{\xi}}\sum_{j=0}^{\xi-1}|j\rangle|j\rangle$ (12)

and using as local settings on Alice’s side the observables represented by the
projectors $|v_{i}\rangle\langle v_{i}|\otimes\mathbbm{1}$, with
$|v_{i}\rangle$ in an orthonormal representation of dimension $\xi$ of $G$,
and as local settings on Bob’s side the observables represented by the
projectors $\mathbbm{1}\otimes|v_{i}^{\ast}\rangle\langle v_{i}^{\ast}|$,
where $|v_{i}^{\ast}\rangle$ is the complex conjugate of $|v_{i}\rangle$.

###### Proof.

By definition of $\xi$, the value $I=\frac{|V|}{\xi}$, can be achieved in
quantum mechanics using the maximally entangled state (12) and locally
measuring the rank-one projectors corresponding to an orthonormal
representation of dimension $\xi$ of $G$ in Alice’s side and its complex
conjugate in Bob’s side. ∎

Theorems 1 and 2 allow us to link an upper bound of the critical detection
efficiency $\eta_{\rm crit}$ for the quantum violation of the Bell inequality
(1) produced with maximally entangled states with invariants of the graph that
originates the Bell inequality.

######  Theorem 3.

For any Bell inequality of the form (1) associated to a graph $G$, assuming
that the number of runs of the Bell test is known (i.e., that we are in Case I
in Sec. 2.2) and that the parties adopt Strategy II (described in Sec. 2.2),
local models simulating the correlations produced by the state (12) and the
measurements described after Eq. (12) are impossible if the detection
efficiency is

$\eta>\sqrt{\frac{\alpha}{|V|/\xi}}\geq\eta_{\rm crit},$ (13)

where $\alpha$, $|V|$, and $\xi$ are the independence number, the number of
vertices, and the orthogonal rank of $G$, respectively.

###### Proof.

Recall that the Collins-Gisin parametrization allows us to write any Bell
expression as a linear combination of joint and marginal probabilities,
without including one of the outcomes of each measurement. Then, a strategy in
case of no detection is to associate the no-detection with the outcome $0$,
which is assumed to be the one that does not appear explicitly in the Bell
expression. Following this strategy, the probabilities in the Bell expression
transforms as follows:

$\displaystyle P(\Pi^{A}_{i}=1)\to\eta P(\Pi^{A}_{i}=1),$ (14) $\displaystyle
P(\Pi^{B}_{j}=1)\to\eta P(\Pi^{B}_{j}=1),$ (15) $\displaystyle
P(\Pi^{A}_{i}=\Pi^{B}_{j}=1)\to\eta^{2}P(\Pi^{A}_{i}=\Pi^{B}_{j}=1).$ (16)

If the Bell expression contains no marginal items, as it is the case in the
Bell functional in (1), then, in Eq. (2), $Q_{A}=Q_{B}=0$. If no detection is
associated to the outcome $0$, then $X=0$. Consequently, the quantum value in
the ideal case becomes $\eta^{2}Q$. Then, in this case,

$\eta_{\rm crit}=\sqrt{\frac{C}{Q}},$ (17)

where $C$ is the upper bound of $I$ for LHV models. Then, using Theorems 1 and
2, we obtain Eq. (13). ∎

###  3.2 Examples of nonlocal correlations with low $\eta_{\rm crit}$

Here, we use Theorem 3 to identify quantum correlations and Bell inequalities
with low $\eta_{\rm crit}$.

####  3.2.1 Definitions

######  Definition 9 (Pauli observables).

The set $P_{n}$ of Pauli observables for a system of $n\geq 2$ qubits consists
of the nontrivial quantum observables represented by $n$-term tensor products
of the Pauli matrices $\sigma_{x}$, $\sigma_{y}$, $\sigma_{z}$, and $I$ (the
$2\times 2$ identity matrix).

The cardinality of $P_{n}$ is $|P_{n}|=4^{n}-1$, since $P_{n}$ does not
contain the $2^{n}\times 2^{n}$ identity matrix.

######  Definition 10 (Pauli states).

The set ${\cal P}_{n}(\mathbb{C})$ of Pauli states for a system of $n\geq 2$
qubits consists of the common eigenstates of all the maximal subsets of
$P_{n}$ containing only mutually compatible observables (i.e., represented by
mutually commuting matrices) of maximal size.

The Pauli states are also called the “quantum states arising from the Pauli
group” [64]. The eigenvectors of each subset of maximal size of $P_{n}$
containing only mutually compatible observables provide an unique orthogonal
basis of vectors with $d=2^{n}$ vectors. There are
$L=\prod_{j=1}^{n}(2^{j}+1)$ such subsets, and ${\cal P}_{n}(\mathbb{C})$ is
the union of the $L$ disjoint orthogonal bases. Accordingly, $|{\cal
P}_{n}(\mathbb{C})|=Ld$.

Hereafter, we denote by ${\cal P}_{n}(\mathbb{R})$ the subset of ${\cal
P}_{n}(\mathbb{C})$ represented by vectors with all components in
$\mathbb{R}$. $|{\cal P}_{n}(\mathbb{R})|=\prod_{j=1}^{n}(2^{j}+2)$.

######  Definition 11 (Newman states).

The set ${\cal N}_{d}$ of Newman states for a quantum system of dimension $d$,
where $d=4k,k\in\mathbb{N}$, consists of the states represented by
$d$-dimensional rays with components $-1$ and $1$ and such that the number of
$-1$ components is even.

For example, ${\cal N}_{4}=\\{(1,1,1,1)$, $(1,1,-1,-1)$, $(1,-1,1,-1)$,
$(1,-1,-1,1)\\}$. We remark that $(a,b,c,d)$ and $-1\times(a,b,c,d)$ represent
the same state. As it can be seen, $|{\cal N}_{d}|=2^{d-2}$.

######  Definition 12 (Newman graphs).

The Newman graph $Y_{d}$ is the graph of orthogonality of ${\cal N}_{d}$,
where $d=4k,k\in\mathbb{N}$.

The name follows from a family of graphs studied by Newman (see Sec. 6.6 of
[65]).

######  Definition 13 (Lovász’s number).

The Lovász number of a graph $G$ is [60, 61]

$\vartheta(G):=\max\sum_{i\in V}|\langle\psi|v_{i}\rangle|^{2},$ (18)

where the maximum is taken over all orthonormal representations
$\\{|v_{i}\rangle\\}_{i\in V}$ of $G$ and handles $|\psi\rangle$ (i.e.,
normalized vectors) in any dimension.

By the definition of $\vartheta(G)$, there is a quantum realization that
achieves $I=\vartheta(G)$ for the $I$ associated to $G$ using Eq. (1).

######  Definition 14 (Fractional packing number).

The fractional packing number of a graph $G$ [60, 61, 62] is

$\alpha^{\ast}(G):=\max\sum_{i\in V}p_{i},$ (19)

where the maximum is taken over all $p_{i}\geq 0$ and for all cliques $C$ of
$G$, under the restriction $\sum_{i\in C}p_{i}\leq 1$.

It will be useful that $\vartheta(G)\leq\alpha^{\ast}(G)$.

######  Definition 15 (Hadamard or orthogonality graphs Omega).

For $n\in\mathbb{N}$, an orthogonality graph $\Omega_{n}=(V,E)$ is the graph
with vertex set $V=\\{-1,1\\}^{n}$ and edge set $E=\\{(u,v)\in V\times
V:\langle u,v\rangle=0\\}$. That is, each vertex is assigned a $\pm 1$-vector
of length $n$, and two vertices are adjacent if and only if the corresponding
vectors are orthogonal.

Geometrically, the vectors assigned to the vertices of the Hadamard graph
$\Omega_{n}$ correspond to the directions of the vertices of an
$n$-dimensional hypercube centered at the origin. Newman states may be seen as
a subset of such hypercube directions. Therefore, a Newman graph $Y_{n}$ is an
induced subgraph of an orthogonality graph $\Omega_{n}$.

######  Definition 16 (Induced subgraph).

Given a graph $G$ with vertex set $V$ and edge set $E$, and a subset of
vertices $S\subset V$, the subgraph of $G$ induced by $S$ is the graph with
vertex set $S$, and edge set consisting of all the edges $(u,v)\in E$ such
that $u,v\in S$ [58].

######  Definition 17 (Hadamard matrix).

A Hadamard matrix of order $n$ is a real $n\times n$ square matrix $H_{n}$ in
which all its entries are either $+1$ or $-1$, and whose rows are mutually
orthogonal.

The order $n$ of a Hadamard matrix must be $1$, $2$, or a multiple of $4$.
Therefore, if $n$ is an even number, each pair of rows in a Hadamard matrix
represents two mutually orthogonal $\pm 1$-vectors in dimension $n$. The same
is true for its columns considered as $\pm 1$-vectors. Therefore, taking any
pair of rows (alternatively, columns), the number of matching entries must be
equal to the number of mismatching entries, exactly $n/2$.

######  Definition 18 (Lexicographic product of graphs).

The lexicographic product of two graphs $G$ and $H$ with respective vertex
sets $V(G)=\\{u_{i}\\}_{i}$ and $V(H)=\\{v_{k}\\}_{k}$ is a graph $G[H]$ such
that its vertex set is the Cartesian product $V(G[H])=V(G)\times V(H)$, and
any two vertices $(u_{i},v_{k})$ and $(u_{j},v_{l})$ in $G[H]$ are adjacent if
and only if either $u_{i}$ is adjacent with $u_{j}$ in $G$ or $u_{i}=u_{j}$
and $v_{k}$ is adjacent with $v_{l}$ in $H$.

The lexicographic product is associative but not commutative (a fact
emphasized by the notation).

####  3.2.2 Pauli-4320

The graph of orthogonality of ${\cal P}_{4}(\mathbb{R})$ has $\alpha=72$ and
$\vartheta=\alpha^{\ast}=\frac{|V|}{\xi}=270$. Therefore, by preparing the
maximally entangled state (12) of local dimension $\xi=2^{4}=16$ and allowing
the parties to choose between the $4320$ two-outcome measurements represented
by $|v_{i}\rangle\langle v_{i}|$, with $|v_{i}\rangle\in{\cal
P}_{4}(\mathbb{R})$, they produce a violation of the Bell inequality (1)
which, using Theorem 3, allows us to conclude that

$\eta_{\rm crit}^{{\cal P}_{4}(\mathbb{R})}\leq 0.516,$ (20)

which is an unprecedentedly low upper bound for this dimension (see Sec. 2.1).

Notice that $4320$ local choices are not too many for a realistic Bell test.
For example, a photonic loophole-free Bell test may have $3502784150$ trials
[14], which is enough for a Bell test in which each party has to chose between
$4320$ settings, as it gives $187.7$ trials for each possible combination of
settings $(x,y)$, which is more than three times the number of trials per
$(x,y)$ in the first loophole-free Bell test [17]. Recall that all
measurements have two outcomes, as in the test of the Clauser-Horne-Shimony-
Holt Bell inequality [20]. Therefore, only two detectors per party are
necessary.

####  3.2.3 Pauli-36720

We conjecture that the graph of orthogonality of ${\cal P}_{4}(\mathbb{C})$
has $\alpha=396$. This conjecture is based on the fact that, after months of
computations, $396$ is the largest value that we have found (and we have found
it many times, which suggests that our search is sufficiently dense). The
computation is based on a greedy-type algorithm taking into account the
symmetry of the graph as well as known upper bounds for the independence
number by means of spectral graph theory. Given a graph $G$, we proceed as
follows. $(i)$ Compute the automorphism group of $G$ and the corresponding
orbits. These orbits will yield a partition of the vertex set
$\\{1,\ldots,|V(G)|\\}$. $(ii)$ From each orbit $O_{k}$ we select a vertex
$v^{k}\in O_{k}$. This vertex then has two options: It can either be part of a
maximal independent vertex set or it is not, i.e., $v^{k}\in\mathcal{I}(G)$ or
$v^{k}\notin\mathcal{I}(G)$. If $v^{k}\in\mathcal{I}$, then remove $v^{k}$ and
all neighbours of $v^{k}$. This produces a tuple $(G^{1},1)$ containing a new
graph ${G}^{1}$ and $1$, as we have removed a vertex from the independent set
of the original graph. On the other hand, if $v^{k}\notin\mathcal{I}(G)$, we
can remove the whole orbit $O_{k}$ of $G$ with $v^{k}\in O_{k}$ what yields
another graph $G^{2}$. As we have not removed a member of $\mathcal{I}$, we
store the tuple $(G^{2},0)$. In total, this produces a sequence of graphs with
a strictly decreasing number of vertices. Once the size of all graphs is lower
than a threshold $\kappa$ for which $\alpha$ can be computed directly, the
decomposition stops yielding a set $\\{(G^{k},H^{k})\\}$, where
$H^{k}\in\\{(0,1)^{n}\\}$ denotes the choice in each step. The independence
number of $G$ is given by the maximum over
$\tilde{\alpha}_{k}=\alpha(G_{k})+\sum_{j}(H^{k})_{j}$. However, the problem
with this approach is (revealing the hardness of the problem of computing
$\alpha$) that the number of graphs in the decomposition grows exponentially.
If one has a sufficiently high lower bound for $\alpha(G)$ given a priori, one
only needs to collect those graphs appearing in the decomposition process
whose independence number is larger than this a priori bound.

In addition, $\vartheta=\alpha^{\ast}=\frac{|V|}{\xi}=2295$. Therefore, if the
above conjecture is correct, then, by preparing the maximally entangled state
(12) of local dimension $\xi=2^{4}=16$ and allowing the parties to choose
between the $36720$ two-outcome measurements represented by
$|v_{i}\rangle\langle v_{i}|$, with $|v_{i}\rangle\in{\cal
P}_{4}(\mathbb{C})$, they can produce a violation of the Bell inequality (1)
which, using Theorem 3, allows us to conclude that

$\eta_{\rm crit}^{{\cal P}_{4}(\mathbb{C})}\leq 0.415.$ (21)

####  3.2.4 Newman-$2^{26}$

As it is proven in Sec. 3.2.6, the graph of orthogonality of ${\cal N}_{28}$
has $\alpha=397594$ and
$\vartheta=\alpha^{\ast}=\frac{|V|}{\xi}=\frac{16777216}{7}\approx
2.3967\times 10^{6}$. Therefore, by preparing the maximally entangled state
(12) of local dimension $\xi=28$ and allowing the parties to choose between
the $2^{26}$ two-outcome measurements represented by $|v_{i}\rangle\langle
v_{i}|$, with $|v_{i}\rangle\in{\cal N}_{28}$, they can produce a violation of
the Bell inequality (1) which, using Theorem 3, allows us to conclude that

$\eta_{\rm crit}^{{\cal N}_{28}}\leq 0.407.$ (22)

Arguably, $2^{26}$ two-outcome measurements are too many for a real Bell test.
The aim of this and the next example is to show that, by digging in the
literature, one can find sets of vectors (or graphs), leading to gedanken Bell
tests with very low $\eta_{\rm crit}$.

####  3.2.5 Newman-$2^{30}$

As it is proven in Sec. 3.2.6, the graph of orthogonality of ${\cal N}_{32}$
has $\alpha=3572224$ and $\vartheta=\alpha^{\ast}=\frac{|V|}{\xi}=2^{25}$.
Therefore, by preparing the maximally entangled state (12) of local dimension
$\xi=32$ and allowing the parties to choose between the $2^{30}$ two-outcome
measurements represented by $|v_{i}\rangle\langle v_{i}|$, with
$|v_{i}\rangle\in{\cal N}_{32}$, they produce a violation of the Bell
inequality (1) which, using Theorem 3, allows us to conclude that

$\eta_{\rm crit}^{{\cal N}_{32}}\leq 0.326.$ (23)

####  3.2.6 Independence number and quantum value for the Newman graphs

The independence number of the Newman graph $Y_{n}$ can be obtained by
exploiting a connection [65] between $Y_{n}$ and the orthogonality graphs
$\Omega_{n}$, also known as Hadamard graphs or Deutch-Jozsa graphs. The graphs
$\Omega_{n}$ were introduced by Ito [70, 71] as a tool to provide an algebraic
graph theoretic background for Hadamard matrices. Hadamard graphs appear in
relation to some quantum communication protocols and some proofs of the
Kochen-Specker theorem [72, 73, 74, 75, 76].

By definition, the graph $Y_{n}$ is a subgraph of $\Omega_{n}$ induced by a
specific subset of its vertices.

For our purposes, the only interesting graphs $\Omega_{n}$ are those for which
$n=4k,k\in\mathbb{N}$. Otherwise, $\Omega_{n}$ is empty for $n$ odd, or
bipartite for $n=2\mod 4$ [65]. Restricting ourselves to such interesting
graphs $\Omega_{n=4k}$, the first observation is that $\Omega_{n}$ is the
disjoint union of two isomorphic graphs,

$\Omega_{n}=\Omega_{n}^{\rm e}\sqcup\Omega_{n}^{\rm o},$ (24)

where $\Omega_{n}^{\rm e}$ is the graph defined by the vertices corresponding
to vectors with an even number of components $1$, and $\Omega_{n}^{\rm o}$ is
the graph defined by the vertices corresponding to vectors with an odd number
of components $1$. Therefore, the independence numbers are related as follows:

$\alpha(\Omega_{n})=\alpha(\Omega_{n}^{\rm e})+\alpha(\Omega_{n}^{\rm
o})=2\alpha(\Omega_{n}^{\rm e})$ (25)

and the orthogonal ranks are related as follows:

$\xi(\Omega_{n})=\xi(\Omega_{n}^{\rm e})=\xi(\Omega_{n}^{\rm o}).$ (26)

The second step is noticing that $\Omega_{n}^{\rm e}$ is the lexicographic
product of $Y_{n}$ with the complement of the complete graph on two vertices,

$\Omega_{n}^{\rm e}=Y_{n}[\bar{K}_{2}].$ (27)

Therefore (see Theorem 5),

$\alpha(\Omega_{n}^{\rm e})=\alpha(Y_{n})\alpha(\bar{K}_{2})=2\alpha(Y_{n})$
(28)

and

$\xi(\Omega_{n}^{\rm e})=\xi(Y_{n}).$ (29)

The orthogonal rank of $\Omega_{n}$ is $n$ [77, 78]. Therefore,

$\xi(Y_{n})=n,$ (30)

and the assignment of $n$-dimensional rays with components $-1$ and $1$ to the
vertices $Y_{n}$ such that adjacent vertices are assigned orthogonal rays
yields an orthogonal representation of $Y_{n}$ of minimum dimension.

On the other hand, $\alpha(\Omega_{n})$ is known for $n=4p^{k}$, for $k\geq 1$
where $p$ is an odd prime [79], and also for $n=2^{k}$ for $k\geq 2$ [80]. In
both cases,

$\alpha(\Omega_{n})=4\sum_{i=0}^{n/4-1}\binom{n-1}{i}.$ (31)

It still remains a conjecture whether Eq. (31) is valid when $n$ is another
multiple of $4$. To our knowledge, the first open case is $n=40$ [80]. Taking
Eqs. (25), (28), and (31) into account,

$\alpha(Y_{28})=397594$ (32)

and

$\alpha(Y_{32})=3572224.$ (33)

In addition, $Y_{n}$ has $|V|=2^{n-2}$ vertices and
$|E|=2^{n-4}\binom{n}{n/2}$ edges.

Let us show that, for the two considered Newman graphs, the orthogonal rank
(i.e., the minimal dimension of the physical realization) equals their clique
number (size of the largest clique).

In order to prove that Newman’s graphs $Y_{28}$ and $Y_{32}$ contain cliques
of size $28$ and $32$, respectively, note that such cliques correspond to sets
of pairwise orthogonal $\pm 1$-rays of cardinality $28$ in dimension $28$, or
cardinality $32$ in dimension $32$, in which the number of $-1$ components is
an even (alternatively, odd) number. This fact allows us to rephrase this
problem in a slightly different and more convenient way, using Hadamard
matrices: our goal is to construct adequate Hadamard matrices $H_{n}$ of
orders $n=28$ and $n=32$. Each row in $H_{n}$ is a $\pm 1$-vector in dimension
$n$ and, by definition, the $n$ rows in $H_{n}$ constitute a set of $n$
pairwise orthogonal $\pm 1$-vectors in dimension $n$. In fact, these vectors
are rays since no two rows can have the same entries with opposite signs, due
to orthogonality. If necessary, we can transform $H_{n}$ into another
equivalent $n\times n$ Hadamard matrix by negating rows or columns, or by
interchanging rows or columns, so that the number of $-1$ components of the
row vectors is an even (alternatively, odd) number. Notice that, in the end,
the resulting set of vectors corresponds to a maximum clique of size $n$ in
the Newman graph $Y_{n}$.

According to Hadamard’s conjecture, a Hadamard matrix $H_{n}$ of order $n=4k$
exists for every positive integer $k$. At the present time, after applying the
construction methods due to Sylvester, Paley, Williamson and others, the
smallest order for which no Hadamard matrix is known is $n=668$. And there are
many orders $n>668$ for which $H_{n}$ is known. This means that all Newman
graphs $\Omega_{n=4k}$ with $n<668$ satisfy that $\omega(Y_{n})=n$.

There is a well known recursive procedure to construct Hadamard matrices
$H_{n}$ of order $n=2^{k},k\in\mathbb{N}$, the so called Sylvester’s
construction [81]. Applying this procedure, $H_{32}$ can be obtained. This
matrix fulfills the condition that the number of $-1$ entries in each row is
an even number, hence providing a clique of size $32$ for the Newman graph
$Y_{32}$.

Specifically, from $H_{32}$, we arrive at the following clique of size $32$:
the set of rays of the form $u_{i}\otimes u_{j}\otimes v_{k}$, where
$u_{i},u_{j}\in\\{(1,1,1,1),(1,1,-1,-1),(1,-1,1,-1)$, $(1,-1,-1,1)\\}$,
$v_{k}\in\\{(1,1),(1,-1)\\}$, and $\otimes$ denotes tensor product.

A Hadamard matrix $H_{28}$ is more convoluted. It can be obtained through the
so-called Paley’s construction (Lemma 2 in Ref. [82]). There are $487$
inequivalent matrices $H_{28}$. Examples of them can be found in the
literature. To exhibit a specific instance of a clique of size $28$ induced in
$Y_{28}$ we look for a matrix $H_{28}$ such that the number of $-1$ entries in
each row is again an even number. Such a matrix (using $0,1$ entries instead
of $\pm 1$) can be found, v.g., in Fig. 1 in Ref. [83]: The set of row vectors
obtained by replacing therein each $0$ entry with $-1$ constitutes the desired
clique.

Finally, we will prove that for Newman graphs $Y_{n}$ with $n=28$ and $n=32$,
the quantum value of $I$ given by Eq. (1) can be
$\alpha^{\ast}(Y_{n})=\vartheta(Y_{n})=\frac{|V(Y_{n})|}{\xi(Y_{n})}$. First,
note that both $\Omega_{n}^{\rm e}$ and $\bar{K}_{2}$ are vertex-transitive.
Given that $\Omega_{n}^{\rm e}=Y_{n}[\bar{K}_{2}]$, we know that $Y_{n}$ is
also vertex-transitive, since the lexicographic product of two graphs is
vertex-transitive if and only if both graph factors are vertex-transitive
[84].

On one hand, it is known [77] that

$\vartheta(\Omega_{n})=\frac{2^{n}}{n}.$ (34)

Since $\vartheta$ is multiplicative in the lexicographic product (see Theorem
5), we have $\vartheta(\Omega^{\rm
e})=\vartheta(Y_{n})\times\vartheta(\bar{K}_{2})=2\,\vartheta(Y_{n})$. Notice
that $\vartheta(\Omega^{\rm e})=\frac{\vartheta(\Omega_{n})}{2}$, because
$\Omega_{n}=\Omega^{\rm e}\sqcup\Omega^{\rm o}$. As a consequence,

$\vartheta(Y_{n})=\frac{\vartheta(\Omega_{n})}{4}=\frac{2^{n-2}}{n}.$ (35)

On the other hand, the fractional packing number in a vertex-transitive graph
$G$ satisfies $\alpha^{\ast}(G)=\frac{|V(G)|}{\omega(G)}$, where $|V(G)|$ is
the number of vertices and $\omega(G)$ is the clique number of $G$. Given that
$|Y_{n}|=2^{n-2}$ and knowing that the clique number for $Y_{28}$ and $Y_{32}$
is $\omega(Y_{28})=28$ and $\omega(Y_{32})=32$ (as proved before), and by
vertex-transitivity, we obtain that the quantum values of $I$ can be

$\alpha^{\ast}(Y_{28})=\vartheta(Y_{28})$ (36)

and

$\alpha^{\ast}(Y_{32})=\vartheta(Y_{32}),$ (37)

respectively.

####  3.2.7 Newman-$2^{26}$ and Newman-$2^{30}$ are state-independent
contextuality sets

######  Definition 19 (SI-C set).

A State-independent contextuality (SI-C) set [85] in dimension $d\geq 3$ is a
set of projectors that produces noncontextual correlations (i.e. that violate
some noncontextualty inequality) for any initial quantum state of dimension
$d$.

SI-C sets play a fundamental role in our method for identifying correlations
with low $\eta_{\rm crit}$, as any SI-C set produces a quantum violation of a
graph-based Bell inequality of the form (1). However, there are sets that are
not SI-C sets and produce a quantum violation of a Bell inequality of the form
(1) [85].

######  Theorem 4.

Newman-$2^{26}$ is a SI-C set in dimension $d=28$ and Newman-$2^{30}$ is a
SI-C set in dimension $d=32$.

In order to prove Theorem 4, we will first state and prove the following
lemma, in which in a mild abuse of notation, we will use $\Omega_{n}^{\rm e}$
and $\Omega_{k}^{\rm o}$ to refer not only to the Hadamard graphs but also to
the sets of vectors constituting their orthogonal representations:

######  Lemma 1.

For $n\geq 3$,

$\sum_{\langle v|\in\Omega_{n}^{\rm e}}|v\rangle\langle v|=\sum_{\langle
v|\in\Omega_{n}^{\rm o}}|v\rangle\langle v|=2^{n-1}\mathbb{I}_{n},$ (38)
$\sum_{\langle v|\in\Omega_{n}^{\rm e}}\langle v|=\sum_{\langle
v|\in\Omega_{n}^{\rm o}}\langle v|=\langle 0|_{n},$ (39)

where $\langle 0|_{n}=(0,\ldots,0)$ and all the vectors $\langle v|$’s are
unnormalized.

###### Proof.

We prove the lemma by induction. It’s straightforward to verify that those
claims hold for $n=3$. Let us assume now that they also hold for $n=k$. Notice
that, by adding an adequate extra component $\pm 1$ to the vectors of
$\Omega_{k}^{\rm e}$ and $\Omega_{k}^{\rm o}$, we obtain orthogonal
representations $\Omega_{k+1}^{\rm e}$ and $\Omega_{k+1}^{\rm o}$, so that

$\displaystyle\Omega_{k+1}^{\rm e}$ $\displaystyle=\\{(\langle u|,1)|\langle
u|\in\Omega_{k}^{\rm e}\\}\cup\\{(\langle u|,-1)|\langle u|\in\Omega_{k}^{\rm
o}\\},$ (40) $\displaystyle\Omega_{k+1}^{\rm o}$ $\displaystyle=\\{(\langle
u|,1)|\langle u|\in\Omega_{k}^{\rm o}\\}\cup\\{(\langle u|,-1)\langle
u|\in\Omega_{k}^{\rm e}\\}.$ (41)

This implies that

$\displaystyle\sum_{\langle v|\in\Omega_{k+1}^{\rm e}}\langle v|$
$\displaystyle=\sum_{\langle u|\in\Omega_{k}^{\rm e}}(\langle
u|,1)+\sum_{\langle u|\in\Omega_{k}^{\rm o}}(\langle u|,-1)$
$\displaystyle=(\langle 0|_{k},2^{k-1})+(\langle 0|_{k},-2^{k-1})$
$\displaystyle=\langle 0|_{k+1},$ (42)

where the last equality holds because $\Omega_{k}^{\rm e}$ and
$\Omega_{k}^{\rm o}$ have same number of elements, i.e., $2^{k-1}$.

On the other hand:

$\displaystyle\sum_{\langle v|\in\Omega_{k+1}^{\rm e}}|v\rangle\langle v|$
$\displaystyle=$ $\displaystyle\sum_{\langle u|\in\Omega_{k}^{\rm
e}}\begin{bmatrix}|u\rangle\langle u|&|u\rangle\\\ \langle
u|&1\end{bmatrix}+\sum_{\langle u|\in\Omega_{k}^{\rm
o}}\begin{bmatrix}|u\rangle\langle u|&-|u\rangle\\\ -\langle
u|&1\end{bmatrix}$ $\displaystyle=$
$\displaystyle\begin{bmatrix}\sum\limits_{\langle u|\in\Omega_{k}^{\rm
e}}|u\rangle\langle u|&|0\rangle_{k}\\\ \langle
0|_{k}&2^{k-1}\end{bmatrix}+\begin{bmatrix}\sum\limits_{\langle
u|\in\Omega_{k}^{\rm o}}|u\rangle\langle u|&|0\rangle_{k}\\\ \langle
0|_{k}&2^{k-1}\end{bmatrix}$ $\displaystyle=$
$\displaystyle\begin{bmatrix}2^{k-1}\mathbb{I}_{k}&|0\rangle_{k}\\\ \langle
0|_{k}&2^{k-1}\end{bmatrix}+\begin{bmatrix}2^{k-1}\mathbb{I}_{k}&|0\rangle_{k}\\\
\langle 0|_{k}&2^{k-1}\end{bmatrix}$ $\displaystyle=$ $\displaystyle
2^{k}\mathbb{I}_{k+1}.$ (43)

Similarly, we can prove $\sum_{\langle v|\in\Omega_{k+1}^{\rm
o}}|v\rangle\langle v|=2^{k}\mathbb{I}_{k+1}$.

Thus, our claims hold for any $n\geq 3$. ∎

Now, Theorem 4 is straightforward:

###### Proof.

Let ${\cal N}_{n}$ be the set of rays constituting an orthonormal
representation for the Newman graph $Y_{n}$. From Lemma 1, and by definition,

$\sum_{\langle v|\in{\cal N}_{n}}|v\rangle\langle v|=\frac{1}{2n}\sum_{\langle
u|\in{\Omega}^{\rm e}_{n}}|u\rangle\langle
u|=\frac{2^{n-2}}{n}\mathbb{I}_{n},$ (44)

where $\langle v|$’s are normalized vectors, $\langle u|$’s are unnormalized.
In the case $2^{n-2}/n>\alpha(Y_{n})$, the set ${\cal N}_{n}$ is a SI-C set.
In particular, this is true for ${\cal N}_{28}$ and ${\cal N}_{32}$, as
claimed. It is also true for ${\cal N}_{n}$ with $n=12$, $16$, $20$, $36$,
$44$, $52$, $64$, $68$, $100$, $108$, $128$, $196$, $256$, $324$, $484$,
$500$, $512$, since these are the values for which Eq. (31) can be proven,
satisfy $\alpha(Y_{n})<|V(Y_{n})|/\omega(Y_{n})$, and are smaller than $668$,
which is the smallest value for which no Hadamard matrix is known. ∎

For these sets of Newman states, $\eta_{\rm crit}$ tends to zero as $n$ grows.
In particular, for $n=512$, $\eta_{\rm crit}<1.6\times 10^{-14}$.

####  3.2.8 Experimental realization

One way of preparing and measuring Pauli and Newman states of dimension $d$ is
by using single photons (or neutrons or atoms or any type of radiation) in a
Reck et al. $d$-input $d$-outcome multiport [66] or in its simplification by
Clements et al. [67]. For state preparation, we may take further advantage
from the fact that any unitary can be achieved no matter in which input the
photon is injected. Therefore, we can use a specific input and remove all the
elements in the paths not used. More interestingly is the possibility of
simultaneously injecting several indistinguishable particles (either bosons or
fermions) in different ports of a multiport interfeometer. This would allow us
to achieve high $d$ using more compact setups. In this case, the problem of
preparing and measuring Pauli and Newman states is still open, but can be
addressed by taking advantage of the criteria for the suppression of certain
output events in particular interferometers [68, 69]. For example, Newman
states seem to be achievable using Sylvester interferometers [69].

##  4 Arbitrarily small detection efficiency

Here we show that, beyond specific examples, there are constructive methods
such that, if there are no restrictions on the number of local settings or the
local dimension of the quantum system, we can identify quantum correlations
and a corresponding Bell inequality with respect to which the critical
detection efficiency (above which no LHV model can be constructed) is as close
to zero as desired.

###  4.1 Definitions

######  Definition 20 (OR product of graphs).

The OR product (aka disjunctive product or conormal product) of two graphs $G$
and $H$ with respective vertex sets $V(G)=\\{u_{i}\\}_{i}$ and
$V(H)=\\{v_{k}\\}_{k}$ is a graph $G\star H$ such that its vertex set is the
Cartesian product $V(G\star H)=V(G)\times V(H)$, and any two vertices
$(u_{i},v_{k})$ and $(u_{j},v_{l})$ in $G\star H$ are adjacent if and only if
$u_{i}$ is adjacent with $u_{j}$ in $G$ or $v_{k}$ is adjacent with $v_{l}$ in
$H$. The OR product is both associative and commutative.

######  Definition 21 (Spanning subgraph).

Given a graph $G$ with vertex set $V(G)$ and edge set $E(G)$, a spanning
subgraph $H$ of $G$ (also known as a factor of $G$) is a subgraph of $G$ such
that $V(G)=V(H)$ [58].

###  4.2 General results

######  Theorem 5.

If $G\circ H$ is the graph obtained either by the OR product or the
lexicographic product of the graphs $G$ and $H$, then $\alpha(G\circ
H)=\alpha(G)\alpha(H)$ and $\vartheta(G\circ H)=\vartheta(G)\vartheta(H)$.

That $\alpha$ and $\vartheta$ are both multiplicative in the OR product is
proven in, e.g., [86] (Sec. 21) and [87] (Lemma 2.9). The same fact with
respect to the lexicographic product is proven in, e.g., [88] and [89].

######  Theorem 6.

For any Bell inequality of the form (1) associated to a graph $G^{n}$,
denoting the OR or lexicographic product of $n$ copies of the graph $G$, local
models are impossible if the detection efficiency is

$\eta>\sqrt{\frac{\alpha^{n}}{(|V|/\xi)^{n}}}\geq\eta_{\rm crit}^{G^{n}},$
(45)

where $\alpha$, $|V|$, and $\xi$ are the independence number, the number of
vertices, and the orthogonal rank of $G$, respectively.

The proof follows from Theorem 3 and Theorem 5 for the case $H=G$. These two
theorems can be combined whenever
$\vartheta(G)=\alpha^{\ast}(G)=\frac{|V(G)|}{\xi(G)}$ and
$\vartheta(H)=\alpha^{\ast}(H)=\frac{|V(H)|}{\xi(H)}$, but not in general.

By definition, $G[H]$ is a spanning subgraph of $G\star H$. More explicitly,
$V(G[H])=V(G\star H)$ and $E(G[H])\subset E(G\star H)$. Therefore, by taking
$G\star H$ and deleting some specific edges, we obtain $G[H]$. This implies
that using the lexicographic product is more convenient, as a smaller number
of edges in the final graph means that the violation of the Bell inequality
(1) is, as we will see, more resistant to noise.

###  4.3 Example: Pauli-$240^{n}$

The graph of orthogonality of ${\cal P}_{3}(\mathbb{R})$ has $\alpha=16$ and
$\vartheta=\alpha^{\ast}=30$. Therefore, by preparing the maximally entangled
state (12) of local dimension $\xi=2^{3}=8$ and allowing each of the parties
to choose between the $240$ two-outcome measurements represented by
$|v_{i}\rangle\langle v_{i}|$, with $|v_{i}\rangle\in{\cal
P}_{3}(\mathbb{R})$, they can produce a violation of the Bell inequality (1)
which, using Theorem 3, allows us to conclude that $\eta_{\rm crit}\leq
0.730$.

Therefore, with a system of local dimension $8^{2}$, and locally measuring the
observables associated to the vertices of the lexicographic product of ${\cal
P}_{3}(\mathbb{R})$ with itself,

$\eta_{\rm crit}^{{\cal P}_{3}^{2}(\mathbb{R})}\leq 0.533.$ (46)

And with a system of local dimension $8^{3}$,

$\eta_{\rm crit}^{{\cal P}_{3}^{3}(\mathbb{R})}\leq 0.389.$ (47)

The interest of this method is that it tends faster to $\eta_{\rm crit}=0$
using smaller $d$ than in any previous method. The downside is that, at least
applied to the examples provided here, it requires too many settings.

##  5 How to search for examples with low $\eta_{\rm crit}$ and a smaller
number of settings

Most of the examples we have presented so far require too many settings to be
tested in actual experiments. This leads to the question of whether we can
achieve low $\eta_{\rm crit}$ using a moderate number (e.g., $<100$) of
settings. The aim of this section is showing that, arguably, the answer is
affirmative. However, finding them will require some extra work.

###  5.1 First strategy: Vertex-transitive graphs

So far, our strategy for finding examples with low $\eta_{\rm crit}$ was
inspired by (the graphs of orthogonality of) sets of states common in quantum
mechanics and quantum information (Pauli and Newman states). Interestingly,
all our examples are sets of states whose graph of orthogonality is a vertex-
transitive graph. In addition, vertex transitivity will be an important
property for the second part of the paper, where optimizations of the Bell
inequalities will be carried out. In fact, for a large number of settings,
optimization will only be feasible for vertex-transitive graphs.

######  Definition 22 (Vertex-transitive graph).

A graph is vertex-transitive if, for every pair of vertices, there exists an
automorphism of the graph mapping one to the other.

Consequently, in searching for a systematic method to identify additional
examples with low $\eta_{\rm crit}$ (for maximally entangled states and before
any optimization), it makes sense to focus on vertex-transitive graphs.

Vertex-transitive graphs have been investigated for decades. As a fruit of
these efforts (see, e.g., [84, 91, 90]), there are databases with all vertex-
transitive graphs with up to $47$ vertices [92], all vertex-transitive graphs
of degree $3$ (i.e., each vertex is adjacent to three others) up to $1280$
vertices [93], all circulant graphs up to $60$ vertices, and all circulant
graphs with degrees at most $20$ up to $65$ vertices, at most $16$ up to $70$
vertices, and at most $12$ up to $100$ vertices [94]. Therefore, we can use
these databases to compute $\eta_{\rm crit}$ for all these graphs and their
complements and then select those that are interesting.

For any graph $G$,
$\omega(G)\leq\vartheta(\overline{G})\leq\xi(G)\leq\chi(G)$, where
$\omega(G)$, $\vartheta(\overline{G})$, $\xi(G)$, and $\chi(G)$ are,
respectively, the clique number, the Lovász number of the complement of $G$,
the orthogonal rank, and the chromatic number [86, 95]. The clique number
$\omega$ is a trivial lower bound for $\xi$. The problem is that $\xi$ cannot
be computed efficiently. However, in all the examples with low $\eta_{\rm
crit}$ that we have identified, $\xi=\omega$. Therefore, we can use the
databases and compute, for each $|V|$, the minimum of
$\sqrt{\frac{\alpha}{|V|/\omega}}$. This gives a lower bound for $\eta_{\rm
crit}$ that can be expected (for maximally entangled states and before any
optimization) for the corresponding set of graphs. The results of these
computations for all vertex-transitive graphs up to $47$ vertices are
presented in Table 1.

Table 1 shows that the aforementioned lower bound for $\eta_{\rm crit}$
decreases as the number of vertices increases. Moreover, it suggests that (for
maximally entangled states and before any optimization) there are examples
with $\eta_{\rm crit}<0.5$ and $|V|<100$ vertices.

We can use existing computational tools [96] to estimate the exact $\xi$. To
find a orthogonal representation in $\mathbb{R}^{d}$ (or in $\mathbb{C}^{d}$)
with minimal $\xi$ of the promising graphs, we can write each vector in the
orthogonal representation as a unit vector using $d$ (or $2d$) real variables,
and rotating the orthogonal representation into some canonical position to
reduce the number of variables. Then, we take into account that the
automorphisms of the graph (which can be easily computed) lead to geometric
symmetries in the orthogonal representation. Then, using numerical
optimization software, we run the minimization problem where the objective is
to minimize the sum of squares of inner products for $\mathbb{R}^{d}$ (or the
sum of squares of absolute values of inner products for $\mathbb{C}^{d}$),
where the sum is taken over those pairs of vectors that are supposed to be
orthogonal in the orthogonal representation. Notice that the automorphisms of
the graph dramatically reduce the number of variables in the optimization
problem because now we need only one vector per each orbit of a symmetry
group. This works with many dozens of variables quite well. Maple and other
software can run this in arbitrary precision from which one may recover
analytical expressions for the solutions.

$|V|$ | $n$ | $\min\sqrt{\frac{\alpha}{|V|/\omega}}$
---|---|---
$18$ | $380$ | $0.816$
$19$ | $60$ | $0.795$
$20$ | $1214$ | $0.775$
$21$ | $240$ | $0.756$
$22$ | $816$ | $0.739$
$23$ | $188$ | $0.780$
$24$ | $15506$ | $0.707$
$25$ | $464$ | $0.775$
$26$ | $4236$ | $0.734$
$27$ | $1434$ | $0.745$
$28$ | $25850$ | $0.732$
$29$ | $1182$ | $0.719$
$30$ | $46308$ | $0.707$
$31$ | $2192$ | $0.696$
$32$ | $677402$ | $0.667$
$33$ | $6768$ | $0.625$
$34$ | $132580$ | $0.64$
$35$ | $11150$ | $0.627$
$36$ | $1963202$ | $0.615$
$37$ | $14602$ | $0.604$
$38$ | $814216$ | $0.593$
$39$ | $48462$ | $0.632$
$40$ | $13104170$ | $0.571$
$41$ | $52488$ | $0.561$
$42$ | $946226$ | $0.6$
$43$ | $99880$ | $0.635$
$44$ | $39134640$ | $0.581$
$45$ | $399420$ | $0.571$
$46$ | $34333800$ | $0.562$
$47$ | $364724$ | $0.597$
Table 1: The minimum value of $\sqrt{\frac{\alpha}{|V|/\omega}}$, which is a
lower bound for $\eta_{\rm crit}$, for all vertex-transitive graphs with
$|V|\leq 47$ vertices. $n$ is the number of vertex-transitive graphs with the
corresponding number of vertices.

###  5.2 Second strategy: Nonvertex-transitive graphs

So far, we have focused on graphs that are vertex transitive. The reasons for
this are that vertex-transitive graphs are relatively easy to identify and
have a lot of symmetry. The latter is crucial for the optimization discussed
in the second step of the method.

However, in [97], it is shown that there are other graphs leading to quantum
correlations based on maximally entangled states violating a Bell inequality:
Those admitting an orthonormal representation in dimension $\xi$ and
nonnegative vertex weights $w=\\{w_{i}\\}_{i=1}^{n}$ such that
$\sum_{i=1}^{n}w_{i}/\xi>\alpha(G,w)$, where $\alpha(G,w)$ is the independence
number of the corresponding weighted graph. In addition, in [85], it is shown
that a condition for these graphs is that the fractional chromatic number
satisfies $\chi_{f}>\xi$. Interestingly, this condition, which is not
sufficient for the graphs to have associated SI-C sets (see Theorem 1 in [85])
is, in fact, sufficient for having quantum correlations based on maximally
entangled states violating a Bell inequality.

Therefore, another strategy to find examples with low $\eta_{\rm crit}$ would
be the following: Find graphs with $\chi_{f}>\xi$. For each of them, find $w$,
such that $\sum_{i=1}^{n}w_{i}/\xi>\alpha(G,w)$. Then, in a similar way as for
Theorem 3, we can prove for these graphs and weights,

$\eta_{\rm
crit}\leq\sqrt{\frac{\alpha(G,w)}{\sum_{i=1}^{n}\frac{w_{i}}{\xi}}}.$ (48)

Interestingly, since these weights are often natural numbers (e.g., for the
Yu-Oh set [98], the weights are $2$ for $4$ of the vectors and $3$ for the
other $9$ vectors [97]), one can see the weighted graphs $(G,w)$ as
nonweighted graphs $G$ with an extended number of vertices (e.g., for the Yu-
Oh set, $G$ would have $4\times 2+9\times 3=35$ vertices). Then, for finding
candidates that may have a low $\eta_{\rm crit}$, we can use databases of
nonweighted graphs of $13$ or more vertices (as it is known that the graphs
for which $\chi_{f}>\xi$ must have, at least, $13$ vertices [99]) and there
identify, first, graphs with $\chi_{f}>\omega$, where $\omega$ is the clique
number, which is easier to compute than $\xi$. Since $\omega\leq\xi$, this is
a necessary condition. Later on, one can use existing computational tools [96]
to obtain $\xi$.

##  6 Noise and how to obtain better Bell inequalities

Here, we first show that, in all the examples with low $\eta_{\rm crit}$
presented so far, the values shown for $\eta_{\rm crit}$ are very sensitive to
noise (Theorem 8). The good news is that all the upper bounds for $\eta_{\rm
crit}$ have been obtained with respect to a graph-based Bell inequality of the
form in Eq. (1). However, for fixed correlations, we can optimize our Bell
inequalities and obtain a lower value for $\eta_{\rm crit}$, which can also be
more robust to noise. This optimization is discussed in Sec. 6.2 and uses the
high symmetry of the measurements (their graph of orthogonality is vertex-
transitive) producing the correlations.

###  6.1 Noise and graph-based Bell inequalities

In most discussions on the critical detection efficiency (e.g., [21, 29, 30]),
the effect of noise is modeled with the assumption that the effective state is
of the form

$\rho=W|\psi\rangle\langle\psi|+(1-W)\frac{\mathbbm{1}}{d^{2}},$ (49)

where $|\psi\rangle$ is the targeted state, $W$ is the visibility of the
state, $\mathbbm{1}$ is the identity, and $d$ is the dimension of the local
system. In this work, we will follow this practice. However, it must be
pointed out that, in some cases [100], the effective state is not of the form
(49) and it is important to take this into account [101].

######  Theorem 7.

For a Bell inequality of the form (1) associated to a graph $G(V,E)$ with
vertex set $V$ and edge set $E$, and states of the form (49), the critical
visibility $W_{\rm crit}$, i.e., the minimal value of $W$ in
$\eqref{eq:werner}$ for a violation in (1) is given by

$W_{\rm crit}\leq\frac{\alpha-Q_{\rm mix}}{(|V|/d)-Q_{\rm mix}},$ (50)

where

$Q_{\rm mix}=\frac{1}{d^{2}}\left(|V|-|E|/\Xi\right).$ (51)

###### Proof.

Notice that $Q_{\rm mix}$ is the violation of (1) for the maximally mixed
state. ∎

######  Theorem 8.

For a Bell inequality of the form (1) associated to a graph $G(V,E)$ with
vertex set $V$ and edge set $E$ and states of the form (49), the critical
detection efficiency $\eta_{\rm crit}$ is given by

$\eta_{\rm crit}^{2}\leq\frac{\alpha
d^{2}}{|V|\left[W(d-1)+1\right]-|E|(1-W)/\Xi}.$ (52)

###### Proof.

The quantum violation of the Bell inequality (1) with state (49) and perfect
detection efficiency is given by

$Q^{\prime}=WQ+(1-W)Q_{\text{mix}},$ (53)

where $Q\geq\frac{|V|}{d}$ is the expected quantum violation and $Q_{\rm mix}$
is the value for the maximally mixed state, which is given by (51). Then, the
critical detection efficiency in Eq. (13) becomes Eq. (52). ∎

Theorem 8 implies that, for the graph-based Bell inequalities (1), $\eta_{\rm
crit}$ rapidly increases with the number of edges unless $W$ is very close to
$1$. Therefore, although experimental values of $W$ can be as high as $0.980$
for $d=3$ and $0.943$ for $d=17$ [102], it would be desirable to find Bell
inequalities for which the same correlations (i.e., the same state and the
same measurements) have a value for $\eta_{\rm crit}$ (and for $W_{\rm crit}$)
that is much less sensitive to noise. This problem is addressed in the next
section.

###  6.2 Optimized Bell inequalities based on symmetries

####  6.2.1 Introduction

The graph-based Bell inequality (1) only takes into account probabilities
$P(\Pi_{i}^{A}=a,\Pi_{j}^{B}=b)$ in which either $i=j$ or $i$ and $j$ are
adjacent in the graph $G$. However, in a Bell test Alice and Bob independently
choose their measurements in such a way that the choice on one of them is
spacelike separated from the recording of the measurement outcome on the
other. Therefore, while every observable $\Pi_{i}^{A}$ of Alice is compatible
with every observable $\Pi_{j}^{B}$ of Bob, inequality (1) does not use most
of the joint probability distributions $P(\Pi_{i}^{A}=a,\Pi_{j}^{B}=b)$. All
the not used distributions are thus wasted.

An interesting question is the following: What if we use the same state and
measurements used in the violation of the graph-based Bell inequality (1) and
consider all the joint probability distributions
$P(\Pi_{i}^{A}=a,\Pi_{j}^{B}=b)$? Can we then obtain a better Bell inequality?

“Better” may mean having higher resistance to noise (i.e., lower $W_{\rm
crit}$), having lower critical detection efficiency $\eta_{\rm crit}$, or
both, depending on what we are interested in. For designing a loophole-free
Bell test, what we need is that the experimental values for the visibility and
the detection efficiency, $W_{\text{exp}}$ and $\eta_{\text{exp}}$,
respectively, are both above their respective critical values. That is, we
need $W_{\text{exp}}>W_{\rm crit}$ and $\eta_{\text{exp}}>\eta_{\rm crit}$.

In the next sections we show how to compute $W_{\rm crit}$ and $\eta_{\rm
crit}$ for states of interest. Intentionally, in the first example, we focus
on an instance which does not offer neither a low $W_{\rm crit}$ nor a low
$\eta_{\rm crit}$, but which will guide us to attack more interesting
examples.

Figure 1: Graph of orthogonality of the $24$ Pauli states in ${\cal
P}_{2}(\mathbb{R})$. Vertices (dots) represent states and edges connect those
that are orthogonal. The $24$ states can be distributed in $6$ disjoint
orthogonal bases, which are indicated by thicker edges.

####  6.2.2 Pauli-$24$

Fig. 1 shows the graph of orthogonality of the $24$ (not normalized) states in
${\cal P}_{2}(\mathbb{R})$. This graph has $\alpha=5$ and
$\vartheta=\alpha^{\ast}=6$. Therefore, by preparing the maximally entangled
state (12) of local dimension $\xi=2^{2}=4$ and allowing each of the parties
to choose between the $24$ two-outcome measurements represented by
$|v_{i}\rangle\langle v_{i}|$, with $|v_{i}\rangle\in{\cal
P}_{2}(\mathbb{R})$, Alice and Bob can produce a violation of the Bell
inequality (1) which, using Theorem 3, allows us to conclude that

$\eta_{\rm crit}^{{\cal P}_{2}(\mathbb{R})}\leq 0.913$ (54)

and, using Theorem 7, allows us to conclude that

$W_{\rm crit}^{{\cal P}_{2}(\mathbb{R})}\leq 0.911.$ (55)

####  6.2.3 Gilbert’s algorithm

While our graph-based Bell inequalities are neither tight (i.e., facets of the
local polytope) nor robust to noise, they can be further improved to offer
better detection efficiency and noise robustness. This can be achieved by
calculating the Bell functional in Eq. (3) using two different methods.

The first method is a linear program which optimizes over the entire local
polytope to find the best Bell functional [27]. However, this technique
requires enumerating and storing all the local deterministic points which are
given by the vertices of the local polytope. This becomes an increasingly
difficult computational task as the number of measurement settings increases.
As an example, the local polytope corresponding to the Bell inequality with
$24$ settings per party derived from $\mathcal{P}_{2}(\mathbb{R})$ has
$2^{48}$ vertices. This number is too large to be stored on a standard
computer. In this paper, we use a second method which is based on Gilbert’s
distance algorithm [103] and does not require storing all the vertices of the
local polytope. However, it should be noted that, for the cases we are
interested in (e.g., $\mathcal{P}_{2}(\mathbb{R})$), the problem is still
intractable using Gilbert’s original algorithm. The problem only becomes
feasible when symmetries are also taken into account, as explained in Sec.
6.2.4.

Gilbert’s algorithm is a well-known numerical method to detect collisions
between convex sets. It has been used for improving detection efficiencies of
Bell inequalities [27], deciding whether or not a given correlation is
nonlocal [104], and entanglement witnessing [105, 106]. The algorithm
minimizes the distance between a local point on a facet of the local polytope
and a nonlocal point specified by the user. The minimization is achieved by
iteratively finding a better local point that minimizes this distance. The
algorithm terminates when the difference of distances between successive
iterations falls below a certain threshold value (typically taken to be
extremely small). The resulting Bell functional is then identified as the
separating hyperplane between the specified nonlocal point and the local point
on the facet found by minimizing the distance. In the following, we will
present this algorithm in more detail. The algorithm is based on an oracle
which is capable of maximizing over the local polytope $\mathcal{P}$ the inner
product between a point in $\mathbb{R}^{n}$. Initially, one has to specify the
local polytope $\mathcal{P}\subset\mathbb{R}^{n}$, presented as the convex
hull of vertices $\\{c_{k}\\}_{k}$, and a point $q\in\mathbb{R}^{n}$
associated to the given quantum correlation. Then, the algorithm proceeds as
follows. First, it chooses a point $s_{0}\in\mathcal{P}$. Second, with the
given point $s_{k}$, it uses the oracle to compute

$\displaystyle\tilde{s}_{k}:$
$\displaystyle=\underset{p\in\mathcal{P}}{\text{argmax}}\,\langle
q-s_{k},p-s_{k}\rangle$
$\displaystyle=\underset{p\in\mathcal{P}}{\text{argmax}}\,\langle
q-s_{k},p\rangle.$ (56)

Third, given $s_{k}$ and $\tilde{s}_{k}$, it calculates the convex combination
of both which minimizes the distance to the quantum point $q$, that is,

$\displaystyle\lambda_{k}:=\underset{\lambda\in[0,1]}{\text{min}}\,||(1-\lambda)s_{k}+\lambda\tilde{s}_{k}-q||.$
(57)

Since the objective function in (6.2.3) is linear and $\mathcal{P}$ convex,
the maximizer will be an extreme point of $\mathcal{P}$. In particular,
$\tilde{s}_{k}$ will be a vertex of the local polytope $\mathcal{P}$. The
optimal value for $\lambda$ in the $k$-th iteration, denoted by $\lambda_{k}$,
can be computed directly and is given by

$\displaystyle\lambda_{k}=\text{min}\,\left\\{\frac{\langle
q-s_{k},\tilde{s}_{k}-s_{k}\rangle}{||\tilde{s}_{k}-s_{k}||^{2}},1\right\\}.$
(58)

Then, it defines the new starting point to be
$s_{k+1}:=(1-\lambda_{k})s_{k}+\lambda_{k}\tilde{s}_{k}$ and it proceeds with
the second step. In the standard Gilbert’s algorithm, the oracle is
implemented by enumerating all the vertices of the local polytope
$\mathcal{P}$ to compute the inner product in the last equality of Eq.
(6.2.3). For a geometrical interpretation of the iteration of Gilbert’s
algorithm, see Fig. 2.

Figure 2: Illustration of Gilbert’s algorithm. The quantum point $q$ lies
outside the local polytope $\mathcal{P}$. Starting with an arbitrary local
point $s_{k}\in\mathcal{P}$, the oracle yields the point $\tilde{s}_{k}$
within $\mathcal{P}$, maximizing the overlap with $q-s_{k}$. From there, a new
starting point $s_{k+1}$ can be calculated.

This algorithm provides a sequence of Bell functionals, which become better
with each iteration. Note that it does not necessarily provide a tight Bell
inequality like the first method. Moreover, calculating the local bound of the
resultant Bell functional still remains an NP hard problem, which again
requires enumerating and storing all the local deterministic points at least
for one party111For a given bipartite Bell functional where each measurement
has only two outcomes $\pm 1$, once we have fixed the deterministic assignment
of one party, the optimal value of the Bell functional and the corresponding
deterministic assignments of another party are determined. Refer to Sec. 1 in
appendix C of Ref. [107] for more details.. This issue is also shared by the
oracle in the standard Gilbert’s algorithm, since the evaluation of Eq.
(6.2.3) is equivalent to find the local bound of one Bell functional.

####  6.2.4 Gilbert’s algorithm with symmetrization

The two problems mentioned at the end of the previous section can be solved
simultaneously by replacing the hitherto generic oracle with an oracle that
takes into account the symmetries of the problem. This provides an advantage
that is crucial for improving the speed of convergence. In this respect, it is
important to notice that the vertices of the local polytope (and the polytope
itself) are invariant under the following invertible transformations: (i)
Swapping the outcomes of a measurement setting for either Alice or Bob. (ii)
Simultaneously permuting the measurement settings of Alice and Bob. (iii)
Swapping the measurement settings of Alice and Bob. Here, “invariant” means
that the transformations map local correlations to local correlations.

The joint probability distributions obtained by performing measurements on a
quantum state are also invariant under some of these transformations. We
denote by $\mathcal{S}$ a subset of these transformations which keep the
quantum joint probability distributions and the local polytope invariant
simultaneously.

We consider a matrix similar to the one in Eq. (3) in which the entries are
probability distributions instead of coefficients, given as,

$\displaystyle M_{p}=$
$\displaystyle\left(\begin{tabular}[]{c|ccc}$1$&$P(\Pi_{1}^{A}\\!=\\!1)$&\ldots&$P(\Pi_{m}^{A}\\!=\\!1)$\\\
\hline\cr$P(\Pi_{1}^{B}\\!=\\!1)$&$P(\Pi_{1}^{A}\\!=\\!\Pi_{1}^{B}\\!=\\!1)$&$\dots$&$P(\Pi_{m}^{A}\\!=\\!\Pi_{1}^{B}\\!=\\!1)$\\\
$\vdots$&$\vdots$&$\ddots$&$\vdots$\\\
$P(\Pi_{m}^{B}\\!=\\!1)$&$P(\Pi_{1}^{A}\\!=\\!\Pi_{m}^{B}\\!=\\!1)$&$\dots$&$P(\Pi_{m}^{A}\\!=\\!\Pi_{m}^{B}\\!=\\!1)$\end{tabular}\right).$
(63)

The corresponding Bell inequality can then be calculated as ${\rm
tr}(IM_{p}^{T})\leq\lambda$. Under the transformations $S\in\mathcal{S}$ we
have,

${\rm tr}(IM_{p}^{T})\\!=\\!{\rm tr}(IS(M_{p})^{T})\\!=\\!{\rm
tr}(S^{-1}(I)M_{p}^{T})\leq\lambda,$ (64)

where $S(M_{p})$ is the resultant matrix after transformation $S$. Therefore,
we have

$\displaystyle{\rm tr}(IM_{p}^{T})\\!=\\!{\rm
tr}\left(I\bar{M}_{p}^{T}\right)\\!=\\!{\rm tr}(\bar{I}M_{p}^{T})\\!=\\!{\rm
tr}(\bar{I}\bar{M}_{p}^{T}),$ (65)

where

$\bar{M}_{p}=\frac{1}{|\mathcal{S}|}\sum_{S_{i}\in\mathcal{S}}S_{i}(M_{p}),\
\bar{I}=\frac{1}{|\mathcal{S}|}\sum_{S_{i}\in\mathcal{S}}S_{i}^{-1}(M_{p}),$
(66)

and $|\mathcal{S}|$ is the cardinality of $\mathcal{S}$. Using this symmetry
$\mathcal{S}$, it is sufficient to consider only inequalities that share this
symmetry. In particular, for a symmetric inequality, the vertices of the local
polytope can be partitioned into different equivalence classes with respect to
that symmetry and the local bound can be computed by choosing only one
representative out of each class. This drastically reduces the total number of
local vertices required, allowing us to enumerate all symmetrized local points
and evaluate the local bound.

For convenience, here we focus on the symmetrization applied only to Alice’s
measurement settings. Each equivalence class consists of vertices which can be
transformed into each other by using the aforementioned symmetry
transformations, while the same is not true for vertices in different
equivalence classes, i.e., the partition generates disjoint sets. This leads
to a modified oracle, which is much more efficient than the original one since
the number of equivalence classes could much smaller than the number of all
vertices. This is indeed the case for $\mathcal{P}_{2}(\mathbb{R})$.

Now, we describe how to obtain the reduced set of vertices on which the
optimization in (6.2.3) has to run. In the first step, we have to determine
the allowed symmetry transformations $\mathcal{S}$, which should be shared by
the chosen quantum point $q$ and the local polytope $\mathcal{P}$. As already
pointed out, $\mathcal{P}$ is invariant under the permutation of parties, the
permutation of the measurements for each party, and the permutation of the
outcomes for each measurement. By construction, the chosen quantum point $q$
is also invariant under the permutation of parties. Usually, $q$ can change
after the permutation of outcomes for each measurement. In general,
determining the permutation symmetries of measurements in the point $q$ can be
difficult when the number of measurements is large. In the cases considered
here, those symmetry transformations correspond to the ones in the
automorphism group of the graph associated to the SI-C sets. Therefore, the
symmetry transformations used in the Gilbert’s algorithm with symmetrization
are the ones in the automorphism group and the permutation of parties. It
remains to explain how the vertices are partitioned into different equivalence
classes.

The first important observation is that now we do not need to generate, store,
and classify all vertices, since assignments with different number of $1$’s
cannot be equivalent to each other. Hence, we can do the classification
inductively. We start with the assignment that only contains $0$’s. Obviously,
this is invariant under all possible permutations. From this, we generate all
possible assignments that can be obtained by replacing one $0$ by one $1$.
Within this set, we check whether some of these assignments are equivalent
under the given symmetry transformations $\mathcal{S}$, which are presented as
permutations. Then, we only keep one representative for each class. This
procedure is repeated until no $0$ is left in the assignment vector.

Selecting only a single vertex from each equivalence class (and all the
vertices of Bob), we find that the total number of deterministic assignments
for Alice is $21564$ for the Bell inequality corresponding to
$\mathcal{P}_{2}(\mathbb{R})$ (while, without symmetrization, it would be
$2^{24}$).

We also modify the Gilbert’s algorithm to evaluate the Bell functional
according to the symmetrization procedure in Eq. (65). Specifically, we
symmetrize the local point chosen in each iteration of the program after
minimizing its distance from the target nonlocal point, see Fig. 3 for a
simple illustration. This results in better convergence times of the algorithm
since symmetrization does not increase the distance.

Figure 3: Illustration of Gilbert’s algorithm with symmetrization. In this
simple example, the point $q$ and the polytope $\mathcal{P}$ are invariant
under the flip around line $l$. After the point $s_{k+1}$ has been found in
the standard Gilbert’s algorithm, we obtain its symmetrization $\bar{s}_{k+1}$
for the flip around line $l$. The point $\bar{s}_{k+1}$ is used instead of
$s_{k+1}$ as the new starting point for the next iteration.

####  6.2.5 Example: Bell inequality for Pauli-$24$ that minimizes $\eta_{\rm
crit}$ and $W_{\rm crit}$

As an example, here we present a Bell functional for the correlations produced
by the maximal entangled state (12), with $\xi=4$, and the measurements
associated to the states in $\mathcal{P}_{2}(\mathbb{R})$ which has lower
detection efficiency and larger tolerance to white noise than those of to the
graph-based Bell functional (1). The purpose of this example is to show that
the values of $\eta_{\rm crit}$ and $W_{\rm crit}$ obtained in the first step
of the method can, in principle, always be improved.

Applying Gilbert’s algorithm and the symmetrization technique to the
correlations produced by ${\cal P}_{2}(\mathbb{R})$ and maximally entangled
states, we have obtained the following Bell inequality:

$I_{{\cal P}_{2}(\mathbb{R})}\leq 0,$ (67)

where

$I_{{\cal
P}_{2}(\mathbb{R})}=\left(\begin{array}[]{c|rr}&|v\rangle&|v\rangle\\\
\hline\cr\langle v|&M_{1}&M_{2}\\\ \langle v|&M_{2}&M_{1}\end{array}\right),$
(68)

with $M_{1}$ to be a matrix full of $0$’s, $|v\rangle$ to be a vector full of
$-6$’s, and

$M_{2}=\left(\begin{array}[]{rrrrrrrrrrrrrrrrrrrrrrrr}5&5&\bar{4}&\bar{4}&5&5&\bar{4}&\bar{4}&5&5&\bar{4}&\bar{4}\\\
5&5&\bar{4}&\bar{4}&\bar{4}&\bar{4}&5&5&\bar{4}&\bar{4}&5&5\\\
\bar{4}&\bar{4}&5&5&5&5&\bar{4}&\bar{4}&\bar{4}&\bar{4}&5&5\\\
\bar{4}&\bar{4}&5&5&\bar{4}&\bar{4}&5&5&5&5&\bar{4}&\bar{4}\\\
5&\bar{4}&5&\bar{4}&5&\bar{4}&5&\bar{4}&5&\bar{4}&5&\bar{4}\\\
5&\bar{4}&5&\bar{4}&\bar{4}&5&\bar{4}&5&\bar{4}&5&\bar{4}&5\\\
\bar{4}&5&\bar{4}&5&5&\bar{4}&5&\bar{4}&\bar{4}&5&\bar{4}&5\\\
\bar{4}&5&\bar{4}&5&\bar{4}&5&\bar{4}&5&5&\bar{4}&5&\bar{4}\\\
5&\bar{4}&\bar{4}&5&5&\bar{4}&\bar{4}&5&\bar{4}&5&5&\bar{4}\\\
5&\bar{4}&\bar{4}&5&\bar{4}&5&5&\bar{4}&5&\bar{4}&\bar{4}&5\\\
\bar{4}&5&5&\bar{4}&5&\bar{4}&\bar{4}&5&5&\bar{4}&\bar{4}&5\\\
\bar{4}&5&5&\bar{4}&\bar{4}&5&5&\bar{4}&\bar{4}&5&5&\bar{4}\end{array}\right),$
(69)

where $\bar{4}=-4$.

For the maximally entangled state (12), the quantum value is

$I_{{\cal P}_{2}(\mathbb{R})}=18.$ (70)

In addition, for the correlations produced by ${\cal P}_{2}(\mathbb{R})$ and
maximally entangled states,

$W_{\rm crit}=\frac{7}{9}=0.778,$ (71)

which is $14.62\%$ lower than the upper bound in (55), and

$\eta_{\rm crit}=\frac{4}{5}=0.8,$ (72)

which is $12.38\%$ lower than the upper bound in (54).

We can prove that $W_{\rm crit}$ and $\eta_{\rm crit}$ are the smallest
possible values for the correlations produced by ${\cal P}_{2}(\mathbb{R})$
and maximally entangled states as follows: First, we collect all the $452929$
pairs of deterministic assignments for the two parties which achieve the
maximal bound for LHV models. Each of them corresponds to a matrix $M_{p}$.
After symmetrization, there are only $132$ different matrices $\bar{M}_{p}$,
whose convex combination can lead to the corresponding quantum probability
matrix either with $W=7/9$ or with $\eta=4/5$, as one can verify with linear
programming. Inequality (67) is not tight. There is a tight Bell inequality
providing the same $\eta_{\rm crit}$ and $W_{\rm crit}$ than the ones for
inequality (67), but it does not have the two blocks of $0$’s that we have in
(69). If we want to keep the $0$’s, inequality (67) is the only solution.

Notice that symmetries of the initial graph are crucial for finding (69). For
example, notice that there are only $6$ different parameters in the symmetric
inequality for the case of $\mathcal{P}_{2}(\mathbb{R})$. In comparison, there
are $624$ parameters in the nonsymmetric inequality for
$\mathcal{P}_{2}(\mathbb{R})$. In the general case, there are $2m+2$
parameters in the symmetric inequality for $\mathcal{P}_{m}(\mathbb{R})$ and
$\mathcal{P}_{m}(\mathbb{C})$. This makes it also possible to find a better
inequality without resorting to Gilbert’s method. To be more explicit, we can
choose $t$ different values for each parameter, then there are $t^{2m+2}$
different inequalities. For each inequality, we can verify whether it
separates the target quantum point and the LHV polytope or not by considering
only the deterministic assignments up to symmetry. As discussed before, when
$m=2$, there are $21564$ different deterministic assignments for Alice up to
symmetry. Therefore, for a fixed inequality, this verification can be done
very fast. Similarly, we can calculate $\eta_{\rm crit}$ and $W_{\rm crit}$
for each inequality. As we can see in Eq. (69), we can set some parameters to
be $0$ for the best $\eta_{\rm crit}$ and $W_{\rm crit}$. This trick can speed
up the numerical calculation further.

##  7 Towards high-dimensional long-distance loophole-free Bell tests

We have shown how to identify quantum correlations between systems of moderate
dimension ($d\leq 128$) that allow for loophole-free Bell nonlocality with low
detection efficiency. Our results imply that, probably, loophole-free Bell
nonlocality can be achieved in carefully designed tests involving pairs of
systems of these dimensions, which is interesting by itself as it goes beyond
previous loophole-free Bell tests, all of them based on qubits. More
interestingly, our results also imply that loophole-free Bell nonlocality can
be achieved through longer distances than those of previous loophole-free Bell
tests. When photons propagate thorough fibers, they experience propagation
losses proportional to the propagation distance and which depend on the
optical wavelength. This means that in a Bell test over long distances (and
unless we add, e.g., heralded qudit amplifiers [39] or split each photon into
two [41, 42] before the local measurements), the detection efficiency
decreases with the distance. For example, with telecom wavelengths, in $10$ km
of fiber, we may have losses of $0.2$ dB/km, which implies multiplying by
$0.64$ the detection efficiency that we had before adding $10$ km of fiber.
Therefore, if we have examples of loophole-free Bell nonlocality requiring
$\eta_{\rm crit}<0.5$, we can achieve loophole-free nonlocality over $10$ km
if we have $\eta_{\rm exp}>0.785$ before adding the $10$ km of fiber. Such
$\eta_{\rm exp}$ has been achieved in previous photonic loophole-free
experiments [14, 15], even including ($<200$ m of) fibers and the couplings.

In this paper, we have shown how to achieve $\eta_{\rm crit}<0.52$ with local
dimensions $16$ [see Eq. (20)] and how to obtain Bell inequalities with even
lower $\eta_{\rm crit}$ and higher resistance to noise. Now the question is
what are the values of the visibility $W$ that are experimentally achievable
for the required configurations. Although some previous results are very
promising [102], it is not clear to us whether similar values ($W_{\rm
exp}>0.95$) can be achieved for the states and measurements described in this
paper. For further progress, we need to know what pairs $(\eta_{\rm
exp},W_{\rm exp})$ can be obtained for the type of states and measurements
proposed here (e.g., for $d=16$ and Pauli-$4320$). In addition, we have
introduced methods to identify further examples with low $\eta_{\rm crit}$
requiring smaller number of settings.

Figure 4: $\eta_{\rm crit}$ as a function of the dimension $d$ of the local
system. The previous smallest values are those in [21, 26, 28] and use
nonmaximally entangled states. Pauli (Newman) states refer to the case in
which the local measurements are projectors on the Pauli (Newman) states and
the initial state is maximally entangled, as described in Sec. 3.2.

As shown in Fig. 4, the first step of our method already yields upper bounds
for $\eta_{\rm crit}$ which are substantially smaller than the lowest values
previously known for any dimension $d\geq 16$. These values indicate that
there are quantum correlations which have sufficiently low $\eta_{\rm crit}$
for loophole-free Bell tests with higher-dimensional quantum systems and,
eventually, over longer distances. We have also shown how to improve any of
these values and we have described how we are trying to find more, and
probably better, examples in the future.

It now remains to be seen how far we can go on the experimental side. In
particular, there is one question, to which we do not have the answer: Is
there a way to encode high-dimensional entanglement in photons that allows, at
the same time, (i) to measure all the necessary one-dimensional projectors
locally and switch quickly between them, (ii) distribute the photons over,
e.g., $5$–$10$ km achieving visibilities $W_{\rm exp}>0.95$, (iii) using
superconducting detectors to actually achieve $\eta_{\rm exp}>0.5$? Hopefully,
the combination of techniques presented here and the interaction with
experimental groups will help us to produce high-dimensional loophole-free
Bell nonlocality over long distances in the near future.

The code supporting the results reported in this paper is available in [108].

## Acknowledgments

We thank Ernesto Galvão, Junior R. Gonzales-Ureta, Petr Lisoněk, Debashis
Saha, and Stefan Trandafir for discussions, and the University of Siegen for
enabling our computations through the OMNI cluster. This work is supported by
Universidad de Sevilla Project Qdisc (Project No. US-15097), with FEDER funds,
MCINN/AEI Projet No. PID2020-113738GB-I00, QuantERA grant SECRET, by MCINN/AEI
(Project No. PCI2019-111885-2), Deutsche Forschungsgemeinschaft (DFG, German
Research Foundation, Project No. 447948357 and No. 440958198), the Sino-German
Center for Research Promotion (Project No. M-0294), and the ERC (Consolidator
Grant 683107/TempoQ). ZPX is supported by the Humboldt Foundation. JS is
supported by the House of Young Talents of the University of Siegen. JRP is
supported by Universidad de Sevilla Project No. US-1254251, with FEDER funds,
and Junta de Andalucía Project No. P20-00592.

## References

  * [1] J. S. Bell, On the Einstein Podolsky Rosen paradox, Physics 1, 195 (1964).
  * [2] N. Brunner, D. Cavalcanti, S. Pironio, V. Scarani, and S. Wehner, Bell nonlocality, Rev. Mod. Phys. 86, 419 (2014).
  * [3] P. M. Pearle, Hidden-variable example based upon data rejection, Phys. Rev. D 2, 1418 (1970).
  * [4] As explained in Ref. [3].
  * [5] R. Colbeck, Quantum and Relativistic Protocols for Secure Multi-Party Computation, PhD thesis, University of Cambridge, 2006; arXiv:0911.3814.
  * [6] S. Pironio, A. Acín, S. Massar, A. Boyer de la Giroday, D. N. Matsukevich, P. Maunz, S. Olmschenk, D. Hayes, L. Luo, T. A. Manning, and C. Monroe, Random numbers certified by Bell’s theorem, Nature 464, 1021 (2010).
  * [7] W.-Z. Liu, M.-H. Li, S. Ragy, S.-R. Zhao, B. Bai, Y. Liu, P. J. Brown, J. Zhang, R. Colbeck, J. Fan, Q. Zhang, and J.-W. Pan, Device-independent randomness expansion against quantum side information, Nat. Phys. 17, 448 (2021).
  * [8] L. K. Shalm, Y. Zhang, J. C. Bienfang, C. Schlager, M. J. Stevens, M. D. Mazurek, C. Abellán, W. Amaya, M. W. Mitchell, M. A. Alhejji, H. Fu, J. Ornstein, R. P. Mirin, S. W. Nam, and E. Knill, Device-independent randomness expansion with entangled photons, Nat. Phys. 17, 452 (2021).
  * [9] A. K. Ekert, Quantum cryptography based on Bell’s theorem, Phys. Rev. Lett. 67, 661 (1991).
  * [10] D. Mayers and A. Yao, Quantum cryptography with imperfect apparatus, Proceedings 39th Annual Symposium on Foundations of Computer Science (IEEE, Los Alamitos, CA, 1998), p. 503.
  * [11] J. Barrett, L. Hardy, and A. Kent, No signaling and quantum key distribution, Phys. Rev. Lett. 95, 010503 (2005).
  * [12] A. Acín, N. Brunner, N. Gisin, S. Massar, S. Pironio, and V. Scarani, Device-independent security of quantum cryptography against collective attacks, Phys. Rev. Lett. 98, 230501 (2007).
  * [13] S. Pironio, A. Acín, N. Brunner, N. Gisin, S. Massar, and V. Scarani, Device-independent quantum key distribution secure against collective attacks, New J. Phys. 11, 045021 (2009).
  * [14] M. Giustina, M. A. M. Versteegh, S. Wengerowsky, J. Handsteiner, A. Hochrainer, K. Phelan, F. Steinlechner, J. Kofler, J.-Å. 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, Significant-loophole-free test of Bell’s theorem with entangled photons, Phys. Rev. Lett. 115, 250401 (2015).
  * [15] 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, Strong loophole-free test of local realism, Phys. Rev. Lett. 115, 250402 (2015).
  * [16] W. Rosenfeld, D. Burchardt, R. Garthoff, K. Redeker, N. Ortegel, M. Rau, and H. Weinfurter, Event-ready Bell test using entangled atoms simultaneously closing detection and locality loopholes, Phys. Rev. Lett. 119, 010402 (2017).
  * [17] 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, Loophole-free Bell inequality violation using electron spins separated by 1.3 kilometres, Nature 526, 682 (2015).
  * [18] I. Pitowsky, Quantum Probability – Quantum Logic, Lecture Notes in Physics 321 (Springer, Berlin, 1989).
  * [19] A. Garg and N. D. Mermin, Detector inefficiencies in the Einstein-Podolsky-Rosen experiment, Phys. Rev. D 35, 3831 (1987).
  * [20] J. F. Clauser, M. A. Horne, A. Shimony, and R. A. Holt, Proposed experiment to test local hidden-variable theories, Phys. Rev. Lett. 23, 880 (1969).
  * [21] P. H. Eberhard, Background level and counter efficiencies required for a loophole-free Einstein-Podolsky-Rosen experiment, Phys. Rev. A 47, R747(R) (1993).
  * [22] J. F. Clauser and M. A. Horne, Experimental consequences of objective local theories, Phys. Rev. D. 10 526 (1974).
  * [23] N. Brunner and N. Gisin, Partial list of bipartite Bell inequalities with four binary settings, Phys. Lett. A 372, 3162 (2008).
  * [24] E. Zambrini Cruzeiro and N. Gisin, Complete list of tight Bell inequalities for two parties with four binary settings, Phys. Rev. A 99, 022104 (2019).
  * [25] S. Massar, Nonlocality, closing the detection loophole, and communication complexity, Phys. Rev. A 65, 032121 (2002).
  * [26] T. Vértesi, S. Pironio, and N. Brunner, Closing the detection loophole in Bell experiments using qudits, Phys. Rev. Lett. 104, 060401 (2010).
  * [27] I. Márton, E. Bene, and T. Vértesi, Bounding the detection efficiency threshold in Bell tests using multiple copies of the two-qubit maximally entangled state, Phys. Rev. A 107, 022205 (2023).
  * [28] N. Miklin, A. Chaturvedi, M. Bourennane, M. Pawłowski, and A. Cabello, Exponentially decreasing the critical detection efficiency for any Bell inequality, Phys. Rev. Lett. 129, 230403 (2022).
  * [29] J.-Å. Larsson and J. Semitecolos, Strict detector-efficiency bounds for $n$-site Clauser-Horne inequalities, Phys. Rev. A 63, 022117 (2001).
  * [30] A. Cabello, D. Rodríguez, and I. Villanueva, Necessary and sufficient detection efficiency for the Mermin inequalities, Phys. Rev. Lett. 101, 120402 (2008).
  * [31] K. F. Pál, T. Vértesi, and N. Brunner, Closing the detection loophole in multipartite Bell tests using Greenberger-Horne-Zeilinger states, Phys. Rev. A 86, 062111 (2012).
  * [32] A. Cabello and J.-Å. Larsson, Minimum detection efficiency for a loophole-free atom-photon Bell experiment, Phys. Rev. Lett. 98, 220402 (2007).
  * [33] N. Brunner, N. Gisin, V. Scarani, and C. Simon, Detection loophole in asymmetric Bell experiments, Phys. Rev. Lett. 98, 220403 (2007).
  * [34] G. Garbarino, Minimum detection efficiencies for a loophole-free observable-asymmetric Bell-type test, Phys. Rev. A 81, 032106 (2010).
  * [35] M. Araújo, M. T. Quintino, D. Cavalcanti, M. França Santos, A. Cabello, and M. Terra Cunha, Tests of Bell inequality with arbitrarily low photodetection efficiency and homodyne measurements, Phys. Rev. A 86, 030101(R) (2012).
  * [36] J. Å. Larsson, Loopholes in Bell inequality tests of local realism, J. Phys. A: Math. Theor. 47, 424003 (2014).
  * [37] J. Hofmann, M. Krug, N. Ortegel, L. Gérard, M. Weber, W. Rosenfeld, and H. Weinfurter, Heralded entanglement between widely separated atoms, Science 337, 72 (2012).
  * [38] T. C. Ralph and A. P. Lund, Nondeterministic noiseless linear amplification of quantum systems, AIP Conference Proceedings 1110, 155 (2009).
  * [39] N. Gisin, S. Pironio, and N. Sangouard, Proposal for implementing device-independent quantum key distribution based on a heralded qubit amplifier, Phys. Rev. Lett. 105, 070501 (2010).
  * [40] C. Branciard, Detection loophole in Bell experiments: How postselection modifies the requirements to observe nonlocality, Phys. Rev. A 83, 032123 (2011).
  * [41] A. Cabello and F. Sciarrino, Loophole-free Bell test based on local precertification of photon’s presence, Phys. Rev. X 2, 021010 (2012).
  * [42] E. Meyer-Scott, D. McCloskey, K. Gołos, J. Z. Salvail, K. A. G. Fisher, D. Hamel, A. Cabello, K. J. Resch, and T. Jennewein, Certifying the presence of a photonic qubit by splitting it in two, Phys. Rev. Lett. 116, 070501 (2016).
  * [43] M. Giustina, A. Mech, S. Ramelow, B. Wittmann, J. Kofler, J. Beyer, A. Lita, B. Calkins, T. Gerrits, S. W. Nam, R. Ursin, and A. Zeilinger, Bell violation using entangled photons without the fair-sampling assumption, Nature 497, 227 (2013).
  * [44] B. G. Christensen, K. T. McCusker, J. B. Altepeter, B. Calkins, T. Gerrits, A. E. Lita, A. Miller, L. K. Shalm, Y. Zhang, S. W. Nam, N. Brunner, C. C. W. Lim, N. Gisin, and P. G. Kwiat, Detection-loophole-free test of quantum nonlocality, and applications, Phys. Rev. Lett. 111, 130406 (2013).
  * [45] Y. Liu, X. Yuan, M. Li, W. Zhang, Q. Zhao, J. Zhong, Y. Cao, Y.-H. Li, L.-K. Chen, H. Li, T. Peng, Y.-A. Chen, C. Peng, S.-C. Shi, Z. Wang, L. You, X. Ma, J. Fan, Q. Zhang, and J.-W. Pan, High-speed device-independent quantum random number generation without a detection loophole, Phys. Rev. Lett. 120, 010503 (2018).
  * [46] L. Shen, J. Lee, L. P. Thinh, J.-D. Bancal, A. Cerè, A. Lamas-Linares, A. Lita, T. Gerrits, S. W. Nam, V. Scarani, and C. Kurtsiefer, Randomness extraction from Bell violation with continuous parametric down-conversion, Phys. Rev. Lett. 121, 150402 (2018).
  * [47] P. Bierhorst, E. Knill, S. Glancy, Y. Zhang, A. Mink, S. Jordan, A. Rommal, Y.-K. Liu, B. Christensen, S. W. Nam, M. J. Stevens, and L. K. Shalm, Experimentally generated randomness certified by the impossibility of superluminal signals, Nature 556, 223 (2018).
  * [48] Y. Liu, Q. Zhao, M.-H. Li, J.-Y. Guan, Y. Zhang, B. Bai, W. Zhang, W.-Z. Liu, C. Wu, X. Yuan, H. Li, W. J. Munro, Z. Wang, L. You, J. Zhang, X. Ma, J. Fan, Q. Zhang, and J.-W. Pan, Device-independent quantum random-number generation, Nature 562, 548 (2018).
  * [49] M.-H. Li, C. Wu, Y. Zhang, W.-Z. Liu, B. Bai, Y. Liu, W. Zhang, Q. Zhao, H. Li, Z. Wang, L. You, W. J. Munro, J. Yin, J. Zhang, C.-Z. Peng, X. Ma, Q. Zhang, J. Fan, and J.-W. Pan, Test of local realism into the past without detection and locality loopholes, Phys. Rev. Lett. 121, 080404 (2018).
  * [50] Y. Zhang, L. K. Shalm, J. C. Bienfang, M. J. Stevens, M. D. Mazurek, S. W. Nam, C. Abellán, W. Amaya, M. W. Mitchell, H. Fu, C. A. Miller, A. Mink, and E. Knill, Experimental low-latency device-independent quantum randomness, Phys. Rev. Lett. 124, 010505 (2020).
  * [51] L. K. Shalm, Y. Zhang, J. C. Bienfang, C. Schlager, M. J. Stevens, M. D. Mazurek, C. Abellán, W. Amaya, M. W. Mitchell, M. A. Alhejji, H. Fu, J. Ornstein, R. P. Mirin, S. W. Nam, and E. Knill, Device-independent randomness expansion with entangled photons, Nat. Phys. 17, 452 (2021).
  * [52] M.-H. Li, X. Zhang, W.-Z. Liu, S.-R. Zhao, B. Bai, Y. Liu, Q. Zhao, Y. Peng, J. Zhang, Y. Zhang, W. J. Munro, X. Ma, Q. Zhang, J. Fan, and J.-W. Pan, Experimental realization of device-independent quantum randomness expansion, Phys. Rev. Lett. 126, 050503 (2021).
  * [53] W.-Z. Liu, M.-H. Li, S. Ragy, S.-R. Zhao, B. Bai, Y. Liu, P. J. Brown, J. Zhang, R. Colbeck, J. Fan, Q. Zhang, and J.-W. Pan, Device-independent randomness expansion against quantum side information, Nat. Phys. 17, 448 (2021).
  * [54] W.-Z. Liu, Y.-Z. Zhang, Y.-Z. Zhen, M.-H. Li, Y. Liu, J. Fan, F. Xu, Q. Zhang, and J.-W. Pan, Photonic verification of device-independent quantum key distribution against collective attacks, Phys. Rev. Lett. 129, 050502 (2022).
  * [55] J.-L. Chen, A. Cabello, Z.-P. Xu, H.-Y. Su, C. Wu, and L. C. Kwek, Hardy’s paradox for high-dimensional systems, Phys. Rev. A 88, 062116 (2013).
  * [56] T. K. Lo and A. Shimony, Proposed molecular test of local hidden-variables theories, Phys. Rev. A 23, 3003 (1981).
  * [57] D. Collins and N. Gisin, A relevant two qubit Bell inequality inequivalent to the CHSH inequality, J. Phys. A: Math. Gen. 37, 1775 (2004).
  * [58] R. Diestel, Graph Theory, Graduate Texts in Mathematics 173 (Springer, Berlin, 2017).
  * [59] L. Hogben, K. F. Palmowski, D. E. Roberson, and S. Severini, Orthogonal representations, projective rank, and fractional minimum positive semidefinite rank: Connections and new directions, Electron. J. Linear Algebra 32, 98 (2017).
  * [60] L. Lovász, On the Shannon capacity of a graph, IEEE Trans. Inf. Theory 25, 1 (1979).
  * [61] M. Grötschel, L. Lovász, and A. Schrijver, Relaxations of vertex packings, J. Combin. Theory B 40, 330 (1986).
  * [62] C. E. Shannon, The zero-error capacity of a noisy channel. IRE Trans. Inform. Theory 2, 8 (1956).
  * [63] A. Cabello, S. Severini, and A. Winter, (Non-)Contextuality of physical theories as an axiom, Mittag-Leffler-2010fall Report No. 8 (2010).
  * [64] M. Planat, Quantum states arising from the Pauli groups, symmetries and paradoxes, in Symmetries and Groups in Contemporary Physics. Proceedings of the XXIX International Colloquium on Group-Theoretical Methods in Physics, edited by C. Bai, J.-P. Gazeau, and M. L. Ge, Nankai Series in Pure, Applied Mathematics and Theoretical Physics 11 (World Scientific, Singapore, 2013), p. 295.
  * [65] M. W. Newman, Independent Sets and Eigenspaces, Ph.D. thesis, University of Waterloo, 2004.
  * [66] M. Reck, A. Zeilinger, H. J. Bernstein, and P. Bertani, Experimental realization of any discrete unitary operator, Phys. Rev. Lett. 73, 58 (1994).
  * [67] W. R. Clements, P. C. Humphreys, B. J. Metcalf, W. S. Kolthammer, and I. A. Walmsley, Optimal design for universal multiport interferometers, Optica 3, 1460 (2016).
  * [68] M. C. Tichy, M. Tiersch, F. de Melo, F. Mintert, and A. Buchleitner, Zero-transmission law for multiport beam splitters, Phys. Rev. Lett. 104, 220405 (2010).
  * [69] A. Crespi, Suppression laws for multiparticle interference in Sylvester interferometers, Phys. Rev. A 91, 013811 (2015).
  * [70] N. Ito, Hadamard graphs. I, Graphs Comb. 1, 57 (1985).
  * [71] N. Ito, Hadamard graphs. II, Graphs Comb. 1, 331 (1985).
  * [72] G. Brassard, R. Cleve, and A. Tapp, The cost of exactly simulating quantum entanglement with classical communication, Phys. Rev. Lett. 83, 1874 (1999).
  * [73] V. Galliard, A. Tapp, and S. Wolf, Deterministic quantum non-locality and graph colorings, Theor. Comput. Sci. 486, 20 (2013).
  * [74] D. Avis, A quantum protocol to win the graph colouring game on all Hadamard graphs, IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 89, 1378 (2006).
  * [75] P. J. Cameron, A. Montanaro, M. W. Newman, S. Severini, and A. Winter, On the quantum chromatic number of a graph, Electron. J. Comb. 14, R81 (2007).
  * [76] G. Scarpa and S. Severini, Kochen-Specker sets and the rank-1 quantum chromatic number, IEEE Trans. Inf. Theory 58, 2524 (2012).
  * [77] L. Mančinska and D. E. Roberson, Quantum homomorphisms, J. Combin. Theory Ser. B 118, 228 (2016).
  * [78] P. Wocjan and C. Elphick, Spectral lower bounds for the orthogonal and projective ranks of a graph, Electron. J. Comb. 26, 3.45 (2019).
  * [79] P. Frankl, Orthogonal vectors in the $n$-dimensional cube and codes with missing distances, Combinatorica 6, 279 (1986).
  * [80] F. Ihringer and H. Tanaka, The independence number of the orthogonality graph in dimension $2^{k}$, Combinatorica 39, 1425 (2019).
  * [81] J. J. Sylvester, Thoughts on inverse orthogonal matrices, simultaneous sign successions, and tessellated pavements in two or more colours, with applications to Newton’s rule, ornamental tile-work, and the theory of numbers, Philos. Mag. 34, 461 (1867).
  * [82] R. E. A. C. Paley, On orthogonal matrices, J. Math. Phys. 4, 311 (1933).
  * [83] H. Kimura, Classification of Hadamard matrices of order 28, Discrete Math. 133, 171 (1994).
  * [84] B. D. McKay, Topics in Computational Graph Theory, Ph.D. thesis, University of Melburne, 1980.
  * [85] A. Cabello, M. Kleinmann, and C. Budroni, Necessary and sufficient condition for quantum state-independent contextuality, Phys. Rev. Lett. 114, 250402 (2015).
  * [86] D. E. Knuth, The sandwich theorem, Electron. J. Combin. 1, A1 (1994).
  * [87] R. J. Nowakowski and D. F. Rall, Associative graph products and their independence, domination and coloring numbers, Discuss. Math. Graph Theory 16, 53 (1996).
  * [88] D. Geller and S. Stahl, The chromatic number and other functions of the lexicographic product, J. Comb. Theory. Ser. B 19, 87 (1975).
  * [89] D. E. Roberson, Conic formulations of graph homomorphisms, J. Algebr. Comb. 43, 877 (2016).
  * [90] G. F. Royle, and C. E. Praeger, Constructing the vertex-transitive graphs of order 24, J. Symb. Comput. 8, 4 (1989).
  * [91] B. D. McKay and G. F. Royle, The transitive graphs with at most 26 vertices, Ars Combin. 30, 161 (1990).
  * [92] D. Holt and G. Royle, A census of small transitive groups and vertex-transitive graphs, J. Symb. Comput. 101, (2020).
  * [93] P. Potočnik, P. Spiga, and G. Verret, Cubic vertex-transitive graphs on up to 1280 vertices, J. Symb. Comput. 50, (2013).
  * [94] B. D. McKay, Graphs.
  * [95] L. Lovász, Graphs and Geometry, Institute of Mathematics, Ëotvös University, Budapest, 2019.
  * [96] Z.-P. Xu, X.-D. Yu, and M. Kleinmann, State-independent quantum contextuality with projectors of nonunit rank, New J. Phys. 23, 043025 (2021).
  * [97] A. Cabello, Converting contextuality into nonlocality, Phys. Rev. Lett. 127, 070401 (2021).
  * [98] S. Yu and C. H. Oh, State-independent proof of Kochen-Specker theorem with 13 rays, Phys. Rev. Lett. 108, 030402 (2012).
  * [99] A. Cabello, M. Kleinmann, and J. R. Portillo, Quantum state-independent contextuality requires 13 rays, J. Phys. A: Math. Theor. 49, 38LT01 (2016).
  * [100] A. Cabello, Á. Feito, and A. Lamas-Linares, Bell’s inequalities with realistic noise for polarization-entangled photons Phys. Rev. A 72, 052112 (2005).
  * [101] F. A. Bovino, G. Castagnoli, A. Cabello, and A. Lamas-Linares, Experimental noise-resistant Bell-inequality violations for polarization-entangled photons, Phys. Rev. A 73, 062110 (2006).
  * [102] N. Herrera Valencia, V. Srivastav, M. Pivoluska, M Huber, N. Friis, W. McCutcheon, and M. Malik, High-dimensional pixel entanglement: Efficient generation and certification, Quantum 4, 376 (2020).
  * [103] E. G. Gilbert, An iterative procedure for computing the minimum of a quadratic form on a convex set, J. SIAM Control 4, 61 (1966).
  * [104] A. Montina and S. Wolf, Discrimination of non-local correlations, Entropy 21, 104 (2019).
  * [105] J. Shang and O. Gühne, Convex optimization over classes of multiparticle entanglement, Phys. Rev. Lett. 120, 050506 (2018).
  * [106] P. Pandya, O. Sakarya, and M. Wieśniak, Hilbert-Schmidt distance and entanglement witnessing, Phys. Rev. A 102, 012409 (2020).
  * [107] J. R. Gonzales-Ureta, A. Predojević and A. Cabello, Optimal and tight Bell inequalities for state-independent contextuality sets, arXiv:2207.08850
  * [108] Z.-P. Xu, J. Steinberg, J. Singh, A. J. López-Tarrida, J. R. Portillo, and A. Cabello, Code to accompany Graph-theoretic approach to Bell experiments with low detection efficiency, https://gitlab.com/JoStei1996/symmetric_bell.