A Bi-directional multi-solution scalable Grover search Algorithm

Abstract

Abstract Grover’s search algorithms, including various partial Grover searches (PGS), experience scaling problems when multiple solutions are sought, as the number of iterations increases 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) $$ N 1 - 1 b ⌊ r dk ⌋ iterations (here, $$\mathcal {N}=2^r$$ N = 2 r elements, $$k=\log _2 b$$ 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}$$ O ( $$\sqrt{s\mathcal {N}}$$ s N ) average complexity for s solutions, when $$dk < r$$ d k < r . The Qiskit Python implementation of the proposed BMGS algorithm is available on GitHub ( https://github.com/hafeezzwiz21/Multi-Solution-DFGS-BMGS ).