From Bits to Shor

1.1 Where this all came from

Let's start with a story, because it explains why "quantum computer" is a sensible idea and not science fiction.

• 1928, David Hilbert (German mathematician) asked: is there a mechanical procedure that can decide whether any mathematical statement is true? That question forced people to define what a "procedure", meaning an algorithm, actually is.
• 1936, Alan Turing (English mathematician) answered with the Turing machine: an infinitely long tape of cells, a head that reads and writes one symbol at a time, and a table of rules saying "if you're in state A and read a 1, write 0, move right, go to state B." Every laptop and phone today is, in theory, a Turing machine.
• 1982, Richard Feynman pointed out that simulating nature (atoms, molecules) on such a machine is brutally slow, because nature is quantum. His suggestion: build the computer out of quantum things.
• 1985, David Deutsch (English physicist) wrote down the theory of a universal quantum computer: a Turing machine whose tape and head obey quantum physics.

1.2 So what is quantum computing?

Here's a definition worth memorising:

Two things in that sentence matter. First, it's a different model, not a faster version of the same thing. Second, the speedups apply to specific problems. A quantum computer will not make Word open faster.

That's why, in practice, there are no standalone quantum computers. We have a QPU (quantum processing unit) that sits beside normal hardware, the same way a GPU does. Your CPU runs the program, hands the hard quantum-shaped part to the QPU, gets the answer back and continues.

1.3 Why do we need it?

Reason 1: chips are hitting physical limits

Moore's Law was the observation that the number of transistors on a chip doubles roughly every two years. It held for decades, but transistors are now only a few dozen atoms wide. Shrink them further and electrons start to "leak" through barriers by quantum tunnelling, a quantum effect that makes the transistor unreliable. So the free performance gains are slowing down.

Reason 2: some problems are hopeless for any classical computer

Computer scientists sort problems by how fast the work grows as the input gets bigger. This is computational complexity theory. The main families:

Two examples of how fast things explode:

• Seating 10 people around a round table: \((10-1)! = 9! = 362{,}880\) arrangements.
• A travelling salesman visiting 20 cities and returning home: \(\frac{(20-1)!}{2} = 60{,}822{,}550{,}204{,}416{,}000 \approx 6.08\times 10^{16}\) possible routes.

Play with the growth yourself. Notice how \(2^n\) and \(n!\) go from "fine" to "longer than the age of the universe" within a few clicks.

Reason 3: nature itself is quantum

Here's the clearest way to see it. To describe n qubits exactly, a classical computer must store \(2^n\) numbers (called amplitudes; you'll meet them in Chapter 2). Each extra qubit doubles the memory.

1.4 Bits vs qubits: the side-by-side

Here's the full comparison:

In one line: "Quantum is not a faster classical computer. It is a different tool for specific problems."

Three myths to unlearn

1.5 Classical coin vs quantum coin

A coin shows the deepest difference between the two worlds: where randomness comes from.

A classical coin

• Sample space {H, T}. A fair coin gives \(P(H)=P(T)=0.5\).
• The randomness comes from chaos: initial spin, air, the surface. If you knew all of those perfectly, you could predict the result. It's randomness from ignorance.
• It can be biased (a weighted coin, a special flipping style).
• Computers mostly use pseudo-random number generators (PRNGs): formulas that produce numbers that look random from a starting value called a seed. Same seed gives the same sequence every time. They're fast and reproducible, but predictable if you know the seed and the algorithm.
• True randomness needs physical noise: heat (thermal noise), avalanche diodes, radioactive decay.

A quantum coin

Put a qubit in the state

In words: "plus state equals one over root two times zero, plus one over root two times one." You make it by applying a Hadamard gate (H) to |0⟩.

Measure it and you get 0 or 1 with exactly 50/50 probability. But here the randomness is intrinsic. There is no hidden spin or air current that decided it; physics itself has not decided until you look. That randomness can even be certified with Bell tests, which is how device-independent quantum random number generators (QRNGs) work.

You can also make a biased quantum coin by choosing an angle θ:

With θ = 30°, \(\cos^2 30^\circ = 0.75\), so P(0) = 0.75 and P(1) = 0.25.

Schrödinger's cat

Then there's the famous thought experiment: a cat in a sealed box with a device that is triggered by a single quantum event. Quantum mechanics says that until you open the box, the system is in a superposition of "cat alive" and "cat dead". Schrödinger meant it as a joke about how strange this is. For us, the lesson is: a qubit really is in a blend of 0 and 1 until measured, and opening the box (measuring) forces one answer.

1.6 What quantum computers are good at, and what's still hard

The IBM roadmap (May 2022, updated August 2024) points one way: more qubits per chip, chips linked together, and a shift from "more qubits" to "better, error-corrected qubits".

1.7 The NISQ era, supremacy and advantage

NISQ stands for Noisy Intermediate-Scale Quantum, a term coined by John Preskill in 2018. It describes where we are today:

• Devices with roughly 50 to 1,000 qubits that are not error-corrected.
• Useful for quantum simulation (chemistry, physics), hybrid quantum-classical algorithms like VQE (Variational Quantum Eigensolver) and QAOA (Quantum Approximate Optimization Algorithm), and research and proof-of-concept work.
• Not yet full-scale universal quantum computing.

A useful chart plots physical error rate against number of qubits. NISQ sits above the error-correction threshold. Below that line, adding more qubits for error correction actually reduces errors, and you get fault-tolerant quantum computing (FTQC). Google's Willow chip (2024, reported in Nature 2025) was the first to show error correction getting better as the code grew.

Key areas to watch: cryptography, optimisation, drug discovery, climate modelling.

1.8 How do you physically build a qubit?

A qubit is any physical system with two clearly separated states you can control. Several very different technologies compete:

1.9 Applications: where quantum could actually help

Pick a field.

1.10 The tools you'll use

• Real quantum computers on the cloud: IBM, Google, Rigetti, Fujitsu.
• Fake devices, meaning simulators that copy a real chip's noise (e.g. IBM's FakePerth): IBM Quantum, AWS Braket, Azure Quantum.
• Simulators: The Quantum Land (drag-and-drop, used in class), Qiskit (Python, used in the labs), Cirq (Google).

The developer workflow has four steps: Code (Qiskit / Cirq), Translate the algorithm into a quantum circuit, Choose real hardware or a simulator, Execute (measure, iterate). Inside every run: Initialize qubits, Apply gates, let interference shape the outcomes, Measure to get a classical result.

2.1 What quantum mechanics says

Quantum mechanics is the physics of very small things: atoms, electrons, photons (particles of light). Before it existed, classical physics (Newton's laws) explained footballs and planets perfectly, but it could not explain why atoms only emit certain colours of light, or how light and matter exchange energy.

Three ideas are all you need to start:

• Quantised: energy comes in fixed packets. An electron in an atom can only sit on certain energy levels, like a ladder with no half-steps. That's why neon signs glow in specific colours.
• Wave–particle duality: light and electrons arrive at a detector as single dots (like particles), but spread out and interfere (like waves).
• Probabilistic: the theory usually can't predict exactly what will happen, only the probabilities.

2.2 The double-slit experiment

This is the experiment that broke classical physics, and it explains interference, the most important tool in quantum computing.

Fire particles (electrons or photons) one at a time at a wall with two narrow slits, and record where each lands on a screen behind it. Each particle arrives as a single dot. But after thousands of dots, they form stripes: bright bands where many land and dark bands where almost none land. That stripe pattern is what waves do when they pass through two slits and overlap. So each single particle somehow went "through both slits" and interfered with itself.

Now put a detector at the slits to see which one each particle uses. The stripes disappear. You get two plain blobs. Measuring "which path" destroyed the interference.

2.3 The math toolkit (ten minutes, I promise)

Before writing qubits down, you need three small tools. That's genuinely all the math in this course.

Tool 1: complex numbers as arrows

A complex number \(z = a + bi\) (where \(i^2=-1\)) is just an arrow on a 2D plane. It has a length \(|z| = \sqrt{a^2+b^2}\) and an angle called the phase. The neat way to write an arrow of length 1 pointing at angle θ is Euler's formula:

"e to the i theta" is simply "the arrow of length 1 at angle θ". So \(e^{i\pi} = -1\) (pointing left), \(e^{i\pi/2} = i\) (pointing up).

The only thing you'll do with these arrows is add them (head to tail) and then take the squared length \(|z|^2\). That squared length becomes a probability.

Tool 2: vectors and matrices

We write the two basic qubit states as columns of numbers:

The funny bracket \(|\;\rangle\) is called a ket (Dirac notation). It just means "this is a quantum state".

A gate is a 2×2 matrix, and applying it means matrix × vector. Example, the NOT gate X:

Row times column: top row (0, 1) · (1, 0) = 0; bottom row (1, 0) · (1, 0) = 1. So X turns |0⟩ into |1⟩.

Tool 3: the tensor product (combining qubits)

Two qubits together have four basic states: |00⟩, |01⟩, |10⟩, |11⟩. You combine single-qubit states with the tensor product ⊗, which multiplies every entry by every entry:

So n qubits need a column of \(2^n\) numbers. That's the 2ⁿ from Chapter 1.

2.4 The quantum state and measurement

A quantum state holds all the information about a system. For one qubit:

"Psi" (ψ) is the name of the state. α (alpha) and β (beta) are complex numbers called amplitudes. They can be negative or complex, which normal probabilities can't.

The Born rule (measurement)

When you measure, you get:

That's why the squares must add to 1: the probabilities must total 100%. Example: \(|\psi\rangle = 0.6|0\rangle + 0.8|1\rangle\) gives P(0) = 0.36, P(1) = 0.64.

Collapse: after measuring, the blend is gone. If you got 1, the qubit is now |1⟩, and measuring again gives 1 every time.

The Bloch sphere

Because of normalisation (and because an overall phase doesn't matter physically), every single-qubit state can be written with just two angles:

Read θ as latitude and φ as longitude on a globe, and every qubit state is a point on a sphere, the Bloch sphere. North pole = |0⟩, south pole = |1⟩, the equator holds the 50/50 states (|+⟩, |−⟩, |i⟩, |−i⟩) which differ only in phase. Gates become rotations of the arrow.

2.5 Single-qubit gates

Gates are the steps of a quantum program. Each is a small matrix that changes the state, and every gate is unitary, \(U^\dagger U = I\), which means it can be undone. (The dagger † means "flip rows and columns and take the complex conjugate"; it's the "undo" of a gate.) This is very different from a classical AND gate, where you can't recover the inputs from the output.

Gate tables often include a "Native?" column. Native gates are the ones the hardware can do directly (on IBM chips: X, √X, R_z and a two-qubit gate). Everything else, including H, is compiled into native gates by the transpiler before running. That's the "compilation / transpilation" step you'll see in Chapter 3.

2.6 Multi-qubit gates

Single-qubit gates can never link two qubits together. For that, we need gates that act on two or three qubits at once. They're written as bigger matrices on the combined (tensor-product) state.

CNOT's matrix is the identity on the top half (control = 0: do nothing) and an X on the bottom half (control = 1: flip). The Toffoli matrix is the same idea, 8×8, with X only in the last 2×2 block.

2.7 Superposition

Let's look at each phenomenon from three angles: quantum mechanics, physics, and its role in algorithms.

• Quantum mechanics: any isolated system can be a linear combination of basis states, \(\alpha|0\rangle+\beta|1\rangle\). The qubit is not secretly 0 or 1 that we just don't know. It really is in both until measured.
• The math behind it: linearity of Hilbert space. If |a⟩ and |b⟩ are allowed states, then \(c_1|a\rangle + c_2|b\rangle\) is also allowed.
• Physics: a photon polarised at 45° is a superposition of horizontal and vertical. In IBM's chips, a superconducting circuit's two lowest energy levels (from a Josephson junction) form the |0⟩ and |1⟩.
• Algorithms: applying H to each of n qubits creates an equal superposition of all \(2^n\) inputs:

"H on every qubit turns all-zeros into an equal mix of every number from 0 to 2ⁿ−1." With 3 qubits that's |000⟩ through |111⟩, each with amplitude 1/√8. This is the starting move of Deutsch–Jozsa, Grover, Bernstein–Vazirani, QPE and Shor.

2.8 Entanglement

Definition: a multi-qubit state is entangled if it cannot be written as a product of individual qubit states. You can't describe each qubit on its own.

This is the Bell state (also called an EPR pair). Try to factor it: you'd need a product that gives |00⟩ and |11⟩ but no |01⟩ or |10⟩. Impossible. So the two qubits share one joint state.

Building a Bell pair

Measure both: you get 00 or 11, each 50% of the time, and never 01 or 10. Each result on its own is random, but the two always match.

There are four Bell states, and they form a complete basis for two qubits:

Physics: entanglement comes from interactions, e.g. spin–spin coupling, or a crystal splitting one photon into an entangled pair (spontaneous parametric down-conversion). Algorithms: it enables teleportation, superdense coding, QKD, and VQE.

2.9 Interference

Here's the rule that makes quantum computers different from "just randomness":

Classical probability would add the squares instead, \(|\psi_1|^2 + |\psi_2|^2\), and nothing could ever cancel.

Worked example: H twice

Start with |0⟩. After one H: \(\tfrac{1}{\sqrt2}(|0\rangle+|1\rangle)\). Apply H again. Each of the two branches splits again:

• |0⟩ branch → \(\tfrac12|0\rangle + \tfrac12|1\rangle\)
• |1⟩ branch → \(\tfrac12|0\rangle - \tfrac12|1\rangle\)

Now add: |0⟩ gets ½ + ½ = 1, |1⟩ gets ½ − ½ = 0. You always read 0. The two paths to |1⟩ cancelled, just like the dark stripes in the double slit. Put a Z between the two H's and the minus sign moves, so you always read 1 instead.

Algorithmic role: the Quantum Fourier Transform uses interference to isolate frequencies, and Grover's algorithm amplifies the right answer by constructive interference.

2.10 The no-cloning theorem

Statement: there is no operation (no unitary U) that copies an unknown quantum state:

Why (a 4-line proof): suppose such a U existed. It must copy the basis states: \(U|0\rangle|0\rangle = |00\rangle\) and \(U|1\rangle|0\rangle = |11\rangle\). Gates are linear, so for \(|\psi\rangle=\alpha|0\rangle+\beta|1\rangle\):

These only match when α or β is 0. So no machine can copy a general superposition. (Notice the left side is the Bell state: CNOT "tries to copy" and produces entanglement instead.)

2.11 Randomness

Measurement outcomes are probabilistic by the Born rule, \(P(0)=|\alpha|^2,\ P(1)=|\beta|^2\). A photon polarised at 45° gives random horizontal/vertical results. That's fundamentally unpredictable, and Bell tests rule out "hidden variables" that secretly decide the answer.

2.12 Quantum teleportation

What it does: moves a qubit's state from Alice to Bob without sending the particle itself.

What you need: one shared entangled pair (Alice holds one half, Bob the other), and a normal phone or internet line to send 2 classical bits.

How it works, step by step

1. Alice has a mystery state |ψ⟩ on q0. Alice and Bob share a Bell pair on q1 (Alice) and q2 (Bob).
2. Alice applies CNOT (q0 → q1), then H on q0. This is a Bell measurement set-up: it rotates her two qubits so that measuring them in the normal basis tells her which Bell state they were in.
3. Alice measures q0 and q1, getting two random bits m0 m1. Her original state is destroyed (as no-cloning requires).
4. She phones Bob the two bits.
5. Bob fixes his qubit: if m1 = 1 apply X; if m0 = 1 apply Z. His qubit is now exactly |ψ⟩.

2.13 Superdense coding

What it does: Alice sends 2 classical bits to Bob by transmitting only 1 qubit. It's teleportation's mirror image.

1. Share: Alice and Bob share a Bell pair in advance (q0 Alice, q1 Bob).
2. Encode: Alice applies one of four gates to her qubit: 00 → I, 01 → X, 10 → Z, 11 → X then Z (often written "XZ"). This turns the pair into one of the four Bell states.
3. Send: Alice physically sends her one qubit to Bob.
4. Decode: Bob applies CNOT (q0 → q1) then H on q0, and measures both. He reads Alice's two bits exactly.

They are mirror images. Each trades one resource for the other, and both only work because entanglement was shared in advance. Without that pre-shared pair, one qubit can carry at most one classical bit (Holevo's bound).

2.14 Summary table and the Bell-state lab

The lab: "Simulate a Bell state, explain the histogram, then insert one more H"

In The Quantum Land you set the number of qubits, drag gates onto wires, the site translates your circuit to QASM code (a text format for circuits), sends it to a server that runs it many times (shots), and draws the averaged results as a histogram. Use the circuit simulator above to check your reasoning; pick the "Lab" examples from its list.

• Bell state histogram: two bars, 00 and 11, each about 50%. Why: after H + CNOT the state is \(\tfrac{1}{\sqrt2}(|00\rangle+|11\rangle)\); the Born rule gives ½ each, and 01/10 have amplitude 0.
• Add H on q0 at the end: the state becomes \(\tfrac12(|00\rangle+|01\rangle+|10\rangle-|11\rangle)\). All four bars at 25%. The correlation looks gone in this measurement, but it's hiding in the minus sign on |11⟩ (a phase you can't see in a histogram).
• Add the extra H on q0 before the CNOT instead: H·H = I by interference, so q0 is back to |0⟩, the CNOT does nothing, and you get 00 with 100%. Where you put a gate matters.

3.1 What is a quantum algorithm?

Definition: a quantum algorithm is a set of instructions written to run on a quantum computer. It uses superposition, entanglement, and interference to solve problems in ways classical logic cannot. The goal: measuring at the end gives the correct answer with high probability. The work breaks into four steps:

1. Initialize qubits: prepare the starting state, often |0⟩.
2. Apply quantum gates: transform the state (H, CNOT, phase gates, an oracle).
3. Use quantum interference: design operations so useful outcomes become more likely and unwanted ones less likely.
4. Measure the qubits: get classical results (0s and 1s) and interpret them.

A point that's easy to miss: the circuit is only one part of the algorithm. The full cycle is Initialize → Operate → Measure → Interpret. Classical set-up before the circuit and classical post-processing after it (like the gcd step in Shor) can matter just as much.

Why quantum algorithms matter now

• Unlocking quantum potential: hardware is useless without algorithms that give it problems to solve.
• Quantum speed-up: Shor's and Grover's algorithms show real advantages over classical approaches. Shor breaks public-key crypto (RSA, ECC); Grover speeds up brute-force search, which weakens symmetric keys like AES.
• Future innovation: better hardware enables more experiments, which leads to better algorithms.

The best one-line summary of the whole field:

Or put simply: "Think of it as a program built for quantum hardware, not magic or a faster answer to every problem."

Sorting the famous algorithms: The ones covered in this course are Deutsch–Jozsa, Bernstein–Vazirani, Grover, QPE, Shor and VQE. Others you'll hear about: QAOA (optimisation), Simon's algorithm, HHL (linear equations) and quantum walks.

3.2 How a quantum algorithm is developed

Think of it as a winding road with these stops. It's a cycle: when results are inaccurate or noisy, you go round again. A useful split: steps 1–4 happen on paper and on a perfect simulator; steps 5–7 happen on a real, noisy chip.

1. Problem framing: define the goal, inputs and outputs.
2. Algorithm design: map the math to quantum primitives (superposition, oracle, QFT…).
3. Circuit construction: write the circuit with gates and measurements (Qiskit).
4. Validation on an ideal simulator: check amplitudes and probabilities with no noise.
5. Compilation / transpilation: rewrite for a specific chip's native gates and wiring; optimise.
6. Noise modelling and fake back-end: emulate realistic errors with a fake device (e.g. FakePerth).
7. Execution: run on the chosen back-end with a chosen number of shots.
8. Result analysis: collect counts, compute metrics (accuracy, fidelity).
9. Iterate and optimise: reduce circuit depth, refactor sub-circuits.

3.3 Why we transpile: the chip's wiring

Now the step most beginners skip: transpilation. Your circuit assumes any qubit can talk to any other, using any gate. A real chip can't do that, for two reasons:

• Wiring: qubits are only connected to their neighbours. The map of which qubits are wired together is the coupling map.
• Native gates: the chip only understands a few gates. IBM Heron chips: CZ, RZ, SX and X. Everything else (H, CNOT, Toffoli…) must be rewritten in those.

Example: IBM's 7-qubit chip. You want a CNOT between qubit 0 and qubit 6, but they aren't wired together. The transpiler moves qubit 0's state step by step with SWAP gates along the route 0 → 1 → 3 → 5, so it ends up next to 6. That's 3 SWAPs, and since each SWAP = 3 CNOTs, that's 9 extra noisy gates. Click two qubits below to see the route.

The 6 phases of transpilation

Every circuit is rewritten in six phases before it runs:

That's exactly the line transpile(qc, simulator) in every lab, and the Grover lab uses optimization_level=3. IBM's own tests show the best level depends on the circuit, so compare them.

3.4 Oracles and quantum parallelism

The oracle

A quantum oracle is a black-box operation used to evaluate a function or check properties of an input without revealing its internal mechanism. You can't look inside; you can only query it. We compare algorithms by counting queries. Think of a locked vending machine: you only learn about it by pressing buttons.

There's a catch: quantum operations must be reversible. A function like AND isn't: if AND outputs 0, you can't tell whether the input was 00, 01 or 10. So the standard oracle keeps the input x and XORs the answer into an extra qubit y:

"The oracle preserves x and writes f(x) into y using XOR." Applying it twice gives back the original (y ⊕ f ⊕ f = y), so it's its own inverse and a valid unitary. That's why we need the auxiliary qubit.

Quantum parallelism

Quantum parallelism is the ability of a quantum computer to apply an operation to multiple inputs simultaneously by using a superposition of quantum states. Put H on every input qubit, then call the oracle once, with y = 0:

One call to \(U_f\), and the state now "contains" f(x) for every x. Example with f = AND on 2 bits: after H⊗H and one oracle call the state is \(\tfrac12\big(|00\rangle|0\rangle + |01\rangle|0\rangle + |10\rangle|0\rangle + |11\rangle|1\rangle\big)\). That's all 4 rows of the AND truth table after one call; classically that takes 4 calls.

3.5 Phase kickback: the trick behind the oracles

Phase kickback is a quantum effect where a controlled operation transfers phase information from the target qubit to the control qubit's superposition. In three steps: control in superposition → controlled operation → relative phase changes. It sounds backwards, but it's how oracles "write" their answer into the qubits we measure. And it's useful because quantum computers can transform phase information into measurable outcomes through interference.

The key fact: the state \(|-\rangle = \tfrac{1}{\sqrt2}(|0\rangle-|1\rangle)\) is unchanged by X except for a sign, \(X|-\rangle = -|-\rangle\). So:

If f(x) = 1, the oracle flips the target, which just multiplies everything by −1. That minus sign "belongs" to |x⟩. The target is untouched; the information jumped ("kicked back") into the phase of the input register.

A two-line derivation shows it directly with the XOR oracle on target |−⟩:

In short: teleportation and superdense coding move data between people; phase kickback works inside a circuit to compute.

A demo

1. Preparation: q0: H → |+⟩. q1: X then H → |−⟩.
2. Kickback: CNOT (q0 control, q1 target). The control changes from |+⟩ to |−⟩.
3. Measurement: H on q0 turns |−⟩ into |1⟩. Result: 1 (100%).

Load "Phase kickback" in the circuit simulator to see this.

3.6 Deutsch and Deutsch–Jozsa

The problem

You're given a black-box function f that takes bits and returns 0 or 1. You're promised it's one of two kinds:

• Constant: same output for every input (all 0s, or all 1s).
• Balanced: exactly half the inputs give 0, half give 1.

Which kind is it?

Deutsch (1 bit, 1985)

With one input bit there are four possible functions: f(0)=f(1)=0 and f(0)=f(1)=1 are constant; f(x)=x and f(x)=NOT x are balanced. Classically you must test twice (x = 0 and x = 1). Quantum needs once:

1. Prepare 2 qubits as |0⟩|1⟩.
2. Apply H to both: \(|+\rangle|-\rangle\).
3. Apply the oracle. Phase kickback gives \(\tfrac{1}{\sqrt2}\big((-1)^{f(0)}|0\rangle + (-1)^{f(1)}|1\rangle\big)|-\rangle\).
4. Apply H to the first qubit and measure: you get \(|f(0)\oplus f(1)\rangle\). 0 = constant, 1 = balanced.

⊕ means XOR: it's 0 if f(0) and f(1) are equal (constant), 1 if they differ (balanced). One query answered a question about both values. That's interference at work.

Deutsch–Jozsa (n bits, 1992)

Same idea with n input bits. Classically, in the worst case you must check \(2^{n-1}+1\) inputs (more than half) to be sure. Quantum: one query. After H⊗ⁿ, oracle, H⊗ⁿ, the amplitude of the all-zero outcome is:

If f is constant, all the signs agree and add up to ±1: you see 00…0 with certainty. If balanced, half are + and half are −, so they cancel to exactly 0: you never see 00…0.

The circuit as five boxes (the states ψ₀ to ψ₃ sit between the steps):

1. Initialize n input qubits to |0⟩ and one target to |1⟩
2. Create superposition: H on all (target becomes |−⟩)
3. Apply the oracle \(U_f\): phase \((-1)^{f(x)}\) kicks back
4. Apply H to the input qubits (interference)
5. Measure: all 0s → constant, otherwise balanced

3.7 Grover's search algorithm

The problem: find a marked item in an unsorted collection of N items. Formally, find x₀ where

Picture 1,000 closed boxes, one holds a prize. Classically you open them one by one: about N/2 on average, N in the worst case, so O(N). Grover (1996, Lov Grover) needs only about \(\sqrt N\) queries: a quadratic speed-up. For a million boxes, that's ~785 steps instead of ~500,000.

The four steps

1. Initialise: H on every qubit. All N items get equal amplitude \(1/\sqrt N\).
2. Oracle: flips the sign of the marked item's amplitude (multiplies it by −1) and leaves the rest alone. Probabilities don't change yet, because \((-a)^2 = a^2\). It just marks the answer.
3. Diffusion ("inversion about the mean"): compute the average amplitude, then reflect every amplitude around it: \(a \to 2\bar a - a\). Because the marked one is now negative, it sits far below the mean and gets flung far above it. The others shrink slightly.
4. Repeat steps 2–3 about \(\frac{\pi}{4}\sqrt{N}\) times, then measure.

Each oracle + diffusion pair rotates the state a little closer to the answer, by angle 2θ. After about (π/4)√N turns, you're pointing at it. With M marked items, use \(\frac{\pi}{4}\sqrt{N/M}\).

Worked example with real numbers (8 boxes, target |110⟩)

1. Initialise: 3 qubits, 8 states, each amplitude \(1/\sqrt8 \approx 0.354\), probability 12.5%.
2. Oracle: |110⟩'s amplitude becomes −0.354. Every probability is still 12.5%.
3. Mean: \(\bar a = \frac{7(0.354) - 0.354}{8} \approx 0.265\).
4. Reflect about the mean (\(2\bar a - a\)): wrong answers become \(2(0.265) - 0.354 \approx 0.177\); the target becomes \(2(0.265) + 0.354 \approx 0.884\).
5. Probabilities: target \(0.884^2 \approx\) 78.1%; each other state \(0.177^2 \approx 3.1\%\).

Two iterations is the sweet spot (\(\frac\pi4\sqrt8 \approx 2.22 \to 2\)). A third overshoots and the probability crashes to 33%. Reproduce every number above in the lab below (3 qubits, marked item 110).

3.8 Shor's algorithm

Peter Shor, 1994: a quantum algorithm that factors a composite integer N into its primes in polynomial time. It uses Quantum Phase Estimation and the Quantum Fourier Transform to find the period of a modular arithmetic function.

How close is the threat?

Estimates of how many qubits it would take to break RSA-2048 keep shrinking as algorithms improve, while chips keep growing:

The gap is still huge (thousands of times) and the estimates assume noisy qubits with heavy error correction. In short: Shor breaks RSA/ECC (HTTPS, banking, software updates) because it solves their math fast, but not yet: it needs an error-corrected machine.

The big idea: turn factoring into period finding

Pick a random number a. Look at the powers of a, mod N: \(a^1, a^2, a^3, \dots \pmod N\). This sequence repeats. The length of the repeat is the period (or order) r: the smallest r with \(a^r \equiv 1 \pmod N\). If you know r, a little classical arithmetic gives the factors.

Part 1: classical setup and reduction

1. Pick a random a. Compute gcd(a, N). If it isn't 1, you got lucky: that's already a factor.
2. Hand a and N to Part 2 to find r.
3. If r is odd, or \(a^{r/2} \equiv -1 \pmod N\), pick a new a and retry.
4. Otherwise the factors are \(\gcd(a^{r/2}-1,\,N)\) and \(\gcd(a^{r/2}+1,\,N)\).

Why it works: \(a^r - 1 = (a^{r/2}-1)(a^{r/2}+1)\) is a multiple of N, but (thanks to the checks) neither bracket alone is. So each bracket must share a factor with N, and gcd pulls it out. gcd (greatest common divisor) is fast to compute with Euclid's algorithm.

Part 2: quantum order-finding

1. Put all exponents x into one superposition (H gates on a "control register").
2. Compute \(a^x \bmod N\) into a second register for all x at once (controlled modular exponentiation, \(U_a^{2^j}\) gates). The registers become entangled.
3. Apply the inverse Quantum Fourier Transform to the control register. It turns the repeating pattern into sharp peaks (Chapter 4).
4. Measure: you get a number m with \(m / 2^t \approx s/r\) for some random s. The continued fractions algorithm turns that fraction into r.

Here's why this is phase estimation. Define the gate "multiply by a": \(M_a|x\rangle = |a x \bmod N\rangle\). Its eigenvalues are \(e^{2\pi i k/r}\) for k = 0 … r−1, so its phases are fractions k/r with the period hidden in the denominator. And the easy start state |1⟩ is an equal mix of all those eigenvectors:

How many control qubits? \(m = 2\lceil\log_2 N\rceil + 1\). Example: suppose r = 6, so the phase to find is 1/6. With m = 5, the best approximation is y = 5 out of 32 (about a 68% chance), and 32/5 = 6.4 rounds to 6, which is correct. With m = 4, the best is 3/16, and 16/3 = 5.33 rounds to 5, which is wrong. Too few qubits give a wrong period.

Cost and success: each controlled \(M_a^{2^j}\) costs O(n²) gates (n = number of bits in N) and there are O(n) of them, so O(n³) in total. One run fails (r odd, or trivial gcd) with probability at most ½, so a few repeats are enough. The powers \(a^2, a^4, \dots \bmod N\) are computed on a normal computer first.

Worked example: factoring 15

N = 15, pick a = 7. gcd(7, 15) = 1, so no lucky shortcut. Powers of 7 mod 15:

r = 4 is even. \(7^{2} = 49\). Then \(\gcd(48, 15) = 3\) and \(\gcd(50, 15) = 5\). So 15 = 3 × 5.

Same number, different a

Now use a = 2. Step 1: gcd(2, 15) = 1, so use order finding. Step 2: 2¹ = 2, 2² = 4, 2³ = 8, 2⁴ = 16 ≡ 1 (mod 15), so r = 4. Step 3: x = 2^{r/2} = 2² = 4. Step 4: gcd(4 − 1, 15) = 3 and gcd(4 + 1, 15) = 5. Different a, same period, same factors. (This is exactly what the Shor lab prints for N = 15.)

3.9 Algorithms for today's chips: VQE and QAOA

Shor and Grover need big, error-corrected machines. What can we run now, on 50 to a few hundred noisy qubits where circuits must stay short? The answer is the hybrid loop:

1. Quantum chip runs a short circuit with some rotation angles θ and measures a cost
2. Classical computer (an optimizer) picks better angles
3. Repeat until the cost stops improving

• VQE (Variational Quantum Eigensolver): finds the lowest energy (the "ground state") of a molecule.
• QAOA (Quantum Approximate Optimization Algorithm): finds good answers to optimisation problems like routing and scheduling.

VQE in detail

Input: a Hamiltonian H (the energy operator of the system) and a parametrized circuit (the "ansatz" or variational form) that prepares a trial state \(|\psi(\theta)\rangle\). Cost: the energy of that trial state:

"The average energy you'd measure in the state the circuit makes." By the variational principle, it can never be lower than the true ground energy, so pushing it down gets you closer to the answer.

1. Start from |0⟩ and prepare a reference state (IBM's example: X on qubit 0).
2. Apply the variational form \(U_V(\theta)\) (IBM's example: RZ and RY on each qubit plus one CX, 8 angles in total).
3. Estimate C(θ) on the quantum computer. H is written as a weighted sum of parts (e.g. weights 2, −2, 3, −3); each part is measured and the results are added up.
4. A classical optimizer (e.g. COBYLA) picks the next angles.
5. Repeat until it converges.

In IBM's run, the simulator found a cost of about −6.0 after 136 evaluations; the real hardware ended several percent off after 96. Every new set of angles means running the circuit again, so IBM groups all runs in one session to queue only once.

3.10 Limitations and comparison

Two families of algorithms

Hardware limits

• Noise: qubits lose their state quickly, and gates make errors.
• Error correction: one logical qubit may need hundreds to thousands of physical qubits.
• Scale: today's machines have hundreds to a few thousand qubits. Shor on RSA-2048 needs close to a million noisy qubits (Gidney, 2025, "less than a million").

Algorithm challenges

• Few real speed-ups: only structured problems benefit. Grover's quadratic gain is often eaten by slow quantum clock speeds and error-correction overhead.
• Input and output: loading classical data into qubits can cost as much as the speed-up saves, and each measurement gives very little information.
• No guarantees: VQE and QAOA can get stuck in local minima and "barren plateaus" (flat landscapes where training stalls). Classical methods keep matching claimed advantages.
• Practical limits: deep circuits are destroyed by noise, qubit connectivity is limited, and debugging is hard (you can't peek at a state without destroying it).

Five limits

1. Noise limits circuit size; reliable machines around 2029
2. Speed-ups only for special problems, not everything
3. Measurement gives one answer per shot
4. Loading big data into qubits is slow
5. Expensive: extreme cooling (near −273 °C), many physical qubits per logical qubit

Side by side

4.1 Game: find the hidden beat

Goal: discover the "hidden period" in a repeating pattern, just like the QFT finds hidden periodicities in quantum data. Listen (or watch the dots), then guess how many claps make up one repeat. The loud clap marks the start of each repeat.

When the period is 3, you hear it instantly. When it's 10, you need to concentrate. And if the pattern is long and noisy, your ears give up. The QFT is a mathematical ear that finds the period of a pattern hidden inside 2ⁿ amplitudes, using only about n² gates.

4.2 The classical Fourier transform

The Fourier Transform (FT) expresses a signal as a sum of sine waves with different frequencies. It converts a signal from the time domain ("what happens when") into the frequency domain ("which rhythms are in it").

For a list of N numbers \(x = (x_0, \dots, x_{N-1})\), the Discrete Fourier Transform (DFT) produces a new list \(y = (y_0, \dots, y_{N-1})\):

For each frequency k, walk through the signal, spin each sample \(x_j\) by angle \(2\pi jk/N\), and add everything up. If the signal really repeats at that frequency, the spins line up and add to something big. If not, they point in random directions and cancel. Interference again.

4.3 The Quantum Fourier Transform

In quantum computing, the amplitudes \(\alpha_j\) of the basis states \(|j\rangle\) play the role of the classical numbers \(x_j\). The QFT does the DFT on those amplitudes. On a single basis state:

Every output |k⟩ gets the same size, 1/√N, so a single input becomes a perfectly even superposition. The information is in the phases: output k's arrow is turned by j·k/N of a full circle.

• N: total number of basis states (2ⁿ for n qubits). j: input basis-state index. k: index of each output state.
• 1/√N: normalisation, keeps total probability = 1.
• \(e^{2\pi ijk/N}\): the phase factor applied to each output state.

It changes the computational basis (|0⟩, |1⟩, …) into the Fourier basis (states with evenly spaced phases). And the QFT matrix is unitary (\(U^\dagger U = I\)), so it's a valid quantum gate.

For one qubit (N = 2) the QFT is just the Hadamard gate. For two qubits (N = 4, and \(e^{2\pi i/4} = i\)):

Below, each dial is one output amplitude. Pick an input |j⟩ and watch how fast the hands turn as k increases. The bigger j, the faster they spin. That "spin speed" encodes j.

The product form: why it's cheap

The QFT output turns out to be a product of single-qubit states, one per qubit:

Each output qubit is an equal blend of |0⟩ and |1⟩ with its own phase. One qubit turns j/2 of a circle, the next j/4, the next j/8, like the hands of a clock: second hand, minute hand, hour hand. Because each qubit only needs one H and a few phase rotations, the whole circuit is small.

"Exponential compression": the QFT acts on all 2ⁿ amplitudes at once using only ~n² gates, while the classical FFT needs ~n·2ⁿ steps. But remember the catch from Chapter 3: you can't read all the amplitudes out. The QFT is only useful as a step inside algorithms where one measurement is enough, like period finding.

4.4 Building the QFT circuit, and its inverse

Goal: analyse the periodicity (repeating patterns) encoded in quantum states. The construction for n qubits:

1. For each qubit j from 0 to n−1:
   • Apply H to qubit j.
   • For each later qubit k > j: apply a controlled rotation \(R_m\) with qubit k as control and j as target, where \(m = k - j + 1\).
2. Finally, reverse the order of the qubits with SWAPs (the "bit reversal").

R₂ is a 90° phase (π/2), R₃ is 45° (π/4), R₄ is 22.5°, and so on: smaller and smaller twists.

The 2-qubit QFT

1. H on q0
2. Controlled-P(π/2) from q1 → q0
3. H on q1
4. SWAP q0 and q1

Gate count: n Hadamards + n(n−1)/2 controlled rotations + about n/2 swaps = O(n²). For 3 qubits: 3 H + 3 CP + 1 SWAP.

Inverse QFT (QFT⁻¹ or QFT†)

• Same as the QFT but with negative phase rotations.
• Circuit: reverse the gate order of the QFT, and replace each \(R_k\) by \(R_k^\dagger\) (negative angle). Swaps go at the start (they're their own inverse).
• \(R_k R_k^\dagger = I\), and \(\mathrm{QFT}\cdot\mathrm{QFT}^{-1} = I\).

Lab demo: build the 2-qubit QFT and verify the inverse. QFT then QFT⁻¹ on |00⟩ gives |00⟩ with 100%: a single bar of 1024 counts. Load "QFT then inverse QFT" in the circuit simulator to confirm.

4.5 Finding a hidden period with the QFT

Example: the repeating sequence [1, 2, 3, 1, 2, 3, 1, 2, 3, …] has true period r = 3. In a quantum computer, we encode a period like this: a state that has equal amplitude on every r-th basis state (e.g. |0⟩, |3⟩, |6⟩, …) and zero elsewhere. Apply the QFT, and the output has sharp peaks at multiples of N/r.

Measure, and you get one of those peaks. From the spacing between peaks (or from k/N ≈ s/r) you work out r. The offset x₀ only changes phases, not where the peaks are, which is why it doesn't matter where the pattern starts.

Does the number of qubits matter? Yes.

Running the QFT on n qubits means working in a space of size N = 2ⁿ. The peaks land at multiples of N/r, so you need N to be big enough compared with r. For period r = 4:

What if N isn't a multiple of r (like r = 3 with N = 16)? The peaks get blurry: probability leaks into neighbouring k's. More qubits make the peaks sharper and the estimate of r more accurate. That's exactly why Shor uses about 2·log₂N counting qubits. Try r = 3 above with 3 qubits and then 7 qubits.

What if we don't know the period? One last example, [1,2,3,1,2,3,1,2,3,1, 1,2,3,…], hides a bigger repeat (length 10) inside a smaller one. The QFT still finds it: it reveals every rhythm present, which is something your ears struggled with in the game.

4.6 Bernstein–Vazirani (BV)

The problem: a black box hides a secret bit string a. When you query it with x, it returns the dot product mod 2:

It counts how many positions are 1 in both a and x, and tells you whether that count is odd.

• Classical: n queries. Ask x = 100…0 to learn a₁, then 010…0 to learn a₂, etc. One bit per query.
• Quantum: 1 query, no matter how long a is.

Circuit

1. Initialise \(|0\rangle^{\otimes n}|1\rangle\) and apply H to all qubits (the last one becomes |−⟩).
2. Apply \(U_f\): a CNOT from each input qubit where \(a_i = 1\) to the last qubit. Phase kickback gives \(\frac{1}{\sqrt{2^n}}\sum_x (-1)^{a\cdot x}|x\rangle\).
3. Apply H again to the first n qubits and measure. The result is exactly a.

Why: H⊗ⁿ is its own inverse, and H⊗ⁿ|a⟩ is exactly \(\frac{1}{\sqrt{2^n}}\sum_x (-1)^{a\cdot x}|x\rangle\). So the last H's turn the state back into |a⟩. Interference concentrates 100% of the probability on the secret.

The lab example uses secret_number = '1011001' (7 bits), so 7 + 1 = 8 qubits and 7 classical bits. That's the "BV-8" lab. BV is an extension of Deutsch–Jozsa: both use an oracle and phase kickback.

4.7 Quantum Phase Estimation (QPE)

The problem: you have a gate U and one of its eigenstates |ψ⟩, a special state that U doesn't change except for a phase:

Find φ. (Eigen = "own" in German: |ψ⟩ is U's "own" state, and \(e^{2\pi i\varphi}\) is its eigenvalue.)

The circuit

1. Two registers: n counting qubits in |0⟩ and the target register in |ψ⟩: \(|0\rangle^{\otimes n}\otimes|\psi\rangle\).
2. H on every counting qubit.
3. For each counting qubit j (0 to n−1): apply \(U^{2^j}\) to the target, controlled by qubit j. By phase kickback, counting qubit j picks up phase \(e^{2\pi i\,2^j\varphi}\).
4. Apply the inverse QFT to the counting register.
5. Measure: you get an integer m, and \(\varphi \approx m/2^n\).

After step 3 the counting register is exactly in "QFT form" with j replaced by \(2^n\varphi\). The inverse QFT un-does it and hands you \(2^n\varphi\) as a binary number. With n counting qubits you get φ to n binary digits.

The lab: U = P(2π·0.25), target |1⟩, so φ = 0.25. With n = 4 counting qubits the result is 0100 = 4, and 4/16 = 0.25. Exact, because 0.25 = 0.0100 in binary fits in 4 bits.

Example: finding the T gate's rotation. The T gate turns |1⟩ by 1/8 of a full circle (\(e^{i\pi/4} = e^{2\pi i\cdot 1/8}\)). Can QPE find 1/8? Step 1: an X gate turns the target into |1⟩. Step 2: H on 3 counting qubits. Step 3: apply controlled-T 1, 2 and 4 times (1/8, 2/8, 4/8 of a turn). Step 4: the inverse QFT turns those rotations into bits. Measured 001 = 1, and 1/8 = φ. Try the "T gate" button.

Accuracy and cost: when φ doesn't fit in n bits (try 1/3), the histogram spreads, and QPE returns the closest n-bit value at least ~40% of the time (exactly \(4/\pi^2 \approx 40.5\%\)). So run it several times and take the most common answer. More counting qubits give a sharper peak, but the number of controlled-U applications doubles with each extra qubit, and deep circuits suffer on noisy hardware. Classically, estimating a phase to n bits this way would take about 2ⁿ uses of U; QPE needs O(n) qubits.

4.8 Grover in the lab

You know how Grover works from Chapter 3. Here's how the lab actually builds it for 3 qubits with marked_state = "101".

The oracle (flip the sign of |101⟩ only)

1. Apply X to every qubit where the target bit is 0. This maps |101⟩ to |111⟩.
2. Apply a multi-controlled Z on |111⟩, built as H · MCX (multi-controlled X, Toffoli for 3 qubits) · H on the last qubit.
3. Undo the X gates.

The diffuser (inversion about the mean)

H on all → X on all → (H · MCX · H on the last qubit) → X on all → H on all. Mathematically this is \(2|s\rangle\langle s| - I\), where |s⟩ is the equal superposition: "reflect about the average".

How many iterations?

So about 945 of 1024 shots land on 101. The lab prints "Optimal Grover iterations: 2" and then reverses each result string (k[::-1]) to undo Qiskit's bit order before plotting.

Plot success probability against the fraction of marked items M/N: classical random guessing is a straight line, while Grover with one iteration (\(\sin^2 3\theta\), with \(\sin^2\theta = M/N\)) reaches 100% at M/N = ¼ and drops back to 0 at ¾. With too many solutions, Grover can do worse than guessing.

4.9 Shor in the lab

The full recipe:

1. Choose a random a < N with gcd(a, N) = 1.
2. Define the periodic function \(f(x) = a^x \bmod N\).
3. Find the period r with a quantum circuit: Hadamards → controlled modular exponentiation (\(U_a^{2^0}, U_a^{2^1}, \dots\)) → inverse QFT → measure.
4. Compute r from the measurement by classical post-processing (continued fractions).
5. Factors: \(p = \gcd(a^{r/2}-1, N)\), \(q = \gcd(a^{r/2}+1, N)\).

Look closely and you'll see step 3 is exactly QPE, with U = multiplication by a mod N. That's why the lab's quantum_order_estimation is literally a QPE circuit: H on 6 counting qubits, phase rotations \(2\pi\cdot 2^q/r\), inverse QFT, measure. (It "cheats" by computing the true r classically to set the phases, since a full modular-exponentiation circuit is too big for a lab.)

Reading the lab output

• For 15 with a = 2: \(2^4 = 16 \equiv 1\), so r = 4. \(2^2 = 4\); gcd(3, 15) = 3, gcd(5, 15) = 5.
• For 55 with a = 36: the true order is 5 (odd), so it retries. For a = 39 the true order is 10, but 6 counting qubits estimated 11. Estimates can be wrong, and that's one reason Shor is a repeat-until-success algorithm. In the end, a random a happened to share a factor with 55 (the "lucky gcd" step), giving 5 × 11.

Compare the number of operations against the number of digits: the classical curve shoots up towards 10³⁰ for 300-digit numbers, while Shor's stays low and nearly flat. That gap is the exponential speed-up.

4.10 Comparison and lab summary

Lab summary

• Lab 1, QFT-3: build a 3-qubit QFT; create hidden periods 2, 3, 4; simulate; plot histograms (use the period finder above to predict them).
• Lab 2, BV-8: 7-bit secret + 1 ancilla; let the user type the secret; check the output equals it.
• Lab 3, Grover on 3 qubits: oracle, diffuser, 2 iterations, histogram.
• Lab 4, Shor's factoring: choose a, find r with QPE, compute factors of a user-supplied N.
• Bonus: run each on FakePerth (a noisy copy of IBM's 7-qubit Perth chip) vs. the ideal simulator and compare fidelity: how close the noisy histogram is to the ideal one. Expect bars to "leak" into wrong answers on the fake device. That's Chapter 5 (errors and noise) knocking.

5.1 Errors before qubits: classical error correction

Classical bits go wrong too: electrical noise, imperfect circuits, a signal that fades on its way down a cable. The errors come in three shapes.

The first question is always: how do you even know something went wrong? You can't compare against the original, because the receiver never had it. The answer is to send a little extra, called redundancy, and check that it still agrees with itself. The slides show three ways.

The 3-repetition code

Send every bit three times: 0 becomes 000 and 1 becomes 111. The receiver takes a majority vote. One flipped copy is outvoted by the other two, so the error is detected and corrected. Two flips win the vote, and the answer comes out wrong.

If each copy flips independently with probability p, the vote fails only when two or three copies flip:

With p = 0.1, one bit alone is wrong 10% of the time, but the vote is wrong only 2.8% of the time. The code helps only while p is below 0.5. Past that, the copies are more likely wrong than right, and voting makes things worse.

Parity check

Add one parity bit so the total number of 1s is always even. 100011 has three 1s, which is odd, so append 1. 110011 has four, so append 0. The receiver recounts. An odd total means something flipped, so it rejects the data and asks again. A parity bit detects a single error but can't say which bit it was, so it can't correct it. Two flips cancel out and go unnoticed.

Hamming codes

Richard Hamming's trick is to use several parity bits, each checking a different, overlapping group of positions. Put them at positions 1, 2 and 4, the powers of 2. When one bit flips, the pattern of failed checks, called the syndrome, spells out the bad position in binary. Then you flip it back. Hamming(7,4) protects 4 data bits with only 3 extra bits, where repetition would need 8.

Try flipping two bits. The syndrome still points somewhere, but at the wrong place, and the "fix" adds a third error. Every code has a limit on how many errors it can handle.

5.2 Why quantum errors are harder

Qubits do their job through superposition and entanglement. Those are exactly the properties that make them sensitive to their environment, so errors aren't a rare accident. They are constant. To build reliable machines we have to detect, correct, mitigate and suppress them. Three things from Chapter 2 make that hard:

5.3 Types of quantum noise

Picture the qubit as an arrow on the Bloch sphere from Chapter 2. Each kind of noise does something different to that arrow.

A shrunken arrow is a qubit that's partly random. The length of the arrow is how much "quantumness" is left: 1 means a pure state, and 0 is a fair coin with no phase at all. Try each channel on different starting states, and notice that some errors can't touch some states.

5.4 Coherence, decoherence, T₁ and T₂

Coherence is a qubit's ability to stay in superposition. Every algorithm depends on it. Decoherence is the environment (heat, vibration, radiation, magnetic fields) leaking into the qubit and destroying that quantum information. Hardware quotes two clocks for it:

After one T₁, a qubit that started in |1⟩ is still there only about 37% of the time. T₂ can never be longer than 2T₁, because losing energy also destroys the phase.

On today's hardware both are only tens to hundreds of microseconds. That is the real limit on circuit depth: every gate takes time, and the whole algorithm has to finish before the qubits forget. It's why the deep circuits in Shor are out of reach and short ones like VQE are not.

5.5 Detecting quantum errors and noise

Before you can fight noise you have to measure it. The slides list four techniques:

• Fidelity: how close an actual output state or distribution is to the ideal, from 0 to 1.
• Randomized benchmarking: run long random sequences of gates that should multiply out to "do nothing", and see how fast the result decays. That gives the average gate fidelity, without being fooled by state preparation or readout errors.
• Quantum process tomography: feed in many known states, measure in many bases, and reconstruct the whole operation a gate actually performs, imperfections included. It's thorough but expensive, so it's only practical for one or two qubits.
• Hardware error reports: providers publish calibration data for every qubit and connection, refreshed many times a day.

Reading the report

From this dashboard: 2-qubit (CZ) error ≈ 1.55 × 10⁻³, single-qubit (SX) error ≈ 1.8 × 10⁻⁴, readout error ≈ 4.0 × 10⁻³, T₁ ≈ 300 µs, T₂ ≈ 324 µs. Two-qubit gates are almost ten times worse than one-qubit gates, which is why transpilers (Chapter 3) work so hard to cut CNOTs.

A quick rule of thumb: if errors are independent, a circuit succeeds roughly when every operation does, so multiply the success chances.

A circuit with 100 CZs, 200 SX gates and 5 readouts on this chip: 0.99845¹⁰⁰ ≈ 0.857, times 0.99982²⁰⁰ ≈ 0.965, times 0.99597⁵ ≈ 0.980, which is about 0.81. One run in five is spoiled before you even start, and doubling the CZ count drops it to about 0.70.

5.6 Lab: watching noise in Qiskit

The first lab notebook (Error.ipynb) adds noise to a small circuit on purpose and compares the results. The steps:

1. Build the circuit: put q0 in |1⟩, copy it into q1 and q2 with two CNOTs (the repetition code), then decode with two CNOTs and a Toffoli that flips q0 back if q1 and q2 both disagree with it.
2. Simulate it ideally (no error).
3. Simulate it with a bit-flip noise model, pauli_error([("X", p), ("I", 1 − p)]), with p = 0.30.
4. Compare the two histograms.
5. Repeat at transpiler optimization levels 0, 1, 2 and 3.

The results: ideal gives 1 in all 1,024 shots. With noise, about 70% 1 and 30% 0 (e.g. 724 vs 300). Optimization levels 0–3 give 748, 718, 682 and 715 ones: no real pattern, just shot noise.

5.7 Quantum error correction (QEC)

Goal: protect quantum information by spreading one logical qubit across many physical qubits.

The 3-qubit bit-flip code

Two CNOTs entangle the qubit with two fresh |0⟩s. Nothing is copied, so no-cloning is safe:

Now measure two parities with ancilla qubits: does q0 agree with q1 (\(Z_0Z_1\)), and does q1 agree with q2 (\(Z_1Z_2\))? Both branches, |000⟩ and |111⟩, give the same parity answers, so α and β are never disturbed. Only the error shows up:

Phase flips get the same treatment after a layer of Hadamards, because H turns Z errors into X errors. Peter Shor combined the two in 1995 to make the first code that handles any single-qubit error, using 9 physical qubits. Modern chips aim for the surface code, a grid of qubits with parity checks all over it. This is where Chapter 1's "about 1,000 physical qubits per logical qubit" comes from.

5.8 Quantum error mitigation (QEM)

Error mitigation is a collection of tricks that reduce the effect of noise on your results, without the extra qubits that full correction needs. It doesn't fix the qubits. It runs the noisy circuit cleverly, many times, and post-processes the numbers to estimate what a perfect machine would have said. That makes it the practical choice for today's NISQ devices. The slides cover four techniques: zero-noise extrapolation, readout-error mitigation, probabilistic error cancellation and Pauli twirling.

Zero-noise extrapolation (ZNE)

You can't turn noise down, but you can turn it up on purpose. Run the circuit at noise levels λ = 1, 1.5, 2, 2.5, 3, measure your answer each time, fit a curve through the points, and follow it back to λ = 0: the zero-noise answer that no machine can run.

How do you scale noise without touching the hardware? Unitary folding. Replace a gate U with U U† U. Mathematically that's still U, because U†U = I, but the chip now runs three gates, so roughly three times the noise. Fold the whole circuit (global folding), single gates (local folding), or insert identities (identity folding). Folding only some gates gives in-between factors like 1.5.

This lab mirrors the second notebook (QEM.ipynb): 10 X gates on one qubit, which multiply out to "do nothing", so the ideal result is P(0) = 1. Each gate has depolarizing noise.

The notebook's run with 2% noise got P(0) = 0.913 unmitigated and 0.961 after linear ZNE with scale factors 1 to 3. That's much closer to 1, but not all the way: the real decay is a curve, and a straight line underestimates it. Try the exponential fit, then try Richardson with shot noise on.

The other mitigation techniques

• Readout-error mitigation: first prepare each basis state and record how often it's misread, to build a "confusion matrix". Then undo that matrix on your real results. It's cheap, and it fixes the 0.4% readout errors in the report above.
• Probabilistic error cancellation (PEC): characterise the noise, then write the ideal gate as a weighted mix of noisy operations, some with negative weights. Randomly sample circuits from that mix and recombine the results with the weights. On average the noise cancels. The price is that the number of runs grows exponentially with circuit size.
• Pauli twirling: sandwich gates between random Pauli gates that cancel out logically. That turns messy, coherent errors into simple random Pauli flips, which the other methods handle much better.

Mitigation versus correction

5.9 Error suppression and dynamical decoupling

Error suppression works before errors happen. It builds resilience into the hardware and the operations themselves, with better-shaped control pulses and circuit designs that avoid trouble. The slides compare it to compressing a file: the information is all still there, but packed into a form that's less exposed.

The classic example is dynamical decoupling (DD). Qubits that sit idle while others work still drift, because of slow, unwanted phase from the environment. DD fills those idle windows with pulse pairs such as X then X, which multiply to the identity. Halfway through, the X turns the drift around, so the second half undoes the first. Sequences go from a plain X–X echo to XY4 (X–Y–X–Y) and XY8.

5.10 Putting it together, and the Mitiq lab

Noise is the central challenge in building large quantum computers, and no single tool beats it. We combine all four:

The Mitiq lab

Mitiq is an open-source Python library for error mitigation from the Unitary Foundation. It implements ZNE, PEC and DDD, and it works with Qiskit, Cirq and Braket. The notebook QEM.ipynb:

1. Build the circuit: 10 X gates on one qubit, then measure. The ideal answer is 0 every time.
2. Simulate it ideally: {'0': 1024}.
3. Add depolarizing noise (initialized_depolarizing_noise(noise_level=0.02)) and run it: P(0) ≈ 0.913.
4. Run ZNE with LinearFactory(scale_factors=[1.0, 1.5, 2.0, 2.5, 3.0]): P(0) ≈ 0.961.
5. Plot ideal, noisy and mitigated side by side.

The key design choice is the executor: a function you write that takes a circuit and returns one number, here P(0). Mitiq folds the circuit, calls your executor at each scale factor, and extrapolates. The notebook can switch to a real IBM back-end with USE_REAL_HARDWARE = True, and then the noise is the chip's own.