Many computer scientists and physicists believe that if we could build a quantum computer, we could use it to calculate things that would be intractable with classical computers. 2

Qubits have another strange property: unlike classical bits, they cannot be copied. This is the content of the quantum no-cloning theorem, which says there is no such thing as a perfect quantum copy machine that can copy any quantum state you feed it. (See Figure 1 for the proof in the single qubit case.) There are also limits on how closely you can approximate a quantum copy machine. 7 The no-cloning theorem allows for cryptographic protocols that go beyond the abilities of classical computers. The best known example is quantum key distribution, 4 which allows two parties to communicate privately, using a quantum channel and an authenticated (public) classical channel.

Quantum Money

The no-cloning theorem means we should not think of qubits the same way we think about bits. One might imagine using a handful of qubits as a form of money. A mint could produce some qubits using some process known only to it, and anyone else, given just those qubits, could not copy them by any means without further information. The no-cloning theorem does not immediately imply secure quantum money is possible; it only says that machines that can copy all quantum states are impossible, and a counterfeiter would be content with a machine that only copied quantum states that represented valid quantum money. A counterfeiter could also try to obtain additional information about the quantum money state by using the algorithm that a merchant would use to verify quantum money. By examining concrete schemes for quantum money, we will see how these kinds of attacks can be avoided.

We distinguish two broad categories of quantum money.

In the simpler version, a mint would produce a quantum bill consisting of some number of qubits. Anyone could store the quantum bill and move it around, maybe even trading it for something else. Whenever someone wants to verify the quantum

the no-cloning
theorem gives us
hope that quantum
information could
be used as
the basis of a better
kind of money.

bill is valid (for example, a merchant who is offered a quantum bill as payment), he or she sends the qubits to the mint and the mint checks that they are still in the correct state using some secret process. In this type of scheme, no one other than the mint knows how to verify the money. We call this private-key quantum money because the key—that is, the information needed to verify the money—is private to the mint.

The other type of quantum money is public-key quantum money. As before, a mint can produce a quantum state and anyone can move it or spend it. Anyone should be able to verify the money themselves without communicating with the mint. Public-key money, if it could be realized, would be the ideal money we discussed earlier.

In the first quantum cryptography paper ever written, 26 Stephen Wiesner described a way to implement private-key quantum money in a provably secure manner. (He wrote the paper in 1969, but it was not published until 1983.) In Wiesner’s scheme, each quantum bill is a unique random quantum state,b which the mint labels with a serial number. The mint keeps track of the state that corresponds to the serial number of each quantum bill and it can use its knowledge of the state to verify the money.

In 1982, Bennett et al. made the first attempt at public-key quantum money. 5 Their scheme only allowed a piece of money to be spent once (they called their quantum states subway tokens, not bills). In hindsight, their scheme is insecure for two different reasons: first, it is based on an insecure protocol for 1-2 oblivious transfer, and second, it can be broken by anyone who can run Shor’s algorithm23, 24 to factor large numbers. (In the early days of quantum cryptography, there was no reason to suspect either of these weaknesses. Shor’s algorithm23 and the general attack14 on oblivious transfer were not known until more than a decade later.)

Surprisingly, the next paper about quantum money did not appear until 2003 when Tokunaga et al. 25 attempted to modify Wiesner’s scheme to prevent the mint from b In fact, this is the random state later used in the BB84 protocol4 for quantum key distribution.