Adaptive quantum phase estimation can be better than non-adaptive

Noah Linden, Ronald de Wolf · 2025

Read Adaptive quantum phase estimation can be better than non-adaptive by Noah Linden, Ronald de Wolf (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-05372.txt.

Introduction

Noah Linden and a co-author show cases where adaptive quantum phase estimation beats the non-adaptive form. Phase estimation is a core quantum tool. It can be run all at once with no feedback, at the cost of many more qubits, and for a fully unknown phase feedback gives no edge.

Their cases add a promise: the phase can take only set values. Under that promise, adaptive runs, which choose later steps from early results, are provably better. The result maps a crisp line where feedback helps in quantum sensing and algorithms.

Catalog record

CREATORNoah Linden, Ronald de Wolf
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE3 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-05372

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Adaptive quantum phase estimation can be better than non-adaptive
Noah Linden, Ronald de Wolf

Abstract
Quantum phase estimation is one of the most important tools in quantum algorithms. It can be made non-adaptive (meaning all applications of the unitary U ϕ U_{\phi} happen simultaneously) without using more applications of U ϕ U_{\phi} , albeit at the expense of using many more qubits. It is also known that there is no advantage for adaptive algorithms in the case where the phase that needs to be estimated is arbitrary or is uniformly random. Here we give examples of a special case of phase estimation, with a promise on the values that the unknown phase can take, where adaptive methods are provably better than non-adaptive methods by a factor of nearly 2 in the number of uses of U ϕ U_{\phi} . We also prove some upper bounds on the maximum advantage that adaptive algorithms for phase estimation can achieve over non-adaptive ones.



1
Introduction

1.1
Phase estimation

In phase estimation we have the ability to apply a unitary
U_{\phi}
(possibly controlled by another qubit) and are given a copy of an eigenstate
|\Psi\rangle
of
U_{\phi}
with eigenvalue
e^{2\pi i\phi}
.
The task is to estimate the phase
\phi\in[0,1)
.
Kitaev
[
kitaev:stabilizer
]
showed how to estimate
\phi
with additive error
\delta
(modulo 1) using roughly
1/\delta
applications of
U_{\phi}
.
The standard circuit for this is as follows. We use a set of
k=\lceil{\log(1/\delta)}\rceil
auxiliary qubits starting in state
|0\rangle
which will end up containing a
k
-bit estimate of
\phi
.
These
k
qubits are first put into a uniform superposition over all
j=0,\ldots,2^{k}-1
, which controls how many times
U_{\phi}
is applied to
|\Psi\rangle
.
Because
|j\rangle\otimes U_{\phi}^{j}|\Psi\rangle=e^{2\pi ij\phi}|j\rangle\otimes|\Psi\rangle
, we obtain the following
k
-qubit state (tensored with our one copy of
|\Psi\rangle
)

\frac{1}{\sqrt{2^{k}}}\sum_{j=0}^{2^{k}-1}e^{2\pi ij\phi}|j\rangle.

(1)

By writing the binary expansion of
j
as a sum of powers of 2, this can be nicely factored as

\frac{1}{\sqrt{2}}(|0\rangle+e^{2\pi i2^{k-1}\phi}|1\rangle)\otimes\frac{1}{\sqrt{2}}(|0\rangle+e^{2\pi i2^{k-2}\phi}|1\rangle)\otimes\cdots\otimes\frac{1}{\sqrt{2}}(|0\rangle+e^{2\pi i\phi}|1\rangle).

(2)

One can think of this as applying the phase
\phi

2^{k-1}
times on the first qubit,
2^{k-2}
times on the second qubit, etc.
An inverse quantum Fourier transform (QFT, denoted
Q
below) will then convert this state into a state whose amplitudes are concentrated around the best
k
-bit approximations of
\phi
(mod 1).
In fact, if
\phi
can be written exactly with
k
bits of precision, then the circuit produces
\phi
with probability 1, because the state of Eq. (
2
) is then
Q|2^{k}\phi\rangle
.

Read the complete text