The history of science and mathematics includes many examples of surprising parallels between seemingly unrelated fields. Sometimes these similarities drive both fields forward in profound ways, although often they are just amusing.
In December, Adam Brown, a physicist at Google, described a surprisingly precise relationship between a foundational quantum-computing algorithm and a whimsical method of calculating the irrational number π. “It’s just a curiosity at the moment,” but “the aspiration might be that if you find new ways to think about things, that people will use that to later make connections that they’d not previously been able to make,” Brown said. “It’s very useful to have more than one way to think about a given phenomenon.”
In a preprint posted online (but not yet peer-reviewed at press time), Brown showed a mathematical correspondence between two seemingly unconnected problems. One is the well-known Grover search algorithm proposed for quantum computers, which should be faster than any classical equivalent. The other is a surprising procedure in which counting the number of collisions between idealized billiard balls produces an arbitrarily precise value for the π.
Quantum Algorithms
Quantum computing exploits quantum bits, or qubits, such as ions or superconducting circuits, that can simultaneously represent two distinct states. In principle, a modest number of qubits can represent and manipulate an exponentially larger number of combinations. Exploiting this possibility for computing seemed like a pipe dream, however, until researchers devised algorithms to extract useful information from the qubits. The first such algorithm, described in 1994 by Peter Shor, then at Bell Labs in New Jersey, efficiently finds the prime factors of a number, potentially cracking important cryptography schemes. The trick is to frame the problem as determining the repetition period of a sequence, essentially a Fourier transform, which can be found using global operations on an entire set of qubits.
The second fundamental algorithm, devised in 1996 by Lov Grover working independently at Bell Labs, operates quite differently. “Shor and Grover are the two most canonical quantum algorithms,” according to Scott Aaronson of the University of Texas at Austin. “Even today, the vast majority of quantum algorithms that we know are recognizably either ‘Shor-inspired’ or ‘Grover-inspired’, or both.”
Grover’s algorithm is often described as a database search, examining a list of N items to find the item that has a desired property. If the list is ordered by some label (for example, alphabetized), any label can be found by repeatedly dividing the list in successive halves, eventually requiring log2N queries. For an unsorted list, however, checking each item in turn requires, on average N/2 steps (and possibly as many as N).
Like other quantum algorithms, Grover’s manipulates the entire set of qubits simultaneously, while preserving the relationships between them (prematurely querying any qubit to determine its state turns it into an ordinary bit, squandering any quantum advantage). However, Grover showed the desired item can generally be found with only
global operations.
This improvement is less than that seen in Shor-style algorithms, which typically are exponentially faster than their classical counterparts. The Grover approach, however, can be applied to more general, unstructured problems, Brown notes.
Grover’s algorithm manipulates the entire set of qubits simultaneously, while preserving the relationships between them.
The calculation starts with an equal admixture of all N qubits. The algorithm then repeatedly subjects all the qubits to two alternating manipulations. The first operation embodies the target: it inverts the state of a specific, but unknown, bit. The task is to determine which bit is altered, but not by measuring them all. The second operation does not require any information about the target. Grover found that each time this sequence is repeated, the weight of the target in the admixture increases (although this cannot be measured). After the correct number of repetitions, there is an extremely high chance a measurement will yield the correct result.
Bouncing Billiards
These sophisticated quantum manipulations may seem to have little relationship to bouncing billiard balls. Yet Brown, while working on issues related to Grover’s algorithm, came across an animation by math popularizer Grant Sanderson that made him notice the similarities. In his paper, Brown shows there is a precise mapping between the two problems.
Sanderson’s animation illustrates a surprising observation described in 2003 by Gregory Galperin, a mathematician at Eastern Illinois University in Charleston. In the paper “Playing Pool with π,” he imagined two billiard balls moving without friction along a horizontal surface, bouncing off each other and off a wall on the left side in completely elastic collisions (which preserve their combined kinetic energy).
If the right-hand ball is sent leftward toward a second stationary ball that is much lighter, the smaller ball will be sent back toward the left-hand wall without slowing the larger ball much. The small ball will bounce off the wall, and then collide with the large one again, repeating this multiple times. Eventually the collisions will turn the large ball around until it finally escapes to the right faster than the small ball can pursue it.
The number of collisions needed before this escape can occur grows larger with the ratio of the mass of the large ball compared to the small one. If the masses are equal, it will take three bounces: the first transfers all motion from the right ball to the left one, which bounces off the wall and then transfers its momentum back to the right ball again. If the large ball is 100 times as massive, the process will take 31 bounces. If the mass ratio is 10,000, there will be 314 bounces. In a spectacularly impractical computation, for every increase of a factor of 100 in the mass ratio, the number of collisions (divided by the square root the mass ratio) includes another digit to the digital representation of π, 3.141592654 …
Brown fortuitously encountered Sanderson’s animation (which uses blocks instead of balls) when Grover’s algorithm was fresh in his mind, and recognized significant similarities between the two situations. The two quantum operations, for example, correspond respectively to collisions between the balls and between the lighter ball and the wall. The mass ratio corresponds to the size of the database. Moreover, the final result was that the number of operations (or bounces) is proportional to π and to the square root of this size or mass ratio. (There are also two factors of two that reflect simple bookkeeping differences between the problems.)
Beyond the surprising connection between such different systems, what on earth is the number π doing in both cases? This irrational number is of course best known as the ratio of the circumference of a circle to its diameter, although it also appears in the proportions of ellipses, as well as higher-dimensional objects like spheres. One way to define a circle is through an algebraic constraint on the horizontal and vertical coordinates, x and y: The points of a circle with radius r are constrained to satisfy x2 + y2 = r2.
As it turns out, both the billiard problem and the Grover algorithm have constraints of this form. Collisions of the balls or manipulations of the quantum system correspond to rotations along the circle defined by these constraints.
For example, for two billiards of mass m (with velocity vm) and M (with velocity vM), an elastic collision preserves their total kinetic energy,
. Completely reversing the velocity of the larger ball requires a total “rotation” by 180° (π radians) in the plane with coordinates vm and vM.
Similarly, for quantum systems, the probability of observing a particular outcome is proportional to the square of the “wave function” corresponding to that outcome. The sum of the probability (squared amplitude) for the target and all other outcomes must be one.
Historical Examples of Connections
There is still the question, “Is this profound insight into the nature of reality, or is it just a sort of curiosity?” Brown said. “Maybe Grover search is telling us something profound about the nature of reality, and maybe the bouncing-ball thing is more of a curiosity, and maybe connecting them is more in the spirit of the second one than the first one.”
Still, there have been numerous cases in physics, and especially in mathematics, where such connections have contributed profoundly to progress. For example, physicists have spent more than two decades exploring a surprising correspondence between strongly interacting multi-particle quantum systems and gravitational models incorporating curved spacetime with one higher dimension. There is even hope the wormholes in spacetime can help resolve paradoxes associated with quantum-mechanical “entanglement” of distant particles.
For quantum systems, the probability of seeing a particular outcome is proportional to the square of the wave function corresponding to that outcome.
Mathematics has frequently advanced through connections between disparate fields. For example, Fermat’s “last theorem,” involving integer solutions of a simple equation, was only proved centuries later using methods from “elliptic curves.” In another example, in January, computer scientists proved a theorem relating entanglement to Alan Turing’s notion of decidable computations, which continues to shake up other seemingly unrelated fields.
For his part, Aaronson suspects the Grover-billiard correspondence, although “striking in its precision,” is probably “just a cute metaphor (in the sense that I don’t know how to use it to deduce anything about Grover’s algorithm that we didn’t already know). And that’s fine.”
Further Reading
Galperin, G.,
“Playing Pool with π: The Number π from a Billiard Point of View),” Regular and Chaotic Dynamics 8, p. 375 (2003).
Brown, A.R.,
“Playing Pool with |ψ〉: from Bouncing Billiards to Quantum Search,” arXiv.org/abs/1912.02207 (2019).
Sanderson, G.,
“How Pi Connects Colliding Blocks to a Quantum Search Algorithm,” Quanta (2020)
Join the Discussion (0)
Become a Member or Sign In to Post a Comment