Simpler Quantum Counting

Understand

A simpler quantum counting algorithm based on amplitude amplification is presented.

• This algorithm is bounded by O(sqrt(N/M)) calls to the controlled-Grover operator where M is the number of marked states and N is the total number of states in the search space.
• This algorithm terminates within log(sqrt(N/M)) consecutive measurement steps when the probability p1 of measuring the state |1> is at least 0.5, and the result from the final step is used in estimating M by a classical post processing.
• The purpose of controlled-Grover iteration is to increase the probability p1.