Fetching the paper…
Reading the bibliography…
We propose a novel quantum algorithm for solving linear optimization problems by quantum-mechanical simulation of the central path.
Asymptotically efficient quantum Karatsuba multiplication, 2019
Craig Gidney · 1904
Earlier work this paper cites.
Quantum algorithms for zero-sum games, 2019
Joran van Apeldoorn and András Gilyén · 1904
Earlier work this paper cites.
Programming in a linear structure
George B. Dantzig · 1948
Earlier work this paper cites.
Principles of linear programming: With particular reference to the double gradient form of the logarithmic potential method
Ragnar Anton Kittil Frisch · 1954
Earlier work this paper cites.
The generalized simplex method for minimizing a linear form under linear inequality restraints
George B. Dantzig, Alex Orden, Philip Wolfe, et al · 1955
Earlier work this paper cites.
The logarithmic potential method of convex programming
Ragnar Anton Kittil Frisch · 1955
Earlier work this paper cites.
La résolution des problèmes de programme linéaire par la méthode du potentiel logarithmique
Ragnar Anton Kittil Frisch · 1956
Earlier work this paper cites.
Quantum Mechanics
Albert Messiah · 1958
Earlier work this paper cites.
The sequential unconstrained minimization technique for nonlinear programing, a primal-dual method
Anthony V. Fiacco and Garth P. McCormick · 1964
Earlier work this paper cites.
Iterative solution of problems of linear and quadratic programming
I.I. Dikin · 1967
Earlier work this paper cites.
Nonlinear programming: sequential unconstrained minimization techniques
Anthony V. Fiacco and Garth P. McCormick · 1968
Earlier work this paper cites.
On the convergence of an iteration process
I.I. Dikin · 1974
Earlier work this paper cites.
Polynomial algorithms in linear programming
Leonid G. Khachiyan · 1980
Earlier work this paper cites.
A new polynomial-time algorithm for linear programming
Narendra Karmarkar · 1984
Earlier work this paper cites.
Linear programming and the Newton barrier flow
Kurt M. Anstreicher · 1988
Earlier work this paper cites.
A general approach to polynomial-time algorithms design for convex programming
Yurii E. Nesterov and Arkadi Nemirovskii · 1988
Earlier work this paper cites.
A polynomial-time algorithm, based on Newton’s method, for linear programming
James Renegar · 1988
Earlier work this paper cites.
The nonlinear geometry of linear programming. I. Affine and projective scaling trajectories
Dave A. Bayer and Jeffrey C. Lagarias · 1989
Earlier work this paper cites.
The nonlinear geometry of linear programming. II. Legendre transform coordinates and central trajectories
Dave A. Bayer and Jeffrey C. Lagarias · 1989
Earlier work this paper cites.
An algorithm for solving linear programming problems in 𝒪 ( n 3 L ) \mathcal{O}(n^{3}L) operations
Clóvis C. Gonzaga · 1989
Earlier work this paper cites.
Pathways to the optimal set in linear programming
Nimrod Megiddo · 1989
Earlier work this paper cites.
Hamiltonian structure of dynamical systems which solve linear programming problems
Leonid Faybusovich · 1991
Earlier work this paper cites.
Interior-Point Polynomial Algorithms in Convex Programming
Yurii E. Nesterov and Arkadi Nemirovskii · 1994
Earlier work this paper cites.
An 𝒪 ( n L ) \mathcal{O}(\sqrt{n}L) -iteration homogeneous and self-dual linear programming algorithm
Yinyu Ye, Michael J. Todd, and Shinji Mizuno · 1994
Earlier work this paper cites.
A Hamiltonian formalism for optimization problems
Leonid Faybusovich · 1995
Earlier work this paper cites.
Quantum networks for elementary arithmetic operations
Vlatko Vedral, Adriano Barenco, and Artur Ekert · 1996
Earlier work this paper cites.
Primal-Dual Interior-Point Methods
Stephen J. Wright · 1997
Cited alongside, same era.
On growth of Sobolev norms in linear Schrödinger equations with smooth time dependent potential
Jean Bourgain · 1999
Cited alongside, same era.
Quantum computation by adiabatic evolution, 2000
Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser · 2000
Cited alongside, same era.
A mathematical view of interior-point methods in convex optimization
James Renegar · 2001
Cited alongside, same era.
Elementary exponential error estimates for the adiabatic approximation
George A. Hagedorn and Alain Joye · 2002
Cited alongside, same era.
Solving some large scale semidefinite programs via the conjugate residual method
Kim-Chuan Toh and Masakazu Kojima · 2002
Cited alongside, same era.
The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation
Shantanav Chakraborty, András Gilyén, and Stacey Jeffery · 2019
Later among the works it cites.
Linear programming using limited-precision oracles
Ambros M. Gleixner and Daniel E. Steffy · 2020
Later among the works it cites.
A faster interior point method for semidefinite programming
Haotian Jiang, Tarun Kathuria, Yin Tat Lee, Swati Padmanabhan, and Zhao Song · 2020
Later among the works it cites.
A quantum interior point method for LPs and SDPs
Iordanis Kerenidis and Anupam Prakash · 2020
Later among the works it cites.
A deterministic linear program solver in current matrix multiplication time
Jan van den Brand · 2020
Later among the works it cites.
Solving tall dense linear programs in nearly linear time
Jan van den Brand, Yin Tat Lee, Aaron Sidford, and Zhao Song · 2020
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Faster dynamic matrix inverse for faster LPs, 2020
Shunhua Jiang, Zhao Song, Omri Weinstein, and Hengjie Zhang · 2004
Cited alongside, same era.
Interior Point Methods for Linear Optimization
Cornelis Roos, Tamás Terlaky, and Jean-Phillipe Vial · 2005
Cited alongside, same era.
Quantum algorithm for linear systems of equations
Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd · 2009
Cited alongside, same era.
Interior point algorithms: theory and analysis
Yinyu Ye · 2011
Cited alongside, same era.
Hamiltonian Simulation using linear combinations of unitary operations
Andrew M. Childs and Nathan Wiebe · 2012
Cited alongside, same era.
Improving the accuracy of linear programming solvers with iterative refinement
Ambros M. Gleixner, Daniel E. Steffy, and Kati Wolter · 2012
Cited alongside, same era.
Later among the works it cites.
Solving linear programs in the current matrix multiplication time
Michael B. Cohen, Yin Tat Lee, and Zhao Song · 2021
Later among the works it cites.
Quantum linear system solver based on time-optimal adiabatic quantum computing and quantum approximate optimization algorithm
Dong An and Lin Lin · 2022
Later among the works it cites.
Quantum resources required to block-encode a matrix of classical data
B. David Clader, Alexander M. Dalzell, Nikitas Stamatopoulos, Grant Salton, Mario Berta, and William J. Zeng · 2022
Later among the works it cites.
Quantum simulation of real-space dynamics
Andrew M. Childs, Jiaqi Leng, Tongyang Li, Jin-Peng Liu, and Chenyi Zhang · 2022
Later among the works it cites.
Mohammadhossein Mohammadisiahroudi, Ramin Fakhimi, and Tamás Terlaky · 2022
Later among the works it cites.
Quantum speedups for linear programming via interior point methods
Simon Apers and Sander Gribling · 2023
Closest in time.
Faster first-order primal-dual methods for linear programming using restarts and sharpness
David Applegate, Oliver Hinder, Haihao Lu, and Miles Lubin · 2023
Closest in time.
Quantum interior point methods for semidefinite optimization
Brandon Augustino, Giacomo Nannicini, Tamás Terlaky, and Luis F. Zuluaga · 2023
Closest in time.
Quantum speedups for zero-sum games via improved dynamic Gibbs sampling
Adam Bouland, Yosheb M. Getachew, Yujia Jin, Aaron Sidford, and Kevin Tian · 2023
Closest in time.
End-to-end resource analysis for quantum interior-point methods and portfolio optimization
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, et al · 2023
Closest in time.
Logarithmic-regret quantum learning algorithms for zero-sum games
Minbo Gao, Zhengfeng Ji, Tongyang Li, and Qisheng Wang · 2023
Closest in time.
Quantum Hamiltonian Descent, 2023
Jiaqi Leng, Ethan Hickman, Joseph Li, and Xiaodi Wu · 2023
Closest in time.
A quantum-classical performance separation in nonconvex optimization, 2023
Jiaqi Leng, Yufan Zheng, and Xiaodi Wu · 2023
Closest in time.
Interior point methods with a gradient oracle
Adrian Vladu · 2023
Closest in time.
Computational Guarantees for Restarted PDHG for LP based on “Limiting Error Ratios” and LP Sharpness
Zikai Xiong and Robert Michael Freund · 2023
Closest in time.
Parallel approximate maximum flows in near-linear work and polylogarithmic depth
Arpit Agarwal, Sanjeev Khanna, Huan Li, Prathamesh Patil, Chen Wang, Nathan White, and Peilin Zhong · 2024
Closest in time.
Logarithmic-regret quantum learning algorithms for zero-sum games
Minbo Gao, Zhengfeng Ji, Tongyang Li, and Qisheng Wang · 2024
Closest in time.
Efficient use of quantum linear system algorithms in inexact infeasible ipms for linear optimization
Mohammadhossein Mohammadisiahroudi, Ramin Fakhimi, and Tamás Terlaky · 2024
Closest in time.
An easily computable upper bound on the hoffman constant for homogeneous inequality systems
Javier F. Peña · 2024
Closest in time.