Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Physical Review A

Grover's quantum search algorithm and Diophantine approximation (4 pages)

Itamar Pitowsky, Shahar Dolev

Published Jan 1, 2006• 0 citations
OpenAlex

Related papers

Grover's Algorithm and Quantum Search

Kolla Bhanu Prakash

Wiley eBooks•Aug 17, 2026•0 citations

Grover’s quantum search algorithm and Diophantine approximation

Shahar Dolev, Itamar Pitowsky, Boaz Tamir

In a fundamental paper [Phys. Rev. Lett. 78, 325 (1997)] Grover showed how a quantum computer can find a single marked object in a database of size $N$ by using only $O(\sqrt{N})$ queries of the oracle that identifies the object. His result was generalized to the case of finding one object in a subset of marked elements. We consider the following computational problem: A subset of marked elements is given whose number of elements is either $M$ or $K$, our task is to determine which is the case. We show how to solve this problem with a high probability of success using iterations of Grover's basic step only, and no other algorithm. Let $m$ be the required number of iterations; we prove that under certain restrictions on the sizes of $M$ and $K$ the estimation $m<2\sqrt{N}∕(\sqrt{K}\ensuremath{-}\sqrt{M})$ obtains. This bound reproduces previous results based on more elaborate algorithms, and is known to be optimal up to a constant factor. Our method involves simultaneous Diophantine approximations, so that Grover's algorithm is conceptualized as an orbit of an ergodic automorphism of the torus. We comment on situations where the algorithm may be slow, and note the similarity between these cases and the problem of small divisors in classical mechanics.

arXiv:quant-ph/0507234•Physical Review A•Feb 3, 2006•3 citations

A Quantum Diophantine Equation Solution Finder

Lara Tatli, P. D. Stevenson

Diophantine equations are multivariate equations, usually polynomial, in which only integer solutions are admitted. A brute force method for finding solutions would be to systematically substitute possible integer values for the unknown variables and check for equality. Grover’s algorithm is a quantum search algorithm which can find marked indices in a list very efficiently. By treating the indices as the integer variables in the Diophantine equation, Grover’s algorithm can be used to find solutions in a brute force way more efficiently than classical methods. We present a hand-coded example for the simplest possible Diophantine equation, and results for a more complicated, but still simulable, equation encoded with a high-level quantum language.

arXiv:2408.11606•Mathematical Problems of Computer Science•Jun 1, 2025•0 citations

Grover’s quantum search algorithm

Samuel J. Lomonaco

Proceedings of symposia in applied mathematics•Jan 1, 2002•6 citations

Mining web data with quantum Grover search algorithm

MU Wan-jun, Zhisheng You

A kind of method of web data mining on association rule,authoritative Web pages and Weblog items with quantum Grover search algorithm and probability were given in this paper,and then the algorithm to be optimal in mining a large volumes of unsorted and unstructured Web data was dicussed.

Jisuanji gongcheng•Jan 1, 2005•1 citation

Current Status and Prospects of Quantum Search Algorithm: Grover’s Algorithm

Joonho Bae

New Physics Sae Mulli•Oct 31, 2024•0 citations
In a fundamental paper [Phys. Rev. Lett. 78, 325 (1997)] Grover showed how a quantum computer can find a single marked object in a database of size NNN by using only O(N)O(\sqrt{N})O(N​) queries of the oracle that identifies the object. His result was generalized to the case of finding one object in a subset of marked elements. We consider the following computational problem: A subset of marked elements is given whose number of elements is either MMM or KKK, our task is to determine which is the case. We show how to solve this problem with a high probability of success using iterations of Grover's basic step only, and no other algorithm. Let mmm be the required number of iterations; we prove that under certain restrictions on the sizes of MMM and KKK the estimation $m<2\sqrt{N}∕(\sqrt{K}\ensuremath{-}\sqrt{M})$ obtains. This bound reproduces previous results based on more elaborate algorithms, and is known to be optimal up to a constant factor. Our method involves simultaneous Diophantine approximations, so that Grover's algorithm is conceptualized as an orbit of an ergodic automorphism of the torus. We comment on situations where the algorithm may be slow, and note the similarity between these cases and the problem of small divisors in classical mechanics.
Diophantine equations are multivariate equations, usually polynomial, in which only integer solutions are admitted. A brute force method for finding solutions would be to systematically substitute possible integer values for the unknown variables and check for equality. Grover’s algorithm is a quantum search algorithm which can find marked indices in a list very efficiently. By treating the indices as the integer variables in the Diophantine equation, Grover’s algorithm can be used to find solutions in a brute force way more efficiently than classical methods. We present a hand-coded example for the simplest possible Diophantine equation, and results for a more complicated, but still simulable, equation encoded with a high-level quantum language.