The Machine That Listens

It started with a tuning fork.

Strike a tuning fork and set it on a table next to a second, identical fork, and something quietly remarkable happens. The second fork begins to hum. Nobody touched it. The sound waves from the first fork crossed the air, and the second fork answered, because those waves arrived at precisely the rhythm it was built to move at. Now change the experiment. Surround that fork with a marching band playing at full volume. Trumpets, drums, cymbals, chaos. The fork ignores nearly all of it. Out of that entire wall of sound, it responds to one frequency, its own, and lets the rest wash past.

The fork is not searching the noise. The fork is not listening to the trumpets one at a time and deciding each one is wrong. The fork answers its own frequency because of what it is, all at once, passively, for free.

Hold that image. Because in the last post, I left you standing at the edge of a promise. We established that factoring, the wall protecting RSA, secretly contains a repeating sequence, and that finding the rhythm of that sequence cracks the wall. We established that a quantum computer can load the entire sequence into superposition at once. And I promised there was a move, the opera singer’s move, that makes the loaded sequence ring at its own natural frequency.

This is that post. This is the payoff of the whole series. And the move has a name that sounds far more intimidating than it deserves.

The prism

There is a mathematical operation called the Fourier transform, which takes any signal and reveals the frequencies hidden inside it. The name honors Joseph Fourier, a French mathematician who worked out the underlying idea in the early 1800s while studying how heat flows through metal. The concept is easier than the name.

Think of a prism. White light enters one side looking like a single, featureless thing. The prism bends each color by a different amount, and out the other side comes a rainbow. The prism did not add anything to the light. The colors were in there the whole time, mixed together so thoroughly that no eye could separate them. The prism’s only job is separation. It answers the question: what is this light actually made of?

A Fourier transform is a prism for any signal. Feed it a sound recording and it tells you which pitches are present and how strongly. Feed it a repeating sequence and it tells you the rhythm of the repetition. The pattern goes in mixed and hidden. The frequencies come out separated and legible.

You have been surrounded by this operation your entire life. When you pick out one voice in a crowded restaurant, the machinery of your inner ear is performing a physical Fourier transform, separating the roar of the room into frequencies so your brain can grab the ones that matter. The equalizer display bouncing on a stereo is a Fourier transform drawn as bars. MP3 files, JPEG images, and noise-canceling headphones all work by transforming a signal into its frequencies, doing something clever there, and transforming back. This is not exotic mathematics. This is Tuesday.

So your classical instinct now sees the finish line, and it is about to lunge for it. We have a sequence with a hidden rhythm. We have an operation that reveals rhythms. Run the sequence through the prism, read off the period, factor the number, collect the Turing Award.

Your classical instinct will keep fighting, and here is where it loses.

Why the classical prism fails

To Fourier-transform a signal classically, you need the signal. All of it, or at least a healthy stretch of it, written down where the algorithm can read it. For a sound recording, fine. For our sequence, that requirement is fatal, because writing down the sequence means computing it, step by step, and the sequence for a real RSA number is astronomically long. That is the same wall we have been staring at for three posts. The classical prism works perfectly and does not help at all, because the price of admission is the very thing we cannot afford.

What we need is a prism that works on a signal nobody ever wrote down. A prism that accepts, as input, a superposition.

That is the quantum Fourier transform, the QFT, and it is the heart of Shor’s algorithm. It is the same prism idea, rebuilt out of quantum operations, so that it acts on all the branches of a superposition at once. And to see why that changes everything, we have to go back to the room of shouters.

The room of shouters, one more time

In the second post of this series, I described interference with a crowded room. Interference means waves combining, so that waves arriving in step reinforce each other and waves arriving out of step cancel each other out. A quantum computer’s entire advantage lives in that one sentence. Every possibility in a superposition is a wave. Arrange the machine so that wrong answers arrive out of step and shout each other into silence, while the right answer arrives in step and grows louder with every contribution.

The QFT is that arrangement, purpose-built for rhythms.

Here is the honest, plain-language version of what happens inside Shor’s algorithm. The machine loads a superposition representing every step of the repeating sequence at once. Qubit is short for quantum bit, and the “not knowing versus not being” distinction matters here as much as it ever has: the machine has not secretly computed one step that we simply have not read yet. Every step is genuinely present, the way the surface of a pond is present everywhere on the pond, and the sequence’s rhythm is spread invisibly across all of it, mixed together like colors in white light.

Then the QFT runs, and every possible answer to the question “what is the period?” becomes a chorus of waves. Consider some wrong guess at the period. Contributions to that guess come from all across the sequence, and because the guess does not match the sequence’s true rhythm, those contributions arrive scattered, out of step, pointing every which way. They cancel. Not approximately. Not mostly. The mathematics of interference grinds wrong guesses toward zero, thousands of contributions annihilating each other in pairs, an entire room of shouters going silent because every voice found its opposite.

Now consider the true period. Contributions to the true period come from across the sequence too, but these arrive in step, because the guess and the rhythm agree. Every wave lands on the pile. The signal grows. Like sound waves reaching a tuning fork built for exactly that frequency, the sequence answers its own rhythm and ignores the noise, not because anything searched, but because of what interference is.

Then you measure. Measurement collapses the superposition to a single outcome, and the QFT has spent all its effort rigging that collapse. The overwhelming share of the probability now sits on outcomes that encode the period. You read out one number, run a short classical calculation on it, of roughly the same difficulty as the greatest-common-divisor step from the last post, and the period falls out. In practice the machine sometimes lands on an unlucky outcome that encodes the period ambiguously, so you run the whole procedure a handful of times and cross-check. A handful. Not an astronomical number. A handful.

The period gives the factors. The factors break RSA. The wall never stood a chance, because nobody ever climbed it. Someone listened to it instead.

The glass breaks

Now the opera singer can finish her note.

She never searched the piano for the right pitch. The glass told her, by being a glass, which frequency it would answer. She supplied that frequency, the waves arrived in step, each push reinforcing the last, and the energy piled up until the glass failed. In the last post I said the glass is not being searched, it is being asked, all at once, what its natural rhythm is, and that it cannot help but answer.

Shor’s algorithm is that question, asked of a number.

And I want to close the loop that this whole series opened with, because it is the same loop. The bombe did not read every rotor setting. Turing found structure, a scrap of known plaintext and a machine forbidden from encrypting a letter as itself, and used that structure to make vast fields of wrong answers eliminate themselves without ever being visited. Shor found structure too, a rhythm hidden inside factoring, and used interference to make vast fields of wrong answers literally cancel themselves out of existence. Eighty years apart, different physics, same idea. You do not defeat an astronomical number by counting through it. You defeat it by exploiting structure.

That is the whole story of this series in one sentence, and as of this post, you have now seen the entire mechanism. There is no further trick hiding behind the curtain. Superposition loads the problem. Structure gives the waves something to agree about. Interference silences the wrong answers. Measurement reads the survivor. That is how a quantum computer breaks RSA.

What we have and have not established

So why is your bank still standing?

Everything in this post is proven mathematics and has been since 1994. Shor’s algorithm works, on paper, with no known error and no fine print in the math itself. What I have not shown you is a machine that can run it against a real key. The algorithm asks its hardware for something brutally hard: thousands of qubits holding a delicate superposition in perfect step through billions of operations, when in reality a qubit can lose its quantum character thousands of times faster than the blink of an eye. The gap between the algorithm on paper and the machine in the lab is the entire remaining question, and it is where every headline, every breathless prediction, and every serious government deadline actually lives.

That gap has a shape, and numbers, and an honest answer to the question everyone asks, which is: how long do we actually have?

That is the next post.