Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2604.10428

Worst-case Harrow-Hassidim-Lloyd algorithm with average-case correct quantum Fourier transform

Changpeng Shao

quant-phSubmitted Apr 12, 2026• Announced Apr 14, 2026• 0 citations• Revised Jul 2, 2026 (v2)
v1 · Apr 12, 2026v2 · Jul 2, 2026
arXivHTMLPDF

Abstract

In [\href{https://quantum-journal.org/papers/q-2022-12-07-872/}{Quantum 6, 872, 2022}], Linden and de Wolf proposed a lightweight protocol for verifying average-case correctness of the quantum Fourier transform (QFT). They showed that good average-case QFT performance is sufficient for good worst-case performance in several quantum information-processing tasks. In this work, we study whether such average-case guarantees are also sufficient when the QFT is used coherently inside the Harrow--Hassidim--Lloyd algorithm. We show that the original average-case condition is not quite strong enough for this purpose, due to possible relative phase errors between different eigenspaces. To address this, we introduce a strengthened Linden--de Wolf-type verification condition that controls the relevant coherences, and prove that it guarantees worst-case correctness of the HHL algorithm in several natural settings.

Comments
23 pages, some typos are fixed

Related papers

Average-Case Verification of the Quantum Fourier Transform Enables Worst-Case Phase Estimation

Noah Linden, Ronald de Wolf

The quantum Fourier transform (QFT) is a key primitive for quantum computing that is typically used as a subroutine within a larger computation, for instance for phase estimation. As such, we may have little control over the state that is input to the QFT. Thus, in implementing a good QFT, we may imagine that it needs to perform well on arbitrary input states. Verifying this worst-case correct behaviour of a QFT-implementation would be exponentially hard (in the number of qubits) in general, raising the concern that this verification would be impossible in practice on any useful-sized system. In this paper we show that, in fact, we only need to have good average-case performance of the QFT to achieve good worst-case performance for key tasks – phase estimation, period finding and amplitude estimation. Further we give a very efficient procedure to verify this required average-case behaviour of the QFT.

arXiv:2109.10215•Quantum•Dec 7, 2022•13 citations

Harrow-Hassidim-Lloyd algorithm without ancilla postselection

Бабухин Данила Валерьевич

Harrow-Hassidim-Lloyd algorithm (HHL) allows for the exponentially faster solution of a system of linear equations. However, this algorithm requires the postselection of an ancilla qubit to obtain the solution. This postselection makes the algorithm result probabilistic. Here we show conditions when the HHL algorithm can work without postselection of the ancilla qubit. We derive expectation values for an observable $M$ on the HHL outcome state when ancilla qubit is measured in $|0\ensuremath{\rangle}$ and $|1\ensuremath{\rangle}$ and show a condition for postselection-free HHL running. We provide an explicit example of a practically interesting input matrix and an observable, which satisfies the postselection-free HHL condition. Our work can improve the performance of the HHL-based algorithms.

arXiv:2208.02200•Physical Review A•Apr 6, 2023•14 citations

Solving the encoding bottleneck: of the HHL algorithm, by the HHL algorithm

Guang Ping He

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.

arXiv:2502.13534•Feb 19, 2025•2 citations

Quantum Worst-Case to Average-Case Reductions for All Linear Problems

Vahid R. Asadi, Alexander Golovnev, Tom Gur +2 more

We study the problem of designing worst-case to average-case reductions for quantum algorithms. For all linear problems, we provide an explicit and efficient transformation of quantum algorithms that are only correct on a small (even sub-constant) fraction of their inputs into ones that are correct on all inputs. This stands in contrast to the classical setting, where such results are only known for a small number of specific problems or restricted computational models. En route, we obtain a tight $Ω(n^2)$ lower bound on the average-case quantum query complexity of the Matrix-Vector Multiplication problem. Our techniques strengthen and generalise the recently introduced additive combinatorics framework for classical worst-case to average-case reductions (STOC 2022) to the quantum setting. We rely on quantum singular value transformations to construct quantum algorithms for linear verification in superposition and learning Bogolyubov subspaces from noisy quantum oracles. We use these tools to prove a quantum local correction lemma, which lies at the heart of our reductions, based on a noise-robust probabilistic generalisation of Bogolyubov's lemma from additive combinatorics.

arXiv:2212.03348•Dec 6, 2022•1 citation

A Note on "Quantum Algorithm for Linear Systems of Equations"

Yongzhen Xu, Yifan Huang, Zekun Ye +1 more

Recently, an efficient quantum algorithm for linear systems of equations introduced by Harrow, Hassidim, and Lloyd, has received great concern from the academic community. However, the error and complexity analysis for this algorithm seems so complicated that it may not be applicable to other filter functions for other tasks. In this note, a concise proof is proposed. We hope that it may inspire some novel HHL-based algorithms that can compute $F(A)|b\rangle$ for any computable $F$.

arXiv:1802.07194•Feb 20, 2018•0 citations

An Iterative Improvement Method for HHL algorithm for Solving Linear System of Equations

Yoshiyuki Saito, Xinwei Lee, Dongsheng Cai +1 more

We propose an iterative improvement method for the Harrow-Hassidim-Lloyd (HHL) algorithm to solve a linear system of equations. This is a quantum-classical hybrid algorithm. The accuracy is essential to solve the linear system of equations. However, the accuracy of the HHL algorithm is limited by the number of quantum bits used to express the eigenvalues of the matrix. Our iterative method improves the accuracy of the HHL solutions, and gives higher accuracy which surpasses the accuracy limited by the number of quantum bits. In practical HHL algorithm, a huge number of measurements is required to obtain good accuracy, even if we provide a sufficient number of quantum bits for the eigenvalue expression, since the solution is statistically processed from the measurements. Our improved iterative method can reduce the number of measurements. Moreover, the sign information for each eigenstate of the solution is lost once the measurement is made, although the sign is significant. Therefore, the naïve iterative method of the HHL algorithm may slow down, especially, when the solution includes wrong signs. In this paper, we propose and evaluate an improved iterative method for the HHL algorithm that is robust against the sign information loss, in terms of the number of iterations and the computational accuracy.

arXiv:2108.07744•Aug 17, 2021•10 citations
In [\href{https://quantum-journal.org/papers/q-2022-12-07-872/}{Quantum 6, 872, 2022}], Linden and de Wolf proposed a lightweight protocol for verifying average-case correctness of the quantum Fourier transform (QFT). They showed that good average-case QFT performance is sufficient for good worst-case performance in several quantum information-processing tasks. In this work, we study whether such average-case guarantees are also sufficient when the QFT is used coherently inside the Harrow--Hassidim--Lloyd algorithm. We show that the original average-case condition is not quite strong enough for this purpose, due to possible relative phase errors between different eigenspaces. To address this, we introduce a strengthened Linden--de Wolf-type verification condition that controls the relevant coherences, and prove that it guarantees worst-case correctness of the HHL algorithm in several natural settings.
The quantum Fourier transform (QFT) is a key primitive for quantum computing that is typically used as a subroutine within a larger computation, for instance for phase estimation. As such, we may have little control over the state that is input to the QFT. Thus, in implementing a good QFT, we may imagine that it needs to perform well on arbitrary input states. Verifying this worst-case correct behaviour of a QFT-implementation would be exponentially hard (in the number of qubits) in general, raising the concern that this verification would be impossible in practice on any useful-sized system. In this paper we show that, in fact, we only need to have good average-case performance of the QFT to achieve good worst-case performance for key tasks – phase estimation, period finding and amplitude estimation. Further we give a very efficient procedure to verify this required average-case behaviour of the QFT.
Harrow-Hassidim-Lloyd algorithm (HHL) allows for the exponentially faster solution of a system of linear equations. However, this algorithm requires the postselection of an ancilla qubit to obtain the solution. This postselection makes the algorithm result probabilistic. Here we show conditions when the HHL algorithm can work without postselection of the ancilla qubit. We derive expectation values for an observable MMM on the HHL outcome state when ancilla qubit is measured in $|0\ensuremath{\rangle}$ and $|1\ensuremath{\rangle}$ and show a condition for postselection-free HHL running. We provide an explicit example of a practically interesting input matrix and an observable, which satisfies the postselection-free HHL condition. Our work can improve the performance of the HHL-based algorithms.
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 NNN-dimensional state exactly, existing state-preparation approaches generally require a runtime of O(N)O(N)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))O(poly(\log N))O(poly(logN)) 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.
We study the problem of designing worst-case to average-case reductions for quantum algorithms. For all linear problems, we provide an explicit and efficient transformation of quantum algorithms that are only correct on a small (even sub-constant) fraction of their inputs into ones that are correct on all inputs. This stands in contrast to the classical setting, where such results are only known for a small number of specific problems or restricted computational models. En route, we obtain a tight Ω(n2)Ω(n^2)Ω(n2) lower bound on the average-case quantum query complexity of the Matrix-Vector Multiplication problem. Our techniques strengthen and generalise the recently introduced additive combinatorics framework for classical worst-case to average-case reductions (STOC 2022) to the quantum setting. We rely on quantum singular value transformations to construct quantum algorithms for linear verification in superposition and learning Bogolyubov subspaces from noisy quantum oracles. We use these tools to prove a quantum local correction lemma, which lies at the heart of our reductions, based on a noise-robust probabilistic generalisation of Bogolyubov's lemma from additive combinatorics.
Recently, an efficient quantum algorithm for linear systems of equations introduced by Harrow, Hassidim, and Lloyd, has received great concern from the academic community. However, the error and complexity analysis for this algorithm seems so complicated that it may not be applicable to other filter functions for other tasks. In this note, a concise proof is proposed. We hope that it may inspire some novel HHL-based algorithms that can compute F(A)∣b⟩F(A)|b\rangleF(A)∣b⟩ for any computable FFF.
We propose an iterative improvement method for the Harrow-Hassidim-Lloyd (HHL) algorithm to solve a linear system of equations. This is a quantum-classical hybrid algorithm. The accuracy is essential to solve the linear system of equations. However, the accuracy of the HHL algorithm is limited by the number of quantum bits used to express the eigenvalues of the matrix. Our iterative method improves the accuracy of the HHL solutions, and gives higher accuracy which surpasses the accuracy limited by the number of quantum bits. In practical HHL algorithm, a huge number of measurements is required to obtain good accuracy, even if we provide a sufficient number of quantum bits for the eigenvalue expression, since the solution is statistically processed from the measurements. Our improved iterative method can reduce the number of measurements. Moreover, the sign information for each eigenstate of the solution is lost once the measurement is made, although the sign is significant. Therefore, the naïve iterative method of the HHL algorithm may slow down, especially, when the solution includes wrong signs. In this paper, we propose and evaluate an improved iterative method for the HHL algorithm that is robust against the sign information loss, in terms of the number of iterations and the computational accuracy.