The Quantum counting algorithm is a quantum algorithm for efficiently counting the number of solutions for a given search problem. The algorithm is based on the quantum phase estimation algorithm and on Grover's search algorithm. Counting problems are common in diverse fields such as statistical estimation, statistical physics, networking, etc. As for quantum computing, the ability to perform quantum counting efficiently is needed in order to use Grover's search algorithm (because running Grover's search algorithm requires knowing how many solutions exist). Moreover, this algorithm solves the quantum existence problem (namely, deciding whether any solution exists) as a special case. The algorithm was devised by Gilles Brassard, Peter Høyer and Alain Tapp in 1998.
The problem Consider a finite set { 0 , 1 } n {\displaystyle \{0,1\}^{n}} of size N = 2 n {\displaystyle N=2^{n}} and a set B {\displaystyle B} of "solutions" (that is a subset of { 0 , 1 } n {\displaystyle \{0,1\}^{n}} ). Define:
{ f : { 0 , 1 } n → { 0 , 1 } f ( x ) = { 1 x ∈ B 0 x ∉ B {\displaystyle {\begin{cases}f:\left\{0,1\right\}^{n}\to \{0,1\}\\f(x)={\begin{cases}1&x\in B\\0&x\notin B\end{cases}}\end{cases}}}
In other words, f {\displaystyle f} is the indicator function of B {\displaystyle B} . Calculate the number of solutions M = | f − 1 ( 1 ) | = | B | {\displaystyle M=\left\vert f^{-1}(1)\right\vert =\vert B\vert } .
Classical solution Without any prior knowledge on the set of solutions B {\displaystyle B} (or the structure of the function f {\displaystyle f} ), a classical deterministic solution cannot perform better than Ω ( N ) {\displaystyle \Omega (N)} , because all the N {\displaystyle N} elements of { 0 , 1 } n {\displaystyle \{0,1\}^{n}} must be inspected (consider a case where the last element to be inspected is a solution).
The algorithm
Setup The input consists of two registers (namely, two parts): the upper p {\displaystyle p} qubits comprise the first register, and the lower n {\displaystyle n} qubits are the second register.
Create superposition The initial state of the system is | 0 ⟩ ⊗ p | 0 ⟩ ⊗ n {\displaystyle |0\rangle ^{\otimes p}|0\rangle ^{\otimes n}} . After applying multiple bit Hadamard gate operation on each of the registers separately, the state of the first register is
1 2 p / 2 ( | 0 ⟩ + | 1 ⟩ ) ⊗ p {\displaystyle {\frac {1}{2^{p/2}}}(|0\rangle +|1\rangle )^{\otimes p}}
and the state of the second register is
… excerpt ends here. Continue reading the full article.
