Quantum
Computing.

Why bother?

Classical computers struggle to simulate quantum systems because the state space grows exponentially with particle count. Richard Feynman observed in 1982 that the natural fix is to compute with a quantum system. David Deutsch followed in 1985 with the universal quantum Turing machine.

Today the question is not whether quantum computers work, but for which problems they will provide a real, scalable advantage over classical hardware.

The qubit.

A qubit's pure state is a unit vector in a 2-dimensional complex Hilbert space:

|ψ⟩ = α|0⟩ + β|1⟩,   |α|² + |β|² = 1

Measurement in the computational basis collapses the state to |0⟩ with probability |α|² or |1⟩ with probability |β|². N qubits live in a 2ᴺ-dimensional space — the resource that makes quantum computing potentially powerful.

Bloch sphere.

The Bloch sphere parameterizes any pure single-qubit state by two angles: |ψ⟩ = cos(θ/2)|0⟩ + e^(iφ) sin(θ/2)|1⟩.

Superposition & entanglement.

Superposition — a qubit in a non-trivial linear combination of |0⟩ and |1⟩.

Entanglement — a multi-qubit state that cannot be written as a tensor product of single-qubit states. The canonical example is a Bell pair:

|Φ⁺⟩ = (|00⟩ + |11⟩) / √2

Measure one qubit and the other's outcome is instantly correlated, regardless of distance. Bell's 1964 inequality and its experimental violations (Aspect 1982; Hensen 2015 loophole-free; Nobel 2022) ruled out local hidden-variable theories.

Gates & circuits.

Gates are unitary operators. A small set — Hadamard (H), phase (S, T), CNOT — is universal: any unitary can be approximated to arbitrary precision (Solovay–Kitaev).

Shor's algorithm.

Peter Shor, 1994. Factor an n-bit integer in polynomial time on a quantum computer. The classical best is sub-exponential (general number field sieve). Shor reduces factoring to order-finding, then uses the quantum Fourier transform to find the period.

If a fault-tolerant quantum computer with a few thousand logical qubits arrives, RSA and ECC are over. NIST has been standardizing post-quantum schemes (Kyber/ML-KEM, Dilithium/ML-DSA) since 2024.

Other key algorithms.

Hardware modalities.

The advantage debate.

2019. Google's Sycamore (53 qubits) sampled random circuits in 200 seconds; they claimed a classical machine would need 10,000 years. IBM responded that a tensor-network simulation could do it in 2.5 days.

2020. USTC's Jiuzhang demonstrated photonic Gaussian boson sampling.

2024–2025. Quantum error correction crossed break-even on several platforms; surface-code logical qubits with sub-physical error rates.

Code sketch.

# Bell pair in Qiskit
from qiskit import QuantumCircuit, transpile
from qiskit_aer import AerSimulator

qc = QuantumCircuit(2, 2)
qc.h(0)              # Hadamard on qubit 0
qc.cx(0, 1)          # CNOT from 0 to 1
qc.measure([0,1], [0,1])

sim = AerSimulator()
result = sim.run(transpile(qc, sim), shots=1024).result()
print(result.get_counts())
# {'00': ~512, '11': ~512}

Glossary.

Decoherence

Loss of phase information from environmental coupling — the enemy of long quantum computations.

Surface code

Topological error-correcting code on a 2D lattice. The most actively engineered fault-tolerant scheme.

NISQ

Noisy Intermediate-Scale Quantum (Preskill, 2018) — the current 50–1000 qubit regime, no full error correction.

T-count

Number of T-gates in a circuit; a proxy for fault-tolerant cost.

Magic state

Resource state needed to perform non-Clifford operations fault-tolerantly.

Watch this.

Watch: Shor algorithm explained

Open problems.

• Scalable, low-overhead fault tolerance below the surface-code threshold.
• A non-cryptographic killer app — quantum chemistry beyond classical reach.
• Practical post-quantum migration of the global PKI.
• The first machine that runs Shor at cryptographically interesting sizes.