Solving the semidefinite relaxation of QUBOs in matrix multiplication time, and faster with a quantum computer
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916779275583488 |
|---|---|
| author | Augustino, Brandon Nannicini, Giacomo Terlaky, Tamás Zuluaga, Luis |
| author_facet | Augustino, Brandon Nannicini, Giacomo Terlaky, Tamás Zuluaga, Luis |
| contents | Recent works on quantum algorithms for solving semidefinite optimization (SDO) problems have leveraged a quantum-mechanical interpretation of positive semidefinite matrices to develop methods that obtain quantum speedups with respect to the dimension $n$ and number of constraints $m$. While their dependence on other parameters suggests no overall speedup over classical methodologies, some quantum SDO solvers provide speedups in the low-precision regime. We exploit this fact to our advantage, and present an iterative refinement scheme for the Hamiltonian Updates algorithm of Brandão et al. (Quantum 6, 625 (2022)) to exponentially improve the dependence of their algorithm on precision. As a result, we obtain a classical algorithm to solve the semidefinite relaxation of Quadratic Unconstrained Binary Optimization problems (QUBOs) in matrix multiplication time. Provided access to a quantum read/classical write random access memory (QRAM), a quantum implementation of our algorithm exhibits a worst case running time of $\mathcal{O} \left(ns + n^{1.5} \cdot \text{polylog} \left(n, \| C \|_F, \frac{1}ε \right) \right)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2301_04237 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Solving the semidefinite relaxation of QUBOs in matrix multiplication time, and faster with a quantum computer Augustino, Brandon Nannicini, Giacomo Terlaky, Tamás Zuluaga, Luis Quantum Physics Optimization and Control 68Q1, 90C22 Recent works on quantum algorithms for solving semidefinite optimization (SDO) problems have leveraged a quantum-mechanical interpretation of positive semidefinite matrices to develop methods that obtain quantum speedups with respect to the dimension $n$ and number of constraints $m$. While their dependence on other parameters suggests no overall speedup over classical methodologies, some quantum SDO solvers provide speedups in the low-precision regime. We exploit this fact to our advantage, and present an iterative refinement scheme for the Hamiltonian Updates algorithm of Brandão et al. (Quantum 6, 625 (2022)) to exponentially improve the dependence of their algorithm on precision. As a result, we obtain a classical algorithm to solve the semidefinite relaxation of Quadratic Unconstrained Binary Optimization problems (QUBOs) in matrix multiplication time. Provided access to a quantum read/classical write random access memory (QRAM), a quantum implementation of our algorithm exhibits a worst case running time of $\mathcal{O} \left(ns + n^{1.5} \cdot \text{polylog} \left(n, \| C \|_F, \frac{1}ε \right) \right)$. |
| title | Solving the semidefinite relaxation of QUBOs in matrix multiplication time, and faster with a quantum computer |
| topic | Quantum Physics Optimization and Control 68Q1, 90C22 |
| url | https://arxiv.org/abs/2301.04237 |