# How many bits do Alice and Bob needs to compare to make sure the channel is secure in BB84?

I was trying to self-study qmc by reading the Quantum Computing A Gentle Introduction book, in section 2.4 it talks about the quantum key distribution protocol BB84. After (I thought) I understood it I went to work on exercise 2.9 and 2.10.

Ex. 2.9 is asking how many bits do Alice and Bob need to compare to be 90% confident that there is no Eve present in BB84. So if I understood correctly, BB84 is as follows:

1. Alice randomly chooses a basis/polarization of photon from the two bases $$\{ | 0 \rangle, | 1 \rangle \}$$ and $$\{ |+\rangle, |-\rangle \}$$ to encode the bit information $$0$$ or $$1$$ (the encoding rule is known e.g. $$|0\rangle$$ represents $$0$$). Then she sends a sequence of such photons to Bob.
2. Bob receives the sequence of photons and randomly chooses a basis from the two same bases and measures for each one of the photon.
3. They then compare the bases they chose and discard the ones where they chose base differently. Bob should be able to figure out what bit Alice is trying to send. (e.g. if the base they use is $$\{ |0\rangle, |1\rangle \}$$ and Bob has measured using the basis $$|1\rangle$$ but got $$0$$ light intensity then he knows that Alice's polarization was $$|0\rangle$$ so the bit information is $$0$$).
4. To be more secure, they also compare a subset of bits, if there is no interference then their bits should all agree. They discard these bits and what left is the key.

Eve, on the other hand, is trying to intercept the photon from Alice, measures it randomly from the two bases too, then she sends the basis she uses for measurement to Bob. After Alice & Bob publicly compare their bases, Eve can know $$25%$$ of the key for sure, although she inevitably changed the photon Bob would have received.

So to answer the first question ex. 2.9, I listed out different scenarios when Alice and Bob compare a subset of bits :

Suppose Alice sends a $$|0\rangle$$,

1. There is $$0.25$$ probability Eve also measures with $$|0\rangle$$, then she would not get detected.

2. $$0.25$$ - Eve measures using $$|1\rangle$$ then she would get detected for sure as Bob will get the opposite bit value as Alice.

3. $$0.25$$ chance Eve measures using $$|+\rangle$$, Bob now will receive $$|+\rangle$$, then if Bob uses $$|0\rangle$$ and obtain the same with $$0.5$$ chance, else if he uses $$|1\rangle$$ to measure but still end up with the correct bit with $$0.5$$ chance. That is $$0.25 \times (0.5 + 0.5) = 0.25$$

4. Same as 3, 0.25

So to sum up the probability Eve would go undetected, it's $$0.25 + 0 + 0.25 + 0.25 = 3/4$$, and we want the sequence of bits Eve goes undetected be less than $$10%$$, which yields $$(\frac{3}{4})^n < 0.1$$, approximately $$n=8$$.

The second question 2.10c, modifies the condition a little bit, instead of Eve chooses from the two known bases (the standard and the $$+/-$$), she does not know which to choose so she chooses randomly, then how many bits A&B needs to compare to have 90% confidence?

My approach is that, suppose Alice still uses standard base $$\{|0\rangle |1\rangle \}$$ and she sends a $$|0\rangle$$. Now Eve can measure it in her base $$\{ |e_1\rangle, |e_2\rangle \}$$ where $$|e_1\rangle = \cos\theta|0\rangle + \sin\theta|1\rangle$$ and $$|e_2\rangle = \sin\theta|0\rangle-\cos\theta|1\rangle$$, then Eve sends off the basis she uses to Bob again. I'm again listing out the scenarios,

1. If Eve measures with $$|e_1\rangle$$ (with 0.5 chance) then Bob receives $$|e_1\rangle$$, then if Bob measures with $$|0\rangle$$ then he gets correct bit with $$|\cos\theta|^2$$ probabiltity, if he measures in $$|1\rangle$$ then he gets correct bit with $$1 - |\sin\theta|^2=|\cos\theta|^2$$. Simiarly when Eve uses $$|e_2\rangle$$

sum up then I got $$0.5\times(2|\cos\theta|^2)+0.5\times(2|\sin\theta|^2)=1$$, this for sure is not correct!

Then I tried to search online and found a solution here, where it says the probability Bob gets correct bit is instead: $$|\langle0|e_1\rangle\langle e_1|0\rangle|^2 + |\langle0|e_2\rangle\langle e_2|0\rangle|^2 =\cos^4\theta+\sin^4\theta$$, then integrate over $$[0, \frac{\pi}{2}]$$ (normalized by $$\pi/2$$) is $$\frac{3}{4}$$ which is again same as in ex2.9.

Can someone explain why it's $$\cos^4\theta+\sin^4\theta$$ in both math details and high-level intuition (e.g. why even Eve does not know which base to use it still requires 8 bits comparison for A&B?)?

Thanks a lot!

Your analysis of Eve's cheating doesn't seem quite right (although the final answer is correct). What you need to say is: Assume Alice prepares a particular state in one of the bases. You could assume that's $|0\rangle$, but you can make the argument more generally.

• With 50% probability, Eve measures in the same basis that Alice prepared in (the 0/1 basis in this case). Eve is guaranteed to get the same answer (0), and so Bob will still get the same answer (0) because we're working specifically in the set of cases where Bob measures in the same basis as Alice. Eve is not detected.

• With 50% probability, Eve measures in the other basis. She'll get an answer. It doesn't actually matter what it is (in this case, either $|+\rangle$ or $|-\rangle$). Bob receives whatever that state is, and measures in the original basis, and gets the two different outcomes with 50:50 probability. Eve never learns anything about Alice's chosen bit, and she is detected half the time.

Overall, Eve learns the bit value half the time, and is detected in 1/4 of the cases. Now, strictly, you should average over all possible inputs of Alice. But there's sufficient symmetry in this simple case that all the outcomes are the same.

In the second question, you've missed one important feature: if Eve changes her measurement basis, the probability that she gets the different results varies (you've kept it fixed at 1/2).

High-level hand waving: If Eve chooses a basis which is very close to the 0/1 basis, she is almost guaranteed to get the same answer as the bit value Alice was sending (if she was sending in the 0/1 basis), and she is almost guaranteed to not be detected. As you get further away from that basis, Eve learns less, and is more likely to be detected. But, the trade-off is that if Alice had used the other basis, her chance of being detected decreases, and her knowledge of the bit improves. That said, it is not a perfect trade-off. I'll show you why very easily: Imagine that Alice is using the two standard bases. What if Eve measures in the basis $(|0\rangle\pm i|1\rangle)/\sqrt{2}$ every time? It is always the case (no matter which basis Alice chooses) that there is a 50% chance of Eve being detected.

Mathematically, what you were supposed to say was to imagine Alice sent $|0\rangle=\cos\theta|e_1\rangle+\sin\theta|e_2\rangle$. Thus, with probability $\cos^2\theta$, Eve gets answer $|e_1\rangle$, which gets passed on to Bob, who gets answer $|0\rangle$ with probability $\cos^2\theta$. Meanwhile, with probability $\sin^2\theta$, Eve gets answer $|e_2\rangle$, sends it on to Bob, and he gets answer $|0\rangle$ with probability $\sin^2\theta$. Thus, the overall probability of Bob not detecting anything is $$\cos^4\theta+\sin^4\theta=1-\frac12\sin^2(2\theta),$$ given that Alice sent $|0\rangle$. The analysis will be identical if Alice sent $|1\rangle$. However, you do need to repeat the analysis for if Alice sent $|+\rangle$. (At this moment, it should become apparent that you needed a phase parameter in your definition of $|e_1\rangle$ and $|e_2\rangle$ if you truly want to average over all possible bases, but I'll keep going with your definition.) So, assume Alice sent $|+\rangle=((\cos\theta+\sin\theta)|e_1\rangle-(\cos\theta-\sin\theta)|e_2\rangle)/\sqrt{2}$. So, Eve gets answer $|e_1\rangle$ with probability $(\cos\theta+\sin\theta)^2/2$, and Bob gets answer $|+\rangle$ with probability $(\cos\theta+\sin\theta)^2/2$. Hence, overall, the probability of Eve not being detected is $$\left(\frac{\cos\theta+\sin\theta}{\sqrt{2}}\right)^4+\left(\frac{\cos\theta-\sin\theta}{\sqrt{2}}\right)^4=1-\frac12\cos^2(2\theta).$$ Averaging over all possible inputs of Alice, we therefore get $$\frac12\left(1-\frac12\cos^2(2\theta)\right)+ \frac12\left(1-\frac12\sin^2(2\theta)\right)=\frac34.$$ At this point, the $\theta$ has disappeared. We don't have to average over all possible $\theta$. However, note that if we had correctly introduced a phase $\phi$ in the definition of $|e_1\rangle$, it would be necessary to perform some averaging. Moreover, the solution that you cite does not do that averaging correctly. Remember that if you want to convert from an integral in $(x,y)$ coordinates to an integral in $(r,\theta)$ coordinates, you need a conversion. You're going to have to perform an integral that's something like $$\frac{1}{2\pi}\int_0^{2\pi}d\phi\int_{0}^{\pi/2}\sin(2\theta)d\theta f(\theta,\phi),$$ where $f(\theta,\phi)$ is the probability of detecting Eve for a given $\theta,\phi$. (You probably want to check out this formula carefully, and verify factors of 2, as I've written this from memory. It gets a bit messy because, given you've used an angle $\theta$ in the definition of $|e_1\rangle$, that translates into an angle of $2\theta$ on the Bloch sphere.)

The other thing we haven't calculated it how much Eve learns. If she corresponds $|e_1\rangle$ with bit value 0, and $|e_2\rangle$ with bit value 1, she is correct with probability $$\frac12\left(\cos^2\theta+\left(\frac{\cos\theta+\sin\theta}{\sqrt{2}}\right)^2\right).$$ You could average this over $\theta$, but one of the interesting things to observe is that if Eve does know that two bases that are being used, she can optimise her value of $\theta$. The value $\theta=\frac{\pi}{8}$ gives her more knowledge (on average) that setting $\theta=0$ or $\pi/4$ (which are effectively the cases you analysed in the first question.

• I understood the basic phrase 'measuring with basis' wrong, I thought by measuring using e.g. standard basis, is that you choose one of the two bases to measure it, so either |0> or |1> but it should be measured 'together' (in practice the actual tool can be a polarizer with the two polarization slots). So now both the ex2.9 and 2.10 answer makes much more sense to me. I see... so the more general definition should be $\cos\theta|0>+e^{i\phi}\sin\theta|1>$.
– Sam
Sep 11 '18 at 4:06
• Interesting ... although the average correct bits Eve gets is 50% but there is this angle where her probability of getting correct bit is higher, although she can't use this $pi/8$ angle information
– Sam
Sep 11 '18 at 4:07