Depth optimization of quantum search algorithms beyond Grover's algorithm
Kun Zhang, V. E. Korepin
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 depth optimization method for the quantum search algorithm. 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.
Topics & Concepts
AlgorithmQuantum algorithmInitializationSpeedupComputer scienceQuantum sortSearch algorithmOracleQuantum phase estimation algorithmQuantumQuantum computerMetric (unit)Beam searchParallel computingQuantum error correctionPhysicsProgramming languageOperations managementQuantum mechanicsEconomicsSoftware engineeringQuantum Computing Algorithms and ArchitectureQuantum Information and CryptographyComputability, Logic, AI Algorithms