<p>The question of cloning the BB84 states was covered in <a href="http://arxiv.org/abs/quant-ph/9909046">the paper</a> "Phase covariant quantum cloning" by Dagmar Bruß, Mirko Cinchetti, G. Mauro D'Ariano, and Chiara Macchiavello [<em>Phys Rev. A,</em> <strong>62,</strong> 012302 (2000), Eq. 36]. They give an optimal cloner for these states (which is also an optimal cloner for any states $\alpha |0\rangle + \beta |1\rangle$ with $\alpha$, $\beta\in \mathbb{R}\:$). They do not optimize using the same fidelity measure that you are asking about, but I suspect that their cloner is optimal for your question. Their cloner gives success probability $$\left(\frac{1}{2}+ \frac{1}{\sqrt{8}}\right)^{2n} \approx .72855^n$$
for counterfeiting $n$ BB84 states, quite a bit better than $(\frac{5}{8})^n$.</p>

<p>UPDATE: Bruß et al.'s optimal cloner is given by $\sum_{i=1}^2 A_i \rho A_i^\dagger$  where</p>

<p>$$A_1 = \left( \begin{array}{cc} \frac{1}{2}+\frac{1}{\sqrt{8}} &amp; 0\\
0 &amp; \frac{1}{\sqrt{8}}\\
0 &amp; \frac{1}{\sqrt{8}}\\
\frac{1}{2}-\frac{1}{\sqrt{8}} &amp; 0
\end{array} 
\right) \ \ \ \ 
A_2 = \left(\begin{array}{cc} 0&amp; \frac{1}{2}-\frac{1}{\sqrt{8}} \\
\frac{1}{\sqrt{8}}&amp;0\\
\frac{1}{\sqrt{8}}&amp;0\\
0&amp;\frac{1}{2}+\frac{1}{\sqrt{8}} 
\end{array} 
\right) .
$$ </p>

<p>The optimal cloner found by the solution to Abel's semindefinite program is $\sum_{i=1}^2 A_i \rho A_i^\dagger$  where:</p>

<p>$$A_1 = \frac{1}{\sqrt{12}}\left( \begin{array}{cc} 3 &amp; 0\\
0 &amp; 1\\
0 &amp; 1\\
1 &amp; 0
\end{array} 
\right) \ \ \ \ 
A_2 = \frac{1}{\sqrt{12}}\left(\begin{array}{cc} 0&amp; 1 \\
1&amp;0\\
1&amp;0\\
0&amp;3 
\end{array} 
\right) .
$$ </p>

<p>These clearly come from the same family of transformations, but have been optimized to satisfy different objective functions. This family of covariant transformations appears to be given by</p>

<p>$$A_1 = \frac{1}{\sqrt{2x^2+4y^2}}\left( \begin{array}{cc} x+y &amp; 0\\
0 &amp; y\\
0 &amp; y\\
x-y &amp; 0
\end{array} 
\right) \ \ \ \ 
A_2 = \frac{1}{\sqrt{2x^2+4y^2}}\left(\begin{array}{cc} 0&amp; x-y \\
y&amp;0\\
y&amp;0\\
0&amp;x+y 
\end{array} 
\right) .
$$ </p>

CC BY-SA 3.0
2011-10-26T12:40:20.110Z
Thanks, Peter!  It would be great to show optimality or even near-optimality of their cloner.  For that, I guess the first step would be showing that the optimal attack is individual rather than collective.
Scott Aaronson
CC BY-SA 3.0
2011-10-26T13:09:45.017Z
If Abel Molina's approach works, it should demonstrate this. If not, you should be able to use the techniques in the optimal cloner papers to get an upper bound, but I don't immediately know what it would be.
Peter Shor 
CC BY-SA 3.0
2011-10-27T14:04:51.377Z
@John: this transformation is the original quantum cloner of Bužek and Hillery. I think what's going on is that there's a one-parameter family of covariant quantum cloners for real-amplitude qubit states. If you require covariance for all states, not just real-amplitude ones, you get only the $x=y=1$ one. (Covariant here means: if you apply the same real rotation to the input and the output state spaces, you get the same transformation. Of course, this is still true if you apply a rotation to the input space first, so you have to also require that the overlap is maximized with no rotation.)
Peter Shor 
CC BY-SA 3.0
2011-10-26T10:02:36.173Z
2011-10-27T02:18:54.180Z
Peter Shor 
<p>It seems like this interaction can be modeled in the following way:</p>

<ol>
<li>Alice prepares one of the states $|000\rangle$, $|101\rangle$,$(|0\rangle+|1\rangle)|10\rangle/\sqrt{2}$, $(|0\rangle-|1\rangle)|11\rangle/\sqrt{2}$, according to a certain probability distribution, and sends the first qubit to Bob.</li>
<li>Bob performs an arbitrary quantum channel that sends his qubit to two qubits, which are then returned to Alice.</li>
<li>Alice performs a projective measurement on the four qubit on her possession. </li>
</ol>

<p>If I am not wrong about this (and sorry if I am), this falls within the formalism from Gutoski and Watrous presented <a href="http://www.cs.uwaterloo.ca/~watrous/Papers/General%20Theory%20of%20Quantum%20Games.pdf">here</a> and <a href="http://arxiv.org/abs/1003.0038">here</a>, which implies that:</p>

<ol>
<li>From Theorem 4.9 in the second of those, it is optimal to Bob to act independently  when Alice repeats this process with several qubits in an independent way, if the objective of Bob is to always fool Alice.</li>
<li>It is possible to obtain the value of c from a small semidefinite program. You can find more details of how to obtain this program in Section 3 <a href="http://arxiv.org/abs/1104.1140">here</a>. See the comments for the cvx code for the program and its value.</li>
</ol>

CC BY-SA 3.0
2011-10-25T21:04:35.093Z
Thanks, Abel -- if this works, it will be an amazing way to completely destroy this problem!  (And, incidentally, one of the clearest demonstrations of the power of the Gutoski-Watrous quantum games formalism.)
Scott Aaronson
CC BY-SA 3.0
2011-10-26T21:51:02.277Z
I did just obtain the same value of 3/4. Its explanatory power is small, but the computer code is at http://www.cs.uwaterloo.ca/~amolinap/scriptWeisner.m and http://www.cs.uwaterloo.ca/~amolinap/prtrace.m.
Abel Molina
CC BY-SA 3.0
2011-10-26T22:10:12.263Z
John and Abel: Thanks so much!!  So then, I guess there's a counterfeiting strategy that does *slightly* better at this task than the "optimal cloner" of Bruß et al. that Peter Shor describes below.  Any chance we could *find* that strategy?  (Now that we know the actual answer to be aiming for, maybe we could just find the strategy directly, without having to solve an SDP.)
Scott Aaronson
CC BY-SA 3.0
2011-10-26T23:12:07.287Z
I'm curious; if you added the four states $\cos(\pi/8) |0\rangle \pm \sin(\pi/8) |1 \rangle$ and  $\sin(\pi/8) |0\rangle \pm \cos(\pi/8) |1 \rangle$ to the Bell states, would the value still be 3/4? That is, is the answer true for all inputs with real coefficients, or just the four Bell states? This might help us narrow down possible strategies.
Peter Shor 
CC BY-SA 3.0
2011-10-27T00:13:51.973Z
The strategy is given by a quantum channel whose Choi-Jamielkowski representation is an optimal solution to the semidefinite program. See http://www.cs.uwaterloo.ca/~amolinap/optSolution.txt for a link to such a solution (the least significant qubit is the one received by Bob, and the other two are the ones he sends to Alice).

If my calculations are correct, the corresponding channel sends |0> to (|01>+|10>)/√2 with probability 1/6, and to (3|00>+|11>)/√10 with probability 5/6. |1> is sent to (|01>+|10>)/√2 with probability 1/6, and to (|00>+3|11>)/√10 with probability 5/6
Abel Molina
CC BY-SA 3.0
2011-10-27T00:23:26.300Z
Similarly, (|0>+|1>)/√2 is sent to (|11>-|00>)/√2 with probability 1/6, and to (|00>+1/2|01>+1/2|10>+|11>)/√(5/2) with probability 5/6. Similarly, (|0>-|1>)/√2 is sent to (|11>-|00>)/√2 with probability 1/6, and to (|00>-1/2|01>-1/2|10>+|11>)/√(5/2) with probability 5/6.
Abel Molina
CC BY-SA 3.0
2011-10-27T00:35:26.753Z
It's kind of interesting that in all four cases for the received state, the strategy has chance of success 3/4.
Abel Molina
CC BY-SA 3.0
2011-10-27T00:51:43.423Z
I also included cos(π/8)|0⟩±sin(π/8)|1⟩ and sin(π/8)|0⟩±cos(π/8)|1⟩, and the answer seems to be still 3/4.
Abel Molina
CC BY-SA 3.0
2011-10-27T01:19:59.373Z
In fact, for any state $\alpha | 0 \rangle + \beta |1\rangle$, $\alpha$ and $\beta$ real, the strategy has 3/4 chance of success. I just did the calculations.
Peter Shor 
CC BY-SA 3.0
2011-10-27T11:27:56.773Z
Abel: Thanks again!  What I find amazing here is that 3/4 is *also* the first, "naive" answer one might guess.  For, if you perform a complete projective measurement on the original money state (say in the {|0>,|1>} basis), then the sequence of measurement outcomes will constitute a *new* money state that passes the verification test with probability (3/4)^n -- as Wiesner pointed out in his original paper.  The trouble is, that strategy doesn't give you *two* money states that pass the verification test with probability (3/4)^n *simultaneously*.
Scott Aaronson
CC BY-SA 3.0
2011-10-27T11:29:17.163Z
Even so, I wonder if it's just a coincidence that the same success probability 3/4 appears in both places, or if there's some deeper reason for it.
Scott Aaronson
CC BY-SA 3.0
2011-10-27T14:10:42.980Z
@Scott: if you do this for six-state BB84, you get success probability $(2/3)^n$, which is the same success probability as the similar naive strategy with verification for one money state. I don't know what happens for 3-dimensional quantum states, but it should be easy to check for 9-state 3-d BB84 (or $d^2$-state $d$-dimensional BB84), since we know the optimal quantum cloner in this case, and if 3-dimensions works the same as 2, then the optimal quantum cloner should also be optimal for your question.
Peter Shor 
CC BY-SA 3.0
2011-10-27T16:59:05.107Z
@Abel: Incidentally, if you haven't noticed, it's possible to rewrite the action of your cloner on the BB84 states in a much more symmetric way.  Namely, let |B> be the conjugate state to |A>.  Then for all |A> in {|0>,|1>,|+>,|->}, your cloner maps |A> to (3|AA>+|BB>)/sqrt(10) with probability 5/6, and to (|AB>+|BA>)/sqrt(2) with probability 1/6.
Scott Aaronson
CC BY-SA 3.0
2011-11-25T17:57:26.550Z
@AbelMolina: I did a minor edit on your post to typeset the states in point one. I've triple checked that the states match with what you had before, but it'd be wise for you to check too. If you are at all uncomfortable with the change, you may of course roll back to the previous version.
qubyte
CC BY-SA 3.0
2012-03-07T21:20:16.660Z
Since @AbelMolina's answer has been converted too an arXiv paper, http://arxiv.org/abs/1202.4010 , I add the link for future readers.
Frédéric Grosshans
CC BY-SA 3.0
2013-05-13T08:27:27.123Z
The links to  cs.uwaterloo.ca/~amolinap/ will be broken soon - the files can now be accessed at  abelmolina.me/scriptWeisner.m, abelmolina.me/prtrace.m, and abelmolina.me/optSolution.txt
Abel Molina
CC BY-SA 3.0
2018-04-04T02:25:01.237Z
There's a newer answer at: https://quantumcomputing.stackexchange.com/ .
Rob
CC BY-SA 3.0
2011-10-25T17:47:58.497Z
2011-11-25T16:30:37.277Z
Abel Molina
<p>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</p>

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

<p>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.</p>

<p>On the other hand, because of the uncertainty relation (or alternatively, the No-Cloning Theorem), it's "intuitively obvious" that, if a counterfeiter who <i>doesn't</i> know the correct bases tries to copy $|\psi_s\rangle$, then the probability that <i>both</i> of the counterfeiter's output states pass the bank's verification test can be at most $c^n$, for some constant $c&lt;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$).</p>

<p>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.</p>

<p>So, <i>has</i> 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?</p>

<p><b>Update:</b> In light of the discussion with Joe Fitzsimons below, I should clarify that I'm looking for more than just a reduction from the security of BB84.  Rather, I'm looking for an <i>explicit upper bound</i> 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 in the basis</p>

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

<p>Or is there an entangled counterfeiting strategy that does better?</p>

<p><b>Update 2:</b> 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, <i>both</i> of these strategies turn out to achieve a success probability of (5/8)<sup>n</sup>.  So, my conjecture of the moment is that (5/8)<sup>n</sup> might be the right answer.  In any case, the fact that 5/8 is a <i>lower</i> 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).</p>

<p><b>Update 3:</b> Nope, the right answer is (3/4)<sup>n</sup>!  See the discussion thread below Abel Molina's answer.</p>

CC BY-SA 3.0
2011-10-24T13:15:41.443Z
Welcome to TP.SE Scott! Good to see you here.
Joe Fitzsimons
CC BY-SA 3.0
2011-10-24T13:22:28.943Z
It seems like Wiesner's scheme corresponds exactly to BB84 where you post select on Bob having chosen exactly the same bases of measurement as Alice has for preparation (since the bank is both Alice and Bob). Clearly the bank could instead chose the measurement basis randomly, and simulate BB84, which would yield strictly weaker security (since you would consider exactly the same measurements but only on a subset of qubits), so you can surely use a proof of BB84 to lower bound the security of the quantum money scheme. Perhaps I'm missing something though.
Joe Fitzsimons
CC BY-SA 3.0
2011-10-24T13:33:05.500Z
Thanks for the welcome and the answer, Joe!  FWIW, I share your intuition that a security proof for Wiesner's scheme ought to be "strictly easier" than a security proof for BB84.  However, with that argument (like with every other one), I keep coming back to the same question: "so then what's the upper bound on c?"
Scott Aaronson
CC BY-SA 3.0
2011-10-24T13:36:38.473Z
Surely it is upper bounded by the probability of determining the key in BB84.
Joe Fitzsimons
CC BY-SA 3.0
2011-10-24T13:38:02.453Z
Also, while it would be OK to deduce the security of Wiesner's scheme from the security of BB84 if that's the only/best alternative, I hold out the hope that there should be a more direct and informative proof.  Furthermore, it seems plausible that a direct proof would be needed for getting an explicit upper bound on c, or for getting a "reasonable" such bound (more like 0.9 than like 0.99999).
Scott Aaronson
CC BY-SA 3.0
2011-10-24T13:43:18.687Z
Joe, I checked the Lo-Chau paper, and unless I missed it, it didn't give an *explicit* upper bound on the copying probability -- just said that it decreases exponentially.  In retrospect, I should've written my question differently: I already know how to give a "proof" using phrases like "surely it should be possible." ;-)  My question is to give a proof that comes with a reasonable, explicit upper bound on c.
Scott Aaronson
CC BY-SA 3.0
2011-10-24T13:48:58.260Z
There is certainly a more direct way. You could simply write the eavesdropper as a unitary operator across the the note + an ancilla system. Expand it into a sum over Paulis, and then calculate the average projection onto the correct subspace as a function of the weight of the Paulis on the note subspace. You get exponential surpression in terms of the weight over that subspace. However for every qubit the operator doesn't act on you lose information in your clone, and the chance of it passing the test decreases exponentially. Balancing the two should then give a bound on $c$.
Joe Fitzsimons
CC BY-SA 3.0
2011-10-24T14:43:04.883Z
Given how basic the question is, I'm amazed no one has done this calculation before!  I could try it, but I'd first have to look up what it means to expand a unitary into a sum over Paulis.  In the meantime, I was sort of hoping that a security proof could give some insight into the question of *what the best counterfeiting strategy looks like.*  In particular: is the best strategy simply to measure each qubit independently, say in the cos(pi/8),sin(pi/8) basis?  Or is there an entangled counterfeiting strategy that does better?
Scott Aaronson
CC BY-SA 3.0
2011-10-25T10:46:13.043Z
Andy: What's ironic is that Paul Christiano and I now know how to prove the security of a *different* quantum money scheme, even against "interactive strategies" like the one you mention.  (We call a scheme "query-secure" if it has that stronger security guarantee, though we'd be open to a better term.)  For Wiesner's original scheme, by contrast, the very fact that any security proof needs to *break down* for interactive strategies, seems to be one factor that makes such a proof trickier.
Scott Aaronson
CC BY-SA 3.0
2018-04-04T01:33:02.797Z
@ScottAaronson - You can ask this question at: https://quantumcomputing.stackexchange.com/ .
Rob
<quantum-computing>
Rigorous security proof for Wiesner's quantum money?
Scott Aaronson
# Rigorous security proof for Wiesner's quantum money?

(Asked by: username_0 on 2011-10-24)

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?

**Update:** In light of the discussion with username_1 below, I should 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 in 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?

**Update 2:** 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).

**Update 3:** Nope, the right answer is (3/4)n! See the discussion thread below username_4's answer.

**Tags:** quantum-computing

> **Comments:**
> **username_1**: Welcome to TP.SE Scott! Good to see you here.  
> **username_1**: It seems like Wiesner's scheme corresponds exactly to BB84 where you post select on Bob having chosen exactly the same bases of measurement as Alice has for preparation (since the bank is both Alice and Bob). Clearly the bank could instead chose the measurement basis randomly, and simulate BB84, which would yield strictly weaker security (since you would consider exactly the same measurements but only on a subset of qubits), so you can surely use a proof of BB84 to lower bound the security of the quantum money scheme. Perhaps I'm missing something though.  
> **username_0**: Thanks for the welcome and the answer, Joe!  FWIW, I share your intuition that a security proof for Wiesner's scheme ought to be "strictly easier" than a security proof for BB84.  However, with that argument (like with every other one), I keep coming back to the same question: "so then what's the upper bound on c?"  
> **username_1**: Surely it is upper bounded by the probability of determining the key in BB84.  
> **username_0**: Also, while it would be OK to deduce the security of Wiesner's scheme from the security of BB84 if that's the only/best alternative, I hold out the hope that there should be a more direct and informative proof.  Furthermore, it seems plausible that a direct proof would be needed for getting an explicit upper bound on c, or for getting a "reasonable" such bound (more like 0.9 than like 0.99999).  
> **username_0**: Joe, I checked the Lo-Chau paper, and unless I missed it, it didn't give an *explicit* upper bound on the copying probability -- just said that it decreases exponentially.  In retrospect, I should've written my question differently: I already know how to give a "proof" using phrases like "surely it should be possible." ;-)  My question is to give a proof that comes with a reasonable, explicit upper bound on c.  
> **username_1**: There is certainly a more direct way. You could simply write the eavesdropper as a unitary operator across the the note + an ancilla system. Expand it into a sum over Paulis, and then calculate the average projection onto the correct subspace as a function of the weight of the Paulis on the note subspace. You get exponential surpression in terms of the weight over that subspace. However for every qubit the operator doesn't act on you lose information in your clone, and the chance of it passing the test decreases exponentially. Balancing the two should then give a bound on $c$.  
> **username_0**: Given how basic the question is, I'm amazed no one has done this calculation before!  I could try it, but I'd first have to look up what it means to expand a unitary into a sum over Paulis.  In the meantime, I was sort of hoping that a security proof could give some insight into the question of *what the best counterfeiting strategy looks like.*  In particular: is the best strategy simply to measure each qubit independently, say in the cos(pi/8),sin(pi/8) basis?  Or is there an entangled counterfeiting strategy that does better?  
> **username_0**: Andy: What's ironic is that Paul Christiano and I now know how to prove the security of a *different* quantum money scheme, even against "interactive strategies" like the one you mention.  (We call a scheme "query-secure" if it has that stronger security guarantee, though we'd be open to a better term.)  For Wiesner's original scheme, by contrast, the very fact that any security proof needs to *break down* for interactive strategies, seems to be one factor that makes such a proof trickier.  
> **username_2**: @ScottAaronson - You can ask this question at: https://quantumcomputing.stackexchange.com/ .  

---

## 2 answers

### Answer by username_4 on 2011-10-25. Score: 34 | Accepted answer

It seems like this interaction can be modeled in the following way:

1. Alice prepares one of the states $|000\rangle$, $|101\rangle$,$(|0\rangle+|1\rangle)|10\rangle/\sqrt{2}$, $(|0\rangle-|1\rangle)|11\rangle/\sqrt{2}$, according to a certain probability distribution, and sends the first qubit to Bob.
2. Bob performs an arbitrary quantum channel that sends his qubit to two qubits, which are then returned to Alice.
3. Alice performs a projective measurement on the four qubit on her possession.

If I am not wrong about this (and sorry if I am), this falls within the formalism from Gutoski and Watrous presented [here](http://www.cs.uwaterloo.ca/~watrous/Papers/General%20Theory%20of%20Quantum%20Games.pdf) and [here](http://arxiv.org/abs/1003.0038), which implies that:

1. From Theorem 4.9 in the second of those, it is optimal to Bob to act independently when Alice repeats this process with several qubits in an independent way, if the objective of Bob is to always fool Alice.
2. It is possible to obtain the value of c from a small semidefinite program. You can find more details of how to obtain this program in Section 3 [here](http://arxiv.org/abs/1104.1140). See the comments for the cvx code for the program and its value.

> **Comments:**
> **username_0**: Thanks, Abel -- if this works, it will be an amazing way to completely destroy this problem!  (And, incidentally, one of the clearest demonstrations of the power of the Gutoski-Watrous quantum games formalism.)  
> **username_4**: I did just obtain the same value of 3/4. Its explanatory power is small, but the computer code is at http://www.cs.uwaterloo.ca/~amolinap/scriptWeisner.m and http://www.cs.uwaterloo.ca/~amolinap/prtrace.m.  
> **username_0**: John and Abel: Thanks so much!!  So then, I guess there's a counterfeiting strategy that does *slightly* better at this task than the "optimal cloner" of Bruß et al. that username_3describes below.  Any chance we could *find* that strategy?  (Now that we know the actual answer to be aiming for, maybe we could just find the strategy directly, without having to solve an SDP.)  
> **username_3**: I'm curious; if you added the four states $\cos(\pi/8) |0\rangle \pm \sin(\pi/8) |1 \rangle$ and  $\sin(\pi/8) |0\rangle \pm \cos(\pi/8) |1 \rangle$ to the Bell states, would the value still be 3/4? That is, is the answer true for all inputs with real coefficients, or just the four Bell states? This might help us narrow down possible strategies.  
> **username_4**: The strategy is given by a quantum channel whose Choi-Jamielkowski representation is an optimal solution to the semidefinite program. See http://www.cs.uwaterloo.ca/~amolinap/optSolution.txt for a link to such a solution (the least significant qubit is the one received by Bob, and the other two are the ones he sends to Alice).  If my calculations are correct, the corresponding channel sends |0> to (|01>+|10>)/√2 with probability 1/6, and to (3|00>+|11>)/√10 with probability 5/6. |1> is sent to (|01>+|10>)/√2 with probability 1/6, and to (|00>+3|11>)/√10 with probability 5/6  
> **username_4**: Similarly, (|0>+|1>)/√2 is sent to (|11>-|00>)/√2 with probability 1/6, and to (|00>+1/2|01>+1/2|10>+|11>)/√(5/2) with probability 5/6. Similarly, (|0>-|1>)/√2 is sent to (|11>-|00>)/√2 with probability 1/6, and to (|00>-1/2|01>-1/2|10>+|11>)/√(5/2) with probability 5/6.  
> **username_4**: It's kind of interesting that in all four cases for the received state, the strategy has chance of success 3/4.  
> **username_4**: I also included cos(π/8)|0⟩±sin(π/8)|1⟩ and sin(π/8)|0⟩±cos(π/8)|1⟩, and the answer seems to be still 3/4.  
> **username_3**: In fact, for any state $\alpha | 0 \rangle + \beta |1\rangle$, $\alpha$ and $\beta$ real, the strategy has 3/4 chance of success. I just did the calculations.  
> **username_0**: Abel: Thanks again!  What I find amazing here is that 3/4 is *also* the first, "naive" answer one might guess.  For, if you perform a complete projective measurement on the original money state (say in the {|0>,|1>} basis), then the sequence of measurement outcomes will constitute a *new* money state that passes the verification test with probability (3/4)^n -- as Wiesner pointed out in his original paper.  The trouble is, that strategy doesn't give you *two* money states that pass the verification test with probability (3/4)^n *simultaneously*.  
> **username_0**: Even so, I wonder if it's just a coincidence that the same success probability 3/4 appears in both places, or if there's some deeper reason for it.  
> **username_3**: @Scott: if you do this for six-state BB84, you get success probability $(2/3)^n$, which is the same success probability as the similar naive strategy with verification for one money state. I don't know what happens for 3-dimensional quantum states, but it should be easy to check for 9-state 3-d BB84 (or $d^2$-state $d$-dimensional BB84), since we know the optimal quantum cloner in this case, and if 3-dimensions works the same as 2, then the optimal quantum cloner should also be optimal for your question.  
> **username_0**: @Abel: Incidentally, if you haven't noticed, it's possible to rewrite the action of your cloner on the BB84 states in a much more symmetric way.  Namely, let |B> be the conjugate state to |A>.  Then for all |A> in {|0>,|1>,|+>,|->}, your cloner maps |A> to (3|AA>+|BB>)/sqrt(10) with probability 5/6, and to (|AB>+|BA>)/sqrt(2) with probability 1/6.  
> **username_5**: @AbelMolina: I did a minor edit on your post to typeset the states in point one. I've triple checked that the states match with what you had before, but it'd be wise for you to check too. If you are at all uncomfortable with the change, you may of course roll back to the previous version.  
> **username_6**: Since @AbelMolina's answer has been converted too an arXiv paper, http://arxiv.org/abs/1202.4010 , I add the link for future readers.  
> **username_4**: The links to  cs.uwaterloo.ca/~amolinap/ will be broken soon - the files can now be accessed at  abelmolina.me/scriptWeisner.m, abelmolina.me/prtrace.m, and abelmolina.me/optSolution.txt  
> **username_2**: There's a newer answer at: https://quantumcomputing.stackexchange.com/ .  

---

### Answer by username_3 on 2011-10-26. Score: 19

The question of cloning the BB84 states was covered in [the paper](http://arxiv.org/abs/quant-ph/9909046) "Phase covariant quantum cloning" by Dagmar Bruß, Mirko Cinchetti, G. Mauro D'Ariano, and Chiara Macchiavello [*Phys Rev. A,* **62,** 012302 (2000), Eq. 36]. They give an optimal cloner for these states (which is also an optimal cloner for any states $\alpha |0\rangle + \beta |1\rangle$ with $\alpha$, $\beta\in \mathbb{R}\:$). They do not optimize using the same fidelity measure that you are asking about, but I suspect that their cloner is optimal for your question. Their cloner gives success probability $$\left(\frac{1}{2}+ \frac{1}{\sqrt{8}}\right)^{2n} \approx .72855^n$$
for counterfeiting $n$ BB84 states, quite a bit better than $(\frac{5}{8})^n$.

UPDATE: Bruß et al.'s optimal cloner is given by $\sum\_{i=1}^2 A\_i \rho A\_i^\dagger$ where

$$A\_1 = \left( \begin{array}{cc} \frac{1}{2}+\frac{1}{\sqrt{8}} & 0\\
0 & \frac{1}{\sqrt{8}}\\
0 & \frac{1}{\sqrt{8}}\\
\frac{1}{2}-\frac{1}{\sqrt{8}} & 0
\end{array}
\right) \ \ \ \
A\_2 = \left(\begin{array}{cc} 0& \frac{1}{2}-\frac{1}{\sqrt{8}} \\
\frac{1}{\sqrt{8}}&0\\
\frac{1}{\sqrt{8}}&0\\
0&\frac{1}{2}+\frac{1}{\sqrt{8}}
\end{array}
\right) .
$$

The optimal cloner found by the solution to Abel's semindefinite program is $\sum\_{i=1}^2 A\_i \rho A\_i^\dagger$ where:

$$A\_1 = \frac{1}{\sqrt{12}}\left( \begin{array}{cc} 3 & 0\\
0 & 1\\
0 & 1\\
1 & 0
\end{array}
\right) \ \ \ \
A\_2 = \frac{1}{\sqrt{12}}\left(\begin{array}{cc} 0& 1 \\
1&0\\
1&0\\
0&3
\end{array}
\right) .
$$

These clearly come from the same family of transformations, but have been optimized to satisfy different objective functions. This family of covariant transformations appears to be given by

$$A\_1 = \frac{1}{\sqrt{2x^2+4y^2}}\left( \begin{array}{cc} x+y & 0\\
0 & y\\
0 & y\\
x-y & 0
\end{array}
\right) \ \ \ \
A\_2 = \frac{1}{\sqrt{2x^2+4y^2}}\left(\begin{array}{cc} 0& x-y \\
y&0\\
y&0\\
0&x+y
\end{array}
\right) .
$$

> **Comments:**
> **username_0**: Thanks, Peter!  It would be great to show optimality or even near-optimality of their cloner.  For that, I guess the first step would be showing that the optimal attack is individual rather than collective.  
> **username_3**: If username_4's approach works, it should demonstrate this. If not, you should be able to use the techniques in the optimal cloner papers to get an upper bound, but I don't immediately know what it would be.  
> **username_3**: @John: this transformation is the original quantum cloner of Bužek and Hillery. I think what's going on is that there's a one-parameter family of covariant quantum cloners for real-amplitude qubit states. If you require covariance for all states, not just real-amplitude ones, you get only the $x=y=1$ one. (Covariant here means: if you apply the same real rotation to the input and the output state spaces, you get the same transformation. Of course, this is still true if you apply a rotation to the input space first, so you have to also require that the overlap is maximized with no rotation.)  

---

