ConceptBeginnerQuantum computing fundamentalsLesson 1

Introduction to Quantum Computing

Quantum computing is a model of computation that processes information encoded in quantum states, evolved by unitary operations and read out by measurement, exploiting superposition, entanglement and interference.

Quantum computing is a model of computation in which information is stored in physical systems governed by the laws of quantum mechanics. Its unit of information is the quantum bit, or qubit, whose state is a unit vector in a two-dimensional complex vector space, not just the value 0 or 1. In the circuit model, a computation has three stages: initialising the qubits, usually in the state $|0\rangle^{\otimes n}$; applying a sequence of quantum gates, which are unitary matrices; and measurement, which returns a classical bit string with probabilities given by the Born rule.

The state of $n$ qubits is described by $2^n$ complex probability amplitudes. This exponential growth is what makes classical simulation expensive: the simulator in this lab stores each amplitude as a double-precision complex number (16 bytes), so it needs about $16\cdot 2^n$ bytes. But this does not mean that a quantum computer "tries all solutions at once" and then hands us the best one; measurement returns only a single $n$-bit outcome. The computational advantage, when there is one, comes from arranging interference so that the amplitudes of correct answers grow and those of wrong answers cancel.

There are proven results for specific problems: Shor's algorithm factors integers in polynomial time, while no polynomial-time classical algorithm is known for this (which is not a proof that none exists); and Grover's algorithm gives a proven quadratic speed-up in the query model for unstructured search. For many other problems no speed-up is known, and quantum computers are not believed to solve NP-complete problems efficiently.

Current devices belong to what Preskill called the NISQ era: tens to hundreds of noisy qubits without full error correction. So we must always distinguish between simulating a circuit on a classical computer, as this lab does, and running it on real quantum hardware; the simulation gives exact mathematical results but proves no quantum advantage, and it becomes practically impossible as the number of qubits grows.

This path is organised step by step: we start with complex numbers, Dirac notation and Hilbert space as mathematical tools, move on to the state, superposition, measurement, interference and entanglement as physical principles, and end with decoherence and noise, which determine what can actually be run on current devices.

Mathematical formula

$$2^n\ \text{complex amplitudes to describe } n \text{ qubits}$$

Worked example

Compute the memory needed to simulate the state vector. Each amplitude takes 16 bytes (two double-precision real numbers).

At $n=16$: $16\cdot 2^{16}=1\,048\,576$ bytes, about 1 MiB, easily possible in the browser.

At $n=30$: $16\cdot 2^{30}=17\,179\,869\,184$ bytes, i.e. 16 GiB. Each extra qubit doubles the memory, so at $n=50$ we need about $1.8\times 10^{16}$ bytes, beyond the reach of ordinary computers. This shows why the lab is limited to 16 qubits by default.

Test your understanding

The quiz needs JavaScript.

Related topics

References

  1. Michael A. Nielsen; Isaac L. Chuang (2010). Quantum Computation and Quantum Information (10th Anniversary Edition). Cambridge University Press doi:10.1017/CBO9780511976667The standard reference for quantum computing; the Crossref record gives 2012 for the Cambridge Core online edition.
  2. John Watrous / IBM Quantum (2025). Basics of Quantum Information (course). IBM Quantum Learning quantum.cloud.ibm.com
  3. John Preskill (2018). Quantum Computing in the NISQ era and beyond. Quantum 2:79 doi:10.22331/q-2018-08-06-79