Document Open Access Logo

Quantum Query Complexity with Matrix-Vector Products

Authors Andrew M. Childs, Shih-Han Hung, Tongyang Li

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.55.pdf
  • Filesize: 0.72 MB
  • 19 pages

Document Identifiers

Author Details

Andrew M. Childs
  • Joint Center for Quantum Information and Computer Science, Department of Computer Science, and Institute for Advanced Computer Studies, University of Maryland, College Park, MD, USA
Shih-Han Hung
  • Joint Center for Quantum Information and Computer Science, Department of Computer Science, and Institute for Advanced Computer Studies, University of Maryland, College Park, MD, USA
Tongyang Li
  • Joint Center for Quantum Information and Computer Science, Department of Computer Science, and Institute for Advanced Computer Studies, University of Maryland, College Park, MD, USA
  • Center for Theoretical Physics, MIT, Cambridge, MA, USA

Funding

AMC and SHH acknowledge support from the Army Research Office (grant W911NF-20-1-0015); the Department of Energy, Office of Science, Office of Advanced Scientific Computing Research, Quantum Algorithms Teams and Accelerated Research in Quantum Computing programs; and the National Science Foundation (grant CCF-1813814).
  • Li, Tongyang: TL acknowledges support from ARO contract W911NF-17-1-0433, NSF grant PHY-1818914, and a Samsung Advanced Institute of Technology Global Research Partnership.

Acknowledgements

We thank Robin Kothari for bringing our attention to work on classical algorithms in the matrix-vector and vector-matrix-vector query models, and for providing feedback on an initial version of this paper. We thank Max Simchowitz and Blake Woodworth for a discussion that clarified aspects of their paper [Braverman et al., 2020], and Jialin Zhang for clarifications of her paper [Sun et al., 2019]. We also thank Ashley Montanaro for pointing out connections to his paper [Montanaro and Shao, 2020], and Joran van Apeldoorn and Sander Gribling for a discussion of their paper [Apeldoorn and Gribling, 2018].

Cite As Get BibTex

Andrew M. Childs, Shih-Han Hung, and Tongyang Li. Quantum Query Complexity with Matrix-Vector Products. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 55:1-55:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ICALP.2021.55

Abstract

We study quantum algorithms that learn properties of a matrix using queries that return its action on an input vector. We show that for various problems, including computing the trace, determinant, or rank of a matrix or solving a linear system that it specifies, quantum computers do not provide an asymptotic speedup over classical computation. On the other hand, we show that for some problems, such as computing the parities of rows or columns or deciding if there are two identical rows or columns, quantum computers provide exponential speedup. We demonstrate this by showing equivalence between models that provide matrix-vector products, vector-matrix products, and vector-matrix-vector products, whereas the power of these models can vary significantly for classical computation.

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum query complexity
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Quantum algorithms
  • quantum query complexity
  • matrix-vector products

Metrics

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

Related Versions

References

  1. Scott Aaronson. Quantum lower bound for the collision problem. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing, pages 635-642, 2002. URL: https://arxiv.org/abs/quant-ph/0111102.
  2. Scott Aaronson. Read the fine print. Nature Physics, 11(4):291, 2015. Google Scholar
  3. Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf. Convex optimization using quantum oracles. Quantum, 4:220, 2020. URL: https://arxiv.org/abs/1809.00643.
  4. Joran van Apeldoorn and Sander Gribling. Simon’s problem for linear functions, 2018. URL: https://arxiv.org/abs/1810.12030.
  5. Simon Apers and Ronald de Wolf. Quantum speedup for graph sparsification, cut approximation and laplacian solving. In Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, pages 637-648. IEEE, 2020. URL: https://arxiv.org/abs/1911.07306.
  6. Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. Quantum lower bounds by polynomials. Journal of the ACM, 48(4):778-797, 2001. URL: https://arxiv.org/abs/quant-ph/9802049.
  7. Ethan Bernstein and Umesh Vazirani. Quantum complexity theory. SIAM Journal on Computing, 26(5):1411-1473, 1997. Google Scholar
  8. Mark Braverman, Elad Hazan, Max Simchowitz, and Blake Woodworth. The gradient complexity of linear regression. In Conference on Learning Theory, pages 627-647, 2020. URL: https://arxiv.org/abs/1911.02212.
  9. Andries E. Brouwer, Arjeh M. Cohen, and Arnold Neumaier. Distance-Regular Graphs. Springer-Verlag, 1989. Google Scholar
  10. Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li, and Xiaodi Wu. Quantum algorithms and lower bounds for convex optimization. Quantum, 4:221, 2020. URL: https://arxiv.org/abs/1809.01731.
  11. Andrew M. Childs. Equation solving by simulation. Nature Physics, 5:861, 2009. URL: https://doi.org/10.1038/nphys1473.
  12. Daniel Copeland and Jamie Pommersheim. Quantum query complexity of symmetric oracle problems. Quantum, 5:403, 2021. URL: https://arxiv.org/abs/1812.09428.
  13. Ankit Garg, Robin Kothari, Praneeth Netrapalli, and Suhail Sherif. No quantum speedup over gradient descent for non-smooth convex optimization. In 12th Innovations in Theoretical Computer Science Conference (to appear), 2021. URL: https://arxiv.org/abs/2010.01801.
  14. Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. Physical Review Letters, 103(15):150502, 2009. URL: https://arxiv.org/abs/0811.3171.
  15. Stephen P. Jordan. Fast quantum algorithm for numerical gradient estimation. Physical Review Letters, 95(5):050501, 2005. URL: https://arxiv.org/abs/quant-ph/0405146.
  16. Pascal Koiran, Vincent Nesme, and Natacha Portier. The quantum query complexity of the abelian hidden subgroup problem. Theoretical Computer Science, 380(1-2):115-126, 2007. Google Scholar
  17. Troy Lee, Miklos Santha, and Shengyu Zhang. Quantum algorithms for graph problems with cut queries. In Proceedings of the 32nd ACM-SIAM Symposium on Discrete Algorithms, pages 939-958. SIAM, 2021. URL: https://arxiv.org/abs/2007.08285.
  18. Ashley Montanaro and Changpeng Shao. Quantum algorithms for learning graphs and beyond, 2020. URL: https://arxiv.org/abs/2011.08611.
  19. Cyrus Rashtchian, David P. Woodruff, and Hanlin Zhu. Vector-matrix-vector queries for solving linear algebra, statistics, and graph problems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. URL: https://arxiv.org/abs/2006.14015.
  20. Jean-Pierre Serre. Linear Representations of Finite Groups, volume 42 of Graduate Texts in Mathematics. Springer, 1977. Google Scholar
  21. Xiaoming Sun, David P. Woodruff, Guang Yang, and Jialin Zhang. Querying a matrix through matrix-vector products. In 46th International Colloquium on Automata, Languages, and Programming. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. URL: https://arxiv.org/abs/1906.05736.
  22. David P. Woodruff. Sketching as a tool for numerical linear algebra. Foundations and Trends in Theoretical Computer Science, 10(1-2):1-157, 2014. URL: https://arxiv.org/abs/1411.4357.
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