Optimal Scaling Quantum Interior Point Method for Linear Optimization

• URL: http://arxiv.org/abs/2512.04510v2
• Date: Fri, 05 Dec 2025 17:47:12 GMT
• Title: Optimal Scaling Quantum Interior Point Method for Linear Optimization
• Authors: Mohammadhossein Mohammadisiahroudi, Zeguan Wu, Pouya Sampourmahani, Jun-Kai You, Tamás Terlaky,
• Abstract summary: We introduce a novel almost-exact quantum IPM, where the system is constructed and solved on a quantum computer.<n>This framework achieves an optimal worst-case scaling of $mathcalO(n2)$ for fully dense LO problems.<n>Our algorithm has a quantum complexity of $mathcalO(n1.5 _A log1)$ queries to QRAM and $mathcalO(n2 log(frac1)$ classical arithmetic operations.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The emergence of huge-scale, data-intensive linear optimization (LO) problems in applications such as machine learning has driven the need for more computationally efficient interior point methods (IPMs). While conventional IPMs are polynomial-time algorithms with rapid convergence, their per-iteration cost can be prohibitively high for dense large-scale LO problems. Quantum linear system solvers have shown potential in accelerating the solution of linear systems arising in IPMs. In this work, we introduce a novel almost-exact quantum IPM, where the Newton system is constructed and solved on a quantum computer, while solution updates occur on a classical machine. Additionally, all matrix-vector products are performed on the quantum hardware. This hybrid quantum-classical framework achieves an optimal worst-case scaling of $\mathcal{O}(n^2)$ for fully dense LO problems. To ensure high precision, despite the limited accuracy of quantum operations, we incorporate iterative refinement techniques both within and outside the proposed IPM iterations. The proposed algorithm has a quantum complexity of $\mathcal{O}(n^{1.5} κ_A \log(\frac{1}ε))$ queries to QRAM and $\mathcal{O}(n^2 \log(\frac{1}ε))$ classical arithmetic operations. Our method outperforms the worst-case complexity of prior classical and quantum IPMs, offering a significant improvement in scalability and computational efficiency.

Related papers

• Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
  We provide an explicit quantum circuit for block encoding a sparse matrix with a periodic diagonal structure.<n>Various applications for the presented methodology are discussed in the context of solving differential problems.
  arXiv  Detail & Related papers  (2026-02-11T07:24:33Z)
• Reducing the Complexity of Matrix Multiplication to $O(N^2log_2N)$ by an Asymptotically Optimal Quantum Algorithm [3.5649163180026484]
  This work presents a quantum kernel-based matrix multiplication algorithm (QKMM)<n>It achieves anally optimal computational complexity of $ O(N2 log N) $, outperforming the classical optimal complexity of $ O(N2.371552) $.
  arXiv  Detail & Related papers  (2026-02-05T10:58:52Z)
• Classical optimization with imaginary time block encoding on quantum computers: The MaxCut problem [1.354560757162539]
  We develop a new method, called ITE-BE, based on a recent imaginary time algorithm.<n>We demonstrate that our method can be successfully combined with other quantum algorithms.
  arXiv  Detail & Related papers  (2024-11-16T08:17:36Z)
• Optimization by Decoded Quantum Interferometry [38.063836468778895]
  We introduce Decoded Quantum Interferometry (DQI), a quantum algorithm that uses the quantum Fourier transform to reduce optimization problems to decoding problems.<n>For approximating optimal fits over finite fields, DQI achieves a superpolynomial speedup over known classical algorithms.
  arXiv  Detail & Related papers  (2024-08-15T17:47:42Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming [0.0]
  In this work, we integrate the potentials of quantum and classical techniques for optimization. We reduce the problem size according to a linear relaxation such that the reduced problem can be handled by quantum machines of limited size. We present numerous computational results from real quantum hardware.
  arXiv  Detail & Related papers  (2023-02-10T20:12:53Z)
• An Inexact Feasible Quantum Interior Point Method for Linearly Constrained Quadratic Optimization [0.0]
  Quantum linear system algorithms (QLSAs) have the potential to speed up algorithms that rely on solving linear systems. In our work, we propose an Inexact-Feasible QIPM (IF-QIPM) and show its advantage in solving linearly constrained quadratic optimization problems.
  arXiv  Detail & Related papers  (2023-01-13T01:36:13Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Automatic and effective discovery of quantum kernels [41.61572387137452]
  Quantum computing can empower machine learning models by enabling kernel machines to leverage quantum kernels for representing similarity measures between data.<n>We present an approach to this problem, which employs optimization techniques, similar to those used in neural architecture search and AutoML.<n>The results obtained by testing our approach on a high-energy physics problem demonstrate that, in the best-case scenario, we can either match or improve testing accuracy with respect to the manual design approach.
  arXiv  Detail & Related papers  (2022-09-22T16:42:14Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  Quantum approximate optimization algorithms (QAOAs) utilize the power of quantum machines and inherit the spirit of adiabatic evolution. We propose QAOA-in-QAOA ($textQAOA2$) to solve arbitrary large-scale MaxCut problems using quantum machines. Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale optimization problems.
  arXiv  Detail & Related papers  (2022-05-24T03:49:10Z)
• Efficient Use of Quantum Linear System Algorithms in Interior Point Methods for Linear Optimization [0.0]
  We develop an Inexact Infeasible Quantum Interior Point Method to solve linear optimization problems. We also discuss how can we get an exact solution by Iterative Refinement without excessive time of quantum solvers.
  arXiv  Detail & Related papers  (2022-05-02T21:30:56Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time. As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware. We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
  arXiv  Detail & Related papers  (2022-02-17T18:59:20Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.