Skip to content

Lesson 1: Introduction to Quantum Computing and Motivation

1.1 Learning Outcomes

By the end of this hour a student will be able to:

  1. Explain why classical computing is approaching physical limits, and why this motivates a new computational model.
  2. Distinguish a bit from a qubit at a conceptual level.
  3. State the three resources that give quantum computers their power: superposition, interference and entanglement.
  4. Place quantum computing within complexity theory (the class BQP) and state what quantum computers are not good at.
  5. 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

\[ E_{\min} = k_B T \ln 2 \]

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

\[ |\psi\rangle = \alpha|0\rangle + \beta|1\rangle, \qquad \alpha,\beta \in \mathbb{C}, \qquad |\alpha|^2 + |\beta|^2 = 1 .\]

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:

  1. 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\).
  2. 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.
  3. 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

\[ |\psi\rangle = \sum_{x \in \{0,1\}^n} \alpha_x |x\rangle, \qquad \sum_x |\alpha_x|^2 = 1 .\]

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):

\[ \mathrm{P} \subseteq \mathrm{BPP} \subseteq \mathrm{BQP} \subseteq \mathrm{PSPACE} \]

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:

  1. A scalable physical system with well-characterised qubits.
  2. The ability to initialise the register to a simple fiducial state such as \(|00\dots0\rangle\).
  3. Decoherence times much longer than the gate-operation time.
  4. A universal set of quantum gates.
  5. 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\).

\[ \text{Memory} = 2^{45} \times 16 = 2^{45} \times 2^4 = 2^{49}\ \text{bytes} \]
\[ 2^{49}\ \text{bytes} = \frac{2^{49}}{2^{40}}\ \text{TB} = 2^{9}\ \text{TB} = \mathbf{512\ TB}. \]

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:

\[ E = k_B T \ln 2 = (1.38\times10^{-23})(350)(0.6931) = 3.348\times10^{-21}\ \mathrm{J}. \]

Power = energy per bit × bits per second:

\[ P = 3.348\times10^{-21} \times 10^{18} = 3.35\times10^{-3}\ \mathrm{W} \approx \mathbf{3.35\ mW}. \]

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\).

\[ |\alpha|^2 = \left(\tfrac{3}{5}\right)^2 = \tfrac{9}{25}, \qquad |\beta|^2 = \left|\tfrac{4i}{5}\right|^2 = \tfrac{4}{5}\cdot\tfrac{4}{5} = \tfrac{16}{25}. \]

Note \(|4i/5|^2 = (4i/5)(\overline{4i/5}) = (4i/5)(-4i/5) = 16/25\).

\[ |\alpha|^2 + |\beta|^2 = \tfrac{9}{25} + \tfrac{16}{25} = 1 \quad \checkmark \]

So it is a valid state. Probabilities:

\[ \Pr[0] = \tfrac{9}{25} = 0.36, \qquad \Pr[1] = \tfrac{16}{25} = 0.64 .\]

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):

\[ t_c = \frac{2^{127}}{10^{12}} = \frac{1.70\times10^{38}}{10^{12}} = 1.70\times10^{26}\ \mathrm{s} \approx 5.4\times10^{18}\ \text{years}. \]

Quantum (Grover needs \(\approx \frac{\pi}{4}\sqrt N\) iterations):

\[ \frac{\pi}{4}\sqrt{2^{128}} = \frac{\pi}{4} \cdot 2^{64} = 0.7854 \times 1.845\times10^{19} = 1.449\times10^{19}\ \text{iterations}. \]
\[ t_q = \frac{1.449\times10^{19}}{10^{9}} = 1.449\times10^{10}\ \mathrm{s} \approx \mathbf{459\ \text{years}}. \]

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.

\[ 2^{300} = 10^{300\log_{10}2} = 10^{300 \times 0.30103} = 10^{90.3} \approx 2\times10^{90}. \]

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

  1. How many classical bytes are needed to store a 30-qubit statevector at single precision (4-byte floats)? [Ans: 8.6 GB]
  2. 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\)]
  3. If Grover requires \(\frac{\pi}{4}\sqrt{N}\) queries, how many queries for \(N = 10^6\)? [Ans: ≈ 785]
  4. Explain in three sentences why a randomised classical algorithm exploring \(2^n\) branches is not equivalent to quantum superposition.
  5. Which DiVincenzo criterion is most challenged by superconducting qubits, and why?
  6. 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.