Solving the encoding bottleneck: of the HHL algorithm, by the HHL algorithm
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Disease X vaccine production and supply chains: risk assessing healthcare systems operating with artificial intelligence and industry 4.0
A set of six algorithmic solutions is presented for resolving vaccine production and supply chain bottlenecks. A different set of algorithmic solutions is presented for forecasting risks during a Disease X event.
Information Theoretic Meta Learning with Gaussian Processes
We formulate meta learning using information theoretic concepts; namely, mutual information and the information bottleneck. The idea is to learn a stochastic representation or encoding of the task description, given by a…
Gaussian ProcessesMeta-LearningBlockchain-Enabled Variational Information Bottleneck for Data Extraction Based on Mutual Information in Internet of Vehicles
The Internet of Vehicles (IoV) network can address the issue of limited computing resources and data processing capabilities of individual vehicles, but it also brings the risk of privacy leakage to vehicle users. Applyi…
Data CompressionData InteractionOn Encoding Matrices using Quantum Circuits
Over a decade ago, it was demonstrated that quantum computing has the potential to revolutionize numerical linear algebra by enabling algorithms with complexity superior to what is classically achievable, e.g., the semin…
Diminution: On Reducing the Size of Grounding ASP Programs
Answer Set Programming (ASP) is often hindered by the grounding bottleneck: large Herbrand universes generate ground programs so large that solving becomes difficult. Many methods employ ad-hoc heuristics to improve grou…