Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

Self-Testing Graph States

Matthew McKague

Published Jan 1, 2014• 61 citations
Publisher
DOI
10.1007/978-3-642-54429-3_7

Related papers

Self-Testing Graph States Permitting Bounded Classical Communication

Uta Isabella Meyer, Ivan Šupić, Frédéric Grosshans +1 more

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.

arXiv:2404.03496•Quantum•Jan 8, 2026•4 citations

State transfer on graphs

Chris D. Godsil

arXiv:1102.4898•Discrete Mathematics•Aug 4, 2011•224 citations

Self-testing graph states

Matthew McKague

We give a construction for a self-test for any connected graph state. In other words, for each connected graph state we give a set of non-local correlations that can only be achieved (quantumly) by that particular graph state and certain local measurements. The number of correlations considered is small, being linear in the number of vertices in the graph. We also prove robustness for the test.

arXiv:1010.1989•Conference on Theory of Quantum Computation, Communication and Cryptography•Oct 11, 2010•38 citations

From graph states to two-graph states

Constanza Riera, Stéphane Jacob, Matthew Geoffrey Parker

arXiv:0801.4754•Designs Codes and Cryptography•Feb 28, 2008•6 citations

Interactive proofs for BQP via self-tested graph states

Matthew McKague

$ \newcommand{\cclass}[1]{\mathsf{#1}} $ Using the measurement-based quantum computation model, we construct interactive proofs with non-communicating quantum provers and a classical verifier. Our construction gives interactive proofs for all languages in $\cclass{BQP}$ with a polynomial number of quantum provers, each of which, in the honest case, performs only a single measurement. In this paper we introduce two main improvements over previous work in self-testing for graph states. Specifically, we derive new error bounds which scale polynomially with the size of the graph compared with exponential dependence on the size of the graph in previous work. We also extend the self-testing error bounds on measurements to a very general set which includes the adaptive measurements used for measurement-based quantum computation as a special case. These improvements allow us to apply graph state self-testing and measurement based quantum computation to build interactive proofs for all languages in $\cclass{BQP}$.

arXiv:1309.5675•Theory of Computing•Jan 1, 2016•120 citations

Universal state transfer on graphs

Stephen Cameron, Shannon Fehrenbach, Leah Granger +3 more

arXiv:1310.3885•Linear Algebra and its Applications•May 21, 2014•26 citations
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.
$ \newcommand{\cclass}[1]{\mathsf{#1}} $ Using the measurement-based quantum computation model, we construct interactive proofs with non-communicating quantum provers and a classical verifier. Our construction gives interactive proofs for all languages in $\cclass{BQP}$ with a polynomial number of quantum provers, each of which, in the honest case, performs only a single measurement. In this paper we introduce two main improvements over previous work in self-testing for graph states. Specifically, we derive new error bounds which scale polynomially with the size of the graph compared with exponential dependence on the size of the graph in previous work. We also extend the self-testing error bounds on measurements to a very general set which includes the adaptive measurements used for measurement-based quantum computation as a special case. These improvements allow us to apply graph state self-testing and measurement based quantum computation to build interactive proofs for all languages in $\cclass{BQP}$.