A Catalyst Framework for the Quantum Linear System Problem via the Proximal Point Algorithm
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918218049781760 |
|---|---|
| author | Kim, Junhyung Lyle Chia, Nai-Hui Kyrillidis, Anastasios |
| author_facet | Kim, Junhyung Lyle Chia, Nai-Hui Kyrillidis, Anastasios |
| contents | Solving systems of linear equations is a fundamental problem, but it can be computationally intensive for classical algorithms in high dimensions. Existing quantum algorithms can achieve exponential speedups for the quantum linear system problem (QLSP) in terms of the problem dimension, but the advantage is bottlenecked by condition number of the coefficient matrix. In this work, we propose a new quantum algorithm for QLSP inspired by the classical proximal point algorithm (PPA). Our proposed method can be viewed as a meta-algorithm that allows inverting a modified matrix via an existing \texttt{QLSP\_solver}, thereby directly approximating the solution vector instead of approximating the inverse of the coefficient matrix. By carefully choosing the step size $η$, the proposed algorithm can effectively precondition the linear system to mitigate the dependence on condition numbers that hindered the applicability of previous approaches. Importantly, this is the first iterative framework for QLSP where a tunable parameter $η$ and initialization $x_0$ allows controlling the trade-off between the runtime and approximation error. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_13879 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Catalyst Framework for the Quantum Linear System Problem via the Proximal Point Algorithm Kim, Junhyung Lyle Chia, Nai-Hui Kyrillidis, Anastasios Quantum Physics Data Structures and Algorithms Machine Learning Optimization and Control Solving systems of linear equations is a fundamental problem, but it can be computationally intensive for classical algorithms in high dimensions. Existing quantum algorithms can achieve exponential speedups for the quantum linear system problem (QLSP) in terms of the problem dimension, but the advantage is bottlenecked by condition number of the coefficient matrix. In this work, we propose a new quantum algorithm for QLSP inspired by the classical proximal point algorithm (PPA). Our proposed method can be viewed as a meta-algorithm that allows inverting a modified matrix via an existing \texttt{QLSP\_solver}, thereby directly approximating the solution vector instead of approximating the inverse of the coefficient matrix. By carefully choosing the step size $η$, the proposed algorithm can effectively precondition the linear system to mitigate the dependence on condition numbers that hindered the applicability of previous approaches. Importantly, this is the first iterative framework for QLSP where a tunable parameter $η$ and initialization $x_0$ allows controlling the trade-off between the runtime and approximation error. |
| title | A Catalyst Framework for the Quantum Linear System Problem via the Proximal Point Algorithm |
| topic | Quantum Physics Data Structures and Algorithms Machine Learning Optimization and Control |
| url | https://arxiv.org/abs/2406.13879 |