Fast Quantum Subroutines for the Simplex Method

References

• Ambainis A (2004) Quantum search algorithms. ACM SIGACT News 35(2):22–35.Crossref, Google Scholar
• Arora S, Kale S (2016) A combinatorial, primal-dual approach to semidefinite programs. J. ACM 63(2):12.Crossref, Google Scholar
• Augustino B, Nannicini G, Terlaky T, Zuluaga L (2021) Quantum interior point methods for semidefinite optimization. Preprint, submitted, December 11, https://arxiv.org/abs/2112:06025.Google Scholar
• Babbush R, McClean JR, Newman M, Gidney C, Boixo S, Neven H (2021) Focus beyond quadratic speedups for error-corrected quantum advantage. PRX Quantum 2(1):010103.Crossref, Google Scholar
• Bennett CH, Bernstein E, Brassard G, Vazirani U (1997) Strengths and weaknesses of quantum computing. SIAM J. Comput. 26(5):1510–1523.Crossref, Google Scholar
• Bertsimas D, Tsitsiklis J (1997) Introduction to Linear Optimization (Athena Scientific, Belmont, MA).Google Scholar
• Borgwardt KH (1982) The average number of pivot steps required by the simplex-method is polynomial. Zeitschrift Oper. Res. 26(1):157–177.Crossref, Google Scholar
• Brandao FG, Svore KM (2017) Quantum speed-ups for solving semidefinite programs. Proc. IEEE 58th Annual Sympos. on Foundations of Comput. Sci. (IEEE, New York), 415–426.Google Scholar
• Brassard G, Hoyer P, Mosca M, Tapp A (2002) Quantum amplitude amplification and estimation. Contemporary Math. 305:53–74.Crossref, Google Scholar
• Casares PAM, Martin-Delgado MA (2020) A quantum interior-point predictor–corrector algorithm for linear programming. J. Phys. A 53(44):445305.Crossref, Google Scholar
• Chakraborty S, Gilyén A, Jeffery S (2019) The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation Proc. 46th Internat. Colloquium Automata, Languages, Programming, vol. 132 of Leibniz International Proceedings in Informatics (Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany), 33:1–33:14.Google Scholar
• Childs AM, Kothari R, Somma RD (2017) Quantum algorithm for systems of linear equations with exponentially improved dependence on precision. SIAM J. Comput. 46(6):1920–1950.Crossref, Google Scholar
• Chvátal V (1983) Linear Programming (W. H. Freeman, New York).Google Scholar
• Clader BD, Jacobs BC, Sprouse CR (2013) Preconditioned quantum linear system algorithm. Phys. Rev. Lett. 110(25):250504.Crossref, Google Scholar
• Dadush D, Huiberts S (2018) A friendly smoothed analysis of the simplex method. Proc. 50th Annual ACM SIGACT Sympos. on Theory of Comput. (ACM, New York), 390–403.Google Scholar
• Durr C, Hoyer P (1996) A quantum algorithm for finding the minimum. Preprint, submitted July 18, https://arxiv.org/abs/quant-ph/9607014.Google Scholar
• Forrest JJ, Goldfarb D (1992) Steepest-edge simplex algorithms for linear programming. Math. Programming 57(1-3):341–374.Crossref, Google Scholar
• Gärtner B, Kaibel V (2007) Two new bounds for the random-edge simplex-algorithm. SIAM J. Discrete Math. 21(1):178–190.Crossref, Google Scholar
• Gill PE, Murray W, Saunders MA, Wright MH (1989) A practical anti-cycling procedure for linearly constrained optimization. Math. Programming 45(1):437–474.Crossref, Google Scholar
• Gilyén A, Su Y, Low GH, Wiebe N (2019) Quantum singular value transformation and beyond: Exponential improvements for quantum matrix arithmetics. Proc. 51st Annual ACM SIGACT Sympos. on Theory of Comput. (ACM, New York), 193–204.Google Scholar
• Giovannetti V, Lloyd S, Maccone L (2008) Quantum random access memory. Phys. Rev. Lett. 100(16):160501.Crossref, Google Scholar
• Grigoriadis MD, Khachiyan LG (1995) A sublinear-time randomized approximation algorithm for matrix games. Oper. Res. Lett. 18(2):53–58.Crossref, Google Scholar
• Grover LK (1996) A fast quantum mechanical algorithm for database search. Proc. 28th Annual ACM Sympos. on Theory of Comput. (ACM, New York), 212–219.Google Scholar
• Grover L, Rudolph T (2002) Creating superpositions that correspond to efficiently integrable probability distributions. Preprint, submitted August 2, https://arxiv.org/abs/quant-ph/0208112.Google Scholar
• Harrow AW, Hassidim A, Lloyd S (2009) Quantum algorithm for linear systems of equations. Phys. Rev. Lett. 103(15):150502.Crossref, Google Scholar
• Høyer P, Mosca M, De Wolf R (2003) Quantum search on bounded-error inputs. Proc. Internat. Colloquium on Automata, Languages, and Programming (Springer, Berlin), 291–299.Google Scholar
• Huangfu Q (2013) High performance simplex solver. PhD thesis, The University of Edinburgh, Edinburgh, UK.Google Scholar
• Kalai G (1992) A subexponential randomized simplex algorithm. Proc. 24th Annual ACM Sympos. on Theory of Comput., 475–482.Google Scholar
• Kerenidis I, Prakash A (2020) A quantum interior point method for LPs and SDPs. ACM Trans. Quantum Comput. 1(1):1–32.Crossref, Google Scholar
• Klee V, Minty GJ (1972) How good is the simplex algorithm. Inequalities 3(3):159–175.Google Scholar
• Kuczyński J, Woźniakowski H (1992) Estimating the largest eigenvalue by the power and Lanczos algorithms with a random start. SIAM J. Matrix Anal. Appl. 13(4):1094–1122.Crossref, Google Scholar
• Lübbecke ME, Desrosiers J (2005) Selected topics in column generation. Oper. Res. 53(6):1007–1023.Link, Google Scholar
• Matoušek J, Sharir M, Welzl E (1996) A subexponential bound for linear programming. Algorithmica 16(4):498–516.Crossref, Google Scholar
• Nannicini G (2020) An introduction to quantum computing, without the physics. SIAM Rev. 62(4):936–981.Google Scholar
• Nannicini G (2021) Fast quantum subroutines for the simplex method. Singh M, Williamson DP, eds. Proc. 22nd IPCO Conf., Lecture Notes in Computer Science (Springer, Berlin).Google Scholar
• Nielsen MA, Chuang I (2002) Quantum Computation and Quantum Information (Cambridge University Press, Cambridge, UK).Google Scholar
• Sanders YR, Berry DW, Costa PC, Tessler LW, Wiebe N, Gidney C, Neven H, et al. (2020) Compilation of fault-tolerant quantum heuristics for combinatorial optimization. PRX Quantum 1(2):020312.Crossref, Google Scholar
• Spielman DA, Teng SH (2004) Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. J. ACM 51(3):385–463.Crossref, Google Scholar
• van Apeldoorn J, Gilyén A (2019a) Improvements in quantum SDP-solving with applications. Baier C, Chatzigiannakis I, Flocchini P, Leonardi S, eds. Proc. 46th Internat. Colloquium on Automata, Languages, and Programming, vol. 132 of Leibniz International Proceedings in Informatics (Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany), 99:1–99:15.Google Scholar
• van Apeldoorn J, Gilyén A (2019b) Quantum algorithms for zero-sum games. Preprint, submitted April 5, https://arxiv.org/abs/1904.03180.Google Scholar
• van Apeldoorn J, Gilyén A, Gribling S, de Wolf R (2017) Quantum SDP-solvers: Better upper and lower bounds. Proc. IEEE 58th Annual Sympos. on Foundations of Comput. Sci. (IEEE, New York), 403–414.Google Scholar
• Yuster R, Zwick U (2005) Fast sparse matrix multiplication. ACM Trans. Algorithms 1(1):2–13.Crossref, Google Scholar