RECORD
Hardware Efficient Quantum Search Algorithm
Quantum Physics · Submitted 26 Mar 2021
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim The circuit cost reduction leads to a remarkable improvement in the system success rates, paving the way for quantum search on NISQ machines.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
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.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Quantum computing has noteworthy speedup over classical computing by taking advantage of quantum parallelism, i.e., the superposition of states. | background 1.00 | 0.04 | 0.02 | asserted 0.98 |
| s1 | In particular, quantum search is widely used in various computationally hard problems. | background 1.00 | 0.04 | 0.02 | asserted 1.00 |
| s2 | 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. | background 1.00 | 0.03 | 0.03 | asserted 1.00 |
| s3 | 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. | background 0.54 | 0.08 | 0.03 | asserted 1.00 |
| s4 | In this paper, we propose a novel hardware efficient quantum search algorithm to overcome this challenge. | contribution 1.00 | 0.81 | 0.12 | asserted 0.98 |
| s5 | Our key idea is to replace the global diffusion operation with low-cost local diffusions. | method 0.79 | 0.72 | 0.07 | asserted 0.98 |
| s6 | 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. | result 0.99 | 0.94 | 0.60 | asserted 1.00 |
| s7 | The circuit cost reduction leads to a remarkable improvement in the system success rates, paving the way for quantum search on NISQ machines. | interpretation 0.77 | 0.81 | 0.72 | asserted 0.95 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
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.
Human review
References
How the literature uses it
8 arXiv papers cite this in 16 sentences
Papers citing it · 14 sentences without a confident label
Cites it as background 2 papers
-
An oracle can be thought as a black box performing a function that is used as an input by another algorithm [ref] .
Automatic Generation of an Efficient Less-Than Oracle for Quantum Amplitude Amplification · Background · 0.92
-
During the last twenty years, many variants of Grover's algorithm have been proposed [ref] .
Quantum search on noisy intermediate-scale quantum devices · Introduction · 0.89
What it cites
Uses the method or tool of 1 paper
-
We use the highest Qiskit compiler optimization level associated with the relaxed peephole optimization [ref] to optimize the circuit and reduce the circuit depth.
Relaxed Peephole Optimization: A Novel Compiler Optimization for Quantum Circuits · Methodology · 1.00
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.