Spotlight #30 – Quantum Information & Computing: Qubits, Entanglement, BB84 and Quantum Algorithms

Classical computers store information as bits — binary values that are definitively 0 or 1. A quantum computer stores information in qubits: two-level quantum systems that can exist in a continuous superposition of |0⟩ and |1⟩ until measured. The power of quantum computation arises not from the superposition alone (a single qubit just stores a point on the Bloch sphere, no more information than a classical angle) but from entanglement between qubits: non-classical correlations that cannot be explained by any shared classical state.

Quantum information theory formalises the limits of what quantum systems can communicate and compute. It has practical applications in cryptography (BB84 quantum key distribution, provably secure by the laws of physics), in algorithms (Grover’s O(√N) search, Shor’s polynomial-time factoring), and in fundamental physics (Bell tests, teleportation, dense coding). The six sections below build the framework from single-qubit geometry through to algorithmic complexity.

1. Qubits and the Bloch Sphere

A qubit is the quantum analogue of a classical bit: a two-level system described by a state vector |ψ⟩ = α|0⟩ + β|1⟩ where α, β ∈ ℂ and |α|² + |β|² = 1. The complete state space (modulo global phase) is the surface of the Bloch sphere — every point corresponds to a distinct pure state. The north and south poles are the computational basis states |0⟩ and |1⟩; the equatorial circle represents states with equal measurement probabilities.

General pure qubit state:
  |ψ⟩ = cos(θ/2)|0⟩ + e^{iφ} sin(θ/2)|1⟩
  θ ∈ [0, π]   (polar angle, determines measurement probabilities)
  φ ∈ [0, 2π) (azimuthal angle, determines phase)

Bloch vector: n = (sinθcosφ, sinθsinφ, cosθ)  — unit vector on S²

Measurement in the computational basis:
  P(|0⟩) = cos²(θ/2)
  P(|1⟩) = sin²(θ/2)
  After measurement the state collapses to |0⟩ or |1⟩ irreversibly.

Key equatorial states:
  |+⟩ = (|0⟩ + |1⟩)/√2   (θ = π/2, φ = 0;  eigenstate of X gate)
  |−⟩ = (|0⟩ − |1⟩)/√2  (θ = π/2, φ = π)
  |i⟩  = (|0⟩ + i|1⟩)/√2  (θ = π/2, φ = π/2; eigenstate of Y gate)

Density matrix (for mixed states and decoherence):
  ρ = |ψ⟩⟨ψ|   (pure state)
  ρ = (I + n·σ) / 2   (σ = Pauli vector)
  Mixed state: |n| < 1; maximally mixed: ρ = I/2 (Bloch vector = 0, complete decoherence)
  Tr(ρ²) = 1 for pure, < 1 for mixed: purity measure.

Decoherence timescales:
  T_1: energy relaxation time (|1⟩ → |0⟩ spontaneously)
  T_2: dephasing time (φ randomises due to environmental noise)
  T_2 ≤ 2T_1 always; for superconducting qubits T_1 ~ T_2 ~ 10–500 µs (2024 state of art)

2. Quantum Entanglement and Bell Inequalities

Entanglement is the distinctively quantum form of correlation. Two qubits in the Bell state |Φ&sup+;⟩ = (|00⟩ + |11⟩)/√2 are individually in maximally mixed states — complete ignorance about each qubit — yet measurements are perfectly correlated: if Alice finds |0⟩, Bob finds |0⟩ regardless of their separation. Bell (1964) showed that no local hidden-variable theory can reproduce all quantum correlations; the CHSH inequality is the testable consequence.

Four maximally entangled Bell (EPR) states for two qubits:
  |Φ&sup+;⟩ = (|00⟩ + |11⟩) / √2
  |Φ−⟩ = (|00⟩ − |11⟩) / √2
  |Ψ&sup+;⟩ = (|01⟩ + |10⟩) / √2
  |Ψ−⟩ = (|01⟩ − |10⟩) / √2

Schmidt decomposition: any bipartite pure state |ψ_{AB}⟩ = Σ_i λ_i |a_i⟩|b_i⟩
  If all λ_i equal: maximally entangled.
  Entanglement entropy: S = −Σ_i λ_i² log_2(λ_i²)

CHSH (Clauser–Horne–Shimony–Holt) inequality:
  Correlation C(a, b) = ⟨A_a B_b⟩ for measurement directions a, b
  Classical bound (any local hidden variable model):
    |C(a,b) − C(a,b') + C(a',b) + C(a',b')| ≤ 2
  Quantum maximum (Tsirelson bound):
    |S_CHSH| ≤ 2√2 ≈ 2.828   (achieved with |Φ&sup+;⟩ and optimal angles)
  Loophole-free experimental record (Delft 2015): S = 2.42 ± 0.20 > 2

No-cloning theorem:
  There is no unitary U such that U|ψ⟩|0⟩ = |ψ⟩|ψ⟩ for all |ψ⟩.
  Proof: unitarity preserves inner products; if |ψ⟩ and |φ⟩ are non-orthogonal,
  ⟨ψ|φ⟩ = ⟨ψ|φ⟩² ⇒ ⟨ψ|φ⟩ = 0 or 1 — contradiction.
  Consequence: unknown quantum states cannot be copied; eavesdroppers disturb the line.

Quantum teleportation (uses entanglement + classical communication):
  Resources: 1 EPR pair + 2 classical bits → teleport 1 qubit state
  Alice measures in Bell basis → 2 classical bits → Bob applies correction unitary
  Teleportation is not superluminal: the classical bits must be transmitted first.

3. BB84 — Quantum Key Distribution

BB84 (Bennett & Brassard, 1984) is the first quantum cryptography protocol. It allows two parties to establish a shared secret key whose security is guaranteed by the laws of quantum mechanics: any eavesdropper necessarily disturbs the quantum states, introducing detectable errors. Unlike classical key exchange (which relies on computational hardness), BB84 is information-theoretically secure against an adversary with unlimited computing power.

Step 1 — Transmission (Alice → Bob):
  Alice chooses random bit (0/1) and random basis (rectilinear + or diagonal ×).
  Encoding:   bit 0 in + → |0⟩;  bit 1 in + → |1⟩
              bit 0 in × → |+⟩;  bit 1 in × → |−⟩
  Alice sends qubit; repeats for n qubits.

Step 2 — Measurement (Bob):
  Bob measures each qubit in a randomly chosen basis (+ or ×).
  If bases agree (probability 1/2): correct result with certainty.
  If bases disagree: random result, uncorrelated with Alice’s bit.

Step 3 — Basis reconciliation (public channel):
  Alice and Bob announce their bases (not bits).
  They keep only the ~n/2 qubits where bases matched: the “sifted key”.

Step 4 — Eavesdropper detection:
  An intercept-resend eavesdropper (Eve) guesses basis correctly 50% of the time.
  When Eve’s basis is wrong, she collapses the state → Bob sees a random result.
  Eve introduces a 25% QBER (quantum bit error rate) in the sifted key.
  Alice and Bob compare a subset of sifted bits publicly:
    QBER = 0: no eavesdropper detected.
    QBER ≈ 11%: Eve present at maximum information gain.
    → They abort if QBER exceeds threshold (~11%).

Step 5 — Privacy amplification:
  Apply universal hash function to sifted key → shorten but make Eve’s information
  negligible. Remaining key is composably secure (Renner 2005).

Security parameter:
  Key rate R ≥ 1 − h(e) − h(e)  (h = binary entropy, e = QBER)
  At e = 0: R = 1 (perfect efficiency). At e = 11%: R = 0 (E91 threshold).

4. Quantum Gates and Universal Quantum Circuits

Quantum computation proceeds by applying unitary transformations (quantum gates) to qubits. Unlike classical logic gates, quantum gates are reversible: every gate has an inverse. A universal gate set is a finite collection of gates from which any unitary transformation can be approximated to arbitrary precision (Solovay–Kitaev theorem).

Pauli gates (rotations by π about x, y, z axes of Bloch sphere):
  X = [[0,1],[1,0]]    (bit flip: |0⟩↔|1⟩)
  Y = [[0,−i],[i,0]]  (bit+phase flip)
  Z = [[1,0],[0,−1]]  (phase flip: |1⟩→−|1⟩)

Hadamard gate (creates equal superposition):
  H = (1/√2)[[1,1],[1,−1]]
  H|0⟩ = |+⟩;  H|1⟩ = |−⟩
  H is its own inverse: H² = I

Phase / S gate:
  S = [[1,0],[0,i]]  (quarter-turn around Z axis)

T gate (pi/8 gate, needed for universality):
  T = [[1,0],[0,e^{iπ/4}]]

CNOT (CX) — entangling two-qubit gate:
  |00⟩→|00⟩, |01⟩→|01⟩, |10⟩→|11⟩, |11⟩→|10⟩
  (target flipped if control = |1⟩)
  Matrix (in {|00⟩,|01⟩,|10⟩,|11⟩} basis):
  [[1,0,0,0],[0,1,0,0],[0,0,0,1],[0,0,1,0]]

Toffoli (CCNOT) — universal for reversible classical computation:
  Flips target qubit iff both controls are |1⟩

Universal gate sets:
  {H, T, CNOT} is universal for quantum computation.
  {H, T} generates dense rotations on Bloch sphere (irrational multiples of π).
  Solovay–Kitaev: any U(2) gate approximated to ε using O(log^c(1/ε)) gates.

Quantum circuit for Bell state preparation:
  Input |00⟩ → H on qubit 1 → CNOT (ctrl=1, tgt=2) → |Φ&sup+;⟩
  Result: (|00⟩ + |11⟩)/√2

5. Grover’s Search Algorithm — Quadratic Speedup

Grover’s algorithm (1996) searches an unsorted database of N items for a marked entry in O(√N) oracle queries — compared to O(N) classically. Although “only” a quadratic speedup (Shor’s exponential speedup is more dramatic), Grover’s universality is remarkable: it applies to any NP problem whose solutions can be verified in polynomial time, giving a general speedup for unstructured search.

Setup (n qubits, N = 2^n items):
  |s⟩ = H^⊗n |0⟩^⊗n = (1/√N) Σ_{x=0}^{N−1} |x⟩   (equal superposition)
  Marked state |ω⟩ (amplitude 1/√N initially)

Grover iteration G = D · O_f:
  O_f (oracle):  |x⟩ → −|x⟩ if x = ω, else |x⟩ (phase kickback trick)
  D  (diffusion): 2|s⟩⟨s| − I  (inversion about mean)
  Each iteration increases amplitude of |ω⟩ by ~ 2/√N

After k iterations:
  α_ω(k) ≈ sin((2k+1)θ)   where sinθ = 1/√N
  Optimal k* = floor(π/4 · √N) ≈ (π/4)√N
  P(|ω⟩) ≈ 1 at k = k*

Oracle query complexity:
  Grover: O(√N)
  Classical: O(N) (worst case), O(N/2) (average)
  Lower bound (BBBV 1996): Ω(√N) — Grover is optimal.

Generalised amplitude amplification:
  Works for any initial distribution; if fraction of good items = a, need O(1/√a) iterations.
  Used in quantum walk algorithms (NAND tree evaluation, element distinctness).

Hardware requirements example (N = 2^{20} ≈ 10^6):
  Classical: avg 500 000 queries
  Grover: ~ 804 iterations of the Grover operator
  At 1 MHz gate rate: < 1 ms for Grover vs 0.5 s classical — modest real-world advantage at this scale.

6. Shor’s Algorithm — Factoring, the RSA Threat and Quantum Advantage

Shor’s algorithm (1994) factors an n-bit integer N in poly(n) time on a quantum computer, with O(n² log n log log n) quantum gates. The best classical algorithm (general number field sieve) requires subexponential time exp(O(n^{1/3})). For 2048-bit RSA keys, Shor’s algorithm on a fault-tolerant quantum computer would take hours; classical GNFS would take longer than the age of the universe.

Core reduction (classical): factoring N → period-finding
  Pick random a coprime to N.
  Find order r: smallest r > 0 such that a^r ≡ 1 (mod N).
  If r is even and a^{r/2} ¬≡ −1 (mod N):
    gcd(a^{r/2} ± 1, N) gives non-trivial factors of N.
  Classical period-finding: O(exp(n^{1/3})) — the hard part.

Quantum period-finding (Quantum Fourier Transform):
  1. Prepare |s⟩ = (1/√2^m) Σ_{x=0}^{2^m-1} |x⟩|0⟩
  2. Apply modular exponentiation: |x⟩|0⟩ → |x⟩|a^x mod N⟩
  3. QFT on first register: produces peaks at multiples of 2^m/r
  4. Measure first register: collapse to value near k·2^m/r
  5. Continued-fraction expansion: recover r from k/r estimate.

Quantum Fourier Transform (n qubits):
  QFT|j⟩ = (1/√2^n) Σ_{k=0}^{2^n−1} e^{2πijk/2^n} |k⟩
  Circuit depth: O(n²) gates (exact), O(n log n) (approximate QFT)

Gate count for factoring 2048-bit RSA:
  Physical qubits needed: ~4 000 logical qubits + error correction → ~4 million physical qubits
  Current state (2024): IBM Eagle 127 qubits, IBM Condor 1 121 qubits
  Timeline estimate: fault-tolerant factoring of RSA-2048 — 2035–2050 range (debated)

Post-quantum cryptography (NIST PQC, 2024 standards):
  CRYSTALS-Kyber (ML-KEM): lattice-based key encapsulation
  CRYSTALS-Dilithium (ML-DSA): lattice-based digital signatures
  SPHINCS+: hash-based signatures
  These are believed secure against both classical and quantum computers.