License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2021.28
URN: urn:nbn:de:0030-drops-135679
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13567/
Go to the corresponding LIPIcs Volume Portal

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

Distributed Quantum Proofs for Replicated Data

pdf-format:
LIPIcs-ITCS-2021-28.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{fraigniaud_et_al:LIPIcs.ITCS.2021.28,
  author =	{Pierre Fraigniaud and Fran\c{c}ois Le Gall and Harumichi Nishimura and Ami Paz},
  title =	{{Distributed Quantum Proofs for Replicated Data}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{28:1--28:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{James R. Lee},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/13567},
  URN =		{urn:nbn:de:0030-drops-135679},
  doi =		{10.4230/LIPIcs.ITCS.2021.28},
  annote =	{Keywords: Quantum Computing, Distributed Network Computing, Algorithmic Aspects of Networks}
}

Keywords: Quantum Computing, Distributed Network Computing, Algorithmic Aspects of Networks
Collection: 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Issue Date: 2021
Date of publication: 04.02.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI