134
Part Three · C · Complexity and cryptography

Quantum money, certified randomness, secure computation

Around 1970 Stephen Wiesner, a graduate student at Columbia, had the first idea in quantum cryptography: banknotes that cannot be forged, because they carry quantum states that cannot be copied. His paper was rejected and only published in 1983, after it had inspired BB84. Fifty years later, in 2025, a quantum computer accessed over the internet produced random numbers that a classical computer could not have faked, under stated assumptions. Between those two events lies a set of tasks only quantum mechanics can do, and some it provably cannot.

On the plate: you are a counterfeiter.

Wiesner money

The bank prints a serial number and nn qubits, each randomly one of ∣0⟩,∣1⟩,∣+⟩,∣−⟩|0\rangle, |1\rangle, |+\rangle, |-\rangle, and secretly records which. To verify, the bank measures each qubit in its recorded basis. A forger who does not know the bases cannot copy the note, by no-cloning (Chapter 102). The simplest attack measures each qubit in the standard basis and prepares two copies of the result. A qubit that was ∣0⟩|0\rangle or ∣1⟩|1\rangle passes; one that was ∣±⟩|\pm\rangle passes half the time. Each qubit passes with probability 3/4, so a forged note passes with (3/4)n(3/4)^n. Abel Molina, Thomas Vidick and John Watrous proved in 2012 that no attack does better at producing two notes that both pass. Established

Try to forge

Use 8 qubits per note and . The plate runs the measure-and-copy attack against random notes. Wiesner’s scheme has a weakness: only the bank can verify, and if the bank returns notes that fail verification, an attacker can learn the states adaptively. Public-key quantum money, which anyone can verify, needs computational assumptions. Scott Aaronson and Paul Christiano proposed a scheme in 2012, and Mark Zhandry introduced “quantum lightning” in 2019, which even the bank cannot copy. Secure public-key schemes from standard assumptions remain an open goal. Debated

Certified randomness, and what is impossible

In 2025 Minzhao Liu and colleagues at JPMorganChase, Quantinuum and US national laboratories sent challenge circuits to Quantinuum’s 56-qubit H2 trapped-ion computer over the internet. It returned samples within about two seconds each, faster than any known classical simulation. Supercomputers then checked a subset with the cross-entropy test (Chapter 127), certifying 71,313 bits of entropy, which an extractor turns into near-perfect random bits. The guarantee assumes the server’s classical rival is limited in compute, a model the authors call practical security against restricted adversaries. Debated

Some tasks are impossible even quantumly. Bit commitment: lock a bit in a box now and reveal it later, so the receiver cannot learn it early and the sender cannot change it. Dominic Mayers, and independently Hoi-Kwong Lo and Hoi Fung Chau, proved in 1997 that no quantum protocol achieves both: if the receiver learns nothing, the two commitments look identical to the receiver, so the sender can switch between them by a local unitary. Established

What you now have

Wiesner money and its 3/4-per-qubit forgery bound, the case for public-key money and quantum lightning, the 2025 certified-randomness experiment and its assumptions, and the impossibility of unconditional bit commitment.

· · ·

Three questions to carry with you.

Why does each forged qubit pass with probability 3/4?tap
It passes surely in the standard basis, and half the time in the diagonal basis.
What makes randomness “certified”?tap
The samples pass a cross-entropy test faster than any classical simulation could have produced them.
Why is bit commitment impossible?tap
If the receiver’s states for 0 and 1 are identical, the sender can switch between commitments with a local unitary.

And one to work out. With 20 qubits per note, what is the probability that a measure-and-copy forgery passes?

P =

Sources: S. Wiesner, SIGACT News 15, 78 (1983). A. Molina, T. Vidick and J. Watrous, TQC 2012, LNCS 7582, 45 (2013). S. Aaronson and P. Christiano, Proc. 44th ACM STOC, 41 (2012). M. Zhandry, Eurocrypt 2019, 408. D. Mayers, Phys. Rev. Lett. 78, 3414 (1997). H.-K. Lo and H. F. Chau, Phys. Rev. Lett. 78, 3410 (1997). M. Liu et al., Nature 640, 343 (2025). Checked by code: (3/4)²⁰ = 0.00317.

Next · Chapter 135
Noise models, T₁ and T₂, and noise characterization (randomized benchmarking, gate set tomography)

"99.9% fidelity" can hide errors that pile up coherently and ruin a computation.

Turn the page