Get best of the week

How π combines colliding blocks and a quantum search algorithm

A curious physicist has discovered an unexpected connection between the theory of collision blocks and the famous quantum search algorithm




What do digits of π, colliding blocks and quantum search algorithms have in common? More than you might think. This connection is provided by two humorous scientific works - one from 2003, and the second from December 2019. Together they combine the worlds of dynamics, geometry and quantum computing, showing how even the most abstract mathematical puzzles can surprisingly reveal a connection with physics.

Lock


To begin to understand these connections, imagine two metal blocks, each of which weighs 1 kg. They are on the surface without friction, to the right of the fixed wall. The block closest to the wall is motionless, the second slides toward it, approaching to the right. A series of clashes must inevitably occur; Suppose that kinetic energy does not disappear in collisions. Under such ideal conditions, this process will proceed like this:


The right block hits the left, giving it the whole impulse. The left block bounces off the wall, returns to the right for another collision and another complete impulse transmission.

However, if you increase the mass of the right block, the situation will become more interesting. If it weighs 100 kg, with each collision it will transmit only a small part of its momentum to the smaller block, and instead of the number of collisions it will increase from 3 to 31.


With a mass ratio of 10,000 to 1, the situation will be resolved after 314 collisions.


Increase the difference by multiplying the mass by 100, and you will be able to observe a shocking trend: the number of collisions will begin to approach the number π closer and closer.


Gregory Galperin, a mathematician from the University of East Illinois, was the first to notice this phenomenon [in 1993]. In 2003, he explained it by visualizing the movements of blocks through a moving point, whose x-coordinates indicate the location of one block and y-coordinates of the second. The trajectory of a point on the plane is connected with a semicircle, whence π appears.

A remarkable result, even if these ideal conditions make it seemingly useless. However, if you neglect the sloppiness of the real world in mathematics, you can find a pure regularity that reveals unexpected connections with other areas of science.

In 2019, I published a set of three videosexplaining Halperin’s results, and among those who looked at them were Adam Brown, a researcher from Google and a physicist at Stanford University. After a few months at the conference, he took me aside to share his observation. To his delight, he discovered that the mathematics that describe the dynamics of these blocks, from a certain point of view, becomes identical to the mathematics that describes one of the most famous quantum algorithms.

Quantum approach


This brings us to the second part of the puzzle: how quantum search works.

Suppose you have a long list of names without sorting - say, a million - and you need to find a specific name. You have no other options than checking one name after another until you come across the right one. On average, it will take you half a million iterations. Sometimes more, sometimes less, but in any case it will take you some time.

A computer could do this search for you, but the problem with large lists is that the amount of time it takes to process them will grow in proportion to their size. At least when using a classic computer. But in 1996, Love Grover, who worked in Bell's labs, describedhow a quantum computer can perform such a search much faster, and in no more than 1000 steps. In the general case, a quantum computer will cope with a list of length N in π / 4 √N steps. Note that as the number N increases, the number of steps a quantum computer grows more slowly than a classical one.

Such search efficiency is possible because a quantum computer processes all elements of the list at the same time. However, he does not just do the same thing a classic computer would do, only at the same time.

A classic computer answers the question: “Is the 21st element of the list the name that I need?” And it repeats it for each position of the list, from 0 to 999,999. Directly, but not very effective.

But Grover’s algorithm works with a list method, which at first seems strange, but in the end is more useful. A classic computer can simply read bits from memory. Uncertainties present in quantum computing lead to the fact that you cannot directly pull out the components of the vector that you are working with. Each position in the list has an additional probabilistic structure. You do not look at what name is in this position, you measure the entire list, getting a random position - the index - in accordance with the probabilities. Due to the underlying quantum mechanics, instead of working directly with probabilistic values, we work with numbers whose square corresponds to the probability of getting an index corresponding to the name you are looking for.



How can reading a random index come in handy? The art of quantum computing is to manipulate a list of probabilities that builds odds in your favor. In our example, this means inventing a way (which is what Grover's algorithm does) to get the number associated with the index of the name you are looking for, close to unity, so that all other numbers are close to zero. Then, reading this list and receiving an index in response, you are likely to know that it corresponds to the name that you are looking for.

Quantum computing tools consist of operations that a researcher can apply to this list of probabilities. In mathematics, such a list is called a vector. It is often convenient to imagine a vector as a point in a coordinate system, or as an arrow drawn from the origin to this point.



A two-component vector can be represented as an arrow in two-dimensional space. A vector with 1,000,000 components lives in a stunning 1,000,000-dimensional space. The operations performed by a quantum computer look like turns and flips of this arrow. Numerically, each operation is indicated by a matrix.



Quantum computations are especially fast because each operation is performed with the entire probability vector, and does not pass componentwise. Grover discovered a tricky way to manipulate a given vector with a pair of intermittent operations, resulting in a vector with the probabilities we need. It is important that the total number of operations required is much smaller than the size of the list.

If it’s hard for you to imagine how this can work, you are not the only one. Therefore, Adam Brown was so happy to discover a way to imagine these abstract vector manipulations in terms of a more understandable puzzle.

Hidden links


It turned out that when I watched my videos about calculating the number π using colliding blocks, Brown just had Grover's algorithm on his mind, so he immediately noticed their connection. “If you spend all day thinking about quantum search, then everything starts to seem like quantum search,” said Brown, “and it so happened by chance that this case really turned out to be related to quantum search.”

And if Galperin’s work on block collisions used the space that encoded the location of each block, then the connection with Grover’s quantum search begins with a vector whose x and y components encode the speed of each block. Each collision of blocks translates into a specific operation on this vector, changing its components. For example, when the left block collides with the wall, changing the direction to the opposite, this means that the component of our vector is multiplied by -1, and the component x remains unchanged. From a geometric point of view, this looks like a reflection of a vector about the x axis.

Similarly, when two blocks collide, a change in their velocities is similar to another flip of this vector, only offset from the center. When the simulation continues, the left block will again collide with the wall, which will lead to another turn on the x axis. Another collision of blocks means another revolution. As a result, with a sufficient number of collisions, the vector will fill the familiar curve: the circle.


Brown noted that if this situation is correctly described, then these two operations, changing in one direction or the other, are identical to the two operations that Grover used in his quantum search algorithm.

To understand how this happens, imagine a large right block in the form of many kilograms glued together. Then, instead of a two-dimensional vector describing each speed, we get an N-dimensional vector, where N is the total number of small blocks, including the isolated block on the left. Each of the small blocks corresponds to a name in an unsorted list, and a separate block on the left corresponds to the target name.

In his work, Brown proved that the way these collisions of blocks change the vector that describes them is absolutely identical to the way the Grover algorithm changes the quantum vector denoting an unsorted list of names. The moment in the system of colliding blocks, when a large block is about to turn around, and almost all the energy in the system is in a small block, corresponds to the moment in the Grover algorithm, when almost all the probability is in the name that you need to find.

The fact that the number π appears when counting collisions is reflected in the Grover algorithm: π / 4 √N steps. The square root in the expression also reflects how far the counting of the digits of π (in degrees 10) goes after multiplying the mass of a large block by 10.

“So far, it's just a gimmick,” Brown said. “But in physics, we have learned that the more ways we can reflect on a problem, the more ideas we can see — so I hope this fact comes in handy someday.” We have few good alternative ways to visualize the Grover algorithm.

These connections emphasize the capabilities of the universal language of mathematics. The use of vectors for coding the state of a physical system works both on large-scale collisions of blocks and on microscales of quantum states. Many fundamental ideas in mathematics, which at first glance seem unpleasantly divorced from reality, turn out to be powerful tools, because if you omit the physical details in one area, you can find its hidden connections with the other.

More articles:


All Articles