# Quantum entropy and ?

Tags:
1. Jan 17, 2014

### iorfus

Hi everyone!
I have a little problem for an upcoming exams, and I think I need just small hints to solve it.

My problem is that I have to write about ten/fifteen pages about SUPERDENSE CODING and QUANTUM CRYPTOGRAPHY, and my professor has taken for granted that these are strongly linked to quantum entropy. He never told us why! Indeed he talked about that as applications of the property quantum entropy. However, on the two books I am using (Nielsen&Chuang and Preskill's Lectures at CalTech), these two subjects are treated with no link to entropy.
Could someone please tell me where is the link? And when can I found material to get a reasonable understanding of that?

Thank you very much!
Iorfus

2. Jan 17, 2014

### atyy

At the classical level, coding is related to information theory, which uses the Shannon mutual information. The Shannon information is a particular type of relative entropy or Kullback-Leibler divergence. The entropy is something like log(number of possibilities) by asymptotic equipartition. The relative entropy has a similar operational meaning. There are quantum analogues of these properties. For example, the classical Boltzmann-Gibbs entropy has the von Neumann entropy as its counterpart.

http://arxiv.org/abs/quant-ph/0102094
The Role of Relative Entropy in Quantum Information Theory
V. Vedral

A useful reference for the classical theory is

http://www.inference.phy.cam.ac.uk/itprnn/book.html
Information Theory, Inference, and Learning Algorithms
David MacKay

3. Jan 17, 2014

### iorfus

Thanks! It really helps with superdense coding!

Does anyone know of a direct link between entropy and cryptography? However, I suspect that my professor wants me to talk about quantum cryptography as a way to exploit entanglement. As entropy is used to quantify entanglement, this is the link, though it is not direct. Any different opinions?

4. Jan 19, 2014

In information theory, (Shannon) entropy is often considered as a measure of uncertainty, or "level of randomness", if that's more comprehensible. Let’s say you have binary string and try to guess the next value in the string. What do you do, to make the best guess?

Of course you will start by analyzing the values you've already got, and look for patterns and regularities. Shannon entropy is a measurement of how hard it is to guess the next value (related to the length of the string).

Some examples of order and disorder in 3 binary strings:

Code (Text):
[B]Binary String   Description               Reason[/B]
--------------------------------------------------------
11111111        Perfectly ordered         All 1's
01010101        Regular, not disordered   Repeating 01's
01101011        Somewhat disordered       No Apparent Pattern
As you see the first string isn't hard to guess at all, the 9th bit will most probably be 1, whereas the last string is a bit more complicated, and your guess could be wrong.

Get it?

The link between Shannon entropy and quantum cryptography is of course the intrinsic random nature of Quantum Mechanics – the best source of pure randomness you'll ever find. The worst source is poorly designed pseudorandom number generators (PRNG), in which clever analysts will find devastating patterns in no time.

Entanglement in quantum cryptography is often used for quantum key exchange, as a safe way of exchange random keys over a quantum channel. How does it work? Well, without going too deep into details, the BB84 protocol utilizes entanglement to transmit the key from Alice to Bob, and here how it works:

• Alice prepares two entangled photons.

• Alice randomly chooses to measure her photon on rectilinear basis (0° & 90°) or diagonal basis (45° & 135°).

• Alice sends the unmeasured photon to Bob who also randomly chooses to measure the received photon on rectilinear or diagonal basis, and records the time and the result.

• When the transmission is finished, Alice sends the measurement basis for each photon to Bob over a public classical channel, and Bob sends his measurement basis to Alice.

• On average, Alice & Bob will have chosen the same measurement basis half the time, and they both discard measurements where a different basis was used.

• Without actually sending one single bit of the binary key, they now have an identical copy of the quantum key, which is 100% random.

• What about eavesdropper? Well to eliminate this, they send a predetermined subset of their bit strings to each other, for comparison. If "Illegal Eve" has tried to intercept the quantum channel, to steal the key, she will immediately be revealed since the two subsets won't match perfectly!
Sweet huh!?

Here's a short introduction to Superdense coding.

Superdense coding: how to send two bits using one qubit

Good luck!

5. Jan 20, 2014

### iorfus

Thanks! this is very useful :-)

I have been reading Preskill and Nielsen&Chuang, and now I am starting to better understand the whole thing. Your point by point explanation is extremely useful as now I have a clearere link with entropy and entanglement. My problem was also that Nielsen&Chuang deals with quantum error correction before introducing cryptography. I have not studied quantum error correction in my course, therefore I find a lot of parts on the book which confuse me. Now it all seems more straightforward and I am almost ready to write :-)

6. Jan 21, 2014

### wle

Some elaboration: in the BB84 protocol Alice and Bob perform $\sigma_{z}$ and $\sigma_{x}$ measurements (for photons, these correspond to rectilinear and diagonal polarisation measurements) on some quantum state $\rho_{\mathrm{ABE}}$ that, in the worst case, you assume might be shared (and correlated with) an eavesdropper (Eve). If Alice and Bob find that they get perfectly correlated results in the cases where they made the same measurements (as determined by sacrificing and testing a random subset, as DevilsAvocado explained), then it's possible to show that Alice and Bob must have been sharing maximally entangled $\lvert \Phi^{+} \rangle$ states:

$$\lvert \Phi^{+} \rangle_{\mathrm{AB}} = \frac{1}{\sqrt{2}} [ \lvert 0 \rangle_{\mathrm{A}} \lvert 0 \rangle_{\mathrm{B}} + \lvert 1 \rangle_{\mathrm{A}} \lvert 1 \rangle_{\mathrm{B}} ] \,. \qquad (1)$$
This is the only quantum state that can produce perfectly correlated outcomes for both $\sigma_{z}$ and $\sigma_{x}$ measurements. In this case, if there's an eavesdropper, the only possibility for a state shared by Alice, Bob, and Eve is one of the form

$$\lvert \Psi \rangle_{\mathrm{ABE}} = \lvert \Phi^{+} \rangle_{\mathrm{AB}} \otimes \lvert \psi \rangle_{\mathrm{E}} \,, \qquad (2)$$
i.e. a state in which Eve is completely uncorrelated with Alice and Bob. This property of quantum physics is sometimes called the "monogamy of entanglement": if two parties (like Alice and Bob here) share a maximally entangled state (or really any pure state), then the same state cannot simultaneously be entangled with the environment or any third party (like Eve here). The security of (entanglement-based) quantum key distribution is based on this principle.

Of course this observation isn't very useful on its own. If you tried to implement a real QKD system just by testing for perfect correlations, any serious experimental physicist would laugh at you: there's simply no such thing as a perfect experiment. You're always going to have a certain amount of noise in your channel, the measurements won't be perfect, and so on, and so you're always going to detect a nonzero error rate in a QKD experiment regardless of whether there's an eavesdropper present. But for the purpose of establishing secrecy, one should assume in the worst case that all the errors you see are the result of tampering by an eavesdropper (because the whole point of QKD is "security based only on the laws of physics").

This is where entropies and information theory come in. If you observe some small but nonzero error rate (call it $\delta$) in a QKD experiment, then generally the best you can do is say that Alice, Bob, and Eve are sharing some state $\rho_{\mathrm{ABE}}$ that is close to an ideal state of the form (2), and in which Eve might be partially correlated with Alice and Bob. In this case, it's known from results in information theory that Alice and Bob can still extract a shorter but nearly perfectly secure key by applying classical error correction and privacy amplification procedures to their raw key bits. The precise amount of key that can safely be extracted this way is quantified by certain entropies. For instance, many QKD security analyses of the last decade or so use a result called the Devetak-Winter bound, which for a given state $\rho_{\mathrm{ABE}}$ says that (in the asymptotic limit) you can safely extract perfectly secret key at a rate given by

$$r = I(\mathrm{A} : \mathrm{B}) - \chi(\mathrm{A} : \mathrm{E}) \,, \qquad (3)$$
where $I(\mathrm{A} : \mathrm{B})$ is the mutual information between Alice and Bob's key bits and $\chi(\mathrm{A} : \mathrm{E})$ is the Holevo quantity between Alice and Eve. Intuitively, this says that the extractable key rate is quantified by how much information Bob has about Alice's version of the key minus how much information Eve has about it. For the BB84 protocol, if you do the exercise of minimising equation (3) over all quantum states compatible with a fixed error rate $\delta$, you'll obtain the Shor-Preskill [1] key rate

$$r = 1 - 2 h(\delta) \qquad (4)$$
(where $h$ is the binary entropy function). This equals 1 for an error rate of zero, and drops to zero for an error rate of about $\delta \approx 11\%$. The implication is that, at least in the asymptotic limit, one can still extract a perfectly secret key from a BB84 implementation as long as the error rate is less than the Shor-Preskill bound of 11% (though possibly at a very reduced rate).

I should point out that this information theoretic approach to studying QKD security only really gained traction around 2005 or 2006, following the paper by Devetak and Winter [2] and a similar result by Renner, Gisin, and Kraus [3]. Earlier security proofs dating to about the year 2000 were based on results from the theory of entanglement distillation and quantum error correction codes (some papers still use this approach). Keep this in mind if you try to learn QKD from textbooks: Nielsen and Chuang was published in the year 2000, which is ancient history as far as QKD security analysis is concerned. As far as I know, Preskill also hasn't updated his lecture notes since he prepared them in the late 1990s and early 2000s.

Summary/TLDR:
• Intuitively, the security of entanglement-based QKD derives from the principle of monogamy of entanglement of quantum correlations.
• Entropies have an operational interpretation in QKD, where they quantify how much key can be securely extracted (using classical error correction and privacy amplification protocols) against an eavesdropper that is partially correlated with Alice and Bob.

[1] P. W. Shor and J. Preskill, Phys. Rev. Lett. 85, 441--444 (2000), arXiv:quant-ph/0003004.
[2] I. Devetak and A. Winter, Proc. R. Soc. A 461, 207--235 (2005), arXiv:quant-ph/0306078.
[3] R. Renner, N. Gisin, and B. Kraus, Phys. Rev. A 72, 012332 (2005), arXiv:quant-ph/0502064.
[4] N. Gisin, G. Ribordy, W. Tittel, and H. Zbinden, Rev. Mod. Phys. 74, 145--195 (2002), arXiv:quant-ph/0101098. (An early review article, a bit out of date now in some respects.)
[5] V. Scarani, H. Bechmann-Pasquinucci, N. J. Cerf, M. Dušek, N. Lütkenhaus, and M. Peev, Rev. Mod. Phys. 81, 1301--1350 (2009), arXiv:0802.4155 [quant-ph]. (A more recent review article, focusing more on the practical aspects of QKD security.)
[6] R. Renner, "Security of Quantum Key Distribution", arXiv:quant-ph/0512258. (Renato Renner's PhD thesis.)
[7] M. Tomamichel and R. Renner, Phys. Rev. Lett. 106, 110506 (2011), arXiv:1009.2015 [quant-ph]. (Sketch of a recent and very elegant security proof of the BB84 protocol based on an entropic uncertainty relation.)
[8] Websites of ID Quantique and MagiQ Technologies. (Two companies that offer QKD systems commercially.)

Last edited: Jan 21, 2014
7. Jan 21, 2014

### wle

A minor detail here: it isn't actually necessary for Alice and Bob to pick the measurement bases equiprobably. In fact, for the BB84 protocol it's common to imagine Alice and Bob both using the $\sigma_{z}$ basis the vast majority of the time for key generation, and only doing occasional random $\sigma_{x}$ measurements for the purpose of testing the quantum channel. This nearly doubles the key generation rate, since the fraction of cases where they pick mismatched bases can be made arbitrarily small this way.

8. Jan 21, 2014

### iorfus

Great! I would have had no idea how to find these updates. I am sure it will be very useful for my assignment and, most importantly, for my understanding. Thanks a lot!

9. Jan 21, 2014

### iorfus

I have a last question that I am not able to solve reading books and all the material on the Internet.

In the EPR based protocol for QKD, devised by Ekart, are the "no-cloning theorem" and the £indistinguishability of non-orthogonal quantum states£ expoloited?
If yes, how?

In my understanding, these two fundamental quanto-mechanical facts are exploited only in BB84. I can't see the direct passage in which they are exploited in the E91, as explained by Preskill at least.

Any hints?

10. Jan 21, 2014

### wle

Not really. The Ekert protocol is an entanglement-based QKD scheme and its security physically derives from the monogamy of entanglement as I explained. The original BB84 protocol is what's called a "prepare-and-measure" scheme, and its security can be considered to derive physically from the no-cloning principle.

That said, these ideas aren't unrelated. The Ekert protocol is really just an entanglement-based version of the BB84 protocol (in my previous post, I used "BB84" to refer to both), and proving the security of one is known to be equivalent to proving the security of the other (this was first observed by Bennett, Brassard, and Mermin [1]). The usual argument one way goes like this: in the BB84 protocol, instead of preparing $\sigma_{z}$ and $\sigma_{x}$ basis states, it is obviously equivalent for Alice to prepare entangled particle pairs in the $\lvert \Phi^{+} \rangle$ state, perform a $\sigma_{z}$ or $\sigma_{x}$ measurement on one of the particles, and send the other particle to Bob. The only difference between this setup and the Ekert protocol is that, in the Ekert protocol, the source of entangled particle pairs is located midway between Alice and Bob and is assumed to be under Eve's control instead of Alice's. This can clearly only increase Eve's power, so a security proof of the Ekert scheme automatically implies the security of the original BB84 scheme. It's also possible to show the converse, so the two are really equivalent to one another.

So while the original prepare-and-measure BB84 protocol physically derives its security from the no-cloning principle, for the purpose of proving its security you can formally recast it as a problem of studying monogamy of entanglement in the context of the Ekert protocol, and vice versa. This is true, by the way, for pretty much any BB84-like QKD scheme. For instance, there are prepare-and-measure and entanglement-based versions of the six-state protocol, which is a protocol similar to BB84/Ekert with the addition that Alice and Bob also use the $\sigma_{y}$ basis.

By the way, if you're interested in QKD from the point of view of entanglement, you may also be interested in looking into something called "device-independent" QKD [2,3,4]. These are entanglement-based QKD protocols that use Bell tests as a measure of entanglement and security, following the idea by Ekert.

[1] C. H. Bennett, G. Brassard, and N. D. Mermin, Phys. Rev. Lett. 68, 557--559 (1992).
[2] J. Barrett, L. Hardy, and A. Kent, Phys. Rev. Lett. 95, 010503 (2005), arXiv:quant-ph/0405101.
[3] A. Acín, N. Brunner, N. Gisin, S. Massar, S. Pironio, and V. Scarani, Phys. Rev. Lett. 98, 230501 (2007), arXiv:quant-ph/0702152.
[4] S. Pironio, A. Acín, N. Brunner, N. Gisin, S. Massar, and V. Scarani, New J. Phys. 11, 045021 (2009), arXiv:0903.4460 [quant-ph].

Last edited: Jan 22, 2014
11. Jan 22, 2014

### iorfus

Fine. This forum is useful I should start contributing to it in the areas I am knowledgeable about.

12. Jan 26, 2014