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:1512.07550 · Quantum Information and Computation

Optimizing the number of gates in quantum search

Srinivasan Arunachalam, Ronald de Wolf

Published Mar 1, 2017• 7 citations
arXivHTMLPDF

Abstract

In its usual form, Grover’s quantum search algorithm uses O( √ N) queries and O( √ N log N) other elementary gates to find a solution in an N-bit database. Grover in 2002 showed how to reduce the number of other gates to O( √ N log log N) for the special case where the database has a unique solution, without significantly increasing the number of queries. We show how to reduce this further to O( √ N log(r) N) gates for every constant r, and sufficiently large N. This means that, on average, the circuits between two queries barely touch more than a constant number of the log N qubits on which the algorithm acts. For a very large N that is a power of 2, we can choose r such that the algorithm uses essentially the minimal number π 4 √ N of queries, and only O( √ N log(log? N)) other gates.

DOI
10.26421/qic17.3-4-4

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

Grover's search algorithm: An optical approach

P. G. Kwiat, J. R. Mitchell, P. D. D. Schwindt +1 more

The essential operations of a quantum computer can be accomplished using solely optical elements, with different polarization or spatial modes representing the individual qubits. We present a simple all-optical implementation of Grover's algorithm for efficient searching, in which a database of four elements is searched with a single query. By ‘compiling’ the actual set-up, we have reduced the required number of optical elements from 24 to only 12. We discuss the extension to large databases, and the limitations of these techniques.

arXiv:quant-ph/9905086•Journal of Modern Optics•Feb 1, 2000•185 citations

Grover's search algorithm: an optical approach

Paul G. Kwiat, J. R. Mitchell, Peter D. D. Schwindt +1 more

The essential operations of a quantum computer can be accomplished using solely optical elements, with different polarization or spatial modes representing the individual qubits. We present a simple all-optical implementation of Grover's algorithm for efficient searching, in which a database of four elements is searched with a single query. By ‘compiling’ the actual set-up, we have reduced the required number of optical elements from 24 to only 12. We discuss the extension to large databases, and the limitations of these techniques.

Journal of Modern Optics•Feb 15, 2000•19 citations

Grover Adaptive Search With Fewer Queries

Hiroaki Ominato, Takahiro Ohyama, Koichiro Yamaguchi

In binary optimization problems, where the goal is to find the input$\boldsymbol {x}$that minimizes a given objective function, Grover adaptive search (GAS) is a well-known quantum algorithm that provides quadratic speedup when compared with the brute-force approaches of classical computers. GAS calls a renowned quantum search algorithm, Grover search (GS), as a subroutine to search for inputs with function values less than the threshold value. If such an input is found, the threshold value is updated with the function value and the search targets are narrowed. To search efficiently for a solution, an appropriate number of queries must be selected to amplify the desired state of the GS in each step. This paper discusses this issue and proposes a new method for selecting the number of queries and provides proof that our method achieves quadratic speedup as well as the original GAS. Furthermore, the simulation results for 40-bit problems confirm that our method allows an optimal solution with 22% fewer queries than the standard method, thus offering the possibility of significantly reduced computation times for combinatorial optimization problems.

IEEE Access•Jan 1, 2024•4 citations

Modelling of Grover’s quantum search algorithms: implementations of Simple quantum simulators on classical computers

Sergey Victorovich Ulyanov, Andrey G. Reshetnikov, Olga Tyatyushkina

Models of Grover’s search algorithm is reviewed to build the foundation for the other algorithms. Thereafter, some preliminary modifications of the original algorithms by others are stated, that increases the applicability of the search procedure. A general quantum computation on an isolated system can be represented by a unitary matrix. In order to execute such a computation on a quantum computer, it is common to decompose the unitary into a quantum circuit, i.e., a sequence of quantum gates that can be physically implemented on a given architecture. There are different universal gate sets for quantum computation. Here we choose the universal gate set consisting of CNOT and single-qubit gates. We measure the cost of a circuit by the number of CNOT gates as they are usually more difficult to implement than single qubit gates and since the number of single-qubit gates is bounded by about twice the number of CNOT’s.

System Analysis in Science and Education•Sep 30, 2020•4 citations

Optimization of partial search

V. E. Korepin

A quantum Grover search algorithm can find a target item in a database faster than any classical algorithm. One can trade accuracy for speed and find a part of the database (a block) containing the target item even faster; this is partial search. A partial search algorithm was recently suggested by Grover and Radhakrishnan. Here we optimize it. Efficiency of the search algorithm is measured by the number of queries to the oracle. The author suggests a new version of the Grover–Radhakrishnan algorithm which uses a minimal number of such queries. The algorithm can run on the same hardware that is used for the usual Grover algorithm.

arXiv:quant-ph/0503238•Journal of Physics A Mathematical and General•Oct 19, 2005•27 citations
In its usual form, Grover’s quantum search algorithm uses O( √ N) queries and O( √ N log N) other elementary gates to find a solution in an N-bit database. Grover in 2002 showed how to reduce the number of other gates to O( √ N log log N) for the special case where the database has a unique solution, without significantly increasing the number of queries. We show how to reduce this further to O( √ N log(r) N) gates for every constant r, and sufficiently large N. This means that, on average, the circuits between two queries barely touch more than a constant number of the log N qubits on which the algorithm acts. For a very large N that is a power of 2, we can choose r such that the algorithm uses essentially the minimal number π 4 √ N of queries, and only O( √ N log(log? N)) other gates.
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.
The essential operations of a quantum computer can be accomplished using solely optical elements, with different polarization or spatial modes representing the individual qubits. We present a simple all-optical implementation of Grover's algorithm for efficient searching, in which a database of four elements is searched with a single query. By ‘compiling’ the actual set-up, we have reduced the required number of optical elements from 24 to only 12. We discuss the extension to large databases, and the limitations of these techniques.
The essential operations of a quantum computer can be accomplished using solely optical elements, with different polarization or spatial modes representing the individual qubits. We present a simple all-optical implementation of Grover's algorithm for efficient searching, in which a database of four elements is searched with a single query. By ‘compiling’ the actual set-up, we have reduced the required number of optical elements from 24 to only 12. We discuss the extension to large databases, and the limitations of these techniques.
In binary optimization problems, where the goal is to find the inputx\boldsymbol {x}xthat minimizes a given objective function, Grover adaptive search (GAS) is a well-known quantum algorithm that provides quadratic speedup when compared with the brute-force approaches of classical computers. GAS calls a renowned quantum search algorithm, Grover search (GS), as a subroutine to search for inputs with function values less than the threshold value. If such an input is found, the threshold value is updated with the function value and the search targets are narrowed. To search efficiently for a solution, an appropriate number of queries must be selected to amplify the desired state of the GS in each step. This paper discusses this issue and proposes a new method for selecting the number of queries and provides proof that our method achieves quadratic speedup as well as the original GAS. Furthermore, the simulation results for 40-bit problems confirm that our method allows an optimal solution with 22% fewer queries than the standard method, thus offering the possibility of significantly reduced computation times for combinatorial optimization problems.
Models of Grover’s search algorithm is reviewed to build the foundation for the other algorithms. Thereafter, some preliminary modifications of the original algorithms by others are stated, that increases the applicability of the search procedure. A general quantum computation on an isolated system can be represented by a unitary matrix. In order to execute such a computation on a quantum computer, it is common to decompose the unitary into a quantum circuit, i.e., a sequence of quantum gates that can be physically implemented on a given architecture. There are different universal gate sets for quantum computation. Here we choose the universal gate set consisting of CNOT and single-qubit gates. We measure the cost of a circuit by the number of CNOT gates as they are usually more difficult to implement than single qubit gates and since the number of single-qubit gates is bounded by about twice the number of CNOT’s.
A quantum Grover search algorithm can find a target item in a database faster than any classical algorithm. One can trade accuracy for speed and find a part of the database (a block) containing the target item even faster; this is partial search. A partial search algorithm was recently suggested by Grover and Radhakrishnan. Here we optimize it. Efficiency of the search algorithm is measured by the number of queries to the oracle. The author suggests a new version of the Grover–Radhakrishnan algorithm which uses a minimal number of such queries. The algorithm can run on the same hardware that is used for the usual Grover algorithm.