{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:07:00Z","timestamp":1750694820930,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":50,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,6,17]],"date-time":"2024-06-17T00:00:00Z","timestamp":1718582400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,6,17]]},"DOI":"10.1145\/3662158.3662788","type":"proceedings-article","created":{"date-parts":[[2024,6,5]],"date-time":"2024-06-05T14:38:06Z","timestamp":1717598286000},"page":"220-230","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["On the Power of Quantum Distributed Proofs"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-7151-2793","authenticated-orcid":false,"given":"Atsuya","family":"Hasegawa","sequence":"first","affiliation":[{"name":"The University of Tokyo, Tokyo, Japan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8630-0113","authenticated-orcid":false,"given":"Srijita","family":"Kundu","sequence":"additional","affiliation":[{"name":"University of Waterloo, Waterloo, Canada"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2219-3320","authenticated-orcid":false,"given":"Harumichi","family":"Nishimura","sequence":"additional","affiliation":[{"name":"Nagoya University, Nagoya, Japan"}]}],"member":"320","published-online":{"date-parts":[[2024,6,17]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"The complexity of quantum states and transformations: from quantum money to black holes. arXiv preprint arXiv:1607.05256","author":"Aaronson Scott","year":"2016","unstructured":"Scott Aaronson. 2016. The complexity of quantum states and transformations: from quantum money to black holes. arXiv preprint arXiv:1607.05256 (2016)."},{"key":"e_1_3_2_1_2_1","volume-title":"Proceedings of the 30th annual ACM symposium on Theory of computing (STOC","author":"Aharonov Dorit","year":"1998","unstructured":"Dorit Aharonov, Alexei Kitaev, and Noam Nisan. 1998. Quantum circuits with mixed states. In Proceedings of the 30th annual ACM symposium on Theory of computing (STOC 1998). 20--30."},{"key":"e_1_3_2_1_3_1","volume-title":"Quantum NP - A Survey. arXiv preprint quant-ph\/0210077","author":"Aharonov Dorit","year":"2002","unstructured":"Dorit Aharonov and Tomer Naveh. 2002. Quantum NP - A Survey. arXiv preprint quant-ph\/0210077 (2002)."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2670418.2670440"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.97.170502"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796302452"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060662"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-011-1302-1"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1412700.1412717"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.87.167902"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/872746.873136"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2022.35"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/1009378.1009560"},{"key":"e_1_3_2_1_14_1","volume-title":"Henrik Lievonen, Augusto Modanese, Marc-Olivier Renou, Gustav Schmid, and Jukka Suomela.","author":"Coiteux-Roy Xavier","year":"2023","unstructured":"Xavier Coiteux-Roy, Francesco d'Amore, Rishikesh Gajjala, Fabian Kuhn, Fran\u00e7ois Le Gall, Henrik Lievonen, Augusto Modanese, Marc-Olivier Renou, Gustav Schmid, and Jukka Suomela. 2023. No distributed quantum advantage for approximate graph coloring. arXiv preprint arXiv:2307.09444 (2023)."},{"volume-title":"Quantum Computing and Communication Complexity. Ph. D. Dissertation","author":"de Wolf Ronald","key":"e_1_3_2_1_15_1","unstructured":"Ronald de Wolf. 2001. Quantum Computing and Communication Complexity. Ph. D. Dissertation. University of Amsterdam. https:\/\/homepages.cwi.nl\/~rdewolf\/publ\/qc\/phd.pdf"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1412700.1412718"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611488"},{"key":"e_1_3_2_1_18_1","volume-title":"Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing (PODC","author":"Fraigniaud Pierre","year":"2010","unstructured":"Pierre Fraigniaud. 2010. Distributed computational complexities: are you volvo-addicted or nascar-obsessed?. In Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing (PODC 2010). 171--172."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2021.28"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-018-0340-8"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212744"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.MFCS.2023.63"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.STACS.2023.42"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.STACS.2019.49"},{"key":"e_1_3_2_1_25_1","volume-title":"Non-trivial lower bound for 3-coloring the ring in the quantum LOCAL model. arXiv preprint arXiv:2212.02768","author":"Gall Fran\u00e7ois Le","year":"2022","unstructured":"Fran\u00e7ois Le Gall and Ansis Rosmanis. 2022. Non-trivial lower bound for 3-coloring the ring in the quantum LOCAL model. arXiv preprint arXiv:2212.02768 (2022)."},{"key":"e_1_3_2_1_26_1","volume-title":"Proceedings of International Symposium on Distributed Computing (DISC","author":"Gavoille Cyril","year":"2009","unstructured":"Cyril Gavoille, Adrian Kosowski, and Marcin Markiewicz. 2009. What can be observed locally? Round-based models for quantum distributed computing. In Proceedings of International Symposium on Distributed Computing (DISC 2009). 243--257."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1145\/3639528.3639535","article-title":"Guest Column: The 7 faces of quantum NP","volume":"54","author":"Gharibian Sevag","year":"2024","unstructured":"Sevag Gharibian. 2024. Guest Column: The 7 faces of quantum NP. ACM SIGACT News 54, 4 (2024), 54--91.","journal-title":"ACM SIGACT News"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2016.v012a019"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.11"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331628"},{"key":"e_1_3_2_1_32_1","volume-title":"Quantum Distributed Algorithm for Triangle Finding in the CONGEST Model. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)","volume":"13","author":"Izumi Taisuke","year":"2020","unstructured":"Taisuke Izumi, Fran\u00e7ois Le Gall, and Fr\u00e9d\u00e9ric Magniez. 2020. Quantum Distributed Algorithm for Triangle Finding in the CONGEST Model. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) (LIPIcs, Vol. 154). 23:1--23:13."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3485628"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1088\/1751-8113\/41\/39\/395309"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"crossref","unstructured":"Alexei Yu Kitaev Alexander Shen and Mikhail N Vyalyi. 2002. Classical and quantum computation. Number 47. American Mathematical Soc.","DOI":"10.1090\/gsm\/047"},{"key":"e_1_3_2_1_36_1","volume-title":"Proceedings of 26th Annual IEEE Conference on Computational Complexity (CCC","author":"Klauck Hartmut","year":"2011","unstructured":"Hartmut Klauck. 2011. On Arthur Merlin games in communication complexity. In Proceedings of 26th Annual IEEE Conference on Computational Complexity (CCC 2011). 189--199."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212771"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-010-0095-3"},{"key":"e_1_3_2_1_39_1","volume-title":"Quantum and randomized communication complexity of XOR functions in the SMP model. Electronic Colloquium on Computational Complexity (ECCC) TR13-010","author":"Liu Yang","year":"2013","unstructured":"Yang Liu and Shengyu Zhang. 2013. Quantum and randomized communication complexity of XOR functions in the SMP model. Electronic Colloquium on Computational Complexity (ECCC) TR13-010 (2013)."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3512751"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.gs.2016.007"},{"key":"e_1_3_2_1_42_1","volume-title":"Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA","author":"Naor Moni","year":"2020","unstructured":"Moni Naor, Merav Parter, and Eylon Yogev. 2020. The power of distributed verifiers in interactive proofs. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2020). 1096--1115."},{"key":"e_1_3_2_1_43_1","volume-title":"2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS","author":"Natarajan Anand","year":"2019","unstructured":"Anand Natarajan and John Wright. 2019. NEEXP is contained in MIP*. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS 2019). IEEE, 510--518."},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"crossref","unstructured":"David Peleg. 2000. Distributed computing: a locality-sensitive approach. SIAM.","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_3_2_1_45_1","volume-title":"Proceedings 19th Annual IEEE Conference on Computational Complexity (CCC 2004","author":"Raz Ran","year":"2004","unstructured":"Ran Raz and Amir Shpilka. 2004. On the power of quantum proofs. In Proceedings 19th Annual IEEE Conference on Computational Complexity (CCC 2004). 260--274. Full version is availabie from the following URL: https:\/\/www.cs.tau.ac.il\/~shpilka\/publications\/RazShpilka_QMA.pdf. Last visited on 2024\/01\/03."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/080733644"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2141938.2141939"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519270.3538413"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519270.3538441"},{"key":"e_1_3_2_1_50_1","volume-title":"Proceedings of the 34th annual ACM symposium on Theory of computing (STOC","author":"Chi-Chih Yao Andrew","year":"2003","unstructured":"Andrew Chi-Chih Yao. 2003. On the power of quantum fingerprinting. In Proceedings of the 34th annual ACM symposium on Theory of computing (STOC 2003). 77--81."},{"key":"e_1_3_2_1_51_1","volume-title":"International Colloquium on Automata, Languages, and Programming (ICALP","author":"Zhang Shengyu","year":"2011","unstructured":"Shengyu Zhang. 2011. On the power of lower bound methods for one-way quantum communication complexity. In International Colloquium on Automata, Languages, and Programming (ICALP 2011). 49--60."}],"event":{"name":"PODC '24: 43rd ACM Symposium on Principles of Distributed Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory","SIGOPS ACM Special Interest Group on Operating Systems"],"location":"Nantes France","acronym":"PODC '24"},"container-title":["Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3662158.3662788","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T23:43:41Z","timestamp":1750290221000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3662158.3662788"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,17]]},"references-count":50,"alternative-id":["10.1145\/3662158.3662788","10.1145\/3662158"],"URL":"https:\/\/doi.org\/10.1145\/3662158.3662788","relation":{},"subject":[],"published":{"date-parts":[[2024,6,17]]},"assertion":[{"value":"2024-06-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}