Adaptive quantum phase estimation can be better than non-adaptive

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_φ$ happen simultaneously without using more applications of U_φ, 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_φ. We also prove some upper bounds on the maximum advantage that adaptive algorithms for phase estimation can achieve over non-adaptive ones.