Wiesner’s Epiphany: The Birth of Quantum Money

In the late sixties, an upcoming Columbia graduate student named Stephan Wiesner came to a startling realization: if used just right, the laws of quantum mechanics allow creating a new form of money. Money that is impossible to forge.

In doing so, Wiesner planted the seeds that would grow into a cutting-edge and highly active field of research called uncloneable cryptography. And within it, the fascinating world of quantum money.

This series traces the notion of quantum money from Wiesner's original epiphany through half a century of ensuing research that yields powerful new results to this very day.

But the first step is to understand Wiesner's original epiphany—which is precisely what we will do in this post.

Wiesner States and Uncertainty

Most physics fans have heard of the Heisenberg uncertainty principle in one form or another, usually explained using complicated physical terms like position, momentum, and entropic relations. The uncertainty principle is actually much more general, and relies on an abstract property called mutual unbiasedness. The famous (and historically, first) position-momentum version is the most famous, but far from being the simplest. In modern terms, we can reframe Wiesner’s observation as isolating the simplest possible uncertainty relation. These relation applies to what we now call Wiesner states. These are, in a sense, the “simplest” states that admit sufficient structure to admit quantum phenomena.

In conjugate coding, we only deal with one qubit at a time (we will deal with many qubits, but all of them are created independently and identically), and this qubit is in one of four states. For visual simplicity, we will denote these for states as |→⟩, |↑⟩, |↗⟩ and |↘⟩ (Modern texts often replace these with |0⟩, |1⟩, |+⟩, and |−⟩ (resp.), and for good reasons.)

These four states are the basic units of what we now call Wiesner states. A general Wiesner state is just a string of many (not necessarily identical) qubits of this form. For example, if we have three qubits whose states are |→⟩, |↑⟩, and |→⟩ respectively, then we have a Wiesner state that we will usually denote as |→↑→⟩.

This is what we call a 3-qubit Wiesner state, and it is clear what an n-qubit Wiesner state should mean.

We can recast the uncertainty of Wiesner states as a game, where I provide you with a uniformly random Wiesner state, and you have to tell me which of the two options is true:

1. The state was either |→⟩ or |↗⟩
2. The state was either |↑⟩ or |↘⟩

Wiesner's first observation was that no strategy can win this game with probability greater than ½ + ½√2 ≈ 85.4%. For now, let us call this number C, and remember that it is a positive number strictly smaller than 1.

The second observation was that sampling a random Wiesner state on n qubits is the same as sampling n Wiesner states on one qubit, and then stringing them together. So winning the game for an n qubit Wiesner state is the same as winning the one qubit game n times in a row, which has probability Cⁿ. In other words, the uncertainty between Wiesner states increases exponentially with n.

But there is a caveat: it is highly non-trivial to prove that these two are actually the same. The ability of the player to observe all qubits together shouldn’t help them, but it is not obvious at all that it doesn’t (and the quirkiness of quantum mechanics doesn’t make us any more confident). Indeed, it took several decades before formal proofs appeared, which cemented Wiesner’s observation as correct.

Measuring a Wiesner State

Quantum measurements are complicated, but in the context of Wiesner states, a very useful family of measurements can be described by straightforward rules.

We start with the one-qubit case. The first thing we do is to choose a measurement basis out of two options: computational or conjugate.

A computational measurement measures whether the qubit is |→⟩ or |↑⟩. If we perform a computational measurement on the Wiesner state |→⟩ (resp. |↑⟩), the result will be → (resp. ↑). But what happens if we measure |↗⟩?

This is where our choice of notation shines: that the arrow ↗ bisects the angle between → and ↑ is not a coincidence, it signifies the fact that, in a very physical sense, the state |↗⟩ is "halfway" from |→⟩ to |↑⟩. The operational meaning is that the measurement will output either ↑ or → with identical probability.

But here the weirdness of quantum theory kicks in: this is not just a measurement error, the state becomes (or more colloquially: collapses to) the outcome of the measurement. In particular, there is no way to distinguish measuring |→⟩ from measuring |↗⟩ and happening to get the result →. As far as our measurement cares, it was always |→⟩.

Applying a computational measurement to |↘⟩ yields identical results, which is also something to keep in mind: computational measurements cannot distinguish |↗⟩ from |↘⟩.

Conjugate measurements work identically, but with the roles of |→⟩ and |↑⟩ replaced with the roles of |↗⟩ and |↘⟩.

Notice what happens here: if measuring a state in one of the types of measurement has a certain outcome, then the outcome of applying the other measurement is completely random. A physicist would say that these two types of measurement are mutually unbiased, and this is the property from which we derive the uncertainty. Through this lens, Heisenberg's original uncertainty principle is just the statement that a position measurement and a momentum measurement are mutually unbiased.

In a Wiesner measurement of a n qubit state, we measure each qubit independently, using either a computational or a conjugate measurement. This means that there are 2^n possible measurements. Since each measurement corresponds to two possible states of the qubit we are measuring, which is in line with the 4^n possible Wiesner states.

In this post and the next, we will only use Wiesner measurements. However, we do not assume that adversaries are limited in the same way.

(This holds a thick clue to where this weird ½ + ½√2 comes from. Consider the following strategy for the one-qubit Wiesner uncertainty game: measure in the computational basis, output the result. If the state is |→⟩ or |↑⟩, you win with certainty. Otherwise, you win with probability one-half. So the total winning probability is 75%. We can't do better with these measurements, exactly because a computational measurement tells us nothing if the state is conjugate. It stands to reason that, due to the symmetry of the problem, the "best" measurement will lie somewhere "in between". Now, the angle between |→⟩ and |↗⟩ is 45 degrees, or π/4, so landing halfway between them requires a rotation of π/8, and it just so happens that cos²(π/8) = ½ + ½√2! This is far from a coincidence. However, converting this intuition to a rigorous argument and extending it to multiple qubits took more than thirty years!)

From Uncertainty to Uncloneability

Even today, the interplay between uncertainty and uncloneability is poorly understood. However, it was worked out for Wiesner states.

If I can make many copies of a one-qubit Wiesner state, I can determine what state it is quite easily. Say I perform a computational measurement on ten copies of the state. If all measurements output ↑ then the probability that the state is not |↑⟩ is very small. I'll leave it to the reader to extend this to a general strategy whose success probability drops sharply with the number of available copies.

Hence, the ability to create arbitrarily many perfect copies contradicts the uncertainty principle. In other words: uncertainty implies uncloneability.

That's hardly enough, but it is a start.

The full statement we need is that as n increases, the probability of transforming a Wiesner state into two states, such that both have any significant overlap with the original Wiesner state, is impossible. This is the strong form of no-cloning that Wiesner noticed.

Conjugate Coding and Money

The last observation of the day is that uncertainty implies a strong asymmetry between the creator and the holder of a Wiesner state (assuming they are separate entities). The creator, given the state back, can verify that it is indeed the correct state. The holder, on the other hand, cannot create two copies that will pass this verification. A state that can be verified… but cannot be cloned… a quantum bill!

The leap from here to quantum money is short: to mint a new bill, the bank samples a random serial number r, and a random Wiesner state |w⟩, where w is a string of arrows uniformly and independently sampled from {→, ↑, ↗, ↘}. The quantum bill is the tuple (r, |w⟩), and the bank keeps a private record (r, w). To verify the banknote (r, ρ), the bank looks up the matching w, and performs the appropriate measurement on ρ.

Next Posts

Is this money secure? The arguments above seem to indicate it, but they don't take one thing into account: the bank! The user's ability to ask the bank to verify notes for them has to considered, and when we do, we find that security is not as obvious as it seems. And that shall be the topic of the next post.

You probably wondered how practical it is to visit the bank to validate money. This is a very good question, and this property is what separates secret key quantum money (like Wiesner's scheme) from public key quantum money, which will be the topic of most of this series.