A quantum dual logarithmic barrier method for linear optimization
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913621689237504 |
|---|---|
| author | Wu, Zeguan Sampourmahani, Pouya Mohammadisiahroudi, Mohammadhossein Terlaky, Tamás |
| author_facet | Wu, Zeguan Sampourmahani, Pouya Mohammadisiahroudi, Mohammadhossein Terlaky, Tamás |
| contents | Quantum computing has the potential to speed up some optimization methods. One can use quantum computers to solve linear systems via Quantum Linear System Algorithms (QLSAs). QLSAs can be used as a subroutine for algorithms that require solving linear systems, such as the dual logarithmic barrier method (DLBM) for solving linear optimization (LO) problems. In this paper, we use a QLSA to solve the linear systems arising in each iteration of the DLBM. To use the QLSA in a hybrid setting, we read out quantum states via a tomography procedure which introduces considerable error and noise. Thus, this paper first proposes an inexact-feasible variant of DLBM for LO problems and then extends it to a quantum version. Our quantum approach has quadratic convergence toward the central path with inexact directions and we show that this method has the best-known $\mathcal{O}(\sqrt{n} \log (n μ_0 /ζ))$ iteration complexity, where $n$ is the number of variables, $μ_0$ is the initial duality gap, and $ζ$ is the desired accuracy. We further use iterative refinement to improve the time complexity dependence on accuracy. For LO problems with quadratically more constraints than variables, the quantum complexity of our method has a sublinear dependence on dimension. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_15977 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A quantum dual logarithmic barrier method for linear optimization Wu, Zeguan Sampourmahani, Pouya Mohammadisiahroudi, Mohammadhossein Terlaky, Tamás Optimization and Control 90C05, 90C51, 81P68 Quantum computing has the potential to speed up some optimization methods. One can use quantum computers to solve linear systems via Quantum Linear System Algorithms (QLSAs). QLSAs can be used as a subroutine for algorithms that require solving linear systems, such as the dual logarithmic barrier method (DLBM) for solving linear optimization (LO) problems. In this paper, we use a QLSA to solve the linear systems arising in each iteration of the DLBM. To use the QLSA in a hybrid setting, we read out quantum states via a tomography procedure which introduces considerable error and noise. Thus, this paper first proposes an inexact-feasible variant of DLBM for LO problems and then extends it to a quantum version. Our quantum approach has quadratic convergence toward the central path with inexact directions and we show that this method has the best-known $\mathcal{O}(\sqrt{n} \log (n μ_0 /ζ))$ iteration complexity, where $n$ is the number of variables, $μ_0$ is the initial duality gap, and $ζ$ is the desired accuracy. We further use iterative refinement to improve the time complexity dependence on accuracy. For LO problems with quadratically more constraints than variables, the quantum complexity of our method has a sublinear dependence on dimension. |
| title | A quantum dual logarithmic barrier method for linear optimization |
| topic | Optimization and Control 90C05, 90C51, 81P68 |
| url | https://arxiv.org/abs/2412.15977 |