Worst-case Harrow-Hassidim-Lloyd algorithm with average-case correct quantum Fourier transform
arXiv:2604.10428
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.
23 pages, some typos are fixed