A Bi-directional Multi-solution Scalable Grover Search Algorithm

Abstract:Grover's search algorithms, including various Partial Grover Searches (PGS), suffer from scaling issues when multiple solutions are sought, as the number of iterations scales with the number of solutions or marked states, making implementation more computationally expensive. Inspired by recent PGS algorithms for multi-solution searchers, this article proposes a scalable Grover quantum search algorithm, referred to as Bi-directional Multi-solution scalable Grover Search (BMGS), to efficiently search for an arbitrary number of solutions from an unstructured database. We introduced a novel multi-segment bidirectional search tactic with PGS across multiple equal segments of each state, starting from an initial state and multiple marked states in parallel, obviating the need for merge operations. We have shown in this work that for each solution our novel approach requires at most $\sqrt{\mathcal{N}}\left (1- \sqrt{\frac{1}{b^{\lfloor\frac{r}{dk}\rfloor}}}\right)$ iterations (here, $\mathcal{N}=2^r$ elements, $k=\log_2 b$, $d$ is the number of equal segments on $r$ qubits, and $b$ is the branching factor). Our proposed BMGS algorithm is benchmarked against state-of-the-art Depth First Grover Search (DFGS) and PGS implementations for an arbitrary number of solutions, ranging from $2$ to $20$ qubits, as a proof of concept. We also show that our BMGS requires fewer iterations for shallow quantum circuits and achieves an optimal $\mathcal{O}$($\sqrt{s\mathcal{N}}$) average complexity for $s$ solutions, when $dk < r$. The Qiskit Python implementation of the proposed BMGS algorithm is available on GitHub\footnote{this https URL}.

Quantum Physics (quant-ph); Artificial Intelligence (cs.AI)

arXiv:2404.15616 [quant-ph]

(or arXiv:2404.15616v2 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2404.15616 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.