Abstract
The Harrow-Hassidim-Lloyd (HHL) algorithm offers exponential speedup forsolving the quantum linear-system problem. But some caveats for the speedupcould 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 generallyrequire 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 algorithmitself. Thus, applying this approach to prepare the initial state of theoriginal HHL algorithm can preserve the exponential speedup advantage. It canalso serve as a standalone solution for other applications demanding rapidstate preparation.