Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2021
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2109.08470 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917169047011328 |
|---|---|
| author | Xue, Cheng Wu, Yu-Chun Guo, Guo-Ping |
| author_facet | Xue, Cheng Wu, Yu-Chun Guo, Guo-Ping |
| contents | While quantum computing provides an exponential advantage in solving system of linear equations, there is little work to solve system of nonlinear equations with quantum computing. We propose quantum Newton's method (QNM) for solving $N$-dimensional system of nonlinear equations based on Newton's method. In QNM, we solve the system of linear equations in each iteration of Newton's method with quantum linear system solver. We use a specific quantum data structure and $l_{\infty}$ tomography with sample error $ε_s$ to implement the classical-quantum data conversion process between the two iterations of QNM, thereby constructing the whole process of QNM. The complexity of QNM in each iteration is $O(\log^4N/ε_s^2)$. Through numerical simulation, we find that when $ε_s>>1/\sqrt{N}$, QNM is still effective, so the complexity of QNM is sublinear with $N$, which provides quantum advantage compared with the optimal classical algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2109_08470 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Quantum Newton's method for solving system of nonlinear algebraic equations Xue, Cheng Wu, Yu-Chun Guo, Guo-Ping Quantum Physics While quantum computing provides an exponential advantage in solving system of linear equations, there is little work to solve system of nonlinear equations with quantum computing. We propose quantum Newton's method (QNM) for solving $N$-dimensional system of nonlinear equations based on Newton's method. In QNM, we solve the system of linear equations in each iteration of Newton's method with quantum linear system solver. We use a specific quantum data structure and $l_{\infty}$ tomography with sample error $ε_s$ to implement the classical-quantum data conversion process between the two iterations of QNM, thereby constructing the whole process of QNM. The complexity of QNM in each iteration is $O(\log^4N/ε_s^2)$. Through numerical simulation, we find that when $ε_s>>1/\sqrt{N}$, QNM is still effective, so the complexity of QNM is sublinear with $N$, which provides quantum advantage compared with the optimal classical algorithm. |
| title | Quantum Newton's method for solving system of nonlinear algebraic equations |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2109.08470 |