Quantum Multigrid Algorithm for Finite Element Problems

O. M. Raisuddin, S. De · 2024 · arXiv

| 编号 QC020 | 主题 量子算法工具箱 | 链接 arXiv:2404.07466 |

摘要

摘要保留原文（英文）

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

Quantum linear system algorithms (QLSAs) can provide exponen?al speedups for the solu?on of linear systems, but the growth of the condi?on number for finite element problems can eliminate the exponen?al speedup. QLSAs are also incapable of using an ini?al guess of a solu?on to improve upon it. To circumvent these issues, we present a Quantum Mul?grid Algorithm (qMG) for the itera?ve solu?on of linear systems by applying the sequence of mul?grid opera?ons on a quantum state. Given an ini?al guess with error ${ϵ}_0,$ qMG can produce a vector encoding the en?re sequence of mul?grid iterates with the final iterate having a rela?ve error $\widetilde{ϵ}=ϵ/{ϵ}_0,$ as a subspace of the final quantum state, with exponen?al advantage in $O\left(\mathrm{polylog}\frac{N}{\widetilde{ϵ}}\right)$ ?me using $O\left(\mathrm{polylog}\frac{N}{\widetilde{ϵ}}\right)$ qubits. Although extrac?ng the final iterate from the sequence is efficient, extrac?ng the sequence of iterates from the final quantum state can be inefficient. We provide an analysis of the complexity of the method along with numerical analysis.

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