Exponential growth
★☆☆A state of \(n\) qubits requires \(2^n\) complex amplitudes. From how many qubits does this number exceed \(10^{80}\), the order of magnitude of the number of atoms in the observable universe?
Chapter 4 · Lectures 4 h + Tutorials 3 h
Two qubits cannot be described by two arrows on two spheres. Some states of the pair assign no eigenstate to either qubit: the information lies in the correlations.
To describe two qubits, we use the tensor product. The space has four dimensions, with basis zero zero, zero one, one zero, one one. With n qubits, you need two to the power n amplitudes.
Some states of the pair cannot be written as the product of two individual states. They are entangled. In the Bell state phi plus, each qubit on its own gives zero or one at random, but the two results are always the same.
These correlations go beyond anything a local hidden-variable theory allows. The Bell test, in the form of the CHSH inequality, bounds a certain combination by two. Quantum mechanics reaches two root two. The experiments of two thousand and fifteen confirmed this with no loophole. Even so, no signal travels faster than light.
The state of a single qubit from an entangled pair is a mixture, described by a density operator. The von Neumann entropy of this mixture measures the entanglement: one bit for a Bell state.
Finally, the BB eighty-four protocol uses measurement to detect an eavesdropper. Its security is proven for the ideal protocol; real devices have flaws, which must be kept under control.
Alice rolls a die (6 outcomes), Bob draws a card (52 outcomes). The combined system has \(6 \times 52 = 312\) outcomes, not \(6 + 52\). In quantum mechanics too, dimensions multiply.
The state space of the system \(A + B\) is \(\mathcal H = \mathcal H_A \otimes \mathcal H_B\), of dimension \(\dim\mathcal H_A \times \dim\mathcal H_B\). The product \(\ket{a}\otimes\ket{b} = \ket{ab}\) is linear in each factor, and
For two qubits, the computational basis is \(\{\ket{00}, \ket{01}, \ket{10}, \ket{11}\}\). In components:
The lecture notes translate “produit tensoriel” as outer product. In English, it is the tensor product (or Kronecker product for matrices). The outer product denotes \(\ket{a}\bra{b}\), which is an operator, not a state.
\(\frac{1}{\sqrt2}\binom{1}{1}\otimes\frac{1}{\sqrt2}\binom{1}{-1} = \frac12(1, -1, 1, -1)^{\mathsf T}\), that is \(\frac12(\ket{00} - \ket{01} + \ket{10} - \ket{11})\). Expanding \((\ket0 + \ket1)\otimes(\ket0 - \ket1)\) gives the same result. Preset “|+⟩|−⟩” in lab 4.1.
A state of \(n\) qubits requires \(2^n\) complex amplitudes. From how many qubits does this number exceed \(10^{80}\), the order of magnitude of the number of atoms in the observable universe?
The lecture notes speak of “quantum parallelism”. A register of 266 qubits does not deliver \(2^{266}\) results: a measurement gives one string of 266 bits. A useful quantum algorithm arranges for the interference between amplitudes to reinforce the right answer before the measurement.
A pure state \(\ket\Psi\) of \(A + B\) is separable (factorisable) if it can be written \(\ket{\psi_A}\otimes\ket{\psi_B}\). Otherwise it is entangled. For two qubits, \(\ket\Psi = \alpha\ket{00} + \beta\ket{01} + \gamma\ket{10} + \delta\ket{11}\) is separable if and only if
Arrange the amplitudes in a matrix \(C = \begin{pmatrix}\alpha&\beta\\ \gamma&\delta\end{pmatrix}\) (rows: Alice, columns: Bob). The criterion reads \(\det C = 0\): the two rows are proportional.
The lecture notes define “correlation or entanglement” together. These are two distinct notions. Two socks of the same colour packed in two suitcases are correlated, with nothing quantum about them. Entanglement is a property of the state: it does not factorise. It produces correlations in several bases at once, and some of them violate Bell inequalities, which no classical correlation does.
The lecture notes write them \(\ket{B_{xy}} = \frac{1}{\sqrt2}\big(\ket{0y} + (-1)^x\ket{1\bar y}\big)\). The names \(\Phi^\pm, \Psi^\pm\) are also common. They form an orthonormal basis of \(\mathbb C^2\otimes\mathbb C^2\).
| State | Expression | \(\langle Z\otimes Z\rangle\) | \(\langle X\otimes X\rangle\) | \(\langle Y\otimes Y\rangle\) |
|---|---|---|---|---|
| \(B_{00} = \Phi^+\) | \(\tfrac{1}{\sqrt2}(\ket{00} + \ket{11})\) | +1 | +1 | −1 |
| \(B_{10} = \Phi^-\) | \(\tfrac{1}{\sqrt2}(\ket{00} - \ket{11})\) | +1 | −1 | +1 |
| \(B_{01} = \Psi^+\) | \(\tfrac{1}{\sqrt2}(\ket{01} + \ket{10})\) | −1 | +1 | +1 |
| \(B_{11} = \Psi^-\) | \(\tfrac{1}{\sqrt2}(\ket{01} - \ket{10})\) | −1 | −1 | −1 |
+1: results always identical; −1: always opposite. The table in the lecture notes speaks of “XX or YY” correlations for the X basis: read this as “results \(++\) or \(--\)”. In every case, each result taken alone remains 50/50. The singlet \(\Psi^-\) is anticorrelated in every direction.
Before running the lab: write down your prediction, run it, compare, then explain the gap in one sentence. Is the state obtained by Hadamard then CNOT separable or entangled? What value do you predict for \(\alpha\delta-\beta\gamma\)?
The sliders set arbitrary real amplitudes; the state is normalised before any calculation. On the right, the Bloch vector of \(\rho_A\): on the circle if the state factorises, at the centre for a Bell state. With \(\cos\theta\ket{00} + \sin\theta\ket{11}\), we have \(\det C = \tfrac12\sin 2\theta\), \(\lambda = \cos^2\theta, \sin^2\theta\), and \(S\) goes from 0 to 1 bit at \(\theta = 45°\).
Let \(\ket{\psi_3} = \frac{1}{\sqrt{10}}\big(2\ket{00} + 2\ket{01} + \ket{10} + \ket{11}\big)\). Is this state entangled?
Compute \(\langle X_A X_B\rangle = \bra{B_{11}}X\otimes X\ket{B_{11}}\) for \(\ket{B_{11}} = \frac{1}{\sqrt2}(\ket{01} - \ket{10})\).
Einstein believed that each particle carries “instructions” fixed at the source. Bell (1964) showed that such a local theory bounds a combination of correlations. In the CHSH form (Clauser, Horne, Shimony, Holt, 1969), Alice chooses between two settings \(a, a'\), Bob between \(b, b'\), each result equals \(\pm1\), and
For spins measured along axes in the \(xz\) plane making angles \(a\) and \(b\) with \(z\), the state \(\ket{\Phi^+}\) gives \(E(a,b) = \cos(a - b)\). For photons and polarisers, the angles are halved: \(E = \cos 2(\alpha - \beta)\).
cos Δ (quantum)1 − 2|Δ|/π (hidden variables)
Each pair receives a random setting at Alice and one at Bob. With the settings 0°, 90°, 45°, 135°, the quantum source gives \(S \approx 2.83\). The hidden-variable model (each pair carries a random direction \(\lambda\), result \(\operatorname{sign}\cos(a - \lambda)\)) tops out at 2. Note that, in both cases, Alice’s results taken alone remain 50/50: Bob cannot send a message through his choice of setting.
With \(E(a,b) = \cos(a - b)\) and the settings \(a = 0°\), \(a' = 90°\), \(b = 45°\), \(b' = 135°\), what is \(S\)? (write, for example, 2*sqrt(2))
The introduction of the lecture notes compares entanglement to two coins, one of which, on Mars, “lands on heads” as soon as the other lands on tails. This picture describes a classical correlation, which hidden instructions explain perfectly well. What is quantum is the violation of CHSH with measurements in different bases.
Nor is there any usable “influence”: Alice’s local statistics do not depend on Bob’s setting (lab 4.2), so no signal travels faster than light. What the experiments rule out are local hidden-variable theories. Einstein was right about the absence of faster-than-light signalling; his hypothesis of pre-established local instructions is refuted.
Two chronological errors: Heisenberg’s uncertainty principle (1927) is in no way a “first indication of non-locality”; and Zeilinger’s experiments date mainly from the 1990s–2010s, not the 1970s–1980s. Clauser published in 1972, Aspect in 1982.
The first experiments left “loopholes”: inefficient detectors, settings chosen too slowly. In 2015, three teams (Delft, Vienna, NIST in Boulder) violated a Bell inequality while closing these loopholes simultaneously. The 2022 Nobel Prize rewarded Aspect, Clauser and Zeilinger for these tests and for the quantum information science that grew out of them.
Bennett and Brassard (1984) proposed sending single photons polarised in one of two bases: \(Z\) (\(\ket H = 0\), \(\ket V = 1\)) or \(X\) (\(+45° = 0\), \(-45° = 1\)). Bob measures in a randomly chosen basis. They then publicly announce their bases (never their bits), keep the cases where they match (the sifted key, about 50%), and then sacrifice part of this key to estimate the error rate. An eavesdropper who measures and resends picks the wrong basis half the time, and then causes an error half the time: 25% errors on the sifted key. The version with entangled pairs (BBM92, exercise 4.2.1 of the lecture notes) works the same way.
| No. | Alice (basis · bit) | Eve | Bob (basis · bit) | Use | Match |
|---|
Half of the sifted bits, chosen at random, are used as a test. \((3/4)^m\) is the probability that Eve, if she intercepts everything, causes no error on the \(m\) tested bits. The 11% threshold corresponds to the security proof of Shor and Preskill (2000) for BB84: beyond it, no correction guarantees secrecy.
The security of BB84 is proven for the ideal protocol: single photons, devices that behave as modelled. Real systems have had implementation flaws (multi-photon pulses, detectors blinded by a laser). And current satellite links go through a trusted relay: the satellite knows the key. It is better to say “security based on physics, under verifiable assumptions” than “unbreakable”.
In the BB84 worksheet of the lecture notes, the rows “axis and state chosen by Bob” are marked “public”: only the bases are announced, not the results. And for 250 tested bits, \((3/4)^{250} \approx 6\times10^{-32}\), not \(3\times10^{-63}\) (which corresponds to 500 bits).
Eve intercepts and resends every photon. Alice and Bob publicly compare 20 bits of their sifted key. What is the probability that they find no error?
\((A\otimes B)(\ket{\psi_A}\otimes\ket{\psi_B}) = A\ket{\psi_A}\otimes B\ket{\psi_B}\). A measurement on Alice alone uses \(A\otimes \mathbb 1\), on Bob alone \(\mathbb 1\otimes B\). These two operators always commute: \([A\otimes\mathbb 1, \mathbb 1\otimes B] = 0\). As matrices (Kronecker product):
The probability that the first qubit gives \(0\) is \(\bra\psi(P_0\otimes\mathbb 1)\ket\psi\), with \(P_0 = \ket0\bra0\): add \(|c_{00}|^2 + |c_{01}|^2\). The state after measurement is the projection, renormalised.
Let \(\ket\psi = \frac{1}{\sqrt8}\ket{00} + \sqrt{\frac38}\ket{01} + \frac12\ket{10} + \frac12\ket{11}\) (example 4.3.2 of the lecture notes). Bob measures his qubit with \(\mathbb 1\otimes P_1\). What is the probability that he finds \(1\)?
In the solution of example 4.3.2, the projection onto \(\ket\phi = \ket{01}\) is written with \(\bra{10}\). Read \(\bra{01}\): it is indeed the \(\sqrt{3/8}\) component of \(\ket{01}\) that gives \(P = 3/8\).
In \(\ket{\Phi^+}\), Alice’s qubit has no ket of its own. To describe it, we replace the state vector by an operator.
Pure state: \(\rho = \ket\psi\bra\psi\). Statistical mixture: \(\rho = \sum_i p_i\ket{\psi_i}\bra{\psi_i}\) with \(\sum_i p_i = 1\). Every physical \(\rho\) is Hermitian, of trace 1 and positive. We have
Purity: \(\mathrm{Tr}\rho^2 = 1\) for a pure state, \(< 1\) for a mixture, with a minimum \(1/N\) in dimension \(N\). For a qubit, \(\rho = \frac12(\mathbb 1 + \vec b\cdot\vec\sigma)\) and \(\mathrm{Tr}\rho^2 = \frac12(1 + |\vec b|^2)\).
Alice’s reduced state is \(\rho_A = \mathrm{Tr}_B\,\rho_{AB} = \sum_m \bra{m}_B\,\rho_{AB}\,\ket{m}_B\). It gives all the statistics of measurements made on A alone. For \(\ket\Psi = \sum c_{ab}\ket{ab}\), \(\rho_A = CC^\dagger\) with the matrix \(C\) of section 4.2. For \(\ket{\Phi^+}\): \(\rho_A = \frac12\mathbb 1\), purity \(\frac12\). The whole is pure, the part is maximally mixed.
\(\rho_W = p\,\ket{\Psi^-}\bra{\Psi^-} + (1-p)\,\mathbb 1/4\) (exercise 4.6.1 of the lecture notes).
The partial transpose over Bob has eigenvalues \((1+p)/4\) (three times) and \((1-3p)/4\). A negative eigenvalue signals entanglement (Peres–Horodecki criterion, exact for two qubits): this requires \(p > 1/3\). The maximum of \(|S|\) is \(2\sqrt2\,p\): between \(1/3\) and \(1/\sqrt2\), the state is entangled without violating CHSH. Note that \(\rho_A = \mathbb 1/2\) for every \(p\): when the global state is mixed, the entropy of the part no longer measures entanglement.
A source produces \(\ket0\) with probability 0.9 and \(\ket1\) with probability 0.1. Compute \(\mathrm{Tr}\rho^2\).
\(\rho_{AB} = \frac12(\ket{01}\bra{01} - \ket{01}\bra{10} - \ket{10}\bra{01} + \ket{10}\bra{10})\). The cross terms vanish under \(\mathrm{Tr}_B\) because \(\braket{1|0} = 0\); what remains is \(\rho_A = \frac12(\ket0\bra0 + \ket1\bra1) = \mathbb 1/2\), zero Bloch vector, purity \(1/2\). By symmetry, \(\rho_B = \rho_A\). Any measurement by Alice alone gives 50/50, in any basis.
The lecture notes state that Schrödinger’s cats are “instantaneously” measured by their environment. Decoherence is not instantaneous: it has a characteristic time, extremely short for a macroscopic object, but measurable for mesoscopic systems. It is this time that one tries to lengthen in a quantum computer.
A given density operator does not say how the state was prepared. An equal mixture of \(\ket{z+}\) and \(\ket{z-}\) and an equal mixture of \(\ket{x+}\) and \(\ket{x-}\) both give \(\rho=\tfrac12\mathbb 1\). If you are handed a qubit in this state, no measurement reveals the recipe: \(\rho\) describes what is known, not the history of the system.
where the \(\lambda_i\) are the eigenvalues of \(\rho\). \(S = 0\) for a pure state, \(S = \log_2 d\) for the maximally mixed state in dimension \(d\). For a pure global state, \(S(\rho_A) = S(\rho_B)\) is the entanglement entropy: zero if and only if the state is separable, 1 bit for a Bell state.
Examples from the lecture notes: \(S = 0.81\) bit for the mixture \((0.75, 0.25)\), \(S = 0.47\) bit for \((0.9, 0.1)\). For \(\cos\theta\ket{00} + \sin\theta\ket{11}\), \(S(\theta) = -\cos^2\theta\log_2\cos^2\theta - \sin^2\theta\log_2\sin^2\theta\): vary θ in lab 4.1.
For \(\ket{B_{00}} = \frac{1}{\sqrt2}(\ket{00} + \ket{11})\), compute \(S(\rho_A)\) in bits.
A source emits photon pairs in \(\ket\phi = \sqrt{0.7}\,\ket{HV} + \sqrt{0.3}\,\ket{VH}\). Compute the entanglement entropy \(S(\rho_A)\) in bits.
For \(\rho_W = p\ket{B_{11}}\bra{B_{11}} + (1-p)\,\mathbb 1/4\), above which value of \(p\) is the state entangled?
In the basis \(\{\ket{00},\ket{01},\ket{10},\ket{11}\}\), \(\rho_W\) has diagonal \(\frac{1-p}{4}, \frac{1+p}{4}, \frac{1+p}{4}, \frac{1-p}{4}\) and two terms \(-p/2\) between \(\ket{01}\) and \(\ket{10}\). Transposition over Bob moves these terms to between \(\ket{00}\) and \(\ket{11}\). The block \(\begin{pmatrix}\frac{1-p}{4}&-\frac p2\\-\frac p2&\frac{1-p}{4}\end{pmatrix}\) has eigenvalues \(\frac{1+p}{4}\) and \(\frac{1-3p}{4}\).
A Hadamard gate is applied to the first qubit of \(\ket{00}\), followed by a CNOT gate (first qubit as control). Which state is obtained? What does the same circuit give starting from \(\ket{01}\), \(\ket{10}\), \(\ket{11}\)?
\(H\otimes\mathbb 1\ket{00} = \frac{1}{\sqrt2}(\ket{00} + \ket{10})\), then CNOT gives \(\frac{1}{\sqrt2}(\ket{00} + \ket{11}) = \ket{B_{00}}\). In general, the circuit maps \(\ket{xy}\) to \(\ket{B_{xy}}\): \(\ket{01}\to\ket{B_{01}}\), \(\ket{10}\to\ket{B_{10}}\), \(\ket{11}\to\ket{B_{11}}\). Run backwards, it performs the Bell measurement used in teleportation.
Alice holds \(\ket\varphi_1 = \alpha\ket0 + \beta\ket1\) and shares \(\ket{B_{00}}_{23}\) with Bob. Rewrite \(\ket\varphi_1\otimes\ket{B_{00}}_{23}\) in the Bell basis of qubits 1 and 2, then give Bob’s correction for each result.
Each result has probability 1/4. Bob applies \(\mathbb 1\), \(X\), \(Z\) or \(ZX\) (up to a global sign) according to the two bits he receives. Before receiving these bits, Bob’s state is \(\mathbb 1/2\): it contains no information about \(\alpha, \beta\).
Clarification: the lecture notes say that Bob obtains a “perfect copy”. It is a transfer, not a copy: Alice’s state is destroyed by her measurement, as the no-cloning theorem requires. And the transfer goes no faster than the two classical bits.
The 1.07 million secret bits of the Stellenbosch–Jinan-1 link were produced during a pass whose reception window lasts about 6 minutes. Assuming a uniform rate over the whole window (rough estimate), how many milliseconds does it take to produce a 256-bit key?
Mean rate: \(1.07\times10^6/360 \approx 2.97\times10^3\) bit/s, so \(t = 256/2970 \approx 0.086\) s, i.e. 86 ms. One pass would yield about 4,180 keys of 256 bits.
Comparison with BB84 (lab 4.3): sifting keeps only half of the detected photons, so, with two equiprobable bases, about 512 detections give 256 sifted bits on average, before error correction and privacy amplification, which consume more. The 1.07 million total is a count of final-key bits, after those steps. The real rate varies during the pass (distance, elevation): the computed value is an order of magnitude.
Analogy: “among the Yoruba (the ibeji) as among the Bamileke, twins are linked beyond distance: what touches one concerns the other”, for an entangled pair. Which assessment is correct?
A quantum key or a post-quantum algorithm only protects what is entrusted to it. An adversary can copy communications encrypted with RSA or elliptic curves today and decrypt them later, if a sufficiently powerful quantum computer becomes available (“harvest now, decrypt later”). The risk concerns data that must stay secret for a long time: medical records, civil registers, land titles, mining data, state secrets. A software answer already exists: the NIST post-quantum cryptography standards (August 2024: FIPS 203 for key establishment, FIPS 204 and 205 for signatures), which require no quantum hardware.
The sovereignty question therefore becomes concrete: who holds the keys, where is the data hosted, who decides the migration schedule, and with what local training?
NIST, “NIST Releases First 3 Finalized Post-Quantum Encryption Standards”, August 2024 — nist.govAn administration is preparing its migration to post-quantum cryptography. Which data should come first, against delayed decryption?
A hospital is considering buying a quantum key distribution (QKD) link to “secure its data”. Which answer is most accurate?
Alice and Bob share a Bell pair and are far apart. What does Bob alone see, whatever Alice does? Discuss in pairs before answering.
Two envelopes hold a red slip and a blue slip; opening one reveals the other. Is this entanglement? Discuss in pairs before answering.
Alice and Bob share the singlet \(\ket{\Psi^-}=(\ket{01}-\ket{10})/\sqrt2\). Alice measures her qubit along \(z\) and finds \(+1\), sending nothing to Bob. Can Bob detect locally that she has measured? Discuss in pairs before answering.
Choose one analogy from this chapter. With the person’s consent, who may be an elder, a practitioner, a craftsperson or a musician, ask: (1) how they present this notion, in what language and with what words; (2) under what conditions this knowledge is passed on; (3) what, in their view, does not translate into physics. Write down the words in the local language, return your file to the person, then present both systems, each coherent by its own criteria, without concluding that one proves the other.
Main ideas.
Formulas.
Pitfalls. Confusing the tensor product (a vector of dimension \(d_Ad_B\)) with the outer product (an operator); believing entanglement sends a signal (\(\rho_B\) does not change); confusing classical correlation with entanglement (pre-existing gloves always satisfy \(|S|\le2\)); believing teleportation moves matter or copies the state (Alice’s measurement destroys it, and 2 classical bits are needed).
| Term | Terme français | Definition |
|---|---|---|
| Bell states | États de Bell | Basis of four maximally entangled two-qubit states. |
| Bell inequalities | Inégalités de Bell | Bounds set by local realism: \(|S|\le2\) for CHSH, \(2\sqrt2\) in quantum theory. |
| Entanglement | Intrication | Non-factorisable state: \(\ket{\psi_{AB}}\neq\ket{\psi_A}\otimes\ket{\psi_B}\). |
| Density matrix | Matrice densité | Density operator \(\rho\ge0\), \(\mathrm{Tr}\rho=1\); pure states and mixtures. |
| Tensor product | Produit tensoriel | Composite space \(\mathcal H_A\otimes\mathcal H_B\) of dimension \(d_Ad_B\). |
| Quantum teleportation | Téléportation quantique | Transfer of a state using entanglement and 2 classical bits, with no transport of matter. |
Some quantum key distribution (QKD) protocols rely on entanglement; others, such as BB84, do not. In October 2024, stations in China and Stellenbosch (South Africa), 12,900 km apart, shared a key via the Jinan-1 satellite, which uses BB84 without entangled photons: up to 1.07 million secret bits in a single pass. QKD establishes a secret key under the protocol’s assumptions and with an authenticated classical channel; message confidentiality also depends on the encryption and the equipment.
Stellenbosch University, 19 March 2025 — su.ac.za; Nature Africa, 6 May 2025The Chinese microsatellite Jinan-1, launched in 2022, distributed quantum keys in real time to mobile ground stations of about 100 kg. It enabled one-time-pad encrypted communication between Beijing and Stellenbosch (South Africa), 12,900 km apart. The satellite emits about \(2.5\times10^8\) photons per second and produces up to 1 Mbit of secure key per pass. It acts as a trusted relay: it knows the keys. This is not end-to-end entanglement.
Li et al., Nature, 19 March 2025; press release of the Chinese Academy of SciencesEagle-1, the first European satellite quantum key distribution system (SES, ESA, European Commission), has not yet been launched. Announcements range from late 2026 to late 2027.
ESA; European Commission (EuroQCI)On 13 August 2024, NIST published three standards: FIPS 203 (ML-KEM), FIPS 204 (ML-DSA) and FIPS 205 (SLH-DSA). In March 2025, it selected HQC, based on error-correcting codes, as a backup mechanism. These are classical algorithms, which run on today’s computers and resist known quantum attacks. QKD, by contrast, is physical and relies on single photons.
NIST, csrc.nist.gov and nist.gov (11 March 2025)In 2025, C. Gidney (Google) estimated that a machine with fewer than a million noisy physical qubits could factor a 2,048-bit RSA integer in less than a week. These are resource estimates: no current machine comes close. But a message encrypted today can be recorded and decrypted later. Hence the migration to post-quantum standards.
arXiv:2505.15917 (May 2025)