Document Open Access Logo

Quantum Logarithmic Space and Post-Selection

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

PDF
Thumbnail PDF

File

LIPIcs.TQC.2021.10.pdf
  • Filesize: 0.71 MB
  • 17 pages

Document Identifiers

Author Details

François Le Gall
  • Graduate School of Mathematics, Nagoya University, Japan
Harumichi Nishimura
  • Graduate School of Informatics, Nagoya University, Japan
Abuzer Yakaryılmaz
  • Center for Quantum Computer Science, University of Latvia, Rīga, Latvia
  • QWorld Association, Tallinn, Estonia

Funding

  • Le Gall, François: Supported by JSPS KAKENHI grants Nos. JP19H04066, JP20H05966, JP20H00579, JP20H04139, JP21H04879 and by the MEXT Quantum Leap Flagship Program (MEXT Q-LEAP) grants No. JPMXS0118067394 and JPMXS0120319794.
  • Nishimura, Harumichi: Supported by JSPS KAKENHI grants Nos. JP19H04066, JP20H05966, JP21H04879 and by the MEXT Q-LEAP grants No. JPMXS0120319794.
  • Yakaryılmaz, Abuzer: Supported by ERC Advanced Grant MQC and ERDF project Nr. 1.1.1.5/19/A/005 "Quantum computers with constant memory".

Acknowledgements

We thank the anonymous reviewers of TQC 2021 for helpful comments.

Cite As Get BibTex

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) https://doi.org/10.4230/LIPIcs.TQC.2021.10

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum computation theory
Keywords
  • computational complexity
  • space-bounded quantum computation
  • post-selection

Metrics

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

Related Versions

References

  1. Scott Aaronson. Quantum computing, postselection, and probabilistic polynomial-time. Proceedings of the Royal Society A, 461(2063):3473-3482, 2005. Google Scholar
  2. Eric Allender and Mitsunori Ogihara. Relationships among PL, #L, and the determinant. RAIRO Theoretical Informatics and Applications, 30(1):1-21, 1996. Google Scholar
  3. Ethan Bernstein and Umesh Vazirani. Quantum complexity theory. SIAM Journal on Computing, 26(5):1411-1473, 1997. Google Scholar
  4. David Deutsch. Quantum theory, the Church-Turing principle and the universal quantum computer. Proceedings of the Royal Society of London A, 400:97-117, 1985. Google Scholar
  5. Bill Fefferman, Hirotada Kobayashi, Cedric Yen-Yu Lin, Tomoyuki Morimae, and Harumichi Nishimura. Space-efficient error reduction for unitary quantum computations. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, volume 55 of LIPIcs, pages 14:1-14:14, 2016. Google Scholar
  6. Bill Fefferman and Cedric Yen-Yu Lin. A complete characterization of unitary quantum space. In Proceedings of the 9th Innovations in Theoretical Computer Science Conference, volume 94 of LIPIcs, pages 4:1-4:21, 2018. Google Scholar
  7. Bill Fefferman and Zachary Remscrim. Eliminating intermediate measurements in space-bounded quantum computation. In Proceedings of the 53rd Annual ACM Symposium on Theory of Computing, to appear, 2021. Also available at arXiv:2006.03530. Google Scholar
  8. Uma Girish, Ran Raz, and Wei Zhan. Quantum logspace algorithm for powering matrices with bounded nom. In Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, to appear, 2021. Also available at arXiv:2006.04880. Google Scholar
  9. Neil Immerman. Nondeterministic space is closed under complementation. SIAM Journal on Computing, 17(5):935-938, 1988. Google Scholar
  10. Hermann Jung. On probabilistic time and space. In Automata, Languages and Programming, volume 194 of LNCS, pages 310-317. Springer, 1985. Google Scholar
  11. Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000. Google Scholar
  12. A. C. Cem Say and Abuzer Yakaryılmaz. Computation with narrow CTCs. In Unconventional Computation, volume 6714 of LNCS, pages 201-211. Springer, 2011. Google Scholar
  13. A. C. Cem Say and Abuzer Yakaryılmaz. Quantum finite automata: A modern introduction. In Computing with New Resources, volume 8808 of LNCS, pages 208-222. Springer, 2014. Google Scholar
  14. Amnon Ta-Shma. Inverting well conditioned matrices in quantum logspace. In 44th ACM Annual Symposium on Theory of Computing, pages 881-890. ACM, 2013. Google Scholar
  15. Dieter van Melkebeek and Thomas Watson. Time-space efficient simulations of quantum computations. Theory of Computing, 8(1):1-51, 2012. Google Scholar
  16. John Watrous. Space-bounded quantum complexity. Journal of Computer and System Sciences, 59(2):281-326, 1999. Google Scholar
  17. John Watrous. On the complexity of simulating space-bounded quantum computations. Computational Complexity, 12(1-2):48-84, 2003. Google Scholar
  18. John Watrous. Quantum computational complexity. In Encyclopedia of Complexity and System Science. Springer, 2009. Also available at arXiv:0804.3401. Google Scholar
  19. Abuzer Yakaryılmaz and A. C. C. Say. Succinctness of two-way probabilistic and quantum finite automata. Discrete Mathematics and Theoretical Computer Science, 12(2):19-40, 2010. Google Scholar
  20. Abuzer Yakaryılmaz and A. C. Cem Say. Unbounded-error quantum computation with small space bounds. Information and Computation, 279(6):873-892, 2011. Google Scholar
  21. Abuzer Yakaryılmaz and A. C. Cem Say. Proving the power of postselection. Fundamenta Informaticae, 123(1):107-134, 2013. Google Scholar
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 About DROPS Imprint Privacy Contact