Korva is a scroll of the internet’s best ideas.
Quantum computing is wave interference
Building a pattern from waves
Take the repeating function 1, 2, 4, 8 and ask which waves add up to build it. The first ingredient is the average value, 3.75. The function repeats four times across a window of 16 slots, so the wave that matters has four cycles across that window. Waves with 1, 2, or 3 cycles contribute nothing, and at 4 cycles the first peak appears. That peak alone carries the period.
Phase and interference
Whether waves reinforce or cancel depends on their phase, meaning how their peaks and troughs line up. Two waves in step add into a bigger wave, two waves knocked out of alignment cancel, and everything in between is a smooth continuum. A signal generator and an oscilloscope can show it with nothing quantum involved, and controlling that phase is what quantum computing is about.
Superposition is the same wave behavior that gives a voice or a musical instrument its tone, as different frequency components add together. The calculation happens in this universe, with no infinite supply of parallel universes doing the work, and there is no empirical evidence for those universes.
Scaling to real numbers
The sequence of pulses and waits that carries out the Fourier transform is the same for 4 qubits or 4,096, and it is never tuned to a known answer. At 15 the pattern can be seen by eye, but at a 600-digit number it cannot. The peak still shows up in the spectrum, and instead of trying every factor by hand, the period pops out.
Why do waves cancel or add up?
When two waves overlap, their displacements at each point simply add together. If two crests line up, the result is a taller wave, and if a crest meets a trough of equal size, they sum to zero. Noise-canceling headphones use this: a microphone picks up outside sound and the speaker plays a mirror-image wave that cancels it. The same arithmetic applies to light, water, and sound.
Why does a quantum computer need interference?
Quantum states carry amplitudes that can be positive, negative, or complex, so contributions to the same outcome can cancel instead of only piling up as classical probabilities do. A quantum algorithm is built so that the amplitudes for wrong answers cancel and the amplitudes for right answers reinforce. Grover's search algorithm and Shor's algorithm both rely on this. If the interference is not arranged well, measuring gives a random result.
How is a Fourier transform run on qubits?
The quantum Fourier transform acts on a register of n qubits using on the order of n squared gates. A classical fast Fourier transform on the same 2 to the n values needs about n times 2 to the n operations. Don Coppersmith and Peter Shor each described this circuit in the early 1990s. The saving in gate count is what makes period finding on large numbers feasible in principle.
More from Computerphile
