Document Open Access Logo

Distributed Quantum Interactive Proofs

Authors François Le Gall, Masayuki Miyamoto, Harumichi Nishimura

PDF
Thumbnail PDF

File

LIPIcs.STACS.2023.42.pdf
  • Filesize: 0.84 MB
  • 21 pages

Document Identifiers

Author Details

François Le Gall
  • Graduate School of Mathematics, Nagoya University, Japan
Masayuki Miyamoto
  • Graduate School of Mathematics, Nagoya University, Japan
Harumichi Nishimura
  • Graduate School of Informatics, Nagoya University, Japan

Funding

FLG was supported by the JSPS KAKENHI grants JP16H01705, JP19H04066, JP20H00579, JP20H04139, JP20H05966, JP21H04879 and by the MEXT Q-LEAP grants JPMXS0118067394 and JPMXS0120319794. MM would like to take this opportunity to thank the “Nagoya University Interdisciplinary Frontier Fellowship” supported by Nagoya University and JST, the establishment of university fellowships towards the creation of science technology innovation, Grant Number JPMJFS212. HN was supported by the JSPS KAKENHI grants JP19H04066, JP20H05966, JP21H04879, JP22H00522 and by the MEXT Q-LEAP grants JPMXS0120319794.

Cite AsGet BibTex

François Le Gall, Masayuki Miyamoto, and Harumichi Nishimura. Distributed Quantum Interactive Proofs. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 42:1-42:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.STACS.2023.42

Abstract

The study of distributed interactive proofs was initiated by Kol, Oshman, and Saxena [PODC 2018] as a generalization of distributed decision mechanisms (proof-labeling schemes, etc.), and has received a lot of attention in recent years. In distributed interactive proofs, the nodes of an n-node network G can exchange short messages (called certificates) with a powerful prover. The goal is to decide if the input (including G itself) belongs to some language, with as few turns of interaction and as few bits exchanged between nodes and the prover as possible. There are several results showing that the size of certificates can be reduced drastically with a constant number of interactions compared to non-interactive distributed proofs. In this paper, we introduce the quantum counterpart of distributed interactive proofs: certificates can now be quantum bits, and the nodes of the network can perform quantum computation. The first result of this paper shows that by using distributed quantum interactive proofs, the number of interactions can be significantly reduced. More precisely, our result shows that for any constant k, the class of languages that can be decided by a k-turn classical (i.e., non-quantum) distributed interactive protocol with f(n)-bit certificate size is contained in the class of languages that can be decided by a 5-turn distributed quantum interactive protocol with O(f(n))-bit certificate size. We also show that if we allow to use shared randomness, the number of turns can be reduced to three. Since no similar turn-reduction classical technique is currently known, our result gives evidence of the power of quantum computation in the setting of distributed interactive proofs as well. As a corollary of our results, we show that there exist 5-turn/3-turn distributed quantum interactive protocols with small certificate size for problems that have been considered in prior works on distributed interactive proofs such as [Kol, Oshman, and Saxena PODC 2018, Naor, Parter, and Yogev SODA 2020]. We then utilize the framework of the distributed quantum interactive proofs to test closeness of two quantum states each of which is distributed over the entire network.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
  • Theory of computation → Quantum computation theory
Keywords
  • distributed interactive proofs
  • distributed verification
  • quantum computation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Harry Buhrman, Richard Cleve, John Watrous, and Ronald De Wolf. Quantum fingerprinting. Physical Review Letters, 87(16):167902, 2001. Google Scholar
  2. Keren Censor-Hillel, Orr Fischer, François Le Gall, Dean Leitersdorf, and Rotem Oshman. Quantum Distributed Algorithms for Detection of Cliques. In Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), pages 35:1-35:25, 2022. Google Scholar
  3. Pierluigi Crescenzi, Pierre Fraigniaud, and Ami Paz. Trade-Offs in Distributed Interactive Proofs. In Proceedings of the 33rd International Symposium on Distributed Computing (DISC 2019), pages 13:1-13:17, 2019. Google Scholar
  4. Pierre Fraigniaud, François Le Gall, Harumichi Nishimura, and Ami Paz. Distributed Quantum Proofs for Replicated Data. In Proceedings of the 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), pages 28:1-28:20, 2021. Google Scholar
  5. Pierre Fraigniaud, Amos Korman, and David Peleg. Local distributed decision. In Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS 2011), pages 708-717, 2011. Google Scholar
  6. Pierre Fraigniaud, Pedro Montealegre, Rotem Oshman, Ivan Rapaport, and Ioan Todinca. On distributed Merlin-Arthur decision protocols. In Proceedings of the International Colloquium on Structural Information and Communication Complexity (SIROCCO 2019), pages 230-245, 2019. Google Scholar
  7. Christopher A Fuchs and Jeroen Van De Graaf. Cryptographic distinguishability measures for quantum-mechanical states. IEEE Transactions on Information Theory, 45(4):1216-1227, 1999. Google Scholar
  8. François Le Gall, Masayuki Miyamoto, and Harumichi Nishimura. Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications, 2022. URL: http://arxiv.org/abs/2210.01389.
  9. François Le Gall, Masayuki Miyamoto, and Harumichi Nishimura. Distributed Quantum Interactive Proofs, 2022. URL: http://arxiv.org/abs/2210.01390.
  10. Mika Göös and Jukka Suomela. Locally checkable proofs in distributed computing. Theory of Computing, 12(1):1-33, 2016. Google Scholar
  11. Gus Gutoski. Quantum strategies and local operations. arXiv preprint, 2010. URL: http://arxiv.org/abs/1003.0038.
  12. Taisuke Izumi, François Le Gall, and Frédéric Magniez. Quantum Distributed Algorithm for Triangle Finding in the CONGEST Model. In Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), pages 23:1-23:13, 2020. Google Scholar
  13. Taisuke Izumi and François Le Gall. Quantum distributed algorithm for the all-pairs shortest path problem in the congest-clique model. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC 2019), pages 84-93, 2019. Google Scholar
  14. Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, and John Watrous. QIP= PSPACE. Journal of the ACM, 58(6):1-27, 2011. Google Scholar
  15. Benjamin Jauregui, Pedro Montealegre, and Ivan Rapaport. Distributed interactive proofs for the recognition of some geometric intersection graph classes. In Proceedings of 29th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2022), pages 212-233, 2022. Google Scholar
  16. Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, and Thomas Vidick. Using entanglement in quantum multi-prover interactive proofs. Computational Complexity, 18(2):273-307, 2009. Google Scholar
  17. Alexei Kitaev and John Watrous. Parallelization, amplification, and exponential time simulation of quantum interactive proof systems. In Proceedings of the thirty-second annual ACM symposium on Theory of computing (STOC 2000), pages 608-617, 2000. Google Scholar
  18. Gillat Kol, Rotem Oshman, and Raghuvansh R Saxena. Interactive distributed proofs. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (PODC 2018), pages 255-264, 2018. Google Scholar
  19. Amos Korman, Shay Kutten, and David Peleg. Proof labeling schemes. Distributed Computing, 22(4):215-233, 2010. Google Scholar
  20. François Le Gall and Frédéric Magniez. Sublinear-time quantum computation of the diameter in congest networks. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (PODC 2018), pages 337-346, 2018. Google Scholar
  21. François Le Gall, Harumichi Nishimura, and Ansis Rosmanis. Quantum Advantage for the LOCAL Model in Distributed Computing. In Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), pages 49:1-49:14, 2019. Google Scholar
  22. Chris Marriott and John Watrous. Quantum Arthur-Merlin games. Computational Complexity, 14(2):122-152, 2005. Google Scholar
  23. Pedro Montealegre, Diego Ramírez-Romero, and Ivan Rapaport. Shared vs Private Randomness in Distributed Interactive Proofs. In Proceedings of the 31st International Symposium on Algorithms and Computation (ISAAC 2020), pages 51:1-51:13, 2020. Google Scholar
  24. Pedro Montealegre, Diego Ramírez-Romero, and Ivan Rapaport. Compact distributed interactive proofs for the recognition of cographs and distance-hereditary graphs. In Proceedings of the International Symposium on Stabilizing, Safety, and Security of Distributed Systems (SSS 2021), pages 395-409, 2021. Google Scholar
  25. Moni Naor, Merav Parter, and Eylon Yogev. The power of distributed verifiers in interactive proofs. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2020), pages 1096-115, 2020. Google Scholar
  26. Ashwin Nayak and Peter Shor. Bit-commitment-based quantum coin flipping. Physical Review A, 67(1):012304, 2003. Google Scholar
  27. Michael A Nielsen and Isaac Chuang. Quantum computation and quantum information, 2002. Google Scholar
  28. Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000. Google Scholar
  29. Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, and Roger Wattenhofer. Distributed verification and hardness of distributed approximation. SIAM Journal on Computing, 41(5):1235-1265, 2012. Google Scholar
  30. Robert W Spekkens and Terry Rudolph. Degrees of concealment and bindingness in quantum bit commitment protocols. Physical Review A, 65(1):012310, 2001. Google Scholar
  31. John Watrous. PSPACE has constant-round quantum interactive proof systems. Theoretical Computer Science, 292(3):575-588, 2003. Google Scholar
  32. John Watrous. The Theory of Quantum Information. Cambridge University Press, 2018. Google Scholar
  33. Mark M. Wilde. Quantum Information Theory. Cambridge University Press, 2017. Google Scholar
  34. Huangjun Zhu and Masahito Hayashi. Efficient verification of hypergraph states. Physical Review Applied, 12(5):054047, 2019. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact