⚛️ quantum physics

A quantum central path algorithm for linear optimization

The paper proposes a novel quantum algorithm that solves linear optimization problems by simulating the central path via nonlinear complementarity equations, achieving $\varepsilon$ -optimality with improved query and gate complexities dependent on the problem size and sparsity.

Original authors: Brandon Augustino, Jiaqi Leng, Jialu Bao, Giacomo Nannicini, Tamás Terlaky, Xiaodi Wu

Published 2026-10-30

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Brandon Augustino, Jiaqi Leng, Jialu Bao, Giacomo Nannicini, Tamás Terlaky, Xiaodi Wu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Optimization is the mathematical art of finding the best possible solution to a problem, whether that means routing a delivery truck through the most efficient traffic, balancing a financial portfolio, or designing a stable bridge. For decades, the most powerful tools for solving these problems have been interior point methods. These algorithms do not jump straight to the answer; instead, they follow a winding, invisible trail known as the central path. Imagine a hiker navigating a mountain range: rather than climbing every peak or descending into every valley, the hiker stays on a specific ridge that leads directly to the lowest point. In the world of linear optimization, this ridge is a smooth curve defined by a set of equations that balance the constraints of the problem. Classical computers trace this path by taking small, calculated steps, solving a complex linear equation at every single turn to determine the next move. While effective, this step-by-step approach can become incredibly slow and resource-heavy as the problems grow larger, requiring the computer to perform millions of calculations just to inch closer to the solution.

A team of researchers has now proposed a fundamentally different way to travel this path, one that bypasses the step-by-step calculations entirely by using the unique laws of quantum mechanics. In a new study, they describe a quantum algorithm that treats the central path not as a series of discrete steps to be solved, but as a physical landscape that can be traversed in a single, continuous motion. Instead of solving equations to find the next point on the path, the algorithm simulates the behavior of a quantum particle moving through a specially designed energy field. This field is constructed so that its lowest energy state, known as the ground state, naturally settles exactly where the optimal solution to the problem lies. By preparing a quantum system in this state and guiding it along the path, the researchers show that the system can arrive at the solution without the iterative back-and-forth that slows down classical computers.

The core of this new method, which the authors call the Quantum Central Path Method, relies on a concept called Hamiltonian simulation. In quantum physics, a Hamiltonian is an operator that represents the total energy of a system, combining both its motion and its position within a potential field. The researchers designed a specific Hamiltonian where the "potential energy" part of the equation is shaped like the central path itself. When the quantum system is in its lowest energy state, its probability distribution is concentrated right on top of the optimal solution. The challenge, however, is that the shape of this energy landscape changes as the algorithm moves closer to the solution. To navigate this, the team developed a two-stage schedule. First, they move the system along the path while keeping the energy landscape relatively broad, allowing the quantum state to flow smoothly from the starting point to the vicinity of the solution. In the second stage, they tighten the landscape, squeezing the quantum state into a sharp, precise peak that corresponds to the exact answer.

This approach offers a significant advantage over previous attempts to use quantum computers for optimization. Earlier quantum algorithms tried to speed up the individual steps of the classical method, essentially asking a quantum computer to solve the linear equations faster. However, those methods still required the computer to take the same number of steps as a classical one, and they often relied on a theoretical memory system called quantum random access memory, which does not yet exist in a practical form. The new method avoids this dependency entirely. It does not try to accelerate a single step; instead, it replaces the entire iterative process with a single quantum evolution. The researchers proved that this algorithm can find a solution to a linear optimization problem with a specific level of precision using a number of operations that scales efficiently with the size of the problem. Crucially, this efficiency holds even without the use of quantum random access memory, making the approach potentially viable for future hardware that relies on standard quantum gates.

To verify that their theoretical framework works in practice, the researchers ran a numerical demonstration on a standard laptop. They took a small, simple optimization problem and reduced the complex, high-dimensional quantum equations down to a two-dimensional version that could be visualized. The results showed the probability density of the quantum state, which looked like a cloud of fog, starting broad and centered on the initial point. As the simulation progressed and the parameters were adjusted, the cloud narrowed and shifted, following the curved path toward the optimal solution. By the end of the simulation, the cloud had collapsed into a tight, bright spot exactly where the correct answer was located. This visual confirmation demonstrated that the quantum state could indeed track the central path and concentrate on the solution as predicted by the theory.

The implications of this work extend beyond just solving linear equations faster. The study establishes a new connection between the mathematical theory of interior point methods and the physical simulation of quantum systems. It suggests that optimization problems can be viewed as dynamical systems that evolve over time, rather than static puzzles to be solved by iteration. While the current algorithm is a theoretical proposal and has not yet been run on a large-scale quantum computer, the mathematical proofs and the successful small-scale simulation provide a strong foundation. The researchers note that their framework could potentially be adapted to more complex types of optimization, such as those involving semidefinite programming or second-order cone constraints. By showing that a quantum computer can traverse the central path in a single, coherent motion, this work opens a new avenue for solving some of the most difficult computational problems of our time, moving away from the limitations of classical iteration toward a more natural, quantum way of finding the best answer.

Technical Summary: A Quantum Central Path Algorithm for Linear Optimization

Problem Statement
The paper addresses the problem of solving Linear Optimization (LO) problems of the form $\min c^\top x$ subject to $Ax \ge b, x \ge 0$ , and its associated dual. While classical Interior Point Methods (IPMs) are the state-of-the-art for solving these problems, they rely on iterative Newton steps that require solving large linear systems (the Newton linear system) at each iteration. Existing Quantum Interior Point Methods (QIPMs) attempt to accelerate this process by using Quantum Linear System Algorithms (QLSAs) to solve these linear systems. However, current QIPMs suffer from two primary limitations: (1) they typically require the Quantum Random Access Memory (QRAM) model, which is often considered impractical for near-term devices; and (2) they remain iterative, inheriting the $O(\sqrt{n} \log(1/\varepsilon))$ iteration complexity of classical IPMs, and rely on expensive quantum state tomography to extract classical solutions.

Methodology
The authors propose a novel approach called the Quantum Central Path Method (QCPM). Unlike QIPMs, which quantize the steps of a classical algorithm, QCPM quantizes the dynamics of the central path itself. The methodology proceeds as follows:

Hamiltonian Formulation: The authors construct a family of time-dependent Hamiltonian operators, $H(\mu, h)$ , defined over the positive orthant. The Hamiltonian is a Schrödinger operator consisting of a kinetic energy term and a potential energy term:
$H(\mu, h) = -\frac{h^2}{2} \nabla^2 + \Phi_\mu(z)$
Here, $\mu$ is the central path parameter (related to the duality gap), and $h$ acts as a scaling parameter analogous to Planck's constant. The potential function $\Phi_\mu(z)$ is derived from a self-concordant barrier function (specifically, a quadratically continued logarithm) and is designed such that its global minimum corresponds exactly to the $\mu$ -center on the central path of the LO problem.
Ground State Encoding: The core theoretical insight is that the ground state (the eigenvector with the lowest eigenvalue) of $H(\mu, h)$ encodes a probability distribution centered on the central path. As $\mu \to 0$ , this distribution concentrates around the optimal solution. The parameter $h$ controls the variance of this distribution; decreasing $h$ "squeezes" the wave packet around the solution.
Eigenpath Traversal: Instead of iterating Newton steps, the algorithm traverses the ground state trajectory of the Hamiltonian. The authors employ a two-stage schedule for the parameters $(\mu, h)$ :
- Stage 1 (Transport): $\mu$ decreases from 1 to $\varepsilon$ while $h = \mu$ . This moves the center of the ground state along the central path.
- Stage 2 (Squeezing): $\mu$ is fixed at $\varepsilon$ , and $h$ is decreased to a target value $h^*$ to narrow the distribution around the $\varepsilon$ -optimal solution.
  This schedule is constructed to ensure that successive ground states have a large overlap ( $> 1/\sqrt{3}$ ), satisfying the conditions for efficient eigenpath traversal algorithms (specifically the method by Boixo, Knill, and Somma).
Implementation: The algorithm prepares the initial ground state (corresponding to $\mu=1$ ) and then simulates the Schrödinger dynamics to traverse the path. It utilizes spatial discretization to map the infinite-dimensional operator to a finite-dimensional matrix suitable for gate-based quantum computers. Crucially, the algorithm does not require QRAM; it only requires access to a binary description of the problem data $(A, b, c)$ via an evaluation oracle for the potential function.

Key Contributions

Novel Paradigm: The paper introduces the first quantum algorithm that solves LO by directly simulating the central path via Schrödinger dynamics, rather than quantizing the Newton steps of classical IPMs.
QRAM Independence: The algorithm operates in the standard gate model without requiring QRAM, addressing a major practical bottleneck in previous QIPM proposals.
Non-Iterative Nature: The solution is obtained in a "one-shot" manner by measuring the final quantum state, avoiding the iterative loop and the associated accumulation of errors or the need for repeated tomography found in QIPMs.
Theoretical Guarantees: The authors provide rigorous proofs for the strong convexity of the potential function, the spectral gap of the Hamiltonian, and the concentration of the ground state around the central path.

Results and Complexity
The paper establishes that the QCPM can solve an LO problem with $m$ constraints and $n$ variables to $\varepsilon$ -optimality with the following complexity:

Query Complexity: $\tilde{O}\left((m + n)^{3/2} \varepsilon^{-1} + (m + n)^{1/2} \varepsilon^{-3/2}\right)$ queries to a potential function oracle.
Gate Complexity: $\tilde{O}\left(\left[(m + n)^{3/2} \varepsilon^{-1} + (m + n)^{1/2} \varepsilon^{-3/2}\right] \cdot \text{nnz}(A)\right)$ elementary gates, where $\text{nnz}(A)$ is the number of non-zero elements in the constraint matrix.

The complexity depends on the problem sparsity and the precision $\varepsilon$ , but notably avoids dependence on the condition number of the problem data.

Significance and Claims
The authors claim that this work provides "convincing evidence that an end-to-end quantum speedup for LO might be possible even in the circuit model without QRAM." They emphasize that the QCPM offers a new paradigm for quantum optimization, distinct from the "quantum subroutine" approach of previous QIPMs.

The paper is modest regarding its current standing, noting that:

The resource analysis suggests the algorithm is theoretically sound but may require significant enhancements (particularly regarding error dependence) to be practical on near-term devices.
The algorithm solves the self-dual embedding model of the LO problem, a standard theoretical approach in classical IPMs, rather than the original problem directly, though the authors believe the termination criteria used in classical methods would apply here as well.
While the framework is promising and has no known direct classical analogue, the paper lays the foundations for rigorous analysis rather than claiming immediate practical superiority over the best classical algorithms (which currently run in $\tilde{O}((m+n)^\omega)$ time).
The authors explicitly state they did not attempt to construct a classical analogue of this quantum dynamical system, acknowledging that designing a classical system that tracks the global minimum of a time-varying potential would be a significant challenge.

In summary, the paper presents a theoretical breakthrough in connecting interior point methods with quantum Hamiltonian simulation, offering a potential pathway to quantum speedups for linear optimization that bypasses the limitations of QRAM and iterative tomography.

Technical Summary: A Quantum Central Path Algorithm for Linear Optimization

More like this