Quantum counting algorithm
Quantum counting solves a generalization of the search problem. It solves the problem of counting the number of marked entries in an unordered list, instead of just detecting if one exists. Specifically, it counts the number of marked entries in an 



N


{\displaystyle N}

-element list, with error 



ε


{\displaystyle \varepsilon }

 making only 



Θ

(



1
ε





N
k




)



{\displaystyle \Theta \left({\frac {1}{\varepsilon }}{\sqrt {\frac {N}{k}}}\right)}

 queries, where 



k


{\displaystyle k}

 is the number of marked elements in the list. More precisely, the algorithm outputs an estimate 




k
′



{\displaystyle k'}

 for 



k


{\displaystyle k}

, the number of marked entries, with the following accuracy: 




|

k
−

k
′


|

≤
ε
k


{\displaystyle |k-k'|\leq \varepsilon k}

.
