A Generalization of Grover's Algorithm

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^{α}], where D is the search space dimension, M is the number of target states, and α≈1, which is close to the optimal scaling.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^{α}], where D is the search space dimension, M is the number of target states, and α≈1, which is close to the optimal scaling.

arXiv:1801.02809Physical Review LettersFeb 7, 201824 citations

Grover's Algorithm with Diffusion and Amplitude Steering

Robert Singleton, Rogers, Michael L, David L Ostby

We review the basic theoretical underpinnings of the Grover algorithm, providing a rigorous and well motivated derivation. We then present a generalization of Grover's algorithm that searches an arbitrary subspace of the multi-dimensional Hilbert space using a diffusion operation and an amplitude amplification procedure that has been biased by unitary {\em steering operators}. We also outline a generalized Grover's algorithm that takes into account higher level correlations that could exist between database elements. In the traditional Grover algorithm, the Hadamard gate selects a uniform sample of computational basis elements when performing the phase selection and diffusion. In contrast, steered operators bias the selection process, thereby providing more flexibility in selecting the target state. Our method is a generalization of the recently proposal pattern matching algorithm of Hiroyuki et al..We review the basic theoretical underpinnings of the Grover algorithm, providing a rigorous and well motivated derivation. We then present a generalization of Grover's algorithm that searches an arbitrary subspace of the multi-dimensional Hilbert space using a diffusion operation and an amplitude amplification procedure that has been biased by unitary {\em steering operators}. We also outline a generalized Grover's algorithm that takes into account higher level correlations that could exist between database elements. In the traditional Grover algorithm, the Hadamard gate selects a uniform sample of computational basis elements when performing the phase selection and diffusion. In contrast, steered operators bias the selection process, thereby providing more flexibility in selecting the target state. Our method is a generalization of the recently proposal pattern matching algorithm of Hiroyuki et al..

arXiv:2110.11163Oct 21, 20212 citations

Discrete Time Multi-particle Grover Search

Christopher Um

Grover's algorithm is a quantum search algorithm that produces a quadratic speedup compared to its classical analog, a brute-force algorithm, and has a complexity of $\mathcal{O}(\sqrt{N})$ . Past works have shown that Grover's algorithm can asymptotically be improved by generalizing the number of marked sites. I examine Grover's algorithm when the number of searching particles is generalized in discrete time setting, which allows to understand the search algorithm in terms of “interactions” between particles. I provide a novel design of Grover with appended interaction terms to analyze $\mathcal{O}$ as $N\rightarrow\infty$ . I utilize the eigenvalue perturbation theory to deduce the optimal interaction condition and show that the condition results in an asymptotic improvement denendent upon the number of particles.Grover's algorithm is a quantum search algorithm that produces a quadratic speedup compared to its classical analog, a brute-force algorithm, and has a complexity of$\mathcal{O}(\sqrt{N})$. Past works have shown that Grover's algorithm can asymptotically be improved by generalizing the number of marked sites. I examine Grover's algorithm when the number of searching particles is generalized in discrete time setting, which allows to understand the search algorithm in terms of “interactions” between particles. I provide a novel design of Grover with appended interaction terms to analyze$\mathcal{O}$as$N\rightarrow\infty$. I utilize the eigenvalue perturbation theory to deduce the optimal interaction condition and show that the condition results in an asymptotic improvement denendent upon the number of particles.

International Conference on Communication and Electronics Systems (ICCES)Jul 8, 20210 citations

Grover's algorithm is a quantum search algorithm that produces a quadratic speedup compared to its classical analog, a brute-force algorithm, and has a complexity of

\mathcal{O}(\sqrt{N})

. Past works have shown that Grover's algorithm can asymptotically be improved by generalizing the number of marked sites. I examine Grover's algorithm when the number of searching particles is generalized in discrete time setting, which allows to understand the search algorithm in terms of “interactions” between particles. I provide a novel design of Grover with appended interaction terms to analyze

\mathcal{O}

N\rightarrow\infty

. I utilize the eigenvalue perturbation theory to deduce the optimal interaction condition and show that the condition results in an asymptotic improvement denendent upon the number of particles.