Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2411.14224 · IEEE International Conference on Rebooting Computing (ICRC)

Thermodynamic Algorithms for Quadratic Programming

Patryk Lipka-Bartosik, Kaelan Donatella, Maxwell Aifer, Denis Melanson, Martí Perarnau-Llobet, Nicolas Brunner, Patrick J. Coles

Published Dec 16, 2024• 6 citations
arXivHTMLPDF

Abstract

Thermodynamic computing has emerged as a promising paradigm for accelerating computation by harnessing the thermalization properties of physical systems. This work introduces a novel approach to solving quadratic programming problems using thermodynamic hardware. By incorporating a thermodynamic subroutine for solving linear systems into the interior-point method, we present a hybrid digital-analog algorithm that outperforms traditional digital algorithms in terms of speed. Notably, we achieve a polynomial asymptotic speedup compared to conventional digital approaches. Additionally, we simulate the algorithm for a support vector machine and predict substantial practical speedups with only minimal degradation in solution quality. Finally, we detail how our method can be applied to portfolio optimization and the simulation of nonlinear resistive networks.

DOI
10.1109/icrc64395.2024.10937015

Related papers

Optimal Scaling Quantum Interior Point Method for Linear Optimization

Mohammadhossein Mohammadisiahroudi, Zeguan Wu, Pouya Sampourmahani +2 more

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.

quant-pharXiv:2512.04510•IEEE International Conference on Quantum Computing and Engineering (QCE)•Dec 5, 2025•1 citation

Quantum Interior Point Methods: A Review of Developments and An Optimally Scaling Framework

Mohammadhossein Mohammadisiahroudi, Zeguan Wu, Pouya Sampourmahani +2 more

The growing demand for solving large-scale, data-intensive linear and conic optimization problems, particularly in applications such as artificial intelligence and machine learning, has highlighted the limitations of classical interior point methods (IPMs). Despite their favorable polynomial-time convergence, conventional IPMs often suffer from high per-iteration computational costs, especially for dense problem instances. Recent advances in quantum computing, particularly quantum linear system solvers, offer promising avenues to accelerate the most computationally intensive steps of IPMs. However, practical challenges such as quantum error, hardware noise, and sensitivity to poorly conditioned systems remain significant obstacles. In response, a series of Quantum IPMs (QIPMs) has been developed to address these challenges, incorporating techniques such as feasibility maintenance, iterative refinement, and preconditioning. In this work, we review this line of research with a focus on our recent contributions, including an almost-exact QIPM framework. This hybrid quantum-classical approach constructs and solves the Newton system entirely on a quantum computer, while performing solution updates classically. Crucially, all matrix-vector operations are executed on quantum hardware, enabling the method to achieve an optimal worst-case scalability w.r.t dimension, surpassing the scalability of existing classical and quantum IPMs.

quant-pharXiv:2512.06224•Dec 9, 2025•1 citation

An Inexact Feasible Quantum Interior Point Method for Linearly Constrained Quadratic Optimization

Zeguan Wu, Mohammadhossein Mohammadisiahroudi, Brandon Augustino +2 more

Quantum linear system algorithms (QLSAs) have the potential to speed up algorithms that rely on solving linear systems. Interior point methods (IPMs) yield a fundamental family of polynomial-time algorithms for solving optimization problems. IPMs solve a Newton linear system at each iteration to compute the search direction; thus, QLSAs can potentially speed up IPMs. Due to the noise in contemporary quantum computers, quantum-assisted IPMs (QIPMs) only admit an inexact solution to the Newton linear system. Typically, an inexact search direction leads to an infeasible solution, so, to overcome this, we propose an inexact-feasible QIPM (IF-QIPM) for solving linearly constrained quadratic optimization problems. We also apply the algorithm to ℓ1-norm soft margin support vector machine (SVM) problems, and demonstrate that our algorithm enjoys a speedup in the dimension over existing approaches. This complexity bound is better than any existing classical or quantum algorithm that produces a classical solution.

arXiv:2301.05357•Entropy•Feb 10, 2023•20 citations

Exploring Quantum Annealing Techniques for Financial Portfolio Optimization

UMA RAMAN, Saif O. Husain, Venkata Siva Bathula +3 more

Quantum annealing has emerged as a promising computational paradigm for solving large-scale combinatorial optimization problems that are intractable for classical algorithms. Financial portfolio optimization, which involves balancing expected returns against risk under multiple practical constraints, represents one of the most challenging optimization tasks in quantitative finance. Traditional approaches based on mean-variance theory, heuristic meta-optimization, and classical quadratic programming often struggle to scale efficiently as the dimensionality of assets and constraints increases. This study explores the application of quantum annealing techniques to financial portfolio optimization by formulating the problem as a quadratic unconstrained binary optimization model suitable for quantum hardware. The paper provides a systematic mapping of portfolio objectives and constraints into the Ising Hamiltonian framework and analyzes how quantum tunneling and probabilistic state transitions can enhance convergence toward near-global optima. Comparative insights between classical solvers and quantum annealing-based approaches are discussed in terms of solution quality, computational efficiency, and scalability. Furthermore, the study highlights current hardware limitations, embedding challenges, and noise effects that influence optimization performance. The findings indicate that quantum annealing offers substantial potential for accelerating portfolio optimization in high-dimensional financial systems, particularly in scenarios involving complex constraints and dynamic market conditions, thereby establishing a foundation for future quantum-driven financial decision-support systems.

International Conference on Innovative Practices in Technology and Management (ICIPTM)•Feb 19, 2026•0 citations

Thermodynamic linear algebra

Maxwell Aifer, Kaelan Donatella, Max Hunter Gordon +5 more

Abstract Linear algebra is central to many algorithms in engineering, science, and machine learning; hence, accelerating it would have tremendous economic impact. Quantum computing has been proposed for this purpose, although the resource requirements are far beyond current technological capabilities. We consider an alternative physics-based computing paradigm based on classical thermodynamics, to provide a near-term approach to accelerating linear algebra. At first sight, thermodynamics and linear algebra seem to be unrelated fields. Here, we connect solving linear algebra problems to sampling from the thermodynamic equilibrium distribution of a system of coupled harmonic oscillators. We present simple thermodynamic algorithms for solving linear systems of equations, computing matrix inverses, and computing matrix determinants. Under reasonable assumptions, we rigorously establish asymptotic speedups for our algorithms, relative to digital methods, that scale linearly in matrix dimension. Our algorithms exploit thermodynamic principles like ergodicity, entropy, and equilibration, highlighting the deep connection between these two seemingly distinct fields, and opening up algebraic applications for thermodynamic computers.

arXiv:2308.05660•npj Unconventional Computing•Nov 5, 2024•47 citations

Hamiltonian simulation with explicit formulas for Digital-Analog Quantum Computing

Mikel Garcia-de-Andoin, Thorge Müller, Gonzalo Camacho

Digital-analog is a quantum computational paradigm that employs the natural interaction Hamiltonian of a system as the entangling resource, combined with single qubit gates, to implement universal quantum operations. As in the case of its digital gate-based counterpart, designing digital-analog circuits that employ optimal quantum resources often requires an exceedingly large classical computational time. In this work we find a suboptimal solution to this exponentially large problem, showing that it can be solved within polynomial computational time. In particular, we provide an exact solution for the problem of expressing arbitrary two-body Hamiltonians as the sum of local unitary transformations of an arbitrary Ising Hamiltonian, with the total number of required terms being at most quadratic in system size. This allows us to design a digital-analog simulation protocol that avoids employing numerical optimization over a large parameter space at the preprocessing stage, minimizing computational resources and allowing for further scaling.

quant-pharXiv:2511.11404•Physical Review A•Nov 17, 2025•2 citations
Thermodynamic computing has emerged as a promising paradigm for accelerating computation by harnessing the thermalization properties of physical systems. This work introduces a novel approach to solving quadratic programming problems using thermodynamic hardware. By incorporating a thermodynamic subroutine for solving linear systems into the interior-point method, we present a hybrid digital-analog algorithm that outperforms traditional digital algorithms in terms of speed. Notably, we achieve a polynomial asymptotic speedup compared to conventional digital approaches. Additionally, we simulate the algorithm for a support vector machine and predict substantial practical speedups with only minimal degradation in solution quality. Finally, we detail how our method can be applied to portfolio optimization and the simulation of nonlinear resistive networks.
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 O(n2)\mathcal{O}(n^2)O(n2) 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 O(n1.5κAlog⁡(1ε))\mathcal{O}(n^{1.5} κ_A \log(\frac{1}ε))O(n1.5κA​log(ε1​)) queries to QRAM and O(n2log⁡(1ε))\mathcal{O}(n^2 \log(\frac{1}ε))O(n2log(ε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.
The growing demand for solving large-scale, data-intensive linear and conic optimization problems, particularly in applications such as artificial intelligence and machine learning, has highlighted the limitations of classical interior point methods (IPMs). Despite their favorable polynomial-time convergence, conventional IPMs often suffer from high per-iteration computational costs, especially for dense problem instances. Recent advances in quantum computing, particularly quantum linear system solvers, offer promising avenues to accelerate the most computationally intensive steps of IPMs. However, practical challenges such as quantum error, hardware noise, and sensitivity to poorly conditioned systems remain significant obstacles. In response, a series of Quantum IPMs (QIPMs) has been developed to address these challenges, incorporating techniques such as feasibility maintenance, iterative refinement, and preconditioning. In this work, we review this line of research with a focus on our recent contributions, including an almost-exact QIPM framework. This hybrid quantum-classical approach constructs and solves the Newton system entirely on a quantum computer, while performing solution updates classically. Crucially, all matrix-vector operations are executed on quantum hardware, enabling the method to achieve an optimal worst-case scalability w.r.t dimension, surpassing the scalability of existing classical and quantum IPMs.
Quantum linear system algorithms (QLSAs) have the potential to speed up algorithms that rely on solving linear systems. Interior point methods (IPMs) yield a fundamental family of polynomial-time algorithms for solving optimization problems. IPMs solve a Newton linear system at each iteration to compute the search direction; thus, QLSAs can potentially speed up IPMs. Due to the noise in contemporary quantum computers, quantum-assisted IPMs (QIPMs) only admit an inexact solution to the Newton linear system. Typically, an inexact search direction leads to an infeasible solution, so, to overcome this, we propose an inexact-feasible QIPM (IF-QIPM) for solving linearly constrained quadratic optimization problems. We also apply the algorithm to ℓ1-norm soft margin support vector machine (SVM) problems, and demonstrate that our algorithm enjoys a speedup in the dimension over existing approaches. This complexity bound is better than any existing classical or quantum algorithm that produces a classical solution.
Quantum annealing has emerged as a promising computational paradigm for solving large-scale combinatorial optimization problems that are intractable for classical algorithms. Financial portfolio optimization, which involves balancing expected returns against risk under multiple practical constraints, represents one of the most challenging optimization tasks in quantitative finance. Traditional approaches based on mean-variance theory, heuristic meta-optimization, and classical quadratic programming often struggle to scale efficiently as the dimensionality of assets and constraints increases. This study explores the application of quantum annealing techniques to financial portfolio optimization by formulating the problem as a quadratic unconstrained binary optimization model suitable for quantum hardware. The paper provides a systematic mapping of portfolio objectives and constraints into the Ising Hamiltonian framework and analyzes how quantum tunneling and probabilistic state transitions can enhance convergence toward near-global optima. Comparative insights between classical solvers and quantum annealing-based approaches are discussed in terms of solution quality, computational efficiency, and scalability. Furthermore, the study highlights current hardware limitations, embedding challenges, and noise effects that influence optimization performance. The findings indicate that quantum annealing offers substantial potential for accelerating portfolio optimization in high-dimensional financial systems, particularly in scenarios involving complex constraints and dynamic market conditions, thereby establishing a foundation for future quantum-driven financial decision-support systems.
Abstract Linear algebra is central to many algorithms in engineering, science, and machine learning; hence, accelerating it would have tremendous economic impact. Quantum computing has been proposed for this purpose, although the resource requirements are far beyond current technological capabilities. We consider an alternative physics-based computing paradigm based on classical thermodynamics, to provide a near-term approach to accelerating linear algebra. At first sight, thermodynamics and linear algebra seem to be unrelated fields. Here, we connect solving linear algebra problems to sampling from the thermodynamic equilibrium distribution of a system of coupled harmonic oscillators. We present simple thermodynamic algorithms for solving linear systems of equations, computing matrix inverses, and computing matrix determinants. Under reasonable assumptions, we rigorously establish asymptotic speedups for our algorithms, relative to digital methods, that scale linearly in matrix dimension. Our algorithms exploit thermodynamic principles like ergodicity, entropy, and equilibration, highlighting the deep connection between these two seemingly distinct fields, and opening up algebraic applications for thermodynamic computers.
Digital-analog is a quantum computational paradigm that employs the natural interaction Hamiltonian of a system as the entangling resource, combined with single qubit gates, to implement universal quantum operations. As in the case of its digital gate-based counterpart, designing digital-analog circuits that employ optimal quantum resources often requires an exceedingly large classical computational time. In this work we find a suboptimal solution to this exponentially large problem, showing that it can be solved within polynomial computational time. In particular, we provide an exact solution for the problem of expressing arbitrary two-body Hamiltonians as the sum of local unitary transformations of an arbitrary Ising Hamiltonian, with the total number of required terms being at most quadratic in system size. This allows us to design a digital-analog simulation protocol that avoids employing numerical optimization over a large parameter space at the preprocessing stage, minimizing computational resources and allowing for further scaling.