Quantum parallelism — and why it does not mean 'try all inputs at once'

hard

Learn with your AI

Open this lesson in your favourite AI. It'll walk you through the why, explain the demo, and quiz you on the try-it list.

Open in Claude Open in ChatGPT

Why this matters

The single most common pop-science misreading of quantum computing is 'a quantum computer evaluates

f

on all

2^n

inputs in parallel — that's why it's fast.' This is technically true and operationally meaningless. Yes,

H^{\otimes n}|0\rangle^{\otimes n}

produces a uniform superposition over all

2^n

basis states, and yes, applying

U_f

produces a state that 'contains'

f

evaluated on all of them. But measurement returns a single outcome with probability

1/2^n

— exactly as bad as random sampling. The actual source of quantum speedup is interference: arranging the post-oracle state so that amplitudes on uninteresting answers cancel and amplitudes on the answer you want add up. Every post-quantum security argument depends on understanding which problems admit such interference patterns and which (apparently) do not — that is the line between 'broken by Shor' and 'safe against quantum.'

Demo

Putting

n

qubits in uniform superposition and running an oracle

U_f

produces

\frac{1}{\sqrt{2^n}}\sum_x |x\rangle|f(x)\rangle

. Measuring the input register returns a uniformly random — no faster than classical random sampling. The 'parallelism' alone is useless; you need interference.

H^{\otimes n}|0\rangle^{\otimes n} = \tfrac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}|x\rangle, \quad U_f \!\left(\tfrac{1}{\sqrt{2^n}}\sum_{x}|x\rangle|0\rangle\right) = \tfrac{1}{\sqrt{2^n}}\sum_{x}|x\rangle|f(x)\rangle

Try it yourself

Run the snippet and verify each of the

2^n = 16

basis states gets exactly probability

1/16

. Increase

n

to 10 and confirm probabilities are

1/1024

. The 'parallel evaluation' is real but invisible — measurement returns one

x

Modify the code to apply a phase oracle that flips the sign of one specific basis state, e.g.

. Measure in the computational basis. The marked state is probability — no speedup.

Prompt your AI

Use these three in order. Each builds on the one before.

1. Basics & terminology

In one paragraph, explain why the slogan 'a quantum computer evaluates $f$ on all $2^n$ inputs at once' is technically true but operationally misleading. What goes wrong if you try to use this 'parallelism' naively?

2. Why it works (the mechanism)

Walk me step by step through Grover's algorithm on $N=4$ items: prepare uniform superposition, mark the target with a phase oracle, apply the diffusion operator, measure. Track the amplitudes at each step. After how many iterations is the marked state's probability maximised?

3. Advanced — application & what's next

Quantum-resistant cryptography frequently appeals to the fact that Grover gives only a *quadratic* speedup on search, while Shor gives an *exponential* speedup on period-finding. Explain mechanistically why the structure of the problem (random search vs. group structure) determines which type of speedup applies, and why this is the foundational asymmetry that the NIST PQC selections lean on.

// main.go package main import ( "fmt" "math" "math/rand" ) // kronecker product of two matrices (represented as flat slices with given dimension) func kron(A []complex128, aRows, aCols int, B []complex128, bRows, bCols int) ([]complex128, int, int) { rows := aRows * bRows cols := aCols * bCols C := make([]complex128, rows*cols) for i := 0; i < aRows; i++ { for j := 0; j < aCols; j++ { for k := 0; k < bRows; k++ { for l := 0; l < bCols; l++ { C[(i*bRows+k)*cols+(j*bCols+l)] = A[i*aCols+j] * B[k*bCols+l] } } } } return C, rows, cols } // Hn builds the n-qubit Hadamard matrix via iterated Kronecker products func Hn(n int) ([]complex128, int) { s := 1.0 / math.Sqrt2 H := []complex128{complex(s, 0), complex(s, 0), complex(s, 0), complex(-s, 0)} M := []complex128{1} mRows, mCols := 1, 1 for i := 0; i < n; i++ { M, mRows, mCols = kron(M, mRows, mCols, H, 2, 2) } _ = mCols return M, mRows } // matrix-vector multiply: M (dim x dim) times v (dim) func matvec(M []complex128, dim int, v []complex128) []complex128 { out := make([]complex128, dim) for i := 0; i < dim; i++ { for j := 0; j < dim; j++ { out[i] += M[i*dim+j] * v[j] } } return out } func main() { n := 4 dim := 1 << n // 2^n = 16 // Build H^n M, _ := Hn(n) // |0...0> state vector start := make([]complex128, dim) start[0] = 1 // Apply H^n psi := matvec(M, dim, start) // Compute probabilities |a|^2 probs := make([]float64, dim) for i, a := range psi { probs[i] = real(a)*real(a) + imag(a)*imag(a) } fmt.Printf("after H^%d on |0...0>: each of the %d amplitudes has |a|^2 = %.4f\n", n, dim, probs[0]) // Simulate measurement: sample x uniformly at random (seed 0 for reproducibility) rng := rand.New(rand.NewSource(0)) shots := 2000 counts := make([]int, dim) for i := 0; i < shots; i++ { // weighted sample via CDF r := rng.Float64() cum := 0.0 chosen := dim - 1 for x, p := range probs { cum += p if r < cum { chosen = x break } } counts[chosen]++ } fmt.Printf("empirical fractions over 2_000 shots, first 4: [%.3f %.3f %.3f %.3f]\n", float64(counts[0])/float64(shots), float64(counts[1])/float64(shots), float64(counts[2])/float64(shots), float64(counts[3])/float64(shots), ) fmt.Println("=> measurement gives a uniformly random x, not f(all x)") }