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
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.
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 ( firstname.lastname@example.org) is an associate
professor, CsaIl, mIt, Cambridge, ma.
Edward Farhi ( email@example.com) is the Cecil and Ida
green professor of physics, and director of the Center for
theoretical physics, mIt, Cambridge, ma.
David Gosset ( firstname.lastname@example.org) is a postdoctorate
fellow in the Department of Combinatorics and
optimization and the Institute for Quantum Computing,
university of Waterloo, Canada.
Avinatan hassidim ( email@example.com) 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 ( firstname.lastname@example.org) is an assistant
professor of applied mathematics, and a member of
CsaIl, mIt, Cambridge, ma.
Andrew Lutomirski ( email@example.com) is co-founder of ama
Capital management llC, palo alto, Ca.