Graph states correspond to mathematical graphs and exhibit nonlocality, as no local hidden-variable (lhv) model can predict all their measurement correlations. In this thesis, we study extensions of nonlocality in graph states, where we allow lhv models to engage in a round of distance-$ddc$ classical communication along the graph's edges, denote as r-lhv* models. Barrett et al.[2007] were the first to report correlations from local Pauli measurements on a particular family of graphs states to refute an r-lhv* description. Their result was pivotal in demonstrating a separation between classical and quantum computing regarding circuit depth without relying on any complexity-theoretic assumptions. Inspired by Barrett et al.'s findings, our first result is a systematic extension of any graph state to what we call `inflated graph state'. These states exhibit correlations that refute any communication-assisted lhv model. For certain graph topologies, the size and number of measurements can be optimized. The smallest graph exhibiting nonlocal correlations from Pauli measurements, while permitting nearest-neighbor communication, is the circle of five qubits. Additionally, the linear graph of four vertices presents the smallest possible such violation using binary inputs and outputs.
Our second result explores the application of the setting compatible with r-lhv* models to self-testing, a method to infer the state and operations based purely on the statistics of measurement outcomes. In particular, all graph states can be self-tested in the standard setting, where parties are not allowed to communicate. We develop a self-testing method within the framework of bounded classical communication, demonstrating that certain graph states can still be robustly self-tested even when communication is allowed. Specifically, we provide an explicit self-test for the circular graph state, as well as the honeycomb and square cluster states — both of which are known to be universal resources for measurement-based quantum computation. Given that communication typically obstructs the self-testing of graph states, we also present a procedure to robustly self-test any graph state by using the inflated graph states, which exhibit nonlocal correlations against bounded classical communication.
We expect these findings to have be useful in an interactive prover scheme while relaxing the standard assumption that the provers cannot communicate, the provers might now engage in distance-bounded classical communication. While the above results are only valid for qubits --two-dimensional systems--, we show that correlations the defy r-lhv* models also exists for graph states in so-called qudit systems for any finite, odd, prime dimension d. For this purpose, we study nonlocality in qudit systems in the standard Bell scenario without communication, as part of our third result.
First, we construct specific correlations that defy lhv models deterministically, as well as correlations that do so with a constant number of measurements, relying on operators innate to higher-dimensional systems than the qudit at hand.
Then, we propose a family of Bell inequalities using correlations related to a given entangled state's Wigner negativity. For a violation with stabilizer states, we resort to Pauli measurements under the adjoint action of a generalization of the qubit pi/8 gate, an abstraction of the Clauser-Horne-Shimony-Holt inequality.
This result can be extended to multipartite stabilizer states, including graph states, where we demonstrate violations robust against bounded classical communication.