TheQuantum counting algorithm is aquantum algorithm for efficiently counting the number of solutions for a given search problem.The algorithm is based on thequantum phase estimation algorithm and onGrover's search algorithm.

Counting problems are common in diverse fields such as statistical estimation, statistical physics, networking, etc. As forquantum 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 whetherany solution exists) as a special case.

The algorithm was devised byGilles Brassard, Peter Høyer and Alain Tapp in 1998.

Consider a finite set${\displaystyle \{0,1{\}}^n}$ of size${\displaystyle N=2^n}$ and a set${\displaystyle B}$ of "solutions" (that is a subset of${\displaystyle \{0,1{\}}^n}$). Define:

In other words,${\displaystyle f}$ is theindicator function of${\displaystyle B}$.

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

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

The input consists of tworegisters (namely, two parts): the upper${\displaystyle p}$ qubits comprise thefirst register, and the lower${\displaystyle n}$ qubits are thesecond register.

The initial state of the system is${\displaystyle |0{⟩}^{\otimes p}|0{⟩}^{\otimes n}}$. After applying multiple bitHadamard gate operation on each of the registers separately, the state of thefirst register is

${\displaystyle \frac{1}{2^{p/2}}(|0⟩+|1⟩{)}^{\otimes p}}$

and the state of thesecond register is

${\displaystyle \frac{1}{2^{n/2}}(|0⟩+|1⟩{)}^{\otimes n}=\frac{1}{\sqrt{N}}\sum _{x=0}^{N-1}|x⟩}$

an equalsuperposition state in the computational basis.

Because the size of the space is${\displaystyle \left|\{0,1{\}}^n\right|=2^n=N}$ and the number of solutions is${\displaystyle \left|B\right|=M}$, we can define the normalized states:^[2]: 252

${\displaystyle |\alpha ⟩=\frac{1}{\sqrt{N-M}}\sum _{x\notin B}|x⟩,\text{and}|\beta ⟩=\frac{1}{\sqrt{M}}\sum _{x\in B}|x⟩.}$

Note that

${\displaystyle \sqrt{\frac{N-M}{N}}|\alpha ⟩+\sqrt{\frac{M}{N}}|\beta ⟩=\frac{1}{\sqrt{N}}\sum _{x=0}^{N-1}|x⟩,}$

which is the state of thesecond register after the Hadamard transform.

Geometric visualization of Grover's algorithm shows that in the two-dimensional space spanned by${\displaystyle |\alpha ⟩}$ and${\displaystyle |\beta ⟩}$, the Grover operator is acounterclockwise rotation; hence, it can be expressed as

in theorthonormal basis${\displaystyle \{|\alpha ⟩,|\beta ⟩\}}$.^{[2]: 252 [3]: 149}

From theproperties of rotation matrices we know that${\displaystyle G}$ is aunitary matrix with the twoeigenvalues${\displaystyle e^{\pm i\theta }}$.^[2]: 253

From here onwards, we follow thequantum phase estimation algorithm scheme: we applycontrolled Grover operations followed by inversequantum Fourier transform; and according to theanalysis, we will find the best${\displaystyle p}$-bit approximation to thereal number${\displaystyle \theta }$ (belonging to the eigenvalues${\displaystyle e^{\pm i\theta }}$ of the Grover operator) with probability higher than${\displaystyle \frac{4}{{\pi }^2}}$.^{[4]: 348 [3]: 157}

Note that the second register is actually in asuperposition of theeigenvectors of the Grover operator (while in the original quantum phase estimation algorithm, the second register is the required eigenvector). This means that with some probability, we approximate${\displaystyle \theta }$, and with some probability, we approximate${\displaystyle 2\pi -\theta }$; those two approximations are equivalent.^{[2]: 224–225}

Assuming that the size${\displaystyle N}$ of the space is at least twice the number of solutions (namely, assuming that${\displaystyle M\le \frac{N}{2}}$), a result of the analysis of Grover's algorithm is:^[2]: 254

${\displaystyle \sin \frac{\theta }{2}=\sqrt{\frac{M}{N}}.}$

Thus, if we find${\displaystyle \theta }$, we can also find the value of${\displaystyle M}$ (because${\displaystyle N}$ is known).

The error

${\displaystyle \frac{|\mathrm{\Delta }M|}{N}=\left|{\sin }^2\left(\frac{\theta +\mathrm{\Delta }\theta }{2}\right)-{\sin }^2\left(\frac{\theta }{2}\right)\right|}$

is determined by the error within estimation of the value of${\displaystyle \theta }$. The quantum phase estimation algorithm finds, with high probability, the best${\displaystyle p}$-bit approximation of${\displaystyle \theta }$; this means that if${\displaystyle p}$ is large enough, we will have${\displaystyle \mathrm{\Delta }\theta \approx 0}$, hence${\displaystyle |\mathrm{\Delta }M|\approx 0}$.^[2]: 263

In Grover's search algorithm, the number of iterations that should be done is${\displaystyle \frac{\pi }{4}\sqrt{\frac{N}{M}}}$.^{[2]: 254 [3]: 150}

Thus, if${\displaystyle N}$ is known and${\displaystyle M}$ is calculated by the quantum counting algorithm, the number of iterations for Grover's algorithm is easily calculated.

The quantum counting algorithm can be used to speed up solution to problems which areNP-complete.

An example of an NP-complete problem is theHamiltonian cycle problem, which is the problem of determining whether agraph${\displaystyle G=(V,E)}$ has aHamiltonian cycle.

A simple solution to the Hamiltonian cycle problem is checking, for each ordering of the vertices of${\displaystyle G}$, whether it is a Hamiltonian cycle or not. Searching through all the possible orderings of the graph's vertices can be done with quantum counting followed by Grover's algorithm, achieving a speedup of the square root, similar to Grover's algorithm.^[2]: 264 This approach finds a Hamiltonian cycle (if exists); for determining whether a Hamiltonian cycle exists, the quantum counting algorithm itself is sufficient (and even the quantum existence algorithm, described below, is sufficient).

Quantum existence problem is a special case of quantum counting where we do not want to calculate the value of${\displaystyle M}$, but we only wish to know whether${\displaystyle M\ne 0}$ or not.^[5]: 147

A trivial solution to this problem is directly using the quantum counting algorithm: the algorithm yields${\displaystyle M}$, so by checking whether${\displaystyle M\ne 0}$ we get the answer to the existence problem. This approach involves some overhead information because we are not interested in the value of${\displaystyle M}$. Quantum phase estimation can be optimized to eliminate this overhead.^[5]: 148

If you are not interested in the control of error probability then using a setup with small number of qubits in the upper register will not produce an accurate estimation of the value of${\displaystyle \theta }$, but will suffice to determine whether${\displaystyle M}$ equals zero or not.^[2]: 263

Quantum relation testing${\displaystyle QRT(value,relation)}$. is an extension of quantum existence testing, it decides whether at least one entry can be found in the data base which fulfils the relation to a certain reference value.^[6] E.g.${\displaystyle QRT(5,>)}$ gives back YES if the data base contains any value larger than 5 else it returns NO. Quantum relation testing combined with classical logarithmic search forms an efficient quantum min/max searching algorithm.^{[5]: 152 [7]}

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

• Quantum algorithms

• CS1 maint: multiple names: authors list
• Articles with short description
• Short description is different from Wikidata