Fetching the paper…
Reading the bibliography…
We describe a quantum algorithm based on an interior point method for solving a linear program with $n$ inequality constraints on $d$ variables.
Quantum algorithms for zero-sum games, 2019
Joran van Apeldoorn and András Gilyén · 1904
Earlier work this paper cites.
Solving linear programs with sqrt(rank) linear system solves, 2019
Yin Tat Lee and Aaron Sidford · 1910
Earlier work this paper cites.
Finite dimensional subspaces of L p L_{p}
D. Lewis · 1978
Earlier work this paper cites.
A polynomial algorithm in linear programming
L. G. Khachiyan · 1979
Earlier work this paper cites.
Extensions of lipschitz mappings into a hilbert space
William B Johnson and Joram Lindenstrauss · 1984
Earlier work this paper cites.
A new polynomial-time algorithm for linear programming
N. Karmarkar · 1984
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.
Interior-Point Polynomial Algorithms in Convex Programming
Yurii Nesterov and Arkadii Nemirovskii · 1993
Earlier work this paper cites.
A technique for bounding the number of iterations in path following algorithms
Pravin M. Vaidya and David S. Atkinson · 1993
Earlier work this paper cites.
Las vegas algorithms for linear and integer programming when the dimension is small
Kenneth L Clarkson · 1995
Earlier work this paper cites.
A fast quantum mechanical algorithm for database search
Lov K. Grover · 1996
Earlier work this paper cites.
A new algorithm for minimizing convex functions over convex sets
Pravin M. Vaidya · 1996
Earlier work this paper cites.
Volumetric path following algorithms for linear programming
Kurt M. Anstreicher · 1997
Earlier work this paper cites.
Tight bounds on quantum searching
Michel Boyer, Gilles Brassard, Peter Høyer, and Alain Tapp · 1998
Earlier work this paper cites.
A Mathematical View of Interior-Point Methods in Convex Optimization
James Renegar · 2001
Earlier work this paper cites.
Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
Daniel A Spielman and Shang-Hua Teng · 2004
Earlier work this paper cites.
S. Cliff Liu, Zhao Song, Hengjie Zhang, Lichen Zhang, and Tianyi Zhou · 2009
Earlier work this paper cites.
Randomized algorithms for matrices and data
Michael W. Mahoney · 2011
Earlier work this paper cites.
Graph sparsification by effective resistances
Daniel A. Spielman and Nikhil Srivastava · 2011
Earlier work this paper cites.
User-friendly tail bounds for sums of random matrices
Joel A. Tropp · 2011
Cited alongside, same era.
A strong direct product theorem for quantum query complexity
Troy Lee and Jérémie Roland · 2013
Cited alongside, same era.
Iterative row sampling
Mu Li, Gary L Miller, and Richard Peng · 2013
Cited alongside, same era.
Uniform sampling for matrix approximation
Michael B Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, and Aaron Sidford · 2015
Cited alongside, same era.
ℓ p \ell_{p} row sampling by Lewis weights
Michael B Cohen and Richard Peng · 2015
Cited alongside, same era.
A faster cutting plane method and its implications for combinatorial and convex optimization
Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong · 2015
Cited alongside, same era.
Quantum algorithms for second-order cone programming and support vector machines
Iordanis Kerenidis, Anupam Prakash, and Dániel Szilágyi · 2021
Later among the works it cites.
L1 Regression with Lewis Weights Subsampling
Aditya Parulekar, Advait Parulekar, and Eric Price · 2021
Later among the works it cites.
Minimum cost flows, MDPs, and ℓ 1 \ell_{1} -regression in nearly linear time for dense instances
Jan van den Brand, Yin Tat Lee, Yang P Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang · 2021
Later among the works it cites.
Quantum speedup for graph sparsification, cut approximation, and Laplacian solving
Simon Apers and Ronald de Wolf · 2022
Later among the works it cites.
Near-optimal quantum algorithms for multivariate mean estimation
Arjan Cornelissen, Yassine Hamoudi, and Sofiene Jerbi · 2022
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Quantum speedup of monte carlo methods
Ashley Montanaro · 2015
Cited alongside, same era.
Faster Algorithms for Convex and Combinatorial Optimization
Yin Tat Lee · 2016
Cited alongside, same era.
Minimum-volume ellipsoids: Theory and algorithms
Michael J Todd · 2016
Cited alongside, same era.
Quantum speed-ups for solving semidefinite programs
F. L. Brandao and K. M. Svore · 2017
Cited alongside, same era.
Low-rank approximation and regression in input sparsity time
Kenneth L. Clarkson and David P. Woodruff · 2017
Cited alongside, same era.
Optimality of the johnson-lindenstrauss lemma
Kasper Green Larsen and Jelani Nelson · 2017
Cited alongside, same era.
Near-optimal quantum algorithms for multivariate mean estimation
Arjan Cornelissen, Yassine Hamoudi, and Sofiene Jerbi · 2022
Later among the works it cites.
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 JA Schuetz, Fernando GSL Brandão, Helmut G Katzgraber, and William J Zeng · 2022
Later among the works it cites.
Computing lewis weights to high precision
Maryam Fazel, Yin Tat Lee, Swati Padmanabhan, and Aaron Sidford · 2022
Later among the works it cites.
A faster quantum algorithm for semidefinite programming via robust ipm framework
Baihe Huang, Shunhua Jiang, Zhao Song, Runzhou Tao, and Ruizhe Zhang · 2022
Later among the works it cites.
Improved iteration complexities for overconstrained p -norm regression
Arun Jambulapati, Yang P. Liu, and Aaron Sidford · 2022
Later among the works it cites.
Efficient use of quantum linear system algorithms in interior point methods for linear optimization
Mohammadhossein Mohammadisiahroudi, Ramin Fakhimi, and Tamás Terlaky · 2022
Later among the works it cites.
Quantum optimization: Potential, challenges, and the path forward, 2023
Amira Abbas, Andris Ambainis, Brandon Augustino, Andreas Bärtschi, Harry Buhrman, Carleton Coffrin, Giorgio Cortiana, Vedran Dunjko, Daniel J. Egger, Bruce G. Elmegreen, Nicola Franco, Filippo Fratini, Bryce Fuller, Julien Gacon, Constantin Gonciulea, Sander Gribling, Swati Gupta, Stuart Hadfield, Raoul Heese, Gerhard Kircher, Thomas Kleinert, Thorsten Koch, Georgios Korpas, Steve Lenk, Jakub Marecek, Vanio Markov, Guglielmo Mazzola, Stefano Mensa, Naeimeh Mohseni, Giacomo Nannicini, Corey O’Meara, Elena Peña Tapia, Sebastian Pokutta, Manuel Proissl, Patrick Rebentrost, Emre Sahin, Benjamin C. B. Symons, Sabine Tornow, Victor Valls, Stefan Woerner, Mira L. Wolf-Bauwens, Jon Yard, Sheir Yarkoni, Dirk Zechiel, Sergiy Zhuk, and Christa Zoufal · 2023
Closest in time.
Quantum Algorithms for Symmetric Cones
Brandon Augustino · 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.
Zhao Song, Junze Yin, and Ruizhe Zhang · 2023
Closest in time.
On computing approximate Lewis weights
Simon Apers, Sander Gribling, and Aaron Sidford · 2024
Closest in time.
Quantum speedup for spectral approximation of Kronecker products
Yeqi Gao, Zhao Song, and Ruizhe Zhang · 2024
Closest in time.