{"id":"arxiv/2604.10428","url":"https://arxiv.org/abs/2604.10428","tags":["quant-ph"],"score":0,"title":"Worst-case Harrow-Hassidim-Lloyd algorithm with average-case correct quantum Fourier transform","domain":"quant-ph","source":"arxiv","authors":["Changpeng Shao"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-04-12","reactions":{}}