cutting the string it is made out of) and then draw it, we might end up with a different diagram. But we would still like to call it the same knot. So the question arises: which pictures represent the same knot? The three modifications to a knot diagram shown in Figure 5 are called the Reidemeister moves. It can easily be seen that by applying these moves you only move between topologically equivalent knots. It is also true (but more difficult to see) that any two diagrams representing the same knot can be mapped into one another using these moves.

There is no known good algorithm to determine whether two knot diagrams represent the same knot; it has only recently been discovered that knot equivalence is decidable. 13 But sometimes there is a way to tell that two diagrams do not represent the same knot; by using a knot invariant. A knot invariant is a property of a knot that is the same for all diagrams representing the same knot. If you can find a knot invariant that takes different values for the two diagrams in question, then you can be sure they represent different knots. (The converse of this is not generally true—there can be two different knots that share the same value for a particular knot invariant.) One of the first knot invariants to be discovered is called the Alexander polynomial—any knot has an associated Alexander polynomial, and its coefficients are integers that can be efficiently calculated from any diagram of that knot.

To make quantum money from knots, the set S in the general collision-free scheme is taken to be the set of knot diagrams, and label f associated with each diagram is its Alexander polynomial. Applying a sequence of random Reidemeister moves randomizes among knots with the same diagram, allowing the measurement that verifies the quantum money states. So the mint prepares the superposition over all diagrams and measures the Alexander polynomial’s coefficients to make a quantum bill, and a merchant measures the coefficients and verifies the superposition is invariant under the Reidemeister moves.

(The actual scheme is somewhat more complicated because knot diagrams are inconvenient to work with—see Farhi et al. 11 for the technical details.)

While no one has proven that knot money is secure, attempts to break it seem to run into knot theory problems that have no known practical solutions.

What Does the Future hold for
Quantum Money?

Public-key quantum money is one of few quantum protocols that does something that is truly impossible classically, even under cryptographic assumptions. QKD can be used to encrypt information between two parties that did not coordinate keys in advance, but under reasonable security assumptions, lattice based cryptography can perform the same feat. 4, 21 Assuming SHA1 is a pseudo random function, one can use it to implement strong coin flipping, 8, 17 and encrypted communication channels enable fast Byzantine agreement. 3, 12 However, no cryptographic assumption enables a digital analog of cash, as any string of bits that would represent a bill can always be copied.

The idea of some kind of quantum object that only one special entity can produce may have applications beyond being used as money. For example, software companies would like to be able to produce software programs that anyone can use but that no one can copy. Whether this is possible for any useful type of software remains to be seen.

Will a future government replace its currency with quantum money? Maybe. You could use it online to purchase things without transaction fees and without oversight from any third party. You could download your quantum money onto your qPhone (not yet trademarked) and use it to buy things from quantum vending machines. With the advent of quantum money, we hope everybody will like spending money a little bit more.

 

References

1. aaronson, s. Quantum copy-protection and quantum money. In Annual IEEE Conference on Computational Complexity (2009), 229–242.

2. bacon, D. and van Dam, W. recent progress in quantum algorithms. Commun. ACM 53 (feb. 2010), 84–93.

3. ben-or, m. and hassidim, a. fast quantum byzantine agreement. In STOC (2005), 481–485.

4. bennett, C.h. and brassard, g. Quantum cryptography: public key distribution and coin tossing. In Proceedings of IEEE International Conference on Computers Systems and Signal Processing (bangalore, India, 1984), 175–179.

5. bennett, C.h., brassard, g., breidbart, s. and Wiesner,
s. Quantum cryptography, or unforgeable subway
tokens. In Advances in Cryptology—Proceedings of
Crypto (1983), volume 82, 267–275.

 

Scott Aaronson ( [e-mail]) is an associate professor, CsaIl, mIt, Cambridge, ma.

Edward Farhi ( [e-mail]) is the Cecil and Ida green professor of physics, and director of the Center for theoretical physics, mIt, Cambridge, ma. David Gosset ( [e-mail]) is a postdoctorate fellow in the Department of Combinatorics and optimization and the Institute for Quantum Computing, university of Waterloo, Canada. Avinatan hassidim ( [e-mail]) is an assistant professor in the Department of Computer science, bar Ilan university, and works at google Israel. his research is supported by a grant from the german-Israeli foundation (gIf) for scientific research and Development under contract number 1-2322-407.7/2011. Jonathan Kelner ( [e-mail]) is an assistant professor of applied mathematics, and a member of CsaIl, mIt, Cambridge, ma. Andrew Lutomirski ( [e-mail]) is co-founder of ama Capital management llC, palo alto, Ca.