Quantum computing started as a complaint about simulation of quantum systems. Richard Feynman pointed out in 1982 that simulating a quantum system on an ordinary computer is brutally expensive: the description of nn interacting quantum particles grows as 2n2^n, so a few dozen of them exhaust any classical machine. His suggested way around it was to stop simulating. Build the computer out of quantum mechanics instead, and let physics keep track of the bookkeeping for free.

That is what a quantum computer is. Not a faster processor, and not a processor that tries many answers in parallel, which is the most common misreading. It is a different computational model: a physical system prepared in a known state, evolved by operations that obey the rules of quantum mechanics, and then measured. The rules permit interference between the possible paths a computation can take, and a quantum algorithm is one that arranges for the wrong answers to interfere destructively and cancel.

For some quantum algorithms the gain can be large: Shor’s algorithm factors integers in polynomial time, which no classical algorithm is known to do, and Grover’s algorithm searches an unstructured collection in quadratically fewer steps than any classical method can. Simulating molecules and materials was the original motivation, and it is still the application most people expect to pay off first; beyond chemistry, finance and energy systems are the sectors usually named. That expectation, rather than any current proven capability on real-world-sized problems, is what has attracted the investment: national programmes across the United States, China, Canada and Europe, cloud access from IBM, Amazon and Microsoft, and a generation of hardware startups.

Unfortunately, there is no demonstrated quantum advantage on a real-world problem anyone needed solved yet. The claims that exist, the most cited being superconducting in 2019 and photonic in 2022, all ran on sampling tasks constructed to be hard for classical computers and useless for anything else, and some have since been matched by better classical algorithms. Size is as much of an obstacle as noise: the instances that fit on today’s hardware are orders of magnitude smaller than anything worth solving. Hence the field’s own name for this period, after Preskill: the NISQ era, Noisy Intermediate-Scale Quantum, with a literature of its own on what such machines might still be good for.

As the technology advances, the foundation stays put. Hardware comes and goes, but every machine and every algorithm is built from the same object: the qubit. It is small enough to describe completely, and that is what the rest of this post, the first of a series, sets out to do.

A qubit is a vector in a Hilbert space

A normal computer runs on bits, which are either 0 or 1 and stay where they are put. A qubit is not a switch. The first postulate of quantum mechanics says what it is instead: the state of a quantum system is a vector, and for a single qubit that vector lives in a two-dimensional complex vector space called a Hilbert space, written H\mathcal{H}.

Vectors in that space are written in Dirac notation: a state is enclosed as ∣ψ⟩|\psi\rangle, called a ket, and its conjugate transpose as ⟨ψ∣\langle\psi|, a bra. The two together give the notation its other name, bra-ket. The two classical values survive as two particular kets, which are nothing more exotic than the two columns of the identity matrix:

∣0⟩=(10),∣1⟩=(01).|0\rangle = \begin{pmatrix} 1 \\ 0 \end{pmatrix}, \qquad |1\rangle = \begin{pmatrix} 0 \\ 1 \end{pmatrix}.

They are orthonormal, so they are a basis, the computational basis, and in it every state of a single qubit is a unit vector written

∣ψ⟩=α∣0⟩+β∣1⟩,α=cos⁡θ2,β=eiϕsin⁡θ2,∣α∣2+∣β∣2=1.|\psi\rangle = \alpha|0\rangle + \beta|1\rangle, \qquad \alpha = \cos\frac{\theta}{2}, \quad \beta = e^{i\phi}\sin\frac{\theta}{2}, \qquad |\alpha|^2 + |\beta|^2 = 1.

Every popular metaphor about qubits is an approximation of that equation. (Why two real angles are enough to reach every state is explained a few paragraphs down.) Any α\alpha and β\beta obeying the normalisation are an equally valid state, so there is a continuum of them, though reading a qubit out still returns one of two answers. That continuum is what the field is betting on: the sectors named earlier all contain problems whose difficulty comes from having to track exponentially many configurations at once, and a register of nn qubits is a single vector carrying 2n2^n amplitudes. Holding them is not the same as trying every answer at once: the measurement still returns one outcome, and almost all of those amplitudes never come out. What they allow is the interference described above, and that is where any advantage has to come from.

Any two-level quantum system will serve as the hardware: the two polarisations of a photon, two energy levels of a superconducting circuit, two states of a trapped ion. Which one to build with is an open engineering question, and the companies are betting differently: Google and IBM on superconducting circuits, IonQ and Quantinuum on trapped ions. Mathematically they are the same object, the unit vector above.

A vector in H\mathcal{H} takes four real numbers to write down, but two of them are not free. Normalisation removes one. An overall phase multiplying the whole state changes no measurable quantity, so it removes another. Two real angles are left, θ\theta and ϕ\phi, and two angles are also what it takes to point somewhere in three dimensions. So the state can be drawn as an arrow in ordinary space, at the coordinates

x=cos⁡ϕ sin⁡θ,y=sin⁡ϕ sin⁡θ,z=cos⁡θ.x = \cos\phi\,\sin\theta, \qquad y = \sin\phi\,\sin\theta, \qquad z = \cos\theta.

That picture is the Bloch sphere. It is a picture: the state is the vector in H\mathcal{H}, and the arrow is a faithful three-dimensional stand-in for it. For a single qubit the two are interchangeable.

The sphere’s poles are ∣0⟩|0\rangle and ∣1⟩|1\rangle, the two outcomes of reading the qubit out in the usual basis. Everything else on the surface is a superposition of them, and where the arrow points sets the odds.

Drag to orbit.

Polar angle θ = 60°
Azimuth φ = 30°
State
—
As a vector in ℂ²
—
Bloch vector
—

Two sliders, and three descriptions of one thing: the ket, the pair of complex amplitudes it stands for, and the arrow. Drag either angle and all three move together. Setting θ=90°\theta = 90° puts the state on the equator, where the two amplitudes have equal magnitude; from there ϕ\phi moves it around the equator without changing either magnitude, which is the phase doing the only thing a phase does.

Gates are unitary matrices

A state is a vector, so an operation on it is a matrix. The second postulate says which matrices are allowed: a closed system evolves by a unitary transformation, ∣ψ′⟩=U∣ψ⟩|\psi'\rangle = U|\psi\rangle with UU†=U†U=IUU^{\dagger} = U^{\dagger}U = I. For one qubit that is a 2×2 complex matrix, and unitarity is what guarantees the result is still a unit vector.

Solving the Schrödinger equation shows that UU is generated by the system’s own Hamiltonian, the operator describing its total energy:

iℏd∣ψ⟩dt=H∣ψ⟩⟹U(t1,t2)=exp⁡ ⁣[−iH(t2−t1)ℏ].i\hbar\frac{d|\psi\rangle}{dt} = H|\psi\rangle \qquad\Longrightarrow\qquad U(t_1, t_2) = \exp\!\left[\frac{-iH(t_2 - t_1)}{\hbar}\right].

That has a practical consequence. A gate is not an abstract instruction. It is an interaction switched on for a measured length of time, which is why gates take time and why time costs fidelity.

These matrices are the quantum equivalent of logic gates, and every 2×2 unitary turns the Bloch sphere about some axis by some angle and does nothing else. So a single-qubit gate can always be read as a rotation: an axis and an angle. The Pauli XX gate is a half turn about the X axis, which is why it swaps ∣0⟩|0\rangle and ∣1⟩|1\rangle. The Hadamard is a half turn about the diagonal between X and Z, which is why it sends ∣0⟩|0\rangle to ∣+⟩|+\rangle, an equal superposition.

Drag to orbit.

Polar angle θ = 60°
Azimuth φ = 30°
Apply a gate
State
—
Bloch vector
—

Each button applies its matrix and prints it. XX swaps the two amplitudes, which on the sphere is a half turn about the X axis. ZZ flips the sign of the second amplitude, a half turn about Z that leaves both poles where they are and moves everything else. SS and TT are rotations about that same Z axis, by 90° and 45°, which is why neither does anything to a state sitting at a pole. Two SS gates make a ZZ; four TT gates do the same. The matrix and the rotation are one operation described twice.

Reading a qubit out

Measurement is a separate postulate, and it is where the sphere stops being the whole story.

A measurement is a set of operators {Mm}\{M_m\}, one per possible outcome mm. The probability of outcome mm from the state ∣ψ⟩|\psi\rangle is

p(m)=⟨ψ∣Mm†Mm∣ψ⟩,with∑mMm†Mm=I,p(m) = \langle\psi| M_m^{\dagger} M_m |\psi\rangle, \qquad\text{with}\qquad \sum_m M_m^{\dagger} M_m = I,

where the second condition is the requirement that the probabilities sum to 1.

The case that matters in practice is a projective measurement. Here the operators are projectors onto the eigenspaces of an observable MM, a Hermitian matrix, which therefore decomposes as M=∑mλmPmM = \sum_m \lambda_m P_m with real eigenvalues λm\lambda_m. The observable is the physical quantity being measured. Its eigenvalues are the values the meter can read.

Measuring in the computational basis means taking the observable to be the Pauli ZZ, whose projectors are P0=∣0⟩⟨0∣P_0 = |0\rangle\langle 0| and P1=∣1⟩⟨1∣P_1 = |1\rangle\langle 1|. For ∣ψ⟩=α∣0⟩+β∣1⟩|\psi\rangle = \alpha|0\rangle + \beta|1\rangle:

p(1)=⟨ψ∣P1†P1∣ψ⟩=⟨ψ∣1⟩⟨1∣ψ⟩=∣β∣2.p(1) = \langle\psi| P_1^{\dagger} P_1 |\psi\rangle = \langle\psi|1\rangle\langle 1|\psi\rangle = |\beta|^2 .

The amplitudes were the probabilities all along: their magnitudes, squared. The average value of the observable over many repetitions is its expectation value:

⟨M⟩ψ=∑mλm p(m)=⟨ψ∣M∣ψ⟩,\langle M \rangle_\psi = \sum_m \lambda_m \, p(m) = \langle\psi| M |\psi\rangle,

which for ZZ works out to ∣α∣2−∣β∣2|\alpha|^2 - |\beta|^2. Substituting ∣α∣=cos⁡(θ/2)|\alpha| = \cos(\theta/2) and ∣β∣=sin⁡(θ/2)|\beta| = \sin(\theta/2) from the parametrisation above gives cos⁡θ\cos\theta, the zz coordinate of the Bloch vector. So ⟨Z⟩\langle Z\rangle is the arrow’s height, and P(0)=(1+z)/2P(0) = (1+z)/2 follows. The same holds on any axis: for the observable along a unit vector n^\hat{n}, the expectation value is the projection n^⋅r⃗\hat{n}\cdot\vec{r} and the two outcomes have probability (1±n^⋅r⃗)/2(1 \pm \hat{n}\cdot\vec{r})/2.

One consequence of this matters more than the rest. A measurement never returns the state vector, only its projection onto an axis chosen in advance, and one shot returns one bit. The vector itself has to be reconstructed from many shots along different axes. That is what makes characterising a qubit expensive, and it is the cost the second post is about.

Drag to orbit.

Polar angle θ = 60°
Azimuth φ = 30°
Measure the observable
State
—
Bloch vector
—
Outcome probabilities
—
Expectation value ⟨Z⟩
—

The Z, X and Y buttons choose the observable. The chosen axis lights up, and the dot on it is where the state projects: the expectation value, shown as a distance. Park the state on the equator and measure Z: the projection sits at the centre, the expectation value is 0, and the two outcomes are a coin flip. Measure X on the same state and the answer can be a certainty. Same qubit, different question.

Density matrices and mixed states

Everything so far has assumed the qubit has a state vector. Some states a real machine produces are not describable by any vector in H\mathcal{H}, and they need a second representation.

That representation is the density matrix. Build it from a state vector by an outer product, ρ=∣ψ⟩⟨ψ∣\rho = |\psi\rangle\langle\psi|, and for one qubit it comes out written directly in the Bloch coordinates:

ρ=12(1+zx−iyx+iy1−z).\rho = \frac{1}{2} \begin{pmatrix} 1 + z & x - iy \\ x + iy & 1 - z \end{pmatrix}.

Everything the ket could do, ρ\rho does. A gate acts as ρ′=UρU†\rho' = U\rho U^{\dagger}. A measurement gives p(m)=tr(Mm†Mmρ)p(m) = \mathrm{tr}(M_m^{\dagger}M_m\rho), with expectation value ⟨O⟩ρ=tr(ρO)\langle O\rangle_\rho = \mathrm{tr}(\rho O). So far this is a change of notation.

It earns its keep on the states that have no vector. The general density matrix is a weighted mixture ρ=∑ipi∣ψi⟩⟨ψi∣\rho = \sum_i p_i |\psi_i\rangle\langle\psi_i|, and unless one of those weights is 1, no single ∣ψ⟩|\psi\rangle reproduces it. Such a state is mixed. The ones that came from a vector are pure. The test is tr(ρ2)\mathrm{tr}(\rho^2), equal to 1 for a pure state and less than 1 for a mixed one. On the sphere the distinction is a length: a pure state’s Bloch vector reaches the surface, a mixed state’s falls short of it.

Decoherence is the process that takes a qubit from the first case to the second. The slider below applies it by degrees.

Drag to orbit.

Polar angle θ = 60°
Azimuth φ = 30°
Decoherence ε = 0°
State
—
Bloch vector
—
Length |r| / purity Tr(ρ²)
—

Push it and the arrow leaves the surface. Length and purity fall together, and the state readout stops offering an α∣0⟩+β∣1⟩\alpha|0\rangle + \beta|1\rangle form, because at that point no pair of numbers α,β\alpha, \beta describes the qubit. That is not a gap in the notation. It is why the density matrix exists.

Watch what the measurement statistics do as the arrow shortens: on ZZ, nothing. A state on the equator was already a coin flip, and the fully mixed state still is: one basis cannot tell superposition from mixture. The difference is that the equator state had an axis of certainty, XX, and the shrinking arrow is losing it. At zero length, (1±n^⋅r⃗)/2(1 \pm \hat{n}\cdot\vec{r})/2 is a coin flip for every n^\hat{n}: there is no longer a right question to ask.

At the far end of the slider the arrow has no length at all and the purity has bottomed out at 1/21/2, the least a qubit can be. What has actually happened to it there is the subject of the next section.

Entanglement and the partial trace

A shorter vector is not damage in the ordinary sense. It is bookkeeping, and seeing why takes two qubits.

Put two together and the joint state is their tensor product, ∣ψ1⟩⊗∣ψ2⟩|\psi_1\rangle \otimes |\psi_2\rangle. Multiplied out, that gives four amplitudes, on ∣00⟩|00\rangle, ∣01⟩|01\rangle, ∣10⟩|10\rangle and ∣11⟩|11\rangle. The map does not always run backwards. Take

∣ψ⟩=∣00⟩+∣11⟩2.|\psi\rangle = \frac{|00\rangle + |11\rangle}{\sqrt{2}}.

Matching coefficients against a product state requires α1β2=0\alpha_1\beta_2 = 0 and β1α2=0\beta_1\alpha_2 = 0, while the surviving terms require all four coefficients to be nonzero. No pair of single-qubit states multiplies out to this. The state is entangled: it exists only as a description of the pair, and neither half has a state of its own.

The operation that makes that concrete is the partial trace, the rule for discarding one half of a joint state. As a density matrix the pair above is

ρ=∣ψ⟩⟨ψ∣=12(1001000000001001),\rho = |\psi\rangle\langle\psi| = \frac{1}{2} \begin{pmatrix} 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 \end{pmatrix},

and tracing out the second qubit runs term by term, with each cross term dying because tr(∣0⟩⟨1∣)=0\mathrm{tr}(|0\rangle\langle 1|) = 0:

ρ1=tr2(ρ)=∣0⟩⟨0∣ tr(∣0⟩⟨0∣)+∣1⟩⟨1∣ tr(∣1⟩⟨1∣)2=12(1001)=12I.\rho_1 = \mathrm{tr}_2(\rho) = \frac{|0\rangle\langle 0|\,\mathrm{tr}(|0\rangle\langle 0|) + |1\rangle\langle 1|\,\mathrm{tr}(|1\rangle\langle 1|)}{2} = \frac{1}{2}\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} = \frac{1}{2}I.

Compare that with the Bloch form of ρ\rho and it gives x=y=z=0x = y = z = 0. The vector has zero length and sits at the centre of the sphere, with tr(ρ2)=1/2\mathrm{tr}(\rho^2) = 1/2, the lowest value it can take. One half of a maximally entangled pair, looked at alone, is as mixed as a qubit can be, and every measurement on every axis is a coin flip. The pair as a whole is a perfectly definite pure state. Nothing was lost. It does not live in the half being held.

That is decoherence, and it is what the slider in the previous section was simulating. A qubit entangles with something that is not being tracked (a neighbouring qubit, the control line, the environment), and the honest description moves to a larger space H1⊗H2\mathcal{H}_1 \otimes \mathcal{H}_2 that includes whatever it entangled with. Looking only at H1\mathcal{H}_1 means implicitly taking that partial trace, and what comes back is a mixed state: an arrow inside the sphere. How far inside depends on how strongly the entanglement took hold.

The information is not destroyed. It is somewhere unreachable, which is the sharp definition, because access to the other half would recover it. DiVincenzo’s criteria for a working quantum computer put a hard requirement on this: a qubit’s decoherence time must be far longer than the time it takes to operate on the qubit.

That completes the object. A qubit is a unit vector in H\mathcal{H}, drawn as an arrow on the Bloch sphere; gates are unitary matrices, which act on the arrow as rotations; a measurement projects it onto an axis and returns one bit; and when the vector is not enough, because the qubit has entangled with something outside the description, a density matrix takes over and the arrow moves inside the sphere. There is nothing further about a single qubit that this leaves out.

Two of those properties are worth putting side by side, because together they explain most of what makes quantum computing hard to engineer. A qubit entangles with things nobody is tracking whether or not the algorithm allows for it, so the arrow shortens on its own. And a measurement returns a projection onto one chosen axis, so the shortening is never directly visible: it has to be reconstructed from many shots along many axes. A qubit is a simple object that is expensive to look at, and a good deal of the field follows from that.

References

The concepts and their presentation follow Nielsen and Chuang throughout; the rest are cited where they appear.

  1. M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information: 10th Anniversary Edition, Cambridge University Press (2010). doi:10.1017/CBO9780511976667
  2. R. P. Feynman, “Simulating physics with computers”, International Journal of Theoretical Physics 21(6), 467-488 (1982). doi:10.1007/BF02650179
  3. P. W. Shor, “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”, SIAM Journal on Computing 26(5), 1484-1509 (1997). doi:10.1137/S0097539795293172
  4. L. K. Grover, “A fast quantum mechanical algorithm for database search”, Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC), 212-219 (1996). doi:10.1145/237814.237866
  5. D. P. DiVincenzo, “The Physical Implementation of Quantum Computation”, Fortschritte der Physik 48(9-11), 771-783 (2000). doi:10.1002/1521-3978(200009)48:9/11
  6. J. Preskill, “Quantum Computing in the NISQ era and beyond”, Quantum 2, 79 (2018). doi:10.22331/q-2018-08-06-79
  7. F. Arute et al, “Quantum supremacy using a programmable superconducting processor”, Nature 574, 505-510 (2019). doi:10.1038/s41586-019-1666-5
  8. L. S. Madsen et al, “Quantum computational advantage with a programmable photonic processor”, Nature 606(7912), 75-81 (2022). doi:10.1038/s41586-022-04725-x
  9. K. Bharti et al, “Noisy intermediate-scale quantum algorithms”, Reviews of Modern Physics 94(1), 015004 (2022). doi:10.1103/RevModPhys.94.015004
  10. P. Murali, D. C. McKay, M. Martonosi and A. Javadi-Abhari, “Software Mitigation of Crosstalk on Noisy Intermediate-Scale Quantum Computers”, ASPLOS (2020). doi:10.1145/3373376.3378477