Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2604.10428 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _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 |