# Inflated Graph States Refuting Communication-Assisted LHV Models

Uta Isabella Meyer, Frédéric Grosshans, Damian Markham

► To cite this version:

Uta Isabella Meyer, Frédéric Grosshans, Damian Markham. Inflated Graph States Refuting Communication-Assisted LHV Models. Physical Review A, 2023, 108 (1), pp.012402. 10.1103/Phys-RevA.108.012402. hal-03872280

HAL Id: hal-03872280

https://cnrs.hal.science/hal-03872280

Submitted on 9 Dec 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Inflated Graph States Refuting Communication-Assisted LHV Models

Uta Isabella Meyer,* Frédéric Grosshans,† and Damian Markham‡

Sorbonne Université, CNRS, LIP6, F-75005 Paris, France

(Dated: November 25, 2022)

Standard Bell inequalities hold when distant parties are not allowed to communicate. Barrett et al. found correlations from Pauli measurements on certain network graphs refute a local hidden variable (LHV) description even allowing some communication along the graph. This has recently found applications in proving separation between classical and quantum computing, in terms of shallow circuits, and distributed computing. The correlations presented by Barrett et al. can be understood as coming from an extension of three party GHZ state correlations which can be embedded on a graph state. In this work, we propose systematic extensions of any graph state, which we dub *inflated graph states* such that they exhibit correlations which refute any communication assisted LHV model. We further show the smallest possible such example, with a 7-qubit linear graph state, as well as specially crafted smaller examples with 5 and 4 qubits. The latter is the smallest possible violation using binary inputs and outputs.

## I. INTRODUCTION

A simple undirected graph is a set of vertices and edges connecting the vertices. Graph states are defined in one to one correspondence with a simple undirected graph, where the vertices represent qubits, and each edge corresponds to a preparation entanglement operation. In quantum information, graph states form an important class of multipartite entangled states [1] including Bell states, GHZ states [2], stabiliser code states and cluster states. Their application ranges from universal resources for quantum computation [3], to error correction and fault tolerance [4, 5], quantum metrology [6] and to quantum network protocols such as secret sharing [7] and anonymous communication [8].

Non-locality is an increasingly recognised resource for quantum information [9]. The standard setting for non-locality is of separated laboratories which are prohibited from communicating, where we look at the correlations that come out of local measurements. If they cannot be reproduced by a local hidden variable models, or equivalently with shared classical randomness, we say they are non-local, and they give rise to quantum advantages in non-local games and communication complexity and are behind device independent security [9]. Any non-trivially connected graph state can demonstrate non-locality [10]. In particular no local hidden variable (LHV) model can describe all Pauli measurements on graph states with more than two connected vertices [11].

Barrett et al. [12] showed that certain graph states still display non-locality even when the LHV model is assisted by classical communication along the graph's edges. Their construction essentially takes the three party GHSZ paradox [13], which corresponds locally to a triangle graph state where different Pauli measurements are performed on each corner, and extends it by adding vertices along

the edges and performing fixed measurements on these additional vertices. The resulting correlations not only violate an LHV description, but also an LHV description extended to allow communication along the edges of the graph up to a fixed distance.

As well as its fundamental interest, this extension of the standard setting for non-locality has given rise to several new applications. It is behind the only assumption free proof of the separation between quantum and classical computational power in the context of shallow circuits [14]. It has further been used to show quantum advantage in distributed computing [15] and to certify randomness replacing the assumptions of no-communication by assumptions on circuit depth of an adversary [16].

In this work we extend the class of graph states that exhibit non-locality when allowing distance-bounded classical communication. We follow the model for networks and allowed communication as presented by Barrett et al. [12]. For bounding classical communication we assume that the vertices can exchange classical information if they are connected by a bounded (yet not vanishing) number of edges. Note that this is a reasonable assumption as, given a graph state, vertices sharing an edge must have interacted in the past (at least indirectly). In particular we consider classical communication restricted to a fixed bounded distance *d* over the graph edges. We denote an LHV model assisted by such classical communication as *d*-LHV*. We construct graph states and formulate GHSZ-like paradoxes [13] that impose an all-or-nothing constraint on any *d*-LHV* model. Using the formulation by Mermin [17], this leads to a Bell inequality that a given graph state violates. We also explore examples for small graph states. We show that the smallest graph state that refutes a *d*-LHV* model with a GHSZ-like paradox using Pauli measurements is a 5-qubit cycle. We also provide a Bell inequality for the smallest possible graph state of four qubits that violates any *d*-LHV* model with binary inputs and outputs. It uses Clifford operations instead of Pauli operators.

The article is structured as follows. We begin in section II with an introduction of graph states and some

<footnote>* uta-isabella.meyer@lip6.fr</footnote>

<footnote>† frederic.grosshans@lip6.fr</footnote>

<footnote>‡ damian.markham@lip6.fr</footnote>
definitions for our construction. In section III we present general conditions for sets of measurements on graph states whose correlations cannot be mimicked by any LHV-model, and then any d-LHV*-model. In section IV we present the inflated graph states, and some definitions and sets of measurements used for our construction. Our main result appears in section V. We define sets of measurements for any inflated graph state, and prove that they satisfy the conditions set out in section III, hence proving that they cannot be mimicked by any d-LHV*-model. In section VI we present the simple Bell inequalities, and in section VII we explore small graph state examples. We close with discussions in section VIII.

## II. GRAPH STATES

We denote a graph $G = (V, E)$ with a set of vertices $V$ and edges $E \subset (V \times V)$. When each vertex represents a qubit, the associated graph state $|G\rangle$ is a quantum state on $n = |V|$ qubits that uniquely corresponds to the graph $G$. The graph state is defined as the unique eigenvector with eigenvalue 1 to the generator elements

$$g_v = X_v \bigotimes_{(u,v) \in E} Z_u, \qquad (1)$$

for all $v \in V$ and with the Pauli operators $\sigma_v = \{1_v, X_v, Y_v, Z_v\}$. The generator elements commute pairwise and generate the stabiliser group $\mathcal{S} = \langle\{g_v, v \in V\}\rangle$. As such any product is a stabiliser element with a decomposition

$$S = \prod_{u \in U \subset V} g_u. \qquad (2)$$

Applying Eq. (1) we can write any stabiliser element as a product of Pauli operators and a sign factor

$$S = \chi \bigotimes_{v \in V} \sigma_v. \qquad (3)$$

We will now specify a map between both representations, Eq. (2) and Eq. (3), that is local to the vertices and its nearest neighbours. Starting from any stabiliser element $S$ as a product of generator elements with an index set $U \subset V$, we determine

$$\delta_u = \begin{cases} 0, & u \notin U, \\ 1, & u \in U, \end{cases} \qquad (4)$$

and $t_u = \sum_{(u,v) \in E} \delta_v$ mod 4 for every vertex $u \in V$. The acquired three bits of information suffice to uniquely assign a Pauli operator with a sign factor to every vertex by using

$$\chi_u \sigma_u = i^{\delta_u} t_u X_u^{\delta_u} Z_u^{t_u}. \qquad (5)$$

Then, the sign factor in Eq. (3) is $\chi = \prod_{v \in V} \chi_v$. Conversely, applying Eq. (5) can be used to determine

whether any Pauli product is a stabiliser element and provide the decomposition into generator elements.

When using graph states, we are very often interested in performing Pauli measurements, whose operators are tensor products of Pauli operators. On a given graph state Pauli measurements have deterministic outcome $\pm 1$ if they are proportional to a stabiliser element as in Eq. (3), otherwise the outcome is random with expectation value 0. When measuring a Pauli product, the outcome can be regarded as a product of the local Pauli operator's outcome. Checking a stabiliser condition, for example, corresponds to checking that the product of all the involved Pauli operators gives the correct sign (according to (3)). Barrett et al. [12] provide a 1-LHV* model that correctly predicts the outcome any Pauli measurement performed on a graph state. However, they also show that by ignoring certain vertices output they abrogate any d-LHV* description. This motivates the following definition.

**Definition II.1 (Submeasurement).** Given a Pauli measurement $M = \bigotimes_{v \in V} \sigma_v$ on the graph state, a submeasurement of $M$ is defined by a Pauli product $C = \bigotimes_{v \in V} \sigma'_v$ such that $\sigma'_v = \sigma_v$ or $\sigma'_v = 1_v$ for all $v \in V$.

When considering the correlations, all the vertices where the submeasurement's operator differs from the Pauli measurement's are those whose outcomes are disregarded.

## III. NON-LOCALITY IN GRAPH STATES

In this section we will review non-locality of graph states, and present an alternative approach to that of [10], which we then extend to show non-locality persists when limited classical communication is allowed between vertices.

Graph states exhibit non-local properties when considering a vertex as a local unit. That is, they contradict the prediction of a measurement's outcome made by a local hidden variable (LHV) model [10]. We formulate LHV models as follows. We denote a hidden variable $\lambda$ with a probability distribution $\rho(\lambda)$. To each $\lambda$, the LHV assigns deterministic variables $h(O, \lambda)$ to local observables $O$. A measurement's outcome is then a probabilistic mixture of the deterministic variable over the distribution of the hidden variable $\lambda$. As the variables' values are the possible observables' outcome, it is $h(\sigma_v, \lambda) = \pm 1$ for Pauli operators $\sigma_v = X_v, Y_v, Z_v$ and $h(1_v, \lambda) = 1$. Given a Pauli measurement $M = \bigotimes_{v \in V} \sigma_v$, the LHV model predicts the outcome as $\langle M \rangle_{\text{LHV}} = \int \rho(\lambda) \prod_{v \in V} h(\sigma_v, \lambda) d\lambda$. In order to show a contradiction with any LHV model, it suffices to show that all arbitrary choices of deterministic variables $h$ sustain the contradiction, thus a probabilistic mixture does as well. We can, therefore, drop the notion of a hidden variable $\lambda$ but consider all possible deterministic variables' outcomes instead.
We briefly outline the arguments for non-locality of graph states, which will be the starting point of our constructions. A set of Pauli measurements {$M_k$}$_k$ on a fixed graph state contradicts any LHV model if it fulfills the three properties. First,

$$|\{k; (M_k)_v = \sigma_v\}| \mod 2 = 0, \forall \sigma_v \neq 1_v, \quad (6)$$

for all $v \in V$ and the set cardinality $|\cdot|$, which states that all non-trivial Pauli operators must occur an even number of times on very vertex. Second and third,

$$M_k = \chi_k S_k, \quad (7)$$

$$\prod_k M_k = -1^{\otimes V}, \quad (8)$$

with a stabiliser elements $S_k$ and sign factors $\chi_k = \pm 1$. Such a set exists for all graph states with at least three connected vertices, as shown in [10].

Equation (6) states that on every vertex, the number of every non-trivial Pauli operators the set of Pauli measurements {$M_k$}$_k$ is even. For any LHV this implies

$$\begin{aligned} \prod_k \langle M_k \rangle_{\text{LHV}} &= \prod_k \int \rho(\lambda) \prod_{v \in V} h((M_k)_v, \lambda) \, d\lambda \\ &= \int \rho(\lambda) \prod_{k'} \prod_{v \in V} h^2((M_{k'})_v, \lambda) \, d\lambda \\ &= \int \rho(\lambda) \prod_{v \in V} (\pm 1)^2 \, d\lambda = 1, \end{aligned}$$

where we used $h((M_k)_v = 1_v, \lambda) = 1$. On the other hand, Eq. (7) implies that quantum mechanics predicts every measurement's outcome to be deterministically $\chi_k = \pm 1$. Furthermore, from Eq. (8) the overall product of measurements' results is then deterministically $\prod_k \langle M_k \rangle_{\text{QM}} = -1$. The contradiction implies that no LHV model can reproduce the results predicted by quantum mechanics.

We now move to consider classical models where distance-bounded communication is permitted.

**Definition III.1.** Given a graph $G$ and non-negative integer $d$, a graph's vertex serves as a local unit and distance is measured along the edges. Then, a communication-assisted LHV model d-LHV* is a hidden variable model where each hidden variable depends on a local input and inputs up to distance $d$, which accounts for vertices broadcasting information about their inputs.

We define slightly adapted conditions on the measurements, which will similarly lead to contradictions. Considering Pauli measurements, d-LHV* model specifies randomly predetermined variables conditioned on the Pauli operators local to a vertex and its neighbours up to distance $d$ edges apart. For every vertex $u$ and $M_k$,

we define an excerpt of local measurements around the vertex $v$ with maximum distance $d$ along the edges

$$(\mathbf{M}_k)_v^d := \bigotimes_{\substack{u \\ |u-v| \le d}} (M_k)_u, \quad (9)$$

which is a tensor product of Pauli operators $\sigma_v^d = \bigotimes_{u, |u-v| \le d} \sigma_u$ around the vertex $v$.

In order to obtain a contradiction between the predictions of quantum mechanics and those allowed by such a d-LHV*, we consider now pairs of measurements ($M_k, C_k$), where the $M_k$ will be the measurements that the vertices are asked to perform, but the $C_k$, which are submeasurements of the $M_k$, are the measurements that lead to contradictions similar to what we have above. Recall that the submeasurement's Pauli operators are either the identity, or identical to the Pauli measurement. The role of the $M_k$ is then to hide from any d-LHV* information that identifies fully the correlations being checked.

For a communication-assisted version of Eq. (6), the number of Pauli products $(\mathbf{M}_k)_v^d$ must be even in the set of measurements conditioned on $(C_k)_v \neq 1_v$, that is

$$|\{k; (\mathbf{M}_k)_v^d = \sigma_v^d \wedge (C_k)_v \neq 1_v\}| \mod 2 = 0, \quad \forall \sigma_v^d, \quad (10)$$

for all vertices $u \in V$. Note that for $d=0$ the above condition is equivalent to Eq. (6) for a given vertex. Again, for $d > 0$, Eq. (10) requires not only that every non-trivial Pauli operator occurs in pairs in the set of submeasurements but that, at the same time, the corresponding Pauli measurements are equal on the neighbour vertices up to distance $d$.

We will now see contradictions between any d-LHV* model and sets of measurements pairs ($M_k, C_k$) that satisfies (10) for all vertices, and

$$C_k = \chi_k S_k, \quad (11)$$

$$\prod_k C_k = -1^{\otimes V}. \quad (12)$$

**Lemma III.2.** If a graph state has sets of measurements and submeasurement pairs {($M_k, C_k$)}$_k$, such that the {$C_k$}$_k$ satisfy (11), (12) and the pairs satisfy Eq. (10) for all vertices, then their statistics cannot be mimicked by any d-LHV* model.

*Proof.* When one performs Pauli measurements on a graph state, any d-LHV* model randomly assigns predetermined variables $h$ for each vertex depending on the Pauli operators on the vertex and its neighbours up to distance $d$. In the submeasurements, we discard certain local outcomes. If they fulfill Eq. (10) on every vertex, all variables conditioned on different Pauli operators occur an even number of times among the set of measurements and $h((C_k)_u = 1_u \{(M_k)_v\}_{0<|u-v|\le d}, \lambda) = 1$. For any d-LHV* model we evaluate the product of all submeasurements'
<figure><img src="image_2.png" /><figcaption>FIG. 1: Circular graph seen as a ($d=1$)-inflated triangle graph whose graph state is locally equivalent to the 3-GHZ state. The nodes contain the vertices' label. We provide a set of Pauli measurements and submeasurements in Tab. I that no ($d=1$)-LHV* model can correctly predict.</figcaption></figure>

outcomes

$$ 
\begin{aligned}
& \prod_k \langle C_k \rangle_{d-\text{LHV}^*} \\
&= \prod_k \int \rho(\lambda) \prod_{u \in V} h((C_k)_u, \{(M_k)_v\}_{0<|u-v|\le d}, \lambda) \, d\lambda \\
&= \int \rho(\lambda) \prod_{u \in V} \prod_k h((\mathbf{M}_k)_u^d, \lambda) \, d\lambda \\
&= \int \rho(\lambda) \, d\lambda = 1.
\end{aligned}
$$

Contrarily, Eq. (11) implies that quantum mechanics predicts every submeasurement's outcome to be deterministically $\chi_k = \pm 1$. Furthermore, from Eq. (12) the overall product of submeasurements' results is then deterministically $\prod_k \langle C_k \rangle_{QM} = -1$. The contradiction implies that no $d$-LHV* model can reproduce the results predicted by quantum mechanics. $\square$

In Tab. I, we see how the cycle graph in Fig. 1, viewed as a triangle with GHSZ like correlations at the corners gives such a contradiction, which is just a different presentation of the results of [12]. In the following we will extend this idea to arbitrary graphs.

## IV. INFLATED GRAPH STATES

In this section we define a method to generate examples from any graph states, which we call inflated graph states, and the measurements that will be used in our construction.

For any graph with at least three connected vertices we construct an inflated graph by substituting every edge by chain of $2d$ vertices bridging the edge. Starting from a graph $G = (V, E)$, the inflated graph $G' = (V', E')$ has the same vertices as the old graph, completed by $2d$ vertices $r_{(u,v)}$ for every edge $(u, v) \in E$ and $r \in [1, 2d]$.

$$ 
\begin{aligned}
M'_1 &= X_1 \quad X'_{1(1,2)} \quad X'_{2(1,2)} \quad Z_2 \quad X_{1(2,3)} \quad X'_{2(2,3)} \quad Z_3 \quad X'_{1(3,1)} \quad X'_{2(3,1)} \\
M'_2 &= Z_1 \quad X'_{1(1,2)} \quad X'_{2(1,2)} \quad X_2 \quad X_{1(2,3)} \quad X'_{2(2,3)} \quad Z_3 \quad X_{1(3,1)} \quad X'_{2(3,1)} \\
M'_3 &= Z_1 \quad X_{1(1,2)} \quad X'_{2(1,2)} \quad Z_2 \quad X'_{1(2,3)} \quad X'_{2(2,3)} \quad X_3 \quad X_{1(3,1)} \quad X'_{2(3,1)} \\
M'_4 &= X_1 \quad X_{1(1,2)} \quad X'_{2(1,2)} \quad X_2 \quad X_{1(2,3)} \quad X'_{2(2,3)} \quad X_3 \quad X_{1(3,1)} \quad X'_{2(3,1)} \\
M'_5 &= X_1 \quad X'_{1(1,2)} \quad X'_{2(1,2)} \quad Y_2 \quad X'_{1(2,3)} \quad X'_{2(2,3)} \quad Y_3 \quad X_{1(3,1)} \quad X'_{2(3,1)} \\
M'_6 &= Y_1 \quad X'_{1(1,2)} \quad X'_{2(1,2)} \quad Z_2 \quad X'_{1(2,3)} \quad X'_{2(2,3)} \quad Y_3 \quad X'_{1(3,1)} \quad X'_{2(3,1)} \\
M'_7 &= Y_1 \quad X'_{1(1,2)} \quad X'_{2(1,2)} \quad Y_2 \quad X_{1(2,3)} \quad X'_{2(2,3)} \quad X_3 \quad X_{1(3,1)} \quad X'_{2(3,1)} \\
M'_8 &= Y_1 \quad X'_{1(1,2)} \quad X'_{2(1,2)} \quad Y_2 \quad X_{1(2,3)} \quad X'_{2(2,3)} \quad Z_3 \quad X'_{1(3,1)} \quad X'_{2(3,1)}
\end{aligned}
$$

<caption>TABLE I: Set of Pauli measurements (black and grey text) and with submeasurements (grey operators are treated as $\mathbb{1}$) on the graph in Fig. 1 that contradicts any $d=1$-LHV* model. In order to account for a round of classical communication among nearest neighbors, the default is that the nearest neighbours are measuring</caption>

Pauli $X$ and we prime an operator when a nearest neighbor measures Pauli $Z$ and double prime when Pauli $Y$. In the first four measurements, the vertices 1, 2, 3 mimic a GHSZ-like paradox on a triangular graph state. The remaining measurements are hiding the classical information acquired by the other vertices from the main three vertices. Altogether the submeasurements fulfill Eq. (11) and Eq. (12), and the pairs fulfill Eq. (10) on all vertices.

The new edges are $(u, 1_{(u,v)})$, $((2d)_{(u,v)}, v) \in E'$ and $(r_{(u,v)}, (r+1)_{(u,v)}) \in E'$ for all $r \in [1, 2d-1]$ and $(u, v) \in E$. Note that even though the notation of the edges is symmetric $((u, v) = (v, u))$, we break it by counting the vertices starting from the first vertex to the second as above. We refer to the original vertices as power vertices and to the newly added vertices as chain vertices. We denote Pauli measurements and stabiliser elements with the primed letter used for the original graph state. Figure 2 shows an exemplary inflated graph.

**Definition IV.1 (Inflated Measurements).** Given a Pauli measurement $M$ on the original graph state, the Inflated measurement $M'$ is a Pauli measurement on the inflated graph state. On the power vertices $u$ it measures $(M')_u = (M)_u$, and $(M')_w = X_w$ on all chain vertices $w = r_{(u,v)}$ with $r \in [1, 2d]$ and $(u, v) \in E$.

**Definition IV.2 (Inflated generator element).** The inflated generator element $f_u$ is a stabiliser element of the inflated graph state with

$$ f_u = g'_u \prod_{\substack{(u,v) \in E, \\ s=1, \dots, d}} g'_{(2s)_{(u,v)}}. \qquad (13) $$

Writing the inflated generator elements in terms of Pauli operators $f_u = X_u \otimes_{v,(u,v) \in E} Z_v \otimes_{s=1}^d X_{(2s)_{(u,v)}}$, we see that they mimic the generator elements of the original graph state $g_v = X_v \otimes_{(u,v) \in E} Z_u$ on the power vertices and measure $X$ on every second chain vertex.
**Definition IV.3** (Inflated Stabiliser Element). Given a stabilizer element $S = \prod_{u \in U} g_u$ with $U \subset V$ on the original graph state, we define the *Inflated Stabiliser* element

$$S' = \prod_{u \in U} f_u, \qquad (14)$$

on the inflated graph state with the inflated generator elements $f_u$ from Def. IV.2.

**Definition IV.4** (Shell Stabiliser Element). For a vertex $u \in V$, with at least two nearest neighbours $v_1, v_2 \in V$, we define the Shell stabiliser element

$$\tilde{S} = f_{v_1}f_{v_2} \qquad (15)$$

on the inflated graph state with the inflated generator elements $f_u$ from Def. IV.2.

**Definition IV.5** (Decoy Measurements). For a vertex $u \in V$ with two nearest neighbours $v_1, v_2 \in V$, and two different Pauli operators $\sigma_u \neq \sigma'_u$, we define a pair of Pauli measurements $(\tilde{M}_1, \tilde{M}_2)$ called *decoy measurements* on the inflated graph state. On the power vertex $u$ they measure

$$(\tilde{M}_1)_u = \sigma_u, \quad (\tilde{M}_2)_u = \sigma'_u.$$

On the chain vertices $w$ linking $u$ to $v_1$ and $v_2$,

$$(\tilde{M}_1)_w = (\tilde{M}_2)_w = X_w,$$

with $w = r_{(u,v_{1(2)})}$ for all $r \in [1, 2d]$, and

$$(\tilde{M}_1)_v = (\tilde{M}_2)_v = (\tilde{S})_v,$$

on all other vertices $v \notin \{u\} \cup \{r_{(u,v)}\}_{v \in \{v_1, v_2\}, r \in [1, 2d]}$ of the inflated graph for the Shell stabiliser element $\tilde{S}$ defined by the same vertices $u, v_1, v_2$.

**Lemma IV.6.** Given the same vertices $u, v_1, v_2$, the Shell stabiliser element $\tilde{C} = \tilde{S}$ from Def. IV.4 is a submeasurement of both decoy measurements $(\tilde{M}_1, \tilde{M}_2)$ from Def. IV.5.

*Proof.* We determine the local Pauli operators and the sign factor of the Shell stabiliser element from Def. IV.4 using the rules in Eq. (5). The power vertex $u$ does not contribute a generator element but two nearest neighbour chain vertices do, therefore, the $\tilde{C}$ has Pauli operator $1_u$ on power vertex $u$. The same holds for the chain vertices $r_{(u,v_1)}$ and $r_{(u,v_2)}$ for $r = 1, 3, \dots, 2d - 1$. The chain vertices $r_{(u,v_1)}$ and $r_{(u,v_2)}$ for $r = 2, 4, \dots, 2d$ contribute a generator element but no nearest neighbours do, therefore the Pauli operators in $\tilde{C}$ is $X$. By definition, all other vertices have congruent Pauli operators. The overall sign factor is +1. $\square$

<figure><img src="image_3.png" /><figcaption>FIG. 2: Example of an inflated graph for $d = 2$ from a graph with 5 (large) vertices. The fat nodes highlight the vertices that measure a non-trivial Pauli operator when measuring the inflated generator element $f_4$ from Def. IV.2. Power vertex 4 and all highlighted chain vertices measure Pauli $X$ while the power vertices 2, 3, 5 measure Pauli $Z$.</figcaption></figure>

## V. MEASUREMENTS INCONSISTENT WITH d-LHV*-MODELS

Given our definitions, we can now move to finding the set of measurement which will allow us to apply lemma III.2. Here, we construct a set of Pauli measurements on the inflated graph state from the Pauli measurements on the original graph state. Then, we show that submeasurements of the new Pauli measurements fulfill Eqs. (10), (11), (12) on all vertices, i.e. they are proportional to stabiliser elements on the inflated graph state, their overall product equals $-1$ and all Pauli operators in the set of submeasurements, together with the Pauli operators from the Pauli measurements on the neighbours up to distance $d$, occur in even pairs. Thus, the new Pauli measurements exhibit correlations that no distance-$d$ communication-assisted LHV model can predict.

Given a set of Pauli measurements $(M_1, \dots, M_N)$ that fulfill Eqs. (6)–(8) on the original graph state, we construct a set of Inflated measurements $(M'_1, \dots, M'_N)$ according to Def. IV.1. Furthermore, we define Inflated stabiliser elements $(S'_1, \dots, S'_N)$ following Def. IV.3 for the stabiliser elements $(S_1 = \chi_1 \tilde{M}_1, \dots, S_N = \chi_N \tilde{M}_N)$ on the original graph state from Eq. (7).

**Lemma V.1.** Starting from a Pauli measurement $M_k = \chi_k S_k$ on the original graph state, given the respective Inflated measurement $M'_k$ from Def. IV.1 and Inflated stabiliser element $S'_k$ from Def. IV.3, then $C'_k = \chi'_k S'_k$ is a submeasurement of the Inflated measurement $M'_k$ and $\chi'_k = \chi_k$.

*Proof.* First, we map the Inflated stabiliser element from its decomposition in generator elements to the representation with a sign factor $\chi'_k$ and local Pauli operators using Eq. (5). From Def. IV.3 the power vertices contribute a generator element if and only if a vertex on the original graph. The nearest-neighbour (a chain vertex) of a power
vertex on the inflated graph contributes a generator element if and only if a nearest-neighbour vertex on the original graph contributes a generator element. Thus, the contribution of generator elements on the power vertices is the same as for the original vertices. As a result, a power vertex has the same Pauli operator with the same local sign as the vertex on the original stabiliser element. Therefore, the submeasurement perfectly coincides with the Pauli measurements on the power vertices and the overall sign is the same.

For the chain vertices, they contribute a generator element if and only if their neighbors at distance 2. As a result the respective $t_w$ mod 2 = 0 from Eq. (5) and therefore, $\sigma_w = X_w$ or $\sigma_w = \mathbb{1}_w$, depending on whether chain vertex $w$ contributes a generator element. This complies with the Inflated measurements where all Pauli operators on the chain vertices are $X$. A minus sign occurs if chain vertex $w$ and its nearest neighbors contribute a generator element, in which case all chain vertices of a given chain do. Since there are an even number of chain vertices in every chain the cumulative sign is +1. Altogether the chain vertices do not invoke a sign change. $\square$

**Lemma V.2.** *The submeasurements ($C'_1 = \chi_1 S'_1, \dots, C'_N = \chi_N S'_N$) of the Inflated measurements ($M'_1, \dots, M'_N$) fulfill Eq. (6) for all vertices and Eq. (7), (8) on the inflated graph state.*

*Proof.* According to Lemma V.1 the submeasurements fulfill Eq. (7). In its proof, we also show that $(C'_k)_u = (M'_k)_u$ on all power vertices $u$. Furthermore, the chain vertices measure Pauli operator $X$ if and only if they contribute a generator element, which they do if and only if the closest power vertex at even distance (from Def. IV.2). Due to, (6) for the original Pauli measurements, the Pauli operators and generator elements occur an even number of times across the set of original Pauli measurements (which are proportional to stabiliser elements on the original graph). As a result, Pauli operators occur an even number of times in the set of submeasurements for all power and chain vertices. Consequently, Eq. (6) holds for all vertices. Lastly, following Lemma V.1, it is $\chi_k = \chi'_k$ and therefore Eq. (8) holds for the set of submeasurements. $\square$

**Lemma V.3.** *The submeasurements ($C'_1 = \chi_1 S'_1, \dots, C'_N = \chi_N S'_N$) and Inflated measurements ($M'_1, \dots, M'_N$) fulfill Eq. (10) on the power vertices.*

*Proof.* The Inflated measurements have Pauli operator $X$ on all chain vertices. Up to distance $d$, all neighbour vertices of any power vertex $u$ are chain vertices, thus $(M_k)_u^d = \sigma_u^k \otimes_{0<|u-v|\le d} X_v$. Since the $\{\sigma_u^k\}_k = \{(M_k)_u\}_k$ fulfill Eq. (6) for all $u \in V$, the $\{M'_k, C'_k\}_k$ fulfill Eq. (10) on all power vertices. $\square$

**Lemma V.4.** *Either the submeasurements ($C'_1 = \chi_1 S'_1, \dots, C'_N = \chi_N S'_N$) and Inflated measurements ($M'_1, \dots, M'_N$) fulfill Eq. (10) on the chain vertices or we can add pairs of decoy measurements from Def. IV.5 with a Shell stabiliser element as both submeasurements to the set of Pauli measurements such that the complete set fulfills Eq. (10) on all vertices.*

*Proof.* We evaluate Eq. (10) for a given chain vertex $w$. Let us call $u$ the power vertex at the end of $w$'s chain with even distance, then $(C'_k)_w \ne \mathbb{1}_w$ if and only if $u$ contributes a generator element to all $S'_k$ with $C'_k = \chi_k S'_k$. Up to distance $d$ along the graph's edges, almost all neighbours of $w$ are chain vertices, thus measuring Pauli operator $X$, the only exception being the closest power vertex of $w$, which we call $v$ ($|v-w| \le d$). Therefore, if $u$ contributes a generator element to $S'_k$, then we are interested in $(M_k)_w^d = \sigma_v \otimes_{w' \ne v, 0 \le |w'-w| \le d} X_{w'}$.

For $u = v$, that is for $|w-v|$ even, Eq. (10) holds for chain vertex $w$, since $(C'_k)_u = (M'_k)_u$ and Lemma V.3 holds on all power vertices $u$.

For $u \ne v$, that is if $|w-v|$ odd, we study how Eq. (10) might not hold on vertex $w$. Consider a set of four Inflated measurements $M'_{k_1}, M'_{k_2}, M'_{l_1}, M'_{l_2}$ with submeasurements, such that $(C'_{k_1})_u = (C'_{l_1})_u, (C'_{k_2})_u = (C'_{l_2})_u, (C'_{k_1})_u \ne (C'_{k_2})_u$. Furthermore, recall $C' = \chi_k S'$, power vertex $v$ contributes a generator element to both $S'_{k_{1,2}}$ while it does to neither of $S'_{l_{1,2}}$. Since Eq. (10) holds on both power vertices $u, v$, such a set either exists or Eq. (10) holds on vertex $w$.

Since the submeasurement are proportional to Inflated Stabiliser elements, the Pauli operators on the power vertex $u$ depends on the contribution of generator elements from main vertex $u$ and its power vertex neighbors, including $v$, following Eq. (5). For two Inflated stabiliser elements with the same Pauli operator on vertex $u$, the contribution to the generator elements from $u$ is the same and from its neighbors modulo two. In the quartet, the measurements $k_1, l_1$ have the same Pauli operator on power vertex $u$ but the power vertex neighbor $v$ does not contribute a generator element to the stabiliser elements they are proportional to. Therefore, there must exist a second power vertex $v'$, which is a power vertex neighbor of $u$ (not necessarily $v$), with opposing contribution of generator element to the stabiliser elements $k_1, l_1$. The same holds for $k_2, l_2$. Note that there might be additional power vertices, but since they must occur in pairs, they can also make their own set of four Inflated measurements. Note furthermore, that, while we focussed on chain vertex $w$, the above quartet accounts of all chain vertices with nearest power vertex $u$ and nearest power vertex at even distance $v$ or $v'$, for all of which Eq. (10) does not hold.

For such a quartet of Inflated Pauli measurements $M'_{k_1}, M'_{k_2}, M'_{l_1}, M'_{l_2}$ we add two decoy measurements $\tilde{M}'_1$ and $\tilde{M}'_2$ from Def. IV.5 with one Shell stabilizer element from Def. IV.4 for both submeasurements around the power vertex $u$ with neighbor power vertices $v$ and $v'$. The Pauli operators are $(\tilde{M}'_1)_u = (M'_{k_1})_u = (M'_{l_1})_u$ and $(\tilde{M}'_2)_u = (M'_{k_2})_u = (M'_{l_2})_u$. It might occur, that two of the four measurements already have the form of Shell stabiliser elements, in which case, we do not need to add the decoy measurements but alter the two measurements
on the power vertex u to have the same Pauli operator as the other to measurements of the quartet.

The added decoy measurements alter Eq. (10) for chain vertices whose closest power vertex is u. Additionally, their submeasurement only measure Pauli operator X on chain vertices with odd distance to power vertex u. As a result, they target precisely those chain vertices, for which Eq. (10) did not hold. One decoy measurement corrects Eq. (10) either for two chain branches and the same Pauli operator σ_u or for the same chain branch and different Pauli operators. □

Altogether, the set of Inflated measurements and sub-measurements constructed in Def.IV.1 and Def.IV.3 from the original set of Pauli measurements fulfill the Eqs. (11)–(10) on all power vertices and most chain vertices. If the above does not hold, one can always isolate responsible sets of four Inflated measurements. Then Def. IV.5 provides an algorithm to construct specific pairs of decoy measurements and submeasurements such that the overall set fulfills Eq. (10) on all vertices. The additional sub-measurements do not impede the results of Lemma V.2 as they occur in equal pairs.

## VI. BELL INEQUALITY

It is often useful to translate statements of non-locality into statistically robust inequalities, in order to experimentally test, or indeed use these kind of statements. Given a GHSZ-like paradox on a graph state, i.e. a set of measurements that fulfills Eqs. (6)–(8), one can sum up the measurements’ operators to form a Bell operator and obtain a corresponding Bell inequality for any LHV model. Specifically, take Eq. (7) and define $B = \sum_k \chi_k M_k = \sum_k S_k$ Suppose the GHSZ-like paradox consists of N measurements, any LHV model predicts

$$ \langle \mathcal{B} \rangle_{\text{LHV}} = \sum_{k=1}^{N} \chi_k < N = \langle \mathcal{B} \rangle_{\text{QM}}. \quad (16) $$

Due to Eq. (8) the inequality must be strict.

One can do the same thing for the inflated graphs, to give bell inequalities for d-LHV* models. We can define a Bell operator from the set of measurements and corresponding submeasurements on the d-inflated graph state, that is $B' = \sum_k \chi'_k C'_k$. The constituting N' submeasurements form a Bell inequality for any communication-assisted LHV (d-LHV*) model,

$$ \langle \mathcal{B}' \rangle_{d-\text{LHV}^*} = \sum_{k=1}^{N'} \chi'_k < N' = \langle \mathcal{B}' \rangle_{\text{QM}}, \quad (17) $$

as they fulfill Eqs. (10)–(12). The relations between these values and the number 2s of added decoy measurements from Def. IV.4 that sustain the paradox in the d-LHV*

<figure><img src="image_4.png" /><figcaption>FIG. 3: Inflated graph for $d=1$ with 7 vertices in a chain from smallest non-trivial graph with 3 vertices in a chain (considering only large balls). The symbols inside the balls denote Pauli operators of Pauli measurements on the corresponding graph states.</figcaption></figure>

setting are simple:

$$ \langle \mathcal{B}' \rangle_{\text{QM}} = N' = N + 2s = \langle \mathcal{B} \rangle_{\text{QM}} + 2s, \quad (18) $$

$$ \langle \mathcal{B}' \rangle_{d-\text{LHV}^*} = \sum_{k=1}^{N'} \chi'_k = \sum_{k=1}^{N} \chi_k + 2s = \langle \mathcal{B} \rangle_{\text{LHV}} + 2s, \quad (19) $$

The violation ratio of the Bell inequality for the original graph state, against any LHV model, is therefore greater than or equal to the violation ratio of the Bell inequality for the inflated graph state against any d-LHV* model:

$$ \frac{\langle \mathcal{B} \rangle_{\text{QM}}}{\langle \mathcal{B} \rangle_{\text{LHV}}} \geq \frac{\langle \mathcal{B} \rangle_{\text{QM}} + 2s}{\langle \mathcal{B} \rangle_{\text{LHV}} + 2s} = \frac{\langle \mathcal{B}' \rangle_{\text{QM}}}{\langle \mathcal{B} \rangle_{d-\text{LHV}^*}}. $$

## VII. SMALL GRAPH STATES

We now move to consider what are the smallest examples that can contradict d-LHV* models. In the original work of [12] the smallest example used 12 qubits. Our construction can use 7 starting from a line of three (See below). We will further find that through a slightly different construction we can show a contradiction with 1-LHV* models using linear graph state of 4 qubits. Interestingly, to have examples using graph states of fewer than 5 qubits, one requires non-Pauli measurements.

### A. Smallest 1-LHV*-violating inflated graph

Consider first the linear graph state with 7 vertices drawn in Fig. 3. It can be considered as an $d=1$-inflated graph of the linear graph state with three qubits in a line, which is locally equivalent to the GHZ state. Here, no LHV model can reproduce the measurement outcome of the four Pauli products $M_1 = Y_1 X_2 Y_3$, $M_2 = Y_1 Y_2 Z_3$, $M_3 = Z_1 Y_2 Y_3$, $M_4 = Z_1 X_2 Z_3$. Then, we construct the Pauli measurements and submeasurements (omitting
<figure><img src="image_5.png" /><figcaption>(a) Linear graph, $l=3$</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>(b) Circular graph</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>(c) Triangle graph</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>(d) Fully connected graph</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>(e) Star graph</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>(f) Square graph</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>(g) Linear graph, $l=4$</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>(h) Two triangle graphs sharing one edge</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>(i) Triangle graph with appendix.</figcaption></figure>

FIG. 4: Circular Graph of 5 vertices in b) and all connected graphs with 3 and 4 vertices. Highlighted vertices flip output variable's sign in 1-LHV* model if they and their direct neighbours measure the indicated Pauli operators. Unspecified operators might be any Pauli operator. Symmetrically equivalent vertices and operators also flip the variables' sign. In (h) it is $\sigma_1\sigma_2\sigma_3\sigma_4 = X_1Y_2Z_3Y_4$ for vertex 1 and $\sigma_1\sigma_2\sigma_3 = Y_1X_2Y_3$ for vertex 2. In (i) it is either $\sigma_1\sigma_2\sigma_3\sigma_4 = Y_1X_2X_3Y_4$ or $\sigma_1\sigma_2\sigma_3\sigma_4 = X_1X_2X_3Z_4$.

grayed out Pauli operators)

$$M'_{1} = Y_{1} X_{1(1,2)} X_{2(1,2)} X_{2} X_{1(2,3)} X_{2(2,3)} Y_{3},$$

$$M'_{2} = Y_{1} X_{1(1,2)} X_{2(1,2)} Y_{2} X_{1(2,3)} X_{2(2,3)} Z_{3},$$

$$M'_{3} = Z_{1} X_{1(1,2)} X_{2(1,2)} Y_{2} X_{1(2,3)} X_{2(2,3)} Y_{3},$$

$$M'_{4} = Z_{1} X_{1(1,2)} X_{2(1,2)} X_{2} X_{1(2,3)} X_{2(2,3)} Z_{3},$$

$$\tilde{M}'_{1} = X_{1} X_{1(1,2)} X_{2(1,2)} X_{2} X_{1(2,3)} X_{2(2,3)} X_{3},$$

$$\tilde{M}'_{2} = X_{1} X_{1(1,2)} X_{2(1,2)} Y_{2} X_{1(2,3)} X_{2(2,3)} X_{3},$$

which leads to the constraints $\langle M'_{k} \rangle_{QM} = \langle M'_{k} \rangle_{1-LHV*}$, for any nearest-neighbour communication-assisted LHV

model

$$-1 = y_1 x_{1(1,2)}^Y x_{2(1,2)}^X x_2 x_{1(2,3)}^X x_{2(2,3)}^Y y_3,$$

$$1 = y_1 x_{1(1,2)}^Y x_{2(1,2)}^Y y_2 x_{2(2,3)}^Z z_3,$$

$$1 = z_1 x_{1(1,2)}^Z y_2 x_{1(2,3)}^Y x_{2(2,3)}^Y y_3,$$

$$1 = z_1 x_{1(1,2)}^Z x_2 x_{2(2,3)}^Z z_3,$$

$$1 = x_1 x_{2(1,2)}^X x_{1(2,3)}^X x_3,$$

$$1 = x_1 x_{2(1,2)}^Y x_{2(2,3)}^Y x_3,$$

The superscripts denote the information acquired from communication with the vertices that change their Pauli operator in the different measurements. Multiplying the constraints results in $-1 = 1$, a contradiction. Thus, no 1-LHV* model can predict all correlations for the 7 qubit chain graph state. Note that the Pauli operators for Pauli products $M'_{1,2,3,4}$ match the ones in $M_{1,2,3,4}$ on the power vertices 1, 2, 3. The Pauli operators $M'_{5,6}$ are added as decoy measurements so that the LHV model fails to distinguish between power vertex 2 measuring $X_2$ or $Y_2$ on the adjacent chain vertices.

More quantitatively, this example shows a 1-LHV* violation ratio of $\frac{6}{4} = \frac{3}{2}$ by inflating the 3-qubit linear graph state to 7 qubits, the later showing a LHV violation ratio of $\frac{4}{2} = 2$.

## B. Smallest 1-LHV*-violating graph through Pauli measurements

The smallest graph state where no 1-LHV* model can reproduce submeasurements from Pauli measurements is the one with 5 vertices in a circle which is drawn in Fig. 4b. These do not follow the structure of the Inflated Pauli measurements and 16 Pauli measurements are needed that exploit the rotational symmetry of the cyclic graph. These are

$$M'_{1} = X_{1} X_{2} X_{3} X_{4} X_{5},$$

$$M'_{2+k} = (X_{1} X_{2} Y_{3} X_{4} X_{5})_{k},$$

$$M'_{7+k} = (Y_{1} X_{2} X_{3} Y_{4} Y_{5})_{k},$$

$$M'_{12+k} = (Y_{1} X_{2} X_{3} Y_{4} X_{5})_{k},$$

with $k = 0, \dots, 4$ denoting a cyclic rotation of the operators. Comparing $\langle M'_{k} \rangle_{QM} = \langle M'_{k} \rangle_{1-LHV*}$ leads to constraints on the variables

$$-1 = x_{1}^{XX} x_{2}^{XX} x_{3}^{XX} x_{4}^{XX} x_{5}^{XX},$$

$$1 = (x_{1}^{XX} \quad y_{3}^{XY} \quad y_{4}^{XY})_{k},$$

$$1 = (y_{1}^{XY} x_{2}^{XY} x_{3}^{XY} y_{4}^{XY})_{k},$$

$$1 = (y_{1}^{XX} x_{2}^{XY} x_{3}^{XY} y_{4}^{XX})_{k},$$

which leads to a contradiction. We have thus obtained a 1-LHV* violation of $\frac{16}{14}$ using Pauli measurements on five qubits.
In order to prove that a graph state with 5 qubits is the smallest graph state such that no 1-LHV* model can predict all Pauli measurements, we show that for every graph state with less than 5 qubits, there exist a 1-LHV* model that correctly predicts the outcome of all Pauli measurements. The model is similar to one proposed by Barrett, Caves et al. in [12]. Specifically, for every vertex $u$, we define hidden variables $z_u, x_u, y_u = \pm 1$ as the output values for a $Z_u, X_u, Y_u$ Pauli measurement. The variables' value $z_u = \pm 1$ is chosen uniformly at random, then one calculates the values of variables $x_u = \prod_{(u,v) \in E} z_v$ and $y_u = x_u z_u$. If no measurement is performed on a vertex, the assumed output is 1. So far the model is a LHV model since it does not rely on any classical communication. Every vertex has the variables $1, z_u, x_u, y_u$ at disposal as output given a local Pauli operator. Any Pauli measurements outcome is then a product of these variables.

We argue that this model correctly predicts any Pauli measurement except when $M = \otimes_u \sigma_u = -S$ for a stabiliser element in Eq.(3). Compare 1 = $x_u \prod_{(u,v) \in E} z_v$ to Eq.(1) to note that the model predicts the measurement of a generator element of the graph state correctly. Furthermore, $y_u = x_u z_u$ mimics the product of Pauli operators up to the missing imaginary unit $i$. Therefore, the model only makes an error, if the missing imaginary units inflict a sign change, which happens exactly for the stabiliser elements with $\chi = -1$ in Eq. (3). A more detailed reasoning can be found in [12].

Including a round of classical communication between along the graph's edges up to distance $d$, a successful model selects the cases when a sign flip of a vertex's output variable is necessary, while remaining foolproof to a submeasurement scheme ignoring certain vertices' outputs. For every connected graph with less than 5 vertices, we display the cases of a needed sign flip in Fig. 4 based on the LHV model described above. An analysis of all the possible Pauli measurements and submeasurements on the graph states reveals that the Distance-1-communication-assisted LHV model predicts the outcomes in accordance with a quantum measurement on the graph state.

### C. Smallest 1-LHV*-violating graph through Clifford measurements

The smallest example for any violation of a 1-LHV* model using binary inputs and outputs is the distance-1 inflated CHSH inequality that resorts to Clifford measurements on a chain of 4 qubits. The Bell operator is

$$ \mathcal{B} = (R_X(\frac{\pi}{2})_1 X_2 + R_X(\frac{3\pi}{2})_1 X_2) X_3 X_4 + (R_X(\frac{\pi}{2})_1 X_2 - R_X(\frac{3\pi}{2})_1 X_2) X_3 Y_4, \quad (20) $$

with $R_X(\theta)_1 = \cos(\frac{\theta}{2})Z_1 + \sin(\frac{\theta}{2})Y_1$ and the grayed-out operator output is ignored in the measurement's outcome.

A 1-LHV* model obeys $\langle \mathcal{B} \rangle_{1-LHV*} \le 2$ while the measurement outcome on the 4 qubit chain graph state equals $\langle \mathcal{B}_{QM} \rangle = 2\sqrt{2}$, leading to a violation ratio of $\sqrt{2}$. This can easily be checked using the same reasoning as above.

This 4-qubit graph is the smallest graph state showing violations for the restricted case of binary inputs and outputs. Indeed, the both 3-qubit graphs states can be simulated classically in this setting. This is obvious for the triangle, where everyone knows all the settings; and Chaves et al. [18, A.3] showed through convex optimization the class corresponding to a 3-qubit linear graph-state in 1-LHV* — the class $\{(1,3), (2,3), (1,2,3)\}$ in their terminology — is nonsignalling boring for binary inputs and outputs.

## VIII. CONCLUSION

From any graph states with more than three connected vertices we constructed a set of Pauli measurements on a $d$-inflated version of the original graph. The set contradicts any LHV model even assisted by classical communication along the graph's edges up to distance $d$. We state the violation in terms of a GHSZ-like paradox which we can write it in terms of a Bell inequality. The construction and proof works for any integer $d$, such that successive inflation is also possible.

Furthermore, we found a set of Pauli measurements for the smallest graph state that is robust against a LHV description including nearest-neighbour classical communication, the circular graph on 5 qubits. The smallest graph state that defies a nearest-neighbour Communication-Assisted LHV model using binary inputs and outputs is a linear graph on 4 qubits; we provide a Bell inequality that uses Clifford operators for this case.

These results are useful in two directions at least. Firstly, we have found much smaller examples than previously, which are minimal in size using only four qubits, well within the reach of many experimental labs. Secondly, the existence of correlations which cannot be explained by communication assisted LHV has already found applications in proving classical and quantum separation for shallow circuits [14, 19], distributed computing [15], and giving novel ways to certify randomness [16]. Given the extent that graph states are used in quantum information, from fault tolerance to quantum sensing, this work gives a good route to finding more applications or improving on those existing.

## ACKNOWLEDGMENTS

We acknowledge funding from the ANR through the ANR-17-CE24-0035 VanQuTe project and EU/ANR via QuantERA/ShoQC ANR-19-QUAN-0005-05.
[1] Marc Hein, Jens Eisert, and Hans J Briegel. Multiparty entanglement in graph states. *Physical Review A*, 69(6): 062311, 2004.

[2] Daniel M. Greenberger, Michael A. Horne, and Anton Zeilinger. *Going Beyond Bell's Theorem*, pages 69–72. Springer Netherlands, Dordrecht, 1989. ISBN 978-94-017-0849-4. doi:10.1007/978-94-017-0849-4_10. URL https://doi.org/10.1007/978-94-017-0849-4_10.

[3] Robert Raussendorf and Hans J Briegel. A one-way quantum computer. *Physical review letters*, 86(22):5188, 2001.

[4] Dirk Schlingemann and Reinhard F Werner. Quantum error-correcting codes associated with graphs. *Physical Review A*, 65(1):012308, 2001.

[5] Earl T Campbell, Barbara M Terhal, and Christophe Vuillot. Roads towards fault-tolerant universal quantum computation. *Nature*, 549(7671):172–179, 2017.

[6] Nathan Shettell and Damian Markham. Graph states as a resource for quantum metrology. *Physical review letters*, 124(11):110502, 2020.

[7] Damian Markham and Barry C Sanders. Graph states for quantum secret sharing. *Physical Review A*, 78(4): 042309, 2008.

[8] Matthias Christandl and Stephanie Wehner. Quantum anonymous transmissions. In *International conference on the theory and application of cryptology and information security*, pages 217–235. Springer, 2005.

[9] Nicolas Brunner, Daniel Cavalcanti, Stefano Pironio, Valerio Scarani, and Stephanie Wehner. Bell nonlocality. *Reviews of Modern Physics*, 86(2):419, 2014.

[10] Otfried Gühne, Géza Tóth, Philipp Hyllus, and Hans J Briegel. Bell inequalities for graph states. *Physical review letters*, 95(12):120405, 2005.

[11] Valerio Scarani, Antonio Acín, Emmanuel Schenck, and Markus Aspelmeyer. Nonlocality of cluster states of qubits. *Phys. Rev. A*, 71:042325, 4 2005. doi: 10.1103/PhysRevA.71.042325. URL https://link.aps.org/doi/10.1103/PhysRevA.71.042325.

[12] Jonathan Barrett, Carlton M Caves, Bryan Eastin, Matthew B Elliott, and Stefano Pironio. Modeling pauli measurements on graph states with nearest-neighbor classical communication. *Physical Review A*, 75(1):012103, 2007.

[13] Daniel M Greenberger, Michael A Horne, Abner Shimony, and Anton Zeilinger. Bell's theorem without inequalities. *American Journal of Physics*, 58(12):1131–1143, 1990. doi:10.1119/1.16243.

[14] Sergey Bravyi, David Gosset, and Robert König. Quantum advantage with shallow circuits. *Science*, 362(6412): 308–311, 2018.

[15] François Le Gall, Harumichi Nishimura, and Analysis Rosmanis. Quantum Advantage for the LOCAL Model in Distributed Computing. In Rolf Niedermeier and Christophe Paul, editors, *36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)*, volume 126 of *Leibniz International Proceedings in Informatics (LIPIcs)*, pages 49:1–49:14, Dagstuhl, Germany, 2019. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. ISBN 978-3-95977-100-9. doi: 10.4230/LIPIcs.STACS.2019.49. URL http://drops.dagstuhl.de/opus/volltexte/2019/10288.

[16] Matthew Coudron, Jalex Stark, and Thomas Vidick. Trading locality for time: certifiable randomness from low-depth circuits. *arXiv preprint arXiv:1810.04233*, 2018.

[17] N David Mermin. Simple unified form for the major no-hidden-variables theorems. *Physical review letters*, 65(27): 3373, 1990.

[18] Rafael Chaves, Daniel Cavalcanti, and Leandro Aolita. Causal hierarchy of multipartite bell nonlocality. *Quantum*, 1:23, April 2017. doi:10.22331/q-2017-08-04-23.

[19] Sergey Bravyi, David Gosset, Robert Koenig, and Marco Tomamichel. Quantum advantage with noisy shallow circuits. *Nature Physics*, 16(10):1040–1045, 2020.