Quantum algorithm for linear systems of equations

A. W. Harrow, A. Hassidim, S. Lloyd · 2009 · Phys. Rev. Lett.

| 编号 QR047 | 主题 算法与批判 | 链接 arXiv:0811.3171 |

摘要

摘要保留原文（英文）

摘要取自 arXiv / 出版方元数据，未作翻译，以保证与原文一致。

Solving linear systems of equations is a common problem that arises both on its own and as a subroutine in more complex problems: given a matrix $A$ and a vector $\vec{b}$ , find a vector $\vec{x}$ such that $A\overrightarrow{x}=\overrightarrow{b}$ . We consider the case where one doesn’t need to know the solution $\vec{x}$ itself, but rather an approximation of the expectation value of some operator associated with $\vec{x}$ , e.g., ${\vec{x}}^{†}M\vec{x}$ for some matrix $M$ . In this case, when $A$ is sparse, $N\times N$ and has condition number $\kappa$ , classical algorithms can find $\vec{x}$ and estimate ${\vec{x}}^{†}M\vec{x}$ in $\tilde{O}(N\sqrt{\kappa })$ time. Here, we exhibit a quantum algorithm for this task that runs in p $\mathrm{Jy}(\log N,\kappa )$ time, an exponential improvement over the best classical algorithm.

本站词条在引用该文献时，会以 wikilink（sources/QR047）链接到本页；右侧「反向链接」面板自动列出所有引用它的词条。