Shor’s algorithm and cat qubits

  1. 1Rhythm
  2. 2Score
  3. 3Errors
  4. 4Reveal

Play through quantum’s most famous algorithm

Shor’s algorithm could one day break the encryption that protects the internet. Learn how it works through 3 puzzles.

About five minutes. No physics required.

// Puzzle 1 of 3

Find the rhythm

Your bank connection is safe because splitting a huge number into its two prime factors is extremely hard. Shor’s trick turns that problem into a different one: finding a rhythm.

Sigma the cat pointing at a wave

Let’s split 15

After how many multiplications are you back at 1?

That rhythm is all you need

    This works for most starting numbers. When it doesn’t, you pick another one and try again.

    Small numbers, short rhythms. Big numbers, impossible ones.

    The numbers that protect the internet are 617 digits long. Their rhythm can run for up to 10617 steps, far more than the roughly 1080 atoms in the observable universe. Classical computers have smarter methods than counting step by step, but none is fast enough.

    A quantum computer doesn’t count. It finds the rhythm through interference, all at once. That is Shor’s algorithm.

    // Puzzle 2 of 3

    Compose the score

    Same rhythm as puzzle 1: powers of 7 on the 15-hour clock. This time, a quantum computer finds it. Its program is written like sheet music: each line is a qubit, read from left to right. Put Shor’s four movements in the right order in six tries or fewer.

    Sigma the cat, half cat and half skeleton
    1. Click the blocks under the staff. Each click fills the next empty slot, left to right. Click a placed block to remove it.
    2. Press “Check my score” once all four slots are full. You have six tries.
    3. Read the colors the game gives back for each block:
      Right block, right place In the score, wrong place Not in the score

    Click a block below to place it.

    Each block does one job. Its description appears here when you click it.

    Writing the score is the easy part. Playing it is not.

    To factor a 617-digit number, this circuit has to run billions of operations without a single note going wrong. Real qubits are noisy, and one uncorrected error ruins the music. So every useful quantum computer needs error correction.

    // Puzzle 3 of 3

    Hunt the errors

    Qubits make two kinds of mistakes. A bit-flip swaps 0 and 1. A phase-flip flips the hidden sign that interference relies on. Error correction never looks at the data directly: it runs checks that light up when neighbouring qubits disagree. Your job is to find the faulty qubit from the lit checks.

    Sigma the cat fixing something with a screwdriver

    Level A: ordinary qubits

    Both kinds of error can happen, so you need both kinds of check, woven into a grid. Each round hides one bit-flip and one phase-flip. Each yellow qubit is watched by the blue checks around it. Tap the yellow qubit that sits between two lit checks of the same color.

    Qubit Check, all quiet Bit-flip check, lit Phase-flip check, lit
    This board: 25 qubits and 16 checks

    Now meet the cat qubit

    A cat qubit is built so that bit-flips become exponentially rare: add a few photons to the “cat”, and they get rarer still. With only phase-flips left to catch, you don’t need the grid any more.

    Level B: cat qubits

    Only phase-flips left, so one row of checks does the job. Tap the cat qubit next to the lit checks.

    Check, all quiet Phase-flip check, lit
    This board: 7 qubits and 6 checks

    Two kinds of error: a grid. One kind: a line.

    2D
    Ordinary qubits: two kinds of check, spread over a surface
    1D
    Cat qubits: one kind of check, along a line

    That difference is why a computer built from cat qubits needs far fewer physical qubits to run the same algorithm. How many for Shor’s algorithm? That is exactly what our new paper estimates.

    29.10.2026