mxx1's avatar

Shor Thing

When people talk about quantum computing, the reference point is usually Peter Shor’s breakthrough in 1994. Shor showed that a quantum computer could factor very large numbers in a radically different way to a classical machine.

In fact it’s about all quantum computers are good for. And even that’s theoretical, not practical.

On a classical computer, the number of steps required to factor an integer with n digits grows approximately as

10^{n/2}

On a quantum computer, Shor’s algorithm instead requires a number of steps proportional to the square of the number of digits:

n^{2}

The difference is exponential growth versus polynomial growth.

Factoring problems that would take classical machines longer than the age of the universe could, in principle, be solved by a quantum computer in hours or days.

Practically speaking this is the only reason why cryptographers, computer scientists, and governments pay so much attention to quantum computing.

Worked example: RSA encryption key

The largest RSA number ever factored, RSA-768 (a 768-bit modulus), was completed in 2009. It required about 2,700 CPU-years of computation and took roughly two and a half years of real time from start to finish. RSA-2048 is about 10^11 times harder to factor in a traditional computer. Even if you had a million-core supercomputer dedicated to the task, the runtime would be on the order of 270 million years.

Quantum Computer: roughly 5–7 days continuous runtime on a machine with under one million noisy physical qubits, assuming ~0.1% gate error rates and surface-code error correction.

Just for the record, this is how RSA works.

Public key: N, e
Private key: d

Construction: N = p*q where p and q are two secret prime numbers which are quite easy to find with simple maths. e is usually chosen by convention, unless it needs to be modified.

Publish the public key, N and e. Keep the private key, d, private.

d is calculated with simple maths from knowing e, p and q.

Assume M is a numeric representation of a plaintext (eg ASCII hex) character in a secure message.

Encrypt: C = M^e mod N
Decrypt: M = C^d mod N

RSA is designed so you can give out your public key to anyone without risk. The idea is:

Public key (N, e): shared openly so anyone can send you encrypted data or check your digital signature.

Private key (d): kept secret so only you can decrypt or sign.

If they want to send you a message then they have their own private keys and publish their public keys.

—

Now here’s the cracking process in plain  English;

1. Everyone can see the public key: it contains one huge number, created by multiplying two very large secret prime numbers together.

2. The private key is built from those primes: if you know them, you can do the arithmetic that unlocks the messages.

3. To crack RSA, you must split the huge public number back into its two secret primes. That’s called factoring. Being primes, there is only pair per N.

4. Once you have those primes, the rest is easy: you can calculate the private key, and then read any message or forge a digital signature.

So the entire security of RSA rests on one thing: how hard it is to split a giant number into the two unique primes that made it.

Note: Forward is easy, backward is hard

Key generation (forward): Start with two secret primes. For example: p = 61 and q = 53. First check they are prime (meaning they have no divisors other than 1 and themselves), which is easy and quick. Once confirmed, multiply them to get N = 61 × 53 = 3233. Publish N (and e). Keep p and q private.

Attacking (backward): If someone only sees N = 3233, they must figure out what two primes multiply to it. For a small number like 3233, that’s easy — divide and eventually you find 61 and 53. You also have to check those are primes. For numbers this small this process is trivial.

Why is it quick to find primes with digital computers? Because primality testing is very different from factoring. To test if a number n is prime, you don’t need to find its factors; you just need to verify whether any exist. There are efficient algorithms for this that rely on modular arithmetic and number theory.

For example, the AKS primality test (2002) is deterministic and runs in polynomial time. Even before that, probabilistic algorithms like Miller-Rabin or Solovay-Strassen could determine primality extremely fast with negligible error. These work by checking congruences that primes must satisfy, and they run in time roughly proportional to a small polynomial in log(n), which is tractable even for numbers with hundreds or thousands of digits.

Factoring, by contrast, is hard because you must actually find the factors, not just confirm whether they exist, and no known classical algorithm can do this in polynomial time.

For real RSA, N is hundreds of digits long. Running this process backward on a 2048-bit N is practically impossible on classical computers. That’s the one-way door that makes RSA secure. For a 2048 digit number there are more primes smaller than the number than there are atoms in the universe. So we can’t just keep a database on these primes as a workaround, there simply isn’t enough matter to make the database.

—

How does Shors Algortithm work? It exploits the fact that factoring an integer can be reduced to finding the period of a modular exponentiation function, a task that is exponentially hard classically but can be solved efficiently with a quantum Fourier transform. A quantum computer prepares superpositions of possible exponents, evaluates modular powers in parallel, and then uses interference to extract the hidden period with high probability. Once the period is known, classical number theory (via the Euclidean algorithm) yields the nontrivial factors of the original number. The speedup arises because the quantum Fourier transform identifies periodicity in polynomial time, something no known classical algorithm can do.

Because that reads like gobbledygook, this is the whole Shor’s-for-15 process in plain English, keeping the flavour of qubits but without the heavy notation.

Starting Point

We want to factor 15. Of course we know 15 = 3 × 5 (both primes), but we want to see how a quantum computer uncovers that.

1. All qubits start at 0

12 qubits: 8 for x, 4 for f(x). In Shor’s algorithm, x is just the input number you feed into the function
f(x) = a^x mod N. This is core equation inside Shor’s algorithm.

  • N is the number we want to factor (say 15).
  • a is a number smaller than N, chosen at random but not sharing a factor with N (say 2). In Shor’s algorithm, a is just a random number you pick that is smaller than the number you want to factor.
  • x is the value of the quantum register.

The quantum computer’s job is not to factor N directly, but to find the period of function above. Once you know the period, the rest is just ordinary number theory that gives you the factors.

So we start at:
State: |00000000⟩|0000⟩.

That is just setting the stage.

THis means there are 12 qubits in total. The algorithm uses two groups.

  • 8 qubits for the input number x
  • 4 qubits for the output of the function f(x)

All qubits start in the zero state: before doing anything, every qubit is just 0. Think of it like a blank spreadsheet with 12 empty cells, all set to zero.

The notation |00000000⟩|0000⟩ means:

  • the first 8 qubits (the input register) are all 0 → |00000000⟩
  • the second 4 qubits (the function register) are all 0 → |0000⟩

So at the very beginning, the machine is just a clean slate: no superpositions, no patterns, just all zeros.

2. Superposition of x

Hadamards Gate makes the first 8 qubits hold all numbers from 0–255 at once. Now we’re in a quantum cloud where every possible x is held in the input register qubits simultaneously.

Note as N gets larger you need more qubits.

3. Compute f(x) = 2^x mod 15

We have two registers of qubits:

  • the first one is holding the input number x
  • the second one will hold the output f(x) = 2^x mod 15. The function is applied by all these little waveform signal inputs into these qubits which effectively apply what are called quantum gates to these qubits, which add up to this function.

When the quantum computer applies the function, it doesn’t loop through x’s one by one like a digital computer would. Because the first register is in superposition, it holds all x’s at once. The machine therefore calculates the output for every one of those x’s simultaneously and stores all the results in the second register.

Now the two registers are linked:

  • if the first register is 0, the second must be 1
  • if the first is 1, the second must be 2
  • if the first is 2, the second must be 4
  • if the first is 3, the second must be 8
    … and so on.

That link is what “entangled” means here. The state of one register determines the state of the other. You can’t describe them separately anymore. Each x is entangled with its function value.

Here are the first 16 values for f(x) = 2^x mod 15:

x=0 → 1
x=1 → 2
x=2 → 4
x=3 → 8
x=4 → 1
x=5 → 2
x=6 → 4
x=7 → 8
x=8 → 1
x=9 → 2
x=10 → 4
x=11 → 8
x=12 → 1
x=13 → 2
x=14 → 4
x=15 → 8

You can see the period right away: the outputs repeat every 4 steps as 1, 2, 4, 8, then back to 1.
So the second register looks like this 1, 2, 4, 8, 1, 2, 4, 8 … and the period is 4.

4. Measurement of second register (collapse to one value)

For superconducting qubits (used by IBM, Google, Rigetti, etc.) a qubit is a tiny electrical circuit that can resonate in two energy states. To measure it, you send in a microwave pulse and watch how the circuit responds. The ground state (|0⟩) and the excited state (|1⟩) reflect the microwave probe differently. By detecting the reflected signal with a sensitive amplifier, the system can tell whether the qubit is in 0 or 1.

When the quantum computer measures the second register like this, it is forced to give a definite answer to the question “what remainder do I see for 2 to the power of x, divided by 15?” There are only four possible outcomes: the remainder can be 1, 2, 4, or 8. These are stored in the second register in binary form: “0001” for 1, “0010” for 2, “0100” for 4, and “1000” for 8.

Suppose the outcome is 1. The act of measurement freezes the second register into the binary digits for “0001.” At that very same instant, the first register, which was previously spread over all numbers, also snaps down. It is no longer allowed to be every possible value of x. It must now be one of the x values that give remainder 1. Those happen to be 0, 4, 8, 12, and so on.

So instead of a vast cloud of every possible number, the first register is now a patterned set: only every fourth number remains. If you wrote those out in binary, you would see the same simple rhythm: 0000, 0100, 1000, 1100 … each one stepping forward by four.

That collapse is the turning point. Before measurement the system was messy, containing all numbers at once. After measurement it is ordered, with a clear regular spacing. The quantum computer has essentially filtered the superposition and the Fourier transform in the next stage can reveal as the hidden period.

Yeah, yeah – there’s a bit of magic in this “snapping down” – read my blog on “quantum computing, explained” if you want to pick up that thread.

5. Apply Quantum Fourier Transform (QFT)

Imagine the first register after collapse. It no longer holds every number, it holds only every 4th one: 0, 4, 8, 12, and so on. If you plotted that on a number line, it would look like the teeth of a comb — evenly spaced bumps with gaps in between.

The Quantum Fourier Transform is like taking that comb pattern and asking “what rhythm produces this spacing?” In math terms, it swaps from looking at positions (0, 4, 8, 12 …) to looking at frequencies.

When you do that, you see a few sharp peaks at particular places. In this case, those peaks show up at 64, 128 or 192. Now, when we actually measure that register, the quantum computer can’t give us all the peaks at once. It must collapse to one definite number. For example, you might see 64.

So the QFT step is the bridge: it takes a regular spacing in the first register and makes it obvious in a new language (frequency), where the period pops out as one value instead of a messy spread.

6. Statistical measurement of first register

If you do the whole process again and again those peaks show up at 64, 128, and 192 keep showing up often, while other numbers hardly ever appear. That repeating bias in the results is what tells you the period.

If you reset the machine and run the algorithm again, you might see 128, or 192. Each single run looks like just one number, but if you repeat the whole experiment many times and collect the results, you see a clear pattern: the same few numbers show up again and again, while everything else almost never appears.

That is the statistical part. Every measurement is just one sample, but the collection of many samples reveals the hidden structure — the period of the function.

7. Classical processing

After the Fourier step you measure the first register and get a number, say 64. To interpret it, divide by the register size 256. That gives 64/256 = 1/4. What matters is the fraction: the denominator, 4, is the period r.

Other likely results work the same way. If you measure 128, you’d get 128/256 = 2/4, and if you measure 192, you’d get 192/256 = 3/4. In every case, the denominator is 4, so r = 4.

Because real machines are noisy, you repeat the whole algorithm many times. Each run gives you just one sample, but over thousands of runs the pattern becomes clear: results always line up with fractions that have denominator 4. That consistency confirms the period.

Now the quantum part is done and the rest is ordinary arithmetic. With a = 2 and r = 4, we compute a^(r/2) = 2^2 = 4. Then we check:

gcd(4 − 1, 15) = gcd(3, 15) = 3

gcd(4 + 1, 15) = gcd(5, 15) = 5

Where gcd is the largest number that divides two numbers evenly.

That gives us the two non-trivial factors of 15.

—

Plain Analogy

Classical computer: they do every step one by one, until theynotice the pattern repeats.

Quantum computer: throws all steps into a waveform, then uses Fourier transform to “listen” to the rhythm of repetition. Once the period is found the arithmetic gives the factors.

—

Final point – what is the economic value of quantum computers running Shors? Once you can use the crowbar to pry a castle door open, the value disappears because the barrier is gone and the usual Viking would throw the crowbar away (unless they didn’t have other weapons at hand). Shor’s algorithm is similar: once someone uses a quantum computer to break RSA by factoring large numbers, the entire encyrption/crypto technology sector collapses. Its value is transitional, enormous at the moment of breakthrough, then vanishing once alternatives are adopted.

Accpeting this, it makes sense for government investment into quantum computing because that short period when the enemy has this technology before you do will be very uncomfortable.

However, for privaate investors, Shor’s does not represent real value, unless you plan to auction it to the highest government bidder. Or unless someone finds another high value algorithm.

Here are the rather dubious and unproven options:

Quantum linear algebra speedups
LLMs are dominated by linear algebra: multiplying very large matrices and vectors. Quantum algorithms (like Harrow–Hassidim–Lloyd, HHL) suggest exponential speedups for solving certain linear systems. In principle, this could accelerate transformer layers. But the algorithms usually require conditions (like well-conditioned sparse matrices and efficient quantum state preparation) that don’t match real LLM training data.

Quantum memory and embeddings
Theories exist about representing embeddings as quantum states, allowing superposition-based similarity search or retrieval with speedups over classical nearest-neighbor methods. This could make inference faster or cheaper in some niches.

Quantum generative models
Quantum Boltzmann machines and quantum GANs have been proposed. These are generative models that use quantum sampling, but so far they have only been toy demonstrations on a handful of qubits.

Quantum-inspired algorithms
Some algorithms inspired by quantum mechanics (like tensor networks) already run classically and help with compression or acceleration of neural nets. They prove useful, but they don’t require an actual quantum computer.

Native Quantum Simulation
Some domains are natively quantum, meaning the system itself is governed by quantum mechanics and classical models are only approximations. In those cases, a quantum computer is a more natural fit. The main proven category here is quantum simulation:

Quantum chemistry: molecules, bonds, reaction pathways. Classical methods (Hartree–Fock, DFT) are approximations that scale badly as the number of orbitals increases. Quantum computers, in principle, can model the exact wavefunction with polynomial resources. This has already been demonstrated in small cases (e.g. hydrogen, lithium hydride, beryllium hydride). But its gas phase only, can only be used to predict reaction rates, not physical or chemical properties.

Condensed matter physics: systems like superconductors, strongly correlated electron materials, and spin lattices are quantum many-body problems. Classical simulations blow up exponentially; quantum computers can directly represent the state.

Quantum field theory: early work shows that lattice field theories (like lattice QCD) could be simulated more efficiently with qubits than with classical Monte Carlo.