Deterministic quantum search with adjustable parameters: implementations and applications

Abstract

Grover's algorithm provides a quadratic speedup over classical algorithms to search for marked elements in an unstructured database. The original algorithm is probabilistic, returning a marked element with bounded error. There are several schemes to achieve the deterministic version, by using the generalized Grover's iteration $G(\alpha ,\beta ):=S_r(\beta )S_o(\alpha )$ composed of phase oracle $S_o(\alpha )$ and phase rotation $S_r(\beta )$. However, in all the existing schemes the value range of $\alpha$ and $\beta$ is limited; for instance, in the three early schemes $\alpha$ and $\beta$ are determined by the proportion of marked states $M/N$. In this paper, we break through this limitation by presenting a search framework with adjustable parameters, which allows $\alpha$ or $\beta$ to be arbitrarily given. The significance of the framework lies not only in the expansion of mathematical form, but also in its application value, as we present two disparate problems which we are able to solve deterministically using the proposed framework, whereas previous schemes are ineffective.

arXiv commentThe title and the abstract have been slightly revised

References in corpus (12)

• Quantum Mechanics helps in searching for a needle in a haystack
• Quantum algorithms: an overview
• Tight bounds on quantum searching
• Grover Algorithm with zero theoretical failure rate
• Fixed-point quantum search with an optimal number of queries
• On Arbitrary Phases in Quantum Amplitude Amplification
• Quantum Algorithms for Element Distinctness
• Deterministic Grover search with a restricted oracle
• Staggered Quantum Walks on Graphs
• A brief introduction to quantum algorithms
• Robust Quantum Walk Search Without Knowing the Number of Marked Vertices
• Element Distinctness Revisited

Cited by in corpus (6)

• Coherence Fraction in Grover Search Algorithm
• Quantum search in many-body interacting system with long-range interaction
• Optimal exact quantum algorithm for the promised element distinctness problem
• Unifying quantum spatial search, state transfer and uniform sampling on graphs: simple and exact
• Derandomization of quantum algorithm for triangle finding
• Revisiting fixed-point quantum search: proof of the quasi-Chebyshev lemma