Adiabatic Quantum Counting by Geometric Phase Estimation

Abstract

We design an adiabatic quantum algorithm for the counting problem, i.e., approximating the proportion, $α$, of the marked items in a given database. As the quantum system undergoes a designed cyclic adiabatic evolution, it acquires a Berry phase $2πα$. By estimating the Berry phase, we can approximate $α$, and solve the problem. For an error bound $ε$, the algorithm can solve the problem with cost of order $(\frac{1}ε)^{3/2}$, which is not as good as the optimal algorithm in the quantum circuit model, but better than the classical random algorithm. Moreover, since the Berry phase is a purely geometric feature, the result may be robust to decoherence and resilient to certain noise.

9 pages