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:2006.05828 · Physical Review A

Introducing structure to expedite quantum searching

Marcin Briański, Jan Gwinner, Vladyslav Hlembotskyi, Witold Jarnicki, Szymon Pliś, Adam Szady

Published Jun 28, 2021• 13 citations
arXivHTMLPDF

Abstract

We present a quantum algorithm for solving the unstructured search problem with one marked element. Our algorithm allows generating quantum circuits that use asymptotically fewer additional quantum gates than the famous Grover's algorithm and may be successfully executed on noisy intermediate-scale quantum devices. We prove that our algorithm is optimal in the total number of elementary gates up to a multiplicative constant. As many NP-hard problems are, in fact, not unstructured, we also describe the partial uncompute technique which exploits the oracle structure and allows a significant reduction in the number of elementary gates required to find the solution. Combining these results allows us to use an asymptotically smaller number of elementary gates than Grover's algorithm in various applications, keeping the number of queries to the oracle essentially the same. We show how the results can be applied to solve hard combinatorial problems, for example, Unique $k$-SAT. Additionally, we show how to asymptotically reduce the number of elementary gates required to solve the unstructured search problem with multiple marked elements.

DOI
10.1103/physreva.103.062425

Related papers

Optimization of 16-Element Quantum Search on IBMQ

Wei Zi, Shuai Yang, Cheng Guo +1 more

Unstructured searching, which is to find the marked element from a given unstructured data set, is a widely studied problem in computer science. It is well known that Grover algorithm provides a quadratic speedup to solve unstructured search problem compared with the classical algorithm. This algorithm has received a lot of attention due to the strong versatility. In this manuscript, we report experimental results of searching a unique target from 16 elements on five different quantum devices of IBM quantum Experience (IBMQ). We first implement the original Grover algorithm on these devices. However, the experiment probability of success of finding the correct target is almost the same as random choice. We then optimize the quantum circuit size of the search algorithm. The oracle operator and diffusion operator are two of the most costly operators in Grover algorithm. For the 16-element quantum search algorithm, both the oracle operator and diffusion operator consist of a triple controlled [Formula: see text] gate ([Formula: see text]) and some single-qubit gates. So we optimize the implementation of the [Formula: see text] gate according to the qubits layout of different quantum devices. On the ibmq_santiago, the experimental success rate of the 16-element quantum search algorithm is increased to [Formula: see text] by the optimization, which is better than all the published experiments implemented on IBMQ devices. For other IBMQ devices, the experimental success rate of 16-element quantum search also has been significantly improved. We then try to further reduce the size of the quantum circuit by modifying the Grover algorithm, with a tolerable loss of the theoretical success probability. On ibmq_quito, the experimental success rate is further improved from 25.23% to 27.56% after optimization. These experimental results show the importance of circuit optimization and algorithm optimization in the Noisy-Intermediate-Scale Quantum (NISQ) era.

SPIN•Sep 1, 2021•1 citation

Hardware Efficient Quantum Search Algorithm

Ji Liu, Huiyang Zhou

Quantum computing has noteworthy speedup over classical computing by taking advantage of quantum parallelism, i.e., the superposition of states. In particular, quantum search is widely used in various computationally hard problems. Grover's search algorithm finds the target element in an unsorted database with quadratic speedup than classical search and has been proved to be optimal in terms of the number of queries to the database. The challenge, however, is that Grover's search algorithm leads to high numbers of quantum gates, which make it infeasible for the Noise-Intermediate-Scale-Quantum (NISQ) computers. In this paper, we propose a novel hardware efficient quantum search algorithm to overcome this challenge. Our key idea is to replace the global diffusion operation with low-cost local diffusions. Our analysis shows that our algorithm has similar oracle complexity to the original Grover's search algorithm while significantly reduces the circuit depth and gate count. The circuit cost reduction leads to a remarkable improvement in the system success rates, paving the way for quantum search on NISQ machines.

arXiv:2103.14196•Mar 26, 2021•6 citations

Scaling Grover’s Search for Large Solution Spaces

Simone Faro, Francesco Pio Marino

Grover's algorithm offers a celebrated quadratic speedup for unstructured search problems, positioning it among the foundational tools of quantum computing. However, its effectiveness critically deteriorates when the number of valid solutions exceeds half of the total search space. In this work, we address this limitation by introducing a novel and efficient technique based on a virtual expansion of the input domain. Our approach extends the range of applicability of Grover's algorithm to high-density solution spaces, including those where the number of solutions is greater than N/2, without increasing the actual circuit depth or memory footprint. The core idea consists in appending one auxiliary qubit to the input register and modifying the oracle to mark only those solutions where the auxiliary qubit is in a fixed state. This effectively reduces the solution density in the extended space, restoring the geometric conditions required for successful amplitude amplification. We further analyze an extension of this strategy involving log n auxiliary qubits, which allows for tunable robustness at a moderate increase in computational cost. The proposed method is simple to implement on existing quantum hardware and maintains Grover's optimal asymptotic complexity in the expanded regime. Both theoretical analysis and empirical simulations confirm that our approach reliably outperforms the standard algorithm in scenarios with high solution density, thus broadening the practical utility of quantum search.

ACM International Symposium on High-Performance Parallel and Distributed Computing (HPDC)•Jul 20, 2025•1 citation

Adaptive complete quantum search with unknown number of solutions

Raj Alexandru Guţoiu, Bogdan-Călin Ciobanu, Pantelimon George Popescu

Unstructured database search is a fundamental problem that requires finding one or more elements satisfying a specific property within a set of candidates. While Grover's algorithm provides a quadratic speedup for finding a marked element when the number of solutions is known, finding all solutions when their number is unknown presents additional challenges. In this paper, we thoroughly analyze this problem by considering all the different regimes of combinations of classical, Grover and generalized fixed-point quantum search instances. We unify these into an adaptive Bayesian approach that maximizes the expected success probability per unit execution time at each searching instance. For a problem with a known number of solutions, much lower than the database size, we prove that our proposed approach is asymptotically optimal within the considered search model. Furthermore, we prove that for any probability distribution characterizing the likely number of solutions, in regimes where the classical verification time is at most 25% of the quantum amplitude amplification time, hybrid classical and Grover approaches are preferred to generalized fixed-point. Outside of this regime, we derive an upper bound on the maximal improvement achievable by fixed-point search compared to the best Grover-based score. Additionally, we determine the optimal transition point between classical sampling and quantum searching using an integral approximation of the probability distribution of the number of solutions. The analytical results are also supported by numerical simulations of the proposed algorithm and by comparisons between the generalized fixed-point and Grover-based search policies.

quant-pharXiv:2610.06364•Oct 6, 2026•0 citations

Grover's search with faults on some marked elements

Dmitry Kravchenko, Nikolajs Nahimovs, Alexander Rivosh

Grover's algorithm is a quantum query algorithm solving the unstructured search problem of size $N$ using $O(\sqrt{N})$ queries. It provides a significant speed-up over any classical algorithm \cite{Gro96}. The running time of the algorithm, however, is very sensitive to errors in queries. It is known that if query may fail (report all marked elements as unmarked) the algorithm needs $Ω(N)$ queries to find a marked element \cite{RS08}. \cite{AB+13} have proved the same result for the model where each marked element has its own probability to be reported as unmarked. We study the behavior of Grover's algorithm in the model where the search space contains both faulty and non-faulty marked elements. We show that in this setting it is indeed possible to find one of non-faulty marked items in $O(\sqrt{N})$ queries. We also analyze the limiting behavior of the algorithm for a large number of steps and show the existence and the structure of limiting state $ρ_{lim}$.

arXiv:1508.05108•Aug 20, 2015•0 citations

Novel Quantum Circuit Designs for the Oracle of Grover’s Algorithm to Solve the Vertex Cover Problem

Jehn‐Ruey Jiang, Wei-Han Yan

We propose new quantum circuit designs for the Grover oracle, i.e., the oracle of Grover’s algorithm, to solve the vertex cover problem (VCP) efficiently. Grover’s algorithm is an unstructured quantum search algorithm to search a target data item out of N data pieces by calling the oracle $\mathrm{O}(\sqrt{N})$ times. It represents a quadratic speedup compared to the classical unstructured data sequential search algorithm, which requires O(N) oracle calls. We are in the noisy intermediate-scale quantum (NISQ) era in which quantum computers have a limited number of qubits, short decoherence time, and low gate fidelity. It is thus desirable to design quantum circuits with three properties: (1) a reduced number of qubits, (2) shorter quantum depth, and (3) fewer gates. We created novel designs of a quantum counter and a quantum semaphore to be applied to the Grover oracle to have the three properties. Through the IBM Quantum Lab service, we executed Grover’s algorithm with the novel quantum circuit designs to solve the VCP to validate the design correctness.

IEEE Eurasia Conference on IOT, Communication and Engineering (ECICE)•Oct 27, 2023•5 citations
We present a quantum algorithm for solving the unstructured search problem with one marked element. Our algorithm allows generating quantum circuits that use asymptotically fewer additional quantum gates than the famous Grover's algorithm and may be successfully executed on noisy intermediate-scale quantum devices. We prove that our algorithm is optimal in the total number of elementary gates up to a multiplicative constant. As many NP-hard problems are, in fact, not unstructured, we also describe the partial uncompute technique which exploits the oracle structure and allows a significant reduction in the number of elementary gates required to find the solution. Combining these results allows us to use an asymptotically smaller number of elementary gates than Grover's algorithm in various applications, keeping the number of queries to the oracle essentially the same. We show how the results can be applied to solve hard combinatorial problems, for example, Unique kkk-SAT. Additionally, we show how to asymptotically reduce the number of elementary gates required to solve the unstructured search problem with multiple marked elements.
Unstructured searching, which is to find the marked element from a given unstructured data set, is a widely studied problem in computer science. It is well known that Grover algorithm provides a quadratic speedup to solve unstructured search problem compared with the classical algorithm. This algorithm has received a lot of attention due to the strong versatility. In this manuscript, we report experimental results of searching a unique target from 16 elements on five different quantum devices of IBM quantum Experience (IBMQ). We first implement the original Grover algorithm on these devices. However, the experiment probability of success of finding the correct target is almost the same as random choice. We then optimize the quantum circuit size of the search algorithm. The oracle operator and diffusion operator are two of the most costly operators in Grover algorithm. For the 16-element quantum search algorithm, both the oracle operator and diffusion operator consist of a triple controlled [Formula: see text] gate ([Formula: see text]) and some single-qubit gates. So we optimize the implementation of the [Formula: see text] gate according to the qubits layout of different quantum devices. On the ibmq_santiago, the experimental success rate of the 16-element quantum search algorithm is increased to [Formula: see text] by the optimization, which is better than all the published experiments implemented on IBMQ devices. For other IBMQ devices, the experimental success rate of 16-element quantum search also has been significantly improved. We then try to further reduce the size of the quantum circuit by modifying the Grover algorithm, with a tolerable loss of the theoretical success probability. On ibmq_quito, the experimental success rate is further improved from 25.23% to 27.56% after optimization. These experimental results show the importance of circuit optimization and algorithm optimization in the Noisy-Intermediate-Scale Quantum (NISQ) era.
Quantum computing has noteworthy speedup over classical computing by taking advantage of quantum parallelism, i.e., the superposition of states. In particular, quantum search is widely used in various computationally hard problems. Grover's search algorithm finds the target element in an unsorted database with quadratic speedup than classical search and has been proved to be optimal in terms of the number of queries to the database. The challenge, however, is that Grover's search algorithm leads to high numbers of quantum gates, which make it infeasible for the Noise-Intermediate-Scale-Quantum (NISQ) computers. In this paper, we propose a novel hardware efficient quantum search algorithm to overcome this challenge. Our key idea is to replace the global diffusion operation with low-cost local diffusions. Our analysis shows that our algorithm has similar oracle complexity to the original Grover's search algorithm while significantly reduces the circuit depth and gate count. The circuit cost reduction leads to a remarkable improvement in the system success rates, paving the way for quantum search on NISQ machines.
Grover's algorithm offers a celebrated quadratic speedup for unstructured search problems, positioning it among the foundational tools of quantum computing. However, its effectiveness critically deteriorates when the number of valid solutions exceeds half of the total search space. In this work, we address this limitation by introducing a novel and efficient technique based on a virtual expansion of the input domain. Our approach extends the range of applicability of Grover's algorithm to high-density solution spaces, including those where the number of solutions is greater than N/2, without increasing the actual circuit depth or memory footprint. The core idea consists in appending one auxiliary qubit to the input register and modifying the oracle to mark only those solutions where the auxiliary qubit is in a fixed state. This effectively reduces the solution density in the extended space, restoring the geometric conditions required for successful amplitude amplification. We further analyze an extension of this strategy involving log n auxiliary qubits, which allows for tunable robustness at a moderate increase in computational cost. The proposed method is simple to implement on existing quantum hardware and maintains Grover's optimal asymptotic complexity in the expanded regime. Both theoretical analysis and empirical simulations confirm that our approach reliably outperforms the standard algorithm in scenarios with high solution density, thus broadening the practical utility of quantum search.
Unstructured database search is a fundamental problem that requires finding one or more elements satisfying a specific property within a set of candidates. While Grover's algorithm provides a quadratic speedup for finding a marked element when the number of solutions is known, finding all solutions when their number is unknown presents additional challenges. In this paper, we thoroughly analyze this problem by considering all the different regimes of combinations of classical, Grover and generalized fixed-point quantum search instances. We unify these into an adaptive Bayesian approach that maximizes the expected success probability per unit execution time at each searching instance. For a problem with a known number of solutions, much lower than the database size, we prove that our proposed approach is asymptotically optimal within the considered search model. Furthermore, we prove that for any probability distribution characterizing the likely number of solutions, in regimes where the classical verification time is at most 25% of the quantum amplitude amplification time, hybrid classical and Grover approaches are preferred to generalized fixed-point. Outside of this regime, we derive an upper bound on the maximal improvement achievable by fixed-point search compared to the best Grover-based score. Additionally, we determine the optimal transition point between classical sampling and quantum searching using an integral approximation of the probability distribution of the number of solutions. The analytical results are also supported by numerical simulations of the proposed algorithm and by comparisons between the generalized fixed-point and Grover-based search policies.
Grover's algorithm is a quantum query algorithm solving the unstructured search problem of size NNN using O(N)O(\sqrt{N})O(N​) queries. It provides a significant speed-up over any classical algorithm \cite{Gro96}. The running time of the algorithm, however, is very sensitive to errors in queries. It is known that if query may fail (report all marked elements as unmarked) the algorithm needs Ω(N)Ω(N)Ω(N) queries to find a marked element \cite{RS08}. \cite{AB+13} have proved the same result for the model where each marked element has its own probability to be reported as unmarked. We study the behavior of Grover's algorithm in the model where the search space contains both faulty and non-faulty marked elements. We show that in this setting it is indeed possible to find one of non-faulty marked items in O(N)O(\sqrt{N})O(N​) queries. We also analyze the limiting behavior of the algorithm for a large number of steps and show the existence and the structure of limiting state ρlimρ_{lim}ρlim​.
We propose new quantum circuit designs for the Grover oracle, i.e., the oracle of Grover’s algorithm, to solve the vertex cover problem (VCP) efficiently. Grover’s algorithm is an unstructured quantum search algorithm to search a target data item out of N data pieces by calling the oracle O(N)\mathrm{O}(\sqrt{N})O(N​) times. It represents a quadratic speedup compared to the classical unstructured data sequential search algorithm, which requires O(N) oracle calls. We are in the noisy intermediate-scale quantum (NISQ) era in which quantum computers have a limited number of qubits, short decoherence time, and low gate fidelity. It is thus desirable to design quantum circuits with three properties: (1) a reduced number of qubits, (2) shorter quantum depth, and (3) fewer gates. We created novel designs of a quantum counter and a quantum semaphore to be applied to the Grover oracle to have the three properties. Through the IBM Quantum Lab service, we executed Grover’s algorithm with the novel quantum circuit designs to solve the VCP to validate the design correctness.