Lesson 1: Introduction to Quantum Computing and Motivation¶
1.1 Learning Outcomes¶
By the end of this hour a student will be able to:
- Explain why classical computing is approaching physical limits, and why this motivates a new computational model.
- Distinguish a bit from a qubit at a conceptual level.
- State the three resources that give quantum computers their power: superposition, interference and entanglement.
- Place quantum computing within complexity theory (the class BQP) and state what quantum computers are not good at.
- Recall the DiVincenzo criteria for a physical quantum computer and name the major hardware platforms.
1.2 Why Do We Need a New Model of Computation?¶
The end of easy scaling¶
For fifty years, computing improved because transistors kept shrinking. Moore's law — the observation by Gordon Moore (1965) that the number of transistors on a chip doubles roughly every two years — was an economic and engineering trend, not a law of physics. It is now failing for three physical reasons:
- Quantum tunnelling. At gate lengths of a few nanometres the insulating oxide layer is only a handful of atoms thick. Electrons tunnel through it, so a transistor that is "off" still leaks.
- Heat dissipation (the power wall). Power density on a modern die approaches that of a rocket nozzle. Clock speeds have been stuck near 3–5 GHz since about 2005.
- Atomic granularity. A silicon lattice constant is ≈ 0.543 nm. You cannot make a channel thinner than a few atoms.
Landauer's principle and reversible computation¶
Landauer's principle (1961). Erasing one bit of information in a computation at temperature \(T\) must dissipate at least
of energy as heat, where \(k_B = 1.38 \times 10^{-23}\ \mathrm{J/K}\) is Boltzmann's constant. At room temperature (\(T = 300\) K) this is about \(2.87 \times 10^{-21}\) J per erased bit.
The important consequence: the heat comes from erasure, not from computation. A logically
reversible computation — one in which the input can always be recovered from the output — has no
fundamental lower bound on dissipated energy. Classical AND is irreversible (from output 0 you
cannot tell whether the input was 00, 01 or 10); NOT is reversible.
Key link to quantum computing. Every quantum gate is described by a unitary matrix, and every unitary matrix is invertible. Quantum computation is intrinsically reversible. This is not a design choice; it is forced by the laws of quantum mechanics.
The simulation argument (Feynman, 1981)¶
Richard Feynman observed that simulating quantum systems on classical computers is exponentially hard. To store the state of \(n\) interacting spin-½ particles you need \(2^n\) complex amplitudes.
| \(n\) qubits | Complex amplitudes \(2^n\) | Memory at 16 bytes each |
|---|---|---|
| 10 | 1 024 | 16 KB |
| 20 | 1 048 576 | 16 MB |
| 30 | \(1.07\times10^9\) | 17 GB |
| 40 | \(1.10\times10^{12}\) | 17.6 TB |
| 50 | \(1.13\times10^{15}\) | 18 PB |
| 300 | \(2^{300}\) | more atoms than the observable universe |
Feynman's conclusion: "Nature isn't classical, dammit, and if you want to make a simulation of nature, you'd better make it quantum mechanical." If a quantum system can hold this information naturally, use a quantum system as the computer.
1.3 Bits versus Qubits¶
Definition (Classical bit). A classical bit is a system with exactly two distinguishable states, labelled \(0\) and \(1\). At any instant it is in exactly one of them.
Definition (Qubit). A qubit (quantum bit) is a two-level quantum system whose state is a unit vector in a two-dimensional complex Hilbert space \(\mathcal{H} \cong \mathbb{C}^2\) with orthonormal basis \(\{|0\rangle, |1\rangle\}\). A general pure qubit state is
The numbers \(\alpha,\beta\) are called amplitudes. The constraint \(|\alpha|^2+|\beta|^2=1\) is the normalisation condition.
Three things must be understood immediately, because most misconceptions start here:
- A qubit is not "0 and 1 at the same time" in any classical sense. It is in a definite state \(|\psi\rangle\), which happens to be a linear combination (superposition) of \(|0\rangle\) and \(|1\rangle\).
- Measurement destroys the superposition. Measuring \(|\psi\rangle\) in the computational basis yields \(0\) with probability \(|\alpha|^2\) and \(1\) with probability \(|\beta|^2\), and the state collapses to \(|0\rangle\) or \(|1\rangle\) accordingly.
- You cannot read \(\alpha\) and \(\beta\) out of a single copy. One qubit yields exactly one classical bit of accessible information (Holevo's bound).
The scaling of state space¶
\(n\) qubits live in \(\mathbb{C}^{2^n}\); a general \(n\)-qubit state is
So \(n\) qubits carry \(2^n\) complex amplitudes, whereas \(n\) classical bits carry one of \(2^n\) values. This is the source of the potential for exponential advantage — but only potential, because measurement gives you back just \(n\) bits.
1.4 The Three Quantum Resources¶
| Resource | Meaning | What it buys you |
|---|---|---|
| Superposition | A register can be prepared in a linear combination of all \(2^n\) basis states at once | Lets a single evaluation of \(U_f\) "touch" every input |
| Interference | Amplitudes are complex and can cancel (\(+a\) and \(-a\) sum to 0) or reinforce | Suppresses wrong answers and amplifies right ones — this is where the algorithm lives |
| Entanglement | Correlations between qubits that cannot be described by any classical joint probability distribution | Creates state space that is not a product of local spaces; enables teleportation and dense coding |
The central design problem of every quantum algorithm is: how do I arrange the interference so that wrong answers cancel and the right answer is left with a large amplitude? Superposition alone gives nothing — a randomised classical algorithm also "explores many branches".
1.5 Where Quantum Computers Help — and Where They Do Not¶
Complexity classes¶
Definition (BQP). Bounded-error Quantum Polynomial time is the class of decision problems solvable by a uniform family of quantum circuits of size polynomial in the input length, with error probability at most \(1/3\) on every input.
Known relations (all containments believed strict, none proved):
Two facts students must retain:
- Integer factoring is in BQP (Shor, 1994) but is not known to be NP-complete. So Shor's algorithm does not show that quantum computers solve NP-complete problems.
- BQP is not known to contain NP. The best general quantum speed-up for NP search is Grover's quadratic one: \(O(\sqrt{N})\) instead of \(O(N)\). A quadratic speed-up does not turn exponential into polynomial.
The realistic speed-up table¶
| Problem | Best classical | Quantum | Speed-up |
|---|---|---|---|
| Integer factoring (\(n\)-bit) | \(\exp(O(n^{1/3}\log^{2/3} n))\) (GNFS) | \(O(n^3)\) (Shor) | Super-polynomial |
| Discrete logarithm | sub-exponential | polynomial (Shor) | Super-polynomial |
| Unstructured search over \(N\) | \(\Theta(N)\) | \(\Theta(\sqrt N)\) (Grover) | Quadratic |
| Simulating quantum systems | exponential | polynomial | Exponential |
| Linear systems \(A\vec x=\vec b\) | \(O(N s \kappa)\) | \(O(\log N \cdot s^2\kappa^2/\epsilon)\) (HHL) | Exponential, with heavy caveats |
| Sorting, general databases, most of everyday computing | — | — | No speed-up |
1.6 Building a Quantum Computer¶
The DiVincenzo criteria (2000)¶
A useful physical implementation must satisfy:
- A scalable physical system with well-characterised qubits.
- The ability to initialise the register to a simple fiducial state such as \(|00\dots0\rangle\).
- Decoherence times much longer than the gate-operation time.
- A universal set of quantum gates.
- A qubit-specific measurement capability.
For quantum communication, two more are added: the ability to interconvert stationary and flying qubits, and the ability to transmit flying qubits faithfully.
Hardware platforms¶
| Platform | Example | Strength | Weakness |
|---|---|---|---|
| Superconducting transmon | IBM, Google, Rigetti | Fast gates (ns), lithographic scaling | Short coherence (µs), needs ≈15 mK dilution fridge |
| Trapped ion | IonQ, Quantinuum | Very high fidelity, all-to-all connectivity | Slow gates (µs–ms) |
| Photonic | Xanadu, PsiQuantum | Room temperature, natural for communication | Probabilistic two-qubit gates |
| Neutral atom | QuEra, Pasqal | Large arrays, reconfigurable | Younger technology |
| Topological | Microsoft | Intrinsic error protection (in principle) | Still largely unrealised |
NISQ¶
Definition (NISQ). Noisy Intermediate-Scale Quantum (Preskill, 2018) describes the present era: devices with roughly 50–1000 physical qubits, gate error rates of order \(10^{-3}\), and no error correction. NISQ machines can run only shallow circuits. Fault-tolerant machines will need thousands of physical qubits per logical qubit.
1.7 Solved Problems¶
Problem 1 — Memory required for classical simulation¶
How much classical memory is needed to store the state vector of a 45-qubit register if each complex amplitude is stored as two 8-byte doubles? Express in TB.
Solution. Number of amplitudes \(= 2^{45}\). Bytes per amplitude \(= 2 \times 8 = 16\).
Comment. This is why the largest exact statevector simulations reported are around 45–49 qubits and require national-laboratory supercomputers. Every extra qubit doubles the requirement.
Problem 2 — Landauer limit for a real processor¶
A processor erases \(10^{18}\) bits per second and operates at 350 K. What is the minimum power it must dissipate, according to Landauer's principle?
Solution. Energy per erased bit:
Power = energy per bit × bits per second:
Comment. Real processors dissipate ~100 W, i.e. about \(3\times10^4\) times the Landauer bound. So irreversibility is not currently the binding constraint — but it becomes one as devices approach the atomic scale, and it explains why reversibility is theoretically attractive.
Problem 3 — Normalisation of a qubit state¶
Is \(|\psi\rangle = \frac{3}{5}|0\rangle + \frac{4i}{5}|1\rangle\) a valid qubit state? If a measurement is performed in the computational basis, what are the outcome probabilities?
Solution. Check normalisation. Here \(\alpha = 3/5\) and \(\beta = 4i/5\).
Note \(|4i/5|^2 = (4i/5)(\overline{4i/5}) = (4i/5)(-4i/5) = 16/25\).
So it is a valid state. Probabilities:
Problem 4 — Grover versus brute force on a symmetric cipher¶
A cipher has a 128-bit key. A classical machine tests \(10^{12}\) keys per second. A hypothetical quantum machine performs \(10^{9}\) Grover iterations per second. Compare the time to break the cipher.
Solution. Search space \(N = 2^{128} \approx 3.40\times10^{38}\).
Classical (expected half the space):
Quantum (Grover needs \(\approx \frac{\pi}{4}\sqrt N\) iterations):
Comment. Grover reduces \(5.4\times10^{18}\) years to \(459\) years — a colossal speed-up, yet still infeasible. This is exactly why the standard mitigation is "double the symmetric key length": AES-256 under Grover has the effective strength of AES-128 classically. Contrast this with RSA, which Shor breaks outright.
Problem 5 — Counting classical states versus quantum amplitudes¶
Compare (a) the number of distinct values 300 classical bits can hold, and (b) the number of complex amplitudes describing 300 qubits. Relate (b) to the estimated \(10^{80}\) atoms in the observable universe.
Solution.
(a) 300 classical bits hold one value at a time, chosen from \(2^{300}\) possibilities.
(b) 300 qubits are described by \(2^{300}\) complex amplitudes simultaneously.
Comparison: \(10^{90.3} / 10^{80} = 10^{10.3} \approx 2\times10^{10}\).
So describing 300 qubits requires about 20 billion times more numbers than there are atoms in the observable universe — while 300 qubits is a device that could plausibly be built.
But note the catch. Measuring those 300 qubits returns only 300 classical bits. The exponential information is present in the state but not extractable. Quantum algorithm design is the art of arranging interference so that the few bits you can extract are the ones you want.
1.8 Practice Problems¶
- How many classical bytes are needed to store a 30-qubit statevector at single precision (4-byte floats)? [Ans: 8.6 GB]
- Verify that \(|\psi\rangle = \frac{1}{\sqrt3}|0\rangle + \sqrt{\frac{2}{3}}\,e^{i\pi/4}|1\rangle\) is normalised and give \(\Pr[1]\). [Ans: valid; \(2/3\)]
- If Grover requires \(\frac{\pi}{4}\sqrt{N}\) queries, how many queries for \(N = 10^6\)? [Ans: ≈ 785]
- Explain in three sentences why a randomised classical algorithm exploring \(2^n\) branches is not equivalent to quantum superposition.
- Which DiVincenzo criterion is most challenged by superconducting qubits, and why?
- A quantum computer solves factoring efficiently. Does it follow that P = NP? Justify.
1.9 Summary¶
- Classical scaling is limited by tunnelling, heat and atomic size; Landauer's principle ties heat to erasure, and quantum gates are inherently reversible.
- A qubit is a unit vector in \(\mathbb{C}^2\); \(n\) qubits require \(2^n\) amplitudes, which is why quantum simulation is classically hard (Feynman's argument).
- Quantum advantage requires interference, not merely superposition.
- BQP contains factoring, but is not known to contain NP; Grover's speed-up is only quadratic.
- The present NISQ era has noisy, uncorrected devices; DiVincenzo's criteria define what a useful machine must satisfy.
Next lesson: L02 — Linear Algebra I: complex vector spaces and Dirac notation.
Practise now: open Interactive-Web-Platform/unit1-qubit-lab.html and use the State
Explorer tab to build superposition states and observe measurement statistics.