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

arXiv:2404.03496 · Quantum

Self-Testing Graph States Permitting Bounded Classical Communication

Uta Isabella Meyer, Ivan Šupić, Frédéric Grosshans, Damian Markham

Published Jan 8, 2026• 4 citations
arXivHTMLPDF

Abstract

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.

DOI
10.22331/q-2026-01-08-1961

Related papers

Self-testing the toric code against classical communication

Gustavo Fróes, Amanda Wei, Carlos de Gois +2 more

Device-independent self-testing certifies a multipartite quantum state from the correlations it produces alone, without assumptions on the inner workings of the devices. Most existing self-tests, however, break down as soon as the parties can exchange messages. We consider a relaxed setting in a quantum network, where in the honest version of the protocol, the parties never communicate, yet certification remains sound even in an untrusted case where the untrusted devices secretly exchange classical messages within a bounded distance in the network. We show that the code space of the toric code, distributed over a network with the geometry of a torus, can be self-tested in this setting in a noise-robust way, against communication up to distances proportional to the network diameter. We also develop an algorithmic method for constructing such protocols and extend our results to the surface code and cluster states, robust to one round of nearest-neighbor classical communication

quant-pharXiv:2609.40259•Oct 1, 2026•0 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

Self-testing of a single quantum device under computational assumptions

Tony Metger, Thomas Vidick

Self-testing is a method to characterise an arbitrary quantum system based only on its classical input-output correlations, and plays an important role in device-independent quantum information processing as well as quantum complexity theory. Prior works on self-testing require the assumption that the system’s state is shared among multiple parties that only perform local measurements and cannot communicate. Here, we replace the setting of multiple non-communicating parties, which is difficult to enforce in practice, by a single computationally bounded party. Specifically, we construct a protocol that allows a classical verifier to robustly certify that a single computationally bounded quantum device must have prepared a Bell pair and performed single-qubit measurements on it, up to a change of basis applied to both the device’s state and measurements. This means that under computational assumptions, the verifier is able to certify the presence of entanglement, a property usually closely associated with two separated subsystems, inside a single quantum device. To achieve this, we build on techniques first introduced by Brakerski et al. (2018) and Mahadev (2018) which allow a classical verifier to constrain the actions of a quantum device assuming the device does not break post-quantum cryptography.

•Jan 1, 2021•11 citations

Quantum correlations on the no-signaling boundary: self-testing and more

Kai-Siang Chen, Gelo Noel M. Tabia, Chellasamy Jebarathinam +3 more

In device-independent quantum information, correlations between local measurement outcomes observed by spatially separated parties in a Bell test play a fundamental role. Even though it is long-known that the set of correlations allowed in quantum theory lies strictly between the Bell-local set and the no-signaling set, many questions concerning the geometry of the quantum set remain unanswered. Here, we revisit the problem of when the boundary of the quantum set coincides with the no-signaling set in the simplest Bell scenario. In particular, for each Class of these common boundaries containing k zero probabilities, we provide a (5−k) -parameter family of quantum strategies realizing these (extremal) correlations. We further prove that self-testing is possible in all nontrivial Classes beyond the known examples of Hardy-type correlations, and provide numerical evidence supporting the robustness of these self-testing results. Candidates of one-parameter families of self-testing correlations from some of these Classes are identified. As a byproduct of our investigation, if the qubit strategies leading to an extremal nonlocal correlation are local-unitarily equivalent, a self-testing statement provably follows. Interestingly, all these self-testing correlations found on the no-signaling boundary are provably non-exposed. An analogous characterization for the set M of quantum correlations arising from finite-dimensional maximally entangled states is also provided. En route to establishing this last result, we show that all correlations of M in the simplest Bell scenario are attainable as convex combinations of those achievable using a Bell pair and projective measurements. In turn, we obtain the maximal Clauser-Horne-Shimony-Holt Bell inequality violation by any maximally entangled two-qudit state and a no-go theorem regarding the self-testing of such states.

arXiv:2207.13850•Quantum•Jul 11, 2023•16 citations

Self-Testing of a Single Quantum Device Under Computational Assumptions

Tony Metger, Thomas Vidick

Self-testing is a method to characterise an arbitrary quantum system based only on its classical input-output correlations, and plays an important role in device-independent quantum information processing as well as quantum complexity theory. Prior works on self-testing require the assumption that the system’s state is shared among multiple parties that only perform local measurements and cannot communicate. Here, we replace the setting of multiple non-communicating parties, which is difficult to enforce in practice, by a single computationally bounded party. Specifically, we construct a protocol that allows a classical verifier to robustly certify that a single computationally bounded quantum device must have prepared a Bell pair and performed single-qubit measurements on it, up to a change of basis applied to both the device’s state and measurements. This means that under computational assumptions, the verifier is able to certify the presence of entanglement, a property usually closely associated with two separated subsystems, inside a single quantum device. To achieve this, we build on techniques first introduced by Brakerski et al. (2018) and Mahadev (2018) which allow a classical verifier to constrain the actions of a quantum device assuming the device does not break post-quantum cryptography.

•Jan 1, 2021•5 citations

Experimental self-testing for photonic graph states

Jia-Min Xu, Qing Fa Zhou, Yu-Xiang Yang +5 more

Graph states-one of the most representative families of multipartite entangled states-are important resources for multiparty quantum communication, quantum error correction, and quantum computation. Device-independent certification of highly entangled graph states plays a prominent role in quantum information processing tasks. Here we have experimentally demonstrated device-independent certification for multipartite graph states by adopting the robust self-testing scheme based on scalable Bell inequalities. Specifically, the prepared multi-qubit Greenberger-Horne-Zeilinger (GHZ) states and linear cluster states achieve a high degree of Bell violation, which are beyond the nontrivial bounds of the robust self-testing scheme. Furthermore, our work paves the way to the device-independent certification of complex multipartite quantum states.

arXiv:2111.07562•Optics Express•Dec 13, 2021•8 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.
Device-independent self-testing certifies a multipartite quantum state from the correlations it produces alone, without assumptions on the inner workings of the devices. Most existing self-tests, however, break down as soon as the parties can exchange messages. We consider a relaxed setting in a quantum network, where in the honest version of the protocol, the parties never communicate, yet certification remains sound even in an untrusted case where the untrusted devices secretly exchange classical messages within a bounded distance in the network. We show that the code space of the toric code, distributed over a network with the geometry of a torus, can be self-tested in this setting in a noise-robust way, against communication up to distances proportional to the network diameter. We also develop an algorithmic method for constructing such protocols and extend our results to the surface code and cluster states, robust to one round of nearest-neighbor classical communication
Self-testing is a method to characterise an arbitrary quantum system based only on its classical input-output correlations, and plays an important role in device-independent quantum information processing as well as quantum complexity theory. Prior works on self-testing require the assumption that the system’s state is shared among multiple parties that only perform local measurements and cannot communicate. Here, we replace the setting of multiple non-communicating parties, which is difficult to enforce in practice, by a single computationally bounded party. Specifically, we construct a protocol that allows a classical verifier to robustly certify that a single computationally bounded quantum device must have prepared a Bell pair and performed single-qubit measurements on it, up to a change of basis applied to both the device’s state and measurements. This means that under computational assumptions, the verifier is able to certify the presence of entanglement, a property usually closely associated with two separated subsystems, inside a single quantum device. To achieve this, we build on techniques first introduced by Brakerski et al. (2018) and Mahadev (2018) which allow a classical verifier to constrain the actions of a quantum device assuming the device does not break post-quantum cryptography.
In device-independent quantum information, correlations between local measurement outcomes observed by spatially separated parties in a Bell test play a fundamental role. Even though it is long-known that the set of correlations allowed in quantum theory lies strictly between the Bell-local set and the no-signaling set, many questions concerning the geometry of the quantum set remain unanswered. Here, we revisit the problem of when the boundary of the quantum set coincides with the no-signaling set in the simplest Bell scenario. In particular, for each Class of these common boundaries containing k zero probabilities, we provide a (5−k) -parameter family of quantum strategies realizing these (extremal) correlations. We further prove that self-testing is possible in all nontrivial Classes beyond the known examples of Hardy-type correlations, and provide numerical evidence supporting the robustness of these self-testing results. Candidates of one-parameter families of self-testing correlations from some of these Classes are identified. As a byproduct of our investigation, if the qubit strategies leading to an extremal nonlocal correlation are local-unitarily equivalent, a self-testing statement provably follows. Interestingly, all these self-testing correlations found on the no-signaling boundary are provably non-exposed. An analogous characterization for the set M of quantum correlations arising from finite-dimensional maximally entangled states is also provided. En route to establishing this last result, we show that all correlations of M in the simplest Bell scenario are attainable as convex combinations of those achievable using a Bell pair and projective measurements. In turn, we obtain the maximal Clauser-Horne-Shimony-Holt Bell inequality violation by any maximally entangled two-qudit state and a no-go theorem regarding the self-testing of such states.
Self-testing is a method to characterise an arbitrary quantum system based only on its classical input-output correlations, and plays an important role in device-independent quantum information processing as well as quantum complexity theory. Prior works on self-testing require the assumption that the system’s state is shared among multiple parties that only perform local measurements and cannot communicate. Here, we replace the setting of multiple non-communicating parties, which is difficult to enforce in practice, by a single computationally bounded party. Specifically, we construct a protocol that allows a classical verifier to robustly certify that a single computationally bounded quantum device must have prepared a Bell pair and performed single-qubit measurements on it, up to a change of basis applied to both the device’s state and measurements. This means that under computational assumptions, the verifier is able to certify the presence of entanglement, a property usually closely associated with two separated subsystems, inside a single quantum device. To achieve this, we build on techniques first introduced by Brakerski et al. (2018) and Mahadev (2018) which allow a classical verifier to constrain the actions of a quantum device assuming the device does not break post-quantum cryptography.
Graph states-one of the most representative families of multipartite entangled states-are important resources for multiparty quantum communication, quantum error correction, and quantum computation. Device-independent certification of highly entangled graph states plays a prominent role in quantum information processing tasks. Here we have experimentally demonstrated device-independent certification for multipartite graph states by adopting the robust self-testing scheme based on scalable Bell inequalities. Specifically, the prepared multi-qubit Greenberger-Horne-Zeilinger (GHZ) states and linear cluster states achieve a high degree of Bell violation, which are beyond the nontrivial bounds of the robust self-testing scheme. Furthermore, our work paves the way to the device-independent certification of complex multipartite quantum states.