Algoritmo de Contagem Quântico Aplicado ao Grafo Bipartido Completo

Abstract

Studies on Quantum Computing have been developed since the 1980s, motivating researches on quantum algorithms better than any classical algorithm possible. An example of such algorithms is Grover's algorithm, capable of finding $k$ (marked) elements in an unordered database with $N$ elements using $O(\sqrt{N/k})$ steps. Grover's algorithm can be interpreted as a quantum walk in a complete graph (with loops) containing $N$ vertices from which $k$ are marked. This interpretation motivated search algorithms in other graphs -- complete bipartite graph, grid, and hypercube. Using Grover's algorithm's linear operator, the quantum counting algorithm estimates the value of $k$ with an error of $O(\sqrt{k})$ using $O(\sqrt{N})$ steps. This work tackles the problem of using the quantum counting algorithm for estimating the value $k$ of marked elements in other graphs; more specifically, the complete bipartite graph. It is concluded that for a particular case, running the proposed algorithm at most $t$ times wields an estimation of $k$ with an error of $O(\sqrt{k})$ using $O(t\sqrt{N})$ steps and success probability of at least $(1-2^{-t})8/{\pi }^2$.