Worst-case Harrow-Hassidim-Lloyd algorithm with average-case correct quantum Fourier transform
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918440872181760 |
|---|---|
| author | Shao, Changpeng |
| author_facet | Shao, Changpeng |
| contents | 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 the average-case correct behavior of the quantum Fourier transform (QFT). They proved that good average-case QFT performance suffices for good worst-case performance in several quantum tasks. Here we provide another application of this worst-case-to-average-case reduction, using a strengthened Linden-de Wolf protocol. We show that, across three distinct scenarios, the Harrow-Hassidim-Lloyd algorithm can be executed with provably good worst-case performance, assuming only that the QFT is correct on average. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_10428 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Worst-case Harrow-Hassidim-Lloyd algorithm with average-case correct quantum Fourier transform Shao, Changpeng Quantum Physics 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 the average-case correct behavior of the quantum Fourier transform (QFT). They proved that good average-case QFT performance suffices for good worst-case performance in several quantum tasks. Here we provide another application of this worst-case-to-average-case reduction, using a strengthened Linden-de Wolf protocol. We show that, across three distinct scenarios, the Harrow-Hassidim-Lloyd algorithm can be executed with provably good worst-case performance, assuming only that the QFT is correct on average. |
| title | Worst-case Harrow-Hassidim-Lloyd algorithm with average-case correct quantum Fourier transform |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2604.10428 |