QUANTUM SPEEDUPS FOR LINEAR PROGRAMMING VIA INTERIOR POINT METHODS

doi:10.1137/25M1736098

2026-01-01

PRE

Simon Apers *

Sander Gribling

DOI：10.1137/25M1736098

原文链接

原文求助

摘要

En 中文

我们描述了一种基于内点法的量子算法，用于求解具有n个不等式约束和d个变量的线性规划问题。该算法明确返回一个与最优解误差为ε的可行解，运行时间为root n.poly(d,log(n),log(1/epsilon))，对于高维线性规划问题（即n >> d）具有次线性时间复杂度。我们的算法加速了Lee和Sidford[求解线性规划的Sqrt(rank)线性系统解，2019]中当前最先进内点法的牛顿步。这要求我们高效地近似障碍函数的海森矩阵和梯度，这些是我们的主要贡献。为了近似海森矩阵，我们描述了一种用于高矩阵A的A(T)A谱近似的量子算法。该算法结合了杠杆分数采样和Grover搜索，通过向A进行O(root nd/delta)行查询返回一个δ近似。这推广了Apers和de Wolf[图稀疏化中的早期量子加速，SIAM J. Comput., 51 (2022), pp. 1703-1742]的工作。为了近似梯度，我们使用了Cornelissen、Hamoudi和Jerbi[近最优量子算法用于多元均值估计，2022]最近的多元均值估计量子算法。虽然直接实现会引入对海森矩阵条件数的依赖，但通过使用我们谱近似的量子算法对随机变量进行预条件处理，我们避免了这一问题。

Keyword:

Key words. quantum algorithms

interior point methods

linear programming

spectral approximation

期刊

SIAM Journal on Computing

IF:

1.6

论文数:

被引数:

机构

centre national de la recherche scientifique (cnrs)

学者数:

24.5W

论文数: 18.2W

被引数: 279

Universite Paris Cite

学者数:

8.9W

论文数: 6.3W

被引数: 604

引用论文

Sublinear Time Algorithms

SIAM Journal on Discrete Mathematics

IF0

2011-01-01

OAAI

Ronitt Rubinfeld; Asaf Shapira

Reflections for quantum query algorithms

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms

IF0

2013-12-18

OAAI

Ben W. Reichardt

Graph Sparsification by Effective Resistances

SIAM Journal on Computing

IF0

2011-01-01

OAAI

Daniel A. Spielman; Nikhil Srivastava

Quantum Interior Point Methods for Semidefinite Optimization

Quantum

IF0

2023-09-11

OAAI

Brandon Augustino; Giacomo Nannicini; Tamás Terlaky; Luis F. Zuluaga

Efficient Use of Quantum Linear System Algorithms in Inexact Infeasible IPMs for Linear Optimization 量子线性系统算法在近似不可行内点法线性优化中的高效应用

Journal of Optimization Theory and Applications

IF0

2024-06-23

PREAI

Mohammadhossein Mohammadisiahroudi; Ramin Fakhimi; Tamás Terlaky

Challenges and opportunities in quantum optimization 量子优化的挑战和机遇

Nature Reviews Physics

IF0

2024-10-28

PREAI

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; Víctor Valls; Stefan Woerner; Mira L. Wolf-Bauwens; Jon Yard; Sheir Yarkoni; Dirk Zechiel; Sergiy Zhuk; Christa Zoufal

Optimal (controlled) quantum state preparation and improved unitary synthesis by quantum circuits with any number of ancillary qubits

QUANTUM

IF5.4

2023-03-20

OAAI

Yuan, Pei; Zhang, Shengyu

Quantum algorithms and lower bounds for convex optimization

QUANTUM

IF5.4

2020-01-13

OAAI

Chakrabarti, Shouvanik; Childs, Andrew M.; Li, Tongyang; Wu, Xiaodi