Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2210.04664

Depth-First Grover Search Algorithm on Hybrid Quantum-Classical Computer

Haoxiang Guo

Published Oct 10, 2022• 0 citations
arXivHTMLPDF

Abstract

We demonstrated the detailed construction of the hybrid quantum-classical computer. Based on this architecture, the useful concept of amplitude interception is illustrated. It is then embedded into a combination of Depth-First Search and Grover's algorithm to generate a novel approach, the Depth-First Grover Search(DFGS), to handle multi-solution searching problems on unstructured databases with an unknown number of solutions. Our new algorithm attains an average complexity of $\mathcal{O}(m\sqrt{N})$ which performs as efficient as a normal Grover Search, and a $\mathcal{O}(\sqrt{p}N)$ complexity with a manually determined constant $p$ for the case with all elements are solutions, where a normal Grover Search will degenerate to $\mathcal{O}(N\sqrt{N})$. The DFGS algorithm is more robust and stable in comparison.

DOI
10.48550/arxiv.2210.04664

Related papers

Mixed Grover: A Hybrid Version to Improve Grover's Algorithm for Unstructured Database Search

Romain Piron, Muhammad Idham Habibie, Claire Goursaud

In this article, we propose a new strategy to exploit Grover's algorithm for unstructured search problems. We first show that running Grover's routine with a reduced number of iterations but allowing several trials presents a complexity advantage while keeping the same success probability. Then, by a theoretical analysis of the performance, we provide a generic procedure to parameterize the number of iterations$k$within one shot of Grover's algorithm and the maximum number of trials$T$, given a targeted success$p$and the size of the database$N$. At the end, we highlight that this new approach permits to reduce the computational time by at least 10% for$p \geq 0.999$independently of the size of the database.

IEEE Transactions on Quantum Engineering•Jan 1, 2025•4 citations

Variational Quantum Search with Shallow Depth for Unstructured Database Search

Junpeng Zhan

Abstract With the advent of powerful quantum computers, the quest for more efficient quantum algorithms becomes crucial in attaining quantum supremacy over classical counterparts in the noisy intermediate-scale quantum era. While Grover's search algorithm and its generalization, quantum amplitude amplification, offer quadratic speedup in solving various important scientific problems, their exponential time complexity limits scalability as the quantum circuit depths grow exponentially with the number of qubits. To overcome this challenge, we propose Variational Quantum Search (VQS), a novel algorithm based on variational quantum algorithms and parameterized quantum circuits. We show that a depth-10 Ansatz can amplify the total probability of k (k ≥ 1) good elements, out of 2n elements represented by n + 1 qubits, from k/2n to nearly 1, as verified for n up to 26, and that the maximum depth of quantum circuits in the VQS increases linearly with the number of qubits. Our experimental results have validated the efficacy of VQS and its exponential advantage over Grover's algorithm in circuit depth for up to 26 qubits. We demonstrate that a depth-56 circuit in VQS can replace a depth-270,989 circuit in Grover's algorithm. Envisioning its potential, VQS holds promise to accelerate solutions to critical problems.

arXiv:2212.09505•Dec 22, 2023•4 citations

Implementation of Grover’s Iterator for Quantum Searching With an Arbitrary Number of Qubits

Sihyung Lee, Seung Yeob Nam

Grover’s algorithm harnesses the power of quantum computing to swiftly locate specific elements in an unstructured database, outperforming classical computers in tasks like database searching. This algorithm capitalizes on the unique ability of qubits to be in both 0 and 1 states simultaneously (superposition), allowing it to scan the entire search space at once. It then boosts the probability of the target element, making it more prominent. While the foundational concepts of Grover’s algorithm are well-documented, practical implementation using quantum operators, especially for large search spaces, remains less explored beyond basic examples with a small number of qubits. Existing general synthesis techniques often involve numerous operators or are time-consuming. Our proposed methods specifically address the amplitude-amplification component of Grover’s algorithm for any size of search space. These methods detail the required types and quantities of qubits and operators, emphasizing minimal usage and efficient assembly. Developed and evaluated in Python, our methods consistently identified target elements with over 95% accuracy and achieved configurations comparably compact as those in the existing literature but at a faster pace. We anticipate that these methods facilitate practical implementations of Grover’s algorithm across various domains.

IEEE Access•Jan 1, 2024•7 citations

Quantum Search using Grover’s Algorithm: Principles, Performance, and Applications

Anggit Gusti Nugraheni, Heri Mahyuzar, Sri Hastuti

Quantum search is one of the most important algorithmic developments in quantum computing because it demonstrates how quantum principles can improve the efficiency of solving unstructured search problems. Grover’s algorithm provides a quadratic speed-up over classical linear search by reducing query complexity from O(N) to O(√N), where N represents the size of the search space. This review examines the principles, performance, and applications of Grover’s algorithm, with emphasis on its theoretical foundation and practical relevance. The discussion covers the roles of superposition, quantum interference, oracle operations, diffusion operators, and amplitude amplification in increasing the probability of measuring a desired solution. The manuscript also reviews the computational performance of quantum search in comparison with classical search methods and considers its relevance to database searching, combinatorial optimisation, cryptography, machine learning, bioinformatics, quantum chemistry, and materials science. The review highlights that Grover’s algorithm is not limited to database retrieval, as many computationally intensive problems can be reformulated as search or optimisation tasks. However, practical implementation remains constrained by current quantum hardware limitations, including decoherence, quantum noise, limited qubit availability, circuit depth, and the difficulty of designing efficient oracles. Despite these challenges, continuing progress in quantum hardware, error correction, cloud-based quantum platforms, and hybrid quantum-classical architectures suggests that quantum search will remain an important area of research. Overall, Grover’s algorithm represents a foundational quantum algorithm with significant theoretical value and potential long-term application in computational domains involving large and unstructured search spaces.

Asian journal of mathematics and computer research•Jun 23, 2026•0 citations

A Bi-directional multi-solution scalable Grover search Algorithm

Debanjan Konar, Zain Hafeez, Vaneet Aggarwal

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 ).

arXiv:2404.15616•Quantum Information Processing•Sep 3, 2026•0 citations

Depth optimization of quantum search algorithms beyond Grover's algorithm

Kun Zhang, V. E. Korepin

Grover's quantum search algorithm provides a quadratic speedup over the classical one. The computational complexity is based on the number of queries to the oracle. However, depth is a more modern metric for noisy intermediate-scale quantum computers. We propose a depth optimization method for the quantum search algorithm. We show that Grover's algorithm is not optimal in depth. We propose a quantum search algorithm, which can be divided into several stages. Each stage has a new initialization, which is a rescaling of the database. This decreases errors. The multistage design is natural for parallel running of the quantum search algorithm.

arXiv:1908.04171•Physical Review A•Mar 26, 2020•55 citations
We demonstrated the detailed construction of the hybrid quantum-classical computer. Based on this architecture, the useful concept of amplitude interception is illustrated. It is then embedded into a combination of Depth-First Search and Grover's algorithm to generate a novel approach, the Depth-First Grover Search(DFGS), to handle multi-solution searching problems on unstructured databases with an unknown number of solutions. Our new algorithm attains an average complexity of O(mN)\mathcal{O}(m\sqrt{N})O(mN​) which performs as efficient as a normal Grover Search, and a O(pN)\mathcal{O}(\sqrt{p}N)O(p​N) complexity with a manually determined constant ppp for the case with all elements are solutions, where a normal Grover Search will degenerate to O(NN)\mathcal{O}(N\sqrt{N})O(NN​). The DFGS algorithm is more robust and stable in comparison.
In this article, we propose a new strategy to exploit Grover's algorithm for unstructured search problems. We first show that running Grover's routine with a reduced number of iterations but allowing several trials presents a complexity advantage while keeping the same success probability. Then, by a theoretical analysis of the performance, we provide a generic procedure to parameterize the number of iterationskkkwithin one shot of Grover's algorithm and the maximum number of trialsTTT, given a targeted successpppand the size of the databaseNNN. At the end, we highlight that this new approach permits to reduce the computational time by at least 10% forp≥0.999p \geq 0.999p≥0.999independently of the size of the database.
Abstract With the advent of powerful quantum computers, the quest for more efficient quantum algorithms becomes crucial in attaining quantum supremacy over classical counterparts in the noisy intermediate-scale quantum era. While Grover's search algorithm and its generalization, quantum amplitude amplification, offer quadratic speedup in solving various important scientific problems, their exponential time complexity limits scalability as the quantum circuit depths grow exponentially with the number of qubits. To overcome this challenge, we propose Variational Quantum Search (VQS), a novel algorithm based on variational quantum algorithms and parameterized quantum circuits. We show that a depth-10 Ansatz can amplify the total probability of k (k ≥ 1) good elements, out of 2n elements represented by n + 1 qubits, from k/2n to nearly 1, as verified for n up to 26, and that the maximum depth of quantum circuits in the VQS increases linearly with the number of qubits. Our experimental results have validated the efficacy of VQS and its exponential advantage over Grover's algorithm in circuit depth for up to 26 qubits. We demonstrate that a depth-56 circuit in VQS can replace a depth-270,989 circuit in Grover's algorithm. Envisioning its potential, VQS holds promise to accelerate solutions to critical problems.
Grover’s algorithm harnesses the power of quantum computing to swiftly locate specific elements in an unstructured database, outperforming classical computers in tasks like database searching. This algorithm capitalizes on the unique ability of qubits to be in both 0 and 1 states simultaneously (superposition), allowing it to scan the entire search space at once. It then boosts the probability of the target element, making it more prominent. While the foundational concepts of Grover’s algorithm are well-documented, practical implementation using quantum operators, especially for large search spaces, remains less explored beyond basic examples with a small number of qubits. Existing general synthesis techniques often involve numerous operators or are time-consuming. Our proposed methods specifically address the amplitude-amplification component of Grover’s algorithm for any size of search space. These methods detail the required types and quantities of qubits and operators, emphasizing minimal usage and efficient assembly. Developed and evaluated in Python, our methods consistently identified target elements with over 95% accuracy and achieved configurations comparably compact as those in the existing literature but at a faster pace. We anticipate that these methods facilitate practical implementations of Grover’s algorithm across various domains.
Quantum search is one of the most important algorithmic developments in quantum computing because it demonstrates how quantum principles can improve the efficiency of solving unstructured search problems. Grover’s algorithm provides a quadratic speed-up over classical linear search by reducing query complexity from O(N) to O(√N), where N represents the size of the search space. This review examines the principles, performance, and applications of Grover’s algorithm, with emphasis on its theoretical foundation and practical relevance. The discussion covers the roles of superposition, quantum interference, oracle operations, diffusion operators, and amplitude amplification in increasing the probability of measuring a desired solution. The manuscript also reviews the computational performance of quantum search in comparison with classical search methods and considers its relevance to database searching, combinatorial optimisation, cryptography, machine learning, bioinformatics, quantum chemistry, and materials science. The review highlights that Grover’s algorithm is not limited to database retrieval, as many computationally intensive problems can be reformulated as search or optimisation tasks. However, practical implementation remains constrained by current quantum hardware limitations, including decoherence, quantum noise, limited qubit availability, circuit depth, and the difficulty of designing efficient oracles. Despite these challenges, continuing progress in quantum hardware, error correction, cloud-based quantum platforms, and hybrid quantum-classical architectures suggests that quantum search will remain an important area of research. Overall, Grover’s algorithm represents a foundational quantum algorithm with significant theoretical value and potential long-term application in computational domains involving large and unstructured search spaces.
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 N(1−1b⌊rdk⌋)\sqrt{\mathcal {N}}\left( 1- \sqrt{\frac{1}{b^{\lfloor \frac{r}{dk}\rfloor }}}\right) N​(1−b⌊dkr​⌋1​​) N 1 - 1 b ⌊ r dk ⌋ iterations (here, N=2r\mathcal {N}=2^rN=2r N = 2 r elements, k=log⁡2bk=\log _2 bk=log2​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 O\mathcal {O}O O ( sN\sqrt{s\mathcal {N}}sN​ s N ) average complexity for s solutions, when dk<rdk < rdk<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 ).
Grover's quantum search algorithm provides a quadratic speedup over the classical one. The computational complexity is based on the number of queries to the oracle. However, depth is a more modern metric for noisy intermediate-scale quantum computers. We propose a depth optimization method for the quantum search algorithm. We show that Grover's algorithm is not optimal in depth. We propose a quantum search algorithm, which can be divided into several stages. Each stage has a new initialization, which is a rescaling of the database. This decreases errors. The multistage design is natural for parallel running of the quantum search algorithm.