A Quantum Dual Logarithmic Barrier Method for Linear Optimization

References

• Apers S, Gribling S (2023) Quantum speedups for linear programming via interior point methods. Preprint, submitted November 6, https://arxiv.org/abs/2311.03215.Google Scholar
• Applegate D, Hinder O, Lu H, Lubin M (2023) Faster first-order primal-dual methods for linear programming using restarts and sharpness. Math. Programming 201(1):133–184.Google Scholar
• Augustino B, Nannicini G, Terlaky T, Zuluaga LF (2023) Quantum interior point methods for semidefinite optimization. Quantum 7:1110.Google Scholar
• Bellavia S, Gondzio J, Porcelli M (2019) An inexact dual logarithmic barrier method for solving sparse semidefinite programs. Math. Programming 178:109–143.Google Scholar
• Casares PA, Martin-Delgado MA (2020) A quantum interior-point predictor–corrector algorithm for linear programming. J. Phys. A Math. Theoret. 53(44):445305.Google Scholar
• Chakraborty S, Gilyén A, Jeffery S (2018) The power of block-encoded matrix powers: Improved regression techniques via faster Hamiltonian simulation. Preprint, submitted April 5, https://arxiv.org/abs/1804.01973.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.Google Scholar
• Cohen MB, Lee YT, Song Z (2021) Solving linear programs in the current matrix multiplication time. J. ACM 68(1):1–39.Google Scholar
• Costa PC, An D, Sanders YR, Su Y, Babbush R, Berry DW (2022) Optimal scaling quantum linear-systems solver via discrete adiabatic theorem. PRX Quantum 3(4):040303.Google Scholar
• Eifler L, Nicolas-Thouvenin J, Gleixner A (2024) Combining precision boosting with LP iterative refinement for exact linear optimization. INFORMS J. Comput. 37(4):933–944. Google Scholar
• Farhi E, Goldstone J, Gutmann S (2014) A quantum approximate optimization algorithm. Preprint, submitted November 14, https://arxiv.org/abs/1411.4028.Google Scholar
• Gilyén A (2019) Quantum singular value transformation & its algorithmic applications. Unpublished PhD thesis, University of Amsterdam, Netherlands.Google Scholar
• Gilyén A, Su Y, Low GH, Wiebe N (2019) Quantum singular value transformation and beyond: Exponential improvements for quantum matrix arithmetics. Charikar M, Cohen E, eds. Proc. 51st Annual ACM SIGACT Sympos. Theory Comput. (Association for Computing Machinery, New York), 193–204.Google Scholar
• Giovannetti V, Lloyd S, Maccone L (2008) Quantum random access memory. Phys. Rev. Lett. 100(16):160501.Google Scholar
• Gleixner AM, Steffy DE, Wolter K (2016) Iterative refinement for linear programming. INFORMS J. Comput. 28(3):449–464.Link, Google Scholar
• Harrow AW, Hassidim A, Lloyd S (2009) Quantum algorithm for linear systems of equations. Phys. Rev. Lett. 103(15):150502.Google Scholar
• Karmarkar N (1984) A new polynomial-time algorithm for linear programming. Combinatorica 4:373–395.Google Scholar
• Kerenidis I, Prakash A (2016) Quantum recommendation systems. Preprint, submitted March 29, https://arxiv.org/abs/1603.08675.Google Scholar
• Kerenidis I, Prakash A (2020) A quantum interior point method for LPs and SDPs. ACM Trans. Quantum Comput. 1(1):1–32.Google Scholar
• Lee YT, Sidford A (2015) Efficient inverse maintenance and faster algorithms for linear programming. Guruswami V, ed. IEEE 56th Annual Sympos. Foundations Comput. Sci. (IEEE Computer Society, Washington, DC), 230–249.Google Scholar
• Lu H (2024) First-order methods for linear programming. Preprint, submitted March 21, https://arxiv.org/abs/2403.14535.Google Scholar
• Mohammadisiahroudi M (2024) Quantum computing and optimization methods. PhD thesis, Lehigh University, Bethlehem, PA.Google Scholar
• Mohammadisiahroudi M, Fakhimi R, Terlaky T (2024) Efficient use of quantum linear system algorithms in inexact infeasible IPMs for linear optimization. J. Optim. Theory Appl. 202(1):146–183.Google Scholar
• Mohammadisiahroudi M, Augustino B, Sampourmahani P, Terlaky T (2025a) Quantum computing inspired iterative refinement for semidefinite optimization. Math. Programming, ePub ahead of print January 11, https://doi.org/10.1007/s10107-024-02183-z.Google Scholar
• Mohammadisiahroudi M, Fakhimi R, Wu Z, Terlaky T (2025b) An inexact feasible interior point method for linear optimization with high adaptability to quantum computers. SIAM J. Optim. 35(4):2203–2233.Google Scholar
• Mohammadisiahroudi M, Wu Z, Augustino B, Carr A, Terlaky T (2025c) Improvements to quantum interior point method for linear optimization. ACM Trans. Quantum Comput. 6(1):1–24.Google Scholar
• Monteiro RD, O’Neal JW (2003) Convergence analysis of a long-step primal-dual infeasible interior-point LP algorithm based on iterative linear solvers. Georgia Institute of Technology, Atlanta. https://optimization-online.org/2003/10/768/.Google Scholar
• Nannicini G (2024) Fast quantum subroutines for the simplex method. Oper. Res. 72(2):763–780.Link, Google Scholar
• Nesterov Y, Nemirovskii A (1994) Interior-Point Polynomial Algorithms in Convex Programming (SIAM, Philadelphia).Google Scholar
• Roos C, Terlaky T, Vial JP (1997) Theory and Algorithms for Linear Optimization: An Interior Point Approach (John Wiley & Sons, Chichester, UK).Google Scholar
• Shor PW (1994) Algorithms for quantum computation: Discrete logarithms and factoring. Goldwasser S, ed. Proc. 35th Annual Sympos. Foundations Comput. Sci. (IEEE Computer Society, Washington, DC), 124–134.Google Scholar
• Tu Y, Dubynskyi M, Mohammadisiahroudi M, Riashchentceva E, Cheng J, Ryashchentsev D, Terlaky T, Liu J (2025) Towards identifying possible fault-tolerant advantage of quantum linear system algorithms in terms of space, time and energy. Preprint, submitted February 16, https://arxiv.org/abs/2502.11239.Google Scholar
• Vaidya PM (1989) Speeding-up linear programming using fast matrix multiplication. Galil Z, ed. 30th Annual Sympos. Foundations Comput. Sci. (IEEE Computer Society, Washington, DC), 332–337.Google Scholar
• van Apeldoorn J, Cornelissen A, Gilyén A, Nannicini G (2023) Quantum tomography using state-preparation unitaries. Bansal N, Nagarajan V, eds. Proc. 2023 Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1265–1318.Google Scholar
• van den Brand J (2020) A deterministic linear program solver in current matrix multiplication time. Farach-Colton M, ed. Proc. 14th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 259–278.Google Scholar
• van den Brand J, Lee YT, Sidford A, Song Z (2020) Solving tall dense linear programs in nearly linear time. Makarychev K, Makarychev Y, Tulsiani M, Kamath G, Chuzhoy J, eds. Proc. 52nd Annual ACM SIGACT Sympos. Theory Comput. (Association for Computing Machinery, New York), 775–788.Google Scholar
• Weber T, Sager S, Gleixner A (2019) Solving quadratic programs to high precision using scaled iterative refinement. Math. Programming Comput. 11(3):421–455.Google Scholar
• Wu Z, Mohammadisiahroudi M, Augustino B, Yang X, Terlaky T (2023) An inexact feasible quantum interior point method for linearly constrained quadratic optimization. Entropy 25(2):330.Google Scholar