Hardware Efficient Quantum Search Algorithm
arXiv:2103.14196
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.
arXiv comment11 pages, 9 figures
References in corpus (10)
- Quantum Computing in the NISQ era and beyond
- Elementary gates for quantum computation
- Near-optimal quantum circuit for Grover's unstructured search using a transverse field
- Depth optimization of quantum search algorithms beyond Grover's algorithm
- Simple Algorithm for Partial Quantum Search
- Prospect of using Grover's search in the noisy-intermediate-scale quantum-computer era
- Quest for Fast Partial Search Algorithm
- Grover like Operator Using Only Single-Qubit Gates
- A family of sure-success quantum algorithms for solving a generalized Grover search problem
- Relaxed Peephole Optimization: A Novel Compiler Optimization for Quantum Circuits