Quantum counting algorithm

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}$ of size $N=2^{n}$ and a set $B$ of "solutions" (that is a subset of $\{0,1\}^{n}$).

Let $f:\left\{0,1\right\}^{n}\rightarrow \left\{0,1\right\}$ such that $f(x)={\begin{cases}1&{\text{if }}x\in B\\0&{\text{if }}x\notin B\end{cases}}$ (namely, $f$ is the indicator function of $B$).

Calculate the number of solutions $M=\left\vert f^{-1}\left(1\right)\right\vert =\vert B\vert$.

Classical solution

Without any prior knowledge on the set of solutions $B$ (or the structure of the function $f$), a classical deterministic solution cannot perform better than $O(N)$, because all the $N$ elements of $\{0,1\}^{n}$ must be inspected (consider a case where the last element to be inspected is a solution).

The algorithm

Quantum counting circuit

Setup

The input consists of two registers (namely, two parts): the upper $p$ qubits comprise the first register, and the lower $n$ qubits are the second register.

Create superposition

The initial state of the system is $|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${\frac {1}{2^{p/2}}}(|0\rangle +|1\rangle )^{\otimes p}$ and the state of the second register is ${\frac {1}{2^{n/2}}}(|0\rangle +|1\rangle )^{\otimes n}={\frac {1}{\sqrt {N}}}\sum _{x=0}^{N-1}|x\rangle$ - an equal superposition state in the computational basis.

Grover operator

Because the size of the space is $\left\vert \{0,1\}^{n}\right\vert =2^{n}=N$ and the number of solutions is $\left\vert B\right\vert =M$, we can define the normalized states $|\alpha \rangle ={\frac {1}{\sqrt {N-M}}}\sum _{x\notin B}{|x\rangle }$ and $|\beta \rangle ={\frac {1}{\sqrt {M}}}\sum _{x\in B}{|x\rangle }$.

Note that ${\sqrt {\frac {N-M}{N}}}|\alpha \rangle +{\sqrt {\frac {M}{N}}}|\beta \rangle ={\frac {1}{\sqrt {N}}}\sum _{x=0}^{N-1}{|x\rangle }$, which is the state of the second register after the Hadamard transform.

Geometric visualization of Grover's algorithm shows that in the two-dimensional space spanned by $|\alpha \rangle$ and $|\beta \rangle$, the Grover operator is a counterclockwise rotation; hence, it can be expressed as $G={\begin{bmatrix}\cos \theta &-\sin \theta \\\sin \theta &\cos \theta \end{bmatrix}}$ in the orthonormal basis $\{|\alpha \rangle ,|\beta \rangle \}$.

From the properties of rotation matrices we know that $G$ is a unitary matrix with the two eigenvalues $e^{\pm i\theta }$.

Estimating the value of $\theta$

From here onwards, we follow the quantum phase estimation algorithm scheme: we apply controlled Grover operations followed by inverse quantum fourier transform; and according to the analysis, we will find the best $p$-bit approximation to the number $\theta$ (belonging to the eigenvalues $e^{\pm i\theta }$ of the Grover operator) with probability higher than ${\frac {4}{\pi ^{2}}}$.

Analysis

Assuming that we've doubled the search space so that $M\leq {\frac {N}{2}}$, we have $\sin {\frac {\theta }{2}}={\sqrt {\frac {M}{2N}}}$ as a result from Grover's algorithm analysis.

The error ${\frac {\vert \Delta M\vert }{2N}}={\Bigg \vert }\sin ^{2}\left({\frac {\theta +\Delta \theta }{2}}\right)-\sin ^{2}\left({\frac {\theta }{2}}\right){\Bigg \vert }$ is determined by the error in the estimation of the value of $\theta$, meaning that for a $p$ large enough we will have $\Delta \theta \approx 0$ hence $\vert \Delta M\vert \approx 0$.

A known result of Grover's search algorithm is that the number of iterations that should be done can be calculated by ${\frac {\pi }{4}}{\sqrt {\frac {N}{M}}}$.

If $N$ is known and $\theta$ is evaluated correctly, using the result of the Quantum counting algorithm $M$, it is possible to determine how many iterations should be done in Grover's search algorithm.

Additional uses

Speeding up NP-complete problems

The Quantum counting algorithm can be used to speed up solution to problems which are NP-complete.

An Hamiltonian cycle is a simple cycle that visits all vertices in a graph. The Hamiltonian cycle problem is determining whether a graph $G=(V,E)$ has an Hamiltonian cycle. This problem is NP-complete.

A simple solution to the Hamiltonian cycle problem is to check for each ordering of the vertices of $G$ whether it is an hamiltonian cycle or not until such ordering is found. Searching through all the possible combinations of the graph's vertices can be done with Quantum counting followed by Grover's algorithm, achieving a speed up of square root, similar to Grover's algorithm.

Quantum existence problem

Quantum existence problem is a special case of quantum counting where we don't want to calculate the value of $M$ but we only wish to decide whether $M\neq 0$ or not. Trivially it is possible to use the quantum counting algorithm and if it yields $M\neq 0$ then we have an answer to the existence problem. This approach involves some overhead information because we are not interested in the value of $M$.

Using a setup with small number of qubits in the upper register will not produce an accurate estimation of the value of $\theta$ but will suffice to realize whether $M$ equals zero or not.

See also

• Quantum phase estimation algorithm
• Grover's algorithm
• Counting problem (complexity)