2023/12/05 by Gustavo Alves Bezerra, Bezerra, Gustavo Alves
Computer Science · #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph)
paper · doi:10.48550/arxiv.2312.03768
openalex publication_date 2023/12/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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(√(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(√(k)) using O(√(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(√(k)) using O(t√(N)) steps and success probability of at least (1 - 2-t)8/π2.