Document Open Access Logo

Distributed Quantum Proofs for Replicated Data

Authors Pierre Fraigniaud, François Le Gall, Harumichi Nishimura, Ami Paz

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2021.28.pdf
  • Filesize: 0.58 MB
  • 20 pages

Document Identifiers

Author Details

Pierre Fraigniaud
  • IRIF, CNRS and Université de Paris, France
François Le Gall
  • Graduate School of Mathematics, Nagoya University, Japan
Harumichi Nishimura
  • Graduate School of Informatics, Nagoya University, Japan
Ami Paz
  • Faculty of Computer Science, Universität Wien, Austria

Funding

  • Fraigniaud, Pierre: Additional support from the ANR projects DESCARTES and QuDATA.
  • Le Gall, François: JSPS KAKENHI grants Nos. JP16H01705, JP19H04066, JP20H04139 and JP20H00579 and MEXT Quantum Leap Flagship Program Grant Number JPMXS0120319794.
  • Nishimura, Harumichi: JSPS KAKENHI grants Nos. JP16H01705, JP19H04066 and MEXT Quantum Leap Flagship Program Grant Number JPMXS0120319794.
  • Paz, Ami: We acknowledge the Austrian Science Fund (FWF) and netIDEE SCIENCE project P 33775-N.

Acknowledgements

We thank the anonymous reviewer of ITCS 2021 who pointed [Bill Rosgen, 2008] to us, and Uri Meir for useful discussions.

Cite AsGet BibTex

Pierre Fraigniaud, François Le Gall, Harumichi Nishimura, and Ami Paz. Distributed Quantum Proofs for Replicated Data. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 28:1-28:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ITCS.2021.28

Abstract

This paper tackles the issue of checking that all copies of a large data set replicated at several nodes of a network are identical. The fact that the replicas may be located at distant nodes prevents the system from verifying their equality locally, i.e., by having each node consult only nodes in its vicinity. On the other hand, it remains possible to assign certificates to the nodes, so that verifying the consistency of the replicas can be achieved locally. However, we show that, as the replicated data is large, classical certification mechanisms, including distributed Merlin-Arthur protocols, cannot guarantee good completeness and soundness simultaneously, unless they use very large certificates. The main result of this paper is a distributed quantum Merlin-Arthur protocol enabling the nodes to collectively check the consistency of the replicas, based on small certificates, and in a single round of message exchange between neighbors, with short messages. In particular, the certificate-size is logarithmic in the size of the data set, which gives an exponential advantage over classical certification mechanisms. We propose yet another usage of a fundamental quantum primitive, called the SWAP test, in order to show our main result.

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum communication complexity
  • Theory of computation → Distributed computing models
Keywords
  • Quantum Computing
  • Distributed Network Computing
  • Algorithmic Aspects of Networks

Metrics

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

Related Versions

References

  1. Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, and Peter W. Shor. The power of unentanglement. Theory of Computing, 5:1:1-1:42, 2009. URL: https://doi.org/10.4086/toc.2009.v005a001.
  2. Yehuda Afek, Shay Kutten, and Moti Yung. The local detection paradigm and its application to self-stabilization. Theoretical Computer Science, 186(1-2):199-229, 1997. URL: https://doi.org/10.1016/S0304-3975(96)00286-1.
  3. Dorit Aharonov and Tomer Naveh. Quantum NP - a survey. arXiv:quant-ph/0210077v1, 2002. URL: http://arxiv.org/abs/quant-ph/0210077.
  4. Noga Alon, Klim Efremenko, and Benny Sudakov. Testing equality in communication graphs. IEEE Transactions on Information Theory, 63(11):7569-7574, 2017. URL: https://doi.org/10.1109/TIT.2017.2744608.
  5. Heger Arfaoui and Pierre Fraigniaud. What can be computed without communications? SIGACT News, 45(3):82-104, 2014. URL: https://doi.org/10.1145/2670418.2670440.
  6. Baruch Awerbuch, Boaz Patt-Shamir, and George Varghese. Self-stabilization by local checking and correction (extended abstract). In 32nd Symposium on Foundations of Computer Science (FOCS), pages 268-277, 1991. URL: https://doi.org/10.1109/SFCS.1991.185378.
  7. Alkida Balliu, Gianlorenzo D'Angelo, Pierre Fraigniaud, and Dennis Olivetti. What can be verified locally? Journal of Computer System and Sciences, 97:106-120, 2018. URL: https://doi.org/10.1016/j.jcss.2018.05.004.
  8. Michael Ben-Or and Avinatan Hassidim. Fast quantum byzantine agreement. In 37th Annual ACM Symposium on Theory of Computing (STOC), pages 481-485, 2005. URL: https://doi.org/10.1145/1060590.1060662.
  9. Hugue Blier and Alain Tapp. A quantum characterization of NP. Computational Complexity, 21(3):499-510, 2012. URL: https://doi.org/10.1007/s00037-011-0016-2.
  10. Ralph Bottesch, Dmitry Gavinsky, and Hartmut Klauck. Equality, revisited. In 40th International Symposium on Mathematical Foundations of Computer Science (MFCS), volume 9235 of LNCS, pages 127-138. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-48054-0_11.
  11. Anne Broadbent and Alain Tapp. Can quantum mechanics help distributed computing? SIGACT News, 39(3):67-76, 2008. URL: https://doi.org/10.1145/1412700.1412717.
  12. Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf. Quantum fingerprinting. Physical Review Letters, 87(16):167902:1-167902:4, 2001. URL: https://doi.org/10.1103/PhysRevLett.87.167902.
  13. Arkadev Chattopadhyay, Jaikumar Radhakrishnan, and Atri Rudra. Topology matters in communication. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 631-640, 2014. URL: https://doi.org/10.1109/FOCS.2014.73.
  14. Arkadev Chattopadhyay and Atri Rudra. The range of topological effects on communication. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP, pages 540-551, 2015. URL: https://doi.org/10.1007/978-3-662-47666-6_43.
  15. Pierluigi Crescenzi, Pierre Fraigniaud, and Ami Paz. Trade-offs in distributed interactive proofs. In 33rd International Symposium on Distributed Computing (DISC), pages 13:1-13:17, 2019. URL: https://doi.org/10.4230/LIPIcs.DISC.2019.13.
  16. Vasil S. Denchev and Gopal Pandurangan. Distributed quantum computing: a new frontier in distributed systems or science fiction? SIGACT News, 39(3):77-95, 2008. URL: https://doi.org/10.1145/1412700.1412718.
  17. Michael Elkin, Hartmut Klauck, Danupon Nanongkai, and Gopal Pandurangan. Can quantum communication speed up distributed computation? In 33rd ACM Symposium on Principles of Distributed Computing (PODC), pages 166-175, 2014. URL: https://doi.org/10.1145/2611462.2611488.
  18. Laurent Feuilloley, Pierre Fraigniaud, and Juho Hirvonen. A hierarchy of local decision. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP), pages 118:1-118:15, 2016. URL: https://doi.org/10.4230/LIPIcs.ICALP.2016.118.
  19. Laurent Feuilloley, Pierre Fraigniaud, Juho Hirvonen, Ami Paz, and Mor Perry. Redundancy in distributed proofs. In 32nd International Symposium on Distributed Computing, DISC, pages 24:1-24:18, 2018. URL: https://doi.org/10.4230/LIPIcs.DISC.2018.24.
  20. Pierre Fraigniaud, Amos Korman, and David Peleg. Towards a complexity theory for local distributed computing. Journal of the ACM, 60(5):35:1-35:26, 2013. URL: https://doi.org/10.1145/2499228.
  21. Pierre Fraigniaud, Pedro Montealegre, Rotem Oshman, Ivan Rapaport, and Ioan Todinca. On distributed Merlin-Arthur decision protocols. In 26th International Colloquium on Structural Information and Communication Complexity (SIROCCO), volume 11639 of LNCS, pages 230-245. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-24922-9_16.
  22. Pierre Fraigniaud, Boaz Patt-Shamir, and Mor Perry. Randomized proof-labeling schemes. Distributed Computing, 32(3):217-234, 2019. URL: https://doi.org/10.1007/s00446-018-0340-8.
  23. Cyril Gavoille, Adrian Kosowski, and Marcin Markiewicz. What can be observed locally? In 23rd International Symposium on Distributed Computing (DISC), volume 5805 of LNCS, pages 243-257. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-04355-0_26.
  24. Mika Göös and Jukka Suomela. Locally checkable proofs in distributed computing. Theory of Computing, 12:19:1-19:33, 2016. URL: https://doi.org/10.4086/toc.2016.v012a019.
  25. Aram W. Harrow and Ashley Montanaro. Testing product states, quantum Merlin-Arthur games and tensor optimization. Journal of the ACM, 60(1):3:1-3:43, 2013. URL: https://doi.org/10.1145/2432622.2432625.
  26. Gene Itkis and Leonid A. Levin. Fast and lean self-stabilizing asynchronous protocols. In 35th Annual Symposium on Foundations of Computer Science (FOCS), pages 226-239, 1994. URL: https://doi.org/10.1109/SFCS.1994.365691.
  27. Taisuke Izumi and François Le Gall. Quantum distributed algorithm for the All-Pairs Shortest Path problem in the CONGEST-CLIQUE model. In 38th ACM Symposium on Principles of Distributed Computing (PODC), pages 84-93, 2019. URL: https://doi.org/10.1145/3293611.3331628.
  28. Taisuke Izumi, François Le Gall, and Frédéric Magniez. Quantum distributed algorithm for triangle finding in the CONGEST model. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS), pages 23:1-23:13, 2020. URL: https://doi.org/10.4230/LIPIcs.STACS.2020.23.
  29. Alexei Yu. Kitaev, Alexander H. Shen, and Mikhail N. Vyalyi. Classical and Quantum Computation. Graduate Studies in Mathematics 47. American Mathematical Society, 2002. Google Scholar
  30. Hartmut Klauck. On Arthur Merlin games in communication complexity. In 26th Annual IEEE Conference on Computational Complexity (CCC), pages 189-199, 2011. URL: https://doi.org/10.1109/CCC.2011.33.
  31. Hartmut Klauck and Supartha Podder. Two results about quantum messages. In 39th International Symposium on Mathematical Foundations of Computer Science (MFCS), volume 8635 of LNCS, pages 445-456. Springer, 2014. URL: https://doi.org/10.1007/978-3-662-44465-8_38.
  32. Hirotada Kobayashi, François Le Gall, and Harumichi Nishimura. Stronger methods of making quantum interactive proofs perfectly complete. SIAM Journal on Computing, 44(2):243-289, 2015. URL: https://doi.org/10.1137/140971944.
  33. Hirotada Kobayashi, Keiji Matsumoto, and Tomoyuki Yamakami. Quantum Merlin-Arthur proof systems: Are multiple Merlins more helpful to Arthur? Chicago Journal of Theoretical Computer Science, 2009:3:1-3:19, 2009. URL: https://doi.org/10.4086/cjtcs.2009.003.
  34. Gillat Kol, Rotem Oshman, and Raghuvansh R. Saxena. Interactive distributed proofs. In 37th ACM Symposium on Principles of Distributed Computing (PODC), pages 255-264, 2018. URL: https://doi.org/10.1145/3212734.3212771.
  35. Amos Korman, Shay Kutten, and David Peleg. Proof labeling schemes. Distributed Computing, 22(4):215-233, 2010. URL: https://doi.org/10.1007/s00446-010-0095-3.
  36. Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, 1997. Google Scholar
  37. François Le Gall and Frédéric Magniez. Sublinear-time quantum computation of the diameter in CONGEST networks. In 37th ACM Symposium on Principles of Distributed Computing (PODC), pages 337-346, 2018. URL: https://doi.org/10.1145/3212734.3212744.
  38. François Le Gall, Harumichi Nishimura, and Ansis Rosmanis. Quantum advantage for the LOCAL model in distributed computing. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS), pages 49:1-49:14, 2019. URL: https://doi.org/10.4230/LIPIcs.STACS.2019.49.
  39. Moni Naor, Merav Parter, and Eylon Yogev. The power of distributed verifiers in interactive proofs. In 31st ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1096-115, 2020. URL: https://doi.org/10.1137/1.9781611975994.67.
  40. Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000. Google Scholar
  41. Rafail Ostrovsky, Mor Perry, and Will Rosenbaum. Space-time tradeoffs for distributed verification. In Structural Information and Communication Complexity - 24th International Colloquium, SIROCCO, pages 53-70, 2017. URL: https://doi.org/10.1007/978-3-319-72050-0_4.
  42. David Peleg. Distributed Computing: A Locality-Sensitive Approach. SIAM, 2000. Google Scholar
  43. Ran Raz and Amir Shpilka. On the power of quantum proofs. In 19th IEEE Conference on Computational Complexity (CCC), pages 260-274, 2004. URL: https://doi.org/10.1109/CCC.2004.1313849.
  44. Bill Rosgen. Distinguishing short quantum computations. In 25th International Symposium on Theoretical Aspects of Computer Science (STACS), pages 597-608, 2008. URL: https://doi.org/10.4230/LIPIcs.STACS.2008.1322.
  45. Seiichiro Tani, Hirotada Kobayashi, and Keiji Matsumoto. Exact quantum algorithms for the leader election problem. ACM Transactions on Computation Theory, 4(1):1:1-1:24, 2012. URL: https://doi.org/10.1145/2141938.2141939.
  46. Andrew Chi-Chih Yao. Quantum circuit complexity. In 34th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 352-361, 1993. URL: https://doi.org/10.1109/SFCS.1993.366852.
  47. Andrew Chi-Chih Yao. On the power of quantum fingerprinting. In 35th ACM Symposium on Theory of Computing (STOC), pages 77-81, 2003. URL: https://doi.org/10.1145/780542.780554.
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