RECORD
Average-Case Verification of the Quantum Fourier Transform Enables Worst-Case Phase Estimation
Quantum Physics · Submitted 21 Sep 2021
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim 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.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
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.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | 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. | background 1.00 | 0.04 | 0.02 | asserted 0.98 |
| s1 | As such, we may have little control over the state that is input to the QFT. | background 0.99 | 0.09 | 0.02 | hedged possibility 1.00 |
| s2 | Thus, in implementing a good QFT, we may imagine that it needs to perform well on arbitrary input states. | background 0.97 | 0.06 | 0.02 | hedged possibility 0.94 |
| s3 | 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. | background 0.61 | 0.08 | 0.03 | asserted 0.82 |
| s4 | 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. | result 0.64 | 0.94 | 0.94 | asserted 1.00 |
| s5 | Further we give a very efficient procedure to verify this required average-case behaviour of the QFT. | contribution 0.59 | 0.95 | 0.11 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v3
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
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.
Human review
How the literature uses it
What this paper does with the arXiv papers it cites
What it cites · 5 sentences without a confident label
Cites as background 7 papers
-
This means that efficient verification of worst-case correctness typically requires additional assumptions, ranging from restrictions on the class of circuits one is verifying (for instance Clifford circuits [ref] ) to cryptographic assumptions (as in Mahadev's approach [ref] , which also assumes the computation starts with a fixed initial state).
Lightweight Detection of a Small Number of Large Errors in a Quantum Circuit · Verification of quantum circuits · 0.85
-
This means that efficient verification of worst-case correctness typically requires additional assumptions, ranging from restrictions on the class of circuits one is verifying (for instance Clifford circuits [ref] ) to cryptographic assumptions (as in Mahadev's approach [ref] , which also assumes the computation starts with a fixed initial state).
Direct Fidelity Estimation from Few Pauli Measurements · Verification of quantum circuits · 0.85
-
This means that efficient verification of worst-case correctness typically requires additional assumptions, ranging from restrictions on the class of circuits one is verifying (for instance Clifford circuits [ref] ) to cryptographic assumptions (as in Mahadev's approach [ref] , which also assumes the computation starts with a fixed initial state).
Classical Verification of Quantum Computations · Verification of quantum circuits · 0.85
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.