Document Open Access Logo

Quantum Logspace Algorithm for Powering Matrices with Bounded Norm

Authors Uma Girish, Ran Raz, Wei Zhan

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.73.pdf
  • Filesize: 0.77 MB
  • 20 pages

Document Identifiers

Author Details

Uma Girish
  • Department of Computer Science, Princeton University, NJ, USA
Ran Raz
  • Department of Computer Science, Princeton University, NJ, USA
Wei Zhan
  • Department of Computer Science, Princeton University, NJ, USA

Funding

Research supported by the Simons Collaboration on Algorithms and Geometry, by a Simons Investigator Award and by the National Science Foundation grant No. CCF-1714779.

Acknowledgements

We would like to thank Dieter van Melkebeek and Subhayan Roy Moulik for very helpful suggestions and comments on a previous version of this work. We also thank the anonymous reviewers for their thorough feedback.

Cite AsGet BibTex

Uma Girish, Ran Raz, and Wei Zhan. Quantum Logspace Algorithm for Powering Matrices with Bounded Norm. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 73:1-73:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ICALP.2021.73

Abstract

We give a quantum logspace algorithm for powering contraction matrices, that is, matrices with spectral norm at most 1. The algorithm gets as an input an arbitrary n× n contraction matrix A, and a parameter T ≤ poly(n) and outputs the entries of A^T, up to (arbitrary) polynomially small additive error. The algorithm applies only unitary operators, without intermediate measurements. We show various implications and applications of this result: First, we use this algorithm to show that the class of quantum logspace algorithms with only quantum memory and with intermediate measurements is equivalent to the class of quantum logspace algorithms with only quantum memory without intermediate measurements. This shows that the deferred-measurement principle, a fundamental principle of quantum computing, applies also for quantum logspace algorithms (without classical memory). More generally, we give a quantum algorithm with space O(S + log T) that takes as an input the description of a quantum algorithm with quantum space S and time T, with intermediate measurements (without classical memory), and simulates it unitarily with polynomially small error, without intermediate measurements. Since unitary transformations are reversible (while measurements are irreversible) an interesting aspect of this result is that it shows that any quantum logspace algorithm (without classical memory) can be simulated by a reversible quantum logspace algorithm. This proves a quantum analogue of the result of Lange, McKenzie and Tapp that deterministic logspace is equal to reversible logspace [Lange et al., 2000]. Finally, we use our results to show non-trivial classical simulations of quantum logspace learning algorithms.

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum complexity theory
Keywords
  • BQL
  • Matrix Powering
  • Quantum Circuit
  • Reversible Computation

Metrics

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

Related Versions

References

  1. Paul Beame, Shayan Oveis Gharan, and Xin Yang. Time-space tradeoffs for learning finite functions from random evaluations, with applications to polynomials. In Conference On Learning Theory (COLT 2018), pages 843-856, 2018. Google Scholar
  2. Charles Bennett. Notes on landauer’s principle, reversible computation, and maxwell’s demon. Studies In History and Philosophy of Science Part B: Studies In History and Philosophy of Modern Physics, 34:501-510, September 2003. URL: https://doi.org/10.1016/S1355-2198(03)00039-X.
  3. Jin-Yi Cai, Venkatesan T Chakaravarthy, and Dieter van Melkebeek. Time-space tradeoff in derandomizing probabilistic logspace. Theory of Computing Systems, 39(1):189-208, 2006. Google Scholar
  4. Shantanav Chakraborty, András Gilyén, and Stacey Jeffery. The power of block-encoded matrix powers: Improved regression techniques via faster hamiltonian simulation. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. 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 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), volume 55. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.ICALP.2016.14.
  6. Bill Fefferman and Cedric Yen-Yu Lin. A complete characterization of unitary quantum space. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  7. Bill Fefferman and Zachary Remscrim. Eliminating intermediate measurements in space-bounded quantum computation, 2020. URL: http://arxiv.org/abs/2006.03530.
  8. Sumegha Garg, Ran Raz, and Avishay Tal. Extractor-based time-space lower bounds for learning. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018), pages 990-1002, 2018. Google Scholar
  9. András Gilyén. Quantum singular value transformation & its algorithmic applications. ILLC Dissertation Series, 2019. Google Scholar
  10. András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 193-204, 2019. Google Scholar
  11. Ofer Grossman and Yang P Liu. Reproducibility and pseudo-determinism in log-space. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 606-620. SIAM, 2019. Google Scholar
  12. Aram W Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. Physical review letters, 103(15):150502, 2009. Google Scholar
  13. Gillat Kol, Ran Raz, and Avishay Tal. Time-space hardness of learning sparse parities. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2017), pages 1067-1080, 2017. Google Scholar
  14. R. Landauer. Irreversibility and heat generation in the computing process. IBM Journal of Research and Development, 5(3):183-191, 1961. Google Scholar
  15. Klaus-Jörn Lange, Pierre McKenzie, and Alain Tapp. Reversible space equals deterministic space. Journal of Computer and System Sciences, 60(2):354-367, 2000. Google Scholar
  16. Chris Marriott and John Watrous. Quantum arthur-merlin games. Computational Complexity, 14(2):122-152, 2005. Google Scholar
  17. Dieter van Melkebeek and Thomas Watson. Time-space efficient simulations of quantum computations. Theory of Computing, 8(1):1-51, 2012. Google Scholar
  18. Dana Moshkovitz and Michal Moshkovitz. Entropy samplers and strong generic lower bounds for space bounded learning. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  19. Michael A Nielsen and Isaac L Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2010. Google Scholar
  20. David Perez-Garcia, Michael M Wolf, Denes Petz, and Mary Beth Ruskai. Contractivity of positive and trace-preserving maps under l p norms. Journal of Mathematical Physics, 47(8):083506, 2006. Google Scholar
  21. Ran Raz. A time-space lower bound for a large class of learning problems. In 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2017), pages 732-742, 2017. Google Scholar
  22. Ran Raz. Fast learning requires good memory: A time-space lower bound for parity learning. Journal of the ACM (JACM), 66(1):1-18, 2018. Google Scholar
  23. Michael Saks and Shiyu Zhou. BPHSPACE(s) ⊆ DSPACE(s^3/2). Journal of computer and system sciences, 58(2):376-403, 1999. Google Scholar
  24. Ohad Shamir. Fundamental limits of online and distributed algorithms for statistical learning and estimation. In Advances in Neural Information Processing Systems 27 (NIPS 2014), pages 163-171, 2014. Google Scholar
  25. Yaoyun Shi. Both toffoli and controlled-not need little help to do universal quantum computing. Quantum Info. Comput., 3(1):84–92, 2003. Google Scholar
  26. Jacob Steinhardt, Gregory Valiant, and Stefan Wager. Memory, communication, and statistical queries. In Conference on Learning Theory (COLT 2016), pages 1490-1516, 2016. Google Scholar
  27. Amnon Ta-Shma. Inverting well conditioned matrices in quantum logspace. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC 2013), pages 881-890, 2013. Google Scholar
  28. John Watrous. Space-bounded quantum complexity. Journal of Computer and System Sciences, 59(2):281-326, 1999. Google Scholar
  29. Fuzhen Zhang. Matrix theory: basic results and techniques. Springer Science & Business Media, 2011. 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 Imprint Privacy Contact