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.

Prerequisites

Quantum mechanics (Ch. 20) \cdot Spin & angular momentum (Ch. SP) \cdot 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:

|\psi⟩ = \alpha|0⟩ + \beta|1⟩ \qquad with |\alpha|^{2} + |\beta|^{2} = 1

(QI.1)

The state lives on the Bloch sphere: |ψ⟩ = cos(θ/2)|0⟩ + e^(iφ) sin(θ/2)|1⟩. 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 2^n-dimensional Hilbert space. The general state: |ψ⟩ = Σ c_x |x⟩ for x ∈ {0,1}^n — requires 2^n complex amplitudes. A 300-qubit state cannot be stored classically (2^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:|

\Phi\pm⟩ = (|00⟩ \pm |11⟩)/\sqrt2 \qquad |\Psi\pm⟩ = (|01⟩ \pm |10⟩)/\sqrt2

Measuring 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(2^n). Single-qubit gates correspond to rotations of the Bloch sphere:

Pauli gates: X = [[0,1],[1,0]] (bit flip), Y = [[0,−i],[i,0]], Z = [[1,0],[0,−1]] (phase flip).

Hadamard: H = (1/√2)[[1,1],[1,−1]]. Maps |0⟩ → (|0⟩+|1⟩)/√2, creates superposition.

Phase gate: S = [[1,0],[0,i]], T = [[1,0],[0,e^(iπ/4)]].

Two-qubit gates: CNOT (controlled-NOT): flips target if control = |1⟩. Matrix: [[1,0,0,0],[0,1,0,0],[0,0,0,1],[0,0,1,0]] 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³(1/ε)) gates).

Example QI.1 — Creating a Bell State

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

Start:|

\psi_{0}⟩ = |00⟩

Apply H to qubit 1:|

\psi_{1}⟩ = (H ⊗ I)|00⟩ = (|0⟩+|1⟩)/\sqrt2 ⊗ |0⟩ = (|00⟩+|10⟩)/\sqrt2

Apply CNOT (control=1, target=2):|

\psi_{2}⟩ = CNOT|\psi_{1}⟩ = (|00⟩+|11⟩)/\sqrt2 = |\Phi+⟩ ✓

Verify entanglement:

Cannot write |\Phi+⟩ = (a|0⟩+b|1⟩)(c|0⟩+d|1⟩) for any a,b,c,d. Proof: would require ac=1/\sqrt2

ad=0, bc=0, bd=1/\sqrt2. From ad=0: a=0 or d=0. From ac=1/\sqrt2 ≠ 0: a≠0, so d=0. But bd=0 and bd

\sqrt2 — contradiction

QI.3 Quantum Algorithms

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

Grover's algorithm: searches an unsorted database of N items for a marked item in O(√N) queries (classical: 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(n³) time (polynomial). Best classical: O(e^(cn^(1/3) (log n)^(2/3))) (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) = a^x mod 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(|\psi

\psi⟩ = (|0⟩+|1⟩)/\sqrt2

U(|+⟩|0⟩) = |+⟩|+⟩ = (|00⟩+|01⟩+|10⟩+|11⟩)/2

But linearity of U requires U(|+⟩|0⟩) = (U(|0⟩|0⟩)+U(|1⟩|0⟩))/\sqrt2 = (|00⟩+|11⟩)/\sqrt2 — contra

diction. 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⟩, |1⟩_L = |111⟩. Detects (but doesn't correct) a single bit 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

Apply one step of Grover's algorithm to search N = 4 items for a marked state. Show that a

single iteration is sufficient to find the answer.

Grover iterations

Intermediate

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: |\psi⟩ = \alpha|0⟩+\beta|1⟩, Bloch sphere. n qubits span 2^n-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(\sqrtN). Both exponentially be$ at classical.
Error correction: surface codes need ~1000 physical qubits per logical, threshold ~1% error rate.