Generalized Grover's algorithm for multiple phase inversion states

Abstract

Grover's algorithm is a quantum search algorithm that proceeds by repeated applications of the Grover operator and the Oracle until the state evolves to one of the target states. In the standard version of the algorithm, the Grover operator inverts the sign on only one state. Here we provide an exact solution to the problem of performing Grover's search where the Grover operator inverts the sign on N states. We show the underlying structure in terms of the eigenspectrum of the generalized Hamiltonian, and derive an appropriate initial state to perform the Grover evolution. This allows us to use the quantum phase estimation algorithm to solve the search problem in this generalized case, completely bypassing the Grover algorithm altogether. We obtain a time complexity of this case of $\sqrt{(}D/M^{\alpha })$ where D is the search space dimension, M is the number of target states, and $\alpha$ ~ 1, which is close to the optimal scaling.

References in corpus (14)

• Quantum information with continuous variables
• Strengths and Weaknesses of Quantum Computing
• Grover's quantum searching algorithm is optimal
• Grover Algorithm with zero theoretical failure rate
• Fixed-point quantum search with an optimal number of queries
• A different kind of quantum search
• Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer
• Macroscopic quantum computation using Bose-Einstein condensates
• Macroscopic quantum information processing using spin coherent states
• Single quantum querying of a database
• A Family of Grover's Quantum Searching Algorithms
• Experimental realization of a continuous version of the Grover algorithm
• Control of non-controllable quantum systems: A quantum control algorithm based on Grover iteration
• Grover like Operator Using Only Single-Qubit Gates

Cited by in corpus (9)

• Information Geometry Aspects of Minimum Entropy Production Paths from Quantum Mechanical Evolutions
• Decrease of Fisher information and the information geometry of evolution equations for quantum mechanical probability amplitudes
• Hybrid quantum-classical unsupervised data clustering based on the self-organizing feature map
• Statistical Approach to Quantum Phase Estimation
• Information Geometric Aspects of Probability Paths with Minimum Entropy Production for Quantum State Evolution
• Complementary-multiphase quantum search for all numbers of target items
• Quadratic Quantum Speedup for Perceptron Training
• Optimal quantum spatial search with one-dimensional long-range interactions
• Exact quantum search based on analytical multiphase matching for known number of target items and the experimental demonstration on IBM Q