Modern Physics · Advanced Topics

Quantum Information & Computation

Quantum mechanics allows information processing fundamentally beyond classical limits. Quantum bits exploit superposition and entanglement to factor large numbers exponentially faster, generate provably secure keys, and simulate quantum systems efficiently.

PrerequisitesQuantum mechanics (Ch. 22) · Spin & angular momentum (Ch. SP) · Linear algebra (Ch. LA)
Learning Goals
  • Represent single- and multi-qubit states on the Bloch sphere and in the computational basis.
  • Apply quantum gates (H, CNOT, Pauli, phase) to create entangled Bell states and verify entanglement.
  • Trace through the Deutsch-Jozsa, Grover, and Shor algorithms and quantify their quantum speedups.
  • Prove the no-cloning theorem and explain its role in quantum key distribution security.
  • Estimate the physical qubit overhead required for fault-tolerant quantum computation using surface codes.

QI.1 Qubits and Quantum States

A qubit is a two-level quantum system. In the computational basis: |0⟩ and |1⟩. A general single-qubit state:

∣ψ⟩=α∣0⟩+β∣1⟩with∣α∣2+∣β∣2=1|\psi\rangle = \alpha|0\rangle + \beta|1\rangle \qquad \text{with} \quad |\alpha|^2 + |\beta|^2 = 1(QI.1)

The state lives on the Bloch sphere: ∣ψ⟩=cos⁡(θ/2)∣0⟩+eiϕsin⁡(θ/2)∣1⟩|\psi\rangle = \cos(\theta/2)|0\rangle + e^{i\phi} \sin(\theta/2)|1\rangle. The north pole is |0⟩, south pole |1⟩, equator is superpositions. Physical implementations: spin-½ (nuclear or electron), photon polarization, transmon circuit (superconducting qubit), trapped ion internal states, nitrogen-vacancy centers in diamond.

An n-qubit system lives in a 2n2^n-dimensional Hilbert space. The general state:∣ψ⟩=∑xcx∣x⟩|\psi\rangle = \sum_x c_x |x\rangle for x∈{0,1}nx \in \{0,1\}^n — requires 2n2^n complex amplitudes. A 300-qubit state cannot be stored classically (23002^{300}> atoms in observable universe).

Definition QI.1 — Entanglement
A multi-qubit state is entangled if it cannot be written as a product of single-qubit states. The four Bell states are maximally entangled two-qubit states:|Φ±⟩=(∣00⟩±∣11⟩)/2∣Ψ±⟩=(∣01⟩±∣10⟩)/2\Phi\pm⟩ = (|00⟩ \pm |11⟩)/\sqrt 2 \qquad |\Psi\pm⟩ = (|01⟩ \pm |10⟩)/\sqrt 2Measuring one qubit instantly collapses the other — but no information is transmitted (no-communication theorem). Entanglement is a resource for quantum teleportation, dense coding, and quantum cryptography.

QI.2 Quantum Gates and Circuits

Quantum operations on n qubits are unitary matrices U∈U(2n)U \in U(2^n). Single-qubit gates correspond to rotations of the Bloch sphere:

Pauli gates: X=(0110)X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} (bit flip), Y=(0−ii0)Y = \begin{pmatrix} 0 & -i \\ i & 0 \end{pmatrix}, Z=(100−1)Z = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix} (phase flip).

Hadamard: H=12(111−1)H = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}. Maps |0⟩ → (|0⟩+|1⟩)/√2, creates superposition.

Phase gate: S=(100i)S = \begin{pmatrix} 1 & 0 \\ 0 & i \end{pmatrix}, T=(100eiπ/4)T = \begin{pmatrix} 1 & 0 \\ 0 & e^{i\pi/4} \end{pmatrix}.

Two-qubit gates: CNOT (controlled-NOT): flips target if control = |1⟩. Matrix: (1000010000010010)\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix} in the |00⟩, |01⟩, |10⟩, |11⟩ basis. CNOT + single-qubit gates form a universal gate set — any unitary can be approximated to arbitrary precision (Solovay-Kitaev theorem, O(log⁡3(1/ε))O(\log^3(1/\varepsilon)) gates).

Example QI.1 — Creating a Bell State

Show how to create the entangled state |Φ+⟩=(∣00⟩+∣11⟩)/2\Phi+⟩ = (|00⟩ + |11⟩)/\sqrt 2 from |00⟩ using H and CNOT.

Start:|ψ0⟩=∣00⟩\psi_{0}⟩ = |00⟩
Apply H to qubit 1:|ψ1⟩=(H⊗I)∣00⟩=(∣0⟩+∣1⟩)/2⊗∣0⟩=(∣00⟩+∣10⟩)/2\psi_{1}⟩ = (H ⊗ I)|00⟩ = (|0⟩+|1⟩)/\sqrt 2 ⊗ |0⟩ = (|00⟩+|10⟩)/\sqrt 2
Apply CNOT (control=1, target=2):|ψ2⟩=CNOT∣ψ1⟩=(∣00⟩+∣11⟩)/2=∣Φ+⟩✓\psi_{2}⟩ = CNOT|\psi_{1}⟩ = (|00⟩+|11⟩)/\sqrt 2 = |\Phi+⟩ ✓
Verify entanglement:Cannot write |Φ+⟩=(a∣0⟩+b∣1⟩)(c∣0⟩+d∣1⟩)\Phi+⟩ = (a|0⟩+b|1⟩)(c|0⟩+d|1⟩) for any a,b,c,d. Proof: would require ac=1/2,ad=0,bc=0,bd=1/2ac=1/\sqrt 2, ad=0, bc=0, bd=1/\sqrt 2. From ad=0:a=0ad=0: a=0 or d=0d=0. From ac=1/2≠0:a≠0ac=1/\sqrt 2 ≠ 0: a≠0, so d=0d=0. Butbd=0But bd=0 and bd=1/2—bd=1/\sqrt 2 — contradiction.
Measurement:Measure qubit 1 in |0⟩,|1⟩ basis. If result |0⟩ (prob ½): qubit 2 collapses to |0⟩. If result |1⟩ (prob ½): qubit 2 collapses to |1⟩. Perfect correlation — EPR pair.

QI.3 Quantum Algorithms

Deutsch-Jozsa: determines if f:{0,1}n→{0,1}f: \{0,1\}^n \to \{0,1\} is constant or balanced in ONE query (classically needs 2n−1+12^{n-1} + 1 queries in the worst case). Demonstrates quantum parallelism — all 2n2^n inputs evaluated simultaneously.

Grover's algorithm: searches an unsorted database of N items for a marked item in O(N)O(\sqrt{N}) queries (classical: O(N)O(N)). The quantum speedup is quadratic: for N = 10⁶, classical needs ~500,000 queries; Grover needs ~785.

Shor's algorithm (1994): factors an n-bit number N in O(n3)O(n^3) time (polynomial). Best classical: O ⁣(ec n1/3(log⁡n)2/3)O\!\left(e^{c\, n^{1/3} (\log n)^{2/3}}\right) (sub-exponential). A 2048-bit RSA key would require ∼4×10⁹ quantum gates on a fault-tolerant quantum computer — breaking public-key cryptography. Shor uses the quantum Fourier transform (QFT) to find the period of f(x)=ax mod Nf(x) = a^x \bmod N, which determines the factors.

Theorem QI.1 — No-Cloning Theorem
It is impossible to create an exact copy of an arbitrary unknown quantum state. Proof: suppose a unitary U copies states: U(∣ψ⟩∣0⟩)=∣ψ⟩∣ψ⟩U(|\psi⟩|0⟩) = |\psi⟩|\psi⟩ for all |ψ⟩\psi⟩. Apply to |ψ⟩=(∣0⟩+∣1⟩)/2\psi⟩ = (|0⟩+|1⟩)/\sqrt 2:U(∣+⟩∣0⟩)=∣+⟩∣+⟩=(∣00⟩+∣01⟩+∣10⟩+∣11⟩)/2U(|+⟩|0⟩) = |+⟩|+⟩ = (|00⟩+|01⟩+|10⟩+|11⟩)/2But linearity of U requires U(∣+⟩∣0⟩)=(U(∣0⟩∣0⟩)+U(∣1⟩∣0⟩))/2=(∣00⟩+∣11⟩)/2—U(|+⟩|0⟩) = (U(|0⟩|0⟩)+U(|1⟩|0⟩))/\sqrt 2 = (|00⟩+|11⟩)/\sqrt 2 — contradiction. Consequence: quantum states cannot be copied. This is why quantum error correction is non-trivial — you cannot simply back up qubits. It also prevents eavesdroppers from quietly copying a quantum key (basis of BB84 security).

QI.4 Quantum Error Correction

Qubits decohere — they interact with the environment and lose their quantum state. Decoherence times: superconducting qubits ∼100 μs, trapped ions ∼seconds. Any useful quantum computation needs error correction.

The key insight: encode one logical qubit in many physical qubits. The 3-qubit repetition code: ∣0⟩L=∣000⟩|0\rangle_L = |000\rangle, ∣1⟩L=∣111⟩|1\rangle_L = |111\rangle. Corrects a single bit flip (but not a phase flip). Full correction needs more qubits.

The Shor code(1995): 9 physical qubits per logical qubit. Corrects any single-qubit error (bit flip OR phase flip). Modern surface codes: ∼1000 physical qubits per logical qubit for a logical error rate of 10⁻¹⁵ (fault-tolerant threshold: physical error rate < ∼1%). Google's 72-qubit Sycamore has ∼0.1% two-qubit gate error — approaching but not yet at fault-tolerant threshold.

QI.5 Quantum Cryptography

BB84 protocol (Bennett-Brassard, 1984): Alice sends photons in one of four polarization states (0°, 45°, 90°, 135°). Bob measures in randomly chosen bases. They publicly compare bases (not results) and keep bits where bases matched. Any eavesdropper disturbs the quantum state (no-cloning theorem) and is detectable via elevated error rate. Security is unconditional — based on quantum mechanics, not computational hardness.

Quantum key distribution (QKD) networks are commercially deployed: Chinese satellite Micius demonstrated QKD over 1200 km (2017). The Toshiba system achieves Mbit/s key rates over fiber.

Definition QI.2 — Common Traps
  • Qubits are amplitudes, not probabilities: phases matter until measurement.
  • Entanglement is not cloning: unknown quantum states cannot be copied perfectly.
  • Measurement is basis-dependent: changing the basis changes outcome probabilities.
  • Error correction protects logical states: it detects syndromes without learning the encoded quantum information.
Exercises — QI.1–QI.5 Quantum Information
1.Walk through the Deutsch algorithm for a single-bit function. Why does it determine constant-vs-balanced in one query when classical requires two?
Straightforward
2.Describe quantum teleportation. Why doesn't it violate no-cloning or allow faster-than-light communication?
Intermediate
3.
Apply one step of Grover's algorithm to search N=4N = 4 items for a marked state. Show that a single iteration is sufficient to find the answer.
Grover iterations
Intermediate
4.
Estimate the number of physical qubits needed for fault-tolerant factoring of a 2048-bit RSA key using surface codes. What error rate threshold must physical gates satisfy?
physical qubits
Challenging
Key Takeaways
  • Qubit: |ψ⟩=α∣0⟩+β∣1⟩\psi⟩ = \alpha|0⟩+\beta|1⟩, Bloch sphere. n qubits span 2ⁿ-dimensional Hilbert space.
  • Bell states: maximally entangled 2-qubit states. Entanglement is a computational/cryptographic resource.
  • Universal gates: single-qubit rotations + CNOT. Solovay-Kitaev: efficient approximation.
  • No-cloning: unknown quantum states cannot be copied. Basis of QKD security.
  • Shor: factor N in poly(log N) time. Grover: search N items in O(N)O(\sqrt N). Shor beats classical exponentially, Grover quadratically.
  • Error correction: surface codes need ~1000 physical qubits per logical, threshold ~1% error rate.