Simple Algorithm
Quantum Computing · Rydberg State · 26 min

Quantum Money & Unclonable Cryptography

From Wiesner's banknotes to modern unclonable primitives.

Around 1970, Stephen Wiesner proposed banknotes that physics, not paper, makes unforgeable. His paper went unpublished until 1983, by which time it had also seeded quantum key distribution. Today quantum money is the gateway to a whole field: cryptography built on the impossibility of copying.

What you’ll learn

  • Define private-key quantum money, its completeness and soundness conditions, and Wiesner's construction.
  • Prove that simple counterfeiting of Wiesner money succeeds with probability exactly (3/4)n(3/4)^n, via a semidefinite program and its dual.
  • Explain adaptive attacks that exploit the bank's verification, and how a bank must respond.
  • Explain why public-key money needs computational assumptions, and analyze the Aaronson–Christiano hidden-subspace verifier.
  • Survey unclonable cryptographic primitives and their main open problems.

Wiesner's banknotes

The bank mints a note with a public serial number ss and nn qubits, each prepared independently and uniformly in one of the four BB84 states ∣0⟩,∣1⟩,∣+⟩,∣−⟩\ket0,\ket1,\ket+,\ket-. It records the classical description (basis and bit of every qubit) under ss in a secret database. To verify, the bank measures each qubit in its recorded basis and accepts if every bit matches. An honest note always passes.

The counterfeiter seems stuck: the four states include non-orthogonal pairs, so by no-cloning no device copies them all, and measuring in the wrong basis randomizes the bit. But "cannot copy perfectly" is not a number. How well can she do?

Attack on each qubitBoth notes passFor n=50n=50
Keep the original; make the copy ∣0⟩\ket01/21/2≈9×10−16\approx9\times10^{-16}
Measure in ZZ, prepare two copies of the result5/85/8≈6×10−11\approx6\times10^{-11}
Universal (Bužek–Hillery) cloner2/32/3≈2×10−9\approx2\times10^{-9}
Optimal attack3/43/4≈6×10−7\approx6\times10^{-7}
Probabilities multiply across independent qubits. For the universal cloner the relevant figure is its global fidelity 2/32/3, not its single-copy fidelity 5/65/6. The optimal value, and the fact that no entangled attack on all nn qubits beats (3/4)n(3/4)^n, is the theorem of the next step.
Predict before you look

The counterfeiter measures one qubit of the note in the ZZ basis and prepares two qubits in the state she saw. What is the probability that both qubits pass the bank's check?

Show the answer

0.625

With probability ½ the qubit is ∣0⟩\ket0 or ∣1⟩\ket1: she reads it perfectly and both copies pass. With probability ½ it is ∣±⟩\ket\pm: her outcome is random, and each copy independently passes the XX check with probability ½, so both pass with probability ¼. Total: 12⋅1+12⋅14=58\tfrac12\cdot1+\tfrac12\cdot\tfrac14=\tfrac58.

The optimal counterfeiter: exactly 3/4 per qubit

DerivationProof by semidefinite programming
  1. p⋆=max⁡Φ CPTP 14∑s∈{0,1,+,−}⟨ss∣ Φ(∣s⟩ ⁣⟨s∣) ∣ss⟩p^\star=\max_{\Phi\ \mathrm{CPTP}}\ \frac14\sum_{s\in\{0,1,+,-\}}\bra{ss}\,\Phi(\dyad s)\,\ket{ss}

    One qubit first. The counterfeiter applies a channel Φ\Phi from one qubit to two; success means both outputs pass the test ∣s⟩ ⁣⟨s∣\dyad s.

  2. p⋆=max⁡ Tr⁡(QJ)  s.t.  J⪰0,  Tr⁡outJ=I,Q=14∑s∣s⟩ ⁣⟨s∣⊗3p^\star=\max\ \Tr(QJ)\ \ \text{s.t.}\ \ J\succeq0,\ \ \Tr_{\mathrm{out}}J=\id,\qquad Q=\tfrac14\textstyle\sum_s\dyad{s}^{\otimes3}

    Encode Φ\Phi by its Choi matrix J=∑jk∣j⟩ ⁣⟨k∣⊗Φ(∣j⟩ ⁣⟨k∣)J=\sum_{jk}\ketbra{j}{k}\otimes\Phi(\ketbra{j}{k}), so that Φ(ρ)=Tr⁡in[(ρT⊗I)J]\Phi(\rho)=\Tr_{\mathrm{in}}[(\rho^{T}\otimes\id)J]; the BB84 states are real, so sˉ=s\bar s=s. Complete positivity means J⪰0J\succeq0, trace preservation means Tr⁡outJ=I\Tr_{\mathrm{out}}J=\id.

  3. Tr⁡(QJ)≤Tr⁡((Y⊗Iout)J)=Tr⁡(Y Tr⁡outJ)=Tr⁡Ywhenever Y⊗Iout⪰Q\Tr(QJ)\le\Tr\big((Y\otimes\id_{\mathrm{out}})J\big)=\Tr\big(Y\,\Tr_{\mathrm{out}}J\big)=\Tr Y\qquad\text{whenever } Y\otimes\id_{\mathrm{out}}\succeq Q

    Weak duality: every such YY certifies an upper bound.

  4. Q=14AA†,A=[∣000⟩,∣111⟩,∣+++⟩,∣−−−⟩],spec⁡(A†A)={32,32,12,12}Q=\tfrac14AA^\dagger,\quad A=\big[\ket{000},\ket{111},\ket{{+}{+}{+}},\ket{{-}{-}{-}}\big],\qquad \operatorname{spec}(A^\dagger A)=\big\{\tfrac32,\tfrac32,\tfrac12,\tfrac12\big\}

    The nonzero spectrum of AA†AA^\dagger is that of the Gram matrix Gst=⟨s∣t⟩3G_{st}=\braket{s|t}^3, whose off-diagonal entries are 00 or ±122\pm\tfrac{1}{2\sqrt2}. It equals I+122M\id+\tfrac{1}{2\sqrt2}M, where MM has eigenvalues ±2\pm\sqrt2. Hence ∥Q∥=38\norm{Q}=\tfrac38.

  5. Y=38 I ⟹ p⋆≤Tr⁡Y=34Y=\tfrac38\,\id\ \Longrightarrow\ p^\star\le\Tr Y=\tfrac34

    A feasible dual point gives the upper bound.

  6. J⋆=112(∣f0⟩ ⁣⟨f0∣+∣f1⟩ ⁣⟨f1∣),∣f0⟩=3∣000⟩+∣011⟩+∣101⟩+∣110⟩,∣f1⟩=3∣111⟩+∣100⟩+∣010⟩+∣001⟩J^\star=\tfrac{1}{12}\big(\dyad{f_0}+\dyad{f_1}\big),\quad \ket{f_0}=3\ket{000}+\ket{011}+\ket{101}+\ket{110},\quad \ket{f_1}=3\ket{111}+\ket{100}+\ket{010}+\ket{001}

    (Input qubit first.) Both vectors lie in the 38\tfrac38-eigenspace of QQ, and Tr⁡outJ⋆=I\Tr_{\mathrm{out}}J^\star=\id. So Tr⁡(QJ⋆)=38Tr⁡J⋆=34\Tr(QJ^\star)=\tfrac38\Tr J^\star=\tfrac34: the bound is attained. This attack passes with probability exactly 34\tfrac34 on each of the four states.

  7. pn⋆=(34)np^\star_n=\Big(\tfrac34\Big)^n

    For nn qubits the objective is Q⊗nQ^{\otimes n}. The dual point Y⊗nY^{\otimes n} stays feasible because ∥Q⊗n∥=(38)n\norm{Q^{\otimes n}}=(\tfrac38)^n, and its value is (34)n(\tfrac34)^n; the product attack J⋆⊗nJ^{\star\otimes n} attains it. Entangling the qubits cannot help. ■\blacksquare

Think first Think first: if the bank drew each qubit from all six states ∣0⟩,∣1⟩,∣±⟩,∣±i⟩\ket0,\ket1,\ket\pm,\ket{\pm i}, would the optimal per-qubit counterfeiting probability go up or down?

Down, to 2/32/3. The success probability is linear in sˉ⊗s⊗s\bar s\otimes s\otimes s, a third moment, and the six states form a 3-design, so the average equals the Haar average. Against a Haar-random state the best attack is the optimal universal cloner, with global fidelity d[1]/d[2]=2/3d[1]/d[2]=2/3; and the same dual certificate, now with ∥Q6∥=13\norm{Q_6}=\tfrac13, proves nothing does better.

Check your understanding

Why does the bound (3/4)n(3/4)^n hold even against counterfeiters who apply one big entangling operation to all nn qubits?

  1. The bank measures the qubits one at a time, which destroys any entanglement
  2. The dual certificate Y⊗nY^{\otimes n} remains feasible for the nn-qubit program, whose objective is Q⊗nQ^{\otimes n}
  3. Entangling operations cannot be applied to banknotes in practice
  4. It does not: entangled attacks achieve (5/6)n(5/6)^n
Show the answer

B. The dual certificate Y⊗nY^{\otimes n} remains feasible for the nn-qubit program, whose objective is Q⊗nQ^{\otimes n}

The nn-qubit SDP optimizes over all channels, entangling ones included. Since Y⊗n⊗I⪰Q⊗nY^{\otimes n}\otimes\id\succeq Q^{\otimes n}, its value (3/4)n(3/4)^n bounds every attack: here the SDP value is multiplicative.

When the bank talks back: adaptive attacks

A simple counterfeiter never talks to the bank again. Real banks verify notes on demand, and that changes everything. If the bank returns a note after a successful verification, rather than issuing a fresh one, every verification is a measurement the attacker can exploit, and Wiesner's scheme can be broken (Lutomirski 2010; Nagaj, Sattath, Brodutch & Unruh 2016).

Public-key money and hidden subspaces

In Wiesner's scheme only the bank can verify. Public-key money lets anyone verify with a public procedure, while only the mint can create notes. This can never be secure against unbounded adversaries: given the public verification circuit, an exponential-time adversary can compute a description of a state it accepts and then prepare that state as often as it likes (Aaronson 2009). Public-key money therefore needs computational assumptions, with no-cloning-style arguments combined with hardness.

DerivationThe verifier is exactly the projector onto the note
  1. H⊗n∣x⟩=2−n/2∑y(−1)x⋅y∣y⟩H^{\otimes n}\ket x=2^{-n/2}\textstyle\sum_{y}(-1)^{x\cdot y}\ket y

    The Hadamard transform over F2n\mathbb F_2^n.

  2. ΠA⊥H⊗n ΠA∣ψ⟩=⟨A∣ψ⟩ ∣A⊥⟩\Pi_{A^\perp}H^{\otimes n}\,\Pi_A\ket\psi=\braket{A|\psi}\,\ket{A^\perp}

    Write ΠA∣ψ⟩=∑x∈Acx∣x⟩\Pi_A\ket\psi=\sum_{x\in A}c_x\ket x. For y∈A⊥y\in A^\perp every sign is +1+1, so each such yy gets amplitude 2−n/2∑xcx=2−n/4⟨A∣ψ⟩2^{-n/2}\sum_x c_x=2^{-n/4}\braket{A|\psi}. The amplitude is the same for all 2n/22^{n/2} values of yy, which makes the result ⟨A∣ψ⟩\braket{A|\psi} times the normalized state ∣A⊥⟩\ket{A^\perp}.

  3. VA≡H⊗n ΠA⊥ H⊗n ΠA=∣A⟩ ⁣⟨A∣V_A\equiv H^{\otimes n}\,\Pi_{A^\perp}\,H^{\otimes n}\,\Pi_A=\dyad{A}

    Because H⊗n∣A⊥⟩=∣A⟩H^{\otimes n}\ket{A^\perp}=\ket A. So the test accepts ∣ψ⟩\ket\psi with probability exactly ∣⟨A∣ψ⟩∣2\abs{\braket{A|\psi}}^2, and a valid note passes undisturbed: two membership queries implement the ideal projective test onto the note.

Security. With the membership tests as black-box oracles, Aaronson and Christiano proved that any counterfeiter who turns one note into two must make exponentially many queries, using an inner-product variant of the quantum adversary method. The hard part is the real world, where the oracles must be replaced by code. Their concrete proposal hid AA in random low-degree polynomials; that instantiation was broken by algebraic attacks, at least in its noise-free form (Pena, Faugère & Perret 2015). Zhandry (2019) later showed that hiding the subspaces with indistinguishability obfuscation yields a secure scheme, assuming post-quantum obfuscation of that kind exists.

Unclonable cryptography

Money is the first of many primitives whose security comes from no-cloning, usually combined with computational assumptions.

PrimitiveGuaranteeStatus (mid-2020s)
Private-key money (Wiesner 1983)Only the bank can mint, and the bank verifiesUnconditionally secure against simple counterfeiting; adaptive security needs care
Public-key money (Aaronson 2009; Aaronson–Christiano 2012)Anyone verifies; only the mint createsCandidates from obfuscation, knots and other structures; a construction from standard assumptions such as LWE is open
Quantum lightning (Zhandry 2019)Even the mint cannot make two notes with the same serial numberCandidates only; open from standard assumptions
Copy-protection (Aaronson 2009)A program state that computes ff but cannot be split into two working copiesImpossible for general functions (Ananth & La Placa 2021); possible for some classes, under strong assumptions or with oracles
Unclonable encryption (Broadbent & Lord 2020)A ciphertext that two parties cannot both decrypt once the key is revealedWeaker "search" security via monogamy-of-entanglement games; the strongest indistinguishability notion is an active research question
Certified deletion (Broadbent & Islam 2020)The receiver can prove that the plaintext was destroyedConstructions exist, some information-theoretically secure
One-shot signatures (Amos, Georgiou, Kiayias & Zhandry 2020)A quantum secret key that can sign exactly one messageConstructed relative to a classical oracle; standard-model constructions are an active topic

Key takeaways

  • Wiesner money: BB84 states with secret bases. Simple counterfeiting succeeds with probability exactly (3/4)n(3/4)^n, certified by a product dual solution of an SDP.
  • Security definitions matter: a bank that hands verified notes back enables adaptive bomb-tester attacks.
  • Public-key money is impossible information-theoretically. Hidden-subspace money verifies with H⊗nΠA⊥H⊗nΠA=∣A⟩ ⁣⟨A∣H^{\otimes n}\Pi_{A^\perp}H^{\otimes n}\Pi_A=\dyad A and is secure relative to oracles; real instantiations hinge on obfuscation.
  • No-cloning underlies a growing family of primitives (lightning, copy-protection, unclonable encryption, certified deletion, one-shot signatures), many still open from standard assumptions.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

What is the optimal success probability of a simple counterfeiting attack on a 30-qubit Wiesner note?

  1. (1/2)30(1/2)^{30}
  2. (5/8)30(5/8)^{30}
  3. (3/4)30(3/4)^{30}
  4. (5/6)30(5/6)^{30}
Show the answer

C. (3/4)30(3/4)^{30}

By the Molina–Vidick–Watrous theorem it is (3/4)30≈1.8×10−4(3/4)^{30}\approx1.8\times10^{-4}, attained by a product attack.

Question 2

Why can't public-key quantum money be secure against computationally unbounded counterfeiters?

  1. No-cloning holds only against efficient adversaries
  2. Public verification necessarily destroys the note
  3. The bank would have to be online for every transaction
  4. From the public verifier, an unbounded adversary can compute a description of an accepted state and prepare it as often as it likes
Show the answer

D. From the public verifier, an unbounded adversary can compute a description of an accepted state and prepare it as often as it likes

The verifier is public, so its accepting subspace can be computed classically (in exponential time). Knowing a state in it, the adversary needs no copying at all. Security must therefore rest on computational hardness.

Question 3

The Aaronson–Christiano verifier applies ΠA\Pi_A, then H⊗nH^{\otimes n}, then ΠA⊥\Pi_{A^\perp}, then H⊗nH^{\otimes n}. For an arbitrary state ∣ψ⟩\ket\psi, the acceptance probability is:

  1. ∥ΠA∣ψ⟩∥2\norm{\Pi_A\ket\psi}^2
  2. ∣⟨A∣ψ⟩∣2\abs{\braket{A|\psi}}^2
  3. ∥ΠA∣ψ⟩∥2⋅∥ΠA⊥H⊗n∣ψ⟩∥2\norm{\Pi_A\ket\psi}^2\cdot\norm{\Pi_{A^\perp}H^{\otimes n}\ket\psi}^2
  4. 1/21/2 for every state supported on AA
Show the answer

B. ∣⟨A∣ψ⟩∣2\abs{\braket{A|\psi}}^2

The composition equals the rank-one projector ∣A⟩ ⁣⟨A∣\dyad A, so the acceptance probability is ∣⟨A∣ψ⟩∣2\abs{\braket{A|\psi}}^2.

Question 4

In the bomb-tester attack on Wiesner money, what role does the bank's verification play?

  1. It is the "bomb": a repeated measurement whose collapses (a Zeno effect) stop the probe from rotating unless the money qubit is unaffected by the CNOT
  2. It supplies fresh copies of the note
  3. It amplifies the probe's rotation
  4. It reveals the bases directly whenever a note fails
Show the answer

A. It is the "bomb": a repeated measurement whose collapses (a Zeno effect) stop the probe from rotating unless the money qubit is unaffected by the CNOT

For ∣0⟩\ket0 or ∣1⟩\ket1 the CNOT entangles probe and note, and each verification collapses the probe back to ∣0⟩\ket0. Only for ∣+⟩\ket+, which the CNOT leaves unchanged, does the rotation accumulate. The attacker learns the state while verification failures stay at probability O(δ)O(\delta).

Further reading

  • S. Wiesner, "Conjugate coding", ACM SIGACT News 15(1), 78 (1983).
  • A. Molina, T. Vidick & J. Watrous, "Optimal counterfeiting attacks and generalizations for Wiesner's quantum money", TQC 2012, LNCS (2013).
  • S. Aaronson, "Quantum copy-protection and quantum money", Proceedings of the 24th IEEE Conference on Computational Complexity (2009).
  • S. Aaronson & P. Christiano, "Quantum money from hidden subspaces", Proceedings of STOC 2012 (2012).
  • D. Nagaj, O. Sattath, A. Brodutch & D. Unruh, "An adaptive attack on Wiesner's quantum money", Quantum Information & Computation 16 (2016).