Self-Testing Graph States Permitting Bounded Classical Communication

Self-testing identifies quantum states and correlations that exhibit nonlocality, distinguishing them, up to local transformations, from other quantum states. Due to their strong nonlocality, it is known that all graph states can be self-tested in the standard setting – where parties are not allowed to communicate. Recently it has been shown that graph states display nonlocal correlations even when bounded classical communication on the underlying graph is permitted, a feature that has found applications in proving a circuit-depth separation between classical and quantum computing. In this work, we develop self testing in the framework of bounded classical communication, and we show that certain graph states can be robustly self-tested even allowing for communication. In particular, we provide an explicit self-test for the circular graph state and the honeycomb cluster state – the latter known to be a universal resource for measurement based quantum computation. Since communication generally obstructs self-testing of graph states, we further provide a procedure to robustly self-test any graph state from larger ones that exhibit nonlocal correlations in the communication scenario.