Document Open Access Logo

Improvements in Quantum SDP-Solving with Applications

Authors Joran van Apeldoorn, András Gilyén

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.99.pdf
  • Filesize: 0.51 MB
  • 15 pages

Document Identifiers

Author Details

Joran van Apeldoorn
  • QuSoft, CWI, The Netherlands
András Gilyén
  • QuSoft, CWI, The Netherlands

Funding

  • van Apeldoorn, Joran: Supported by the Netherlands Organization for Scientific Research, grant number 617.001.351.
  • Gilyén, András: Supported by ERC Consolidator Grant 615307-QPROGRESS and partially supported by QuantERA project QuantAlgo 680-91-034.

Acknowledgements

We thank the authors of [Fernando G. S. L. Brandão et al., 2018] for sending work-in-progress versions of their paper, and Fernando Brãndao, Tongyang Li and Xiaodi Wu for personal communication. A.G. thanks Robin Kothari and Nathan Wiebe for useful discussions. We thank Jamie Sikora for useful discussions about applications and for suggesting the state discrimination problem. We are grateful to Ronald de Wolf and Sander Gribling for useful discussions, and advice about the manuscript.

Cite AsGet BibTex

Joran van Apeldoorn and András Gilyén. Improvements in Quantum SDP-Solving with Applications. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 99:1-99:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.99

Abstract

Following the first paper on quantum algorithms for SDP-solving by Brandão and Svore [Brandão and Svore, 2017] in 2016, rapid developments have been made on quantum optimization algorithms. In this paper we improve and generalize all prior quantum algorithms for SDP-solving and give a simpler and unified framework. We take a new perspective on quantum SDP-solvers and introduce several new techniques. One of these is the quantum operator input model, which generalizes the different input models used in previous work, and essentially any other reasonable input model. This new model assumes that the input matrices are embedded in a block of a unitary operator. In this model we give a O~((sqrt{m}+sqrt{n}gamma)alpha gamma^4) algorithm, where n is the size of the matrices, m is the number of constraints, gamma is the reciprocal of the scale-invariant relative precision parameter, and alpha is a normalization factor of the input matrices. In particular for the standard sparse-matrix access, the above result gives a quantum algorithm where alpha=s. We also improve on recent results of Brandão et al. [Fernando G. S. L. Brandão et al., 2018], who consider the special case when the input matrices are proportional to mixed quantum states that one can query. For this model Brandão et al. [Fernando G. S. L. Brandão et al., 2018] showed that the dependence on n can be replaced by a polynomial dependence on both the rank and the trace of the input matrices. We remove the dependence on the rank and hence require only a dependence on the trace of the input matrices. After we obtain these results we apply them to a few different problems. The most notable of which is the problem of shadow tomography, recently introduced by Aaronson [Aaronson, 2018]. Here we simultaneously improve both the sample and computational complexity of the previous best results. Finally we prove a new Omega~(sqrt{m}alpha gamma) lower bound for solving LPs and SDPs in the quantum operator model, which also implies a lower bound for the model of Brandão et al. [Fernando G. S. L. Brandão et al., 2018].

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum computation theory
Keywords
  • quantum algorithms
  • semidefinite programming
  • shadow tomography

Metrics

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

Related Versions

References

  1. Scott Aaronson. Quantum Copy-Protection and Quantum Money. In çc24th, pages 229-242, 2009. https://arxiv.org/abs/1110.5353. URL: http://dx.doi.org/10.1109/CCC.2009.42.
  2. Scott Aaronson. Shadow Tomography of Quantum States. In \stoc50th, pages 325-338, 2018. https://arxiv.org/abs/1711.01053. URL: http://dx.doi.org/10.1145/3188745.3188802.
  3. Joran van Apeldoorn and András Gilyén. Improvements in Quantum SDP-Solving with Applications. https://arxiv.org/abs/1804.05058, 2018.
  4. Joran van Apeldoorn and András Gilyén. Quantum algorithms for zero-sum games. https://arxiv.org/abs/1904.03180, 2019.
  5. Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf. Quantum SDP-Solvers: Better upper and lower bounds. In \focs58th, pages 403-414, 2017. https://arxiv.org/abs/1705.01843. URL: http://dx.doi.org/10.1109/FOCS.2017.44.
  6. Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf. Convex optimization using quantum oracles. https://arxiv.org/abs/1809.00643, 2018.
  7. Sanjeev Arora and Satyen Kale. A Combinatorial, Primal-Dual Approach to Semidefinite Programs. \jacm, 63(2):12:1-12:35, 2016. Earlier version in STOC'07. URL: http://dx.doi.org/10.1145/2837020.
  8. Aleksandrs Belovs. Variations on Quantum Adversary. https://arxiv.org/abs/1504.06943, 2015.
  9. Dominic W. Berry, Andrew M. Childs, and Robin Kothari. Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters. In \focs56th, pages 792-809, 2015. https://arxiv.org/abs/1501.01715. URL: http://dx.doi.org/10.1109/FOCS.2015.54.
  10. Arvid J. Bessen. Lower bound for quantum phase estimation. \pra, 71(4):042313, 2005. https://arxiv.org/abs/quant-ph/0412008. URL: http://dx.doi.org/10.1103/PhysRevA.71.042313.
  11. Fernando G. S. L. Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore, and Xiaodi Wu. Exponential Quantum Speed-ups for Semidefinite Programming with Applications to Quantum Learning, 2017. First arXiv version. URL: http://arxiv.org/abs/1710.02581v1.
  12. 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, 2018. URL: http://arxiv.org/abs/1710.02581v2.
  13. Fernando G. S. L. Brandão and Krysta M. Svore. Quantum Speed-ups for Solving Semidefinite Programs. In \focs58th, pages 415-426, 2017. https://arxiv.org/abs/1609.05537. URL: http://dx.doi.org/10.1109/FOCS.2017.45.
  14. Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li, and Xiaodi Wu. Quantum algorithms and lower bounds for convex optimization. https://arxiv.org/abs/1809.01731, 2018.
  15. Shantanav Chakraborty, András Gilyén, and Stacey Jeffery. The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation. https://arxiv.org/abs/1804.01973, 2018.
  16. Richard Cleve, Peter Høyer, Benjamin Toner, and John Watrous. Consequences and limits of nonlocal strategies. In çc19th, pages 236-249, 2004. https://arxiv.org/abs/quant-ph/0404076. URL: http://dx.doi.org/10.1109/CCC.2004.1313847.
  17. Christoph Dürr and Peter Høyer. A Quantum Algorithm for Finding the Minimum. https://arxiv.org/abs/quant-ph/9607014, 1996.
  18. Yonina C. Eldar. A Semidefinite Programming Approach to Optimal Unambiguous Discrimination of Quantum States. \ieeeit, 49:446-456, 2003. https://arxiv.org/abs/quant-ph/0206093. URL: http://dx.doi.org/10.1109/TIT.2002.807291.
  19. András Gilyén, Srinivasan Arunachalam, and Nathan Wiebe. Optimizing quantum optimization algorithms via faster quantum gradient computation. In \soda30th, pages 1425-1444, 2019. https://arxiv.org/abs/1711.00465. URL: http://dx.doi.org/10.1137/1.9781611975482.87.
  20. 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 \stoc51st, 2019. (to appear) https://arxiv.org/abs/1806.01838. URL: http://dx.doi.org/10.1145/3313276.3316366.
  21. Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. \jacm, 42(6):1115-1145, 1995. Earlier version in STOC'94. URL: http://dx.doi.org/10.1145/227683.227684.
  22. Iordanis Kerenidis and Anupam Prakash. Quantum Recommendation Systems. In \itcs8th, pages 49:1-49:21, 2017. https://arxiv.org/abs/1603.08675. URL: http://dx.doi.org/10.4230/LIPIcs.ITCS.2017.49.
  23. Iordanis Kerenidis and Anupam Prakash. A Quantum Interior Point Method for LPs and SDPs. https://arxiv.org/abs/1808.09266, 2018.
  24. Jean Lasserre. Global Optimization with Polynomials and the Problem of Moments. \siamjo, 11(3):796-817, 2001. URL: http://dx.doi.org/10.1137/S1052623400366802.
  25. James R. Lee, Prasad Raghavendra, and David Steurer. Lower Bounds on the Size of Semidefinite Programming Relaxations. In \stoc47th, pages 567-576, 2015. https://arxiv.org/abs/1411.6317. URL: http://dx.doi.org/10.1145/2746539.2746599.
  26. Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong. A faster cutting plane method and its implications for combinatorial and convex optimization. In \focs56th, pages 1049-1065, 2015. https://arxiv.org/abs/1508.04874. URL: http://dx.doi.org/10.1109/FOCS.2015.68.
  27. Guang Hao Low and Isaac L. Chuang. Hamiltonian Simulation by Qubitization. https://arxiv.org/abs/1610.06546, 2016.
  28. Guang Hao Low and Isaac L. Chuang. Hamiltonian Simulation by Uniform Spectral Amplification. https://arxiv.org/abs/1707.05391, 2017.
  29. Pablo A. Parrilo. Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization. PhD thesis, California Institute of Technology, 2000. URL: https://thesis.library.caltech.edu/1647/.
  30. Xiaodi Wu. Personal communication. Email, November 2017. 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