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:2406.13785

Efficient Implementation of a Quantum Search Algorithm for Arbitrary N

Alok Shukla, Prakash Vedula

Published Jun 19, 2024• 0 citations
arXivHTMLPDF

Abstract

This paper presents an enhancement to Grover's search algorithm for instances where the number of items (or the size of the search problem) $N$ is not a power of 2. By employing an efficient algorithm for the preparation of uniform quantum superposition states over a subset of the computational basis states, we demonstrate that a considerable reduction in the number of oracle calls (and Grover's iterations) can be achieved in many cases. For special cases (i.e., when $N$ is of the form such that it is slightly greater than an integer power of 2), the reduction in the number of oracle calls (and Grover's iterations) asymptotically approaches 29.33\%. This improvement is significant compared to the traditional Grover's algorithm, which handles such cases by rounding $N$ up to the nearest power of 2. The key to this improvement is our algorithm for the preparation of uniform quantum superposition states over a subset of the computational basis states, which requires gate complexity and circuit depth of only $ O (\log_2 (N)) $, without using any ancilla qubits.

DOI
10.48550/arxiv.2406.13785

Related papers

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

Optimization of a Quantum Subset Sum Oracle

Benoit, Angelo, Schwartz, Sam, Ron K. Cytron

We investigate the implementation of an oracle for the Subset Sum problem for quantum search using Grover's algorithm. Our work concerns reducing the number of qubits, gates, and multi-controlled gates required by the oracle. We describe the compilation of a Subset Sum instance into a quantum oracle, using a Python library we developed for Qiskit and have published in GitHub. We then present techniques to conserve qubits and gates along with experiments showing their effectiveness on random instances of Subset Sum. These techniques include moving from fixed to varying-width arithmetic, using partial sums of a set's integers to determine specific integer widths, and sorting the set to obtain provably the most efficient partial sums. We present a new method for computing bit-string comparisons that avoids arbitrarily large multiple-control gates, and we introduce a simple modification to the oracle that allows for approximate solutions to the Subset Sum problem via Grover search.

arXiv:2410.01775•Oct 2, 2024•0 citations

Implementation of Efficient Quantum Computing Algorithm for Searching

Nirhali Atharva, Malwade Rohit, P. Akshay +2 more

The K-SAT problem is a fundamental challenge in computational theory, widely used in artificial intelligence, cryptography, and optimization. Classical algorithms struggle with exponential time complexity, making them inefficient for large-scale instances. In this research, we propose an efficient quantum computing approach based on Grover’s algorithm to enhance the search process for satisfiable solutions in K-SAT problems. Our implementation leverages quantum superposition and amplitude amplification to explore multiple possible solutions simultaneously, reducing the search complexity from O (2ⁿ) in classical methods to O(√2ⁿ) in quantum computing. We design a quantum oracle that encodes the K-SAT clauses and integrates it into Grover’s iterative search framework. The performance is evaluated through Qiskit simulations, demonstrating a significant improvement in search efficiency compared to classical brute-force techniques. The results highlight the potential of quantum algorithms in solving complex combinatorial problems with enhanced speed and accuracy. This study contributes to the development of quantum-accelerated optimization methods, paving the way for real-world applications in machine learning, cryptanalysis, and large-scale data processing.

International Research Journal on Advanced Engineering Hub (IRJAEH)•May 21, 2025•0 citations

Automatic generation of efficient oracles: The less-than case

Javier Sanchez‐Rivero, Daniel Talaván, José Manuel García-Alonso +2 more

Grover’s algorithm is a well-known contribution to quantum computing. It searches one value within an unordered sequence. A fundamental part of this algorithm is the so-called oracle, a quantum circuit that marks the quantum state corresponding to the desired value. In this work we present a classical algorithm that builds an oracle that performs a less-than operation, marking states representing natural numbers smaller than a given one. Results are shown to prove its functionality. This lessthan oracle implementation works on any number of qubits and does not require any ancilla qubits. Regarding depth, the proposed implementation is compared with Qiskit automatic method, Diagonal. We show that the depth of our less-than oracle implementation is always lower. In addition, a comparison with another method for oracle generation in terms of gate count is also conducted to prove the efficiency of our method. The result presented here is part of a research work that aims to achieve reusable quantum operations that can be composed to perform more complex ones.

Journal of Systems and Software•Sep 4, 2024•5 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 Algorithms for Constraint Satisfaction and Optimization Problems Using Grover's Search and Quantum Walk Algorithms with Advanced Oracle Design

Abdirahman Alasow

The field of quantum computing has emerged as a powerful tool for solving and optimizing combinatorial optimization problems. To solve many real-world problems with many variables and possible solutions for constraint satisfaction and optimization problems, the required number of qubits of scalable hardware for quantum computing is the bottleneck in the current generation of quantum computers. In this dissertation, we will demonstrate advanced, scalable building blocks for the quantum search algorithms that have been implemented in Grover's search algorithm and the quantum walk algorithm. The scalable building blocks are used to reduce the required number of qubits in the design. The proposed architecture effectively scales and optimizes the number of qubits needed to solve large problems with a limited number of qubits. Thus, scaling and optimizing the number of qubits that can be accommodated in quantum algorithm design directly reflect on performance. Also, accuracy is a key performance metric related to how accurately one can measure quantum states. The search space of quantum search algorithms is traditionally created by using the Hadamard operator to create superposition. However, creating superpositions for problems that do not need all superposition states decreases the accuracy of the measured states. We present an efficient quantum circuit design that the user has control over to create the subspace superposition states for the search space as needed. Using only the subspace states as superposition states of the search space will increase the rate of correct solutions. In this dissertation, we will present the implementation of practical problems for Grover's search algorithm and quantum walk algorithm in logic design, logic puzzles, and machine learning problems such as SAT, MAX-SAT, XOR-SAT, and like SAT problems in EDA, and mining frequent patterns for association rule mining.

•Apr 15, 2024•0 citations
This paper presents an enhancement to Grover's search algorithm for instances where the number of items (or the size of the search problem) NNN is not a power of 2. By employing an efficient algorithm for the preparation of uniform quantum superposition states over a subset of the computational basis states, we demonstrate that a considerable reduction in the number of oracle calls (and Grover's iterations) can be achieved in many cases. For special cases (i.e., when NNN is of the form such that it is slightly greater than an integer power of 2), the reduction in the number of oracle calls (and Grover's iterations) asymptotically approaches 29.33%. This improvement is significant compared to the traditional Grover's algorithm, which handles such cases by rounding NNN up to the nearest power of 2. The key to this improvement is our algorithm for the preparation of uniform quantum superposition states over a subset of the computational basis states, which requires gate complexity and circuit depth of only O(log⁡2(N))O (\log_2 (N))O(log2​(N)), without using any ancilla qubits.
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.
We investigate the implementation of an oracle for the Subset Sum problem for quantum search using Grover's algorithm. Our work concerns reducing the number of qubits, gates, and multi-controlled gates required by the oracle. We describe the compilation of a Subset Sum instance into a quantum oracle, using a Python library we developed for Qiskit and have published in GitHub. We then present techniques to conserve qubits and gates along with experiments showing their effectiveness on random instances of Subset Sum. These techniques include moving from fixed to varying-width arithmetic, using partial sums of a set's integers to determine specific integer widths, and sorting the set to obtain provably the most efficient partial sums. We present a new method for computing bit-string comparisons that avoids arbitrarily large multiple-control gates, and we introduce a simple modification to the oracle that allows for approximate solutions to the Subset Sum problem via Grover search.
The K-SAT problem is a fundamental challenge in computational theory, widely used in artificial intelligence, cryptography, and optimization. Classical algorithms struggle with exponential time complexity, making them inefficient for large-scale instances. In this research, we propose an efficient quantum computing approach based on Grover’s algorithm to enhance the search process for satisfiable solutions in K-SAT problems. Our implementation leverages quantum superposition and amplitude amplification to explore multiple possible solutions simultaneously, reducing the search complexity from O (2ⁿ) in classical methods to O(√2ⁿ) in quantum computing. We design a quantum oracle that encodes the K-SAT clauses and integrates it into Grover’s iterative search framework. The performance is evaluated through Qiskit simulations, demonstrating a significant improvement in search efficiency compared to classical brute-force techniques. The results highlight the potential of quantum algorithms in solving complex combinatorial problems with enhanced speed and accuracy. This study contributes to the development of quantum-accelerated optimization methods, paving the way for real-world applications in machine learning, cryptanalysis, and large-scale data processing.
Grover’s algorithm is a well-known contribution to quantum computing. It searches one value within an unordered sequence. A fundamental part of this algorithm is the so-called oracle, a quantum circuit that marks the quantum state corresponding to the desired value. In this work we present a classical algorithm that builds an oracle that performs a less-than operation, marking states representing natural numbers smaller than a given one. Results are shown to prove its functionality. This lessthan oracle implementation works on any number of qubits and does not require any ancilla qubits. Regarding depth, the proposed implementation is compared with Qiskit automatic method, Diagonal. We show that the depth of our less-than oracle implementation is always lower. In addition, a comparison with another method for oracle generation in terms of gate count is also conducted to prove the efficiency of our method. The result presented here is part of a research work that aims to achieve reusable quantum operations that can be composed to perform more complex ones.
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.
The field of quantum computing has emerged as a powerful tool for solving and optimizing combinatorial optimization problems. To solve many real-world problems with many variables and possible solutions for constraint satisfaction and optimization problems, the required number of qubits of scalable hardware for quantum computing is the bottleneck in the current generation of quantum computers. In this dissertation, we will demonstrate advanced, scalable building blocks for the quantum search algorithms that have been implemented in Grover's search algorithm and the quantum walk algorithm. The scalable building blocks are used to reduce the required number of qubits in the design. The proposed architecture effectively scales and optimizes the number of qubits needed to solve large problems with a limited number of qubits. Thus, scaling and optimizing the number of qubits that can be accommodated in quantum algorithm design directly reflect on performance. Also, accuracy is a key performance metric related to how accurately one can measure quantum states. The search space of quantum search algorithms is traditionally created by using the Hadamard operator to create superposition. However, creating superpositions for problems that do not need all superposition states decreases the accuracy of the measured states. We present an efficient quantum circuit design that the user has control over to create the subspace superposition states for the search space as needed. Using only the subspace states as superposition states of the search space will increase the rate of correct solutions. In this dissertation, we will present the implementation of practical problems for Grover's search algorithm and quantum walk algorithm in logic design, logic puzzles, and machine learning problems such as SAT, MAX-SAT, XOR-SAT, and like SAT problems in EDA, and mining frequent patterns for association rule mining.