Gates, no-cloning, algorithms and decoherence

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; teleportation and error correction use it mid-circuit, but the deferred-measurement principle lets any circuit postpone it to the end.

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. A fault-tolerant machine 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.

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.

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.

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.

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.