Symptoms Of The Universe

(Yes, that pun is bloody awful. Apologies.)

Large-number factorisation is a remarkably lopsided problem. Multiplying two large prime numbers together is easy; being handed the answer and asked to recover the two primes is, for a classical computer and a large enough number, much harder (to dramatically understate the case). That imbalance is the basis of RSA encryption, one of the workhorses of internet security: it is easy to make a public number by multiplying two secret primes, but, for large numbers (e.g. 2048-bit values) it’s effectively impossible, for all practical purposes, for an outsider to reverse the process and recover them.

That was the comfortable assumption, at least, until 1994, when Peter Shor showed that a quantum computer could attack the problem in a radically different way. Shor’s algorithm was revolutionary because it demonstrated that a sufficiently large, fault-tolerant quantum computer could, in principle, undo the imbalance and factor large numbers efficiently. And that’s why the phrase “quantum computing breakthrough” tends to leave cryptographers in a rather perturbed state.

The first step in Shor’s algorithm is, however, not even quantum at all. It’s an astoundingly elegant, purely classical, change of perspective: turn factoring into period finding. Instead of trying to pull the hidden primes directly out of a large number, we construct a repeating modular-arithmetic pattern and ask how often it repeats, i.e. what’s the underlying frequency? And once the problem has been recast into finding frequencies, physicists perk up. We’re then in the well-trodden domain of Monsieur Fourier.

But more on Fourier later. First, we need to get to grips with Shor’s strategy.

Remainders of the day

Let’s say we want to factorise a number N. We’re going to start small and choose N = 15. (Yes, that’s hardly a formidable mathematical challenge — particularly if we can remember our times tables — but it serves as an illuminating toy example of Shor’s algorithm in action.) The idea is to pick an integer a that has no common factor with N (other than the trivial 1), then look at the sequence

as x increases (0,1,2,3….). We’re going to choose a = 2 for this example.

The “mod” means modulo arithmetic; we simply divide through by N and take the remainder. The crucial insight is this: because of the modulo arithmetic, the outputs must eventually repeat. The key quantity is the period r: the number of steps it takes before the sequence cycles back to the start. Once we know that period, the factors can be extracted with a little ordinary arithmetic.

Here’s how it works for N = 15, a =2:

x	2x	2x mod 15
0	1	1
1	2	2
2	4	4
3	8	8
4	16	1
5	32	2
6	64	4
7	128	8

So, the sequence is 1, 2, 4, 8, 1, 2, 4, 8, 1, 2, 4, 8…. It repeats every four values. In other words r = 4.

Now the neat bit. Since the period is 4 we know that

(The three-bar equals sign just means “equivalent to”. In other words, $2^4$ (i.e. 16), is the same as 1 in modulo-15 arithmetic, as is $2^8, 2^{12}, 2^{16}, 2^{20}$…etc…)

This means that

But

And there are our factors.

The rhythm in the algorithm

For factorising 15, all of this is, of course, almost farcically unnecessary. We hardly need Peter Shor to tell us that 15 = 3 × 5. But the example captures the essential trick: don’t attack the factors directly, find a period instead. That change of viewpoint is the first key step — and it is entirely classical. Not a qubit in sight.

Now imagine we have a 2048-bit number N = pq, where p and q are prime. (See footnote⁵ for an example of a 2048-bit number. It’s a bit of a beast.) We’re given N. Our task is to find p and q. Unlike our 15 = 5 x 3 example, this one is not something that can be trivially tackled by observation. But exactly the same recipe applies:

• Randomly pick a number a that doesn’t share a factor with N. (If it does share a factor, congratulations. You can have the rest of the day off.)

• Now look at the sequence

where x is once again zero or a positive integer: 0, 1, 2, 3…

Because it’s modulo arithmetic, the sequence must repeat at some point. We just don’t know when. For a 2048-bit number, trying to find that period by simply brute-force stepping through values of x, one at a time, is hopeless. In the hard cases relevant to cryptography, the period can be astronomically large. A single laptop core would not merely be slow, it would take many times the age of the universe to find r using a sequential trial-and-error approach of that type. Even recruiting a billion cores would not turn a brute-force search into something tractable; in this context a billion cores are essentially just as useless as pen and paper, or, indeed, stone tablet and chisel.

This is not to say that all classical approaches are so crude — classical number theory has many far smarter tools than blind stepping. But for the period-finding route at the heart of Shor’s algorithm, direct sequential search is exactly the bottleneck the quantum part is designed to avoid. The reason that the quantum part of Shor’s algorithm is so powerful is that it does not search for the period one step at a time. As we’ll see, it instead extracts the period as a frequency.

• Once we know r, the rest is algebra. If it turns out that r is an odd number, we sigh, choose another value of a, and start again. When r is even, we do exactly what we did above for N = 15:

The left-hand side is divisible by N, so there is a good chance that the two bracketed terms contain the hidden factors of N between them. To extract them, we compute

and

where “gcd” means “greatest common divisor”. (This is a fast operation even on a classical computer; it’s the period-finding step that’s the monumentally time-consuming bit). If the gods of number theory are smiling, these greatest common divisors are neither 1 nor N, but the prime factors we’re looking for.

So, in a nutshell, Shor’s modular-exponentiation strategy transforms the factoring problem into a period-finding problem. We no longer ask, “What are the factors of $N$?” directly. Instead we ask, “How many steps do we need to go before this modular pattern repeats?” In other words, what’s its period? Or, equivalently (and crucially when it comes to quantum computing), what’s its frequency? How often does the pattern repeat?

Period and frequency are two sides of the same coin. The period tells us the spacing between repeats; the frequency tells us how many repeats fit into a given stretch.

Long period, low frequency. Short period, high frequency.

And this is where the ubiquitous Fourier transform makes its entrance. Pass a repeating pattern (or even a non-repeating pattern) to an FT and it tells you which frequencies are present. Importantly, no weird quantum trickery is required — this is a purely classical concept and technique. Fourier analysis⁶ has been with us since the (very) early 19^th century and is a cornerstone of classical physics, engineering, signal processing, image analysis, acoustics, studio recording, optics, crystallography, medical imaging…; everything from the subatomic to the cosmological. Anywhere there are signals, shapes, oscillations, waves, or patterns, Fourier is there (implicitly or explicitly).

The central idea is beautifully simple (and I’ve banged on at length about its elegance and ubiquity before): a complicated pattern can be broken down into simpler waves. The Fourier transform tells us how much of each wave — each frequency — is needed to build the pattern. Or, in slightly more mathematical language, a very large class of functions can be built as a summation of much simpler basis functions, $u_n(x)$ (where $n$ is just a label telling us which of the functions in the basis set we mean):

The coefficients $c_n$ tell us how much of each basis function is needed. Change the coefficients, and we change the mixture. Change the basis functions, and we change the mathematical “ingredients” we are using to build $g(x)$. In Fourier analysis, those basis functions are sines, cosines, or a combination of both. (And it doesn’t just have to be a one-dimensional function — two, and higher, dimensions are equally amenable to Fourier treatment.)

That summation – the “big sigma” sign — in the equation above is the very definition of superposition: a linear sum of basis functions to create a more complicated function. Despite all the “Wow! Quantum! Heads And Tails At The Same Time! Amaaazing!” hyperbole, there’s nothing at all weird, wacky, mystical, or magical about superposition. Nothing. Classical physics, in markedly ordinary settings, does superposition all the time: harmonics combine to give texture and character to voices, musical notes, and sounds in general; ripples overlap on the surface of a pond, lake or ocean; radio, WiFi, and mobile-phone signals superpose all around us; and every image we see is formed from light waves whose fields can add, overlap, and interfere.

As we’ll soon see, quantum mechanics certainly has its weird moments. But superposition isn’t the source.

Fourier analysis earns its stripes

The simplest place to see all this in action is not in a stream of modular-arithmetic values, but in a picture. Imagine a set of evenly spaced stripes: dark, light, dark, light, repeating across the page. Actually, you don’t have to tax your imagination. Here’s something you may recognise…

The distance from one bright stripe to the next in the zebra crossing is the period of the pattern. The number of bright-dark cycles packed into a given distance is its (spatial) frequency (aka wavenumber). Same information, two entirely complementary (and conjugate) descriptions.

To initially keep the Fourier picture as clean as possible, we’ll start not with a traditional stark black-and-white zebra crossing, but with a softened version: a smooth sinusoidal variation from dark to light and back again: one pure sine wave (i.e. a single Fourier component.) Then our “sum” has only one term:

where

For our zebra-crossing example, x is the distance across the crossing: 0 on the left edge, increasing in value to a maximum (i.e. the width of the crossing). The l symbol represents the period of the pattern. More importantly in the context of quantum computing is the associated (spatial) frequency, 1/l (which I’ve highlighted in red.) If, for example, the zebra crossing dark-light pattern repeated every 1 m, then the frequency is simply 1/m (in words, “one (period) per metre”); if the period were instead 50 cm, then the frequency is 2/m (or 2 m^-1; two per metre).

That’s x and 1/l covered. That just leaves the $2\pi$ in the equation for $u_1(x)$ to explain. The frequency, 1/l, tells us how many cycles fit into one metre. But the sine function does not count in cycles; it counts in radians. A sine wave completes one full cycle when its argument changes by 2π radians (or $360^\circ$ in the entirely arbitrary 4,000-year-old angle convention bequeathed to us by the Babylonians⁷.) So we multiply by 2π to convert from cycles per metre to radians per metre.

The quantity $2\pi \times \frac{1}{l}$ is called the angular frequency and tells us how quickly the phase of the sine wave changes as we move along x. The phase is simply where we are in the sine wave’s cycle: peak, valley, zero-crossing, or somewhere in between. If 1/l = 1/m, the wave goes through one full cycle per metre, so its phase changes by 2π radians per metre. If 1/l = 2/m, the phase changes twice as fast: 4π radians per metre.

The Fourier transform takes the period of the zebra-crossing image and converts it to a representation in spatial frequency; it’s exactly the same information, just in a much more compact, and generally easier-to-interpret form (particularly for patterns rather more complicated than a zebra-crossing, like, for example, this). Undergraduate physicists spend a lot of time studying reciprocal space for precisely this reason. (There’s a beautiful relationship between crystal structure, Fourier transforms, reciprocal lattices, diffraction, and the famed double-slit experiment that I unfortunately don’t have space to explore here.)

Superposition without the superstition, revisited

Here’s a demo that puts the maths in a more visual and tangible format. We start with one Fourier component — i.e. one sine wave. Change the stripe period (unit: pixels) via the slider below and note how a smaller value shifts the spike in the Fourier spectrum to a higher frequency (and, of course, vice versa).

Now move the top slider to “2” to add another Fourier component.

Congratulations. You’ve just carried out superposition. (And I’m willing to bet a substantial sum that, in doing so, you observed precisely zero empirical evidence that a new branch of the universe appeared, decoupled, and went off on its merry way.)

You’ve now got a linear summation, i.e. a superposition, of two basis functions:

Nothing mystical. Just a sum of two functions. Superposition.

(“Why c₃ and not c₂?”, you might ask. “And for that matter, why 6πx/l ?” Very good questions. See ⁸ for the gory detail. However, you can comfortably bypass that for now — it really is a footnote in the explanation of quantum computing essentials. All you need to recognise is that a superposition is just a sum of functions.)

By moving the “Fourier components” slider in the demo to the right you increase the number of terms, n, in the summation,

For our zebra-crossing case, our basis function “ingredients” are

Note the argument of that sine function. As we increase the value of n, the sine wave oscillates back and forth in space at a higher rate. This in turn means that as we add more Fourier components, the image of the zebra-crossing sharpens up; those higher spatial frequency components vary more quickly in space. Conversely, if we remove high frequency Fourier components from an image, we’ll tend to blur it, or, at worst, reduce it to a featureless, ill-defined, uncertain blob⁹.

Fourier transforms don’t just convert between spatial period and spatial frequency. They’re routinely used in a vast array of contexts in physics, chemistry, biology, medicine, engineering, and computing — including, in particular, quantum computing — to decompose a waveform into its component frequencies. It’s exactly the same idea: change the representation from one domain to another. Period becomes frequency. And this is precisely the strategy that Shor’s algorithm exploits.

But, as mentioned in passing above, sine functions aren’t the only ingredient we can have for Fourier series and transforms. Cosines also oscillate, of course. Wouldn’t it be helpful if we could combine both sine and cosine representations into a single, more compact form of Fourier analysis? Fortunately, a powerful mathematical identity discovered — or should that be invented? — in the eighteenth century allows us to do just that.

Although some mathematicians may quibble — and there’s nothing a mathematician likes more than quibbling, in my experience — the following compact little gem is routinely described as the most beautiful equation¹⁰ in the world (…or possibly the universe (or multiverse, if you really must)) :

Here’s how Keith J Devlin, professor emeritus at Stanford, has described that mathematical objet d’art (which is due to the 18th century Swiss polymath Leonhard Euler):

…like a Shakespearean sonnet that captures the very essence of love, or a painting that brings out the beauty of the human form that is far more than just skin deep, Euler’s equation reaches down into the very depths of existence.

“…the very depths of existence.” That’s quite the accolade. But the version of Euler’s equation above is really only the special, t-shirt-and meme-ready case. It comes from a more general relation, known as Euler’s formula, which tells us what happens when the angle is not fixed at π radians (aka 180 degrees), but allowed to be any angle $\phi$:

In other words, the famous “most beautiful equation” is essentially one particularly photogenic scene from a much larger mathematical production. And, if you’ll allow me to strain the cliched movie metaphor beyond breaking point, the imaginary number, i, plays a starring role. (Ouch. I’ll get me coat…)

Real and imaginary. It’s complex.

Euler’s formula is not some exotic piece of quantum sorcery (not least because it predates QM by about two hundred years). It’s simply part of the standard physics vocabulary when it comes to waves, rotations, oscillations, and periodic motion. Anywhere sines and cosines turn up — sound, light, electromagnetic waves, vibrations, and, of course, quantum mechanics — Euler is lurking somewhere in the background (usually shoulder-to-shoulder with Fourier.)

Let’s not worry about how the formula is mathematically derived — there are a few neat approaches — and instead focus on a simple graphic that captures just how those cornerstones of mathematical physics, e, i, cos, and sin, are interrelated. (There’s a physicist-friendly Old MacDonald joke lurking in there somewhere, but I’ll spare you.)

The x-axis in the interactive figure embedded at the foot of this section is labelled Re, for real. We’re all — scientist or not — on very familiar terms with real numbers because these represent quantities we can measure: length, voltage, energy, momentum, the eye-wateringly high price of a hot beverage that almost, but not quite, tastes entirely unlike tea, the airspeed velocity of an unladen swallow, etc… Quantum mechanics may be weird, but it’s not that weird: when we measure something, the result must still be a real number.

I make this point, obvious though it may seem, because the y-axis is instead labelled Im. That’s short for imaginary. Imaginary numbers are some multiple of i, the square root of -1. And while i is a fascinating and powerful addition to our mathematical lexicon, it’s most definitely not something we can measure directly. No device, no matter how clever, is going to return $\sqrt{-1}$ as a reading on its display.

So, you might ask, why introduce i at all? Why make things more complex? Because although imaginary numbers are not themselves measurement outcomes, they are extraordinarily useful throughout the physical sciences, mathematics, and engineering when it comes to keeping track of quantities that rotate, oscillate, and interfere. Their real utility, however, comes when we combine them with real numbers. A complex number, often represented by the letter z, does just that: it packages a real part and an imaginary part together into a single object: z = x+ iy. And this, it turns out, is a mathematical object that is particularly at home in the quantum world¹¹.

Talking ’bout a revolution

A more quantum-friendly way to write a complex number, thanks to Euler’s formula above, is this:

All we’ve done here is translate from one representation to another. It’s exactly the same complex number, z, just written in a different way. It’s like giving directions to the same place in two different forms: Go 7 km east, then 7 km north (“7 + 7i“) versus Go north-east for about 10 km. The destination hasn’t changed, only the directions. And, thanks to Pythagoras, Euler, and a bit of basic trigonometry, the translation from one set of directions to the other is straightforward.

In the interactive graphic below, the blue line below is what we call a phasor. It’s got a length r (which we call the modulus). So, from Trig 101,

where x is the distance along the real axis, y is the distance along the imaginary axis, and ϕ is the angle that the phasor makes with the real axis (which we call the phase or phase angle. Hence, phasor. As distinct from phaser.)

This modulus-phase form, $z=re^{i\phi}$, is not just an alternative notation to $z=x+iy$. As we’ll soon see, it’s core to developing an understanding of just how quantum computers work.

For the demo below, use the phase-angle slider, or the $\pm\phi$ buttons, to rotate the arrow around the complex plane. As you change $\phi$, note how the projections onto the real and imaginary axes vary as $r\cos\phi$ and $r\sin\phi$. The modulus slider changes the length of the phasor, $r$, so both projections grow or shrink with it. This simple act of rotating and scaling phasors is exactly what a Fourier transform exploits: it lines up, adds, and cancels arrows to reveal frequencies. (And if these little rotating arrows feel familiar to some of you, that is no accident: this way of thinking is very much in the spirit of Feynman’s QED: The Strange Theory of Light and Matter.)

The classical Fourier transform, discretely

Euler’s formula gives us a pleasingly compact way to write oscillations. Instead of carrying around separate sine and cosine terms, we can package them into a single complex exponential. This is not just mathematical tidiness for the sake of it; when it comes to the Fourier domain, the complex exponential form is exceptionally powerful.

As we’ve seen, a Fourier transform determines how much of each repeating component is present in a signal, image, waveform, or pattern. Written in complex form, those components are not just sine waves. They are a combination of sines and cosines. They’re phasors.

For a discrete signal — that’s a list of values rather than a continuous curve (think of a column of values in a spreadsheet) — the Fourier transform becomes the discrete Fourier transform¹², or DFT:

In words, a list of values

is turned into another list:

The first list is the original data. It could represent essentially anything — brightness along a line (as in our zebra-crossing example), a microphone signal, voltage values from a detector, an MRI scan, or a list of numbers from a modular-arithmetic pattern. The second list is the Fourier-transformed data. As we’re about to see, it tells us how much of each frequency is present.

If you’ve not encountered Fourier analysis before, don’t panic. That equation above may look daunting at best, and downright intimidating at worst, but it’s nowhere near as tricky as it first seems. And we’ve already covered all the maths you need to understand it earlier in this post. In any case, we can’t cut corners here. The discrete Fourier transform is not only the heart of the QC implementation of Shor’s algorithm, it also contains, in miniature, some of the core ideas behind quantum logic.

It is worth taking this slowly, because the type of phase manipulation underpinning the classical DFT is exactly what quantum computing exploits: arrange phases so that contributions matching the underlying pattern reinforce, while incompatible contributions cancel away. And because quantum registers naturally deal in amplitudes and relative phases, the DFT algorithm is exceptionally well matched to the way quantum computers actually process information. It’s all wave manipulation, remember. (And yes, that also goes for the QC platform being developed right now by your smarter doppelgänger in Universe #ZZ9-2112-42-plural-Z-alpha.)

Clocking the frequency

When we introduced the zebra crossing, frequency was explained, as is traditional, in terms of “cycles per metre” or “cycles per pixel”. But there’s a complementary, equally valid, phasor-based way to think about frequency that is core to how the DFT operates: one cycle of a wave is one full turn of a phasor, so frequency is simply how fast the phasor rotates as we move across the wave, pattern, or signal. Higher frequency means a larger phase step from one point to the next.

The DFT is built around this simple idea. For each possible frequency $k$, it multiplies the input by a phasor whose phase varies in the opposite direction. If $k$ matches the input frequency, the phase variation is captured correctly and all the resulting phasors point the same way. If $k$ doesn’t match, some phase variation remains and the phasors cancel when summed. The result? A peak right at the frequency of the input pattern/signal¹³.

Before we dissect the DFT equation symbol by symbol, however, let’s first use a demo to see what it’s doing. (After all, a (moving) picture paints 2¹⁰ words, give or take). We’ve set this up in a way that is very similar to the quantum computing architecture, but right now it remains completely classical — not a qubit in sight.

In the demo below, the upper register — which is nothing more than a list of input values — contains 25 samples of a single complex exponential. It’s a simplified, phasor-friendly version of the initial smooth zebra-crossing pattern and it looks like this:

Before passing this to the DFT, let’s make sure we understand what f_n represents.

For the zebra crossing, we described our basis sine function in terms of the continuous variable, x: $u_n(x)=\sin(n2\pi f x)$, where x was the distance across the crossing. For the complex exponential input to the DFT, we instead have a list of values — at the risk of belabouring the point, it’s a discrete, not a continuous, function. The n tells us which entry in the list we’re looking at — again, it helps to think of a column of values in a spreadsheet — while N is the total number of entries in that list.

So $n/N$ simply tells us how far through the list we are (just like x in the zebra crossing example told us how far across the crossing we were).

If $n=0$, we are at the start.

If $n=N/2$, we are halfway through.

The idea is straightforward: $n/N$ is the discrete version of “position across the pattern”.

The frequency is set by the value of m, which we’re going to set to 4. For all that follows it’s helpful to think of frequency in terms of the number of full phase cycles across the register. In addition to having four cycles across the register, we can also have a phase offset. This is nothing more than a constant additional phase that affects all phasors equally; instead of the first value in the register (i.e. f₀) having a phase of 0, we add a phase angle that rotates the phasor away from being aligned with the positive x-axis direction.

Shift the input phase slider at the top of the demo below back and forth and you’ll see the associated phase variation sweep across the input register — you’re just shifting the peaks and the troughs along. (Make sure to reset the input phase offset to zero before continuing.)

The lower register shows what happens for a specific frequency $k$. To reiterate (because it’s absolutely central to the entire story): the DFT works by multiplying the input by a phasor whose phase varies in the opposite direction (due to the negative sign in the exponent in the DFT equation). Move the “DFT test frequency” slider and note that when $k \neq 4$, i.e. when the frequency does not match that of the input, some phase variation remains: the little yellow phasors point in different directions and cancel .

But when $k=4$, the DFT output has captured — well, “reverse-captured” — the phase variation in the input. All the yellow phasors then point the same way, so the output – the sum of those phasors, courtesy of the big sigma, $\sum$ , in the DFT equation — is large. The DFT has found the frequency of the input pattern.

However, the DFT does not only tell us which frequency is present. Each value of $F_k$ is a phasor, so it has both a length and a phase angle. The length is the modulus of the complex number, denoted mathematically as $|F_k|$ ; it shows how much of frequency k is present. (We’ll have more to say on moduli soon.)

On the other hand, the phase angle tells us, perhaps unsurprisingly, the phase of that frequency component — where it sits in its cycle. You can see that in the demo by moving the “input phase offset” slider. When $k=4$, the yellow DFT phasors still line up, but they all line up in a different direction. The frequency has not changed; only the overall phase of that component has shifted.

Arrows to algebra

To save you having to scroll up, here’s the DFT expression again:

(Before going any further, I’ll just note that the summation, $\sum$, runs from 0 to N-1, because we label the first point in the input data list as #0, rather than #1. The coding community is very used to this convention.)

We’re going to dissect the DFT operation as briefly as possible, and connect the math(s) to the demo.

Here, once more, is our input:

Let’s now plug that expression for f_n into the DFT formula:

Multiplying exponentials means that we simply add the exponents, like this:

Now this is rather neat, because if we have m = k, i.e. we’ve matched the input frequency, the exponent becomes 0 (due to the (m-k) term). So the value of the DFT for that particular frequency is simply:

And any number raised to the power of 0 is 1. So we have 1+1+1+1+…. for a total of N values, i.e. the total number of values in the input data list. Adding up all those ones gives us a big spike in the DFT at a frequency that matches that of the input data. Moreover, 1 is a purely real number. This is why the DFT output phasors in the demo all align along the horizontal for k = 4 (and for an input phase offset of 0.)

For other values of k, the exponent doesn’t become 0, the phasors don’t align, and when they’re added together via the big sigma, $\sum$, they cancel out. So the DFT returns zero for all other frequencies.

This is an idealised example involving a single pure complex exponential with an integer frequency. DFTs of real signals are never quite so tidy. But the core concept and strategy remains exactly the same. Loop through different frequencies, k. Those that match a frequency in the input pattern will capture the phase variation in the input signal to a much greater extent, and appear as a peak in the DFT.

To be Shor

We’ve just Fourier-transformed a clean complex exponential: a signal whose phasor rotates by the same amount from one sample to the next. That was the simplest possible way to see how Fourier analysis detects a frequency. But Shor’s algorithm, as implemented on a quantum computer, does not simply hand the quantum Fourier transform a smooth sine wave. Nor does the quantum modular-exponentiation unit — let’s call it the quMEU — pass the modular sequence 1,2,4,8,1,2,4,8,… directly to the Fourier-transform machinery.

That would be a perfectly valid Fourier transform. But it is not the transform we need.

We’re going to stay classical for just a little while longer, because we can get surprisingly close to the quantum version of Shor’s algorithm without yet introducing a qubit. The key next step is that we stop thinking of the modular values 1,2,4,8,… as sample values in a signal or waveform and change our perspective a little.

In the standard version of Shor’s algorithm, the quMEU has two registers at its output: one still carrying the input value $x$, and a second carrying the modular-output $a^x\bmod N$.

(How the quMEU actually carries out the modular exponentiation quantum mechanically is a post for another day — unless Sean is keen on a Computerphile video that makes the combined extended editions of The Lord of the Rings trilogy seem like a YouTube short. For now, we’ll treat it as a black box.)

What matters for us is not the machinery inside the quMEU, but what it provides as output. For our N =15, a=2 example, we use a four-bit input register, because we are considering x=0 to x=15 (i.e. sixteen (2⁴) different values). The modular outputs are also each less than 16 in value, so we can write them as four-bit labels too. Classically, the quMEU’s output can therefore be represented by the following two-register table:

Each input-register value is simply the corresponding value of $x$ written in binary across four bits; the output-register values are just $1,2,4,8,1,2,4,8,\ldots$ also written in binary. At this point our toy example is almost too small for its own good. Once the table is printed in front of us, the period in the output register is easy to spot by eye. But this is not the situation the algorithm is built for. We do not need Peter Shor’s strategy to factorise 15; we are simply using $N=15,\ a=2$ to expose the nuts and bolts of the approach. In a real quantum-computing architecture there is, of course, no printed table to inspect.

So we should resist the temptation to solve the toy problem by staring at it. Instead, we now use the method that scales, and that — as we’ll see — is fully compatible with quantum mechanics. Focus on one possible output-register value, say,

Now, go down the list of input positions in the table above, starting at the top, and put a “1” if there’s a match with the 0010 output value, and a “0” if there isn’t a match. This is what you get:

This is essentially our zebra crossing again: a regular pattern of bright and dark slots. Let’s get its DFT.

The demo below takes the representative output-register value 0010 and shows how its corresponding input pattern is analysed by a DFT. For each test frequency $k$, the DFT equation is implemented phasor-by-phasor. (The “Step” button increments by a single phasor each time). Most values of $k$ make the contributing phasors point in different directions, so they cancel and the corresponding DFT output — the sum of all the 16 contributing phasors — for that value of k stays as zero.

For $k=0, 4, 8,$ and $12,$however, the contributing phasors line up, so a non-zero output phasor appears. Pressing “Scan k” saves your fingers some work and automatically builds the Fourier spectrum slot by slot, making the peaks at $0,4,8,12$ appear for exactly the same phasor-alignment reason we saw in the earlier DFT demo for the single complex exponential input.

The demo performs the DFT in the most transparent possible way: step through each test frequency $k$, add the corresponding phasors, and watch the peaks appear. The quantum Fourier transform will not do this by looping through $k$ in the same classical way. But, as we’ll soon see, it is also not the case that the whole QFT magically falls out of the aether into our lap because “superposition”. The quantum version still has to be engineered from carefully controlled operations that move amplitudes and, critically, shift phases.

Before we finally get to the QC implementation of Shor’s algorithm, here’s one last illustration of the central importance of phase — not just in quantum mechanics, but in classical waves, images, and the universe of patterns all around us.

When Schrödinger’s cat meets Fourier’s best friend

The DFT output is not just a list of frequency peaks. As is clear from the examples above, each Fourier component is a phasor, with both a length and an angle. The next demo is a small act of Fourier vandalism designed to show just how much that angle matters.

We take the Fourier transforms of the two images below and swap the phasor information around: lengths (i.e. moduli) from one image, angles (i.e. phases) from the other.

The sliders in the demo below control how much we mix the phases or moduli of one image with those of the other. Note that K9 — for it is he — materialises when the phases are shifted towards K9, even though the moduli are still taken from the cat image. By contrast, changing the moduli while keeping the cat phases retains our infamous feline friend.

In many areas of physics and engineering, we very often use what’s called a power spectrum: instead of considering the full Fourier phasor, we keep only the square of its length, $|F_k|^2$. (It is called a power spectrum because, for many physical signals, the power carried by a wave is proportional to the square of its amplitude.) This is enormously useful — physicists are very fond indeed of their power spectra — but throws away all the phase information. And often that is not just a choice. Sometimes, the power spectrum is all we can measure; the phase is out of our reach.

The K9-cat hybrid demo shows what can be lost when we keep the lengths and discard the angles. Peter Coles makes the same point in a more colourful cosmological setting in his highly recommended What the Power Spectrum Misses post: sharp structure depends on Fourier components adding coherently in the right places and cancelling elsewhere, and that coherence lives in the phases.

And this is why we’ve taken an extended (pre)amble through classical Fourier space before venturing into the quantum world. The very same ingredients are at the heart of quantum computing: phasors, moduli and phase angles, interference, and cancellation. We’re going to see that, in quantum mechanics, the phasors represent the complex amplitudes of quantum states: lengths set the measurement probabilities, phase angles decide how the amplitudes interfere. Change the phases, and you change what reinforces, what cancels, and therefore what is likely to be measured.

Quantum computing, at heart, is the controlled engineering of that interference: use amplitudes and phases so that structure and patterns become visible in the measurement statistics.

Now let’s finally see how.

At this point, we’ve already done the majority of the mathematical work needed to make sense of quantum computing. Not all of it — probability, measurement, and interference still have to be explained— but the rotating phasor picture is at the core throughout. We now need to connect that mathematical picture to something physical. What does the spinning arrow represent in a quantum computing architecture? And what’s it got to do with quantum logic operations?

Grounded and excited

Let’s collapse the discussion down to the simplest possible case. Imagine a single atom with two energy levels — low vs high, or, in more physicsy language, ground vs excited — that we decide to use as our quantum bit. Better still, imagine a single charged atom: an ion. Because it’s charged, we can hold it in place using carefully arranged electric fields in an ultrahigh vacuum chamber. We can isolate it from much of the surrounding world, prod it with lasers and microwaves, and read out its state using light. And this is not just a physicist’s pipe dream: trapped ions are one of the leading quantum computing platforms.

We’re going to label the lower-energy state as $\ket{0}$ and the higher-energy state as $\ket{1}$. Those symbols are kets, and they come from Dirac notation — a compact, no-frills mathematical language describing quantum states, as introduced, appropriately enough, by the terse and taciturn Paul Dirac. (For much, much more on kets, bras, brakets, and Dirac notation in general see Chapter 6 of these notes and references therein.)

Throughout this post, however, we won’t require any of the mathematical machinery of Dirac notation other than kets. And, importantly, a ket is nothing more than a label; $\ket{0}$ means “the (ground) state we are calling zero”, and $\ket{1}$ means “the (excited) state we are calling one”. We could just as easily label them as |😐⟩ and |🤩⟩. The ket is not the ion, any more than the word “Nottingham” is the city; it is the mathematical label we use for a physical state of the ion. Map, not territory.

The detailed physics of these two states also doesn’t matter when it comes to getting a grip on the core principles underpinning quantum computing. (If you’re innately detail-focussed, however, see this comprehensive review of trapped-ion QC. And if you want a shorter summary of the key differences between our simplified demo and a real experiment, see this note.) What matters is that the system has two well-defined possibilities: $\ket{0}$ and $\ket{1}$. These are our basis functions.

Odds and arrows

We’re now at the point where all that effort put into understanding phasors comes into its own; the rotating arrows are going to be our quantum book-keepers. A two-state ion is not described by a simple tick-box saying “ground” or “excited”. Instead, each possibility has an amplitude attached to it. An amplitude is a weighting coefficient: it tells us how much of a particular basis state “ingredient” goes into the mixture. For our ion, $c_0$​ weights the $\ket{0}$ ingredient, and $c_1$​ weights the $\ket{1}$ ingredient:

You may not be totally surprised to hear at this stage that the amplitudes c₀ and c₁ are complex numbers; they can therefore be drawn as phasors. Because energy and frequency are two sides of the same coin in quantum mechanics (tied together by the Planck relation E=hf, where h is Planck’s constant), those phasors are not frozen in time, however. They rotate. And they rotate at different rates due to the difference in energy of the $\ket{0}$ and $\ket{1}$ states, as shown in the demo below…

Don’t worry for now about the “Control frame” button. All will become clear(er) soon. (I hope.) For now, stick with “Raw phase”. The rotating phasors represent $c_0$ and $c_1$. The “Superposition mix” slider changes the relative lengths of those two phasors; the bars underneath show the corresponding measurement probabilities. Longer phasor means larger probability; zero-length phasor means that outcome will not appear.

The probability of a measurement outcome is given by the square of the phasor’s length. This is the infamous Born rule.

Why the square of the length? That is a great — and deceptively deep — question. There are long-standing arguments about just why probabilities in quantum mechanics should take this form. (See the first couple of paragraphs of this paper for a flavour of the extent of the debate.) But exactly how best to understand the origin of the Born rule depends on how one thinks about quantum states, measurement, and probability itself.

For our purposes, we can be more pragmatic. The rule is simple to apply and spectacularly well tested: square the length of the phasor to get the probability.

If the ion is definitely in the ground state (i.e. the “Superposition mix” slider is all the way to the left), then the phasor for $\ket{0}$ has length 1, while the phasor for $\ket{1}$ has length zero. Measure the ion, and we find that it’s in the $\ket{0}$ state with 100% probability. No mystery. Likewise, if the ion is definitely in the $\ket{1}$ state (i.e. “Superposition mix” slider all the way to the right), we get $\ket{1}$ every time.

But what’s essential to realise is that even though the probabilities are 100% one way or the other, the phasor in each case is not static — it’s continually revolving. (Even after we make a measurement.)

Moreover, the two phasors do not stay aligned in the “Raw phase” picture. Because the two basis states have different energies, their phasors tick round at different rates. The result is a constantly changing relative angle between $c_0$​ and $c_1$. That relative angle will soon matter, because quantum operations are not just about changing the lengths of these arrows — they are also about setting the phase angles so that amplitudes reinforce or cancel in precisely the right way.

The “Control frame” button shows the same state using a more useful clock. It’s a bit like filming a runner using a camera moving alongside them at exactly the same speed. To someone standing on the pavement, the runner is racing past; to the camera operator moving at the same speed, the runner appears nearly stationary, and the interesting motions are the smaller changes relative to that moving viewpoint. The same trick is happening here. Instead of watching the background phase rotation, we subtract it away and keep track only of the phases that matter for control. The phasors have not stopped being quantum objects; we have simply changed viewpoint. In that frame, the arrows sit still until we deliberately change them. This is the book-keeping frame we will use when we start building quantum logic.

So far, though, all of this has been about the mathematical book-keeping: phasors are just our representation, our model, of how the quantum states evolve. We now need to turn to the nuts and bolts of the quantum mechanics — after all, that’s the central theme of this post. How do we make a measurement? Indeed, what is a measurement in this context?

A light in the black

In the demos below, we’re going to borrow the measurement strategy directly from real ion-trap experiments. Shine a laser tuned to the right frequency on the ion and one state scatters light, making the ion “light up”; conversely, the other state does not lead to scattering and the ion remains dark. For the purposes of the demo, we’re going to associate $\ket{1}$ with the bright outcome and $\ket{0}$ with the dark outcome.

A measurement in this case is a straightforward experimental question: does the ion light up or not? Sometimes that answer is certain: if the ion is prepared in one of the measurement states, the result is fixed. Prepared in one measurement state, the ion scatters lots of light and appears bright; prepared in the other, it remains dark.

For a superposition, however, the amplitudes give probabilities, not a guaranteed result from any single run. So we repeat the same preparation and measurement many times; the pattern of bright and dark outcomes reveals the probabilities encoded in the amplitudes.

“So we repeat the same preparation…” This is crucial. When we measure, we force the superposition to yield one definite outcome: bright or dark, $\ket{1}$ or $\ket{0}$. It is no longer in the original superposition; measurement has collapsed it onto one of the two measurement states. So we go back to the start and repeat. Many, many times. Prepare the superposition, measure, reset, prepare it again, measure it again — over and over, rinse and repeat. The accumulated pattern of bright and dark outcomes across those repeated runs reveals the probabilities encoded in the amplitudes.

The demo below mimics a simplified version of a real trapped-ion measurement. We shine light on the ion and collect scattered photons with a detector. If the ion is in the bright state, it scatters lots of photons. If it is in the dark state, it scatters very few. But real detectors are not perfect. Even when the ion is dark, the detector may still register the occasional stray photon: background light, electronic noise, or what experimentalists call dark counts. So we set a threshold (the dotted vertical line in the shots vs counts histogram). Below that threshold, we call the result dark; above it, we call it bright.

Start with the pulse-duration slider at zero. (We’ll see the relevance of this slider very soon, but for now just ignore it.) We start with the ion in the ground state, $\ket{0}$. Each time we measure the ion — each “shot” — the detector records a number of photon counts. The histogram shows how often each count value occurs across repeated shots. Repeat that preparation-and-measurement cycle a few times and the histogram will build up only on the low-count side of the threshold. Then press “Measure 100 times” (which does what it says on the tin). The ion remains dark across all those repeated measurements; it’s 100 percent in the $\ket{0}$ state.

Now let’s start to prod the ion. The slider controls how long we apply a microwave pulse tuned to the energy gap between the two states. A relatively short pulse — 1.0 microsecond, say — nudges the ion only slightly away from the ground state; a slightly longer pulse pushes its overall quantum state further towards the excited state. (Why? Bear with me.)

Increase the pulse duration (first to 2, then 3, then 4 μs) and measure again. (Make sure you hit the “Reset” button before you change the pulse duration each time in order to wipe the slate clean.) At the shortest pulse times, bright outcomes appear only occasionally. As the duration is increased, they become much more likely. The tempting hypothesis is then “longer pulse means higher probability of brightness (i.e. of being in the excited state)” But keep going and the evidence does not support that picture…

Try a pulse duration of 5 microseconds. Bright.

Now try 10 microseconds. Dark.

Now 15 microseconds. And we’re back to bright.

What’s happening here?

Rabi, set, glow

Let’s do what every good physicist should do in a situation like this: make more systematic and carefully controlled measurements. That’s what the demo below does — it sweeps the pulse duration from 0 to 60 microseconds in steps of 250 nanoseconds (a quarter of a microsecond) and determines the probability of “bright”, i.e. the ion being in the excited state. As you can see, the probability oscillates back and forth as a function of pulse duration.

Those wonderful wiggles are called Rabi oscillations. To reiterate, the microwave pulse is tuned to the energy gap between $\ket{0}$ and $\ket{1}$. As the duration of the pulse is increased, the ion’s quantum state moves from dark towards bright, then back towards dark again. The pulse is not steadily driving the ion into the excited state; it is instead causing a reversible cycle. It is actively controlling the complex amplitudes that determine the relative contributions of $\ket{0}$ and $\ket{1}$ to the superposition. That is why the bright probability rises, falls, and rises again.

This is the bare minimum we require for quantum logic. Once Rabi oscillations appear on demand, we have the fundamental physical ingredient needed for a qubit logic gate: we can prepare and control superpositions of two qubit states.

Now try moving the decoherence slider. The distinct Rabi wiggles decay away. This is what happens when the qubit is no longer sufficiently isolated from its surroundings. Stray fields, vibrations, thermal motion, background radiation, imperfect control pulses — all of these can leak information into the environment, scrambling the carefully controlled phase relationship between the $\ket{0}$ and $\ket{1}$ amplitudes.

That loss of phase coherence is deadly for quantum computing. The entire objective — just as was the case for the DFT — is to make phasors (i.e. complex amplitudes) reinforce or cancel in precisely the right way. If the surrounding world is allowed to keep “poking” the qubit, those phase relationships wash out, the phasors get nudged back and forth uncontrollably, the interference disappears, and all quantum logic goes with it. This is why quantum-computing experiments so often involve ultrahigh vacuum, extreme cooling, vibration isolation, magnetic shielding, and a gobsmacking amount of experimental fuss and bother.

We will now set decoherence back to zero, leave it there, and continue to work in the quantum-mechanical equivalent of the perfect frictionless vacuum beloved of school and undergraduate physics. Entirely unrealistic, yes, but exactly what we need while we learn the machinery of QC. (For a recent readable and fascinating overview of the very many challenges still facing the development of real quantum computers, see this.)

In tune and in time: pulsing on resonance

In a previous demo we had a fictitious “Superposition mix” slider that allowed us to set the lengths of the $c_0$ and $c_1$​ phasors directly. In the real world, the superposition mixture is controlled by applying a microwave pulse for a carefully chosen time. As we’ve seen with Rabi oscillations, a short pulse moves a little amplitude from $\ket{0}$ towards $\ket{1}$ , a longer pulse moves more, and a still longer pulse tips the balance back again. The pulse length is therefore the experimental handle on the phasor lengths, and thus directly controls the measurement probabilities.

The $\pi/4$, $\pi/2$, $3\pi/4$, and $\pi$ labels in the demo below — essentially a tweak of our previous “Superposition mix” simulation — represent microwave pulses (tuned again to the $\ket{0}\leftrightarrow\ket{1}$ transition) with different durations. A $\pi$ pulse is timed to move the ion all the way from $\ket{0}$ to $\ket{1}$, giving the maximum bright probability. A $\pi/2$ pulse lasts half as long and produces an equal mixture of $\ket{0}$ and $\ket{1}$. A $\pi/4$ pulse is shorter again and tips the superposition mixture more heavily towards the $\ket{0}$ state, while a $3\pi/4$ pulse leans the other way and incorporates more of the $\ket{1}$ state in the mix. So the labels are really stopwatch settings: carefully calibrated pulse lengths expressed as angles around the clock face.

We now have the complete control toolbox we need. In the next, and final, section we’re going to come full circle — a complete $2\pi$ radians — and return to Shor’s algorithm, this time from the quantum perspective.

We have finally assembled all the pieces we need. We know how Shor’s algorithm converts factorisation into a period-finding problem. We’ve seen how Fourier analysis turns repeated, periodic structure into peaks in the frequency spectrum. We know how complex numbers are represented by phasors, how phasors encode amplitudes and phases, how measurement turns amplitudes into probabilities, and how resonant pulses let us move amplitude between quantum states. We have also switched into the “control-frame” view, where we’ve shifted our frame of reference and the phasor engineering is much easier to see.

Now let’s put those pieces together to see how a quantum Fourier transform finds the period in a modular exponentiation sequence.

Registering a superposition

Up to this point, our ion has been a one-qubit system: two possible basis states, $\ket{0}$ and $\ket{1}$, with a complex amplitude (i.e. a phasor) associated with each. Shor’s algorithm needs a register: several qubits treated as one combined object. With four qubits, each qubit can be either 0 or 1, so the register has sixteen possible basis states, which we write like this:

These are just four-bit labels. Read as ordinary binary numbers, they correspond to 0, 1, 2, …, 15 in decimal. The state $\ket{0000}$ simply means “all four qubits are in their 0 state.” It is the four-qubit version of starting from $\ket{0}$ in the single-qubit demos. A four-qubit register gives us the sixteen slots we need for the input value, $x$, in our $N=15,\ a=2$ Shor example.

Our first job is to spread amplitude evenly over the register, i.e. to set up an equal superposition of all sixteen basis states. We do that with the $\pi/2$ pulses we have already met: a $\pi/2$ pulse on a single qubit produced an equal superposition of $\ket{0}$ and $\ket{1}$. However, we want to extend the superposition beyond a single qubit so that it spans the four-qubit register. Like this:

Press the Pulse button in the demo below to sequentially go through the steps in engineering the superposition. We start in $\ket{0000}$, with all the amplitude in a single register state: all qubits are in their ground state. In order to establish the superposition — and, more generally, to do quantum logic with more than one qubit — we need to have a mechanism to address individual bits. One way is to apply a weak variation in magnetic field across the register.

Each ion then sits in a slightly different magnetic field, which shifts its $\ket{0}\leftrightarrow\ket{1}$ energy gap slightly. That gives the four qubits slightly different resonant frequencies, $\omega_0,\omega_1,\omega_2,\omega_3$ so that each can be addressed separately. But addressing one qubit does not mean affecting only one basis state. This is key. As we’ll see, a pulse tuned to one qubit acts on that bit wherever it appears across the whole register.

(Note that in a “raw phase” frame, each qubit phasor rotates at a slightly different rate. If we tried to track relative differences in phase in this frame, our heads would be spinning along with the phasors. The demo is therefore drawn in a “control” frame: we account behind the scenes for the microwave frequency associated with each qubit and show only the amplitudes and phases we are actively controlling.)

Pressing the Pulse button applies a $\pi/2$ pulse to whichever qubit is currently selected (via the choice of microwave frequency). The first pulse splits the original $\ket{0000}$ amplitude across the two register states associated with the first qubit, i.e. we have the following state:

(where, to reiterate, we’re setting the relative phase differences to zero for the starting state.) The second pulse acts on the next bit and thus spreads the amplitude over four states.

Why four states? Why does acting on the second qubit produce a superposition involving a mix of all four states, instead of producing two distinct superposition states — one for the first qubit, one for the second? Good question. This one has a straightforward answer (…and nary a mention of bubble gum or wire).

Before applying the second pulse, the register is already in a superposition of two states. Ignoring the relative probabilities of different states for now, consider the effect of the second microwave pulse on both “components” of the superposition state. It does this (momentarily forgetting about factors of $1/\sqrt{2}$ and the like):

and

In other words:

(The factor of 1/2 arises because we have equal probability for each basis state: (1/2)² = 1/4. )

Now take that four-state superposition and apply the next microwave pulse. Using the same logic as above, we’ll end up with a superposition of eight basis states. Application of the fourth and final microwave pulse produces the sixteen-state superposition we need:

where the summation is over all basis states. (Note that (1/4)² = 1/16).

The key point here is that we are not preparing the sixteen amplitudes one by one. We are using bitwise pulses: each pulse addresses one qubit, but acts across the whole register.

Into (and out of) the quMEU

Our carefully prepared sixteen-state superposition is now passed to the quMEU (which, you’ll remember, stands for Quantum Modular Exponentiation Unit.) The inner machinations of the quMEU are most definitely a saga for another day. What matters for our quantum Shor story is what the quMEU outputs.

The quMEU deals with not just one, but two four-qubit registers. The first is the superposition we prepared in the previous section: all sixteen possible input values, x = 0 to 15, represented as four-bit states. The second register starts blank, which in four-qubit notation means $\ket{0000}$. Before the quMEU acts, the combined two-register state is

The first bracket is the input register. The $\ket{0000}$ at the end of the line is the blank output register, waiting to be filled with the modular-exponentiation result. The quMEU leaves the first register alone and writes the modular-exponentiation result into the second register. For example, if we consider the basis state in the input superposition that represents the number 2, i.e. $\ket{0010}$, then the operation of the quMEU is this:

because 2² mod 15 = 4, i.e. 0100 in binary. In general, the quMEU does this:

The first register still holds a superposition of all sixteen values of x, while the second carries the corresponding modular-output value for each component of that superposition. The two registers are therefore correlated: input values 0, 4, 8, 12 are paired with output 0001; input values 1, 5, 9, 13 are paired with output 0010; and so on. This is the quantum version of the classical two-register table we built earlier, and it looks like this:

After the quMEU, the two registers are not merely sitting side by side with independent superpositions. The value in the second register is correlated with the value in the first register, so the overall two-register state cannot be written as a product of the first and second registers. This is entanglement.

Entanglement often gets wrapped up in unnecessary mysticism in pop sci accounts of quantum physics. Here it simply means that the two registers are correlated and cannot be treated as independent. The second register does not carry a value unrelated to the first; it carries the modular-output value associated with each first-register component.

To keep the discussion of the quantum Fourier transform as clear and simple as possible, let’s imagine we’ve made a measurement of the second register and got $0010$. This means that the first register is immediately reduced to the values that were paired with $0010$, i.e. $1,5,9,13$. All the other components are removed by the measurement, because they were correlated with different output-register values. So the first register is reduced to

$\frac{1}{2}\left(\ket{0001}+\ket{0101}+\ket{1001}+\ket{1101}\right)$

Now let’s put the quantum Fourier transform to work.

Fourier, quantised

There is just one final aspect of $\pi/2$ pulses that we need to understand before the QFT is unleashed. Previously, they were used to construct a superposition:

But a $\pi/2$ pulse behaves differently when both states it connects already contain amplitude. Earlier, when we used $\pi/2$ pulses to build our sixteen-state superposition, each pulse was effectively pushing amplitude into an empty state. For example, starting from $\ket{0}$, a $\pi/2$ pulse produces a balanced mixture of $\ket{0}$ and $\ket{1}$. In that situation, it is natural to think of the pulse as “creating superposition.”

But that is only half the story. A $\pi/2$ pulse also works essentially in reverse: it can take amplitude from two connected states and recombine it. If both states already contain phasors, the pulse mixes those phasors together. Where they are aligned, the result is reinforcement. Where they have opposite phase, the result is cancellation.

So, in the QFT stage, the $\pi/2$ pulse is not simply creating “more superposition.” It is recombining amplitude that is already present in the register.

In the simplest phase convention, and if we consider only one qubit, the pulse does this:

but it also does this,

So if amplitude is already present in both states, the two contributions are added into one output and subtracted into the other. That is where the reinforcement and cancellation come from.

This same add-and-subtract logic is what Fourier analysis has been doing all along. The classical and quantum versions differ in implementation, but not in the underlying idea: arrange phasors so that some combinations reinforce and others cancel.

The classical DFT we looked at before explicitly looped through each frequency $k$ and summed up phasors at each step. If those phasors aligned, we had a peak in the DFT; if not, we had cancellation and no output in the DFT.

The QFT does not — indeed, cannot — loop through $k$ in that way, however. Instead, the possible $k$ values are output states of the QFT register, and the pattern of reinforcement and cancellation is imposed by applying the correct sequence of pulses and “wait” events (during which the phase evolves, i.e. the phasors rotate).

The demo below is, I’ve got to stress, definitely not a complete simulation of a full QFT circuit. It is a stripped-down version designed to show the essential mechanism: mixing pulses recombine amplitudes, waiting allows phases to evolve, and measurement samples the surviving output state.

The QFT of course does not know the period in advance. It is simply the Fourier recipe implemented in quantum form. When that recipe acts on a periodic input, the matching frequency components reinforce, while the others cancel. The answer is not built into the procedure; it emerges from the interference.

Start by pressing the “Step” button. Each press advances one stage of the stripped-down QFT logic. Don’t worry for now just how the pulse/wait events work – we’ll get to that. Instead, focus on the evolution of the row of phasors: some disappear as their contributions cancel, while others survive. When the “Measure once” and and “Measure 100 times” buttons become active at the end of the pulse-wait-pulse sequence, use them to sample the QFT output. (Our tried-and-trusted bright/dark strategy again). A single measurement gives one definite four-bit result; repeated measurements build up the peaks statistically. (But, as before, each time we make a measurement, the entire system has to be reset.)

On the face of it, there’s rather a lot going on in that sequence. But it’s much simpler than it at first seems. There are just two types of action: apply a microwave pulse or do nothing. That’s it. Granted, we have to do nothing for just the right amount of time (so that the phasors we have selected rotate by the correct amount), but it really is just a sequence involving nothing more than those those two actions. (Well, apart from the “Reverse Bits” step at the end, and that only involves reading out the bits in the reverse order when interpreting the result.)

Before we break down the operation of the QFT, however, let’s first explain the output. We have spikes at k = 0, 4, 8, and 12 (in my universe, at least; hopefully this holds true in yours too). Why those values?

To understand the output, we’ll use exactly the same phasor logic as for the classical DFT. For each possible Fourier output $F_k$, the phasor angle is set by

For our 1, 5, 9, 13 input we only have four phasors in the 16-bit register that have non-zero amplitude (i.e. non-zero phasor length):

and they each have a phasor length of 1/2. That’s what’s shown in the first row in the diagram below…

The expression for the discrete Fourier transform in this case is this:

where the $f_n$ are our input values, the summation runs over all sixteen states (n=o to n=15), and k is the Fourier output index, or, in other words, the frequency.

For the input we’re considering here, i.e.

the $f_n$ values in the expression for the DFT are very simple indeed:

or, in qubit/binary notation:

and the other twelve values of $f_n$ are all zero.

For the first row in the schematic above, k = 0. That means that the exponential term in the expression for the DFT is also very simple indeed. It’s exp(0) = 1. Hence, the DFT output for k = 0, i.e. F₀, is simply 1/2+1/2+1/2+1/2 = 2.

It’s a little bit more algebraically tedious, but conceptually exactly the same, to calculate the output of the DFT for other values of k. For those values, the exponential term doesn’t conveniently reduce to 1. Instead, we have a phasor angle defined by the the value of $2\pi kn/16$; those angles are shown in the diagram above.

If the phasors all point in different directions such that their sum equals zero, as is the case for k=1, 2, and 3 in the diagram, then the DFT output is correspondingly zero.

If the phasors all point in the same direction (or close to the same direction), as is the case for k =4, then their sum is not zero and we get a peak in the DFT.

The same pattern then repeats (because phasors are cyclical): $k=5,6,7$ cancel; $k=8$ lines up again; $k=9,10,11$ cancel, and $k=12$ lines up again. So the QFT output has peaks at

The $k=0$ peak is what’s known as the “DC term” in traditional Fourier analysis. For a pure sine wave, or pure complex exponential (like we looked at before in the context of the classical DFT and zebra crossings), the average value across one cycle is zero. There is therefore not a peak at k=0. However, if we add an offset to the sine wave to push it up or down the y-axis, then its mean value across one cycle (i.e. one period) will no longer be zero, and we’ll see a peak at k=0. (You can explore this here.)

Similarly, our input register,

has a non-zero average across the n=0 to n=15 states of the register; four slots have amplitude 1/2, while the rest have none. So the appearance of the k=0 peak in the spectrum doesn’t tell us anything other than the mean value of the input is not zero. That’s not particularly helpful when it comes to finding the period emerging from Shor’s algorithm.

The useful period information comes instead from the location of the next peak. The $k=4$ Fourier peak corresponds to four complete phasor cycles across the sixteen-slot register, so one cycle has a period of 16/4 = 4.

In other words, the period, r, is 4.

Bingo. The QFT has found the period!

The peaks at $k=8$ and $k=12$ are harmonics: higher-frequency versions of the same repeating pattern. We also saw this earlier with the zebra-crossing DFT: once a fundamental spacing is present, frequencies that fit two, three, or more cycles into the same repeat can also appear. Here, $k=4$ is the fundamental component; $k=8$ and $k=12$ are its harmonics. They are useful confirmation of the period-four pattern, but the lowest non-zero peak gives us the period directly.

For our toy N = 15, a = 2 model, we of course knew already that the period was 4. But for a 2048-bit number, eyeballing the modular-exponentiation pattern is not an option. The QFT turns hidden periodicity into measurable peaks, and those peaks provide the information needed to recover the period.

That’s the QFT output deciphered. We can, in principle, stop here: the hidden period has been converted into measurable Fourier peaks. But if you want to see the machinery under the bonnet, open the section below. That is where we follow the trimmed pulse sequence — mix, mix, mix, wait, mix, reverse bits, measure — step by step. Readers who lack an infinite supply of parallel realities in which to outsource their reading can safely skip ahead to the closing section.

---

Summing up

Assuming that your attention didn’t collapse several thousand words back, we’ve reached the end of this hybrid tutorial-rant. Having worked through the basic steps underpinning the QFT, I am now even more irked by the “electrons splitting the calculation across an infinite number of parallel realities” trope than I was at the start. Hopefully, you are too.

Hilbert space can certainly help us with the book-keeping. But the experiments don’t happen in Hilbert space: the kets didn’t factor N=15 by themselves, and the matrices didn’t instantaneously transmit the period from some multiverse-spanning server farm. The QFT implements exactly the same Fourier logic as its classical DFT cousin: rotate phasors, sum them, and see what survives. What matters is the controlled physical evolution of amplitudes via phases, pulses, waits, interference, and measurement. This is the nuts-and-bolts of quantum logic — the mechanics of quantum mechanics.

And it all happened in this universe.

Acknowledgments: Anthropic’s Claude Opus 4.5 was used iteratively as a coding assistant to help generate and refine the interactive simulations in this post. The physics explanations, design choices, and final edits are my own. I would also like to thank my colleague Adam Gammon-Smith for his feedback and suggestions for improvement of the post.