Depth optimization of quantum search algorithms beyond Grover's algorithm
arXiv:1908.04171 · doi:10.1103/PhysRevA.101.032346
Abstract
Grover's quantum search algorithm provides a quadratic speedup over the classical one. The computational complexity is based on the number of queries to the oracle. However, depth is a more modern metric for noisy intermediate-scale quantum computers. We propose a new depth optimization method for quantum search algorithms. We show that Grover's algorithm is not optimal in depth. We propose a quantum search algorithm, which can be divided into several stages. Each stage has a new initialization, which is a rescaling of the database. This decreases errors. The multistage design is natural for parallel running of the quantum search algorithm.
arXiv commentPublished version. 13 pages, 2 figures, 4 tables
References in corpus (27)
- Quantum Computing in the NISQ era and beyond
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Quantum Mechanics helps in searching for a needle in a haystack
- Elementary gates for quantum computation
- Logic gates at the surface code threshold: Superconducting qubits poised for fault-tolerant quantum computing
- Strengths and Weaknesses of Quantum Computing
- Quantum Amplitude Amplification and Estimation
- High-fidelity two-qubit quantum logic gates using trapped calcium-43 ions
- High-fidelity quantum logic gates using trapped-ion hyperfine qubits
- Validating quantum computers using randomized model circuits
- Grover's quantum searching algorithm is optimal
- Quantum computers can search rapidly by using almost any transformation
- Complete 3-Qubit Grover Search on a Programmable Quantum Computer
- Fixed-point quantum search with an optimal number of queries
- Near-optimal quantum circuit for Grover's unstructured search using a transverse field
- Time-Space Complexity of Quantum Search Algorithms in Symmetric Cryptanalysis
- A Review on Quantum Search Algorithms
- Variationally Learning Grover's Quantum Search Algorithm
- Simple Algorithm for Partial Quantum Search
- Generalized Quantum Search with Parallelism
- Exactness of the Original Grover Search Algorithm
- General framework for quantum search algorithms
- Optimization of Partial Search
- Quest for Fast Partial Search Algorithm
- Group Theoretical Formulation of Quantum Partial Search Algorithm
- Faster quantum searching with almost arbitrary operators
- Grover like Operator Using Only Single-Qubit Gates
Cited by in corpus (17)
- Large gradients via correlation in random parameterized quantum circuits
- Implementation of efficient quantum search algorithms on NISQ computers
- Prospect of using Grover's search in the noisy-intermediate-scale quantum-computer era
- Opening the Black Box Inside Grover's Algorithm
- Quantum Amplitude Amplification Operators
- Introducing Structure to Expedite Quantum Search
- Automatic Generation of an Efficient Less-Than Oracle for Quantum Amplitude Amplification
- Applications of Universal Parity Quantum Computation
- Hardware Efficient Quantum Search Algorithm
- Reduction of circuit depth by mapping qubit-based quantum gates to a qudit basis
- Optimization of probabilistic quantum search algorithm with a priori information
- Two-Step Quantum Search Algorithm for Solving Traveling Salesman Problems
- Benchmarking 16-element quantum search algorithms on superconducting quantum processors
- Near-deterministic quantum search algorithm without phase design
- Performance of Grover's search algorithm with diagonalizable collective noises
- Asymptotic bounds on quantum partial search algorithm and its applications to parallel search
- Asymptotic optimality of Grover-Radhakrishnan-Korepin algorithm