2 Search Results for "Rosgen, Bill"

Document
DOI: 10.4230/LIPIcs.ITCS.2021.28
Distributed Quantum Proofs for Replicated Data

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

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{fraigniaud_et_al:LIPIcs.ITCS.2021.28,
  author =	{Fraigniaud, Pierre and Le Gall, Fran\c{c}ois and Nishimura, Harumichi and Paz, Ami},
  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 =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.28},
  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}
}
Document
DOI: 10.4230/LIPIcs.STACS.2008.1322
Distinguishing Short Quantum Computations

Authors: Bill Rosgen

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

Abstract
Distinguishing logarithmic depth quantum circuits on mixed states is shown to be complete for $QIP$, the class of problems having quantum interactive proof systems. Circuits in this model can represent arbitrary quantum processes, and thus this result has implications for the verification of implementations of quantum algorithms. The distinguishability problem is also complete for $QIP$ on constant depth circuits containing the unbounded fan-out gate. These results are shown by reducing a $QIP$-complete problem to a logarithmic depth version of itself using a parallelization technique.
Cite as

Bill Rosgen. Distinguishing Short Quantum Computations. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 597-608, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{rosgen:LIPIcs.STACS.2008.1322,
  author =	{Rosgen, Bill},
  title =	{{Distinguishing Short Quantum Computations}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{597--608},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1322},
  URN =		{urn:nbn:de:0030-drops-13222},
  doi =		{10.4230/LIPIcs.STACS.2008.1322},
  annote =	{Keywords: Quantum information, computational complexity, quantum circuits, quantum interactive proof systems}
}
  • Refine by Author
  • 1 Fraigniaud, Pierre
  • 1 Le Gall, François
  • 1 Nishimura, Harumichi
  • 1 Paz, Ami
  • 1 Rosgen, Bill

  • Refine by Classification
  • 1 Theory of computation → Distributed computing models
  • 1 Theory of computation → Quantum communication complexity

  • Refine by Keyword
  • 1 Algorithmic Aspects of Networks
  • 1 Distributed Network Computing
  • 1 Quantum Computing
  • 1 Quantum information
  • 1 computational complexity
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2008
  • 1 2021

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