License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.TQC.2023.9
URN: urn:nbn:de:0030-drops-183193
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18319/
Go to the corresponding LIPIcs Volume Portal

Hiromasa, Ryo ; Mizutani, Akihiro ; Takeuchi, Yuki ; Tani, Seiichiro

Rewindable Quantum Computation and Its Equivalence to Cloning and Adaptive Postselection

pdf-format:
LIPIcs-TQC-2023-9.pdf (0.9 MB)

Abstract

We define rewinding operators that invert quantum measurements. Then, we define complexity classes RwBQP, CBQP, and AdPostBQP as sets of decision problems solvable by polynomial-size quantum circuits with a polynomial number of rewinding operators, cloning operators, and adaptive postselections, respectively. Our main result is that BPP^PP ⊆ RwBQP = CBQP = AdPostBQP ⊆ PSPACE. As a byproduct of this result, we show that any problem in PostBQP can be solved with only postselections of outputs whose probabilities are polynomially close to one. Under the strongly believed assumption that BQP ⊉ SZK, or the shortest independent vectors problem cannot be efficiently solved with quantum computers, we also show that a single rewinding operator is sufficient to achieve tasks that are intractable for quantum computation. In addition, we consider rewindable Clifford and instantaneous quantum polynomial time circuits.

BibTeX - Entry

@InProceedings{hiromasa_et_al:LIPIcs.TQC.2023.9,
  author =	{Hiromasa, Ryo and Mizutani, Akihiro and Takeuchi, Yuki and Tani, Seiichiro},
  title =	{{Rewindable Quantum Computation and Its Equivalence to Cloning and Adaptive Postselection}},
  booktitle =	{18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)},
  pages =	{9:1--9:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-283-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{266},
  editor =	{Fawzi, Omar and Walter, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18319},
  URN =		{urn:nbn:de:0030-drops-183193},
  doi =		{10.4230/LIPIcs.TQC.2023.9},
  annote =	{Keywords: Quantum computing, Postselection, Lattice problems}
}

Keywords: Quantum computing, Postselection, Lattice problems
Collection: 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)
Issue Date: 2023
Date of publication: 18.07.2023

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