A Bi-directional Multi-solution Scalable Grover Search Algorithm

Sicherheitsmeldung mit Schweregrad noch nicht bewertet. Technische Details im Tab „Originaltext“; empfohlene Schritte in der Checkliste.

Originaltext der Quelle (nicht übersetzt) – die deutsche Zusammenfassung findest du im Tab „Kurzfassung".

arXiv:2404.15616v2 Announce Type: replace-cross 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 …

Vollständiger Originalartikel ↗

• Betroffenheit im eigenen Stack prüfen: Versionen/Komponenten abgleichen.
• Originalquelle / Hersteller-Advisory lesen: https://arxiv.org/abs/2404.15616
• Verfügbaren Patch oder Workaround einspielen und dokumentieren.