Quantum money with nearly optimal error tolerance

We present a family of quantum money schemes with classical verification which display a number of benefits over previous proposals. Our schemes are based on hidden matching quantum retrieval games and they tolerate noise up to $23\%$, which we conjecture reaches $25\%$ asymptotically as the dimension of the underlying hidden matching states is increased. Furthermore, we prove that $25\%$ is the maximum tolerable noise for a wide class of quantum money schemes with classical verification, meaning our schemes are almost optimally noise tolerant. We use methods in semidefinite programming to prove security in a substantially different manner to previous proposals, leading to two main advantages: first, coin verification involves only a constant number of states (with respect to coin size), thereby allowing for smaller coins; second, the reusability of coins within our scheme grows linearly with the size of the coin, which is known to be optimal. Last, we suggest methods by which the coins in our protocol could be implemented using weak coherent states and verified using existing experimental techniques, even in the presence of detector inefficiencies.

Figure 1

Maximal pairwise disjoint set of matchings for (a) $n=4$, (b) $n=6$, and (c) $n=8$. Color is used to represent each matching within the maximal pairwise disjoint set.

Figure 2

Schematic illustration of the Bank algorithm for $n=8$. The bank selects $q$ eight-bit strings and initializes the $q$-bit register $r$ to the zero string. The bank creates the corresponding hidden matching states and sends these, together with $r$, to the holder of the coin.

Figure 3

Schematic showing the verification algorithm. The verifier selects a sample $\{{\rho }_{x_1},{\rho }_{x_4},...\}$ of the states contained within the coin which have an $r$ value of 0. He randomly chooses matching measurements and applies them to get classical measurement outcomes which he sends to the bank, together with the index of the state and the matching chosen. The bank checks these against its secret strings, as well as checking $s<T$. Finally, the bank declares an output based on the number of incorrect outcomes.

Figure 4

Representation of the states within the quantum coins sent to the verifiers. The first block on the far left represents all states for which the adversary set $r=1$ for ${\mathrm{Ver}}_1$, and $r=0$ for ${\mathrm{Ver}}_2$. The adversary knows that ${\mathrm{Ver}}_1$ cannot select these states for testing, and so is able to forward on the perfect states to ${\mathrm{Ver}}_2$. The second block of states represents the same, but with the roles of the verifiers reversed. The “Aux. Ver” states in the diagram are the ones that we assume are known to the adversary via auxiliary verifications. The remaining states in white are the ones we consider below—those states for which the $r$ register is zero for both verifiers, and which have not been used in auxiliary verifications.

Figure 5

Plot showing the theoretical bound on protocol noise tolerance (dotted line) and the noise tolerance achieved by the protocols in Sec. 2 (bold line) as the dimension of the underlying systems increase.