用改进的HHL算法解决量子态制备瓶颈，保住指数加速优势
Solving the encoding bottleneck: of the HHL algorithm, by the HHL algorithm
- 用修改版HHL算法近似制备初始量子态，耗时仅O(poly(log N))
- 将状态准备时间从O(N)降至对数级，保住了原算法的指数加速
- 不仅适用于原HHL，还可独立用于其他需快速制备量子态的任务
Harrow-Hassidim-Lloyd（HHL）算法在求解量子线性系统问题上具有指数加速优势，但其速度提升面临若干挑战，其中编码瓶颈尤为突出——即高效制备初始量子态。现有方法精确制备任意N维量子态通常需要O(N)时间，这会破坏算法的加速优势。本文提出，通过采用略微修改的HHL算法，可将状态近似制备时间压缩至O(poly(log N))。将该方法应用于原始HHL算法的初始态准备，可有效维持其指数加速特性。此外，该方案也可作为独立工具，服务于其他需要快速量子态制备的应用场景。
原文摘要 · Abstract (English)
The Harrow-Hassidim-Lloyd (HHL) algorithm offers exponential speedup for solving the quantum linear-system problem. But some caveats for the speedup could be hard to met. One of the difficulties is the encoding bottleneck, i.e., the efficient preparation of the initial quantum state. To prepare an arbitrary $N$-dimensional state exactly, existing state-preparation approaches generally require a runtime of $O(N)$, which will ruin the speedup of the HHL algorithm. Here we show that the states can be prepared approximately with a runtime of $O(poly(\log N))$ by employing a slightly modified version of the HHL algorithm itself. Thus, applying this approach to prepare the initial state of the original HHL algorithm can preserve the exponential speedup advantage. It can also serve as a standalone solution for other applications demanding fast state preparation.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。