Self-Testing Graph States Permitting Bounded Classical Communication

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

doi:10.22331/q-2026-01-08-1961

Self-Testing Graph States Permitting Bounded Classical Communication

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

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

Published:	2026-01-08, volume 10, page 1961
Editor:	Remigiusz Augusiak
Eprint:	arXiv:2404.03496v4
Doi:	https://doi.org/10.22331/q-2026-01-08-1961
Citation:	Quantum 10, 1961 (2026).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

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.

► BibTeX data

@article{Meyer2026selftestinggraph,
  doi = {10.22331/q-2026-01-08-1961},
  url = {https://doi.org/10.22331/q-2026-01-08-1961},
  title = {Self-{T}esting {G}raph {S}tates {P}ermitting {B}ounded {C}lassical {C}ommunication},
  author = {Meyer, Uta Isabella and {\v{S}}upi{\'{c}}, Ivan and Grosshans, Fr{\'{e}}d{\'{e}}ric and Markham, Damian},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {10},
  pages = {1961},
  month = jan,
  year = {2026}
}

► References

[1] John S Bell. ``On the Einstein Podolsky Rosen paradox''. Physics Physique Fizika 1, 195–200 (1964).
https://doi.org/10.1103/PhysicsPhysiqueFizika.1.195

[2] Nicolas Brunner, Daniel Cavalcanti, Stefano Pironio, Valerio Scarani, and Stephanie Wehner. ``Bell nonlocality''. Rev. Mod. Phys. 86, 419–478 (2014).
https://doi.org/10.1103/RevModPhys.86.419

[3] Roger Colbeck. ``Quantum and relativistic protocols for secure multi-party computation''. PhD thesis. University of Cambridge. (2006). url: https://arxiv.org/abs/0911.3814.
arXiv:0911.3814

[4] Roger Colbeck and Adrian Kent. ``Private randomness expansion with untrusted devices''. Journal of Physics A: Mathematical and Theoretical 44, 095305 (2011).
https://doi.org/10.1088/1751-8113/44/9/095305

[5] Antonio Acín and Lluis Masanes. ``Certified randomness in quantum physics''. Nature 540, 213–219 (2016).
https://doi.org/10.1038/nature20119

[6] Stefano Pironio, Antonio Acín, Serge Massar, A Boyer de La Giroday, Dzimitry N Matsukevich, Peter Maunz, Steven Olmschenk, David Hayes, Le Luo, T Andrew Manning, et al. ``Random numbers certified by Bell's theorem''. Nature 464, 1021–1024 (2010).
https://doi.org/10.1038/nature09008

[7] Antonio Acín, Nicolas Gisin, and Lluis Masanes. ``From bell's theorem to secure quantum key distribution''. Phys. Rev. Lett. 97, 120405 (2006).
https://doi.org/10.1103/PhysRevLett.97.120405

[8] Antonio Acín, Nicolas Brunner, Nicolas Gisin, Serge Massar, Stefano Pironio, and Valerio Scarani. ``Device-independent security of quantum cryptography against collective attacks''. Phys. Rev. Lett. 98, 230501 (2007).
https://doi.org/10.1103/PhysRevLett.98.230501

[9] Dominic Mayers and Andrew Yao. ``Quantum cryptography with imperfect apparatus''. In Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280). Pages 503–509. (1998).
https://doi.org/10.1109/SFCS.1998.743501

[10] Dominic Mayers and Andrew Yao. ``Self testing quantum apparatus''. Quantum Information & Computation 4, 273–286 (2004).
https://doi.org/10.26421/QIC4.4-3

[11] Ivan Šupić and Joseph Bowles. ``Self-testing of quantum systems: a review''. Quantum 4, 337 (2020).
https://doi.org/10.22331/q-2020-09-30-337

[12] Umesh Vazirani and Thomas Vidick. ``Fully device independent quantum key distribution''. Commun. ACM 62, 133 (2019).
https://doi.org/10.1145/3310974

[13] Rotem Arnon-Friedman, Frédéric Dupuis, Omar Fawzi, Renato Renner, and Thomas Vidick. ``Practical device-independent quantum cryptography via entropy accumulation''. Nature communications 9, 459 (2018).
https://doi.org/10.1038/s41467-017-02307-4

[14] Rodrigo Gallego, Nicolas Brunner, Christopher Hadley, and Antonio Acín. ``Device-independent tests of classical and quantum dimensions''. Phys. Rev. Lett. 105, 230501 (2010).
https://doi.org/10.1103/PhysRevLett.105.230501

[15] Andrea Coladangelo, Alex B Grilo, Stacey Jeffery, and Thomas Vidick. ``Verifier-on-a-leash: new schemes for verifiable delegated quantum computation, with quasilinear resources''. In Annual international conference on the theory and applications of cryptographic techniques. Pages 247–277. Springer (2019).
https://doi.org/10.1007/978-3-030-17659-4_9

[16] Ben W Reichardt, Falk Unger, and Umesh Vazirani. ``Classical command of quantum systems''. Nature 496, 456–460 (2013).
https://doi.org/10.1038/nature12035

[17] Jérémy Ribeiro, Gláucia Murta, and Stephanie Wehner. ``Fully device-independent conference key agreement''. Physical Review A 97, 022307 (2018).
https://doi.org/10.1103/PhysRevA.97.022307

[18] Kim Vallée, Pierre-Emmanuel Emeriau, Boris Bourdoncle, Adel Sohbi, Shane Mansfield, and Damian Markham. ``Corrected bell and non-contextuality inequalities for realistic experiments''. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences 382, 20230011 (2024).
https://doi.org/10.1098/rsta.2023.0011

[19] Andreas Fyrillas, Boris Bourdoncle, Alexandre Maïnos, Pierre-Emmanuel Emeriau, Kayleigh Start, Nico Margaria, Martina Morassi, Aristide Lemaı̂tre, Isabelle Sagnes, Petr Stepanov, Thi Huong Au, Sébastien Boissier, Niccolo Somaschi, Nicolas Maring, Nadia Belabas, and Shane Mansfield. ``Certified randomness in tight space''. PRX Quantum 5, 020348 (2024).
https://doi.org/10.1103/PRXQuantum.5.020348

[20] Gláucia Murta and Flavio Baccari. ``Self-testing with dishonest parties and device-independent entanglement certification in quantum communication networks''. Phys. Rev. Lett. 131, 140201 (2023).
https://doi.org/10.1103/PhysRevLett.131.140201

[21] Richard Cleve, Peter Hoyer, Benjamin Toner, and John Watrous. ``Consequences and limits of nonlocal strategies''. In Proceedings. 19th IEEE Annual Conference on Computational Complexity, 2004. Pages 236–249. IEEE (2004).
https://doi.org/10.1109/CCC.2004.1313847

[22] Robert Raussendorf and Hans J. Briegel. ``A one-way quantum computer''. Phys. Rev. Lett. 86, 5188–5191 (2001).
https://doi.org/10.1103/PhysRevLett.86.5188

[23] Sara Bartolucci, Patrick Birchall, Hector Bombin, Hugo Cable, Chris Dawson, Mercedes Gimeno-Segovia, Eric Johnston, Konrad Kieling, Naomi Nickerson, Mihir Pant, et al. ``Fusion-based quantum computation''. Nature Communications 14, 912 (2023).
https://doi.org/10.1038/s41467-023-36493-1

[24] Daniel Gottesman. ``Stabilizer codes and quantum error correction''. Ph. D. thesis, California Institute of Technology (1997).
https://doi.org/10.48550/arXiv.quant-ph/9705052
arXiv:quant-ph/9705052

[25] Robert Raussendorf, Jim Harrington, and Kovid Goyal. ``A fault-tolerant one-way quantum computer''. Annals of physics 321, 2242–2270 (2006).
https://doi.org/10.1016/j.aop.2006.01.012

[26] Nathan Shettell and Damian Markham. ``Graph states as a resource for quantum metrology''. Phys. Rev. Lett. 124, 110502 (2020).
https://doi.org/10.1103/PhysRevLett.124.110502

[27] Damian Markham and Barry C. Sanders. ``Graph states for quantum secret sharing''. Phys. Rev. A 78, 042309 (2008).
https://doi.org/10.1103/PhysRevA.78.042309

[28] 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).
https://doi.org/10.1007/11593447_12

[29] Chao-Yang Lu, Xiao-Qi Zhou, Otfried Gühne, Wei-Bo Gao, Jin Zhang, Zhen-Sheng Yuan, Alexander Goebel, Tao Yang, and Jian-Wei Pan. ``Experimental entanglement of six photons in graph states''. Nature physics 3, 91–95 (2007).
https://doi.org/10.1038/nphys507

[30] Ido Schwartz, Dan Cogan, Emma R Schmidgall, Yaroslav Don, Liron Gantz, Oded Kenneth, Netanel H Lindner, and David Gershoni. ``Deterministic generation of a cluster state of entangled photons''. Science 354, 434–437 (2016).
https://doi.org/10.1126/science.aah4758

[31] D Istrati, Y Pilnyak, JC Loredo, C Antón, N Somaschi, P Hilaire, H Ollivier, M Esmann, L Cohen, L Vidro, et al. ``Sequential generation of linear cluster states from a single photon emitter''. Nature communications 11, 5501 (2020).
https://doi.org/10.1038/s41467-020-19341-4

[32] Bryn A Bell, DA Herrera-Martí, MS Tame, Damian Markham, WJ Wadsworth, and JG Rarity. ``Experimental demonstration of a graph state quantum error-correction code''. Nature communications 5, 3658 (2014).
https://doi.org/10.1038/ncomms4658

[33] BA Bell, Damian Markham, DA Herrera-Martí, Anne Marin, WJ Wadsworth, JG Rarity, and MS Tame. ``Experimental demonstration of graph-state quantum secret sharing''. Nature communications 5, 1–12 (2014).
https://doi.org/10.1038/ncomms6480

[34] Otfried Gühne, Géza Tóth, Philipp Hyllus, and Hans J. Briegel. ``Bell inequalities for graph states''. Phys. Rev. Lett. 95, 120405 (2005).
https://doi.org/10.1103/PhysRevLett.95.120405

[35] Géza Tóth, Otfried Gühne, and Hans J. Briegel. ``Two-setting bell inequalities for graph states''. Phys. Rev. A 73, 022303 (2006).
https://doi.org/10.1103/PhysRevA.73.022303

[36] Jonathan Barrett, Carlton M. Caves, Bryan Eastin, Matthew B. Elliott, and Stefano Pironio. ``Modeling Pauli measurements on graph states with nearest-neighbor classical communication''. Phys. Rev. A 75, 012103 (2007).
https://doi.org/10.1103/PhysRevA.75.012103

[37] Uta Isabella Meyer, Frédéric Grosshans, and Damian Markham. ``Inflated graph states refuting communication-assisted local-hidden-variable models''. Phys. Rev. A 108, 012402 (2023).
https://doi.org/10.1103/PhysRevA.108.012402

[38] François Le Gall, Harumichi Nishimura, and Ansis 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.
https://doi.org/10.4230/LIPIcs.STACS.2019.49

[39] Matthew Coudron, Jalex Stark, and Thomas Vidick. ``Trading locality for time: certifiable randomness from low-depth circuits''. Communications in mathematical physics 382, 49–86 (2021).
https://doi.org/10.1007/s00220-021-03963-w

[40] Sergey Bravyi, David Gosset, Robert Koenig, and Marco Tomamichel. ``Quantum advantage with noisy shallow circuits''. Nature Physics 16, 1040–1045 (2020).
https://doi.org/10.1038/s41567-020-0948-z

[41] Sergey Bravyi, David Gosset, and Robert König. ``Quantum advantage with shallow circuits''. Science 362, 308–311 (2018).
https://doi.org/10.1126/science.aar3106

[42] Hoi-Kwong Lo, Marcos Curty, and Bing Qi. ``Measurement-device-independent quantum key distribution''. Phys. Rev. Lett. 108, 130503 (2012).
https://doi.org/10.1103/PhysRevLett.108.130503

[43] Yan-Lin Tang, Hua-Lei Yin, Si-Jing Chen, Yang Liu, Wei-Jun Zhang, Xiao Jiang, Lu Zhang, Jian Wang, Li-Xing You, Jian-Yu Guan, Dong-Xu Yang, Zhen Wang, Hao Liang, Zhen Zhang, Nan Zhou, Xiongfeng Ma, Teng-Yun Chen, Qiang Zhang, and Jian-Wei Pan. ``Field test of measurement-device-independent quantum key distribution''. IEEE Journal of Selected Topics in Quantum Electronics 21, 116–122 (2015).
https://doi.org/10.1109/JSTQE.2014.2361796

[44] Alberto Boaron, Gianluca Boso, Davide Rusca, Cédric Vulliez, Claire Autebert, Misael Caloz, Matthieu Perrenoud, Gaëtan Gras, Félix Bussières, Ming-Jun Li, Daniel Nolan, Anthony Martin, and Hugo Zbinden. ``Secure quantum key distribution over 421 km of optical fiber''. Phys. Rev. Lett. 121, 190502 (2018).
https://doi.org/10.1103/PhysRevLett.121.190502

[45] R. Wang, R. Yang, M. J. Clark, R. D. Oliveira, S. Bahrani, M. Peranić, M. Lončarić, M. Stipčević, J. Rarity, S. K. Joshi, R. Nejabati, and D. Simeonidou. ``Field trial of a dynamically switched quantum network supporting co-existence of entanglement, prepare-and-measure qkd and classical channels''. In 49th European Conference on Optical Communications (ECOC 2023). Volume 2023, pages 1682–1685. (2023).
https://doi.org/10.1049/icp.2023.2666

[46] Maarten Van den Nest, Akimasa Miyake, Wolfgang Dür, and Hans J. Briegel. ``Universal resources for measurement-based quantum computation''. Phys. Rev. Lett. 97, 150504 (2006).
https://doi.org/10.1103/PhysRevLett.97.150504

[47] Matthew McKague. ``Self-testing graph states''. In Conference on Quantum Computation, Communication, and Cryptography. Pages 104–120. Springer (2011).
https://doi.org/10.1007/978-3-642-54429-3_7

[48] Valerio Scarani, Antonio Acín, Emmanuel Schenck, and Markus Aspelmeyer. ``Nonlocality of cluster states of qubits''. Phys. Rev. A 71, 042325 (2005).
https://doi.org/10.1103/PhysRevA.71.042325

[49] Matthew McKague. ``Interactive proofs for $\mathsf{BQP}$ via self-tested graph states''. Theory of Computing 12, 1–42 (2016).
https://doi.org/10.4086/toc.2016.v012a003

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

[51] Marc Hein, Jens Eisert, and Hans J Briegel. ``Multiparty entanglement in graph states''. Physical Review A 69, 062311 (2004).
https://doi.org/10.1103/PhysRevA.69.062311

[52] John F. Clauser, Michael A. Horne, Abner Shimony, and Richard A. Holt. ``Proposed experiment to test local hidden-variable theories''. Phys. Rev. Lett. 23, 880–884 (1969).
https://doi.org/10.1103/PhysRevLett.23.880

[53] Cédric Bamps and Stefano Pironio. ``Sum-of-squares decompositions for a family of Clauser-Horne-Shimony-Holt-like inequalities and their application to self-testing''. Phys. Rev. A 91, 052111 (2015).
https://doi.org/10.1103/PhysRevA.91.052111

[54] Ivan Šupić, Andrea Coladangelo, Remigiusz Augusiak, and Antonio Acín. ``Self-testing multipartite entangled states through projections onto two systems''. New journal of Physics 20, 083041 (2018).
https://doi.org/10.1088/1367-2630/aad89b

Cited by

[1] Konrad Szymański, Lina Vandré, and Otfried Gühne, "Useful entanglement can be extracted from noisy graph states", Quantum 10, 1977 (2026).

[2] Daniel Bhatti and Kenneth Goodenough, "Distributing graph states with a photon-weaving quantum server", arXiv:2504.07410, (2025).

[3] Konrad Szymański, Lina Vandré, and Otfried Gühne, "Useful entanglement can be extracted from noisy graph states", arXiv:2402.00937, (2024).

[4] Oliver Hart, David T. Stephen, Evan Wickenden, and Rahul Nandkishore, "Many-body contextuality and self-testing quantum matter via nonlocal games", arXiv:2512.16886, (2025).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-09 13:29:31) and SAO/NASA ADS (last updated successfully 2026-08-09 13:29:32). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.