Solving the encoding bottleneck: of the HHL algorithm, by the HHL algorithm
This solves a critical bottleneck for quantum linear-system algorithms, enabling practical exponential speedup in quantum computing applications.
The paper tackles the encoding bottleneck in the HHL algorithm, which requires efficient preparation of initial quantum states, by showing that states can be prepared approximately with a runtime of O(poly(log N)) using a modified HHL algorithm, preserving the exponential speedup.
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.