Document Open Access Logo

Space-Efficient Error Reduction for Unitary Quantum Computations

Authors Bill Fefferman, Hirotada Kobayashi, Cedric Yen-Yu Lin, Tomoyuki Morimae, Harumichi Nishimura

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.14.pdf
  • Filesize: 0.57 MB
  • 14 pages

Document Identifiers

Author Details

Bill Fefferman
Hirotada Kobayashi
Cedric Yen-Yu Lin
Tomoyuki Morimae
Harumichi Nishimura

Cite As Get BibTex

Bill Fefferman, Hirotada Kobayashi, Cedric Yen-Yu Lin, Tomoyuki Morimae, and Harumichi Nishimura. Space-Efficient Error Reduction for Unitary Quantum Computations. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.14

Abstract

This paper presents a general space-efficient method for error reduction for unitary quantum computation. Consider a polynomial-time quantum computation with completeness c and soundness s, either with or without a witness (corresponding to QMA and BQP, respectively). To convert this computation into a new computation with error at most 2^{-p}, the most space-efficient method known requires extra workspace of O(p*log(1/(c-s))) qubits. This space requirement is too large for scenarios like logarithmic-space quantum computations. This paper shows an errorreduction method for unitary quantum computations (i.e., computations without intermediate measurements) that requires extra workspace of just O(log(p/(c-s))) qubits. This in particular gives the first method of strong amplification for logarithmic-space unitary quantum computations with two-sided bounded error. This also leads to a number of consequences in complexity theory, such as the uselessness of quantum witnesses in bounded-error logarithmic-space unitary quantum computations, the PSPACE upper bound for QMA with exponentially-small completeness-soundness gap, and strong amplification for matchgate computations.

Subject Classification

Keywords
  • space-bounded computation
  • quantum Merlin-Arthur proof systems
  • error reduction
  • quantum computing

Metrics

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

References

  1. Andris Ambainis and Rūsiņš Freivalds. 1-way quantum finite automata: strengths, weaknesses and generalizations. In 39th Annual Symposium on Foundations of Computer Science, pages 332-341, 1998. URL: http://dx.doi.org/10.1109/SFCS.1998.743469.
  2. Charles H. Bennett. Time/space trade-offs for reversible computation. SIAM Journal on Computing, 18(4):766-776, 1989. URL: http://dx.doi.org/10.1137/0218053.
  3. Bill Fefferman, Hirotada Kobayashi, Cedric Yen-Yu Lin, Tomoyuki Morimae, and Harumichi Nishimura. Space-efficient error reduction for unitary quantum computations. arXiv.org e-Print archive, arXiv:1604.08192 [quant-ph], 2016. URL: http://arxiv.org/abs/1604.08192.
  4. Bill Fefferman and Cedric Lin. Quantum Merlin Arthur with exponentially small gap. arXiv.org e-Print archive, arXiv:1601.01975 [quant-ph], 2016. URL: http://arxiv.org/abs/1601.01975.
  5. Bill Fefferman and Cedric Yen-Yu Lin. A complete characterization of unitary quantum space. arXiv.org e-Print archive, arXiv:1604.01384 [quant-ph], 2016. URL: http://arxiv.org/abs/1604.01384.
  6. Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pages 212-219, 1996. URL: http://dx.doi.org/10.1145/237814.237866.
  7. Tsuyoshi Ito, Hirotada Kobayashi, and John Watrous. Quantum interactive proofs with weak error bounds. In ITCS'12, Proceedings of the 2012 ACM Conference on Innovations in Theoretical Computer Science, pages 266-275, 2012. URL: http://dx.doi.org/10.1145/2090236.2090259.
  8. Stephen P. Jordan, Hirotada Kobayashi, Daniel Nagaj, and Harumichi Nishimura. Achieving perfect completeness in classical-witness quantum Merlin-Arthur proof systems. Quantum Information and Computation, 12(5-6):0461-0471, 2012. Google Scholar
  9. Richard Jozsa, Barbara Kraus, Akimasa Miyake, and John Watrous. Matchgate and space-bounded quantum computations are equivalent. Proceedings of the Royal Society A, 466(2115):809-830, 2010. URL: http://dx.doi.org/10.1098/rspa.2009.0433.
  10. Alexei Kitaev and John Watrous. Parallelization, amplification, and exponential time simulation of quantum interactive proof systems. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, pages 608-617, 2000. URL: http://dx.doi.org/10.1145/335305.335387.
  11. Alexei \relaxYu. Kitaev, Alexander H. Shen, and Mikhail N. Vyalyi. Classical and Quantum Computation, volume 47 of Graduate Studies in Mathematics. American Mathematical Society, 2002. URL: http://dx.doi.org/10.1090/gsm/047.
  12. Hirotada Kobayashi, François Le Gall, and Harumichi Nishimura. Stronger methods of making quantum interactive proofs perfectly complete. SIAM Journal on Computing, 44(2):243-289, 2015. URL: http://dx.doi.org/10.1137/140971944.
  13. Chris Marriott and John Watrous. Quantum Arthur-Merlin games. Computational Complexity, 14(2):122-152, 2005. URL: http://dx.doi.org/10.1007/s00037-005-0194-x.
  14. Dieter van Melkebeek and Thomas Watson. Time-space efficient simulations of quantum computations. Theory of Computing, 8:1-51 (Article 1), 2012. URL: http://dx.doi.org/10.4086/toc.2012.v008a001.
  15. Daniel Nagaj, Pawel Wocjan, and Yong Zhang. Fast amplification of QMA. Quantum Information and Computation, 9(11-12):1053-1068, 2009. Google Scholar
  16. Anand Natarajan and Xiaodi Wu. Private communication, January 2016. Google Scholar
  17. Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000. Google Scholar
  18. Amnon Ta-Shma. Inverting well conditioned matrices in quantum logspace. In STOC'13, Proceedings of the 2013 ACM Symposium on Theory of Computing, pages 881-890, 2013. URL: http://dx.doi.org/10.1145/2488608.2488720.
  19. Barbara M. Terhal and David P. DiVincenzo. Classical simulation of noninteracting-fermion quantum circuits. Physical Review A, 65:article 032325, 2002. URL: http://dx.doi.org/10.1103/PhysRevA.65.032325.
  20. Leslie G. Valiant. Quantum circuits that can be simulated classically in polynomial time. SIAM Journal on Computing, 31(4):1229-1254, 2002. URL: http://dx.doi.org/10.1137/S0097539700377025.
  21. John Watrous. Space-bounded quantum complexity. Journal of Computer and System Sciences, 59(2):281-326, 1999. URL: http://dx.doi.org/10.1006/jcss.1999.1655.
  22. John Watrous. Quantum simulations of classical random walks and undirected graph connectivity. Journal of Computer and System Sciences, 62(2):376-391, 2001. URL: http://dx.doi.org/10.1006/jcss.2000.1732.
  23. John Watrous. On the complexity of simulating space-bounded quantum computations. Computational Complexity, 12(1-2):48-84, 2003. URL: http://dx.doi.org/10.1007/s00037-003-0177-8.
  24. John Watrous. Quantum computational complexity. In Robert A. Meyers, editor, Encyclopedia of Complexity and Systems Science, pages 7174-7201. Springer New York, 2009. URL: http://dx.doi.org/10.1007/978-0-387-30440-3_428.
  25. John Watrous. Zero-knowledge against quantum attacks. SIAM Journal on Computing, 39(1):25-58, 2009. URL: http://dx.doi.org/10.1137/060670997.
  26. Mark M. Wilde. Quantum Information Theory. Cambridge University Press, 2013. URL: http://dx.doi.org/10.1017/CBO9781139525343.
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