11
$\begingroup$

In his celebrated paper "Conjugate Coding" (written around 1970), Stephen Wiesner proposed a scheme for quantum money that is unconditionally impossible to counterfeit, assuming that the issuing bank has access to a giant table of random numbers and that banknotes can be brought back to the bank for verification. In Wiesner's scheme, each banknote consists of a classical "serial number" $s$, together with a quantum money state $|\psi_s\rangle$ consisting of $n$ unentangled qubits, each one either

$$|0\rangle,\ |1\rangle,\ |+\rangle=(|0\rangle+|1\rangle)/\sqrt{2},\ \text{or}\ |-\rangle=(|0\rangle-|1\rangle)/\sqrt{2}.$$

The bank remembers a classical description of $|\psi_s\rangle$ for every $s$. And therefore, when $|\psi_s\rangle$ is brought back to the bank for verification, the bank can measure each qubit of $|\psi_s\rangle$ in the correct basis (either $\{|0\rangle,|1\rangle\}$ or $\{|+\rangle,|-\rangle\}$), and check that it gets the correct outcomes.

On the other hand, because of the uncertainty relation (or alternatively, the No-Cloning Theorem), it's "intuitively obvious" that, if a counterfeiter who doesn't know the correct bases tries to copy $|\psi_s\rangle$, then the probability that both of the counterfeiter's output states pass the bank's verification test can be at most $c^n$, for some constant $c<1$. Furthermore, this should be true regardless of what strategy the counterfeiter uses, consistent with quantum mechanics (e.g., even if the counterfeiter uses fancy entangled measurements on $|\psi_s\rangle$).

However, while writing a paper about other quantum money schemes, my coauthor and I realized that we'd never seen a rigorous proof of the above claim anywhere or an explicit upper bound on $c$: neither in Wiesner's original paper nor in any later one.

So, has such a proof (with an upper bound on $c$) been published? If not, then can one derive such a proof in a more-or-less straightforward way from (say) approximate versions of the No-Cloning Theorem, or results about the security of the BB84 quantum key distribution scheme?

I should maybe clarify that I'm looking for more than just a reduction from the security of BB84. Rather, I'm looking for an explicit upper bound on the probability of successful counterfeiting (i.e., on $c$)---and ideally, also some understanding of what the optimal counterfeiting strategy looks like. I.e., does the optimal strategy simply measure each qubit of $|\psi_s\rangle$ independently, say on the basis

$$\{ \cos(\pi/8)|0\rangle+\sin(\pi/8)|1\rangle, \sin(\pi/8)|0\rangle-\cos(\pi/8)|1\rangle \}?$$

Or is there an entangled counterfeiting strategy that does better?

Right now, the best counterfeiting strategies that I know are (a) the strategy above, and (b) the strategy that simply measures each qubit in the $\{|0\rangle,|1\rangle\}$ basis and "hopes for the best." Interestingly, both of these strategies turn out to achieve a success probability of $(5/8)$$n$. So, my conjecture of the moment is that $(5/8)$$n$ might be the right answer. In any case, the fact that $5/8$ is a lower bound on c rules out any security argument for Wiesner's scheme that's "too" simple (for example, any argument to the effect that there's nothing nontrivial that a counterfeiter can do, and therefore the right answer is $c=1/2$).

$\endgroup$
  • 4
    $\begingroup$ No, $(5/8)^n$ is not the right answer. $\endgroup$ – Peter Shor Apr 4 '18 at 2:53
13
$\begingroup$

Abel Molina, Thomas Vidick, and I proved that the correct answer is $c=3/4$ in this paper:

A. Molina, T. Vidick, and J. Watrous. Optimal counterfeiting attacks and generalizations for Wiesner's quantum money. Proceedings of the 7th Conference on Theory of Quantum Computation, Communication, and Cryptography, volume 7582 of Lecture Notes in Computer Science, pages 45–64, 2013. (See also arXiv: 1202.4010.)

This assumes the counterfeiter uses what we call a "simple counterfeiting attack," which means a one-shot attempt to transform one copy of a money state into two. (I interpret your question to be about such attacks.)

The attack of Brodutch, Nagaj, Sattath, and Unruh that @Rob referred to (and which is a fantastic result in my opinion) requires the counterfeiter to interact repeatedly with the bank and assumes the bank will provide the counterfeiter with the same money state after each verification.

The paper describes the optimal channel, which is not an entanglement breaking (i.e., measure and prepare) channel. It's an example of a cloner, and explicitly it looks like this: $$ \Phi(\rho) = A_0 \rho A_0^{\dagger} + A_1 \rho A_1^{\dagger} $$ where $$ A_0 = \frac{1}{\sqrt{12}} \begin{pmatrix} 3 & 0\\ 0 & 1\\ 0 & 1\\ 1 & 0 \end{pmatrix} \quad\text{and}\quad A_1 = \frac{1}{\sqrt{12}} \begin{pmatrix} 0 & 1\\ 1 & 0\\ 1 & 0\\ 0 & 3 \end{pmatrix}. $$

For different sets of money states and figures of merit, you may end up with different optimal values and cloners. For example, if the money states also include $| 0\rangle \pm i |1\rangle$, then the Bužek-Hillery cloner is optimal and the correct value of $c$ drops to 2/3.

$\endgroup$
7
$\begingroup$

"I'm looking for an explicit upper bound on the probability of successful counterfeiting ...".

In "An adaptive attack on Wiesner's quantum money", by Aharon Brodutch, Daniel Nagaj, Or Sattath, and Dominique Unruh, last revised on 10 May 2016, the authors claim a success rate of: "~100%".

The paper makes these claims:

Main results. We show that in a strict testing variant of Wiesner's scheme (that is, if only valid money is returned to the owner), given a single valid quantum money state $(s,\left|\$_s\right>)$, a counterfeiter can efficiently create as many copies of $\left|\$_s\right>$ as he wishes (hence, the scheme is insecure). He can rely on the quantum Zeno effect for protection – if he disturbs the quantum money state only slightly, the bill is likely to be projected back to the original state after a test. Interestingly, this allows a counterfeiter to distinguish the four different qubit states with an arbitrarily small probability of being caught.

...

In this paper, we have focused on Wiesner's money in a noiseless environment. That is, the bank rejects the money if even a single qubit is measured incorrectly. In a more realistic setting, we have to deal with noise, and the bank would want to tolerate a limited amount of errors in the quantum state [PYJ+12], say 10%.

Also see: "Quantum Bitcoin: An Anonymous and Distributed Currency Secured by the No-Cloning Theorem of Quantum Mechanics", by Jonathan Jogenfors, 5 Apr 2016, where he discusses Wiesner's scheme and proposes one of his own.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.