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

arXiv:1912.02207 · Quantum

Playing Pool with |ψ⟩ : from Bouncing Billiards to Quantum Search

Adam R. Brown

Published Nov 2, 2020• 13 citations
arXivHTMLPDF

Abstract

In ``Playing Pool with π '' \cite{Galperin}, Galperin invented an extraordinary method to learn the digits of π by counting the collisions of billiard balls. Here I demonstrate an exact isomorphism between Galperin's bouncing billiards and Grover's algorithm for quantum search. This provides an illuminating way to visualize Grover's algorithm.

DOI
10.22331/q-2020-11-02-357

Related papers

Similarity between Grover’s quantum search algorithm and classical two-body collisions

Jingfu Zhang, Zhi-Heng Lu

By studying the diffusion operator in Grover’s quantum search algorithm, we find an analogy between quantum searching and classical, elastic two-body collisions. We exploit this mathematical analogy using a thought experiment involving multiple collisions between two bodies to help illuminate why Grover’s quantum search algorithm works. Related issues are discussed.

arXiv:quant-ph/0110077•American Journal of Physics•Dec 20, 2002•9 citations

Grover's quantum search algorithm

Samuel J. Lomonaco

This paper is a written version of a one hour lecture given on Lov Grover's database search algorithm. Table Of Contents 1 ... Problem Definition 2 ... The quantum mechanical perspective 3 ... Properties of the inversion I_|psi> 4 ... The method in Lov's "madness" 5 ... Summary of Grover's algorithm 6 ... An example of Grover's algorithm References

arXiv:quant-ph/0010040•Oct 10, 2000•5 citations

A Review of Grover's Search Algorithm: Applications and Modifications

Ela Demirci, Emre Atlıer Olca

This study investigates the applications and adaptations of the Grover's search algorithm, an algorithm that uses quantum technologies to provide quadratic speedup while searching unsorted data. Through extensive literature review, the applications of Grover's algorithm such as database search, machine learning, cryptography, and optimization is explored in order to further understand areas open to alteration in the algorithm. Visuals are provided with the aim of enhancing the comprehension of Grover's algorithm. This study underscores how various components of Grover's search-like the oracle, diffusion operator, and iteration count-can be modified to solve complex problems more efficiently than classical search algorithms. A table generalizing aspects of modification and each of their benefits is given as an output. The growing importance of quantum technologies and the United Nations' selection of 2025 as the International Year of Quantum Science and Technology makes this research timely.

International Artificial Intelligence and Data Processing Symposium (IDAP)•Sep 6, 2025•4 citations

Quantum Machine Learning: A Case Study of Grover’s Algorithm

Bikram Khanal, Pablo Rivas, Javier Orduz +1 more

The complexity of searching algorithms in classical computing is a perpetual researched field. Quantum computers and quantum algorithms can compute these problems faster, and, in addition, machine learning implementation could provide a prominent way to boost quantum technology. We call quantum machine learning to this novel set of tools coming from artificial intelligence and quantum mechanics. To achieve our purpose, we focus on applications on quantum machine learning; in particular, we propose a review and exploration of topics such as variational quantum algorithms, kernel methods, and a review of Grover’s algorithm (GA) as a quantum classifier. We start with the GA exploration to achieve this goal, which is a quantum search algorithm that achieves quadratic speedup over optimal classical search implementation. This paper implements a GA exploration that includes a concept summary and implementation, considering only AND, XOR, and OR gates. We also discuss potential in quantum machine learning.

International Conference on Computational Science and Computational Intelligence (CSCI)•Dec 1, 2021•16 citations

Quantum Search Algorithm

Che‐Ming Li, Jin-Yuan Hsieh, Der-San Chuu

IntroductionFor a search problem associated with a unsorted database, the remarkable Grover's quantum algorithm (1) provides a quadratic speedup over its classical counterpart.The search problem can be described as follows: for a given function f , there exists one unknown element in the set {0, 1, ..., N -1} that satisfies f (x)=-1, say x = τ, whereas the other N -1o n e sg i v e f (x)=1.How many times of evaluations of f are required to determine the element τ for f (τ)=-1?Through a conventional algorithm, one needs O(N) trials to achieve this aim.How about the utility of quantum algorithm for the search?For the scenario in the quantum world, the search problem can be rephrased in the quantum mechanical language: for a given unitary operator I τ , that is sometimes called the oracle operator, and a set of state vectors (orthonormal basis): s = {|0 , |1 , ..., |N -1 }, I τ |x = |x for all states in the set except I τ |x = -|x for x = τ.H owma n yqueriesofI τ are required to determine |τ ?By Grover's algorithm, one needs only O( √ N) quantum mechanical steps to find the marked state |τ out.It has been shown that Grover's algorithm is optimal since it needs minimal oracle calls to perform a quantum search (2).The quantum searching process will be briefly reviewed as follows.The first step of Grover's algorithm is to prepare a superposition state of all elements with uniform probability amplitude:Then apply the Grover kernel G = -I η I τ to |s ,w h er eI η is a unitary operator and contains no bias against the marked state.For large N,a f t e ra b o u tm = π √ N/4 repetitions of G operations, the probability to observe |τ is close to one, i.e., G m |s ∼ |τ .( 2 ) Since every single G involves one query of I τ ,onlyO( √ N) searching steps are required for a quantum search task.In what follows, we will first investigate on the general SU(2) formulation for the kernel of Grover's searching operator G.The discussions of quantum searching certainty, robustness, and the analog analogue version of the Grover's algorithm will be given afterwards.

InTech eBooks•Apr 26, 2011•1 citation

PHASE MATCHING IN FIXED-POINT QUANTUM SEARCH ALGORITHM

Hong‐Fu Wang, Shou Zhang, Yongfang Zhao

We investigate the phase matching problem in the fixed-point quantum search algorithm proposed by Grover [Phys. Rev. Lett.95 (2005) 150501]. We show that the optimal phase shift is π/3.61, which replaces the π/3 phase shift in fixed-point quantum search algorithm. The π/3.61-phase algorithm can be achieved in [Formula: see text] with the success probability of at least 94.11%, which offsets disadvantage that the success probability of getting correct results usually decreases with the increase of marked items when original Grover quantum search algorithm is applied to search an unordered database. In the meantime, this work also indicates that Grover quantum search algorithm is considerably robust to certain kinds of perturbations and is robust against modest noise in the initialization procedure.

International Journal of Quantum Information•Sep 1, 2009•2 citations
In ``Playing Pool with π '' \cite{Galperin}, Galperin invented an extraordinary method to learn the digits of π by counting the collisions of billiard balls. Here I demonstrate an exact isomorphism between Galperin's bouncing billiards and Grover's algorithm for quantum search. This provides an illuminating way to visualize Grover's algorithm.
This study investigates the applications and adaptations of the Grover's search algorithm, an algorithm that uses quantum technologies to provide quadratic speedup while searching unsorted data. Through extensive literature review, the applications of Grover's algorithm such as database search, machine learning, cryptography, and optimization is explored in order to further understand areas open to alteration in the algorithm. Visuals are provided with the aim of enhancing the comprehension of Grover's algorithm. This study underscores how various components of Grover's search-like the oracle, diffusion operator, and iteration count-can be modified to solve complex problems more efficiently than classical search algorithms. A table generalizing aspects of modification and each of their benefits is given as an output. The growing importance of quantum technologies and the United Nations' selection of 2025 as the International Year of Quantum Science and Technology makes this research timely.
The complexity of searching algorithms in classical computing is a perpetual researched field. Quantum computers and quantum algorithms can compute these problems faster, and, in addition, machine learning implementation could provide a prominent way to boost quantum technology. We call quantum machine learning to this novel set of tools coming from artificial intelligence and quantum mechanics. To achieve our purpose, we focus on applications on quantum machine learning; in particular, we propose a review and exploration of topics such as variational quantum algorithms, kernel methods, and a review of Grover’s algorithm (GA) as a quantum classifier. We start with the GA exploration to achieve this goal, which is a quantum search algorithm that achieves quadratic speedup over optimal classical search implementation. This paper implements a GA exploration that includes a concept summary and implementation, considering only AND, XOR, and OR gates. We also discuss potential in quantum machine learning.
IntroductionFor a search problem associated with a unsorted database, the remarkable Grover's quantum algorithm (1) provides a quadratic speedup over its classical counterpart.The search problem can be described as follows: for a given function f , there exists one unknown element in the set {0, 1, ..., N -1} that satisfies f (x)=-1, say x = τ, whereas the other N -1o n e sg i v e f (x)=1.How many times of evaluations of f are required to determine the element τ for f (τ)=-1?Through a conventional algorithm, one needs O(N) trials to achieve this aim.How about the utility of quantum algorithm for the search?For the scenario in the quantum world, the search problem can be rephrased in the quantum mechanical language: for a given unitary operator I τ , that is sometimes called the oracle operator, and a set of state vectors (orthonormal basis): s = {|0 , |1 , ..., |N -1 }, I τ |x = |x for all states in the set except I τ |x = -|x for x = τ.H owma n yqueriesofI τ are required to determine |τ ?By Grover's algorithm, one needs only O( √ N) quantum mechanical steps to find the marked state |τ out.It has been shown that Grover's algorithm is optimal since it needs minimal oracle calls to perform a quantum search (2).The quantum searching process will be briefly reviewed as follows.The first step of Grover's algorithm is to prepare a superposition state of all elements with uniform probability amplitude:Then apply the Grover kernel G = -I η I τ to |s ,w h er eI η is a unitary operator and contains no bias against the marked state.For large N,a f t e ra b o u tm = π √ N/4 repetitions of G operations, the probability to observe |τ is close to one, i.e., G m |s ∼ |τ .( 2 ) Since every single G involves one query of I τ ,onlyO( √ N) searching steps are required for a quantum search task.In what follows, we will first investigate on the general SU(2) formulation for the kernel of Grover's searching operator G.The discussions of quantum searching certainty, robustness, and the analog analogue version of the Grover's algorithm will be given afterwards.
We investigate the phase matching problem in the fixed-point quantum search algorithm proposed by Grover [Phys. Rev. Lett.95 (2005) 150501]. We show that the optimal phase shift is π/3.61, which replaces the π/3 phase shift in fixed-point quantum search algorithm. The π/3.61-phase algorithm can be achieved in [Formula: see text] with the success probability of at least 94.11%, which offsets disadvantage that the success probability of getting correct results usually decreases with the increase of marked items when original Grover quantum search algorithm is applied to search an unordered database. In the meantime, this work also indicates that Grover quantum search algorithm is considerably robust to certain kinds of perturbations and is robust against modest noise in the initialization procedure.