Thermodynamic Algorithms for Quadratic Programming
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912128651231232 |
|---|---|
| author | Bartosik, Patryk-Lipka Donatella, Kaelan Aifer, Maxwell Melanson, Denis Perarnau-Llobet, Marti Brunner, Nicolas Coles, Patrick J. |
| author_facet | Bartosik, Patryk-Lipka Donatella, Kaelan Aifer, Maxwell Melanson, Denis Perarnau-Llobet, Marti Brunner, Nicolas Coles, Patrick J. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_14224 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Thermodynamic Algorithms for Quadratic Programming Bartosik, Patryk-Lipka Donatella, Kaelan Aifer, Maxwell Melanson, Denis Perarnau-Llobet, Marti Brunner, Nicolas Coles, Patrick J. Emerging Technologies Statistical Mechanics Optimization and Control 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. |
| title | Thermodynamic Algorithms for Quadratic Programming |
| topic | Emerging Technologies Statistical Mechanics Optimization and Control |
| url | https://arxiv.org/abs/2411.14224 |