Quantum SDP-Solvers: Better upper and lower bounds

Joran van Apeldoorn1, András Gilyén1, Sander Gribling1, and Ronald de Wolf2

1QuSoft, CWI, Amsterdam, the Netherlands
2QuSoft, CWI and University of Amsterdam, the Netherlands

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

Brandão and Svore [14] recently gave quantum algorithms for approximately solving semidefinite programs, which in some regimes are faster than the best-possible classical algorithms in terms of the dimension $n$ of the problem and the number $m$ of constraints, but worse in terms of various other parameters. In this paper we improve their algorithms in several ways, getting better dependence on those other parameters. To this end we develop new techniques for quantum algorithms, for instance a general way to efficiently implement smooth functions of sparse Hamiltonians, and a generalized minimum-finding procedure.

We also show limits on this approach to quantum SDP-solvers, for instance for combinatorial optimization problems that have a lot of symmetry. Finally, we prove some general lower bounds showing that in the worst case, the complexity of every quantum LP-solver (and hence also SDP-solver) has to scale linearly with $mn$ when $m\approx n$, which is the same as classical.

Semidefinite programs (SDPs) are an important tool in convex optimization tasks and approximation algorithms. They allow to optimize a linear function over positive semidefinite matrices, subject to linear constraints on those matrices, and they are solvable in polynomial time on a classical computer. Brandão and Svore recently gave a quantum algorithm for solving semidefinite programs that (in some regimes) is faster than the best-possible classical algorithm. In this paper we improve on their algorithm in several ways, in particular we obtain a 4-th root improvement in the running time with respect to the required precision. We also show strong limits for this particular approach to quantum SDP-solvers, for instance for combinatorial optimization problems that have a lot of symmetry, and we prove some general limitations for quantum SDP-solvers.

► BibTeX data

► References

[1] 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.
https:/​/​doi.org/​10.4086/​toc.2012.v008a006

[2] Sanjeev Arora and Satyen Kale. A combinatorial, primal-dual approach to semidefinite programs. Journal of the ACM , 63(2):12:1–12:35, 2016. Earlier version in STOC'07.
https:/​/​doi.org/​10.1145/​2837020

[3] Andris Ambainis. Quantum walk algorithm for element distinctness. SIAM Journal on Computing , 37(1):210–239, 2007. Earlier version in FOCS'04. arXiv: quant-ph/​0311001.
https:/​/​doi.org/​10.1137/​S0097539705447311
arXiv:quant-ph/0311001

[4] Joran van Apeldoorn and András Gilyén. Improvements in quantum SDP-solving with applications. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP) , pages 99:1–99:15, 2019. arXiv: 1804.05058.
https:/​/​doi.org/​10.4230/​LIPIcs.ICALP.2019.99
arXiv:1804.05058

[5] Joran van Apeldoorn and András Gilyén. Quantum algorithms for zero-sum games. arXiv: 1904.03180, 2019.
arXiv:1904.03180

[6] Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf. Quantum SDP-solvers: Better upper and lower bounds. In Proceedings of the 58th IEEE Symposium on Foundations of Computer Science (FOCS) , pages 403–414, 2017. arXiv: 1705.01843.
https:/​/​doi.org/​10.1109/​FOCS.2017.44
arXiv:1705.01843

[7] Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf. Convex optimization using quantum oracles. Quantum , 4:220, 2020. arXiv: 1809.00643.
https:/​/​doi.org/​10.22331/​q-2020-01-13-220
arXiv:1809.00643

[8] Noga Alon and Joel H. Spencer. The Probabilistic Method. Wiley-Interscience, third edition, 2008.
https:/​/​doi.org/​10.1002/​0471722154

[9] Michel Boyer, Gilles Brassard, Peter Høyer, and Alain Tapp. Tight bounds on quantum searching. Fortschritte der Physik, 46(4–5):493–505, 1998. arXiv: quant-ph/​9605034.
https:/​/​doi.org/​10.1002/​(SICI)1521-3978(199806)46:4/​5<493::AID-PROP493>3.0.CO;2-P
arXiv:quant-ph/9605034

[10] Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. Simulating Hamiltonian dynamics with a truncated Taylor series. Physical Review Letters , 114(9):090502, 2015. arXiv: 1412.4687.
https:/​/​doi.org/​10.1103/​PhysRevLett.114.090502
arXiv:1412.4687

[11] Dominic W. Berry, Andrew M. Childs, and Robin Kothari. Hamiltonian simulation with nearly optimal dependence on all parameters. In Proceedings of the 56th IEEE Symposium on Foundations of Computer Science (FOCS) , pages 792–809, 2015. arXiv: 1501.01715.
https:/​/​doi.org/​10.1109/​FOCS.2015.54
arXiv:1501.01715

[12] Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. In Quantum Computation and Quantum Information: A Millennium Volume, volume 305 of Contemporary Mathematics Series, pages 53–74. AMS, 2002. arXiv: quant-ph/​0005055.
https:/​/​doi.org/​10.1090/​conm/​305/​05215
arXiv:quant-ph/0005055

[13] 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 Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP) , pages 27:1–27:14, 2019. arXiv: 1710.02581.
https:/​/​doi.org/​10.4230/​LIPIcs.ICALP.2019.27
arXiv:1710.02581

[14] Fernando G. S. L. Brandão and Krysta M. Svore. Quantum speed-ups for solving semidefinite programs. In Proceedings of the 58th IEEE Symposium on Foundations of Computer Science (FOCS) , pages 415–426, 2017. arXiv: 1609.05537.
https:/​/​doi.org/​10.1109/​FOCS.2017.45
arXiv:1609.05537

[15] Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li, and Xiaodi Wu. Quantum algorithms and lower bounds for convex optimization. Quantum , 4:221, 2020. arXiv: 1809.01731.
https:/​/​doi.org/​10.22331/​q-2020-01-13-221
arXiv:1809.01731

[16] Richard Cleve, Artur Ekert, Chiara Macchiavello, and Michele Mosca. Quantum algorithms revisited. Proceedings of the Royal Society A , 454(1969):339–354, 1998. arXiv: quant-ph/​9708016.
https:/​/​doi.org/​10.1098/​rspa.1998.0164
arXiv:quant-ph/9708016

[17] Andrew M. Childs, Robin Kothari, and Rolando D. Somma. Quantum algorithm for systems of linear equations with exponentially improved dependence on precision. SIAM Journal on Computing , 46(6):1920–1950, 2017. arXiv: 1511.02306.
https:/​/​doi.org/​10.1137/​16M1087072
arXiv:1511.02306

[18] Anirban Narayan Chowdhury and Rolando D. Somma. Quantum algorithms for Gibbs sampling and hitting-time estimation. Quantum Information and Computation , 17(1&2):41–64, 2017. arXiv: 1603.02940.
https:/​/​doi.org/​10.26421/​QIC17.1-2
arXiv:1603.02940

[19] Andrew M. Childs and Nathan Wiebe. Hamiltonian simulation using linear combinations of unitary operations. Quantum Information and Computation , 12(11&12):901–924, 2012. arXiv: 1202.5822.
https:/​/​doi.org/​10.26421/​QIC12.11-12
arXiv:1202.5822

[20] George B. Dantzig. Maximization of a linear function of variables subject to linear inequalities. In Activity Analysis of Production and Allocation, Cowles Commission Monograph No. 13, pages 339–347. John Wiley & Sons Inc., New York, N. Y., 1951.

[21] Christoph Dürr and Peter Høyer. A quantum algorithm for finding the minimum. arXiv: quant-ph/​9607014, 1996.
arXiv:quant-ph/9607014

[22] Christoph Dürr, Mark Heiligman, Peter Høyer, and Mehdi Mhalla. Quantum query complexity of some graph problems. SIAM Journal on Computing , 35(6):1310–1328, 2006. Earlier version in ICALP'04. arXiv: quant-ph/​0401091.
https:/​/​doi.org/​10.1137/​050644719
arXiv:quant-ph/0401091

[23] Martin Grötschel, László Lovász, and Alexander Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica , 1(2):169–197, 1981.
https:/​/​doi.org/​10.1007/​BF02579273

[24] Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric Algorithms and Combinatorial Optimization. Springer, 1988.

[25] Lov Grover and Terry Rudolph. Creating superpositions that correspond to efficiently integrable probability distributions. arXiv: quant-ph/​0208112, 2002.
arXiv:quant-ph/0208112

[26] Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the 28th ACM Symposium on the Theory of Computing (STOC) , pages 212–219, 1996. arXiv: quant-ph/​9605043.
https:/​/​doi.org/​10.1145/​237814.237866
arXiv:quant-ph/9605043

[27] 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 ACM Symposium on the Theory of Computing (STOC) , pages 193–204, 2019. arXiv: 1806.01838.
https:/​/​doi.org/​10.1145/​3313276.3316366
arXiv:1806.01838

[28] Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM , 42(6):1115–1145, 1995. Earlier version in STOC'94.
https:/​/​doi.org/​10.1145/​227683.227684

[29] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. Physical Review Letters , 103(15):150502, 2009. arXiv: 0811.3171.
https:/​/​doi.org/​10.1103/​PhysRevLett.103.150502
arXiv:0811.3171

[30] Shelby Kimmel. Quantum adversary (upper) bound. Chicago Journal of Theoretical Computer Science , 2013:4:1–14, 2013. Earlier version in ICALP'12. arXiv: 1101.0797.
https:/​/​doi.org/​10.4086/​cjtcs.2013.004
arXiv:1101.0797

[31] Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell. Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM Journal on Computing , 37(1):319–357, 2007. Earlier version in FOCS'04.
https:/​/​doi.org/​10.1137/​S0097539705447372

[32] Iordanis Kerenidis and Anupam Prakash. A quantum interior point method for LPs and SDPs. arXiv: 1808.09266, 2018.
arXiv:1808.09266

[33] Guang Hao Low and Isaac L. Chuang. Optimal Hamiltonian simulation by quantum signal processing. Physical Review Letters , 118(1):010501, 2017. arXiv: 1606.02685.
https:/​/​doi.org/​10.1103/​PhysRevLett.118.010501
arXiv:1606.02685

[34] Guang Hao Low and Isaac L. Chuang. Hamiltonian simulation by qubitization. Quantum , 3:163, 2019. arXiv: 1610.06546.
https:/​/​doi.org/​10.22331/​q-2019-07-12-163
arXiv:1610.06546

[35] 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 56th IEEE Symposium on Foundations of Computer Science (FOCS) , pages 1049–1065, 2015. arXiv: 1508.04874.
https:/​/​doi.org/​10.1109/​FOCS.2015.68
arXiv:1508.04874

[36] Michael A. Nielsen and Isaac L. Chuang. Quantum computation and quantum information. Cambridge University Press, 2000.
https:/​/​doi.org/​10.1017/​CBO9780511976667

[37] Y. Nesterov and A. Nemirovski. Interior-point polynomial algorithms in convex programming, volume 13 of SIAM Studies in Applied Mathematics. Society for Industrial and Applied Mathematics (SIAM), 1994.
https:/​/​doi.org/​10.1137/​1.9781611970791

[38] David Poulin and Pawel Wocjan. Preparing ground states of quantum many-body systems on a quantum computer. Physical Review Letters , 102(13):130503, 2009. arXiv: 0809.2705.
https:/​/​doi.org/​10.1103/​PhysRevLett.102.130503
arXiv:0809.2705

[39] 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. arXiv: 0905.2199.
https:/​/​doi.org/​10.1103/​PhysRevLett.103.220502
arXiv:0905.2199

[40] James Renegar. ``Efficient'' subgradient methods for general convex optimization. SIAM Journal on Computing , 26(4):2649–2676, 2016. arXiv: 1605.08712.
https:/​/​doi.org/​10.1137/​15M1027371
arXiv:1605.08712

[41] James Renegar. Accelerated first-order methods for hyperbolic programming. Mathematical Programming, 173(1):1–35, 2019. arXiv: 1512.07569.
https:/​/​doi.org/​10.1007/​s10107-017-1203-y
arXiv:1512.07569

[42] Alexander Schrijver. Theory of Linear and Integer Programming. John Wiley & Sons, Inc., New York, NY, USA, 1986.

[43] Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing , 26(5):1484–1509, 1997. Earlier version in FOCS'94. arXiv: quant-ph/​9508027.
https:/​/​doi.org/​10.1137/​S0097539795293172
arXiv:quant-ph/9508027

[44] Koji Tsuda, Gunnar Rätsch, and Manfred K. Warmuth. Matrix exponentiated gradient updates for on-line learning and Bregman projection. Journal of Machine Learning Research, 6:995–1018, 2005. Earlier version in NIPS'04.
http:/​/​jmlr.csail.mit.edu/​papers/​volume6/​tsuda05a/​tsuda05a.pdf

[45] Manfred K. Warmuth and Dima Kuzmin. Online variance minimization. Machine Learning, 87(1):1–32, 2012. Earlier version in COLT'06.
https:/​/​doi.org/​10.1007/​s10994-011-5269-0

Cited by

[1] Tomotaka Kuwahara, Álvaro M. Alhambra, and Anurag Anshu, "Improved Thermal Area Law and Quasilinear Time Algorithm for Quantum Gibbs States", Physical Review X 11 1, 011047 (2021).

[2] Nai-Hui Chia, András Pal Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang, and Chunhao Wang, "Sampling-based Sublinear Low-rank Matrix Arithmetic Framework for Dequantizing Quantum Machine Learning", Journal of the ACM 69 5, 1 (2022).

[3] Dylan Herman, Cody Googin, Xiaoyuan Liu, Yue Sun, Alexey Galda, Ilya Safro, Marco Pistoia, and Yuri Alexeev, "Quantum computing for finance", Nature Reviews Physics 5 8, 450 (2023).

[4] Taylor L. Patti, Jean Kossaifi, Anima Anandkumar, and Susanne F. Yelin, "Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints", Quantum 7, 1057 (2023).

[5] Zhicheng Zhang, Qisheng Wang, and Mingsheng Ying, "Parallel Quantum Algorithm for Hamiltonian Simulation", Quantum 8, 1228 (2024).

[6] Dan-Bo Zhang, Guo-Qing Zhang, Zheng-Yuan Xue, Shi-Liang Zhu, and Z. D. Wang, "Continuous-Variable Assisted Thermal Quantum Simulation", Physical Review Letters 127 2, 020502 (2021).

[7] Brandon Augustino and Giacomo Nannicini, Encyclopedia of Optimization 1 (2023) ISBN:978-3-030-54621-2.

[8] Sergey Bravyi, Anirban Chowdhury, David Gosset, and Pawel Wocjan, "Quantum Hamiltonian complexity in thermal equilibrium", Nature Physics 18 11, 1367 (2022).

[9] Thais L. Silva, Márcio M. Taddei, Stefano Carrazza, and Leandro Aolita, "Fragmented imaginary-time evolution for early-stage quantum signal processors", Scientific Reports 13 1, 18258 (2023).

[10] Anurag Anshu, Srinivasan Arunachalam, Tomotaka Kuwahara, and Mehdi Soleimanifar, "Sample-efficient learning of interacting quantum systems", Nature Physics 17 8, 931 (2021).

[11] Dana Lahat, Yanbin Lang, Vincent Y. F. Tan, and Cedric Fevotte, "Positive Semidefinite Matrix Factorization: A Connection With Phase Retrieval and Affine Rank Minimization", IEEE Transactions on Signal Processing 69, 3059 (2021).

[12] Anurag Anshu, Srinivasan Arunachalam, Tomotaka Kuwahara, and Mehdi Soleimanifar, 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) 685 (2020) ISBN:978-1-7281-9621-3.

[13] Kyle E. C. Booth, Bryan O'Gorman, Jeffrey Marshall, Stuart Hadfield, and Eleanor Rieffel, "Quantum-accelerated constraint programming", Quantum 5, 550 (2021).

[14] Daniel J. Egger, Claudio Gambella, Jakub Marecek, Scott McFaddin, Martin Mevissen, Rudy Raymond, Andrea Simonetto, Stefan Woerner, and Elena Yndurain, "Quantum Computing for Finance: State-of-the-Art and Future Prospects", IEEE Transactions on Quantum Engineering 1, 1 (2020).

[15] Bobak Toussi Kiani, Giacomo De Palma, Milad Marvian, Zi-Wen Liu, and Seth Lloyd, "Learning quantum data with the quantum earth mover’s distance", Quantum Science and Technology 7 4, 045002 (2022).

[16] Tony Metger and Henry Yuen, 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) 1349 (2023) ISBN:979-8-3503-1894-4.

[17] Álvaro M. Alhambra, "Quantum Many-Body Systems in Thermal Equilibrium", PRX Quantum 4 4, 040201 (2023).

[18] Kyle E. C. Booth, Bryan O’Gorman, Jeffrey Marshall, Stuart Hadfield, and Eleanor Rieffel, Lecture Notes in Computer Science 12333, 72 (2020) ISBN:978-3-030-58474-0.

[19] Yu Tong, Dong An, Nathan Wiebe, and Lin Lin, "Fast inversion, preconditioned quantum linear system solvers, fast Green's-function computation, and fast evaluation of matrix functions", Physical Review A 104 3, 032422 (2021).

[20] Kianna Wan, Mario Berta, and Earl T. Campbell, "Randomized Quantum Algorithm for Statistical Phase Estimation", Physical Review Letters 129 3, 030503 (2022).

[21] Hari Krovi, "Improved quantum algorithms for linear and nonlinear differential equations", Quantum 7, 913 (2023).

[22] Lexing Ying, "Stable factorization for phase factors of quantum signal processing", Quantum 6, 842 (2022).

[23] Sofiene Jerbi, Lea M. Trenkwalder, Hendrik Poulsen Nautrup, Hans J. Briegel, and Vedran Dunjko, "Quantum Enhancements for Deep Reinforcement Learning in Large Spaces", PRX Quantum 2 1, 010328 (2021).

[24] Farhad Khosravi, Artur Scherer, and Pooya Ronagh, 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) 184 (2023) ISBN:979-8-3503-4323-6.

[25] Chenyi Zhang, Jiaqi Leng, and Tongyang Li, "Quantum algorithms for escaping from saddle points", Quantum 5, 529 (2021).

[26] Patrick Rall, Chunhao Wang, and Pawel Wocjan, "Thermal State Preparation via Rounding Promises", Quantum 7, 1132 (2023).

[27] Pavel Svetlichnyy and T. A. B. Kennedy, "Decay of quantum conditional mutual information for purely generated finitely correlated states", Journal of Mathematical Physics 63 7, 072201 (2022).

[28] Patrick Rebentrost, Yassine Hamoudi, Maharshi Ray, Xin Wang, Siyi Yang, and Miklos Santha, "Quantum algorithms for hedging and the learning of Ising models", Physical Review A 103 1, 012418 (2021).

[29] Daniel J. Egger, Jakub Mareček, and Stefan Woerner, "Warm-starting quantum optimization", Quantum 5, 479 (2021).

[30] Benjamin C B Symons, David Galvin, Emre Sahin, Vassil Alexandrov, and Stefano Mensa, "A practitioner’s guide to quantum algorithms for optimisation problems", Journal of Physics A: Mathematical and Theoretical 56 45, 453001 (2023).

[31] Zane M. Rossi and Isaac L. Chuang, "Semantic embedding for quantum algorithms", Journal of Mathematical Physics 64 12, 122202 (2023).

[32] Alexander M. Dalzell, B. David Clader, Grant Salton, Mario Berta, Cedric Yen-Yu Lin, David A. Bader, Nikitas Stamatopoulos, Martin J. A. Schuetz, Fernando G. S. L. Brandão, Helmut G. Katzgraber, and William J. Zeng, "End-To-End Resource Analysis for Quantum Interior-Point Methods and Portfolio Optimization", PRX Quantum 4 4, 040325 (2023).

[33] Youle Wang, Guangxi Li, and Xin Wang, "Variational Quantum Gibbs State Preparation with a Truncated Taylor Series", Physical Review Applied 16 5, 054035 (2021).

[34] Brandon Augustino, Giacomo Nannicini, Tamás Terlaky, and Luis F. Zuluaga, "Quantum Interior Point Methods for Semidefinite Optimization", Quantum 7, 1110 (2023).

[35] Luuk Coopmans, Yuta Kikuchi, and Marcello Benedetti, "Predicting Gibbs-State Expectation Values with Pure Thermal Shadows", PRX Quantum 4 1, 010305 (2023).

[36] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe, "Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics", arXiv:1806.01838, (2018).

[37] Alexander M. Dalzell, Sam McArdle, Mario Berta, Przemyslaw Bienias, Chi-Fang Chen, András Gilyén, Connor T. Hann, Michael J. Kastoryano, Emil T. Khabiboulline, Aleksander Kubica, Grant Salton, Samson Wang, and Fernando G. S. L. Brandão, "Quantum algorithms: A survey of applications and end-to-end complexities", arXiv:2310.03011, (2023).

[38] Carlo Ciliberto, Mark Herbster, Alessandro Davide Ialongo, Massimiliano Pontil, Andrea Rocchetto, Simone Severini, and Leonard Wossnig, "Quantum machine learning: a classical perspective", Proceedings of the Royal Society of London Series A 474 2209, 20170551 (2018).

[39] Patrick Rebentrost and Seth Lloyd, "Quantum computational finance: quantum algorithm for portfolio optimization", arXiv:1811.03975, (2018).

[40] 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", arXiv:1710.02581, (2017).

[41] Ronald de Wolf, "Quantum Computing: Lecture Notes", arXiv:1907.09415, (2019).

[42] Joran van Apeldoorn and András Gilyén, "Improvements in Quantum SDP-Solving with Applications", arXiv:1804.05058, (2018).

[43] Rui Chao, Dawei Ding, Andras Gilyen, Cupjin Huang, and Mario Szegedy, "Finding Angles for Quantum Signal Processing with Machine Precision", arXiv:2003.02831, (2020).

[44] András Gilyén, Srinivasan Arunachalam, and Nathan Wiebe, "Optimizing quantum optimization algorithms via faster quantum gradient computation", arXiv:1711.00465, (2017).

[45] Patrick Rebentrost, Maria Schuld, Leonard Wossnig, Francesco Petruccione, and Seth Lloyd, "Quantum gradient descent and Newton's method for constrained polynomial optimization", arXiv:1612.01789, (2016).

[46] Joran van Apeldoorn and András Gilyén, "Quantum algorithms for zero-sum games", arXiv:1904.03180, (2019).

[47] András Gilyén and Alexander Poremba, "Improved Quantum Algorithms for Fidelity Estimation", arXiv:2203.15993, (2022).

[48] Nai-Hui Chia, András Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang, and Chunhao Wang, "Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning", arXiv:1910.06151, (2019).

[49] Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li, and Xiaodi Wu, "Quantum algorithms and lower bounds for convex optimization", arXiv:1809.01731, (2018).

[50] Sam McArdle, András Gilyén, and Mario Berta, "Quantum state preparation without coherent arithmetic", arXiv:2210.14892, (2022).

[51] Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf, "Convex optimization using quantum oracles", arXiv:1809.00643, (2018).

[52] Yimin Ge, Jordi Tura, and J. Ignacio Cirac, "Faster ground state preparation and high-precision ground energy estimation with fewer qubits", arXiv:1712.03193, (2017).

[53] Yizhou Liu, Weijie J. Su, and Tongyang Li, "On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walks", Quantum 7, 1030 (2023).

[54] Zane M. Rossi and Isaac L. Chuang, "Multivariable quantum signal processing (M-QSP): prophecies of the two-headed oracle", Quantum 6, 811 (2022).

[55] Ivan Bardet and Cambyse Rouzé, "Hypercontractivity and logarithmic Sobolev Inequality for non-primitive quantum Markov semigroups and estimation of decoherence rates", arXiv:1803.05379, (2018).

[56] Nai-Hui Chia, Tongyang Li, Han-Hsuan Lin, and Chunhao Wang, "Quantum-inspired sublinear algorithm for solving low-rank semidefinite programming", arXiv:1901.03254, (2019).

[57] Chenyi Zhang and Tongyang Li, "Quantum Lower Bounds for Finding Stationary Points of Nonconvex Functions", arXiv:2212.03906, (2022).

[58] Garrett T. Floyd, David P. Landau, and Michael R. Geller, "Quantum algorithm for Wang-Landau sampling", arXiv:2208.09543, (2022).

[59] Cezar-Mihail Alexandru, Ella Bridgett-Tomkinson, Noah Linden, Joseph MacManus, Ashley Montanaro, and Hannah Morris, "Quantum speedups of some general-purpose numerical optimisation algorithms", Quantum Science and Technology 5 4, 045014 (2020).

[60] Adam Izdebski and Ronald de Wolf, "Improved Quantum Boosting", arXiv:2009.08360, (2020).

[61] Leonard Wossnig, "Quantum Machine Learning For Classical Data", arXiv:2105.03684, (2021).

[62] Joran van Apeldoorn, Sander Gribling, Yinan Li, Harold Nieuwboer, Michael Walter, and Ronald de Wolf, "Quantum algorithms for matrix scaling and matrix balancing", arXiv:2011.12823, (2020).

[63] Weiyuan Gong, Chenyi Zhang, and Tongyang Li, "Robustness of Quantum Algorithms for Nonconvex Optimization", arXiv:2212.02548, (2022).

[64] Tongyang Li and Ruizhe Zhang, "Quantum Speedups of Optimizing Approximately Convex Functions with Applications to Logarithmic Regret Stochastic Convex Bandits", arXiv:2209.12897, (2022).

[65] Simon Apers and Sander Gribling, "Quantum speedups for linear programming via interior point methods", arXiv:2311.03215, (2023).

[66] Aaron Sidford and Chenyi Zhang, "Quantum speedups for stochastic optimization", arXiv:2308.01582, (2023).

[67] Nikhil S. Mande and Ronald de Wolf, "Tight Bounds for Quantum Phase Estimation and Related Problems", arXiv:2305.04908, (2023).

[68] Simon Apers, "Quantum Walk Sampling by Growing Seed Sets", arXiv:1904.11446, (2019).

The above citations are from Crossref's cited-by service (last updated successfully 2024-02-26 07:15:52) and SAO/NASA ADS (last updated successfully 2024-02-26 07:15:52). The list may be incomplete as not all publishers provide suitable and complete citation data.