University Physics IV · Frontiers of Modern Physics · 15.3

Gates, No-Cloning, Algorithms & Decoherence

Everything a quantum computer does between preparation and readout is one unitary matrix, and most of the headline results are consequences of that single fact: what you can build from a handful of gates, what you provably cannot copy, and why the machine has a stopwatch running against it.

Open the lab ↓Practice & worked examples ↓

Build the model

Connect the measurement to the mechanism.

A quantum computation is a unit vector in a 2ⁿ-dimensional space, pushed around by unitary matrices and read out once by the Born rule. Unitarity is not a design choice: closed-system Schrödinger evolution is generated by a Hermitian Hamiltonian, so U = exp(−iHt/ħ) preserves inner products, every gate is reversible, and every gate library is a set of rotations. Three results follow from that alone.

Universality is cheap — arbitrary single-qubit rotations plus one entangling gate such as CNOT reach any unitary, and Solovay–Kitaev says a fixed discrete set does it with only polylogarithmic overhead. No-cloning is free — a copier must act linearly on superpositions, and linearity delivers a|00⟩ + b|11⟩ where a true copy demands (a|0⟩ + b|1⟩)⊗², so no dynamics need be invoked. And the speedups are structural rather than magical: Grover rotates the state towards the marked item by a fixed angle per query, needing about (π/4)√N of them and provably no fewer, while Shor recasts factoring as period-finding, which the quantum Fourier transform does in polynomial time.

What the model costs is isolation. The register is never closed; it entangles with uncontrolled environmental degrees of freedom, and tracing them out turns a pure density matrix into a mixed one over T₁ and T₂. So the question that decides an algorithm is not whether it terminates, but whether it terminates inside T₂.

Simple definition: A quantum gate is a unitary matrix acting on the 2ⁿ amplitudes of an n-qubit register, so every step of a computation is reversible and norm-preserving until a measurement is made.
Example: A Hadamard sends |0⟩ to (|0⟩ + |1⟩)/√2, each outcome at probability 0.5; apply it again without measuring and the amplitudes recombine to give |0⟩ with probability 1, because H² = I.

Every gate is a unitary matrixU†U = I|ψ′⟩ = U|ψ⟩U = exp(−iHt/ħ)

Closed-system evolution preserves norms, so every gate inverts as U⁻¹ = U† and no step inside a circuit can erase information.

U is 2ⁿ × 2ⁿ for n qubits — n = 50 already means 1.13 × 10¹⁵ amplitudes

Universal gate set{any single-qubit rotation} + CNOTCNOT|a, b⟩ = |a, a⊕b⟩

Rotations alone keep a product state a product state. One entangling gate plus arbitrary rotations reaches any unitary you name.

⊕ is addition mod 2; CNOT is its own inverse, so CNOT² = I

No-cloning, from linearity aloneU(a|0⟩+b|1⟩)|0⟩ = a|00⟩ + b|11⟩ ≠ (a|0⟩+b|1⟩)⊗²

Four lines, no dynamics: linearity forbids a universal copier, which is what makes an eavesdropper detectable in QKD.

The two sides agree only when ab = 0, i.e. only for the basis states

Teleportation ledger1 unknown qubit = 1 shared Bell pair + 2 classical bits

Bob applies I, X, Z or ZX on that message. The original is destroyed and the bits travel at c, so neither no-cloning nor relativity is touched.

Alice's Bell measurement gives 00, 01, 10 or 11, each at probability 0.25

Grover iteration and its optimumP(k) = sin²((2k+1)θ), sin θ = 1/√Nkₒₚₜ ≈ (π/4)√N

Quadratic, not exponential, and provably optimal: N = 10⁶ falls from about 5 × 10⁵ expected classical queries to 785.

N is the size of the search space, k the number of oracle queries

Coherence budgetρ₀₁(t) = ρ₀₁(0) e^(−t/T₂)depth ≈ T₂ / t_gate

T₂ = 100 μs with 25 ns gates allows roughly 4000 of them — the number that decides whether an algorithm fits at all.

T₁ is energy relaxation, T₂ ≤ 2T₁ the phase coherence time, both in seconds

A circuit is one unitary matrix

Between preparation and measurement, everything a quantum computer does is multiplication by a unitary matrix. That is forced rather than chosen: a closed system evolves under the Schrödinger equation with a Hermitian generator, and U = exp(−iHt/ħ) then satisfies U†U = I. Three habits follow. Norms are preserved, so the probabilities still sum to 1 after every step and nothing needs renormalising mid-circuit. Every gate is invertible with U⁻¹ = U†, so a circuit read backwards undoes itself — H and CNOT are each their own inverse, H² = CNOT² = I. And no gate can erase: irreversible AND and OR have no unitary form, so classical logic must be embedded reversibly, at the price of ancilla qubits and a final uncomputation step that returns the scratch space to |0⟩. Measurement is the only non-unitary act in the model, and it is spent once, at the end.

Universality: rotations plus one entangler

You do not need separate hardware for every unitary. Single-qubit rotations move each qubit on its own Bloch sphere, and a product of them applied to a product state returns a product state — rotations alone can never build a correlation, which is why an entangling gate is compulsory rather than convenient. Add CNOT, which maps |a, b⟩ to |a, a⊕b⟩ and turns (H⊗I)|00⟩ into the Bell state (|00⟩ + |11⟩)/√2, and the set is universal: any unitary on n qubits is approximable to arbitrary accuracy. Real hardware supplies a fixed discrete set, typically H, S, T and CNOT, and the Solovay–Kitaev theorem guarantees that an arbitrary rotation to accuracy ε costs only about log^c(1/ε) gates from it, with c near 2. Universality says nothing about efficiency: a general n-qubit unitary carries roughly 4ⁿ parameters and cannot be compiled short. The useful algorithms are exactly those whose unitary happens to factor into a polynomial number of gates.

No-cloning, and the two rules it does not break

Suppose a machine copies: U|ψ⟩|0⟩ = |ψ⟩|ψ⟩ for every ψ. Feed it |0⟩ and |1⟩, and linearity fixes what it must do to a superposition: U(a|0⟩ + b|1⟩)|0⟩ = a|00⟩ + b|11⟩. A genuine copy is (a|0⟩ + b|1⟩)⊗(a|0⟩ + b|1⟩) = a²|00⟩ + ab|01⟩ + ab|10⟩ + b²|11⟩. Those agree only when ab = 0, that is only for the two basis states you fed in. The argument used linearity and nothing else — no Hamiltonian, no uncertainty relation. Teleportation looks like a counterexample and is not. Alice and Bob share a Bell pair; Alice makes a joint Bell measurement on her half and the unknown qubit, gets one of four outcomes each at probability 0.25, and sends those two classical bits; Bob applies I, X, Z or ZX. The unknown state reappears at Bob's end, but Alice's measurement destroyed hers, so nothing was copied — and before the bits arrive Bob's qubit is the maximally mixed state ½I, so nothing was signalled either.

Where the speedup comes from, and where it stops

Superposition alone buys nothing, because measurement returns a single basis state. The work is done by interference: arranging the circuit so that amplitudes for wrong answers cancel. Grover makes this geometric. With one marked item among N, the uniform state sits an angle θ from the unmarked subspace with sin θ = 1/√N, and oracle plus diffusion rotate it a further 2θ each query, so P(k) = sin²((2k+1)θ) and the optimum is near (π/4)√N. For N = 10⁶ that is 785 queries against about 5 × 10⁵ expected classically — quadratic, provably optimal for an unstructured oracle, and it overshoots if you keep going. Shor is different in kind: factoring is recast as finding the period of a^x mod N, and the quantum Fourier transform extracts that period in polynomial time. Be exact about the two claims. Grover's optimality is a theorem. Shor's advantage is not, because no classical lower bound on factoring is known and BQP versus BPP is open.

Decoherence is unitarity applied to a bigger system

The register is never closed. It couples to two-level defects, stray photons, phonons and the control lines themselves, and the joint system-plus-environment still evolves perfectly unitarily. The damage appears when you trace the environment out: the pure density matrix ρ = |ψ⟩⟨ψ| becomes a mixture whose off-diagonal terms have shrunk, and it is those off-diagonal terms that carried the relative phase the interference depended on. Two timescales measure it. T₁ is energy relaxation, |1⟩ decaying towards |0⟩. T₂ is phase coherence, the decay of the off-diagonals, bounded by T₂ ≤ 2T₁ because every relaxation event also destroys phase, while pure dephasing lowers T₂ without touching T₁. On a current transmon both sit near 100 μs while single-qubit gates take about 25 ns and two-qubit gates about 250 ns, so roughly 4000 single-qubit or 400 two-qubit operations fit before the phase is gone. That ratio, not the qubit count, is what an algorithm must fit inside.

You cannot copy, so you spread and read the syndrome

Classical error correction repeats a bit three times, which no-cloning forbids outright. Quantum codes instead spread one logical qubit across many physical ones and measure only stabiliser operators — parities such as Z₁Z₂, which reveal whether two qubits disagree without revealing which state they are in, so the encoded superposition survives being measured. A second gift makes the job finite: an arbitrary small error decomposes into I, X, Z and XZ parts, and the syndrome measurement projects onto one of them, so a code that corrects a discrete set corrects everything. The threshold theorem then states that if the physical error rate sits below a threshold — near 10⁻² for the surface code — arbitrarily long computation is possible with overhead only polylogarithmic in the length. The catch is the prefactor. At a physical rate of 10⁻³ a distance-17 patch needs about 2d² = 578 physical qubits per logical qubit, before the factories that distil the non-Clifford gates.

Change one variable at a time

Make the relationship visible.

Interactive model

Search space size N64 items

Oracle queries k6 queries

Error probability per query ε0.000

Keep ε at 0 and drag k past the faint vertical: the ideal curve peaks at (π/4)√N and then falls again, because a Grover step is a rotation, not a ratchet. Now raise ε to 0.02 and watch the solid peak sink and slide left of the ideal one.

OPTIMAL QUERY COUNT5.8 queries

IDEAL P AT k0.997

NOISY P AT k0.997

CLASSICAL P AT k0.094

Live interpretationOPTIMAL QUERY COUNT: 5.8 queries. IDEAL P AT k: 0.997. NOISY P AT k: 0.997. CLASSICAL P AT k: 0.094

Catch the common trap

Explain before calculating.

An unstructured search over N = 4 × 10⁶ items runs Grover's algorithm with a perfect oracle and one marked item. Roughly how many oracle queries does it need, and what happens if you run four times that many?

Choose an answer to test the model.

Practice & worked examples

Reason from the model, then test the result.

EasyA transmon qubit has T₁ = 90 μs and T₂ = 120 μs. Single-qubit gates take 25 ns, two-qubit gates 250 ns. A circuit has 400 single-qubit and 120 two-qubit gates on its critical path. Does it fit inside the coherence time, and how much of T₂ does it spend?

Check the quoted times are legal first: T₂ ≤ 2T₁ = 180 μs, and 120 μs obeys that, so this device is dephasing-limited rather than relaxation-limited.
Single-qubit time on the critical path: 400 × 25 ns = 10 000 ns = 10 μs.
Two-qubit time: 120 × 250 ns = 30 000 ns = 30 μs. The two-qubit gates are a quarter of the count and three quarters of the time.
Total circuit duration 40 μs, which is 40/120 = 0.333 of T₂.
The off-diagonal density-matrix elements have decayed by e^(−t/T₂) = e^(−1/3) = 0.72, so about 28% of the coherence is already gone when the readout happens.

Answer40 μs, one third of T₂, leaving coherence at 0.72 of its initial value. It fits, but only just — and this counts elapsed time alone, ignoring per-gate infidelity, which usually bites first.

MediumAn unstructured list of N = 1024 entries contains exactly one marked item. Find the Grover angle θ, the optimal number of iterations, the success probability there, and compare with a classical scan.

The uniform superposition carries amplitude 1/√N on the marked item, so sin θ = 1/√1024 = 1/32 = 0.03125 and θ = arcsin(0.03125) = 0.031255 rad.
Each Grover iteration rotates the state by a further 2θ, giving P(k) = sin²((2k+1)θ). This peaks when (2k+1)θ = π/2, so k = π/(4θ) − ½ = 25.129 − 0.5 = 24.63.
k must be an integer, so test both neighbours: P(24) = sin²(49 × 0.031255) = 0.9985 and P(25) = sin²(51 × 0.031255) = 0.9995. Take k = 25.
A classical scan checks entries until it hits the marked one: 512 queries expected, 1024 in the worst case.
So 25 queries replace 512, a factor of about 20 — and because the cost goes as √N, a list 100 times longer costs only 10 times more queries, not 100.

Answerθ = 0.03126 rad, kₒₚₜ = 25 iterations, P = 0.9995 — against 512 expected classical queries, a saving of roughly 20-fold.

HardA processor has physical two-qubit error rate p = 1.0 × 10⁻³ against a surface-code threshold pₜₕ = 1.0 × 10⁻², so the logical error rate per round is roughly p_L ≈ 0.03 (p/pₜₕ)^((d+1)/2) at code distance d. An algorithm needs 10⁸ logical operations with total failure probability under 1%. Find the required p_L, the smallest odd distance d, and the physical-qubit cost at about 2d² per logical qubit.

Budget the failure uniformly: 10⁸ operations share a total of 0.01, so p_L ≤ 0.01/10⁸ = 1 × 10⁻¹⁰ per operation.
Being below threshold is what makes suppression work at all: p/pₜₕ = 10⁻³/10⁻² = 0.1 < 1, so p_L ≈ 0.03 × 10^(−(d+1)/2) falls as d grows. Above threshold the same expression would grow with d instead.
Solve 0.03 × 10^(−(d+1)/2) ≤ 10⁻¹⁰: rearranged, 10^((d+1)/2) ≥ 3.0 × 10⁸, so (d+1)/2 ≥ 8.48 and d ≥ 15.95.
The distance must be an odd integer, so d = 17, giving p_L ≈ 0.03 × 10⁻⁹ = 3 × 10⁻¹¹ — comfortably inside budget, whereas d = 15 gives 3 × 10⁻¹⁰, three times over it.
Cost: 2d² = 2 × 289 = 578 physical qubits per logical qubit, so a 100-logical-qubit register needs about 5.8 × 10⁴ physical qubits, before any magic-state factories.

Answerp_L ≤ 1 × 10⁻¹⁰ forces d = 17 (p_L ≈ 3 × 10⁻¹¹), at 578 physical qubits per logical qubit — about 5.8 × 10⁴ physical qubits for a 100-logical-qubit register.