• Numerous Needles.
In the duality, the mass of the small ball is 1 because there is 1 correct answer (i.e. 1 basis
state whose sign is flipped by the oracle), and the mass of the heavy ball is M = d − 1
because there are d − 1 incorrect answers. If we were to adapt the Grover method to an
oracle with n correct answers (n needles in the haystack) and d − n incorrect answers,
this would correspond to a mass n for the small ball and mass d − n for the heavy ball.
It is clear that if you double the mass of both balls, the number of collisions does not
change. Only the ratio matters. This is dual to the slightly less obvious fact that the
runtime of the Grover task depends only on the ratio of the number of correct answers to
the number of incorrect answers #
queries
= b
π
4
p
(d − n)/n c.
Galperin’s π-calculating plan displays a wanton disregard for engineering practicalities.
It requires that we overcome friction, overcome inelasticities, overcome the blurring effects of
quantum mechanics, and then having overcome all these things it requires exceptional patience,
because even pedestrian initial velocities provoke catastrophic corrections from special relativity.
Nevertheless, whatever the shortcomings of billiard balls as tools for calculating π, the results
of this paper suggest a tool that is even worse. We might start with a qu(100
N
+ 1)it, and then
step-by-step enact the quantum mirror of Galperin’s method, mirroring each velocity with an
amplitude, mirroring each billiard collision with a unitary, before ending with a painstaking
tomographic reconstruction of the final state and ushering in a new-if-pointless era of quantum
arithmetic. It would not be easy, it would not be useful, but it would be a picturesquely quixotic
way to seek π in the |ψi.
Acknowledgements
Thank you to Creon Levit and Michael Nielsen for feedback on a draft of this paper.
References
[1] G. Galperin, “Playing pool with π”, Regular and Chaotic Dynamics, v. 8, no. 4 (2003)
[2] Grant Sanderson, “The most unexpected answer to a counting puzzle”,
https://youtu.be/HEfHFsfGXjs
[3] L. K. Grover, “A Fast quantum mechanical algorithm for database search,”
Proceedings, 28th Annual ACM Symposium on the Theory of Computing (STOC), 1996,
pages 212-219; arXiv:quant-ph/9605043
10