1 Search Results for "Yakaryılmaz, Abuzer"

Document
DOI: 10.4230/LIPIcs.TQC.2021.10
Quantum Logarithmic Space and Post-Selection

Authors: François Le Gall, Harumichi Nishimura, and Abuzer Yakaryılmaz

Published in: LIPIcs, Volume 197, 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)

Abstract
Post-selection, the power of discarding all runs of a computation in which an undesirable event occurs, is an influential concept introduced to the field of quantum complexity theory by Aaronson (Proceedings of the Royal Society A, 2005). In the present paper, we initiate the study of post-selection for space-bounded quantum complexity classes. Our main result shows the identity PostBQL = PL, i.e., the class of problems that can be solved by a bounded-error (polynomial-time) logarithmic-space quantum algorithm with post-selection (PostBQL) is equal to the class of problems that can be solved by unbounded-error logarithmic-space classical algorithms (PL). This result gives a space-bounded version of the well-known result PostBQP = PP proved by Aaronson for polynomial-time quantum computation. As a by-product, we also show that PL coincides with the class of problems that can be solved by bounded-error logarithmic-space quantum algorithms that have no time bound.
Cite as

François Le Gall, Harumichi Nishimura, and Abuzer Yakaryılmaz. Quantum Logarithmic Space and Post-Selection. In 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 197, pp. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{legall_et_al:LIPIcs.TQC.2021.10,
  author =	{Le Gall, Fran\c{c}ois and Nishimura, Harumichi and Yakary{\i}lmaz, Abuzer},
  title =	{{Quantum Logarithmic Space and Post-Selection}},
  booktitle =	{16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)},
  pages =	{10:1--10:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-198-6},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{197},
  editor =	{Hsieh, Min-Hsiu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2021.10},
  URN =		{urn:nbn:de:0030-drops-140054},
  doi =		{10.4230/LIPIcs.TQC.2021.10},
  annote =	{Keywords: computational complexity, space-bounded quantum computation, post-selection}
}
  • Refine by Author
  • 1 Le Gall, François
  • 1 Nishimura, Harumichi
  • 1 Yakaryılmaz, Abuzer

  • Refine by Classification
  • 1 Theory of computation → Quantum computation theory

  • Refine by Keyword
  • 1 computational complexity
  • 1 post-selection
  • 1 space-bounded quantum computation

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 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