Document Open Access Logo

Quantum SDP Solvers: Large Speed-Ups, Optimality, and Applications to Quantum Learning

Authors Fernando G. S. L. Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore, Xiaodi Wu

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.27.pdf
  • Filesize: 0.49 MB
  • 14 pages

Document Identifiers

Author Details

Fernando G. S. L. Brandão
  • Institute of Quantum Information and Matter, California Institute of Technology, USA
Amir Kalev
  • Joint Center for Quantum Information and Computer Science, University of Maryland, USA
Tongyang Li
  • Joint Center for Quantum Information and Computer Science, University of Maryland, USA
Cedric Yen-Yu Lin
  • Joint Center for Quantum Information and Computer Science, University of Maryland, USA
Krysta M. Svore
  • Station Q, Quantum Architectures and Computation Group, Microsoft Research, USA
Xiaodi Wu
  • Joint Center for Quantum Information and Computer Science, University of Maryland, USA

Acknowledgements

We thank Scott Aaronson, Joran van Apeldoorn, Andr{á}s Gilyén, Cupjin Huang, and anonymous reviewers for helpful discussions. We are also grateful to Joran van Apeldoorn and Andr{á}s Gilyén for sharing a working draft of [Apeldoorn and Gilyén, 2018] with us. FB was supported by NSF. CYL and AK were supported by the Department of Defense. TL was supported by NSF CCF-1526380. XW was supported by NSF grants CCF-1755800 and CCF-1816695, and also by the U.S. Department of Energy, Office of Science, Office of Advanced Scientific Computing Research, Quantum Algorithms Teams program.

Cite AsGet BibTex

Fernando G. S. L. Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore, and Xiaodi Wu. Quantum SDP Solvers: Large Speed-Ups, Optimality, and Applications to Quantum Learning. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.27

Abstract

We give two new quantum algorithms for solving semidefinite programs (SDPs) providing quantum speed-ups. We consider SDP instances with m constraint matrices, each of dimension n, rank at most r, and sparsity s. The first algorithm assumes an input model where one is given access to an oracle to the entries of the matrices at unit cost. We show that it has run time O~(s^2 (sqrt{m} epsilon^{-10} + sqrt{n} epsilon^{-12})), with epsilon the error of the solution. This gives an optimal dependence in terms of m, n and quadratic improvement over previous quantum algorithms (when m ~~ n). The second algorithm assumes a fully quantum input model in which the input matrices are given as quantum states. We show that its run time is O~(sqrt{m}+poly(r))*poly(log m,log n,B,epsilon^{-1}), with B an upper bound on the trace-norm of all input matrices. In particular the complexity depends only polylogarithmically in n and polynomially in r. We apply the second SDP solver to learn a good description of a quantum state with respect to a set of measurements: Given m measurements and a supply of copies of an unknown state rho with rank at most r, we show we can find in time sqrt{m}*poly(log m,log n,r,epsilon^{-1}) a description of the state as a quantum circuit preparing a density matrix which has the same expectation values as rho on the m measurements, up to error epsilon. The density matrix obtained is an approximation to the maximum entropy state consistent with the measurement data considered in Jaynes' principle from statistical mechanics. As in previous work, we obtain our algorithm by "quantizing" classical SDP solvers based on the matrix multiplicative weight update method. One of our main technical contributions is a quantum Gibbs state sampler for low-rank Hamiltonians, given quantum states encoding these Hamiltonians, with a poly-logarithmic dependence on its dimension, which is based on ideas developed in quantum principal component analysis. We also develop a "fast" quantum OR lemma with a quadratic improvement in gate complexity over the construction of Harrow et al. [Harrow et al., 2017]. We believe both techniques might be of independent interest.

Subject Classification

ACM Subject Classification
  • Theory of computation → Semidefinite programming
  • Theory of computation → Quantum query complexity
  • Theory of computation → Convex optimization
Keywords
  • quantum algorithms
  • semidefinite program
  • convex optimization

Metrics

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

Related Versions

References

  1. Scott Aaronson. The learnability of quantum states. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 463(2088):3089-3114, 2007. URL: http://arxiv.org/abs/quant-ph/0608142.
  2. Scott Aaronson. Shadow Tomography of Quantum States. In Proceedings of the Fiftieth Annual ACM Symposium on Theory of Computing. ACM, 2018. URL: http://arxiv.org/abs/1711.01053.
  3. Scott Aaronson, Xinyi Chen, Elad Hazan, and Ashwin Nayak. Online Learning of Quantum states, 2018. URL: http://arxiv.org/abs/1802.09025.
  4. Joran van Apeldoorn and András Gilyén. Improvements in Quantum SDP-solving with Applications, 2018. URL: http://arxiv.org/abs/1804.05058.
  5. Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf. Quantum SDP-Solvers: Better upper and lower bounds. In 58th Annual IEEE Symposium on Foundations of Computer Science. IEEE, 2017. URL: http://arxiv.org/abs/1705.01843.
  6. Sanjeev Arora, Elad Hazan, and Satyen Kale. The Multiplicative Weights Update Method: a Meta-Algorithm and Applications. Theory of Computing, 8(6):121-164, 2012. URL: http://dx.doi.org/10.4086/toc.2012.v008a006.
  7. Sanjeev Arora and Satyen Kale. A combinatorial, primal-dual approach to semidefinite programs. In Proceedings of the Thirty-ninth Annual ACM Symposium on Theory of Computing, pages 227-236. ACM, 2007. Google Scholar
  8. Fernando G. S. L. Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore, and Xiaodi Wu. Quantum SDP Solvers: Large Speed-ups, Optimality, and Applications to Quantum Learning, 2019. URL: http://arxiv.org/abs/1710.02581.
  9. Fernando G. S. L. Brandão and Krysta Svore. Quantum speed-ups for semidefinite programming. In 58th Annual IEEE Symposium on Foundations of Computer Science. IEEE, 2017. URL: http://arxiv.org/abs/1609.05537.
  10. Nai-Hui Chia, Tongyang Li, Han-Hsuan Lin, and Chunhao Wang. Quantum-inspired classical sublinear-time algorithm for solving low-rank semidefinite programming via sampling approaches, 2019. URL: http://arxiv.org/abs/1901.03254.
  11. Anirban Narayan Chowdhury and Rolando D. Somma. Quantum algorithms for Gibbs sampling and hitting-time estimation. Quantum Information &Computation, 17(LA-UR-16-21218), 2017. URL: http://arxiv.org/abs/1603.02940.
  12. Gus Gutoski and Xiaodi Wu. Parallel approximation of min-max problems with applications to classical and quantum zero-sum games. In Proceedings of the Twenty-seventh Annual IEEE Symposium on Computational Complexity (CCC), pages 21-31. IEEE, 2012. Google Scholar
  13. Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu. Sample-optimal Tomography of Quantum States. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing, pages 913-925. ACM, 2016. URL: http://arxiv.org/abs/1508.01797.
  14. Aram W. Harrow, Cedric Yen-Yu Lin, and Ashley Montanaro. Sequential measurements, disturbance and property testing. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1598-1611. SIAM, 2017. URL: http://arxiv.org/abs/1607.03236.
  15. Elad Hazan. Efficient algorithms for online convex optimization and their applications. PhD thesis, Princeton University, 2006. Google Scholar
  16. Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, and John Watrous. QIP=PSPACE. Journal of the ACM (JACM), 58(6):30, 2011. URL: http://arxiv.org/abs/0907.4737.
  17. Edwin T. Jaynes. Information theory and statistical mechanics. Physical Review, 106(4):620, 1957. Google Scholar
  18. Shelby Kimmel, Cedric Yen-Yu Lin, Guang Hao Low, Maris Ozols, and Theodore J. Yoder. Hamiltonian simulation with optimal sample complexity. npj Quantum Information, 3(1):13, 2017. URL: http://arxiv.org/abs/1608.00281.
  19. James R. Lee, Prasad Raghavendra, and David Steurer. Lower Bounds on the Size of Semidefinite Programming Relaxations. In Proceedings of the Forty-seventh Annual ACM Symposium on Theory of Computing, pages 567-576, New York, NY, USA, 2015. ACM. URL: http://dx.doi.org/10.1145/2746539.2746599.
  20. Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong. A faster cutting plane method and its implications for combinatorial and convex optimization. In Proceedings of the Fifty-sixth Annual IEEE Symposium on Foundations of Computer Science, pages 1049-1065. IEEE, 2015. URL: http://arxiv.org/abs/1508.04874.
  21. Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. Quantum principal component analysis. Nature Physics, 10(9):631, 2014. URL: http://arxiv.org/abs/1307.0401.
  22. Daniel Nagaj, Pawel Wocjan, and Yong Zhang. Fast amplification of QMA, 2009. URL: http://arxiv.org/abs/0904.1549.
  23. Ryan O'Donnell and John Wright. Efficient Quantum Tomography. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing, pages 899-912. ACM, 2016. URL: http://arxiv.org/abs/1508.01907.
  24. David Poulin and Pawel Wocjan. Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer. Physical Review Letters, 103(22):220502, 2009. URL: http://arxiv.org/abs/0905.2199.
  25. Ewin Tang. A quantum-inspired classical algorithm for recommendation systems. In Proceedings of the 51st Annual ACM Symposium on Theory of Computing. ACM, 2019. URL: http://arxiv.org/abs/1807.04271.
  26. Ronald de Wolf. Personal communication, 2017. Google Scholar
  27. Xiaodi Wu. Parallelized Solution to Semidefinite Programmings in Quantum Complexity Theory, 2010. URL: http://arxiv.org/abs/1009.2211.
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