# Scalable Bell inequalities for graph states of arbitrary prime local
dimension and self-testing

Rafael Santos1 1Center for Theoretical Physics, Polish Academy of Sciences,
Aleja Lotników 32/46, 02-668 Warsaw, Poland
2 School of Physics, Indian Institute of Science Education and Research
Thiruvananthapuram, Kerala, India 695551
3Max-Planck-Institut für Quantenoptik, Hans-Kopfermann-Straße 1, 85748
Garching, Germany  Debashis Saha2 1Center for Theoretical Physics, Polish
Academy of Sciences, Aleja Lotników 32/46, 02-668 Warsaw, Poland
2 School of Physics, Indian Institute of Science Education and Research
Thiruvananthapuram, Kerala, India 695551
3Max-Planck-Institut für Quantenoptik, Hans-Kopfermann-Straße 1, 85748
Garching, Germany  Flavio Baccari3 1Center for Theoretical Physics, Polish
Academy of Sciences, Aleja Lotników 32/46, 02-668 Warsaw, Poland
2 School of Physics, Indian Institute of Science Education and Research
Thiruvananthapuram, Kerala, India 695551
3Max-Planck-Institut für Quantenoptik, Hans-Kopfermann-Straße 1, 85748
Garching, Germany  Remigiusz Augusiak1 1Center for Theoretical Physics, Polish
Academy of Sciences, Aleja Lotników 32/46, 02-668 Warsaw, Poland
2 School of Physics, Indian Institute of Science Education and Research
Thiruvananthapuram, Kerala, India 695551
3Max-Planck-Institut für Quantenoptik, Hans-Kopfermann-Straße 1, 85748
Garching, Germany

###### Abstract

Bell nonlocality—the existence of quantum correlations that cannot be
explained by classical means—is certainly one of the most striking features of
quantum mechanics. Its range of applications in device-independent protocols
is constantly growing. Many relevant quantum features can be inferred from
violations of Bell inequalities, including entanglement detection and
quantification, and state certification applicable to systems of arbitrary
number of particles. A complete characterisation of nonlocal correlations for
many-body systems is, however, a computationally intractable problem. Even if
one restricts the analysis to specific classes of states, no general method to
tailor Bell inequalities to be violated by a given state is known. In this
work we provide a general construction of Bell inequalities that are maximally
violated by graph states of any prime local dimension. These form a broad
class of multipartite quantum states that have many applications in quantum
information, including quantum error correction. We analytically determine
their maximal quantum violation, a number of high relevance for device-
independent applications of Bell inequalities. Finally, we show that these
inequalities can be used for self-testing of multi-qutrit graph states such as
the well-known four-qutrit absolutely maximally entangled state AME(4,3).

##  Introduction

The first Bell inequalities were introduced to show that certain predictions
of quantum theory cannot be explained by classical means [1]. In particular,
correlations obtained by performing local measurements on joint entangled
quantum states are able to violate Bell inequalities and hence cannot arise
from a local hidden variable model (LHV). The existence of such non-local
correlations is referred to as Bell non-locality or simply non-locality.

Since then the range of applications of Bell inequalities has become much
wider. In particular, they can be used for certification of certain relevant
quantum properties in a device-independent way, that is, under minimal
assumptions about the underlying quantum system. First, violation of Bell
inequalities can be used to certify the dimension of a quantum system [2] or
the amount of entanglement present in it [3]. Then, Bell violations are used
to certify that the outcomes of quantum measurements are truly random [4], and
to estimate the amount of generated randomness [5, 6, 7].

The maximum exponent of the certification power of Bell inequalities is known
as self-testing. Introduced in [8], self-testing allows for almost complete
characterization of the underlying quantum system based only on the observed
Bell violation. It thus appears to be one of the most accurate methods for
certification of quantum systems which makes self-testing a highly valuable
asset for the rapidly developing of quantum technologies. In fact, self-
testing techniques have shown to be amenable for near-term quantum devices,
allowing for a proof-of-principle state certification of up to few tens of
particles [9, 10]. For this reason self-testing has attracted a considerable
attention in recent years (see, e.g., Ref. [11]).

However, most of the above applications require Bell inequalities that exhibit
carefully crafted features. In the particular case of self-testing one needs
Bell inequalities whose maximal quantum values are achieved by the target
quantum state and measurements that one aims to certify. Deriving Bell
inequalities tailored to generic pure entangled states turns out to be in
general a difficult challenge. Even more so if one looks for inequalities
applicable to systems of arbitrary number of parties or arbitrary local
dimension. The standard geometric approach to derive Bell inequalities has
been successful in deriving many interesting and relevant inequalities [12,
13, 14, 15, 16], but typically fails to serve a self-testing purpose,
providing inequalities with unknown maximal quantum violation.

In order to construct Bell inequalities that are tailored to specific quantum
states, a more promising path is to exploit the ”quantum properties” of the
considered system such as its symmetries. Two proposals in this direction have
succeeded in designing different classes of Bell inequalities tailored to the
broad family of multi-qubit graph states [17, 18] and the first Bell
inequalities maximally violated by the maximally entangled state of any local
dimension [19]. The success of these methods was further confirmed by later
applications to design the first self-testing Bell inequalities for graph
states [17], for genuinely entangled stabilizer subspaces [20, 21] or
maximally entangled two-qutrit states [22], as well as to derive many other
classes of Bell inequalities tailored to two-qudit maximally entangled [23,
24] or many-qudit Greenberger-Horne-Zeilinger states [25]. Some of these
constructions were later exploited to provide self-testing schemes for the
maximally entangled [23, 26] or the GHZ states [27] of arbitrary local
dimension.

In this work we show that similar ideas can be used to provide a general
construction of Bell inequalities tailored to graph states of arbitrary prime
local dimension. Graph states constitute one of the most representative
classes of genuinely entangled multipartite quantum states considered in
quantum information, covering the well-known Greenberger-Horne-Zeilinger, the
cluster [28] or the absolutely maximally entangled states [29], that have
found numerous applications, e.g., in quantum computing [30, 31, 32] or
quantum metrology [33]. Interestingly, our construction provides the first
example of Bell inequalities maximally violated by the absolutely maximally
entangled states of non-qubit local dimension such as the four-qutrit AME(4,3)
state [29]. Moreover, it generalizes and unifies in a way the constructions of
Refs. [34] and [22] to graph states of arbitrary prime local dimension.

The manuscript is organized as follows. In Sec. 2 we provide some background
information which is necessary for further considerations; in particular we
explain in detail the notions of the multipartite Bell scenario and graph
states and also state the definition of self-testing we use in our work. Next,
in Sec. 3 we introduce our general construction of Bell inequalities for graph
states. We then show in Sec. 4 that our new Bell inequalities allow for self-
testing of all graph states of local dimension three. We conclude in Sec. 5
where we also provide a list of possible research directions for further
studies that follow from our work.

##  Preliminaries

###  2.1 Bell scenario and Bell inequalities

Let us begin by introducing some notions and terminology. We consider a
multipartite Bell scenario in which $N$ distant observers $A_{i}$ share a
quantum state $\rho$ defined on the product Hilbert space

$\mathcal{H}=\mathcal{H}_{1}\otimes\ldots\otimes\mathcal{H}_{N}.$ (1)

Each observer $A_{i}$ can perform one of $m_{i}$ measurements
$M_{x_{i}}^{i}\equiv\\{M_{a_{i}|x_{i}}^{i}\\}_{a_{i}}$ on their share of this
state, where $x_{i}$ stand for the measurement choices, whereas $a_{i}$ denote
the outcomes; here we label them as $x_{i}=1,\ldots,m$ and
$a_{i}=0,\ldots,d-1$, respectively. Recall that the measurement operators
satisfy $M_{a_{i}|x_{i}}^{i}\geq 0$ for any choice of $a_{i}$ and $x_{i}$ as
well as $\sum_{a_{i}}M_{a_{i}|x_{i}}^{i}=\mathbbm{1}$ for any $x_{i}$.

The observers repeat their measurements on the local parts of the state $\rho$
which creates correlations between the obtained outcomes. These are captured
by a collection of probability distributions
$\vec{p}\equiv\\{p(\vec{a}|\vec{x})\\}\in\mathbbm{R}^{(md)^{N}}$, where
$p(\vec{a}|\vec{x})\equiv p(a_{1},\ldots,a_{N}|x_{1},\ldots,x_{N})$ is the
probability of obtaining the outcome $a_{i}$ by the observer $i$ upon
performing the measurement $M_{x_{i}}^{i}$ and can be represented by the Born
rule

$p(\vec{a}|\vec{x})=\mathrm{Tr}\left[\rho\left(M_{a_{1}|x_{1}}^{1}\otimes\ldots\otimes
M_{a_{N}|x_{N}}^{N}\right)\right].$ (2)

A behaviour $\vec{p}$ is said to be local or classical if for any $\vec{a}$
and $\vec{x}$, the joint probabilities $p(\vec{a}|\vec{x})$ factorize in the
following sense,

$p(\vec{a}|\vec{x})=\sum_{\lambda}\mu(\lambda)p_{1}(a_{1}|x_{1},\lambda)\cdot\ldots\cdot
p_{N}(a_{N}|x_{N},\lambda),$ (3)

where $\lambda$ is a random variable with a probability distribution
$\mu(\lambda)$ representing the possibilities for the parties to share
classical correlations and $p_{i}(a_{i}|x_{i},\lambda)$ is an arbitrary
probability distribution corresponding to the observer $A_{i}$. On the other
hand, if a behavior $\vec{p}$ does not admit the above form, we call it Bell
non-local or simply non-local. In any Bell scenario correlations that are
classical in the above sense form a polytope with finite number of vertices,
denoted $L_{N,m,d}$.

Any non-local distribution $\vec{p}$ can be detected to be outside the local
polytope from the violation of a Bell inequality. The generic form of such
inequalities is

$I:=\sum_{\vec{a},\vec{x}}\alpha_{\vec{a},\vec{x}}\,p(\vec{a}|\vec{x})\leq\beta_{L},$
(4)

where $\beta_{L}=\max_{\vec{p}\in L_{N,m,d}}I$ is the classical bound of the
inequality and $\alpha_{\vec{a},\vec{x}}$ are some real coefficients defining
the inequality. Any $\vec{p}$ that violates a Bell inequality is detected as
non-local.

Let us finally introduce another number characterizing a Bell inequality—the
so-called quantum or Tsirelson’s bound—which is defined as

$\beta_{Q}=\sup_{\vec{p}\in Q_{N,m,d}}I,$ (5)

where the maximisation runs on all quantum behaviours, i.e., all distributions
$\vec{p}$ that can be obtained by performing quantum measurements on quantum
states of arbitrary local dimension. The set of quantum correlations
$Q_{N,m,d}$ is in general not closed [35] and thus $\beta_{Q}$ is a supremum
and not a strict maximum. Determining the quantum bound for a generic Bell
inequality is an extremely difficult problem. However, interestingly, in
certain cases it can still be found analytically. A way to obtain $\beta_{Q}$
or at least an upper bound on it is to find a sum-of-squares decomposition of
a Bell operator $\mathcal{B}$ corresponding to the Bell inequality. More
specifically, if for any choice of measurement operators one is able to
represent the Bell operator as

${\cal B}=\eta\mathbbm{1}-\sum_{k}P^{\dagger}_{k}P_{k},$ (6)

where $P_{k}$ are some operators composed of $M_{n_{i}|x_{i}}^{i}$, then
$\eta$ is an upper bound on $\beta_{Q}$. Indeed, Eq. (6) implies that for all
$|\psi\rangle$, $\langle\psi|{\cal B}|\psi\rangle\leqslant\eta$, and thus,
$\beta_{Q}\leq\eta$. If a quantum state saturates this upper bound, then it
follows from (6) that $P_{k}|\psi\rangle=0$ for all $k$. As we will see later
such relations are particularly useful to prove a self-testing statement from
the maximal violation of a Bell inequality.

For further convenience we also introduce an alternative description of the
Bell scenario in terms of generalized expectation values (see, e.g., Ref.
[25]). These are in general complex numbers defined through the
$N$-dimensional discrete Fourier transform of $\\{p(\vec{a}|\vec{x})\\}$,

$\langle A_{n_{1}|x_{1}}^{1}\ldots
A_{n_{N}|x_{N}}^{N}\rangle=\sum_{\vec{a}}\omega^{\vec{a}\cdot\vec{n}}p(\vec{a}|\vec{x}),$
(7)

where $\omega=\mathrm{exp}(2\pi\mathrm{i}/d)$ is the $d$th root of unity,
$\vec{a}:=(a_{1},\ldots,a_{N})\in\\{0,\ldots,d-1\\}^{N}$ and
$\vec{n}:=(n_{1},\ldots,n_{N})\in\\{0,\ldots,d-1\\}^{N}$, and
$\vec{a}\cdot\vec{n}=\sum_{i}a_{i}n_{i}$. The inverse transformation gives

$p(\vec{a}|\vec{x})=\frac{1}{d^{N}}\sum_{\vec{n}}\omega^{-\vec{a}\cdot\vec{n}}\langle
A_{n_{1}|x_{1}}^{1}\ldots A_{n_{N}|x_{N}}^{N}\rangle.$ (8)

Combining Eqs. (2) and (8) one finds that if the correlations $\vec{p}$ are
quantum, that is, originate from performing local measurements on composite
quantum states, the complex expectation values can be represented as

$\langle A_{n_{1}|x_{1}}^{1}\ldots
A_{n_{N}|x_{N}}^{N}\rangle=\mathrm{Tr}\left[\rho\left(A_{n_{1}|x_{1}}^{1}\otimes\ldots\otimes
A_{n_{N}|x_{N}}^{N}\right)\right],$ (9)

where $A_{n_{i}|x_{i}}^{i}$ are simply Fourier transforms of the measurement
operators $M_{a_{i}|x_{i}}^{i}$ given by

$A_{n_{i}|x_{i}}^{i}=\sum_{a_{i}=0}^{d-1}\omega^{n_{i}a_{i}}M_{a_{i}|x_{i}}^{i}.$
(10)

Clearly, due to the fact that the Fourier transform is invertible, for a given
$x_{i}$ and $i$, the $d$ operators $A_{n_{i}|x_{i}}^{i}$ with
$n_{i}=0,\ldots,d-1$ uniquely represent the corresponding measurement
$M_{x_{i}}^{i}$.

Let us now discuss a few properties of the Fourier-transformed measurement
operators that will prove very useful later. For clarity of the presentation
we consider a single quantum measurement $M=\\{M_{a}\\}$ and the corresponding
$A_{n}$ operators obtained via Eq. (10). First, one easily finds that
$A_{0}=\mathbbm{1}$. Second,

$A_{d-n}=A_{-n}=A_{n}^{\dagger}$ (11)

which is a consequence of the fact that
$\omega^{d-n}=\omega^{-n}=(\omega^{n})^{*}$ holds true for any
$n\in\\{0,\ldots,d-1\\}$. Third, $A_{n}^{\dagger}A_{n}\leq\mathbbm{1}$ for any
$n=0,\ldots,d-1$ (for a proof see Ref. [22]).

Let us finally mention that if $M$ is projective then all $A_{n}$ are unitary
and their eigenvalues are simply powers of $\omega$; equivalently
$A_{n}^{d}=\mathbbm{1}$. It is also not difficult to see that in such a case,
$A_{n}$ are operator powers of $A_{1}$, that is, $A_{n}=A_{1}^{n}$. In this
way we recover a known fact that a projective measurement can be represented
by a single observable. We exploit these properties later in our construction
of Bell inequalities as well as in deriving the self-testing statement. In
fact, in what follows we denote the observables measured by the party $i$ by
$A_{i,x_{i}}$.

###  2.2 Self-testing

Here we introduce the definition of $N$-partite self-testing that we adopt in
this work. Let us consider again the Bell scenario described above, assuming,
however, that the shared state $\rho$, the Hilbert space it acts on as well as
the local measurements are all unknown. The aim of the parties is to deduce
their form from the observed correlations $p(\vec{a}|\vec{x})$. Since the
dimension of the joint Hilbert space $\mathcal{H}$ is now unconstrained
(although finite) we can simplify the latter problem by assuming that the
shared state is pure, i.e., $\rho=|\psi\rangle\\!\langle\psi|$ for some
$|\psi\rangle\in\mathcal{H}$, and the measurements are projective, in which
case they are represented by unitary observables $A_{i,x_{i}}$ acting on
$\mathcal{H}_{i}$.

Consider then a target state $|\hat{\psi}\rangle\in(\mathbb{C}^{d})^{\otimes
N}$ and the corresponding measurements $\hat{A}_{i,x_{i}}$, giving rise to the
same behaviour $\\{p(\vec{a}|\vec{x})\\}$. We say that the observed
correlations self-test the given state and measurements if the following
definition applies.

######  Definition 1.

If from the observed correlations $\\{p(\vec{a}|\vec{x})\\}$ one can identify
a qudit in each local Hilbert space in the sense that
$\mathcal{H}_{i}=\mathbbm{C}^{d}\otimes\mathcal{H}_{i}^{\prime}$ for some
auxiliary Hilbert space $\mathcal{H}_{i}^{\prime}$, and also deduce the
existence of local unitary operations
$U_{i}:\mathcal{H}_{i}\to\mathbbm{C}^{d}\otimes\mathcal{H}_{i}^{\prime}$ such
that

$(U_{1}\otimes\ldots\otimes
U_{N})|\psi\rangle=|\hat{\psi}\rangle\otimes|\mathrm{aux}\rangle$ (12)

for some
$|\mathrm{aux}\rangle\in\mathcal{H}_{i}^{\prime}\otimes\ldots\otimes\mathcal{H}_{N}^{\prime}$,
and, moreover,

$U_{i}\,A_{i,x_{i}}\,U_{i}^{\dagger}=\hat{A}_{i,x_{i}}\otimes\mathbbm{1}_{i},$
(13)

where $\mathbbm{1}_{i}$ is the identity acting on $\mathcal{H}^{\prime}_{i}$,
then we say that the reference quantum state $|\hat{\psi}\rangle$ and
measurements $\hat{A}_{i,x_{i}}$ have been self-tested in the experiment.

Importantly, only non-local correlations can give rise to a valid self-testing
statement. Moreover, since it is based only on the observed correlations
$\\{p(\vec{a}|\vec{x})\\}$, self-testing can characterize the state and the
measurements only up to certain equivalences. In particular, the statement
above includes all possible operations that keep the correlations
$\\{p(\vec{a}|\vec{x})\\}$ unchanged, such as: (i) the addition of an
auxiliary state $|\mathrm{aux}\rangle$ on which the measurements act trivially
and (ii) the rotation by an arbitrary local unitary operations. It is also not
difficult to check that $\\{p(\vec{a}|\vec{x})\\}$ does not change if one
applies the transposition map to the quantum state as well as all the
observables, and thus sometimes one needs to take into account this extra
degree of freedom, which leads to a slightly weaker definition of self-testing
[22, 36]. In the present case, since the graph states are all real the
transposition does not pose any problem as far as the state self-testing is
concerned, yet it does for the measurements.

###  2.3 Graph states

Let us finally recall the definition of multipartite graph states of prime
local dimension [37, 38, 39]. Consider a graph
$\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{R},d)$, where $d$ is any prime
number such that $d\geq 2$, $\mathcal{V}:=\\{1,\ldots,N\\}$ is the set of
vertices of the graph, $\mathcal{E}$ is the set of edges connecting vertices,
and $\mathcal{R}:=\\{r_{i,j}\\}$ is a set of natural numbers from
$\\{0,\ldots,d-1\\}$ specifying the number of edges connecting vertices
$i,j\in\mathcal{V}$; in particular, $r_{i,j}=0$ means there is no edge between
$i$ and $j$. We additionally assume that $r_{i,i}=0$ for all $i$, meaning that
the graph has no loops as well as that the graph $\mathcal{G}$ is connected,
meaning that it does not have any isolated vertices. By $\mathcal{N}_{i}$ we
denote the neighbourhood of the vertex $i$ which consists of all elements of
$\mathcal{V}$ that are connected to $i$.

Assume then that each vertex $i\in\mathcal{V}$ of the graph corresponds to a
single quantum system held by the party $A_{i}$ and let us associate to it the
following $N$-qudit operator

$G_{i}=X_{i}\otimes\bigotimes_{j\in\mathcal{N}_{i}}Z_{j}^{r_{ij}}\qquad(i=1,\ldots,N)$
(14)

with $X$ and $Z$ being the generalizations of the qubit Pauli matrices to
$d$-dimensional Hilbert spaces defined via the following relations

$Z|i\rangle=\omega^{i}|i\rangle,\qquad
X|i\rangle=|i+1\rangle\qquad(i=0,\ldots,d-1),$ (15)

where the addition is modulo $d$. Due to the fact that $XZ=\omega^{-1}ZX$, it
is not difficult to see that the operators $G_{i}$ mutually commute. It then
follows that there is a unique pure state
$|G\rangle\in(\mathbbm{C}^{d})^{\otimes N}$, called graph state, which is a
common eigenstate of all $G_{i}$ corresponding to the eigenvalue one, i.e.,

$G_{i}|G\rangle=|G\rangle\qquad(i=1,\ldots,N).$ (16)

Given the above property, the $G_{i}$ are usually referred to as stabilizing
operators. Notice also that in the particular case of $d=2$ this construction
naturally reproduces the $N$-qubit graph states [39], where vertices can only
be connected by single edges.

Let us illustrate the above construction with a couple of examples.

#### Example 1: Maximally entangled two-qudit state.

Let us start with the simplest possible graph, consisting of two vertices
connected by an edge (cf. Fig. 1(a)). The corresponding generators are given
by

$G_{1}=X\otimes Z,\qquad G_{2}=Z\otimes X,$ (17)

and stabilize a single state in $\mathbbm{C}^{d}\otimes\mathbbm{C}^{d}$ which
is equivalent up to local unitary operations to the maximally entangled state
of two qudits,

$|\psi_{d}^{+}\rangle=\frac{1}{\sqrt{d}}\sum_{i=0}^{d-1}|ii\rangle$ (18)

in which both local Schmidt bases are the computational one. In fact, the
above state is stabilized by another pair of operators, namely,

$G^{\prime}_{1}=X\otimes X,\qquad G^{\prime}_{2}=Z\otimes Z^{\dagger},$ (19)

which are obtained from $G_{i}$ by an application of the Fourier matrix to the
second site.

#### Example 2: GHZ state.

The above two-vertex graph naturally generalizes to a star graph consisting of
$N$ vertices (cf. Fig. 1(b)). The associated generators are of the form

$G_{1}=X_{1}Z_{2}\ldots Z_{N}$ (20)

and

$G_{i}=Z_{1}X_{i}\qquad(i=2,\ldots,N),$ (21)

and stabilize an $N$-qudit state which is equivalent under local unitary
operations to the well-known Greenberger-Horne-Zeilinger (GHZ) state

$|\mathrm{GHZ}_{N,d}\rangle=\frac{1}{\sqrt{d}}\sum_{i=0}^{d-1}|i\rangle^{\otimes
N}.$ (22)

Figure 1: Three examples of graphs defining: (a) the maximally entangled state
of two qudits, (b) the $N$-qudit GHZ state, (c) the four-qutrit absolutely
maximally entangled state AME(4,3).

#### Example 3: AME(4,3).

The third and the last example is concerned with the four-qutrit absolutely
maximally entangled state111A multipartite state is termed absolutely
maximally entangled if any of its $\lfloor N/2\rfloor$-partite subsystems is
in the maximally mixed state [40]., named AME(4,3) [29]. The graph defining it
is presented in Fig. 1(c). The stabilizing operators corresponding to this
graph read

$G_{1}=X_{1}Z_{2}Z_{4},\qquad G_{2}=Z_{1}X_{2}Z_{3},\qquad
G_{3}=Z_{2}X_{3}Z_{4}^{2},\qquad G_{4}=Z_{1}Z_{3}^{2}X_{4}.$ (23)

They stabilize a three-qutrit maximally entangled state AME(4,3) which is
equivalent under local unitary operations and relabelling of the subsystems to
(see, e.g., Ref. [41]),

$|\mathrm{AME}(4,3)\rangle=\frac{1}{3}\sum_{i,j=0}^{2}|i\rangle|j\rangle|i+j\rangle|i+2j\rangle,$
(24)

where the addition is modulo three.

##  Construction of Bell inequalities for arbitrary graph states of prime
local dimension

Here we present our first main result: a general construction of Bell
inequalities whose maximal quantum value is achieved by the $N$-qudit graph
states of arbitrary prime local dimension and quantum observables
corresponding to mutually unbiased bases at every site. Our construction is
inspired by the recent approach to construct CHSH-like Bell inequalities for
the $N$-qubit graph states presented in Ref. [34] and by another construction
of Bell inequalities maximally violated by the maximally entangled two-qudit
state introduced in Ref. [22].

First, in Sec. 3.1 we recall the general class of Bell inequalities maximally
violated by $N$-qubit graph states of Ref. [34]. Then, in Sec. 3.2 we
introduce the main building block to generalise this construction to arbitrary
prime dimension. We illustrate the Bell inequality construction with some
simple examples in Sec. 3.3 and then move to introduce the general form of the
inequality valid of any $N$-qudit graph state of prime dimension in Sec. 3.4.

###  3.1 Multiqubit graph states

Let us assume that $d=2$ and let us consider a graph $\mathcal{G}$. Without
any loss of generality we can assume that a vertex with the largest
neighbourhood is the first one, that is,
$N_{1}=\max_{i=1,\ldots,N}|\mathcal{N}_{i}|$. If there are many vertices with
the maximal neighbourhood in $\mathcal{G}$, we are free to choose any of them
as the first one.

To every generator $G_{i}$ we associate an expectation value in which the $X$
and $Z$ Pauli matrices are replaced by quantum observables or their
combinations using the following rule. At the first qubit we make the
following assignment,

$X\to\frac{1}{\sqrt{2}}(A_{1,0}+A_{1,1}),\qquad
Z\to\frac{1}{\sqrt{2}}(A_{0,1}-A_{1,1}),$ (25)

whereas the Pauli matrices at the remaining sites are directly replaced by
observables, that is,

$X\to A_{i,0},\qquad Z\to A_{i,1}$ (26)

with $i=2,\ldots,N$. Recall that the first index enumerates the parties, while
the second one measurement choices. This procedure gives us $N$ expectation
values which after being combined altogether lead us to the following Bell
inequality [34]:

$\displaystyle I_{G}$ $\displaystyle:=$
$\displaystyle\frac{N_{1}}{\sqrt{2}}\left\langle(A_{1,0}+A_{1,1})\prod_{i\in\mathcal{N}(1)}A_{i,1}\right\rangle+\frac{1}{\sqrt{2}}\sum_{i\in\mathcal{N}(1)}\left\langle(A_{1,0}-A_{1,1})A_{i,0}\prod_{j\in\mathcal{N}(1)\setminus\\{1\\}}A_{j,1}\right\rangle$
(27) $\displaystyle+\sum_{i\notin\mathcal{N}(1)\cup\\{1\\}}\left\langle
A_{i,0}\prod_{j\in\mathcal{N}(i)}A_{j,1}\right\rangle\leq\beta_{C}^{G},$

where the classical bound can directly be determined for any graph $G$ and is
given by $\beta_{C}^{G}=N+(\sqrt{2}-1)N_{1}-1$. More importantly, the maximal
quantum value can also be analytically computed for any graph and amounts to
$\beta_{Q}^{G}=N+N_{1}-1$. This value is achieved by the graph state
$|G\rangle\in(\mathbbm{C}^{2})^{\otimes N}$ corresponding to the graph
$\mathcal{G}$ and the following observables:

$A_{1,0}=\frac{1}{\sqrt{2}}(X+Z),\qquad A_{1,1}=\frac{1}{\sqrt{2}}(X-Z)$ (28)

for the first observer and $A_{i,0}=X$ and $A_{i,1}=Z$ for the remaining
observers $i=2,\ldots,N$.

It is worth stressing here that one of the key observations making the
construction of Ref. [34] work is that for any graph there exists a choice of
observables at any site, given by the above formulas, turning the quantum
operators appearing in the expectation values of (27) into the stabilizing
operators $G_{i}$; in particular, it is a well-known fact that combinations of
the Pauli matrices in Eq. (28) are proper quantum observables with eigenvalues
$\pm 1$.

###  3.2 Replacement rule for operators of arbitrary prime dimension

We now move on to introduce the main ingredient needed to generalise the above
construction to graph states of prime local dimension $d\geq 3$.

A naive approach to constructing Bell inequalities for graph states of higher
local dimensions would be to directly follow the $d=2$ strategy. That is, at a
chosen site the $X$ and $Z$ operators are replaced by combinations of general
$d$-outcome observables $A_{0}$ and $A_{1}$. However, this simple approach
fails to work beyond $d=3$ because for any prime $d\geq 3$ it is impossible
find nonzero complex numbers $\alpha,\beta\in\mathbbm{C}$ for which

$O=\alpha X+\beta Z,$ (29)

is a valid quantum observable; in fact, for no complex numbers the above
combinations can be unitary, unless $d=2$ (cf. Fact 2 in Appendix A). This
makes the transformation (28) irreversible. Phrasing differently, there are no
unitary observables $A_{0}$ and $A_{1}$ such that $X=\alpha A_{0}+\beta A_{1}$
and $Z=\delta A_{0}+\gamma A_{1}$ for some complex numbers
$\alpha,\beta,\gamma,\delta\in\mathbbm{C}$.

Nevertheless, there exist other sets of $d$-outcome quantum observables which
can be linearly combined to form quantum observables, and thus are convenient
for our purposes. One such choice is the following set of $d$ unitary matrices

$O_{k}:=XZ^{k}\qquad(k=0,\ldots,d-1).$ (30)

It is not difficult to check that $O_{k}^{d}=\mathbbm{1}_{d}$ for any
$k=0,\ldots,d-1$ and prime $d$, meaning that the eigenvalues of each of these
unitary matrices belong to the set $\\{1,\omega,\ldots,\omega^{d-1}\\}$, and
thus are proper $d$-outcome observables in our formalism. It is also worth
mentioning that for any prime $d\geq 2$ their eigenvectors together with the
standard basis in $\mathbbm{C}^{d}$ form $d+1$ mutually unbiased bases.

Let us now assume that $d$ is a prime number greater than two ($d\geq 3$) and
consider the following linear combinations of $O_{k}$ and their powers,

$\displaystyle\overline{O}_{x}^{(n)}=\frac{\lambda_{n}}{\sqrt{d}}\sum^{d-1}_{k=0}\omega^{nxk}\omega^{nk(k+1)}O_{k}^{n},$
(31)

where $x=0,1,\ldots,d-1$ and $\lambda_{n}$ are complex coefficients defined as
[22]:

$\lambda_{n}=\left[\varepsilon_{d}\left(\frac{n}{d}\right)\right]^{-1}\omega^{-g(n,d)/48},$
(32)

where

$\varepsilon_{d}:=\left\\{\begin{array}[]{ll}1,&\quad\mathrm{if}\quad d\equiv
1\mod 4,\\\\[4.30554pt] \mathbbm{i},&\quad\mathrm{if}\quad d\equiv 3\mod
4.\end{array}\right.$ (33)

$\left(\frac{n}{d}\right)$ is the Legendre symbol222Recall that the Legendre
symbol $\left(\frac{n}{d}\right)$ equals $+1$ if $n$ is a quadratic residue
modulo $d$ and $-1$ otherwise, and, finally, the coefficients $g(n,d)$ are
given by

$g(n,d)=\left\\{\begin{array}[]{lll}n[n^{2}-d(d+6)+3]&\mbox{if}&n\equiv
0\mbox{ mod 2 and }n+d+1/2\equiv 0\mbox{ mod 2,}\\\\[4.30554pt]
n[n^{2}-d(d-6)+3]&\mbox{if}&n\equiv 0\mbox{ mod 2 and }n+d+1/2\equiv 1\mbox{
mod 2,}\\\\[4.30554pt] n(n^{2}+3)+2d^{2}(-5n+3)&\mbox{if}&n\equiv 1\mbox{ mod
4,}\\\\[4.30554pt] n(n^{2}+3)+2d^{2}(n+3)&\mbox{if}&n\equiv 3\mbox{ mod
4.}\end{array}\right.$ (34)

Importantly, it was proven in Ref. [22] (see Appendix D therein) that
$\overline{O}_{x}^{(n)}$ are unitary and satisfy

$\left[\overline{O}_{x}^{(n)}\right]^{d}=\mathbbm{1}_{d}$ (35)

for any $x=0,\ldots,d-1$ and $n=1,\ldots,d-1$. What is more,
$\overline{O}_{x}^{(n)}$ turns out to be the $n$th power of
$\overline{O}_{x}$, that is, $\overline{O}_{x}^{(n)}=[\overline{O}_{x}]^{n}$.
All this means that for any $x$ the set
$\\{\overline{O}_{x}^{(n)}\\}_{n=0,\ldots,d-1}$ represents a legitimate
$d$-outcome projective quantum measurement. Let us finally mention that the
linear transformation (31) can be inverted, giving

$O^{n}_{l}=\frac{\omega^{-nl(l+1)}}{\sqrt{d}\,\lambda_{n}}\sum^{d-1}_{x=0}\omega^{-nxl}\,\overline{O}_{x}^{(n)}.$
(36)

The fact that both $O_{k}$ and $\overline{O}_{k}$ are unitary quantum
observables that are related by a linear reversible transformation given by
Eqs. (31) and (36) is the key ingredient in our construction. That is, we can
proceed in analogy to $d=2$ case, where we used the replacement defined in Eq.
(25) to define the Bell inequality and we could later reverse it by a suitable
choice of quantum observables (28) to obtain the maximal quantum violation
with a graph state.

The replacement rule we use for the case of arbitrary prime dimension becomes:

$\left(XZ^{k}\right)^{n}\,\to\,\widetilde{A}^{(n)}_{k}:=\frac{\omega^{-nk(k+1)}}{\sqrt{d}\,\lambda_{n}}\sum^{d-1}_{t=0}\omega^{-ntk}A_{t}^{n},$
(37)

where $A_{t}$ with $t=0,\ldots,d-1$ are unitary observables. Notice that since
we deal now with $d$-outcome quantum measurements we need to also take into
account the powers $n$ of the corresponding observables. In fact, these under
the Fourier transform represent the outcomes of projective measurements.

Crucially, this transformation can be inverted in the sense that there exist a
choice of observables $A_{i,t}$,

$A_{t}^{n}=\frac{\lambda_{n}}{\sqrt{d}}\sum_{k=0}^{d-1}\omega^{ntk}\omega^{nk(k+1)}\left(XZ^{k}\right)^{n}.$
(38)

for which $\widetilde{A}_{k}^{(n)}$ in Eq. (37) can be brought back to
$XZ^{k}$.

These new operators $\widetilde{A}^{(n)}_{k}$ satisfy the following relations
(see Fact 3 in Appendix A for a proof):

$\left(\widetilde{A}^{(n)}_{k}\right)^{\dagger}=\widetilde{A}^{(d-n)}_{k}=\widetilde{A}^{(-n)}_{k}$
(39)

for any pair $n,k=0,\ldots,d-1$, and

$\sum^{d-1}_{k=0}\widetilde{A}^{(d-n)}_{k}\widetilde{A}^{(n)}_{k}=d\mathbbm{1}$
(40)

for any $n=0,\ldots,d-1$.

###  3.3 Examples

Before presenting our construction in full generality, let us first illustrate
how to use the qudit replacement rule to obtain valid Bell inequalities
tailored to graph states by means of two examples.

#### Example 1: AME(4,3).

As mentioned in Sec. 2.3, the the four-qutrit absolutely maximally entangled
state is a graph state corresponding to the graph presented on Fig. 1. The
stabilizing operators defining this state are given in Eq. (23). We recall
them here

$G_{1}=X_{1}Z_{2}Z_{4},\qquad G_{2}=Z_{1}X_{2}Z_{3},\qquad
G_{3}=Z_{2}X_{3}Z_{4}^{2},\qquad G_{4}=Z_{1}Z_{3}^{2}X_{4}.$ (41)

Since the neighbourhood of all vertices of this graph is of size two, each
vertex is equally good to implement the transformation (37). For simplicity we
choose it to be the first site. Moreover, as in the previous example, we
denote the observables measured by the four parties as $A_{x}$, $B_{y}$, etc.

Now, to create the set of matrices $XZ^{k}$ [necessary for the transformation
(37)] at the first site we consider the stabilizing operators $G_{1}$,
$G_{1}G_{2}$, and $G_{1}G_{2}^{2}$. These are, however, insufficient to
uniquely define $|\mathrm{AME}(4,3)\rangle$ as they do not include $G_{3}$ and
$G_{4}$. Since $G_{3}$ has the identity at the first position we can include
it as it is, whereas we need to take a product of $G_{4}$ with $G_{1}$ to
create $XZ$ at the first site. As a result, the final set of stabilizing
operators which we use to construct a Bell inequality for
$|\mathrm{AME}(4,3)\rangle$ consists of

$\displaystyle G_{1}$ $\displaystyle\\!\\!\\!=\\!\\!\\!$ $\displaystyle
X\otimes Z\otimes\mathbbm{1}\otimes Z,$ $\displaystyle G_{1}G_{2}$
$\displaystyle\\!\\!\\!=\\!\\!\\!$ $\displaystyle XZ\otimes ZX\otimes Z\otimes
Z,$ $\displaystyle G_{1}G_{2}^{2}$ $\displaystyle\\!\\!\\!=\\!\\!\\!$
$\displaystyle XZ^{2}\otimes ZX^{2}\otimes Z^{2}\otimes Z,$ $\displaystyle
G_{3}$ $\displaystyle\\!\\!\\!=\\!\\!\\!$ $\displaystyle\mathbbm{1}\otimes
Z\otimes X\otimes Z^{2}$ $\displaystyle G_{1}G_{4}$
$\displaystyle\\!\\!\\!=\\!\\!\\!$ $\displaystyle XZ\otimes Z\otimes
Z^{2}\otimes ZX.$ (42)

Now, to each of these stabilizing operators we associate an expectation value
in which particular matrices are replaced by quantum observables or their
combinations. For pedagogical purposes, let us do it site by site. As already
mentioned, at the first site we use Eq. (37) which for $d=3$ gives

$\displaystyle X$ $\displaystyle\to$
$\displaystyle\widetilde{A}_{0}:=\frac{1}{\sqrt{3}\,\lambda_{1}}\left(A_{0}+A_{1}+A_{2}\right),$
$\displaystyle XZ$ $\displaystyle\to$
$\displaystyle\widetilde{A}_{1}:=\frac{1}{\sqrt{3}\,\lambda_{1}\omega}\left(A_{0}+\omega^{-1}A_{1}+\omega^{-2}A_{2}\right),$
$\displaystyle XZ^{2}$ $\displaystyle\to$
$\displaystyle\widetilde{A}_{2}:=\frac{1}{\sqrt{3}\,\lambda_{1}}\left(A_{0}+\omega^{-2}A_{1}+\omega^{-1}A_{2}\right),$
(43)

where
$\lambda_{1}=-\mathrm{i}\omega^{2/3}=\omega^{1/12}=\mathrm{exp}(\pi\mathbbm{i}/18)$
and $\lambda_{2}=\lambda_{1}^{*}$ [cf. Eqs. (32), (33) and (34)] and we
denoted for simplicity $\widetilde{A}_{i}\equiv\widetilde{A}_{i}^{(1)}$. We
dropped the subscript $n$ appearing in the transformation (37) because for
$n=2$ one has $(XZ^{k})^{2}=(XZ^{k})^{\dagger}$ for $k=0,1,2$ and
$\widetilde{A}_{i}^{(2)}=\widetilde{A}_{i}^{\dagger}$ [cf. Eq. (39)];
nevertheless, we need to take into account the case $n=2$ when constructing
the Bell inequality.

We then note that at the second site we also have three independent unitary
observables [note that $(ZX)^{3}=(ZX^{2})^{3}=\mathbbm{1}$] and therefore we
can directly substitute

$Z\to B_{0},\qquad ZX\to B_{1},\qquad ZX^{2}\to B_{2}.$ (44)

At the third site we have $Z$, $Z^{2}$ which represent a single measurement
(cf. Sec. 2.1), and $X$ which is independent of the other two. We thus
substitute $Z^{k}\to C_{0}^{k}$ with $k=1,2$ and $X\to C_{1}$. Analogously,
for the fourth party we have $Z\to D_{0}$ and $ZX\to D_{1}.$

Taking all the above substitutions into account we arrive at the following
assignments

$\displaystyle G_{1}$ $\displaystyle\to$
$\displaystyle\langle\widetilde{A}^{(1)}_{0}B_{0}D_{0}\rangle,\qquad
G_{1}G_{2}\to\langle\widetilde{A}_{1}^{(1)}B_{1}C_{0}D_{0}\rangle,\qquad
G_{1}G_{2}^{2}\to\langle\widetilde{A}_{2}^{(1)}B_{2}C_{0}^{2}D_{0}\rangle,$
(45) $G_{1}G_{4}\to\langle\widetilde{A}_{1}^{(1)}B_{0}C_{0}^{2}D_{1}\rangle,$
(46)

and for $G_{3}$:

$G_{3}\to\langle B_{0}C_{1}D_{0}\rangle.$ (47)

Notice that the expectation values corresponding to $n=2$ in the assignment
(37) are simply complex conjugations of the above ones. By adding all the
obtained expectation values, we finally obtain a Bell inequality of the form

$\displaystyle I_{\mathrm{AME}}$ $\displaystyle:=$
$\displaystyle\frac{1}{\sqrt{3}\,\lambda_{1}}\left[\langle(A_{0}+A_{1}+A_{2})B_{0}D_{0}\rangle+\langle(A_{0}+\omega^{2}A_{1}+\omega
A_{2})B_{2}C_{0}^{2}D_{0}\rangle\right]$ (48)
$\displaystyle+\frac{1}{2\sqrt{3}\,\lambda_{1}\omega}\left[\langle(A_{0}+\omega
A_{1}+\omega^{2}A_{2})B_{1}C_{0}D_{0}\rangle+\langle(A_{0}+\omega
A_{1}+\omega^{2}A_{2})B_{0}C_{0}^{2}D_{1}\rangle\right]$
$\displaystyle+\langle
B_{0}C_{1}D_{0}\rangle+c.c.\leq\beta_{\mathrm{AME}}^{C},$

where c.c. stands for the complex conjugation of all five terms and represents
the expectation values obtained for the case $n=2$ of the assignment (37); in
particular, it makes the Bell expression real. Moreover, the second line comes
with $1/2$ coefficient for reasons that will become clear later. The classical
value in this case is

$\beta_{\mathrm{AME}}^{C}=7.63816.$ (49)

Let us prove that the maximal quantum violation of this inequality is
$\beta_{\mathrm{AME}}^{Q}=8$. First, denoting by $\mathcal{B}_{\mathrm{AME}}$
a Bell operator constructed from $I_{\mathrm{AME}}$, we can write the
following sum-of-squares decomposition

$\displaystyle 8\mathbbm{1}-\mathcal{B}_{\mathrm{AME}}$
$\displaystyle\\!\\!\\!=\\!\\!\\!$
$\displaystyle(\mathbbm{1}-\widetilde{A}_{0}B_{0}D_{0})^{\dagger}(\mathbbm{1}-\widetilde{A}_{0}B_{0}D_{0})+(\mathbbm{1}-\widetilde{A}_{2}B_{2}C_{0}^{2}D_{0})^{\dagger}(\mathbbm{1}-\widetilde{A}_{2}B_{2}C_{0}^{2}D_{0})$
(50)
$\displaystyle+\frac{1}{2}(\mathbbm{1}-\widetilde{A}_{1}B_{1}C_{0}D_{0})^{\dagger}(\mathbbm{1}-\widetilde{A}_{1}B_{1}C_{0}D_{0})+\frac{1}{2}(\mathbbm{1}-\widetilde{A}_{1}B_{0}C_{0}^{2}D_{1})^{\dagger}(\mathbbm{1}-\widetilde{A}_{1}B_{0}C_{0}^{2}D_{1})$
$\displaystyle+(\mathbbm{1}-B_{0}C_{1}D_{0})^{\dagger}(\mathbbm{1}-B_{0}C_{1}D_{0}),$

where $A_{x}$, $B_{y}$, etc. are arbitrary three-outcome unitary observables.
To prove that this decomposition holds true one simply expands its right-hand
side and uses the property [cf. Eq. (40)], which in the particular case $d=3$
reads,

$\widetilde{A}_{0}^{\dagger}\widetilde{A}_{0}+\widetilde{A}_{1}^{\dagger}\widetilde{A}_{1}+\widetilde{A}_{2}^{\dagger}\widetilde{A}_{2}=3\mathbbm{1}.$
(51)

Now it becomes clear why the second line of $I_{\mathrm{AME}}$ comes with
$1/2$.

From this decomposition we immediately conclude that
$8\mathbbm{1}-\mathcal{B}_{\mathrm{AME}}\geq 0$ for any choice of the local
observables, which implies that also for any state $|\psi\rangle$,
$\langle\psi|\mathcal{B}_{\mathrm{AME}}|\psi\rangle\leq 8$. To show that this
bound is tight it suffices to provide a quantum realisation achieving it. Such
a realisation can be constructed by inverting the transformation in Eqs. (3.3)
and (44), that is, by taking

$A_{x}=\frac{\lambda_{1}}{\sqrt{3}}\sum_{k=0}^{2}\omega^{xk}\omega^{k(k+1)}O_{k}\qquad(i=0,1,2),$
(52)

and $B_{y}=ZX^{y}$ with $y=0,1,2$, $C_{0}=Z$ and $C_{1}=X$, and $D_{w}=ZX^{w}$
with $w=0,1$, we can bring the Bell operator $\mathcal{B}_{\mathrm{AME}}$ to

$\mathcal{B}_{\mathrm{AME}}=G_{1}+G_{1}G_{2}^{2}+\frac{1}{2}(G_{1}G_{2}+G_{1}G_{4})+G_{3}+h.c.,$
(53)

which is simply a sum of the stabilizing operators of
$|\mathrm{AME(4,3)}\rangle$. As a result, the latter achieves the maximal
quantum value of the Bell inequality (48).

#### Example 2: Two-qudit maximally entangled state.

Let us then consider the case of arbitrary prime $d$ and construct Bell
inequalities for the simplest graph state which is the maximally entangled
state (18) stabilized by the two generators given in Eq. (19).

Since we are now concerned with the bipartite scenario we can denote the
observables measured by the parties by $A_{x}$ and $B_{y}$; the numbers of
observables on both sites will be specified later. As already explained, to
construct Bell inequalities we cannot simply use the replacement (25), we
rather need to employ the one in Eq. (37). Let us moreover assume that we
implement this transformation at Alice’s site.

To be able to apply the above assignments, we need to consider a larger set of
stabilizing operators which apart from $X$ and $Z^{k}$ operators contain also
$(XZ^{k})^{n}$ with $k=0,\ldots,d-1$ and $n=1,\ldots,d-1$. To construct such a
set one can for instance take the following products of $G_{i}^{\prime}$ given
in Eq. (19):

$G_{1}^{\prime}(G_{2}^{\prime})^{k}=XZ^{k}\otimes
XZ^{-k}\qquad(k=0,1,\ldots,d-1).$ (54)

However, to take into account all the outcomes of the measurements performed
by both parties we need to also include the powers of the above stabilizing
operators [cf. Sec. 2.1] which leads us to the following $d(d-1)$ stabilizing
operators of $|\psi_{d}^{+}\rangle$:

$\mathcal{G}^{n}_{k}:=\left[G_{1}^{\prime}(G_{2}^{\prime})^{k}\right]^{n}=\left(XZ^{k}\right)^{n}\otimes\left(XZ^{-k}\right)^{n}\qquad(k=0,\ldots,d-1;\,n=1,\ldots,d-1).$
(55)

We can now construct Bell inequalities maximally violated by the two-qudit
maximally entangled states. Precisely, to each of the stabilizing operators
$\mathcal{G}_{k}^{n}$ we associate an expectation value in which the
particular matrices appearing at the first site are replaced by the
combinations (37) of the observables $A_{x}$,

$\left(XZ^{k}\right)^{n}\,\to\,\widetilde{A}_{k}^{(n)},$ (56)

whereas at the second site we substitute directly

$\left(XZ^{-k}\right)^{n}\,\to\,B_{k}^{n}.$ (57)

In other words, we associate

$\mathcal{G}_{k}^{n}\,\to\,\left\langle\widetilde{A}_{k}^{(n)}B_{k}^{n}\right\rangle$
(58)

with $k=0,1,2$ and $n=1,2$.

Adding then all the obtained expectation values and exploiting the fact that
$\lambda_{n}^{-1}=\lambda_{n}^{*}$, we finally arrive at Bell inequalities
derived previously in Ref. [22]:

$\displaystyle I_{\max}$ $\displaystyle\\!\\!\\!:=\\!\\!\\!$
$\displaystyle\sum_{n=1}^{d-1}\sum_{k=0}^{d-1}\left\langle\widetilde{A}^{(n)}_{k}B_{k}^{n}\right\rangle$
(59) $\displaystyle\\!\\!\\!=\\!\\!\\!$
$\displaystyle\frac{1}{\sqrt{d}}\sum_{n=1}^{d-1}\lambda_{n}^{*}\sum_{x,y=0}^{d-1}\omega^{-nxy}\left\langle
A_{x}^{n}B_{y}^{n}\right\rangle\leq\beta_{\max}^{C},$

where $\beta_{\max}^{C}$ stands for the maximal classical value of $I_{\max}$.
It is in general difficult to compute $\beta_{\max}^{C}$ analytically,
however, for the lowest values of $d=3,5,7$ it was found numerically in [22];
for completeness we listed these values in Table 1.

$d$ | $\beta_{L}$ | $\beta_{Q}$ | $\beta_{Q}/\beta_{L}$
---|---|---|---
3 | $6\cos(\pi/9)$ | 6 | 1.064
5 | $4(2+\sqrt{5})$ | 20 | 1.1803
7 | $\simeq 33.3494$ | 42 | 1.2594
Table 1: Maximal classical values of the Bell expression $I_{\max}$ given in
Eq. (59) for $d=3,5,7$. For comparison we also present the maximal quantum
values.

On the other hand, these Bell inequalities are designed so that their maximal
quantum value can be determined straightforwardly. Let us formulate and prove
the following fact.

######  Fact 1.

The maximal quantum value of the Bell expressions $I_{\max}^{(d)}$ is
$\beta_{\max}^{Q}=d(d-1)$.

###### Proof.

The proof is straightforward and consists of two steps. First, we denote by

$\mathcal{B}_{\max}=\frac{1}{\sqrt{d}}\sum_{n=1}^{d-1}\frac{1}{\lambda_{n}}\sum_{x,y=0}^{d-1}\omega^{-nxy}A_{x}^{n}\otimes
B_{y}^{n}$ (60)

a Bell operator associated to the expression $I_{\max}^{(d)}$, where $A_{x}$
and $B_{y}$ are arbitrary $d$-outcome unitary observables. Second, one uses
Eq. (40) as well as the fact that the Bell operator is Hermitian to observe
that the following sum-of-squares decomposition holds true

$d(d-1)\mathbbm{1}-\mathcal{B}_{\max}=\frac{1}{2}\sum_{n=1}^{d-1}\sum_{y=0}^{d-1}\left(\mathbbm{1}-\widetilde{A}_{y}^{(n)}\otimes
B_{y}^{n}\right)^{\dagger}\left(\mathbbm{1}-\widetilde{A}_{y}^{(n)}\otimes
B_{y}^{n}\right).$ (61)

Consequently, $d(d-1)\mathbbm{1}-\mathcal{B}_{\max}$ is a positive semi-
definite operator for any choice of local observables, and thus
$\beta_{\max}^{(d)}\leq d(d-1)$. To prove that this inequality is tight we can
construct a quantum realisation for which $I_{\max}^{(d)}=d(d-1)$. Precisely,
we notice that for the following choice of observables for Alice and Bob [cf.
Eq. (38)],

$A_{x}^{n}=\frac{\lambda_{n}}{\sqrt{d}}\sum_{k=0}^{d-1}\omega^{nxk}\omega^{nk(k+1)}(XZ^{k})^{n},\qquad
B_{y}^{n}=(XZ^{-k})^{n}$ (62)

the Bell operator $\mathcal{B}_{\max}$ simply becomes a sum of the stabilizing
operators of $|\psi_{d}^{+}\rangle$,

$\mathcal{B}_{\max}=\sum_{n=1}^{d-1}\sum_{k=0}^{d-1}\left[G^{\prime}_{1}(G_{2}^{\prime})^{k}\right]^{n},$
(63)

meaning that
$\langle\psi_{d}^{+}|\mathcal{B}_{\max}|\psi_{d}^{+}\rangle=d(d-1)$. As a
result $\beta_{\max}^{(d)}=d(d-1)$, which completes the proof. ∎

###  3.4 General construction

We are now ready to provide our general construction of Bell inequalities for
arbitrary graph states. Let us first set the notation.

Consider a graph $\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{R},d)$ and
choose two of its vertices that are connected. Without any loss of generality
we can label them by $1$ and $2$. Let then $\mathbb{N}_{1}$ and $N_{1}$ be
respectively the neighbourhood of the first vertex, i.e., the set of all
vertices that are connected to it, and its cardinality. Clearly, we can
relabel all the other neighbours of vertex $1$ by
$j\in\mathbb{N}_{1}\setminus\\{2\\}\equiv\\{3,\ldots,N_{1}+1\\}$. We finally
label the remaining vertices that are not connected to the first vertex as
$l\in\mathcal{V}\setminus\\{1,\mathbb{N}_{1}\\}\equiv\\{N_{1}+2,\ldots,N\\}$.
The generators corresponding to the graph $\mathcal{G}$ are denoted $G_{i}$
[see Eq. (14) for the definition thereof], whereas the graph state stabilized
by them by $|G\rangle$.

Let us then define the Bell scenario. It will be beneficial for our
construction to slightly modify the way we denote the observers and the
observables they measure. Precisley, the observables measured by the first two
parties are denoted by $A_{x}$ and $B_{y}$ with $x,y=0,\ldots,d-1$,
respectively; notice that both them can choose among $d$ different settings.
Then, the other observers connected to the first party $A$ measure three
observables which we denote $C^{(i)}_{z}$ with $z=0,1,2$ and
$i\in\mathcal{N}_{1}\setminus\\{2\\}$. The remaining observers (that do not
belong to $\mathcal{N}_{1}$) have only two observables at their disposal,
denoted $D^{(i)}_{0},D^{(i)}_{1}$ where $i\in\\{N_{1}+2,\ldots,N\\}$.

To derive a Bell inequality tailored to the graph state $|G\rangle$ we begin
by rewriting the stabilizing operators $G_{i}$ corresponding to $\mathcal{G}$
by explicitly presenting operators acting on the first two sites as well as on
the neighbourhood $\mathcal{N}_{1}$. The first two stabilizing operators read

$G_{1}=X_{1}\otimes
Z^{r_{1,2}}_{2}\otimes\bigotimes_{m\in\mathcal{N}_{1}\setminus\\{2\\}}Z_{m}^{r_{1,m}}$
(64)

and

$G_{2}=Z^{r_{1,2}}_{1}\otimes
X_{2}\otimes\bigotimes_{m\in\mathcal{N}_{1}\setminus\\{2\\}}Z_{m}^{r_{2,m}}\otimes\bigotimes_{m=N_{1}+2}^{N}Z_{m}^{r_{2,m}}.$
(65)

Then, those associated to the other vertices belonging to $\mathcal{N}_{1}$
are given by

$G_{i}=Z^{r_{1,i}}_{1}\otimes Z_{2}^{r_{2,i}}\otimes
X_{i}\otimes\bigotimes_{m\in\mathcal{N}_{1}\setminus\\{2,i\\}}Z_{m}^{r_{i,m}}\otimes\bigotimes_{m=N_{1}+2}^{N}Z_{m}^{r_{i,m}},$
(66)

where $j=3,\ldots,N_{1}$, whereas the remaining $G_{i}$’s for
$i\in\\{N_{1}+2,\ldots,N\\}$ are of the following form

$G_{i}=\mathbbm{1}_{1}\otimes
Z_{2}^{r_{2,i}}\otimes\bigotimes_{m\in\mathcal{N}_{1}\setminus\\{2\\}}Z_{m}^{r_{i,m}}\otimes
X_{i}\otimes\bigotimes_{m\in\\{N_{1}+2,\ldots,N\\}\setminus\\{i\\}}Z_{m}^{r_{i,m}},$
(67)

It is worth adding here that since by assumption the first two vertices are
connected, $r_{1,2}\neq 0$. Moreover, $G_{1}$ acts trivially on all sites that
are outside $\mathcal{N}_{1}\cup\\{1\\}$.

Given the stabilizing operators, let us then follow the procedure outline
already in the previous examples. We begin by constructing a suitable set of
stabilizing operators. First, to create at the first site the operators
$XZ^{k}$ required for the assignment (37), we consider products
$G_{1}G_{2}^{k}$ with $k=0,\ldots,d-1$. This set, however, does not uniquely
define the graph state $|G\rangle$ as it lacks the other generators. To
include them we first notice that any $G_{i}$ with
$i\in\mathcal{N}_{1}\setminus\\{2\\}$ contains the $Z$ operator or its power
at the first position and therefore we take their products with $G_{1}$, that
is, $G_{1}G_{i}$ with $i\in\mathcal{N}_{1}\setminus\\{2\\}$, again to obtain
$XZ^{k}$ at the first site. On the other hand, the remaining generators
$G_{i}$ for $i\in\\{N_{1}+2,\ldots,N\\}$ have the identity at the first
position and therefore we directly add them to the set.

Thus, the total list of the stabilizing operators that we use to construct a
Bell inequality is

$\begin{array}[]{ccll}\mathcal{G}_{1,k}^{n}&:=&(G_{1}G_{2}^{k})^{n}&(k=0,\ldots,d-1),\\\\[4.30554pt]
\mathcal{G}_{2,k}^{n}&:=&\left(G_{1}G_{k}\right)^{n}&(k=3,\ldots,N_{1}+1),\\\\[4.30554pt]
\mathcal{G}_{3,k}^{n}&:=&G_{k}^{n}&(k=N_{1}+2,\ldots,N),\end{array}$ (68)

where we have added powers to include all outcomes in the Bell scenario. Let
us now write these operators explicitly

$\mathcal{G}^{n}_{1,k}=\left(XZ^{kr_{1,2}}\right)_{1}^{n}\otimes\left(Z^{r_{1,2}}X^{k}\right)_{2}^{n}\otimes\bigotimes_{m\in\mathcal{N}_{1}\setminus\\{2\\}}Z_{m}^{n(r_{1,m}+kr_{2,m})}\otimes\bigotimes_{m\in\\{N_{1}+2,\ldots,N\\}}Z_{m}^{nkr_{2,m}}$
(69)

for $k=0,\ldots,d-1$,

$\mathcal{G}^{n}_{2,k}=\left(XZ^{r_{1,k}}\right)^{n}_{1}\otimes
Z^{n(r_{1,2}+r_{2,k})}_{2}\otimes(Z^{r_{1,k}}X)_{k}^{n}\otimes\bigotimes_{m\in\mathcal{N}_{1}\setminus\\{2,k\\}}Z_{m}^{n(r_{1,m}+r_{k,m})}\otimes\bigotimes_{m\in\\{N_{1}+2,\ldots,N\\}}Z_{m}^{nr_{k,m}}$
(70)

for $k=3,\ldots,N_{1}+2$, and

$\mathcal{G}^{n}_{3,k}=\mathbbm{1}_{1}\otimes
Z_{2}^{nr_{2,k}}\otimes\bigotimes_{m\in\mathcal{N}_{1}\setminus\\{2\\}}Z_{m}^{nr_{k,m}}\otimes
X^{n}_{k}\otimes\bigotimes_{m\in\\{N_{1}+2,\ldots,N\\}\setminus\\{k\\}}Z_{m}^{nr_{k,m}}$
(71)

for $k\in\\{N_{1}+2,\ldots,N\\}$.

We associate to each of these stabilizing operators an expectation value in
which the local operators are replaced by $d$-outcome observables or
combinations thereof. Let us begin with the first site where we have
$(XZ^{kr_{1,2}})^{n}$ with $k=0,\ldots,d-1$, $XZ^{r_{1,i}}$ with
$i=3,\ldots,N_{1}$ and the identity. It is important to notice here that due
to the fact that $d$ is a prime number, for any $r_{1,2}\neq 0$, $kr_{1,2}$
spans the whole set $\\{0,\ldots,d-1\\}$ for $k=0,\ldots,d-1$; in other words,
the function $f(k)=kr_{1,2}$ defined on the set $\\{0,\ldots,d-1\\}$ is a one-
to-one function. Thus, $XZ^{kr_{1,2}}$ contains all the $d$ different matrices
appearing in the transformation (37). We thus substitute

$(XZ^{kr_{1,2}})^{n}\,\to\,\widetilde{A}_{kr_{1,2}}^{(n)}:=\frac{\omega^{-nkr_{1,2}(kr_{1,2}+1)}}{\sqrt{d}\,\lambda_{n}}\sum_{x=0}^{d-1}\omega^{-nkr_{1,2}x}A_{x}^{n}.$
(72)

Analogously, we substitute

$(XZ^{r_{1,i}})^{n}\,\to\,\widetilde{A}_{r_{1,i}}^{(n)}:=\frac{\omega^{-nr_{1,i}(kr_{1,i}+1)}}{\sqrt{d}\,\lambda_{n}}\sum_{x=0}^{d-1}\omega^{-nr_{1,i}x}A_{x}^{n}$
(73)

for $i=3,\ldots,N_{1}+1$; in both cases $n=1,\ldots,d-1$.

Let us then move to the second site. The matrices appearing there are
$Z^{r_{1,2}}X^{k}$ with $k=0,\ldots,d-1$ and $Z^{n(r_{1,2}+r_{2,i})}$ with
$i=3,\ldots,N_{1}+1$. Since for any $r_{1,2}$ the former are all proper
observables in our scenario, that is, they are unitary and their spectra
belong to $\\{1,\omega^{1},\ldots,\omega^{d-1}\\}$, we can directly substitute
them by observables $B_{k}$. Specifically, for $k=0$ we assign

$Z^{n}\,\to\,B_{0}^{n}$ (74)

which implies in particular that

$Z^{nr_{1,2}}\,\to\,B_{0}^{nr_{1,2}},$ (75)

and for the remaining $k=1,\ldots,d-1$,

$(Z^{r_{1,2}}X^{k})^{n}\,\to\,B_{k}^{n}.$ (76)

We distinguish the case $k=0$ to simplify the assignment of observables to the
other set of matrices $Z^{n(r_{1,2}+r_{2,i})}$ with $i=3,\ldots,N_{1}+1$.
These are simply powers of $Z$ and thus we associate with them a single
observable $B_{0}$; precisely,

$Z^{n(r_{1,2}+r_{2,i})}\to B_{0}^{n(r_{1,2}+r_{2,i})}.$ (77)

Let us now consider all sites from $\mathcal{N}_{1}\setminus\\{2\\}$. From
Eqs. (69), (70) and (71) it follows that the operators appearing there are
$Z^{r_{1,i}}X$ with $i=3,\ldots,N_{1}+1$ and powers of $Z$, and thus we can
make the following replacements

$Z\,\to\,C_{0}^{(i)}\qquad\mathrm{and}\qquad Z^{r_{1,i}}X\,\to\,C_{1}^{(i)}$
(78)

for any $i=3,\ldots,N_{1}$. Finally, for the remaining sites we have simply
the $X$ operator at various sites and powers of $Z$. Thus, for any
$i=N_{1}+2,\ldots,N$,

$Z\,\to\,D_{0}^{(i)}\qquad\mathrm{and}\qquad X\,\to\,D_{1}^{(i)}.$ (79)

Collecting all these substitutions together we have

$\mathcal{G}_{1,0}^{n}\,\to\,\widetilde{\mathcal{G}}_{1,0}^{(n)}:=\widetilde{A}_{0}^{(n)}\otimes
B_{0}^{nr_{1,2}}\otimes\bigotimes_{i=3}^{N_{1}+1}\left[C^{(i)}_{0}\right]^{nr_{1,i}}$
(80)

and

$\mathcal{G}_{1,k}^{n}\,\to\,\widetilde{\mathcal{G}}_{1,k}^{(n)}:=\widetilde{A}_{kr_{1,2}}^{(n)}\otimes
B_{k}^{n}\otimes\bigotimes_{i=3}^{N_{1}+1}\left[C^{(i)}_{0}\right]^{n(r_{1,i}+kr_{2,i})}\otimes\bigotimes_{i=N_{1}+2}^{N}\left[D^{(i)}_{0}\right]^{nkr_{2,i}}$
(81)

for $k=1,\ldots,d-1$. Then,

$\mathcal{G}_{2,k}^{n}\,\to\,\widetilde{\mathcal{G}}_{2,k}^{(n)}:=\widetilde{A}_{r_{1,k}}^{(n)}\otimes
B_{0}^{n(r_{1,k}+r_{2,k})}\bigotimes_{i=3}^{k-1}\left[C_{0}^{(i)}\right]^{n(r_{1,i}+r_{k,i})}\otimes\left[C^{(k)}_{1}\right]^{n}\otimes\bigotimes_{i=k+1}^{N_{1}+1}\left[C_{0}^{(i)}\right]^{n(r_{1,i}+r_{k,i})}\bigotimes_{i=N_{1}+2}^{N}\left[D_{0}^{(i)}\right]^{nr_{k,i}}$
(82)

with $k\in\\{3,\ldots,N_{1}+1\\}$, and, finally,

$\mathcal{G}_{3,k}^{n}\,\to\,\widetilde{\mathcal{G}}_{3,k}^{(n)}:=B_{0}^{nr_{2,k}}\bigotimes_{i=3}^{N_{1}+1}\left[C_{0}^{(i)}\right]^{nr_{k,i}}\bigotimes_{i=N_{1}+2}^{k-1}\left[D_{0}^{(i)}\right]^{nr_{k,i}}\otimes\left[D_{1}^{(k)}\right]^{n}\otimes\bigotimes_{i=k+1}^{N}\left[D_{0}^{(i)}\right]^{nr_{k,i}}$
(83)

for $k\in\\{N_{1}+2,\ldots,N\\}$.

Lastly, by taking a weighted sum of expectation values of the above operators,
we arrive at the following class of Bell expressions for a given graph state:

$\displaystyle
I_{\mathcal{G}}:=\sum_{n=1}^{d-1}\left[\left\langle\widetilde{\mathcal{G}}_{1,0}^{(n)}\right\rangle+\sum_{k=1}^{d-1}c_{1,k}\left\langle\widetilde{\mathcal{G}}_{1,k}^{(n)}\right\rangle+\sum_{k=3}^{N_{1}+1}c_{2,k}\left\langle\widetilde{\mathcal{G}}_{2,k}^{(n)}\right\rangle+\sum_{k=N_{1}+2}^{N}\left\langle\widetilde{\mathcal{G}}_{3,k}^{(n)}\right\rangle\right],$
(84)

where $c_{i,k}>0$ are some free parameters that satisfy

$c_{1,k}+\sum_{\begin{subarray}{c}j=3\\\
\\{j:r_{1,j}=kr_{1,2}\\}\end{subarray}}^{N_{1}+1}c_{2,j}=1$ (85)

for each $k=1,\ldots,d-1$, where the second sum goes over all $j$ such that
for a fixed $k$, $r_{1,j}=kr_{1,2}$. As we will see below the conditions (85)
are used for constructing sum-of-squares decompositions of the Bell operators
corresponding to $I_{\mathcal{G}}$, which in turn are crucial for determining
the maximal quantum values of $I_{\mathcal{G}}$. In fact, we can prove the
following theorem.

######  Theorem 2.

The maximal quantum value of $I_{\mathcal{G}}$ is

$\beta_{\mathcal{G}}^{Q}=(d-1)(N-N_{1}+d-1).$ (86)

###### Proof.

To prove this statement let us consider a Bell operator corresponding to
$I_{\mathcal{G}}$,

$\mathcal{B}_{\mathcal{G}}=\sum_{n=1}^{d-1}\left[\widetilde{\mathcal{G}}_{1,0}^{(n)}+\sum_{k=1}^{d-1}c_{1,k}\,\widetilde{\mathcal{G}}_{1,k}^{(n)}+\sum_{k=3}^{N_{1}+1}c_{2,k}\,\widetilde{\mathcal{G}}_{2,k}^{(n)}+\sum_{k=N_{1}+2}^{N}\widetilde{\mathcal{G}}_{3,k}^{(n)}\right],$
(87)

where $\widetilde{\mathcal{G}}_{i,k}^{(n)}$ are defined in Eqs. (80)-(83). We
show that $\mathcal{B}_{\mathcal{G}}$ admits the following sum-of-squares
decomposition

$\displaystyle\mathcal{B}_{\mathcal{G}}$ $\displaystyle\\!\\!\\!=\\!\\!\\!$
$\displaystyle(d-1)(N-N_{1}+d-1)\mathbbm{1}$
$\displaystyle-\frac{1}{2}\sum_{n=1}^{d-1}\left[\left(\mathbbm{1}-\widetilde{\mathcal{G}}^{(n)}_{1,0}\right)^{\dagger}\left(\mathbbm{1}-\widetilde{\mathcal{G}}^{(n)}_{1,0}\right)+\sum_{k=1}^{d-1}c_{1,k}\left(\mathbbm{1}-\widetilde{\mathcal{G}}^{(n)}_{1,k}\right)^{\dagger}\left(\mathbbm{1}-\widetilde{\mathcal{G}}^{(n)}_{1,k}\right)\right.$
$\displaystyle\hskip
42.67912pt\left.+\sum_{k=3}^{N_{1}+1}c_{2,k}\left(\mathbbm{1}-\widetilde{\mathcal{G}}^{(n)}_{2,k}\right)^{\dagger}\left(\mathbbm{1}-\widetilde{\mathcal{G}}^{(n)}_{2,k}\right)+\sum_{k=N_{1}+2}^{N}\left(\mathbbm{1}-\widetilde{\mathcal{G}}^{(n)}_{3,k}\right)^{\dagger}\left(\mathbbm{1}-\widetilde{\mathcal{G}}^{(n)}_{3,k}\right)\right].$

To verify that this decomposition holds true let us expand the expression
appearing in the square brackets for a particular $n$,

$\displaystyle\left(1+\sum_{k=1}^{d-1}c_{1,k}+\sum_{k=3}^{N_{1}+1}c_{2,k}+N-N_{1}-1\right)\mathbbm{1}-\mathcal{B}_{\mathcal{G}}^{(n)}-\left[\mathcal{B}_{\mathcal{G}}^{(n)}\right]^{\dagger}+\left(\widetilde{\mathcal{G}}^{(n)}_{1,0}\right)^{\dagger}\widetilde{\mathcal{G}}^{(n)}_{1,0}$
$\displaystyle+\sum_{k=1}^{d-1}c_{1,k}\left(\widetilde{\mathcal{G}}^{(n)}_{1,k}\right)^{\dagger}\widetilde{\mathcal{G}}^{(n)}_{1,k}+\sum_{k=3}^{N_{1}+1}c_{2,k}\left(\widetilde{\mathcal{G}}^{(n)}_{2,k}\right)^{\dagger}\widetilde{\mathcal{G}}^{(n)}_{2,k}+\sum_{k=N_{1}+2}^{N}\left(\widetilde{\mathcal{G}}^{(n)}_{3,k}\right)^{\dagger}\widetilde{\mathcal{G}}^{(n)}_{3,k},$
(89)

where $\mathcal{B}^{(n)}_{\mathcal{G}}$ is a part of the Bell operator
corresponding to a particular $n$, that is,

$\mathcal{B}_{\mathcal{G}}^{(n)}=\widetilde{\mathcal{G}}_{1,0}^{(n)}+\sum_{k=1}^{d-1}c_{1,k}\,\widetilde{\mathcal{G}}_{1,k}^{(n)}+\sum_{k=3}^{N_{1}+1}c_{2,k}\,\widetilde{\mathcal{G}}_{2,k}^{(n)}+\sum_{k=N_{1}+2}^{N}c_{3,k}\,\widetilde{\mathcal{G}}_{3,k}^{(n)}.$
(90)

We now notice that by summing all the conditions (85) one can deduce that

$\sum_{k=1}^{d-1}c_{1,k}+\sum_{k=3}^{N_{1}+1}c_{2,k}=d-1,$ (91)

which implies that the coefficient in front of the identity simplifies to
$d+N-N_{1}-1$. Using the definitions of $\widetilde{\mathcal{G}}_{i,k}^{(n)}$
one then has that

$\displaystyle\left(\widetilde{\mathcal{G}}^{(n)}_{1,0}\right)^{\dagger}\widetilde{\mathcal{G}}^{(n)}_{1,0}+\sum_{k=1}^{d-1}c_{1,k}\left(\widetilde{\mathcal{G}}^{(n)}_{1,k}\right)^{\dagger}\widetilde{\mathcal{G}}^{(n)}_{1,k}+\sum_{k=3}^{N_{1}+1}c_{2,k}\left(\widetilde{\mathcal{G}}^{(n)}_{2,k}\right)^{\dagger}\widetilde{\mathcal{G}}^{(n)}_{2,k}+\sum_{k=N_{1}+2}^{N}\left(\widetilde{\mathcal{G}}^{(n)}_{3,k}\right)^{\dagger}\widetilde{\mathcal{G}}^{(n)}_{3,k}$
$\displaystyle\hskip
28.45274pt=\left(\widetilde{A}_{0}^{(n)}\right)^{\dagger}\widetilde{A}_{0}^{(n)}+\sum_{k=1}^{d-1}c_{1,k}\left(\widetilde{A}_{kr_{1,2}}^{(n)}\right)^{\dagger}\widetilde{A}_{kr_{1,2}}^{(n)}+\sum_{k=3}^{N_{1}+1}c_{2,k}\left(\widetilde{A}_{r_{1,k}}^{(n)}\right)^{\dagger}\widetilde{A}_{r_{1,k}}^{(n)}+(N-N_{1}-1)\mathbbm{1}$
$\displaystyle\hskip
28.45274pt=\sum_{k=0}^{d-1}\left(\widetilde{A}_{k}^{(n)}\right)^{\dagger}\widetilde{A}_{k}^{(n)}+(N-N_{1}-1)\mathbbm{1}=(d+N-N_{1}-1)\mathbbm{1},$
(92)

where the second line follows from the fact that apart from the first position
all the local operators in $\widetilde{\mathcal{G}}_{i,k}^{(n)}$ are unitary
(notice also that $\widetilde{\mathcal{G}}_{3,k}^{(n)}$ have the identity at
the first position), whereas the second line stems from the conditions (40)
and (85). All this allows us to rewrite (3.4) simply as
$2(d+N-N_{1}-1)\mathbbm{1}-\mathcal{B}_{\mathcal{G}}^{(n)}-\mathcal{B}_{\mathcal{G}}^{(n)\dagger}$.
Taking finally the sum of these terms over $n=1,\ldots,d-1$ we arrive at the
decomposition (3.4), which completes the first part of the proof.

From the decomposition (3.4) one directly infers that
$(d-1)(d+N-N_{1}-1)\mathbbm{1}-\mathcal{B}_{\mathcal{G}}$ is a positive semi-
definite operator for any choice of the local observables, which is equivalent
to say that for any Bell operator $\mathcal{B}_{\mathcal{G}}$ corresponding to
$I_{\mathcal{G}}$ and any pure state $|\psi\rangle$, the following inequality
is satisfied

$\langle\psi|\mathcal{B}_{\mathcal{G}}|\psi\rangle\leq(d-1)(d+N-N_{1}-1).$
(93)

To show that this inequality is tight, and at the same time complete the
proof, let us provide a particular quantum realisation that achieves it. To
this end, we can invert the transformation we used to construct
$I_{\mathcal{G}}$. Precisely, we let the first party measure $d$ observables
$A_{k}$ with $k=0,\ldots,d-1$ which are defined in Eq. (38); for them
$\widetilde{A}_{k}^{(n)}=(XZ^{k})^{n}$. The remaining parties measure

$B_{0}^{n}=Z^{n},\qquad
B_{k}^{n}=(Z^{r_{1,2}}X^{k})^{n}\qquad(k=0,\ldots,d-1)$ (94)
$C_{0}^{(i)}=Z,\qquad C_{1}^{(i)}=Z^{r_{1,i}}X$ (95)

for $i=3,\ldots,N_{1}+1$, and, finally,

$D_{0}^{(i)}=Z,\qquad D_{1}^{(i)}=X$ (96)

for $i=N_{1}+2,\ldots,N$.

It is not difficult to see that for this choice of quantum observables the
Bell operator reduces to a combination of the stabilizing operators of the
given graph state $|G\rangle$, that is,

$\mathcal{B}_{\mathcal{G}}=\sum_{n=1}^{d-1}\left[G_{1}^{n}+\sum_{k=1}^{d-1}c_{1,k}(G_{1}G_{2}^{k})^{n}+\sum_{k=3}^{N_{1}+1}c_{2,k}(G_{1}G_{k})^{n}+\sum_{k=N_{1}+2}^{N}G_{k}^{n}\right].$
(97)

Owing to the conditions (85) as well as (91), one finds that

$\langle G|\mathcal{B}_{\mathcal{G}}|G\rangle=(d-1)(N-N_{1}+d-1),$ (98)

which is what we aimed to prove. ∎

We have thus obtained a family of Bell expressions whose maximal quantum
values are achieved by graph states of arbitrary prime local dimension. To
turn them into nontrivial Bell inequalities one still needs to determine their
maximal classical values which is in general a hard task. For the simplest
cases such as Bell inequalities for the AME(4,3) state or those tailored to
the maximally entangled state of two qudits for low $d$’s, the classical
bounds can be determined numerically [cf. Eq. (49) and Table 1]. On the other
hand, in the next section we show that our inequalities allow to self-test the
graph states of local dimension three, and thus for all of them the classical
bound is strictly lower than the Tsirelson’s bound. It is also worth
mentioning that the ratio between the maximal quantum and classial values will
certainly depend on the choice of vertices 1 and 2, in particular on the
number of neighbours of the first vertex $N_{1}$ because this number appears
in the formula for $\beta_{Q}$ (86).

Let us finally mention that our inequalities are scalable in the sense that
the number of expectation values they are constructed from scales linearly
with $N$. Indeed, it follows from Eq. (84) that the number of expectation
values in $I_{\mathcal{G}}$ is

$(d-1)[N+(N_{1}+d)(d-1)]$ (99)

which in the worst case $N_{1}=N-1$ reduces to $(d-1)[Nd+(d-1)^{2}]$. This
number can still be lowered twice because the expectation values in
$I_{\mathcal{G}}$ for $n=\lceil d/2\rceil,\ldots,d-1$ are complex conjugations
of those for $n=1,\ldots,\lfloor d/2\rfloor$. Another possibility for lowering
it number is to choose as the first vertex the one with the lowest
neighbourhood. While it is an interesting question whether it is possible to
design another construction which requires measuring even less expectation
values, it seems that the linear scaling in $N$ is the best one can hope for.

##  Self-testing of qutrit graph states

Here we show our second main result: we demonstrate that our Bell inequalities
can be used to self-test arbritrary graph states of local dimension $d=3$. In
this particular case the general Bell expression (84) can be written as

$\displaystyle
I_{\mathcal{G}}:=\left\langle\widetilde{\mathcal{G}}_{1,0}^{(n)}\right\rangle+\sum_{k=1}^{d-1}c_{1,k}\left\langle\widetilde{\mathcal{G}}_{1,k}^{(n)}\right\rangle+\sum_{k=3}^{N_{1}+1}c_{2,k}\left\langle\widetilde{\mathcal{G}}_{2,k}^{(n)}\right\rangle+\sum_{k=N_{1}+2}^{N}\left\langle\widetilde{\mathcal{G}}_{3,k}^{(n)}\right\rangle+c.c.,$
(100)

or explicitly as,

$\displaystyle I_{\mathcal{G}}$ $\displaystyle\\!\\!\\!:=\\!\\!\\!$
$\displaystyle\left\langle\widetilde{A}_{0}B_{0}^{r_{1,2}}\prod_{i=3}^{N_{1}+1}\left[C^{(i)}_{0}\right]^{r_{1,i}}\right\rangle$
(101)
$\displaystyle+\sum_{k=1}^{2}c_{1,k}\left\langle\widetilde{A}_{kr_{1,2}}B_{k}\prod_{i=3}^{N_{1}+1}\left[C^{(i)}_{0}\right]^{r_{1,i}+kr_{2,i}}\prod_{i=N_{1}+2}^{N}\left[D^{(i)}_{0}\right]^{kr_{2,i}}\right\rangle$
$\displaystyle+\sum_{k=3}^{N_{1}+1}c_{2,k}\left\langle\widetilde{A}_{r_{1,k}}B_{0}^{r_{1,k}+r_{2,k}}\prod_{i=3}^{k-1}\left[C^{(i)}_{0}\right]^{r_{1,i}+r_{k,i}}\,C^{(k)}_{1}\,\prod_{i=k+1}^{N_{1}+1}\left[C^{(i)}_{0}\right]^{r_{1,i}+r_{k,i}}\prod_{i=N_{1}+2}^{N}\left[D_{0}^{(i)}\right]^{r_{k,i}}\right\rangle$
$\displaystyle+\sum_{k=N_{1}+2}^{N}\left\langle
B_{0}^{r_{2,k}}\prod_{i=3}^{N_{1}+1}\left[C^{(i)}_{0}\right]^{r_{k,i}}\prod_{i=N_{1}+2}^{k-1}\left[D_{0}^{(i)}\right]^{r_{k,i}}\,D_{1}^{(k)}\,\prod_{i=k+1}^{N}\left[D_{0}^{(i)}\right]^{r_{k,i}}\right\rangle+c.c.,$

where $c.c.$ stands for the complex conjugation and represents the $n=2$ term
in Eq. (84), whereas the coefficients $c_{1,k}$ and $c_{2,k}$ satisfy the
condition (85).

Let us now prove that maximal violation of $I_{\mathcal{G}}$ can be used to
self-test the corresponding graph state according to Definition 1. To this
aim, we state the following theorem.

######  Theorem 3.

Consider a connected graph $G$ and assume that the maximal quantum value of
the corresponding Bell expression $I_{\mathcal{G}}$ is achieved by a pure
state $|\psi\rangle\in\mathcal{H}_{1}\otimes\ldots\otimes\mathcal{H}_{N}$ and
observables $A_{x}$, $B_{y}$, etc. acting on the local Hilbert spaces
$\mathcal{H}_{i}$. Then, each Hilbert space $\mathcal{H}_{i}$ decomposes as
$\mathcal{H}_{i}=\mathbbm{C}^{3}\otimes\mathcal{H}_{i}^{\prime}$ and there
exist local unitary operators $U_{i}$ with $i=1,\ldots,N$ such that

$(U_{1}\otimes\ldots\otimes
U_{N})|\psi\rangle=|\psi_{G}\rangle\otimes|\mathrm{aux}\rangle$ (102)

with $|\mathrm{aux}\rangle$ being some state from the auxiliary Hilbert space
$\mathcal{H}_{1}^{\prime}\otimes\ldots\otimes\mathcal{H}_{N}^{\prime}$.

Before we present our proof let us mention that it is follows a similar
reasoning to the proof of self-testing of $N$-qubit graph states in [34], but
since we deal here with qutrits it also makes a use of one of the results of
Ref. [22], which for completeness we state in Appendix B as Fact 5.

###### Proof.

Let us first notice that it is convenient to assume that the local reduced
density matrices of the state $|\psi\rangle$ are full rank; otherwise we are
able to characterize the observables only on the supports of these reduced
density matrices. Moreover, we assume for simplicity that $r_{1,2}=1$; recall
that by construction $r_{1,2}\neq 0$. The proof for the other case of
$r_{1,2}=2$ goes along the same lines.

The sum-of-squares decomposition (3.4) implies the following relations for the
state and observables that achieve the maximal quantum value of the Bell
expression $I_{\mathcal{G}}$,

$\widetilde{\mathcal{G}}_{1,k}^{(n)}|\psi\rangle=|\psi\rangle$ (103)

for $k=0,1,2$,

$\widetilde{\mathcal{G}}_{2,k}^{(n)}|\psi\rangle=|\psi\rangle$ (104)

for $k=3,\ldots,N_{1}+1$, and

$\widetilde{\mathcal{G}}_{3,k}^{(n)}|\psi\rangle=|\psi\rangle$ (105)

for $k=N_{1}+2,\ldots,N$.

Before we employ the above relations in order to prove our self-testing
statement let us recall that $\widetilde{A}_{x}^{(n)}$ $(x=0,1,2)$ are
combinations of the first party’s observables and are not unitary in general;
still, they satisfy $\widetilde{A}_{x}^{(2)}=\widetilde{A}_{x}^{(1)\dagger}$.
At the same time $B_{y}$, $C_{z}^{(i)}$, and $D_{w}^{(i)}$ are all unitary
observables which in the particular case $d=3$ satisfy
$B_{y}^{2}=B_{y}^{\dagger}$ etc. This implies that
$\widetilde{\mathcal{G}}_{i,k}^{(2)}=\widetilde{\mathcal{G}}_{i,k}^{(1)\dagger}$.

The main technical step we need is to identify at each site two unitary
observables whose anticommutator is unitary. This allows us to make use of
Fact 5 and Corollary 4 (see Appendix B) to define local unitary operators that
map the two unkown observables to the qutrit ones. For parties having three
measurement choices, the remaining observable will be directly mapped to other
qutrit operators thanks to anticommutation relations that can be inferred from
the sum-of-squares decompositions.

Our proof is quite technical and long and therefore to make it easier to
follow we divide it into a few steps. In the first four we characterize every
party’s observables that give rise to the maximal quantum violation of the
inequality, while in the last one we prove the self-testing statement for the
state.

Step 1. ($A_{x}$ observables). Let us first determine the form of the first
party’s observables $A_{x}$. To this end, we concentrate on conditions (103)
which for $n=1$ and $r_{1,2}=1$ can be rewritten as

$\displaystyle\widetilde{A}_{0}\otimes
B_{0}\otimes\overline{C}_{1}|\psi\rangle$ $\displaystyle\\!\\!\\!=\\!\\!\\!$
$\displaystyle|\psi\rangle,$ $\displaystyle\widetilde{A}_{1}\otimes
B_{1}\otimes\overline{C}_{1}\overline{C}_{2}\otimes\overline{D}|\psi\rangle$
$\displaystyle\\!\\!\\!=\\!\\!\\!$ $\displaystyle|\psi\rangle,$
$\displaystyle\widetilde{A}_{2}\otimes
B_{2}\otimes\overline{C}_{1}\overline{C}_{2}^{\dagger}\otimes\overline{D}^{\dagger}|\psi\rangle$
$\displaystyle\\!\\!\\!=\\!\\!\\!$ $\displaystyle|\psi\rangle,$ (106)

where $\overline{C}_{i}$ and $\overline{D}$ are short-hand notations for

$\overline{C}_{i}=\bigotimes_{m=3}^{N_{1}+1}\left[C^{(m)}_{0}\right]^{r_{i,m}},\qquad\overline{D}=\bigotimes_{m=N_{1}+2}^{N}\left[D^{(m)}_{0}\right]^{r_{2,m}},$
(107)

where $i=1,2$, and, finally,

$\widetilde{A}_{k}\equiv\widetilde{A}_{k}^{(1)}=\frac{\omega^{-k(k+1)}}{\sqrt{3}\,\lambda_{1}}\sum^{2}_{t=0}\omega^{-tk}A_{t}.$
(108)

Recall that in the case $d=3$,
$\widetilde{A}_{k}^{(2)}=\widetilde{A}_{k}^{(1)\dagger}$. Moreover, since
$\widetilde{\mathcal{G}}_{i,k}^{(2)}=\widetilde{\mathcal{G}}_{i,k}^{(1)\dagger}$,
Eq. (103) for $n=2$ gives another set of conditions, similar to (4) but with
all local operators being Hermitian-conjugated. By the very definition,
$B_{i}$, $\overline{C}_{i}$ and $\overline{D}$ are unitary and satisfy
$B_{i}^{3}=\overline{C}_{i}^{3}=\overline{D}^{3}=\mathbbm{1}$.

The above equations contain all three operators $\widetilde{A}_{i}$
$(i=0,1,2)$. Let us then concentrate on the first condition in (4) and use the
fact that $B_{0}$ and $\overline{C}_{1}$ are unitary to rewrite it as

$\widetilde{A}_{0}|\psi\rangle=B_{0}^{\dagger}\otimes\overline{C}_{1}^{\dagger}|\psi\rangle,$
(109)

which, taking into account that $B_{0}^{3}=\mathbbm{1}$ as well as
$\overline{C}_{1}^{3}=\mathbbm{1}$, implies also that

$\widetilde{A}_{0}^{2}|\psi\rangle=B_{0}\otimes\overline{C}_{1}|\psi\rangle.$
(110)

We can now use again the first condition in Eq. (4) but with all local
operators being ”daggered” (recall that it follows from Eq. (103) for $n=2$),
which allows us to obtain
$\widetilde{A}_{0}^{2}|\psi\rangle=\widetilde{A}_{0}^{\dagger}|\psi\rangle$.
Since the reduced density matrix corresponding to the first subsystem of
$|\psi\rangle$ is full rank, the latter is equivalent to the following
relation

$\widetilde{A}_{0}^{2}=\widetilde{A}_{0}^{\dagger}.$ (111)

Using similar arguments one then shows that $\widetilde{A}_{0}$ is unitary,
which together with (111) implies that $\widetilde{A}_{0}^{3}=\mathbbm{1}$ and
thus $\widetilde{A}_{0}$ is a proper quantum observable.

Employing then the second and the third relation in Eq. (4), one can draw the
same conclusions for the other two operators on Alice’s side,
$\widetilde{A}_{1}$ and $\widetilde{A}_{2}$. As a consequence, all three
$\widetilde{A}_{i}$ are quantum observables; in particular, they satisfy

$\widetilde{A}_{i}^{2}=\widetilde{A}_{i}^{\dagger}\qquad(i=1,2,3).$ (112)

Let us now use (112) to characterize $A_{x}$ observables. By substituting Eq.
(108) into it one finds, after a bit of algebra, that the observables $A_{x}$
are related via the following formula:

$\displaystyle\\{A_{i},A_{j}\\}=-\omega A_{k}^{\dagger},$ (113)

where $i,j,k=0,1,2$ and $i\neq j\neq k$. Using again Eq. (108) one can also
derive similar relations for the tilted observables,

$\\{\widetilde{A}_{i},\widetilde{A}_{j}\\}=-\widetilde{A}_{k}^{\dagger}$ (114)

with $i,j,k=0,1,2$ such that $i\neq j\neq k$.

Importantly, equations (113) and, analogously, (114) were solved in Ref. [22].
In fact, it was proven there (cf. Fact 5 and Corollary 4 in Appendix B) that
one can identify a qutrit Hilbert space in $\mathcal{H}_{1}$ in the sense that
$\mathcal{H}_{1}=\mathbbm{C}^{3}\otimes\mathcal{H}_{1}^{\prime}$ for some
auxiliary Hilbert space $\mathcal{H}_{1}^{\prime}$, and that there exists a
unitary operation $U_{1}:\mathcal{H}_{1}\to\mathcal{H}_{1}$ such that [notice
that the third observable $\widetilde{A}_{2}$ is obtained from the first two
by using (114)]

$U_{1}\,\widetilde{A}_{i}\,U_{1}=XZ^{i}\otimes P_{1}^{(1)}+(XZ^{i})^{T}\otimes
P_{2}^{(1)}\qquad(i=0,1,2),$ (115)

where $P_{i}^{(1)}$ $(i=1,2)$ are two projectors such that
$P_{1}^{(1)}+P_{2}^{(1)}=\mathbbm{1}_{1}^{\prime}$, where
$\mathbbm{1}_{1}^{\prime}$ is the indentity on $\mathcal{H}_{1}^{\prime}$.
There are thus two inequivalent sets of observables at the first site that
give rise to the maximal violation of our Bell inequality: $XZ^{i}$ with
$i=0,1,2$ and their transpositions.

Step 2. ($B_{y}$ observables). We can now move on to characterizing the
$B_{y}$ observables. First, by combining the identities in (4) with Eq. (114)
and then by using the fact that $\overline{C}_{1}$ and $\overline{C}_{2}$
commute as well as that $\widetilde{A}_{i}$ are unitary, one finds the
following equations

$\displaystyle\\{B_{i},B_{j}\\}|\psi\rangle$
$\displaystyle\\!\\!\\!=\\!\\!\\!$ $\displaystyle-B_{k}^{\dagger}|\psi\rangle$
(116)

for all triples $i,j,k$ such that $i\neq j\neq k$. By virtue of the fact that
all the single-party reduced density matrices of $|\psi\rangle$ are full rank,
these are equivalent to the following matrix equations

$\displaystyle\\{B_{0},B_{1}\\}$ $\displaystyle\\!\\!\\!=\\!\\!\\!$
$\displaystyle-B_{2}^{\dagger},$ $\displaystyle\\{B_{0},B_{2}\\}$
$\displaystyle\\!\\!\\!=\\!\\!\\!$ $\displaystyle-B_{1}^{\dagger},$
$\displaystyle\\{B_{1},B_{2}\\}$ $\displaystyle\\!\\!\\!=\\!\\!\\!$
$\displaystyle-B_{0}^{\dagger},$ (117)

and thus the $B_{y}$ observables satisfy analogous relations to $A_{x}$. This
implies that $\mathcal{H}_{2}=\mathbbm{C}^{3}\otimes\mathcal{H}_{2}^{\prime}$
for some auxiliary Hilbert space $\mathcal{H}_{2}^{\prime}$, and there exists
a unitary operation $U_{2}:\mathcal{H}_{2}\to\mathcal{H}_{2}$ such that (cf.
Fact 5 and Corollary 4)

$U_{2}\,B_{i}\,U_{2}^{\dagger}=ZX^{i}\otimes P_{1}^{(2)}+(ZX^{i})^{T}\otimes
P_{2}^{(2)}.$ (118)

for $i=0,1,2$, where $P_{1}^{(2)}$ and $P_{1}^{(2)}$ are two orthogonal
projectors such that $P_{2}^{(2)}+P_{2}^{(2)}=\mathbbm{1}_{2}^{\prime}$, where
$\mathbbm{1}_{2}^{\prime}$ is the identity acting on
$\mathcal{H}_{2}^{\prime}$ [notice that as before the form of the third
observable $B_{2}$ follows from (4)].

Step 3. ($C_{z}^{(i)}$ observables). Let us now move on to the $C_{z}^{(i)}$
observables that are measured by the observers numbered by
$i=3,\ldots,N_{1}+1$, and consider the first equation in (4) and the
conditions that follow from (104), which for our purposes we state as

$\widetilde{A}_{0}\otimes
B_{0}\otimes\left[C_{0}^{(k)}\right]^{r_{1,k}}\otimes\overline{C}_{0,k}|\psi\rangle=|\psi\rangle$
(119)

and

$\widetilde{A}_{r_{1,k}}\otimes B_{0}^{r_{1,k}+r_{2,k}}\otimes
C^{(k)}_{1}\otimes\overline{C}_{0,k}^{\prime}\otimes\overline{D}_{k}|\psi\rangle=|\psi\rangle$
(120)

with $k=3,\ldots,N_{1}+1$, and

$\overline{C}_{0,k}=\bigotimes_{\begin{subarray}{c}m=3\\\ m\neq
k\end{subarray}}^{N_{1}}\left[C^{(m)}_{0}\right]^{r_{1,m}},\qquad\overline{C}_{0,k}^{\prime}=\bigotimes_{\begin{subarray}{c}m=3\\\
m\neq
k\end{subarray}}^{N_{1}}\left[C^{(m)}_{0}\right]^{r_{1,m}+r_{k,m}},\qquad\overline{D}_{k}=\bigotimes_{m=N_{1}+1}^{N}\left[D^{(m)}_{0}\right]^{r_{k,m}}.$
(121)

Importantly, $r_{1,k}\neq 0$ for any $k=3,\ldots,N_{1}+1$, and hence all
equations in (120) contain either $\widetilde{A}_{1}$ or $\widetilde{A}_{2}$.
Let us then exploit the fact that all local operators in both Eqs. (119) and
(120) are unitary and therefore these equations can be rewritten as

$\displaystyle\left[C_{0}^{(k)}\right]^{r_{1,k}}|\psi\rangle$
$\displaystyle\\!\\!\\!=\\!\\!\\!$
$\displaystyle\widetilde{A}_{0}^{\dagger}\otimes
B_{0}^{\dagger}\otimes\overline{C}_{0,k}^{\dagger}|\psi\rangle,$
$\displaystyle C_{1}^{(k)}|\psi\rangle$ $\displaystyle\\!\\!\\!=\\!\\!\\!$
$\displaystyle\widetilde{A}_{1}^{\dagger}\otimes
B_{0}^{-(r_{1,k}+r_{2,k})}\otimes\left[\overline{C}_{0,k}^{\prime}\right]^{\dagger}\otimes\overline{D}_{k}^{\dagger}|\psi\rangle.$
(122)

Crucially, $\overline{C}_{0,k}$, $\overline{C}_{0,k}^{\prime}$ commute and
therefore we deduce that

$\left\\{\left[C_{0}^{(k)}\right]^{r_{1,k}},C_{1}^{(k)}\right\\}|\psi\rangle=\\{\widetilde{A}_{0},\widetilde{A}_{1}\\}^{\dagger}\otimes
B_{0}^{\lambda_{k}}\otimes\overline{C}_{0,k}^{\dagger}\left[\overline{C}_{0,k}^{\prime}\right]^{\dagger}\otimes\overline{D}_{k}^{\dagger}|\psi\rangle,$
(123)

where for simplicity we denoted $\lambda_{k}=-(1+r_{1,k}+r_{2,k})$. In a fully
analogous way we can derive

$\left\\{\left[C_{0}^{(k)}\right]^{r_{1,k}},C_{1}^{(k)}\right\\}^{\dagger}|\psi\rangle=\\{\widetilde{A}_{0},\widetilde{A}_{1}\\}\otimes
B_{0}^{-\lambda_{k}}\otimes\overline{C}_{0,k}\,\overline{C}_{0,k}^{\prime}\otimes\overline{D}_{k}|\psi\rangle.$
(124)

Both these conditions when combined with Eq. (114) allow us to conclude that

$\left\\{\left[C_{0}^{(k)}\right]^{r_{1,k}},C_{1}^{(k)}\right\\}^{\dagger}\left\\{\left[C_{0}^{(k)}\right]^{r_{1,k}},C_{1}^{(k)}\right\\}=\left\\{\left[C_{0}^{(k)}\right]^{r_{1,k}},C_{1}^{(k)}\right\\}\left\\{\left[C_{0}^{(k)}\right]^{r_{1,k}},C_{1}^{(k)}\right\\}^{\dagger}=\mathbbm{1}_{k},$
(125)

i.e., the above anticommutator is unitary. We can therefore use Fact 5 and
Corollary 4 (see Appendix B) which say that for any $k=3,\ldots,N_{1}+1$,
$\mathcal{H}_{k}=\mathbbm{C}^{3}\otimes\mathcal{H}_{k}^{\prime}$ with
$\mathcal{H}_{k}^{\prime}$ being some auxiliary Hilbert space of unknown
dimension, as well as that there exist unitary operations $U_{k}$ such that

$U_{k}\,\left[C_{0}^{(k)}\right]^{r_{1,k}}\,U_{k}^{\dagger}=Z^{r_{1,k}}\otimes\mathbbm{1}_{k}^{\prime},$
(126)

and

$U_{k}\,C_{1}^{(k)}\,U_{k}^{\dagger}=Z^{r_{1,k}}X\otimes{P_{1}^{(k)}}+(Z^{r_{1,k}}X)^{T}\otimes{P_{2}^{(k)}},$
(127)

where $P_{1}^{(k)}+P_{2}^{(k)}=\mathbbm{1}_{k}^{\prime}$.

Step 4. ($D_{w}^{(i)}$ observables). Let us finally focus on the $D$
observables. We first consider all vertices $i\in\\{N_{2}+2,\ldots,N\\}$ that
are connected to the second vertex. For them $r_{2,k}\neq 0$ and therefore we
have from Eq. (105),

$B_{0}^{r_{2,k}}\otimes\widetilde{C}_{0,k}\otimes\overline{D}_{0,k}^{\prime}\otimes
D_{1}^{(k)}\,|\psi\rangle=|\psi\rangle,$ (128)

where

$\widetilde{C}_{0,k}=\bigotimes_{m=3}^{N_{1}}\left[C^{(m)}_{0}\right]^{r_{k,m}},\qquad\overline{D}_{0,k}^{\prime}=\bigotimes_{\begin{subarray}{c}i=N_{1}+1\\\
i\neq k\end{subarray}}^{N}\left[D_{0}^{(i)}\right]^{r_{k,i}}.$ (129)

At the same time, Eq. (103) for $k=1$ gives

$\widetilde{A}_{r_{1,2}}\otimes
B_{1}\otimes\overline{C}_{1}\overline{C}_{2}\otimes\left[D_{0}^{(k)}\right]^{r_{2,k}}\otimes\overline{D}_{0,k}\,|\psi\rangle=|\psi\rangle$
(130)

where

$\overline{D}_{0,k}=\bigotimes_{\begin{subarray}{c}i=N_{1}+1\\\ i\neq
k\end{subarray}}^{N}\left[D_{0}^{(i)}\right]^{r_{2,i}}.$ (131)

We then rewrite both Eqs. (128) and (131) as

$\displaystyle D_{1}^{(k)}|\psi\rangle$ $\displaystyle\\!\\!\\!=\\!\\!\\!$
$\displaystyle
B_{0}^{-r_{2,k}}\otimes\widetilde{C}_{0,k}^{\dagger}\otimes\left[\overline{D}^{\prime}_{0,k}\right]^{\dagger}|\psi\rangle,$
$\displaystyle\left[D_{0}^{(k)}\right]^{r_{2,k}}|\psi\rangle$
$\displaystyle\\!\\!\\!=\\!\\!\\!$
$\displaystyle\widetilde{A}_{1}^{\dagger}\otimes
B_{1}^{\dagger}\otimes\overline{C}_{1}^{\dagger}\overline{C}_{2}^{\dagger}\otimes\overline{D}_{0,k}^{\dagger}|\psi\rangle$
(132)

Since as already proven, the anticommutator of $B_{0}^{-r_{2,k}}$ and $B_{1}$
is unitary for any $k$ such that $r_{2,k}\neq 0$, the above equations imply
that for all $k=N_{1}+2,\ldots,N$ for which $r_{2,k}\neq 0$, the
anticommutator of $D_{1}^{(k)}$ and $[D_{0}^{(k)}]^{r_{2,k}}$ is unitary too.

We can now move on to those vertices $i\in\\{N_{1}+2,\ldots,N\\}$ that are
connected to the remaining neighbours of the first vertex. In this case we
proceed in the same way as above, however, we now combine the conditions (104)
and (105) as well as we employ the forms of the $C_{z}^{(i)}$ operators given
in Eqs. (126) and (127) to observe that for any site $k$ which is connected to
a neighbour $m$ of the first vertex the anticommutator of $D_{1}^{(k)}$ and
$[D_{0}^{(k)}]^{r_{m,k}}$ is unitary and therefore $D_{0/1}^{(k)}$ satisfy the
assumptions of Fact 5 in Appendix B.

Let us finally consider the remaining vertices that are not neighbours of the
first vertex. For each of them we can prove that the anticommutator of the
local observables $D_{0/1}^{(k)}$ or powers thereof is unitary in a recursive
way starting from vertices connected to those that are connected to the
neighbours of the first vertex and employing the relations (105). Step by step
we can prove the same statement for all $D$ sites exploiting the fact that the
graph is connected and therefore for each vertex there is a path connecting it
with any other vertex in the graph.

We thus conclude that for all vertices $k=N_{1}+2,\ldots,N$ the local Hilbert
is $\mathcal{H}_{k}=\mathbbm{C}^{3}\otimes\mathcal{H}_{k}^{\prime}$ for some
finite-dimensional $\mathcal{H}_{k}^{\prime}$ and that there exists a unitary
$U_{k}$ such that (cf. Fact 5 and Corollary 4 in Appendix B)

$U_{k}\,D_{0}^{(k)}\,U_{k}^{\dagger}=Z\otimes\mathbbm{1}_{k}^{\prime}$ (133)

and

$U_{k}\,D_{1}^{(k)}\,U_{k}^{\dagger}=X\otimes P_{1}^{(k)}+X^{T}\otimes
P_{2}^{(k)}.$ (134)

The state. Having determined the form of all local observables we can now move
on to proving the self-testing statement for the state. After substituting the
above observables, the ”rotated” Bell operator corresponding to the Bell
inequality which is maximally violated can be expressed as

$U\,\mathcal{B}_{\mathcal{G}}\,U^{\dagger}=\sum_{m_{1},\ldots,m_{N}=0}^{1}B_{\boldsymbol{m}}\otimes
P_{m_{1}}^{(1)}\otimes\ldots\otimes P_{m_{N}}^{(N)},$ (135)

where $U=U_{1}\otimes\ldots\otimes U_{N}$ and $P_{m_{i}}^{(i)}$ are
projections introduced above that satisfy $P^{(i)}_{1}P^{(i)}_{2}=0$ for any
site $i=1,\ldots,N$, $B_{\boldsymbol{m}}$ with $\boldsymbol{m}:=m_{1}\ldots
m_{N}$, where $m_{i}=0,1$, are $N$-qutrit Bell operators obtained from

$B=\mathcal{G}_{1,0}+\sum_{l=1}^{2}c_{1,l}\,\mathcal{G}_{1,l}+\sum_{l=3}^{N_{1}+1}c_{2,l}\,\mathcal{G}_{2,l}+\sum_{l=N_{1}+2}^{N}\mathcal{G}_{3,l}+\mathrm{h.c.},$
(136)

through the application of the identity map ($m_{i}=0$) or the transposition
map ($m_{i}=1$) to the observables appearing at site $i$. Here,
$\mathcal{G}_{a,b}$ are the stabilizing operators of the graph state
$|G\rangle$ defined in Eqs. (68) for $n=1$ and $d=3$, which for completeness
we restate here as

$\mathcal{G}_{1,0}=X_{1}\otimes
Z_{2}\otimes\bigotimes_{i=3}^{N_{1}+1}Z_{i}^{r_{1,i}},$ (137)
$\mathcal{G}_{1,k}=\left(XZ^{k}\right)_{1}\otimes\left(ZX^{k}\right)_{2}\otimes\bigotimes_{i=3}^{N_{1}+1}Z_{i}^{r_{1,i}+kr_{2,i}}\otimes\bigotimes_{i=N_{1}+2}^{N}Z_{i}^{kr_{2,i}},$
(138)

with $k=1,2$,

$\mathcal{G}_{2,k}=(XZ^{r_{1,k}})_{1}\otimes
Z_{2}^{r_{1,k}+r_{2,k}}\otimes\bigotimes_{i=3}^{k-1}Z^{r_{1,i}+r_{k,i}}_{i}\otimes\left(Z^{r_{1,k}}X\right)_{k}\otimes\bigotimes_{i=k+1}^{N_{1}+1}Z^{r_{1,i}+r_{k,i}}_{i}\otimes\bigotimes_{i=N_{2}+2}^{N}Z^{r_{k,i}}_{i}$
(139)

with $k=3,\ldots,N_{1}+1$

$\mathcal{G}_{3,k}=Z^{r_{2,k}}_{2}\otimes\bigotimes_{i=3}^{N_{1}+1}Z^{r_{k,i}}_{i}\otimes\bigotimes_{i=N_{1}+2}^{k-1}Z_{i}^{r_{k,i}}\otimes
X_{k}\otimes\bigotimes_{i=k+1}^{N}Z_{i}^{r_{k,i}},$ (140)

with $k=N_{1}+2,\ldots,N$. The subscripts were added to $X$ and $Z$ to denote
the site at which these operators act; recall also that we fixed $r_{1,2}=1$.

The formula (135) takes into account the fact that at each site we have two
choices of measurements, with and without the transposition. Thus, the Bell
operator is composed of $2^{N}$ $N$-qutrit Bell operators. For instance, for
$m_{1}=\ldots=m_{N}=0$ no partial transposition is applied to $B$ and
therefore $B_{0\ldots 0}\equiv B$, whereas for $m_{1}=\ldots=m_{N}=1$ the
partial transposition is applied to every site and hence $B_{1\ldots
1}=B^{T}$, where $T$ stands for the global transposition.

In order to find the form of the state maximally violating our inequality we
now determine the eigenvector(s) of the Bell operator
$\mathcal{B}_{\mathcal{G}}$ corresponding its maximal eigenvalue which is
$2(N-N_{1}+d-1)$ [cf. Eq. (86)]. To this end, let us focus on the $N$-qutrit
operators $B_{\boldsymbol{m}}$ and prove that the latter number is an
eigenvalue of only two of them, $B$ and $B^{T}$, which correspond to the cases
$m_{1}=m_{2}=\ldots=m_{N}=0,1$, whereas the eigenvalues of the remaining
operators are all lower.

Clearly, $B$ is composed of the stabilizing operators of the graph state
$|G\rangle$ and therefore its maximal eigenvalue conincides with the maximal
quantum violation of the inequality which is $2(N-N_{1}+d-1)$. The same
applies to $B^{T}$ because the transposition does not change the eigenvalues
and the graph state is real.

Let us then move on to the remaining cases, i.e., $m_{i}$ are not all equal.
We will show that in all those $2^{N}-2$ cases the $B_{\boldsymbol{m}}$
operators have eigenvalues lower than $2(N-N_{1}+2)$ because for all those
cases one can pick a few stabilizing operators $\mathcal{G}_{a,b}$ whose
partial transpositions cannot stabilize a common pure state anymore. For
further benefits let us denote by $\mathcal{G}_{a,b}^{\boldsymbol{m}}$ the
stabilizing operators which are partially transposed with respect to those
subsystems $i$ for which $m_{i}=1$. We divide the proof into three parts
corresponding to three cases: (i) $m_{1}=m_{2}=0$, (ii)$m_{1}=m_{2}=1$ and
(iii) $m_{1}=0$, $m_{2}=1$ or $m_{1}=1$, $m_{2}=0$, and also a few sub-cases.

  * •

The first one assumes that either $m_{1}=1$ and $m_{2}=0$ or $m_{1}=0$ and
$m_{2}=1$, i.e., we take the transposed observables at the first or the second
site, but not both at the same time. For simplicity let us then fix $m_{1}=1$
and $m_{2}=0$. We consider three operators $\mathcal{G}_{1,i}^{T_{1}}$ with
$i=0,1,2$, where $T_{1}$ is the transposition applied to the observables at
the first site. It is not difficult to observe that using the explicit forms
of the stabilizing operators [cf. Eqs. (137) and (138)] and including the
transposition at the first site, one obtains

$\mathcal{G}_{1,0}^{T_{1}}\mathcal{G}_{1,1}^{T_{1}}\mathcal{G}_{1,2}^{T_{1}}=[X^{T}(XZ)^{T}(XZ^{2})^{T}]_{1}\otimes[Z\,ZX\,ZX^{2}]_{2},$
(141)

where we also used the fact that the products of the observables at the
remaining sites amounts to identity. Using then the fact that $ZX=\omega XZ$,
the above simplifies to

$\mathcal{G}_{1,0}^{T_{1}}\mathcal{G}_{1,1}^{T_{1}}\mathcal{G}_{1,2}^{T_{1}}=\omega\mathbbm{1}.$
(142)

This simple fact precludes that there exists a common eigenvector of
$\mathcal{G}_{1,i}^{T_{1}}$ $(i=1,2,3)$ with eigenvalue one.

  * •

Next, we consider the case when the observables at the first two sites are not
transposed, i.e., $m_{1}=m_{2}=0$. There thus exists $i\neq 1,2$ such that
$m_{i}=1$. Let us first assume that this particular vertex belongs to
$i\in\\{3,\ldots,N_{1}+1\\}$, i.e., we take the transposed observables for
this site. We then consider two operators $\mathcal{G}_{1,0}$ and
$\mathcal{G}_{2,i}$. Notice then that the first of these operators has the $Z$
observable at site $i$ because $i\in\mathcal{N}_{1}$, i.e., it is connected to
the first vertex, whereas the second one has $Z^{r_{1,i}}X$ at this position.
At the remaining positions different than the first two they have only $Z$
observable or the identity which do not feel the action of transposition. All
this means that in this case
$\mathcal{G}_{1,0}^{\boldsymbol{m}}=\mathcal{G}_{1,0}$ and
$\mathcal{G}_{2,i}^{\boldsymbol{m}}=\mathcal{G}_{2,i}^{T_{i}}$. Due to the
fact that the transposition at site $i$ modifies $X$ appearing in
$\mathcal{G}_{2,i}$ to $X^{\dagger}$, the operators $\mathcal{G}_{1,0}$ and
$\mathcal{G}_{2,i}^{T_{i}}$ do not commute (recall that by the very definition
the stabilizing operators without the transposition commute). By virtue of
Fact 4 stated in Appendix A this implies that $\mathcal{G}_{1,0}$ and
$\mathcal{G}_{2,i}^{T_{i}}$ do not stabilize a common pure state.

Let us now move on to the second sub-case in which $m_{i}=1$ for any
$i\in\mathcal{N}_{1}$ and there exist $i\in\\{N_{1}+2,\ldots,N\\}$ such that
$m_{i}=2$. Since the graph is connected there exist another vertex $j\neq 1,i$
which is connected to $i$. Analogously to the previous case, we consider two
operators: $\mathcal{G}_{3,i}^{\boldsymbol{m}}$ and one of
$\mathcal{G}_{a,b}^{\boldsymbol{m}}$, where the choice of the latter operator
is dictated by the choice of the vertex $j$ which $i$ is connected to: for
$j=2$ we take $\mathcal{G}_{1,1}^{\boldsymbol{m}}$; for
$j\in\\{3,\ldots,N_{1}+1\\}$ we take $\mathcal{G}_{2,j}^{\boldsymbol{m}}$;
finally, for $j\in\\{N_{1}+2,\ldots,N\\}$ we take
$\mathcal{G}_{3,j}^{\boldsymbol{m}}$.

Now, $\mathcal{G}_{3,i}^{\boldsymbol{m}}$ has the $X$ operator at site $i$ and
the $Z$ operator at the remaining ”$D$” sites, whereas all the other operators
$\mathcal{G}_{a,b}^{\boldsymbol{m}}$ for $a=1,2,3$ and $b\neq i$ listed above
have only either the $Z$ operator or the identity at all ”$D$” sites. Thus,
$\mathcal{G}_{a,b}^{\boldsymbol{m}}=\mathcal{G}_{a,b}$ for any $a=1,2,3$ and
$b\neq i$ and any sequence $\boldsymbol{m}$ in which $m_{l}=1$ for
$l=1,\ldots,N_{1}+1$, and
$\mathcal{G}_{3,i}^{\boldsymbol{m}}=\mathcal{G}_{3,i}^{T_{i}}$. Now, it
clearly follows that $\mathcal{G}_{3,i}^{\boldsymbol{m}}$ does not commute
with the chosen $\mathcal{G}_{a,b}$ because the transposition at site $i$
changes the $X$ operator to $X^{2}$ and because, by the very definition,
$\mathcal{G}_{3,i}$ (without the transposition) commutes with any other
$\mathcal{G}_{a,b}$. As before this implies that
$\mathcal{G}_{3,i}^{\boldsymbol{m}}\mathcal{G}_{a,b}=\omega^{q}\mathcal{G}_{a,b}\mathcal{G}_{3,i}^{\boldsymbol{m}}$
for some $q=1,2$, and therefore these two operators cannot stabilize a common
pure state [cf. Fact 4 in Appendix A].

  * •

The last case to consider is when $m_{1}=m_{2}=1$; the remaining $m_{i}$ can
take arbitrary values except for being all equal to one, which corresponds to
the already-considered case of all observables being transposed. Here we can
use the fact that $\mathcal{G}_{a,b}^{\boldsymbol{m}}$ for all $a,b$ stabilize
the graph state $|G\rangle$ if and only if
$[\mathcal{G}_{a,b}^{\boldsymbol{m}}]^{T}$ does, where $T$ is the global
transposition. We can thus apply the global transposition to all the operators
$\mathcal{G}_{a,b}^{\boldsymbol{m}}$ and consider again the case when
$m_{0}=m_{2}=0$ and there is some $i\neq 1,2$ such that $m_{i}=1$, which has
already been considered above.

Knowing that among all the $B_{\boldsymbol{m}}$ operators only $B$ and $B^{T}$
give rise to the maximal quantum violation of the Bell inequality
corresponding to the considered graph, we can determine the form of the state
$|\psi\rangle$ maximally violating the inequality. Due to the fact that each
local Hilbert space decomposes as
$\mathcal{H}_{k}=\mathbbm{C}^{3}\otimes\mathcal{H}_{k}^{\prime}$ we can write
the state as

$|\psi\rangle=\sum_{i_{1},\ldots,i_{N}}|\psi_{i_{1},\ldots,i_{N}}\rangle\otimes|i_{1}\rangle_{1}\otimes\ldots\otimes|i_{N}\rangle_{N},$
(143)

where $|\psi^{\prime}\rangle=(U_{1}\otimes\ldots\otimes U_{N})|\psi\rangle$,
$|\psi_{i_{1},\ldots,i_{N}}\rangle$ are some vectors from
$(\mathbbm{C}^{3})^{\otimes N}$ and the local bases $|i_{k}\rangle$ are the
eigenbases of the projectors $P^{(k)}_{m_{k}}$. The fact that $|\psi\rangle$
achieves the maximal quantum value of the inequality,
$\beta_{Q}=2(N-N_{1}+2)$, means that the following identity

$\mathcal{B}_{\mathcal{G}}|\psi\rangle=2(N-N_{1}+2)|\psi\rangle$ (144)

holds true. Plugging Eqs. (143) and (135) into the above equation one finds
that it is satisfied iff for every sequence $\boldsymbol{m}$,

$B_{\boldsymbol{m}}|\psi_{i_{1},\ldots,i_{N}}\rangle=2(N-N_{1}+2)|\psi_{i_{1},\ldots,i_{N}}\rangle,$
(145)

holds true for all those sequences $i_{1},\ldots,i_{N}$ for which the local
vectors $|i\rangle_{k}$ at site $k$ are the eigenvectors of the operator
$P_{m_{k}}^{(k)}$. As already discussed above, this condition can be met for
only two of these operators, $B$ and $B^{T}$. Moreover, the stabilizing
operators that $B$ (and thus also $B^{T}$) are composed of stabilize a unique
state, which is the graph state $|G\rangle$. Consequently,
$|\psi_{i_{1},\ldots,i_{N}}\rangle=|G\rangle$ for any sequence
$i_{1},\ldots,i_{N}$ for which the corresponding local vectors are the
eigenvectors of $P_{0}^{(k)}$ (or $P_{1}^{(k)}$ in the case of $B^{T}$).

On the other hand, we showed that the eigenvalues of the remaining operators
$B_{\boldsymbol{m}}$ are lower than the maximal violation of the Bell
inequality and thus in all those cases Eq. (145) can be satisfied iff the
corresponding vectors vanish, $|\psi_{i_{1},\ldots,i_{N}}\rangle=0$. Taking
all this into account, we conclude that the state $|\psi^{\prime}\rangle$ has
the following form

$(U_{1}\otimes\ldots\otimes
U_{N})|\psi\rangle=|\psi_{\mathcal{G}}\rangle\otimes|\varphi\rangle,$ (146)

where $|\varphi\rangle$ is some state from the auxiliary Hilbert spaces
$\mathcal{H}_{1}^{\prime}\otimes\ldots\otimes\mathcal{H}_{N}^{\prime}$ that
satisfies

$\left(P_{i}^{(1)}\otimes\ldots\otimes
P_{i}^{(N)}\right)|\varphi\rangle=|\varphi\rangle\qquad(i=0,1).$ (147)

This completes the proof. ∎

##  Conclusions and outlook

In this work we introduced a family of Bell expressions whose maximal quantum
values are achieved by graph states of arbitrary prime local dimension. While
at the moment we are unable to compute their maximal classical values, we
believe the corresponding Bell inequalities are all nontrivial. This belief is
supported by a few examples of Bell inequalities for which the classical bound
was found numerically, and the fact that in the particular case of qutrit
states they enable self-testing of all graph states. We thus introduced a
broad class of Bell inequalities that can be used for testing non-locality of
many interesting and relevant multipartite states, including the absolutely
maximally entangled states. Moreover, in the particular case of many-qutrit
systems our inequalities can also be employed to self-test the graph states,
in particular the four-qutrit absolutely maximally entangled state.

There is a few possible directions for further research that are inspired by
our work:

  * •

First of all, as far as implementations of self-testing are concerned it is a
problem of a high relevance to understand how robust our self-testing
statements are against noises and experimental imperfections.

  * •

Another possible direction that is related to the possibility of experimental
implementations of self-testing is to find Bell inequalities maximally
violated by graph states that require performing the minimal number of two
measurement per observer to self-test the state. For instance, for the GHZ
state such a Bell inequality [25] and a self-testing scheme [26] based on the
maximal violation of this inequality were introduced recently; this inequality
is based, however, on a slightly different construction which is not directly
related to the stabilizer formalism used by us here.

  * •

Third, it is interesting to explore whether one can derive self-testing
statements based on the maximal violation of our inequalities for higher prime
dimensions $d\geq 0$. While it is already known (cf. Ref. [22]) that these
inequalities do not serve the purpose as far as quantum observables are
concerned because there exist many different choices of them that are not
unitarily equivalent, whether they enable self-testing of graph states remains
open. In other words, it is unclear whether the given graph state is the only
one (up to the above equivalences) that meets the necessary and sufficient
conditions for the maximal quantum violation of the corresponding Bell
inequality stemming from the sum-of-squares decomposition.

  * •

The fourth possible direction is to generalize our construction so that it
allows for designing Bell inequalities that are maximally violated by other
classes of states such as for instance the hyper-graph states [42] (see also
Ref. [43] in this context).

  * •

Last but not least, one can also explore the possibility of self-testing of
genuinely entangled subspaces within the stabilizer formalism in Hilbert
spaces of arbitrary prime local dimension along the lines of Refs. [20, 21].

## Acknowledgments

We acknowledge the VERIqTAS project funded within the QuantERA II Programme
that has received funding from the European Union’s Horizon 2020 research and
innovation programme under Grant Agreement No 101017733 and the Polish
National Science Center. F. B. is supported by the Alexander von Humboldt
foundation.

##  Appendix A A few facts

######  Fact 2.

Consider the generalized Pauli matrices defined through the following formulas

$X|i\rangle=|i+1\rangle,\qquad Z|i\rangle=\omega^{i}|i\rangle,$ (148)

where $|i\rangle$ $(i=0,\ldots,d-1)$ are the elements of the standard basis of
$\mathbbm{C}^{d}$. There are no complex numbers $\alpha,\beta\neq 0$ for which
$\alpha X+\beta Z$ is unitary.

###### Proof.

The proof is elementary. We first expand

$(\alpha X+\beta Z)^{\dagger}(\alpha X+\beta
Z)=(|\alpha|^{2}+|\beta|^{2})\mathbbm{1}+\alpha^{*}\beta
X^{\dagger}Z+\beta^{*}\alpha Z^{\dagger}X.$ (149)

Let us then show that for any $d\geq 3$, the operators $X^{\dagger}Z$ and
$Z^{\dagger}X$ are linearly independent. To this end, we assume that
$X^{\dagger}Z$ and $Z^{\dagger}X$ are linearly dependent and thus
$X^{\dagger}Z=\eta Z^{\dagger}X$ for some $\eta\in\mathbbm{C}$. By using the
fact that $ZX=\omega XZ$, we can rewrite this equation as
$X^{\dagger}Z=\eta\omega^{d-1}XZ^{\dagger}$, which, taken into account the
fact that $X$ and $Z$ are unitary further rewrites as
$Z^{2}=\eta\omega^{d-1}X^{2}$ which for $d\geq 3$ is satisfied iff $\eta=0$.

It now follows that the expression (149) equals $\mathbbm{1}$ if and only if
$\alpha$ or $\beta$ vanishes. This completes the proof. ∎

Let us notice that the above fact fails to be true for $d=2$ because in this
case $ZX=-XZ$ and therefore $XZ$ and $ZX$ are linearly dependent, which makes
it possible to find $\alpha,\beta$ such that $\alpha X+\beta Z$ is unitary. In
fact, any pair of real positive numbers obeying $\alpha^{2}+\beta^{2}=1$ makes
this matrix unitary.

Let us finally provide a proof of the properties (39) and (40). For this
purpose we recall $\widetilde{A}^{(n)}_{k}$ to be given by

$\widetilde{A}^{(n)}_{k}:=\frac{\omega^{-nk(k+1)}}{\sqrt{d}\,\lambda_{n}}\sum^{d-1}_{t=0}\omega^{-ntk}A_{t}^{n},$
(150)

where $A_{t}$ are unitary observables.

######  Fact 3.

Consider the following matrices

$\widetilde{A}^{(n)}_{k}:=\frac{\omega^{-nk(k+1)}}{\sqrt{d}\,\lambda_{n}}\sum^{d-1}_{t=0}\omega^{-ntk}A_{t}^{n},$
(151)

where $A_{t}$ are unitary observables. For any $n=0,\ldots,d-1$, the following
identity holds true:

$\sum^{d-1}_{k=0}\widetilde{A}^{(d-n)}_{k}\widetilde{A}^{(n)}_{k}=\sum^{d-1}_{k=0}\left[\widetilde{A}^{(n)}_{k}\right]^{\dagger}\widetilde{A}^{(n)}_{k}=d\mathbbm{1}.$
(152)

###### Proof.

After plugging Eq. (151) into Eq. (152), one obtains

$\sum^{d-1}_{k=0}\widetilde{A}^{(d-n)}_{k}\widetilde{A}^{(n)}_{k}=\frac{1}{d|\lambda_{n}|^{2}}\sum_{s,t=0}^{d-1}\sum_{k=0}^{d-1}\omega^{nk(s-t)}A_{s}^{-n}A_{t}^{n}.$
(153)

Employing then the following identity

$\sum_{k=0}^{d-1}\omega^{nk(s-t)}=d\delta_{s,t}$ (154)

and the fact that $|\lambda_{n}|^{2}=1$ for any $n$, one directly arrives at
Eq. (152), which completes the proof. ∎

######  Fact 4.

Consider two $N$-qudit operators $S_{1}$ and $S_{2}$ which are $N$-fold tensor
products of $X^{i}Z^{j}$ with $i,j=0,\ldots,d-1$ with prime $d$. Assume also
that $S_{1}^{d}=S_{2}^{d}=\mathbbm{1}$. If $[S_{1},S_{2}]\neq 0$, then they
cannot stabilize a common pure state in; in other words, no nonzero
$|\psi\rangle\in(\mathbbm{C}^{d})^{\otimes N}$ exists such that
$S_{i}|\psi\rangle=|\psi\rangle$ for $i=1,2$.

###### Proof.

Let us first notice that the Weyl-Heisenberg matrices $W_{i,j}=X^{i}Z^{j}$
satisfy the following commutation relations
$W_{i,j}W_{k,l}=\omega^{f(i,j,k,l)}W_{k,l}W_{i,j}$ with
$f:\\{0,\ldots,d-1\\}^{4}\to\\{0,\ldots,d-1\\}$, and thus there exists
$q=\\{1,\ldots,d-1\\}$ such that

$S_{1}S_{2}=\omega^{q}S_{2}S_{1}\qquad(q=1,\ldots,d-1),$ (155)

where $q\neq 0$ due to the assumption that $S_{i}$ do not commute.

Now, let us assume that $S_{i}$ stabilize a common pure state,
$S_{i}|\psi\rangle=|\psi\rangle$ for $i=1,2$. Then, the relation (155) implies
$|\psi\rangle=\omega^{q}|\psi\rangle$ which is satisfied iff $|\psi\rangle=0$,
which leads to a contradiction. This ends the proof. ∎

##  Appendix B Characterization of observables

The following proposition was proven in Appendix B of Ref. [22].

######  Fact 5.

Let $R_{0}$ and $R_{1}$ acting on some finite-dimensional Hilbert space
$\mathcal{B}$ be unitary operators satisfying
$R_{0}^{3}=R_{1}^{3}=\mathbbm{1}$. If the anticommutator $\\{R_{0},R_{1}\\}$
is unitary, then $\mathcal{H}=\mathbbm{C}^{3}\otimes\mathcal{H}^{\prime}$ for
some Hilbert space $\mathcal{H}^{\prime}$ and there exists a unitary
$U:\mathcal{H}\to\mathbbm{C}^{3}\otimes\mathcal{H}^{\prime}$ such that

$\displaystyle UR_{0}U^{\dagger}$ $\displaystyle\\!\\!\\!=\\!\\!\\!$
$\displaystyle X\otimes Q+X\otimes Q^{\perp}=X\otimes\mathbbm{1}^{\prime},$
$\displaystyle UR_{1}U^{\dagger}$ $\displaystyle\\!\\!\\!=\\!\\!\\!$
$\displaystyle X^{2}Z\otimes Q+Z^{2}\otimes Q^{\perp},$ (156)

where $Q$ and $Q^{\perp}$ are orthogonal projections satisfying
$Q+Q^{\perp}=\mathbbm{1}^{\prime}$ and $\mathbbm{1}^{\prime}$ stands for the
identity acting on $\mathcal{H}^{\prime}$.

Based on the above fact let us now show demonstrate that for each of the
subsets of observables $A_{x}$, $B_{y}$, $C_{z}^{(i)}$ and $D_{w}^{(i)}$ there
exist local unitary operations bringing them to the forms used in Eqs. (115),
(118), (126) and (127), and finally, (133) and (134).

######  Corollary 4.

The following statements can be verified by a direct check:

  * •

($A_{x}$ observables) By using $\mathcal{U}_{1}=F^{\dagger}V_{1}F\otimes
Q_{1}+F^{\dagger}V_{1}^{*}V_{2}F\otimes Q_{2}$, where $F$, $V_{1}$ and $V_{2}$
are unitary operations given by

$F=\frac{1}{\sqrt{3}}\left(\begin{array}[]{ccc}1&1&1\\\ 1&\omega&\omega^{2}\\\
1&\omega^{2}&\omega\end{array}\right),\qquad
V_{1}=\left(\begin{array}[]{ccc}1&0&0\\\ 0&1&0\\\
0&0&\omega\end{array}\right),\qquad V_{2}=\left(\begin{array}[]{ccc}1&0&0\\\
0&0&1\\\ 0&1&0\end{array}\right),$ (157)

one can bring the observables in Eq. (5) into the following form used in Eq.
(115):

$\displaystyle X\otimes Q+X^{T}\otimes Q^{\perp},$ $\displaystyle XZ\otimes
Q+(XZ)^{T}\otimes Q^{\perp}.$ (158)

  * •

($B_{y}$ and $C_{z}^{(i)}$ observables) By using
$\mathcal{U}_{2}=V_{3}F\otimes Q+(V_{1}V_{3})^{*}F\otimes Q^{\perp}$, and
relabeling $Q\leftrightarrow Q^{\perp}$ one brings the observables (5) to
those in Eq. (118), that is,

$\displaystyle Z\otimes Q+Z\otimes Q^{\perp}=Z\otimes\mathbbm{1},$
$\displaystyle ZX\otimes Q+(ZX)^{T}\otimes Q^{\perp},$ (159)

where

$V_{3}=\left(\begin{array}[]{ccc}1&0&0\\\ 0&\omega^{2}&0\\\
0&0&\omega^{2}\end{array}\right).$ (160)

Then, by applying $\mathcal{U}_{3}=(V_{1}V_{3})^{*}\otimes
Q+V_{2}^{\prime}\otimes Q^{\perp}$ operation we can bring (• ‣ 4) to

$\displaystyle Z\otimes Q+Z\otimes Q=Z\otimes\mathbbm{1},$ $\displaystyle
Z^{2}X\otimes Q+(Z^{2}X)^{T}\otimes Q^{\perp}.$ (161)

Depending on the value of $r_{1,k}\neq 0$, both (• ‣ 4) and (• ‣ 4) are used
in Eqs. (126) and (127).

  * •

($D_{w}^{(i)}$ observables) By applying $\mathcal{U}_{4}=V_{1}V_{3}\otimes
Q+(V_{1}V_{3})^{*}\otimes Q^{\perp}$ to the above observables (• ‣ 4) one can
bring them to the following form

$\displaystyle Z\otimes Q+Z\otimes Q^{\perp}=Z\otimes\mathbbm{1},$
$\displaystyle X\otimes Q+X^{T}\otimes Q^{\perp},$ (162)

which is used in Eqs. (133) and (134).

## References

  * [1] J. S. Bell, “On the Einstein-Podolsky-Rosen paradox,” Physics Physique Fizika, vol. 1, no. 3, p. 195, 1964.
  * [2] N. Brunner, S. Pironio, A. Acin, N. Gisin, A. A. Méthot, and V. Scarani, “Testing the dimension of hilbert spaces,” Phys. Rev. Lett., vol. 100, p. 210503, May 2008. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevLett.100.210503
  * [3] T. Moroder, J.-D. Bancal, Y.-C. Liang, M. Hofmann, and O. Gühne, “Device-independent entanglement quantification and related applications,” Phys. Rev. Lett., vol. 111, p. 030501, Jul 2013. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevLett.111.030501
  * [4] S. Pironio, A. Acín, S. Massar, A. B. 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, vol. 464, no. 7291, pp. 1021–1024, Apr 2010. [Online]. Available: https://doi.org/10.1038/nature09008
  * [5] A. Acín, S. Massar, and S. Pironio, “Randomness versus nonlocality and entanglement,” Phys. Rev. Lett., vol. 108, p. 100402, Mar 2012. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevLett.108.100402
  * [6] A. Acín, S. Pironio, T. Vértesi, and P. Wittek, “Optimal randomness certification from one entangled bit,” Phys. Rev. A, vol. 93, p. 040102, Apr 2016. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.93.040102
  * [7] E. Woodhead, J. Kaniewski, B. Bourdoncle, A. Salavrakos, J. Bowles, A. Acín, and R. Augusiak, “Maximal randomness from partially entangled states,” Phys. Rev. Research, vol. 2, p. 042028, Nov 2020. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevResearch.2.042028
  * [8] D. Mayers and A. Yao, “Self testing quantum apparatus,” arXiv preprint quant-ph/0307205, 2003.
  * [9] D. Wu, Q. Zhao, X.-M. Gu, H.-S. Zhong, Y. Zhou, L.-C. Peng, J. Qin, Y.-H. Luo, K. Chen, L. Li, N.-L. Liu, C.-Y. Lu, and J.-W. Pan, “Robust self-testing of multiparticle entanglement,” Phys. Rev. Lett., vol. 127, p. 230503, Dec 2021. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevLett.127.230503
  * [10] B. Yang, R. Raymond, H. Imai, H. Chang, and H. Hiraishi, “Testing scalable Bell inequalities for quantum graph states on ibm quantum devices,” IEEE Journal on Emerging and Selected Topics in Circuits and Systems, vol. 12, no. 3, pp. 638–647, 2022. [Online]. Available: https://ieeexplore.ieee.org/document/9866745
  * [11] I. Šupić and J. Bowles, “Self-testing of quantum systems: a review,” Quantum, vol. 4, p. 337, Sep. 2020. [Online]. Available: https://doi.org/10.22331/q-2020-09-30-337
  * [12] J. F. Clauser, M. A. Horne, A. Shimony, and R. A. Holt, “Proposed experiment to test local hidden-variable theories,” Phys. Rev. Lett., vol. 23, pp. 880–884, Oct 1969. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevLett.23.880
  * [13] D. Collins, N. Gisin, N. Linden, S. Massar, and S. Popescu, “Bell inequalities for arbitrarily high-dimensional systems,” Phys. Rev. Lett., vol. 88, p. 040404, Jan 2002. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevLett.88.040404
  * [14] J. Barrett, A. Kent, and S. Pironio, “Maximally nonlocal and monogamous quantum correlations,” Phys. Rev. Lett., vol. 97, p. 170409, Oct 2006\. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevLett.97.170409
  * [15] W. Laskowski, T. Paterek, M. Żukowski, and Č. Brukner, “Tight multipartite bell’s inequalities involving many measurement settings,” Phys. Rev. Lett., vol. 93, p. 200401, Nov 2004. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevLett.93.200401
  * [16] M. Żukowski and Č. Brukner, “Bell’s theorem for general n-qubit states,” Phys. Rev. Lett., vol. 88, p. 210401, May 2002. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevLett.88.210401
  * [17] O. Gühne, G. Tóth, P. Hyllus, and H. J. Briegel, “Bell inequalities for graph states,” Phys. Rev. Lett., vol. 95, p. 120405, Sep 2005. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevLett.95.120405
  * [18] G. Tóth, O. Gühne, and H. J. Briegel, “Two-setting Bell inequalities for graph states,” Phys. Rev. A, vol. 73, p. 022303, Feb 2006. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.73.022303
  * [19] A. Salavrakos, R. Augusiak, J. Tura, P. Wittek, A. Acín, and S. Pironio, “Bell inequalities tailored to maximally entangled states,” Phys. Rev. Lett., vol. 119, p. 040402, Jul 2017. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevLett.119.040402
  * [20] F. Baccari, R. Augusiak, I. Šupić, and A. Acín, “Device-independent certification of genuinely entangled subspaces,” Phys. Rev. Lett., vol. 125, p. 260507, Dec 2020. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevLett.125.260507
  * [21] O. Makuta and R. Augusiak, “Self-testing maximally-dimensional genuinely entangled subspaces within the stabilizer formalism,” New Journal of Physics, vol. 23, no. 4, p. 043042, apr 2021. [Online]. Available: https://dx.doi.org/10.1088/1367-2630/abee40
  * [22] J. Kaniewski, I. Šupić, J. Tura, F. Baccari, A. Salavrakos, and R. Augusiak, “Maximal nonlocality from maximal entanglement and mutually unbiased bases, and self-testing of two-qutrit quantum systems,” Quantum, vol. 3, p. 198, 2019.
  * [23] A. Tavakoli, M. Farkas, D. Rosset, J.-D. Bancal, and J. Kaniewski, “Mutually unbiased bases and symmetric informationally complete measurements in Bell experiments,” Science Advances, vol. 7, no. 7, p. eabc3847, 2021. [Online]. Available: https://www.science.org/doi/abs/10.1126/sciadv.abc3847
  * [24] G. Pereira Alves and J. Kaniewski, “Optimality of any pair of incompatible rank-one projective measurements for some nontrivial Bell inequality,” Phys. Rev. A, vol. 106, p. 032219, Sep 2022. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.106.032219
  * [25] R. Augusiak, A. Salavrakos, J. Tura, and A. Acín, “Bell inequalities tailored to the Greenberger–Horne–Zeilinger states of arbitrary local dimension,” New Journal of Physics, vol. 21, no. 11, p. 113001, nov 2019. [Online]. Available: https://doi.org/10.1088/1367-2630/ab4d9f
  * [26] S. Sarkar, D. Saha, J. Kaniewski, and R. Augusiak, “Self-testing quantum systems of arbitrary local dimension with minimal number of measurements,” npj Quantum Information, vol. 7, p. 151, 2019. [Online]. Available: https://www.nature.com/articles/s41534-021-00490-3
  * [27] S. Sarkar and R. Augusiak, “Self-testing of multipartite Greenberger-Horne-Zeilinger states of arbitrary local dimension with arbitrary number of measurements per party,” Phys. Rev. A, vol. 105, p. 032416, Mar 2022. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.105.032416
  * [28] H. J. Briegel and R. Raussendorf, “Persistent entanglement in arrays of interacting particles,” Phys. Rev. Lett., vol. 86, pp. 910–913, Jan 2001\. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevLett.86.910
  * [29] W. Helwig, “Absolutely maximally entangled qudit graph states,” arxiv:1306.2879, 2013. [Online]. Available: https://arxiv.org/abs/1306.2879
  * [30] X.-C. Yao, T.-X. Wang, H.-Z. Chen, W.-B. Gao, A. G. Fowler, R. Raussendorf et al., “Experimental demonstration of topological error correction,” Nature, vol. 482, no. 7386, pp. 489–494, Feb. 2012. [Online]. Available: https://doi.org/10.1038/nature10770
  * [31] R. Raussendorf and H. J. Briegel, “A one-way quantum computer,” Physical Review Letters, vol. 86, pp. 5188–5191, May 2001. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevLett.86.5188
  * [32] H. J. Briegel, D. E. Browne, W. Dür, R. Raussendorf, and M. V. den Nest, “Measurement-based quantum computation,” Nature Physics, vol. 5, no. 1, pp. 19–26, jan 2009. [Online]. Available: https://doi.org/10.1038%2Fnphys1157
  * [33] G. Tóth and I. Apellaniz, “Quantum metrology from a quantum information science perspective,” Journal of Physics A: Mathematical and Theoretical, vol. 47, no. 42, p. 424006, oct 2014. [Online]. Available: https://doi.org/10.1088/1751-8113/47/42/424006
  * [34] F. Baccari, R. Augusiak, I. Šupić, J. Tura, and A. Acín, “Scalable Bell inequalities for qubit graph states and robust self-testing,” Phys. Rev. Lett., vol. 124, p. 020402, Jan 2020. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevLett.124.020402
  * [35] W. Slofstra, “The set of quantum correlations is not closed,” arXiv:1703.08618. [Online]. Available: https://arxiv.org/abs/1703.08618
  * [36] J. Kaniewski, “Weak form of self-testing,” Phys. Rev. Research, vol. 2, p. 033420, Sep 2020. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevResearch.2.033420
  * [37] D. Schlingemann and R. F. Werner, “Quantum error-correcting codes associated with graphs,” Phys. Rev. A, vol. 65, p. 012308, Dec 2001. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.65.012308
  * [38] E. Hostens, J. Dehaene, and B. De Moor, “Stabilizer states and clifford operations for systems of arbitrary dimensions and modular arithmetic,” Phys. Rev. A, vol. 71, p. 042315, Apr 2005. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.71.042315
  * [39] M. Hein, W. Dür, J. Eisert, R. Raussendorf, M. Nest, and H.-J. Briegel, “Entanglement in graph states and its applications,” arXiv preprint quant-ph/0602096, 2006. [Online]. Available: https://arxiv.org/abs/quant-ph/0602096
  * [40] P. Facchi, G. Florio, G. Parisi, and S. Pascazio, “Maximally multipartite entangled states,” Phys. Rev. A, vol. 77, p. 060304, Jun 2008. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.77.060304
  * [41] A. Cervera-Lierta, J. I. Latorre, and D. Goyeneche, “Quantum circuits for maximally entangled states,” Phys. Rev. A, vol. 100, p. 022342, Aug 2019\. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.100.022342
  * [42] M. Rossi, M. Huber, D. Bruß, and C. Macchiavello, “Quantum hypergraph states,” New Journal of Physics, vol. 15, no. 11, p. 113022, nov 2013\. [Online]. Available: https://doi.org/10.1088/1367-2630/15/11/113022
  * [43] M. Gachechiladze, C. Budroni, and O. Gühne, “Extreme violation of local realism in quantum hypergraph states,” Phys. Rev. Lett., vol. 116, p. 070401, Feb 2016. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevLett.116.070401