Fetching the paper…
Reading the bibliography…
There is an increasing interest in quantum algorithms for optimization problems.
Johann Radon, “Mengen konvexer körper, die einen gemeinsamen punkt enthalten,” Mathematische Annalen 83
1921
Earlier work this paper cites.
Branko Grünbaum, “Partitions of mass-distributions and of convex bodies by hyperplanes.” Pacific Journal of Mathematics 10
1960
Earlier work this paper cites.
Anatoly Yur’evich Levin, “An algorithm for minimizing convex functions,” Doklady Akademii Nauk 160
1965
Earlier work this paper cites.
Donald J Newman, “Location of the maximum on unimodal surfaces,” Journal of the ACM (JACM) 12
1965
Earlier work this paper cites.
Beresford N Parlett, “Analysis of algorithms for reflections in bisectors,” SIAM Review 13
1971
Earlier work this paper cites.
George Fix and Richard Heiberger, “An algorithm for the ill-conditioned generalized eigenvalue problem,” SIAM Journal on Numerical Analysis 9
1972
Earlier work this paper cites.
David B Yudin and Arkadii S Nemirovski, “Evaluation of the information complexity of mathematical programming problems,” Ekonomika i Matematicheskie Metody 13
1976
Earlier work this paper cites.
Naum Z Shor, “Cut-off method with space extension in convex programming problems,” Cybernetics 13
1977
Earlier work this paper cites.
Leonid G Khachiyan, “Polynomial algorithms in linear programming,” USSR Computational Mathematics and Mathematical Physics 20
1980
Earlier work this paper cites.
I. Gohberg, P. Lancaster, and L. Rodman, Matrix Polynomials , Classics in Applied Mathematics (Society for Industrial and Applied Mathematics (SIAM, 3600 Market Street, Floor 6, Philadelphia, PA 19104), 1982)
1982
Earlier work this paper cites.
Robert L Smith, “Efficient monte carlo procedures for generating points uniformly distributed over bounded regions,” Operations Research 32
1984
Earlier work this paper cites.
Angelika Bunse-Gerstner, “An algorithm for the symmetric generalized eigenvalue problem,” Linear Algebra and its Applications 58
1984
Earlier work this paper cites.
Prabhakar Raghavan and Clark D. Tompson, “Randomized rounding: A technique for provably good algorithms and algorithmic proofs,” Combinatorica 7
1987
Earlier work this paper cites.
Simon Duane, A.D. Kennedy, Brian J. Pendleton, and Duncan Roweth, “Hybrid monte carlo,” Physics Letters B 195
1987
Earlier work this paper cites.
Zhi-hao Cao, “On a deflation method for the symmetric generalized eigenvalue problem,” Linear Algebra and its Applications 92
1987
Earlier work this paper cites.
Leonid G Khachiyan, Sergei Pavlovich Tarasov, and I. I. Erlikh, “The method of inscribed ellipsoids,” in Soviet Math. Dokl , Vol. 37 (1988) pp. 226–230
1988
Earlier work this paper cites.
Y.E. Nesterov and A.S. Nemirovskii, “Self-concordant functions and polynomial-time methods in convex programming,” (1989), report, Central Economic and Mathematics Institute, USSR Acad. Sci
1989
Earlier work this paper cites.
Pravin M Vaidya, “A new algorithm for minimizing convex functions over convex sets,” in 30th Annual Symposium on Foundations of Computer Science (IEEE Computer Society, 1989) pp. 338–343
1989
Earlier work this paper cites.
James Demmel and Bo Kågström, “The generalized schur decomposition of an arbitrary pencil a– λ \lambda b—robust software with error bounds and applications. part i: theory and algorithms,” ACM Transactions on Mathematical Software (TOMS) 19
1993
Earlier work this paper cites.
David S Atkinson and Pravin M Vaidya, “A cutting plane algorithm for convex programming that uses analytic centers,” Mathematical Programming 69
1995
Earlier work this paper cites.
A Yu Kitaev, “Quantum measurements and the abelian stabilizer problem,” arXiv preprint quant-ph/9511026 (1995)
1995
Earlier work this paper cites.
S.J. Wright, Primal-Dual Interior-Point Methods , Other Titles in Applied Mathematics (Society for Industrial and Applied Mathematics, 1997)
1997
Earlier work this paper cites.
We refer to Chapter 1 of Wright 1997 for an excellent introduction to primal-dual interior-point methods. Due to the reliance of reliance of interior-point methods on solving linear systems, Kerenidis and Prakash 2020 ; Augustino et al. 2021 ended up with a bound dependent on the condition number κ \kappa of a linear system based on the Karush-Kuhn-Tucker (KKT) conditions. As is well known ( Wright 1997 , p. 215) , this goes to infinity for all instances, by the design of the method, which may be not ideal in practice. Furthermore, there is the issue of the HHL algorithm Harrow et al. 2009 providing the solution of the linear system only as a quantum state, whereas the interior-point method Kerenidis and Prakash 2020 ; Augustino et al. 2021 needs a classical update. The HHL hence needs to be run many times and the quantum state measured many times, to estimate the classical update
1997
Earlier work this paper cites.
László Lovász, “Hit-and-run mixes fast,” Mathematical Programming 86
1999
Earlier work this paper cites.
Brian Borchers, “Sdplib 1.2, a library of semidefinite programming test problems,” Optimization Methods and Software 11
1999
Earlier work this paper cites.
Francoise Tisseur, “Backward error and condition of polynomial eigenvalue problems,” Linear Algebra and Appl 309
2000
Earlier work this paper cites.
Hans D Mittelmann, “An independent benchmarking of sdp and socp solvers,” Mathematical Programming 95
2003
Earlier work this paper cites.
Horst Alzer, “Some beta-function inequalities,” Proceedings. Section A, Mathematics-The Royal Society of Edinburgh 133
2003
Earlier work this paper cites.
Stephen P Boyd and Lieven Vandenberghe, Convex optimization (Cambridge university press, 2004)
2004
Earlier work this paper cites.
Dimitris Bertsimas and Santosh Vempala, “Solving convex programs by random walks,” Journal of the ACM (JACM) 51
2004
Earlier work this paper cites.
Giuseppe Calafiore, “Random walks for probabilistic robustness,” in 2004 43rd IEEE Conference on Decision and Control (CDC)(IEEE Cat. No. 04CH37601) , Vol. 5 (IEEE, 2004) pp. 5316–5321
2004
Earlier work this paper cites.
Craig Lucas, Algorithms for Cholesky and QR Factorizations, and the Semidefinite Generalized Eigenvalue Problem , Ph.D. thesis , The University of Manchester (2004)
2004
Earlier work this paper cites.
Santosh Vempala, “Geometric random walks: a survey,” Combinatorial and computational geometry 52
2005
Earlier work this paper cites.
Michael Berhanu, The polynomial eigenvalue problem , Ph.D. thesis, University of Manchester (2005)
2005
Earlier work this paper cites.
Boris Teodorovich Polyak and Pavel Sergeevich Shcherbakov, “The d-decomposition technique for linear matrix inequalities,” Automation and Remote Control 67
2006
Cited alongside, same era.
László Lovász and Santosh Vempala, “Fast algorithms for logconcave functions: Sampling, rounding, integration and optimization,” in 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06) (IEEE, 2006) pp. 57–68
2006
Cited alongside, same era.
Jean-Daniel Boissonnat and Monique Teillaud, Effective computational geometry for curves and surfaces (Springer, 2006)
2006
Cited alongside, same era.
Pawel Wocjan and Shengyu Zhang, “Several natural BQP-Complete problems,” arXiv e-prints , quant-ph/0606179 (2006), arXiv:quant-ph/0606179 [quant-ph]
2006
Cited alongside, same era.
D. Mackey, Niloufer Mackey, Christian Mehl, and Volker Mehrmann, “Vector spaces of linearizations for matrix polynomials,” SIAM Journal on Matrix Analysis and Applications 28
2019
Later among the works it cites.
Marc Ganzhorn, Daniel J. Egger, Panagiotis Kl. Barkoutsos, Pauline Ollitrault, Gian Salis, Nikolaj Moll, Andreas Fuhrer, Peter Mueller, Stefan Woerner, Ivano Tavernelli, and Stefan Filipp, “Gate-efficient simulation of molecular eigenstates on a quantum computer,” Phys. Rev. Applied 11
2019
Later among the works it cites.
Vojtech Havlicek, Antonio D. Corcoles, Kristan Temme, Aram W. Harrow, Abhinav Kandala, Jerry M. Chow, and Jay M. Gambetta, “Supervised learning with quantum-enhanced feature spaces,” Nature 567
2019
Later among the works it cites.
Fernando GSL 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) (Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019)
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
2006
Cited alongside, same era.
Nicholas J Higham, D Steven Mackey, and Françoise Tisseur, “The conditioning of linearizations of matrix polynomials,” SIAM Journal on Matrix Analysis and Applications 28
2006
Cited alongside, same era.
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
2007
Cited alongside, same era.
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 (2007) pp. 227–236
2007
Cited alongside, same era.
Giuseppe C. Calafiore and Fabrizio Dabbene, “A probabilistic analytic center cutting plane method for feasibility of uncertain lmis,” Automatica 43
2007
Cited alongside, same era.
Luis A Rademacher, “Approximating the centroid is hard,” in Proceedings of the twenty-third annual symposium on Computational geometry (2007) pp. 302–305
2007
Cited alongside, same era.
Elad Hazan, “Sparse approximate solutions to semidefinite programs,” in Latin American symposium on theoretical informatics (Springer, 2008) pp. 306–316
2008
Cited alongside, same era.
F. Dabbene, P. Shcherbakov, and B. T. Polyak, “A randomized cutting plane scheme with geometric convergence: Probabilistic analysis and sdp applications,” in 2008 47th IEEE Conference on Decision and Control (2008) pp. 3044–3049
2008
Cited alongside, same era.
2019
Later among the works it cites.
Joran van Apeldoorn and András Gilyén, “Improvements in quantum sdp-solving with applications,” in Proceedings of 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019 (2019)
2019
Later among the works it cites.
András Gilyén, Srinivasan Arunachalam, and Nathan Wiebe, “Optimizing quantum optimization algorithms via faster quantum gradient computation,” in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SIAM, 2019) pp. 1425–1444
2019
Later among the works it cites.
Augustin Chevallier, Random walks for estimating densities of states and the volume of convex bodies in high dimensional spaces , Theses , Université Côte d’Azur (2019)
2019
Later among the works it cites.
Diego Armentano and Carlos Beltran, “The polynomial eigenvalue problem is well conditioned for random inputs,” SIAM Journal on Matrix Analysis and Applications 40
2019
Later among the works it cites.
Carlos Beltrán and Khazhgali Kozhasov, “The real polynomial eigenvalue problem is well conditioned on the average,” Foundations of Computational Mathematics , 1–19 (2019)
2019
Later among the works it cites.
H. Abraham et al., “Qiskit: An open-source framework for quantum computing,” (2019)
2019
Later among the works it cites.
B. O’Donoghue, E. Chu, N. Parikh, and S. Boyd, “SCS: Splitting conic solver, version 2.1.4,” https://github.com/cvxgrp/scs (2019)
2019
Later among the works it cites.
Anirudha Majumdar, Georgina Hall, and Amir Ali Ahmadi, “Recent scalability improvements for semidefinite programming with applications in machine learning, control, and robotics,” Annual Review of Control, Robotics, and Autonomous Systems 3
2020
Later among the works it cites.
Haotian Jiang, Tarun Kathuria, Yin Tat Lee, Swati Padmanabhan, and Zhao Song, “A faster interior point method for semidefinite programming,” in 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) (IEEE, 2020) pp. 910–918
2020
Later among the works it cites.
APS Mosek, “The mosek optimization software,” (2020), online at http://www.mosek.com
2020
Later among the works it cites.
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 (2020)
2020
Later among the works it cites.
Iordanis Kerenidis and Anupam Prakash, “A quantum interior point method for lps and sdps,” ACM Transactions on Quantum Computing 1
2020
Later among the works it cites.
Joran Van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf, “Quantum SDP-solvers: Better upper and lower bounds,” Quantum 4
2020
Later among the works it cites.
Shouvanik Chakrabarti, Andrew M Childs, Tongyang Li, and Xiaodi Wu, “Quantum algorithms and lower bounds for convex optimization,” Quantum 4
2020
Later among the works it cites.
As it has been shown in ( Van Apeldoorn et al. 2020 , Appendix E) , in the MWU algorithm, r R ϵ \frac{rR}{\epsilon} should be seen as an important parameter, as one can trade-off dependence on one of the three individual parameters for the dependence on the others
2020
Later among the works it cites.
Joran van Apeldoorn, A quantum view on convex optimization , Ph.D. thesis, University of Amsterdam Institute for Logic, Language and Computation (ILLC) (2020)
2020
Later among the works it cites.
Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf, “Convex optimization using quantum oracles,” Quantum 4
2020
Later among the works it cites.
Haotian Jiang, Yin Tat Lee, Zhao Song, and Sam Chiu-wai Wong, “An improved cutting plane method for convex optimization, convex-concave games, and its applications,” in Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (2020) pp. 944–953
2020
Later among the works it cites.
2020
Later among the works it cites.
Jan van den Brand, “A deterministic linear program solver in current matrix multiplication time,” in Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SIAM, 2020) pp. 259–278
2020
Later among the works it cites.
Jeffrey B Parker and Ilon Joseph, “Quantum phase estimation for a class of generalized eigenvalue problems,” Physical Review A 102
2020
Later among the works it cites.
An exponential quantum speed-up claimed by Lloyd et al. 2014 only under very particular circumstances, incl. low-rank matrices and strong assumptions on the initialization, has since been disputed Tang 2018 ; Chia et al. 2020 ; Tang 2021 ; Chepurko et al. 2020 . We do not claim an exponential quantum speed-up is available
2020
Later among the works it cites.
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,” in Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing , STOC 2020 (Association for Computing Machinery, New York, NY, USA, 2020) p. 387–400
2020
Later among the works it cites.
2020
Later among the works it cites.
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 (ITCS 2021) , Leibniz International Proceedings in Informatics (LIPIcs), Vol. 185, edited by James R. Lee (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2021) pp. 53:1–53:20
2021
Closest in time.
Brandon Augustino, Giacomo Nannicini, Tamás Terlaky, and Luis F Zuluaga, “An inexact-feasible quantum interior point method for semidefinite optimization,” (2021)
2021
Closest in time.
Mohammad Hossein Mohammadi Siahroudi, Ramin Fakhimi, and Tamás Terlaky, “Efficient use of quantum linear system algorithms in interior point methods for linear optimization,” (2021)
2021
Closest in time.
2021
Closest in time.
Daniel J Egger, Jakub Mareček, and Stefan Woerner, “Warm-starting quantum optimization,” Quantum 5
2021
Closest in time.
Ewin Tang, “Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions,” Phys. Rev. Lett. 127
2021
Closest in time.