Communications - August 2012

tracking each individual bill as it is used. They achieved this by requiring that the owner of a bill modify the bill before allowing the bank to verify it. The modification is done in a special way so that valid bills remain valid but are otherwise randomized so that the bank cannot tell them apart. This scheme has the significant disadvantage that upon discovering a single counterfeit bill, the bank is required to immediately invalidate every bill it has ever issued. In our opinion this scheme therefore has limited practical applicability.

The idea of public-key quantum money gained traction in the years that followed. Aaronson proved a “ complexity-theoretic no-cloning theorem,” 1 which showed that even with access to a verifier, a counterfeiter with limited computational resources cannot copy an arbitrary state. Mosca and Stebila proposed18 the idea of a quantum coin as distinct from a quantum bill—each quantum coin of a given denomination would be identical. Using the complexity-theoretic no-cloning theorem they argued it might be possible to implement a quantum coin protocol but they did not give a concrete implementation. Aaronson1 proposed the first concrete scheme for public-key quantum money; however, this scheme was shown to be insecure in Lutomirski et al. 16 In the latter paper, the authors suggested the idea of collision-free quantum money. Unlike quantum coins, each collision-free quantum bill has a serial number and nobody, not even the mint, can produce two bills with the same serial number. This feature can be useful to prevent the mint from printing more money than it says it is printing. The mint posts a list of all serial numbers of every quantum bill ever produced, and we can be sure the mint produced at most one bill for each serial number on the list. In a subsequent paper, Farhi et al. proposed a concrete scheme they believed was both collision free and secure against counterfeiting. 11

Here, we tell you how some of these proposals work.

Wiesner’s Quantum Money Wiesner’s original quantum money scheme26 works as follows. To produce

the resurgence
of interest in
quantum money
is centered
around the idea
of public-key
quantum money.

a quantum bill using n qubits, the mint first chooses n one-qubit states randomly drawn from the set {|Sz = 1ñ, |Sz = −1ñ, |Sx = 1ñ, |Sx = −1ñ}. The mint then assigns that state a classical serial number. A piece of quantum money consists of the n qubit state and its serial number. The mint keeps a list of all serial numbers issued as well as a description of which state corresponds to which serial number. When you pay for something with a quantum bill, the merchant sends the quantum state and its serial number back to the mint for verification. The mint looks up the serial number and retrieves the description of the corresponding quantum state. Then the mint verifies the given state is the state that goes with the attached serial number. This kind of money cannot be forged by someone outside the mint. Since a would-be forger has no knowledge of the basis that each qubit was prepared in, the quantum no-cloning theorem says he or she cannot reliably copy the n qubit quantum state (Figure 2).

The main weakness in Wiesner’s scheme is that the merchant must communicate with the bank to verify each transaction. So this scheme, although theoretically inspiring and provably secure, would not be much more powerful than credit cards. Wiesner’s scheme is a private-key quantum money scheme because the mint must keep a private secret—the complete description of the state—to use for verification.

Challenges in Designing
Public-key Quantum Money

The resurgence of interest in quantum money is centered around the idea of public-key quantum money. As we have discussed, a public-key quantum money scheme would have the following properties. 16

1. The mint can mint it. That is, there is an efficient algorithm to produce the quantum money state.

2. Anyone can verify it without communicating with the mint. That is, there is an efficient measurement anyone can perform that accepts money produced by the mint with high probability and minimal damage.