Fundamental rate-loss tradeoff for the quantum internet Koji Azuma,1,∗ Akihiro Mizutani,2 and Hoi-Kwong Lo3 1NTT Basic Research Laboratories, NTT Corporation, 3-1 Morinosato Wakamiya, Atsugi, Kanagawa 243-0198, Japan 2Department of Materials Engineering Science, Graduate School of Engineering Science, Osaka University, 1-3 Machikaneyama, Toyonaka, Osaka 560-8531, Japan 3Department of Physics and Department of Electrical & Computer Engineering, University of Toronto, Toronto, Ontario, Canada (Dated: January 13, 2016) 6 The quantuminternet holds promise for performing quantumcommunication—such as quantum 1 teleportation and quantum key distribution (QKD)—freely between any parties all over the globe. 0 Suchafuturequantumnetwork,dependingonthecommunicationdistanceoftherequestingparties, 2 necessitatestoinvokeseveralclassesofopticalquantumcommunicationsuchaspoint-to-pointcom- n municationprotocols,intercityQKDprotocolsandquantumrepeaterprotocols. Recently,Takeoka, a Guha and Wilde (TGW) have presented a fundamental rate-loss tradeoff on quantum communica- J tion capacity and secret keyagreement capacity of anylossy channelassisted byunlimited forward 2 and backward classical communication [Nat. Commun. 5, 5235 (2014)]. However, this bound is 1 applicable only to the simplest class of quantum communication, i.e., the point-to-point communi- cation protocols, and it has thus remained open to grasp the potential of a ‘worldwide’ quantum ] h network. Here we generalize the TGW bound to be applicable to any type of two-party quantum p communication over the quantum internet, including other indispensable but much more intricate - classes of quantumcommunication—intercity QKDprotocols andquantumrepeater protocols. We t also show that there is essentially no scaling gap between our bound and the quantum commu- n nication efficiencies of known protocols. Therefore, our result—corresponding to a fundamental a u and practical limitation for the quantum internet—will contribute to design an efficient quantum q internet in the future. [ PACSnumbers: 03.67.Hk,03.67.Dd,03.65.Ud,03.67.-a 1 v 3 Inthe conventionalInternet,ifaclient,Alice,wantstocommunicatewithanotherclient,Bob,anInternetprotocol 3 determines the path that the data follows to travel across multiple networks from Alice to Bob. Analogously, in the 9 future, according to a request for performing quantum communication between Alice and Bob, a quantum internet 2 protocol will supply the resources for quantum communication, such as unconditionally secure key and quantum 0 entanglement,to Alice andBobby utilizing properintermediate nodesconnectedby opticalfibres witheachother[1] . 1 [c.f. Fig. 1 (a)]. To such an optical network, photon loss in optical fibres is the dominant impediment in general [2]. 0 Nonetheless,aslongasAliceandBobarenottoofarawayfromeachother,sayoveracouplehundredkilometres,the 6 intermediate nodes would not be necessary, because the current point-to-point quantum communication has already 1 been very efficient as well as ready for practical use [3]. Besides, in terms of the communication efficiency for the : v distance,knownschemes[4–11]forthepoint-to-pointlinkshavenoscalinggapwithageneralupperboundonquantum i X communicationcapacityandsecretkeyagreementcapacityofanymemorylesslossychannel(whichmayormaynotbe noisy)undertheuseofunlimitedforwardandbackwardclassicalcommunication,calledTakeoka-Guha-Wilde(TGW) r a bound [12, 13] (see also subsequent important improvements [14, 15] to the TGW bound). Hence, there remains not muchroomtoimprovethoseschemesforpoint-to-pointlinksfurther. Nevertheless,thepoint-to-pointcommunication is not efficient enough to achieve the quantum internet. For example, the point-to-point quantum communication over 1,000 km needs to take almost one century to provide just one bit of secure key or one ebit for them under the use of a typical standard telecom optical fibre with loss of about 0.2 dB/km [16]. Therefore, for the request from far distant Alice and Bob, the quantum internet necessitates long-distance quantum communication schemes utilizing intermediate nodes, such as intercity QKD protocols [17–19] and quantum repeaters [20–34]. In particular, theseschemeswouldbeingreaterdemandforthequantuminternetthanthepoint-to-pointquantumcommunication, analogouslytothecurrentInternetwhereaclientcommunicateswithafardistantclientviarepeaternodescommonly and even unconsciously. Therefore, besides the TGW bound for the point-to-point links, it is important to find out a similarly fundamental and general limitation on the long-distance quantum communication schemes, which results ∗Electronicaddress: [email protected] 2 (a)! (b)! &’()"*+,-,+(%$! !"#$%! .%/%$+,-0$1!21*1,! 30+*% ! 4"5% ! 6)2-$17/8! :;<<- ! 9/8-$17/8! :;<<- " " " ! :;<<-! !2’-$17/8! FIG. 1: Quantum internet and the most general protocol. Panel (a) depicts a general quantum internet where Alice and Bob request its internet protocol to supply them with the resources for quantum communication, such as unconditionally secure key and quantum entanglement. Accordingly, the quantuminternet protocol considers any quantumnetwork G (which might be a quantum subnetwork of a quantum internet) associated with a directed graph G = (V,E). The set V of vertices is composed of thenodes as V ={A,B,C1,C2,...,Cn} (n=9 in thispanel) and theset E of edges specifies quantumchannels {Ne}e∈E in such a way that a quantum channel to send a quantum system from node v1 ∈V to node v2 ∈V is represented byNv1→v2. Thequantuminternetprotocol cancombinegivenquantumchannels{Ne}e∈E withLOCCarbitrarily, toprovide the required resources for Alice and Bob. However, our bound suggests that the obtainable secret bits or ebits are upper bounded by a bound for the point-to-point communication between a single parity having nodes V ⊂V with A and another A party having V (= V \V ) with B. In panel (b), we describe the paradigm of the most general two-party communication B A protocols, by exemplifying a linear network with n=4. In the i-th round (i=1,2,...,l), according to theprevious outcomes ki−1 =ki−1...k2k1,theprotocolusesaquantumchannelNeki−1 witheki−1 ∈E,followedbyLOCCprovidingaquantumstate ρˆkAiBC1C2...Cn withanewoutcomeki. Afteranl-thround,AliceandBobmayobtaintheresourcesforquantumcommunication. in understanding the full potential of the future quantum internet. However, it remained open to determine this limitation due to the complex nature of those schemes coming from the use of many intermediate nodes as well as a large variety of combinations of different elements such as quantum memories and quantum error correction and of different primitives such as entanglement generation, entanglement swapping and entanglement purification. The main point of this paper is to present a fundamental and practical limitation on the quantum internet. In particular, we derive rate-loss tradeoffs for any two-party quantum communication—composed of the use of optical fibres connecting nodes as well as arbitrary local operations and unlimited forward and backward (public) classical communication(LOCC)—overthequantuminternet,bytailoringtheTGWboundtobeingapplicabletoanynetwork topology. The key insight is reduction. Given any quantum network (which might be a subnetwork of a quantum internet), Alice’s node A and Bob’s node B, we can consider any bipartition of the nodes in the quantum network, V including node A and V containing node B [c.f. Fig. 1 (a)]. By regarding all nodes at V as local at A and A B A all nodes at V as local at B—which could never increase the difficulty of quantum communication between A and B B, one could reduce any network flow as a flow between a point-to-point link between A and B only. Therefore, an upper bound on the key rate or distillable entanglement for a point-to-point link automatically carries over to an upper bound to the quantum network. As this upper bound for point-to-point links, we simply use the TGW bound [12]. Our reductionidea is a simple observation. Nonetheless, ratherremarkably,we will showhere that the obtained boundsareexcellentinthesensethattheyhavenoscalinggapwithachievablequantumcommunicationefficienciesof knownprotocolsforintercityQKDandquantumrepeaters,intermsofrate-losstradeoffs. Thisisbroughtbythefact that our bounds essentially depend only on the number of the channel uses to establish a quantum communication resource for Alice and Bob and the squashed entanglement [12, 13] of the used optical channels. To obtainourbound, we needto define ageneralparadigmoftwo-partycommunicationoverthe quantuminternet [c.f. Fig. 1 (a)]. In the quantum internet, there are a variety of optical channels connecting nodes, for example depending on those lengths. This necessitates to generalize the paradigm [12, 13] of Takeoka et al. for the point-to- pointcommunicationwhereithasbeenenoughtotreatonlyoneopticalchannelbetweenAliceandBob. Forinstance, 3 weneedtoallowthechoiceofwhichchanneltouseinthenextroundtodependontheoutcomesofLOCCoperations in previous rounds, in contrast to the paradigm of Takeoka et al. [12, 13]. To make this more precise, let us define the general protocol. We assume that any classical communication over the network is freely usable. Suppose that Alice (A) and Bob (B) call a quantum internet protocol to share a re- sourceforquantumcommunication,unconditionallysecurekeyorquantumentanglement,overthequantumnetwork. Accordingly, the quantum internet protocol determines a subnetwork to supply the resource to Alice and Bob. The subnetwork is characterized by a directed graph G = (V,E) with a set V of vertices and a set E of edges, where the vertices of G represent Alice’s node, Bob’s node and intermediate nodes Ck in the subnetwork, i.e., k=1,2,...,n { } V = A,B,C1,C2,...,Cn , and an edge ε = v1 v2 E of G for v1,v2 V specifies a quantum channel v1→v2 { } → ∈ ∈ N to send a quantum system from node v to node v in the subnetwork. Then, the most general protocol proceeds in 1 2 an adaptive manner as follows [c.f. Fig. 1 (b) which exemplifies a linear network with n=4]. The protocol starts by preparingthewholesysteminaseparablestateρˆA1BC1C2...Cn andthenbyusingaquantumchannelNe1 withe1 ∈E. ThisisfollowedbyarbitraryLOCCamongallthenodes,whichgivesanoutcomek andaquantumstateρˆABC1C2...Cn with probability pk1. In the second round, depending on the outcome k1, a node1uses a quantum channekl1Nek1 with e E,followedbyLOCCamongallthe nodes. This LOCCgivesanoutcomek andaquantumstateρˆABC1C2...Cn wki1th∈probability p . Similarly, in the i-th round, according to the previous o2utcomes k := k ..k.2kk1k (with k0 := 1), the protko2|cko1l uses a quantum channel Neki−1 with eki−1 ∈ E, followed by LOCi−C1 provii−d1ing a2qu1antum state ρˆAkiBC1C2...Cn with a new outcome ki with probability pki|ki−1. After a finite number of rounds, say after an l-th round, the protocol must present ρˆAklB = TrC1C2...Cn(ρˆAklBC1C2...Cn) close to a target state τˆdAkBl with rank dkl in the sense of ||ρˆAklB −τˆdAkBl ||1 ≤ ǫ for ǫ > 0, from which Alice and Bob can distil log2dkl secret bits for the purpose of the unconditionally secure communication or log2dkl ebits for the purpose of the quantum teleportation. After all, the protocol results in presenting log2dkl secret bits or ebits with probability pkl by using quantum channels {Neki}i=0,1,...,l−1, where pki :=pki|ki−1...pk3|k2pk2|k1pk1. For this general adaptive protocol, our main result is described as follows. Let us divide set V into two disjoint sets, V including A and V including B, satisfying V =V V and V = V V [c.f. Fig. 1 for the examples]. If A B A B B A Neki is a channel between a node in VA and a node in VB, w\e write ki ∈ KVA\↔VB. For example, k1 ∈ KVA↔VB in Fig. 1 (b). Then, for any choice of V and V , the most general protocol has a limitation described by A B l−1 1 pkllog2dkl ≤ 1 16√ǫ pkiEsq(Neki)+4h(2√ǫ), (1) Xkl − Xi=0ki∈KXVA↔VB  where h is the binary entropy function with a property of lim h(x)=0 and E ( ) is the squashed entanglement x→0 sq N of channel N [12, 13]. This bound is reduced to klpkllog2dkl ≤ il−=10 ki∈KVA↔VB pkiEsq(Neki) for ǫ →0. The bound (1) is obtained by regarding the general mPulti-party protocolPas bipPartite communication between V and V A B and by applying the TGW bound to the bipartite one (see Appendix for the proof). Since the bound holds for any choice of V , the bound shows that the average of the obtained secret bits or ebits is most tightly bounded by the A choice of V that minimizes the right-hand side of Eq. (1). A As an instructive application of the bound (1), we first derive an upper bound for a linear optical network, which includes intercity QKD protocols and quantum repeater protocols. Here the goal of Alice and Bob, separated over distanceL,istosharesecretbitsorebitsbyutilizingintermediatenodes Cj . Forsimplicity,supposethatthey j=1,...,n { } are located at regular intervals and connected with optical fibres with transmittance ηL0 :=e−L0/latt for attenuation length l and L :=L/(n+1) with each other. Then, since they can use only the same optical channel connecting att 0 ftohrewadhjiachceTntakneoodkeaseattable.sht,aavlelathlreeacdhyandneerlisve{dNaenki}uip=p0e,1r,.b..,ol−u1ndmounsttbheetshqeuasashmeedleonsstayncghlaenmneenltwoifththteracnhsamnintetlan[1c2e,η1L30]., This implies Esq(Neki)≤2log2[(1+ηL0)/(1−ηL0)] for any of the channels {Neki}i=0,1,...,l−1, where the factor 2 in thefrontcomesfromthefactthatasingleuseofanopticalchannelfortransmissionofanopticalpulsecorrespondsto the sending of two optical modes associatedwith its polarizationdegrees of freedom. Then, the bound (1) is reduced to l−1 1 1+η hlog2dklikl ≤ 1 16√ǫ2log2(cid:18)1 ηL0(cid:19) pki +4h(2√ǫ), (2) −  − L0 Xi=0ki∈KXVA↔VB  wherehfklikl representstheaverageoffunctionfkl overkl,thatis,hfklikl := klpklfkl. ForthechoiceofVA ={A} and VB = {C1,C2,...,Cn,B} (VA = {A,C1,C2,...,Cn} and VB = {B}),P il−=10 ki∈KVA↔VB pki represents the P P 4 averagenumber hmkAl↔C1ikl (hmkCln↔Bikl) oftimes the opticalchannelbetweenAlice andnode C1 (betweennode Cn andBob)isused. Similarly,forthechoiceofV = A,C1,...,Cj andV = Cj+1,...,Cn,B forj =1,2,...,n 1, A B { } { } − il−=10 ki∈KVA↔VB pki describestheaveragenumberhmCklj↔Cj+1ikl ofchannelusesbetweennode Cj andnode Cj+1. HPenceP, Eq. (2) gives 1 1+η hlog2dklikl ≤ 1 16√ǫ(cid:20)2min{hmkAl↔C1ikl,hmCkl1↔C2ikl,...,hmkCln↔Bikl}log2(cid:18)1 ηL0(cid:19)+4h(2√ǫ)(cid:21). (3) − − L0 Since hmkAl↔C1ikl +hmCkl1↔C2ikl +...+hmkCln↔Bikl = l, we have min{hmkAl↔C1ikl,hmCkl1↔C2ikl,...,hmkCln↔Bikl} ≤ l/(n+1), which concludes 1 2l 1+η hlog2dklikl ≤ 1 16√ǫ(cid:20)n+1log2(cid:18)1 ηL0(cid:19)+4h(2√ǫ)(cid:21). (4) − − L0 Ibnyp2a(rnti+cu1la)−r,1tlhoigsb[(o1u+ndηsho)/w(s1thaηtth)]efaovrerǫage0s,ecwrheticbhitissoarppebroitxsimpeartecdhatnonbeleu4s[e(,nh+log12)dlnkl2i]k−l1/ηl,arfeourpLperbo1u.nTdhede 2 L0 − L0 ≃ L0 0 ≫ bound (4) is tight enough to show that the existing intercity QKD protocols and quantum repeater protocols are pretty good in the sense that they have the same scaling with this simple bound. To show this, let us first compare the bound (4) with the intercity QKD protocols [17–19]. This class of QKD protocolsleadstoasquarerootimprovementinthesecretkeyrateoverconventionalQKDschemes(withoutquantum repeaters) bounded by the TGW bound. Nonetheless, it can be obtained without the need of matter quantum memoriesorquantumerrorcorrection[19],whichisinastrikingcontrasttoquantumrepeaters[20–34]. Inparticular, those protocolsare modifications of the measurement-device-independentQKD (mdiQKD) [35] andall of them use a singleuntrustedintermediatenode C inthe middle ofcommunicatorsAlice andBob. NodeC sharesopticalchannels with Alice and Bob, whose transmittance is described by η . Then, using matter quantum memories at node C L/2 [17, 18] or using only optical devices at node C [19], the protocols present a secret bit per about η−1 uses of optical L/2 channels between Alice and node C and between Bob and node C. This implies that the average secret bits of these protocolsperchanneluseareinthe orderofη . However,thisisexactlythe samescalingofthe bound(4), because L/2 the bound (4) is proportional to η = η for n = 1, ǫ 0 and L 1. In fact, this is easily confirmed by seeing L0 L/2 ≃ 0 ≫ Fig. 2 (a). Next, let us compare the bound (4) with the performance of achievable quantum repeater protocols. Actu- ally, there are many quantum repeater schemes [20–34], depending on the assumed devices of the repeater nodes C1,C2,...,Cn . For instance, a protocol assumes repeater nodes equipped with atomic-ensemble quantum memo- { } ries as well as optical devices [21, 27]. To obtain better scaling, instead of the atomic-ensemble quantum memories, another protocols [20, 25, 26, 30, 32] use matter qubits satisfying not only DiVincenzo’s five criteria for a universal quantum computation but also his extra criterion on the efficient coupling with single photons [36]. Moreover, re- cently, there is even an all-photonic scheme [33] that does not use matter quantum memories at all and works by using only optical devices. However, since our aim here is to show the existence of a quantum repeater protocol that has the same scaling with the bound (4) in principle, let us introduce an idealized qubit-based protocol which uses a noiseless quantum computer with the function of the perfect coupling with single photons at each repeater node. In the idealized qubit-based protocol, (i) a node X V except for B begins by producing a single photon which ∈ is in maximally entangled state Φ+ = (0 H + 1 V )/√2 with a qubit of the local quantum computer, where | i | i| i | i| i H , V is an orthonormal basis for the polarization degrees of freedom of the single photon and 0 , 1 is a {| i | i} {| i | i} computational basis of the qubit. (ii) Then, the node X except for B sends its right-hand-side adjacent node the single photon through the optical fibre with transmittance η . (iii) On receiving the photon from the left-hand-side L0 adjacent node, the node X except for A performs a quantum non-demolition (QND) measurement to confirm the successful arrival of the single photon, and announces the measurement outcome via a heralding signal. If this QND measurementprovesthe successfularrivalofthe singlephoton,the nodeX transfersthe quantumstateofthephoton into a qubit of the local quantum computer faithfully, establishing a maximally entangled state between the node X and the left-hand-side adjacent node. (iv) If the node X except for B is informed of the loss of the sent photon in the transmission by the heralding signal from the right-hand-side adjacent node, the node X and its right-hand-side adjacent node repeat steps (i)-(iii). (v) If everynode shares a maximally entangledstate with the adjacent nodes, all the repeater nodes C1,C2,...,Cn apply the Bell measurement to a pair of local qubits that have been entangled { } with qubits inthe adjacentrepeater nodes. This givesAlice andBoba pair ofqubits in a maximally entangledstate. Let us estimate the performance of this idealized qubit-based protocol. Since the entanglement generation process (i)-(iii) is repeated until a single photon sent in step (ii) survives over the fibre transmission with transmittance η , L0 the average of the number m of the channel uses to obtain the entanglement between adjacent nodes in step (iii) is ∞ m(1 η )m−1η = η−1. If we regard the entanglement generation process (i)-(iii) as a single round of m=1 − L0 L0 L0 P 5 (a) (b) /G()lÚÚ kkll --11-5050 (I(II)) (III) /G()lÚÚ kkll --11-5050 n=10 n=n2=030 g 10 (IV) g 10 n=0 o -20 o -20 l l 0 200 400 600 800 0 2000 4000 6000 8000 10000 DistanceL [km] DistanceL [km] FIG. 2: Secret bits or ebits per channel use, hGklikl/l with Gkl := log2dkl, for protocols based on a linear network with total distance L. The protocols use intermediate nodes {C1,C2,...,Cn} connected by optical fibres each other and located at regular intervals, say L =L/(n+1). The solid curves represent achievable performance, while the dashed curves are our 0 generalupperbounds(4)forthelinearnetwork,2(n+1)−1log [(1+η )/(1−η )],forvariousn. Inpanel(a),weprovidethe 2 L0 L0 performanceofmdiQKDprotocols[19,35]usingonlyasingleintermediatenode(n=1)equippedwithfeasibleopticaldevices. Lines(II)and(IV)representtheall-photonicintercityQKDprotocol[19]andtheoriginalmdiQKDprotocol[35],respectively. These lines just refer to the performance given in Fig. 3 of Ref. [19], where a collection of the state-of-art optical devices such assingle-photonsources,activefeedforwardtechniquewithanopticalswitchandsingle-photondetectorsisassumedtobeused (c.f. [19] for the details). The key rate scales linearly with η (i.e., the transmittance over distance L) for the mdiQKD [35], L butitscaleslinearlywiththesquarerootofη fortheall-photonicintercityQKD[19]. Inaddition,weshowourgeneralbound L (4) for n=1 as line (I) and the TGW bound [12] (corresponding to our bound with n=0) as line (III). Comparing lines (I) and (II), we can see that the all-photonic intercity QKD protocol has the same scaling with our general bound (4) for n=1. In panel (b), for various n, we provide the performance of the idealized qubit-based quantum repeater protocol introduced in the main text, (n+1)−1η =(n+1)−1η , as solid lines and our bound (4) as dashed curves. We can see that there is L0 L/(n+1) essentially noscaling gap between our bound (4) and theidealized qubit-basedprotocol. the protocol and the process is executed between adjacent repeater nodes in parallel independently, the idealized qubit-based protocol should present a pair of qubits in a maximally entangled state for the total number l of the rounds with l=(n+1)η−1 in a manner arbitrary close to a deterministic process. Therefore, the averagesecret bits L0 orebits ofthe idealizedqubit-basedprotocolper channeluse is (n+1)−1η , whichis exactly the same scalingofthe L0 bound (4). This fact is also easily confirmed by seeing Fig. 2 (b). Since the existingquantumrepeaterprotocols[20–34]arebasedonmorepracticaldevicesthanthe idealizedqubit- basedprotocol,theymustbelessefficientthantheidealizedqubit-basedprotocol,owingtomoreimperfectionscaused by the practical devices. However,there are schemes [25, 26, 30, 32, 33] whose performance is essentially determined by distance L even under the use of such more practical devices similarly to the idealized qubit-based protocol as 0 well as our bound (4). In other words, the quantum repeater protocols [25, 26, 30, 32, 33] have no scaling gap with our bound (4). Wehaveseenthatourbound(1)issimplebutpowerfulenoughtoderiverate-losstradeoffs(4)withthesamescaling withexistingintercityQKDprotocolsandquantumrepeaters. Notethatwehaveassumedthattheintermediatenodes C1,C2,...,Cn are located at regular intervals, but this assumption is unnecessary. In particular, similarly to the { } derivationof Eq.(4), from ourbound (1), it is notdifficult to obtain rate-losstradeoffsfor anylinear optical network where the intermediate nodes are not necessarily positioned at regular intervals, and the existing intercity QKD protocolsandquantumrepeaterprotocolsarestillshowntohavethesamescalingwiththetradeoffs. Moreover,ifthe future quantum internet protocolwas programmedto always find out a linear network as the subnetwork G over the quantum internet by using an algorithm for the shortest path problem, our bound for the linear network would help to run the algorithm via determining the weights for all the edges associated with optical channels. This application willalsoholdevenifthequantuminternetprotocolusestreenetworksasthesubnetworkGinsteadoflinearnetworks. More generally, the quantum internet protocol prefers to use a more general network topology as the subnetwork G. Even in this case, our bound is useful to determine the obtainable secret bits or ebits because they are always upper bounded by Eq. (1) for the minimum bipartition given by choosing V and V properly. A B Although we have just considered only the lossy channels as the examples of the applications of our bound (1), this is, of course, not only the case as long as the squashed entanglement of the channel in Eq. (1) can be estimated for given channels. Even though in Fig. 2, we have plotted only the results for a linear chain of pure-loss channels, it should be noted that the TGW bound is very general and applies to any memoryless lossy channels (which may or may not be noisy) and, with the observation made in the present paper, to any network topology. While we have employed mainly the TGW bound in our paper, it should be noted that our reduction idea may be useful to derive 6 a good bound for a general network topology from a bound for point-to-point quantum communication generally. We have just begun to grasp full implications of our bound: For instance, its applications to the many-body physics regardedas a quantum networkand to a more complicatedquantum communicationprotocol—suchas a multi-party protocol like Ref. [39]—will be in a fair way to appear. We thank S. Guha, S. Pirandola, M. Takeoka and M. M. Wilde for valuable discussions about their papers [12– 15, 37]. K.A. thanks support from the Project UQCC by the National Institute of Information and Communications Technology. H.-K.L. acknowledges financial support from NSERC and CRC program. Note added.—During the preparationofthis paper,Pirandolauploadedarelatedpaper[37]onthe arXiv,basedon their recentpapers[14,15]. Ourresultsdo notsubsume,norarethey subsumedby the resultsin Ref.[37]. Pirandola assumed that the channels are stretchable whereas we do not make such an assumption [38]. On the other hand, for the specificcaseofapurelylossychannelthatisusedingeneratingthesimulationresultsinFig.2,Pirandola’sresult gives a better bound than ours. Appendix A: Proof for the main result (1) Here we provide the proof for the main result, that is, Eq. (1). Although here we focus on deriving the bound (1) for QKD protocols between Alice and Bob, the same technique can be applied for protocols to share entanglement between them, similarly to the TGW bound [12, 13]. Suppose that, with the help of other parties Ck in a quantum network, Alice and Bob share physical k=1,2,...,n { } systems in private state [40] A′A′′ B′B′′ H ⊗H γˆAB =UˆA′B′A′′B′′(Φ Φ ρˆA′′B′′)UˆA′B′A′′B′′† (A1) d | ih |A′B′ ⊗ with unitary operator UˆA′B′A′′B′′ := d−1 ij ij UˆA′′B′′, maximally entangled state Φ := i,j=0| ih |A′B′ ⊗ ij | iA′B′ d−1 ii /√d and orthonormal statesP ij for systems . In particular, Alice i=0 | iA′B′ {| iA′B′}i,j=0,1,...,d−1 HA′ ⊗ HB′ aPnd Bob obtain a private state through the following most general adaptive protocol: (i) Alice, Bob and par- ties Ck begin by preparing their physical systems 0 in a separable state ρˆABC1C2...Cn, where j := { }k=1,2,...,n H 1 H j j j j j and j representsthephysicalsystemheldbypartyX A,B,C1,C2,...,Cn . (HiiA)⊗InHthBe⊗fiHrstC1ro⊗uHndC,2p⊗ar·t·y·⊗XH1Cn A,BH,XC1,C2,...,Cn sends his/her subsystem ¯ to∈pa{rty Y 1 throughquan}- X|1 | ∈{ } H | tum channel NH¯X|1→H˜Y|1 with isometric extension UH¯X|1→H˜Y|1⊗HE1 for environment system HE1, which provides a refreshed description of the whole system, 0′|1 with 0′|1 = 0 ˜ , 0 = 0′|1 ¯ and 0′|1 = 0 H HY|1 HY|1⊗HY|1 HX|1 HX|1 ⊗HX|1 HZ HZ for any party Z except for parties X 1 and Y 1. This is followed by an LOCC operation, which presents a re- | | newed entire system 1|1 in state ρˆABC1C2...Cn with probability p . Let be a system that purifies the state H k1 k1 HRk1 ρˆABC1C2...Cn, providing pure-state expression ρˆ . (iii) Similarly, in the ith round (i = 2,3,...,l), k1 | k1iABC1C2...CnRk1 depending on the previous outcomes ki−1 := ki−1 k1 (with k0 := 1), for given entire system (i−1)|ki−2, party X|ki−1 ∈{A,B,C1,C2,...,Cn} sendshis/hersubsy··st·emH¯X|ki−1 topartyY|ki−1 ∈{A,B,C1,C2H,...,Cn}through quantum channel H¯X|ki−1→H˜Y|ki−1 with isometric extension H¯X|ki−1→H˜Y|ki−1⊗HEki−1 for environment system HEki−1, which updNates the description of the whole system as H(Ui−1)′|ki−1 with HY(i−|k1i−)′1|ki−1 =HY(i−|k1i)−|1ki−2 ⊗H˜Y|ki−1, HX(i−|k1i)−|k1i−2 = HX(i−|k1i)−′|1ki−1 ⊗H¯X|ki−1 and HZ(i−1)′|ki−1 = HZ(i−1)|ki−2 for any party Z except for parties X|ki−1 and Y ki−1. This is followed by an LOCC operation, providing an entire system i|ki−1 in state ρˆAkBC1C2...Cn with | H i probability pki|ki−1. Let HRki be a system that purifies the state ρˆkAiBC1C2...Cn, presenting pure-state expression |ρˆkiiABC1C2...CnRki. (iv) Finally,i.e.,inthe lthround,Alice andBobobtainstateρˆAklBC1C2...Cn closetoprivatestate γˆAB for integer dk ( 1). dkl l ≥ From the definition, the final state ρˆABC1C2...Cn should be close to private state γˆAB, i.e., ρˆAB γˆAB ǫ for kl dkl || kl − dkl||1 ≤ ǫ>0, where we define ρˆX :=Tr (ρˆXY). From the continuity of the squashed entanglement [41], this implies Y |EsHqAl|kl−1:HBl|kl−1(ρˆAklB)−EsHqAl|kl−1:HBl|kl−1(γˆdAkBl)|≤16√ǫlogd′kl +4h(2√ǫ), (A2) where d′ := min dim( l|kl−1),dim( l|kl−1) , h(x) := xlog x (1 x)log (1 x) and EX:Y(ρˆXY) is the kl { HA HB } − 2 − − 2 − sq squashed entanglement between systems X and Y in state ρˆXY [42]. Since d′kl = dkl without loss of generality 7 and EsHqAl|kl−1:HBl|kl−1(γˆdAkBl)≥logdkl [41], we have logdkl ≤ 1 116√ǫ(EsHqAl|kl−1:HBl|kl−1(ρˆAklB)+4h(2√ǫ)). (A3) − Our proof for Eq. (1) is made by regarding the general multi-party protocol as bipartite communication and by applying the technique of the TGW bound [12] to the bipartite one. Hence, let us divide the set of parties A,B,C1,C2,...,Cn (=: )intotwodisjointgroups and (= )thatincludepartiesAandB,respectively. A B A W{ edefine r := } Pr and r := rP. InaddPition,wPe\rPegardk ask K (k K ) if X k HPA an⊗dXY∈kPAHX H(ifPXB k ⊗X∈PBHaXnd Y k ) for Ci−=1 A oir−C1 ∈= Bin.|PIAn whi−a1t ∈folloowust|,PwAe i−1 C i−1 C i−1 C i−1 C deriv|e ineq∈uaPlities for t|wo ca∈sePs, k |K ∈ Pand k | K ∈ P.\P i−1 ∈ in|PA i−1 ∈ out|PA Let us consider an ith round with ki−1 ∈ Kin|PA. In this case, the channel NH¯X|ki−1→H˜Y|ki−1 should be regarded as just a localchannelfor the bipartite communicationbetween and . To make this clearer,let us first assume A B X k and Y k . Then, we have P P i−1 A i−1 A | ∈P | ∈P pki|ki−1EsHqiA|ki−1:HiB|ki−1(ρˆAkiB)≤ pki|ki−1EsHqiP|kAi−1:HiP|kBi−1(ρˆkAiBC1C2...Cn) (A4) Xki Xki EsHqP(iA−1)′|ki−1:HP(iB−1)′|ki−1( H¯X|ki−1→H˜Y|ki−1(ρˆkABC1C2...Cn)) (A5) ≤ N i−1 EHP(iA−1)|ki−2:HP(iB−1)|ki−2(ρˆABC1C2...Cn). (A6) sq k ≤ i−1 The first inequality is derived from the fact that the squashed entanglement does not increase under partial traces. ThesecondinequalitycomesfromthefactthatthesquashedentanglementdoesnotincreaseonaverageunderLOCC. The final inequality states that the squashed entanglement does not increase under any local quantum channel. The same inequality is obtained if we begin by assuming X k and Y k . i−1 B i−1 B | ∈P | ∈P Let us consider an ith round with ki−1 ∈Kout|PA. In this case, NH¯X|ki−1→H˜Y|ki−1 is a channel connecting parties and nontrivially, which should put a limitation on the communication. To make this more precise, we first A B aPssume XPk and Y k . Then, we have i−1 A i−1 B | ∈P | ∈P pki|ki−1EsHqiA|ki−1:HiB|ki−1(ρˆAkiB)≤ pki|ki−1EsHqiP|kAi−1:HiP|kBi−1(ρˆkAiBC1C2...Cn) (A7) Xki Xki EsHqP(iA−1)′|ki−1:H(PiB−1)′|ki−1( H¯X|ki−1→H˜Y|ki−1(ρˆAkBC1C2...Cn)) (A8) ≤ N i−1 =EsHqP(iA−1)′|ki−1:H(PiB−1\)(′Y|k|ki−i−11)⊗HY(i−|k1i)−|k1i−2⊗H˜Y|ki−1(UH¯X|ki−1→H˜Y|ki−1⊗HEki−1(|ρˆki−1iABC1C2...CnRki−1)) (A9) ≤EsHqP(iA−1)′|ki−1⊗HP(iB−1\)(′Y|k|ki−i−11)⊗HY(i−|k1i)−|k1i−2⊗HRki−1:H˜Y|ki−1(UH¯X|ki−1→H˜Y|ki−1⊗HEki−1(|ρˆki−1iABC1C2...CnRki−1)) +EsHqP(iA−1)′|ki−1⊗H˜Y|ki−1⊗HEki−1:HP(iB−1\)(′Y|k|ki−i−11)⊗HY(i−|k1i)−|k1i−2(UH¯X|ki−1→H˜Y|ki−1⊗HEki−1(|ρˆki−1iABC1C2...CnRki−1)) (A10) =EsHqP(iA−1)′|ki−1⊗HP(iB−1\)(|Yk|ik−i2−1)⊗HY(i−|k1i)−|k1i−2⊗HRki−1:H˜Y|ki−1(NH¯X|ki−1→H˜Y|ki−1(|ρˆki−1iABC1C2...CnRki−1)) +EsHqP(iA−1)′|ki−1⊗H¯X|ki−1:HP(iB−1\)(|Yk|ik−i2−1)⊗HY(i−|k1i)−|k1i−2(|ρˆki−1iABC1C2...CnRki−1) (A11) Esq( H¯X|ki−1→H˜Y|ki−1)+EsHqP(iA−1)|ki−2:HP(iB−1)|ki−2(ρˆkABC1C2...Cn). (A12) ≤ N i−1 The first inequality is derived from the fact that the squashed entanglement does not increase under partial traces. ThesecondinequalitycomesfromthefactthatthesquashedentanglementdoesnotdecreaseonaverageunderLOCC. The third inequality is the application of Lemma 2 in Ref. [12] by regarding HP(iA−1)′|ki−1 as system A, H˜Y|ki−1 as system B , as system E , (i−1)′|ki−1 (i−1)|ki−2 as system B , and as system E . The final 1 HEki−1 1 HPB\(Y|ki−1) ⊗HY|ki−1 2 HRki−1 2 inequality follows from the definition [12] of the squashed entanglement of a quantum channel. The same inequality is derived if we start by assuming X k and Y k . i−1 B i−1 A | ∈P | ∈P 8 Therefore, using Eqs. (A6) and (A12) recursively and the fact that ρˆABC1C2...Cn is separable, we obtain 1 pklEsHqAl|kl−1:HBl|kl−1(ρˆAklB)= pkl−1 pkl|kl−1EsHqAl|kl−1:HBi|kl−1(ρˆAklB) (A13) Xkl kXl−1 Xkl ≤ pkl−1Esq(NH¯X|kl−1→H˜Y|kl−1) kl−1∈XKout|PA + pkl−1EsHqP(lA−1)|kl−2:HP(lB−1)|kl−2(ρˆAklB−C11C2...Cn) (A14) kX l−1 l ≤ pki−1Esq(NH¯X|ki−1→H˜Y|ki−1). (A15) Xi=1ki−1∈XKout|PA Combined with Eq. (A3), this concludes l pkllogdkl ≤ 1 116√ǫ pki−1Esq(NH¯X|ki−1→H˜Y|ki−1)+4h(2√ǫ). (A16) Xkl − Xi=1ki−1∈XKout|PA  This is equivalent to Eq. (1). [1] H.J. Kimble, Nature453, 1023 (2008). [2] T. D. Ladd et al.,Nature 464, 45 (2010). [3] H.-K.Lo, M. Curty,and K.Tamaki, NaturePhoton. 8, 595 (2014). [4] C. H. Bennett and G. Brassard, Proceedings of IEEE International Conference on Computers, Systems, and Signal Pro- cessing, Bangalore, India, IEEE Press (New York),1984, pp.175-179. [5] C. H. Bennett,Phys. Rev.Lett. 68, 3121 (1992). [6] W.-Y.Hwang, Phys. Rev.Lett. 91, 057901 (2003). [7] H.-K.Lo, X. Ma, and K.Chen, Phys. Rev.Lett. 94, 230504 (2005). [8] X.-B. Wang,Phys. Rev.Lett. 94, 230503 (2005). [9] K.Azuma et al.,Phys. Rev.A 80, 060303(R) (2009). [10] K.Azuma and G. Kato, Phys.Rev.A 85, 060303(R) (2012). [11] T. Sasaki, Y.Yamamoto, and M. Koashi, Nature509, 475 (2014). [12] M. Takeoka, S. Guha,and M. M. Wilde, Nat. Commun. 5, 5235 (2014). [13] M. Takeoka, S. Guha,and M. M. Wilde, IEEE Trans. Inf. Theory 39(3), 733 (2014). [14] S.Pirandola, R.Laurenza, C. Ottaviani, and L. Banchi, arXiv:1510.08863. [15] S.Pirandola and R.Laurenza, arXiv:1512.04945. [16] N.Gisin, G. Ribordy,W. Tittel and H.Zbinden,Rev.Mod. Phys.74, 145 (2002). [17] S.Abruzzo, H.Kampermann, and D. Bruß, Phys. Rev.A 89, 012301 (2014). [18] C. Panayi, M. Razavi, X.Ma, and N. Lu¨tkenhaus,New J. Phys.16, 043005 (2014). [19] K.Azuma, K. Tamaki, and W.J. Munro, Nat. Commun. 6, 10171 (2015). [20] H.J. Briegel, W. Du¨r, J. I.Cirac, P. Zoller, Phys.Rev.Lett. 81, 5932 (1998). [21] L.-M. Duan,M. D.Lukin,J. I.Cirac, and P. Zoller, Nature414, 413 (2001). [22] P.Kok, C. P. Williams, and J. P. Dowling, Phys.Rev.A 68, 022301 (2003). [23] L. Childress, J. M. Taylor, A. S.Sørensen, and M. D.Lukin,Phys. Rev.Lett. 96, 070504 (2006). [24] P.van Loock, et al.,Phys. Rev.Lett. 96, 240501 (2006). [25] L. Jiang et al.,Phys.Rev. A 79, 032325 (2009). [26] W. J. Munro, K. A.,Harrison, A. M. Stephens,S. J. Devitt,and K.Nemoto, Nat.Photon. 4, 792 (2010). [27] N.Sangouard, C. Simon, N.de Riedmatten,and N.Gisin, Rev.Mod. Phys.83, 33 (2011). [28] K.Azuma, H. Takeda, M. Koashi, and N.Imoto, Phys.Rev.A 85, 062309 (2012). [29] M. Zwerger, W. Du¨r, and H. J. Briegel, Phys. Rev.A 85, 062326 (2012). [30] W. J. Munro, A.M. Stephens,S.J. Devitt,K. A.Harrison, and K. Nemoto, Nat. Photon. 6, 777 (2012). [31] Y.Li, S. D. Barrett, T. M. Stace, and S. C. Benjamin, New J. Phys.15, 023012 (2013). [32] A.Grudkaet al., Phys.Rev.A 90, 062311 (2014). [33] K.Azuma, K. Tamaki, and H.-K.Lo, Nat. Commun. 6, 6787 (2015). [34] W. J. Munro, K. Azuma,K. Tamaki, and K. Nemoto, IEEE J. Sel. Top. Quant.Electron. 21(3), 6400813 (2015). [35] H.-K.Lo, M. Curty,and B. Qi, Phys. Rev.Lett. 108, 130503 (2012). [36] D.P. DiVincenzo, arXiv:quant-ph/0002077. 9 [37] S.Pirandola, arXiv:1601.00966. [38] Notethattheboundbasedontherelativeentropyofentanglementinpapers[14,15,37]canbeusedonchannelsforwhich theteleportation correction operations suitably commute with thechannel. This is a feature held by Pauli channels (e.g., depolarizing and dephasingchannels), erasurechannels andGaussian channels. By contrast, amplitudedampingchannels are not stretchable [15]. [39] K.P. Seshadreesan, M. Takeoka, M. M. Wilde, arXiv:1503.08139. [40] K.Horodecki, M. Horodecki, P. Horodecki, and J. Oppenheim,Phys.Rev.Lett. 94, 160502 (2005). [41] M. Christandl, The Structure of Bipartite Quantum States: Insights from Group Theory and Cryptography. PhD thesis (Universityof Cambridge, 2006). [42] M. Christandl and A.Winter, J. Math. Phys.45, 829 (2004).