Quantum money from knots

Edward Farhi, David Gosset, Avinatan Hassidim, Andrew Lutomirski, Peter W. Shor

Introduction

In classical computing, information is inherently copyable, presenting a fundamental challenge for digital currency: the "double-spending" problem. Traditionally, we rely on central authorities like banks to verify transactions. Quantum mechanics offers a physical solution via the no-cloning theorem, which prevents the perfect duplication of an unknown quantum state. While "private-key" quantum money (verifiable only by the issuer) has existed conceptually since 1969, this paper proposes a robust public-key quantum money scheme. This system allows any merchant to verify a bill's authenticity without contacting the mint, using the complex mathematics of knot theory.

The conceptual symbol for quantum money represented as a quantum state.

Methodology: Minting and Verification

The proposed scheme represents unforgeable "bills" as quantum superpositions of equivalent knot diagrams, specifically utilizing "grid diagrams."

Minting

The minting process involves creating a uniform quantum superposition of all possible grid diagrams. The mint then measures a specific knot invariant—the Alexander polynomial. The outcome of this measurement serves as the bill's unique serial number $p$. The resulting quantum state $|\$_{p}\rangle$ is a superposition of all grid diagrams that share that specific polynomial.

Public Verification

To verify a bill $(p, |\$_{p}\rangle)$, a merchant performs two independent checks:

  1. Invariant Check: They compute the Alexander polynomial of the state to ensure it matches the serial number $p$.
  2. Superposition Check: They employ a Quantum Markov Chain based on "grid moves." These are transformations that alter a diagram's appearance without changing the underlying knot. If the state is a genuine uniform superposition of equivalent knots, it remains unchanged (an eigenvector with eigenvalue 1) under this Markov process.

Security and Knot Equivalence

The security of this scheme rests on the computational asymmetry of knot equivalence. While calculating the Alexander polynomial is efficient, determining whether two complex diagrams represent the same knot—or finding the sequence of moves to transform one into the other—is a notoriously difficult problem, even for quantum computers.

Reidemeister moves: fundamental transformations that change a knot diagram while preserving the underlying knot topology.

The paper highlights that this "hardness" makes knots superior to other structures, like graphs. While graph isomorphism is often solvable in practice, knot equivalence remains a robust cryptographic primitive. By using a quantum Markov chain to "mix" diagrams, the verifier confirms the state is a broad superposition without needing to solve the underlying hard problem of knot transformation.

Conclusion and Future Outlook

The authors provide a formal protocol for a public-key quantum money system resistant to known "state restoration" attacks. However, the security remains conjectured, based on the assumption that finding sequences of Reidemeister moves is hard on average. Future research is needed to prove the mixing times of these Markov chains and to explore more complex knot invariants. Practically, the implementation of such a system requires universal quantum computers and a functional quantum internet, technologies currently in early development.

Summary updated

BibTeX
@inproceedings{farhi2012quantum,
  author = {Edward Farhi and David Gosset and Avinatan Hassidim and Andrew Lutomirski and Peter W. Shor},
  title = {{Quantum money from knots}},
  booktitle = {ITCS},
  year = {2012},
  doi = {10.1145/2090236.2090260},
}

Loading related content...

Figure