Report

Quantum Network Coding - How can network coding be applied to quantum information? Harumichi Nishimura (Nagoya U.) June 9th, 2013 NetCod 2013 @Calgary Quantum Network Coding: Motivations • Quantum communication – point-to-point case – extension to networks – applications (unconditionally secure key distribution, powerful verification systems, etc.) – expensive resource • Network coding [Ahlswede-Cai-Li-Yeung00] – efficient communication on networks – many other merits (wireless networks, secure communication, etc.) Butterfly Network 1 1 2 1 2 2 1 +2 1 1 +2 2 2 2 1 +2 1 1 Quantum Butterfly 1 1 2 1 2 2 quantum bit 1 +2 1 quantum channel 1 +2 2 2 2 1 +2 1 1 quantum operation Outline of This Talk • Basics on quantum information • Basic setting – One-shot case – Asymptotic case – Network coding vs. routing • With extra resources – Classical communication – Entanglement Quantum States Quantum Mechanics Mathematical Representation quantum system Hilbert space quantum state unit vector time evolution unitary operator measurement projectors Qubit system 2 := two dim. complex inner product space with orthonormal basis |0 and |1 ≅ ℂ2 Bloch sphere |0 = 0 + |1 ≅ | | = cos |0 + sin |1 ≅ (cos , cos sin , sin sin ) |0 +|1 |1 |0 +|1 Multiple Qubits Two-qubit states can be represented by a unit vector in 2 ⊗ 2 spanned by |00 ≔ |0 ⊗ |0 , |01 , |10 , and |11 = 00 + 01 + 10 + |11 ( 0 + β 1 ) ⊗ (|0 + |1 ) EPR pair |Φ+ ≔ EinsteinPodolskiy -Rosen 1 2 |00 + 1 2 The first and second qubits are entangled |11 N-qubit states can be represented by a unit vector in 2⊗ ≔ 2 ⊗ 2 ⊗ ⋯ ⊗ 2 |Φ + Measurements • Physical process to obtain classical information from quantum states (in general, the states are changed by the measurement) • Described by projectors corresponding to an orthonormal basis = 0 + |1 measurement in basis {|0 , |1 } obtains 0 with 0 2 = ||2 obtains 1 with 1 2 = ||2 inner product between |1 and | • Orthogonal states are perfectly distinguishable |Φ+ = |00 + |11 / 2 |Φ− = |00 − |11 / 2 |Ψ + = |01 + |10 / 2 |Ψ − = |01 − |01 / 2 orthogonal perfectly distinguishable by the measurement in the basis (Bell basis) {|Φ+ , |Φ− , |Ψ + , |Ψ − } Quantum Operations & Channels • In a narrow sense, a quantum operation – transforms N-qubit states into N-qubit states – is represented by a unitary operator • In this talk, a quantum channel with capacity N is the identity operator on the N-qubit states (noiseless) • More generally, a quantum operation is implemented by 3 steps 1. 2. 3. Add extra qubits (ancilla) prepared in a fixed state Apply a unitary to the composite system (input+ancilla) Take some part of the composite system as output input | ancilla |0000 U output NOTE: Even a general operation is represented by a linear operator. Two Quantum Tools • Quantum Teleportation [BBCJPW93] – Alice can send a qubit to Bob using two bits and an EPR pair between Alice and Bob |Φ+ = |00 + |11 / 2 = | • Dense coding [Bennett-Wiesner92] – Alice can send two bits to Bob using a qubit and an EPR pair between Alice and Bob |Φ+ = |00 + |11 / 2 | = Dense Coding Dense coding [Bennett-Wiesner92] Alice can send two bits to Bob using a qubit and an EPR pair between Alice and Bob |Φ+ = |00 + |11 / 2 1st stage: Alice’s local operation = 1 Alice applies bit-flip = 1 Alice applies phase-flip =00 |Φ + = = |00 + |11 / 2 =10 |Ψ + = |10 + |01 / 2 =01 |Φ− = |00 − |11 / 2 =11 |Ψ − = −|10 + |01 / 2 0 1 : bit-flip 1 0 |0 + |1 orthogonal = |1 + |0 1 0 : phase-flip 0 −1 |0 + |1 2nd stage: Alice sends her part of the pair and Bob measures the pair in basis {|Φ+ , |Φ− , |Ψ + , |Ψ − }. |0 − |1 No-Cloning Theorem [Wootters-Zurek82] • There is no quantum operation that clones a given state. input | output | ⊗ | U ancilla | • We can copy a bit like |0 ↦ 00 , 1 ↦ |11 but this is not quantum copying: | = 1 |0 2 + 1 |1 2 ↦ |Φ+ = 1 |00 2 + 1 |11 2 Basic Setting Before Basic Setting • This talk focuses on multiple unicast networks – By the non-cloning theorem, quantum analogue of multicast networks is not straightforward [Shi-Soljanin06, Kobayashi-Le Gall-N-Roetteler10] our target |1 , |2 |1 |1 , |2 |1 , |2 | 2 | 2 |1 Basic Setting [Hayashi-Iwama-N-Raymond-Yamashita07] • Quantum network N – directed acyclic graph with source nodes 1 , 2 , … , and target nodes 1 , 2 , … , – has a qubit | – each edge is a quantum channel with capacity 1 (while any two neighboring nodes u and v may have d edges, in which we often say edge (u,v) has capacity d) – each node v can apply any quantum operation that transforms input qubits from the incoming edges into output qubits to the outgoing edges input v ancilla Uv • N is solvable if there is a choice of quantum operations such that every | can be recovered at – we can define the “approximate” version where each target can recover the qubit with some closeness factor (fidelity). output Is Butterfly Quantumly Solvable? |1 | 2 1 2 quantum bit |0 | quantum operation |1 quantum channel 2 Bloch sphere 1 Is Butterfly Quantumly Solvable? |1 | 2 1 1 2 1 +2 1 +2 2 1 1 2 1 +2 2 Is Butterfly Quantumly Solvable? |1 | 2 1 1 2 1 2 1 +2 1 +2 1 +2 Theorem: The butterfly network is not quantumly solvable (in fact, not quantumly solvable within some approximation factor) [HINRY07] 2 1 2 Ideas: Simplifying the Problem |1 |2 =| 1 2 |0 |1 2 1 Ideas: Simplifying the Problem |1 1 | 2 1 | Ideas: Simplifying the Problem |1 1 | If we want to distinguish whether = 0 or 1 faithfully, we cannot make the red quantum channel noiseless any more! 2 1 | Basic Setting: Asymptotic Case [Leung-Oppenheim-Winter10] • The previous setting is one-shot; one qubit at each node must be sent to the corresponding target node by a single use of the network 1 N if there is a2 • A rate (1 , 2 , … , ) is achievable in a network choice of quantum operations such that each can send 3 qubits to by uses of N. – negligible approximation errors are allowed – time-sharing (or fractional coding) is allowed Theorem: • The achievable rate region in the butterfly network is {(1 , 2 )|1 + 2 ≤ 1} [LOW10, Hayashi07] This is achieved by routing • The rates in some types of shallow networks are also achievable by routing [LOW10] 2 2 1 1 3 1 1 achieved by routing Basic Setting: Asymptotic Case [Leung-Oppenheim-Winter10] Theorem: • The achievable rate region in the butterfly network is {(1 , 2 )|1 + 2 ≤ 1} This is achieved by routing Reduction to quantum secret sharing [Gottesman00, IMQNTW05] n qubits |1 n qubits |2 A A C n uses B B C cannot recover quantum secret |1 |2 can recover quantum secret |1 |2 dim(C)≥dim(|1 |2 ) Network Coding vs. Routing NC rate ≥ × (Routing rate) 1 1 2 2 [Harvey-Kleinberg-Lehman04] 1 2 2 1 2 = =1 …….. …….. 1 Two Quantum Tools • Quantum Teleportation [BBCJPW93] – Alice can send a qubit to Bob using two bits and an EPR pair between Alice and Bob |Φ+ = |00 + |11 / 2 = | • Dense coding [Bennett-Wiesner92] – Alice can send two bits to Bob using a qubit and an EPR pair between Alice and Bob |Φ+ = |00 + |11 / 2 | = Quantum Teleportation 1st Stage: Alice measures her two qubits (after a unitary operation) |Φ+ = |00 + |11 / 2 | 2nd Stage: Alice sends her measurement results and Bob corrects the error 0 1 : bit error 1 0 |0 + |1 |1 + |0 = 1 0 : phase error 0 −1 |0 + |1 |0 − |1 = | | Coding vs. Routing (Quantum) QNC rate ≥ × (QRouting rate) [Jain-Franceschetti-Meyer11] 1. Send |Φ+ from p |1 1 1 | 2 2 2 …….. …….. | Coding vs. Routing (Quantum) 2. At , run 1st step of quantum teleportation |Φ+ shared |1 1 1 | 2 2 2 …….. …….. | Coding vs. Routing (Quantum) 3. Run 2nd step of quantum teleportation 1 1 1 1 1 1 |1 2 2 2 2 2 2 |2 …….. …….. | Coding vs. Routing (Quantum) QNC ) × (QRouting rate) QNC rate rate ≥ ≥ (2× (QRouting rate) 1 1 1 2 2 2 1 1 2 2 2 |2 1 1 …….. …….. 2 2 1 1 1 |1 2 2 | = Σ = Σ Coding vs. Routing (Quantum) QNC rate ≥ × (QRouting rate) capacity 2 1 1 1 2 2 2 1 1 2 2 2 |2 1 1 …….. …….. 2 2 1 1 1 |1 2 2 dense coding | = Σ = Σ Summary for Basic Setting • The butterfly network is classically solvable but not quantumly solvable (in both of the one-shot & asymptotic cases) – optimal quantum rate is achieved by routing – seems to be typical • There is an example such that the rate for quantum network coding is unboundedly better than that for quantum routing (using quantum teleportation & dense coding) – seems to be exceptional • OPEN: achievable rates for general graphs With Extra Resources With Free Classical Communication • This is the second-best for implementation: – Classical communication is much more “effective” than quantum (speed, noise-tolerance, money, etc.) • Setting – Free two-way classical communication: classical communication is freely available between any two nodes – Free one-way (forward/backward) classical communication: classical communication is freely available according to (or in the reverse direction to) the directed edges of the underlying graph Free Two-way Classical Communication Important fact: The underlying graph becomes “undirected” quantum teleportation 2 2 2 1 From Classical NC to Quantum NC Theorem: If rate (1 , 2 , … , ) is achievable in a classical network, then the same rate is also achievable in the corresponding quantum network under free classical communication [Kobayashi-Le Gall-N-Roetteler 09, 11] |Φ+ shared KLNR From Classical NC to Quantum NC |0 + |1 |0 + |1 |Φ+ =|00 +|11 shared KLNR = 1st step: Simulate classical protocol at each node introducing ancilla | | | , | | | + | | | + | | + | | , | | From Classical NC to Quantum NC |0 + |1 |0 + |1 |Φ+ =|00 +|11 shared KLNR | , | | + | | | + | = 2nd step: Remove the ancilla • measurement in Fourier basis • correction of phase errors using classical communication | | | | + | | = , | | From Classical NC to Quantum NC Theorem: If rate (1 , 2 , … , ) is achievable in a classical network, then the same rate is also achievable in the corresponding quantum network under free classical communication [Kobayashi-Le Gall-N-Roetteler 09, 11] Comments: • available to share EPR pairs or more general entangled states • the amount of classical communication is not much: at most 3 (which can be improved to 2) factors of quantum communication. OPEN (“converse” of Theorem): If rate (1 , 2 , … , ) is achievable in a quantum network under free classical communication, is the same rate also achievable in the corresponding “undirected” classical network? cf. [Conjecture: Li-Li04] In multiple unicast classical networks on undirected graphs, network coding does not allow any advantage over routing. Free Forward Classical Communication [LOW10] • We cannot reverse the directed edge – butterfly is not quantum solvable in this case • Still, we can use quantum teleportation 2 1 1/2 1/2 1 1 With Free Entanglement • Advantage – can prepare shared entangled states offline (i.e., at any time) • Setting – Free entanglement between any two nodes: any two nodes in networks share any entangled states at will – Free entanglement between neighboring nodes: any two neighboring nodes are allowed to share entanglement – Free entanglement between source nodes: any source nodes are allowed to shared entanglement Free Entanglement between Any Two Nodes Two observations by Leung-Oppenheim-Winter [LOW10] Proposition 1: Under free entanglement, the achievable rate for “quantum communication” in a quantum network is exactly 1/2 of that for “classical communication” in the same network. Rate for sending qubits Rate for sending bits 2 2 2 1 1 1 2 1 quantum channel Free Entanglement between Any Two Nodes Proposition 2: The achievable rate for “quantum communication” in a quantum network under free entanglement is at least that for “classical communication” in the corresponding classical network. 2 Rate for sending bits 1 1 2 1 Rate for sending qubits 1 1 classical channel 1 quantum channel Free Entanglement between Any Two Nodes Proposition 1: Under free entanglement, the achievable rate for “quantum communication” in a quantum network is exactly 1/2 of that for “classical communication” in the same network. Proposition 2: OPEN (conjectured in [LOW10]): The achievable rate for “quantum communication” in a quantum The achievable rate for “quantum communication” in a quantum network under free entanglement is at least that for “classical network under free entanglement is exactly that for “classical communication” in the corresponding classical network. communication” in the corresponding classical network. OPEN (conjectured in [LOW10]): The achievable rate for “classical communication” in a quantum network under free entanglement is exactly 1/2 of that for “classical communication” in the corresponding classical network. cf. proven for point-to-point channels [Cleve-van Dam-Nielsen-Tapp97] Other Cases Free entanglement between neighboring nodes 2 Same as the basic setting (no additional resources) [Hayashi07] 1 1 1 cf. [Satoh-Le Gall-Imai12] Free entanglement between source nodes 1 ? 1 1 cf. [Hayashi07, SoedaKinjo-Tuner-Murao11] Another Second Best: Entanglement + Classical Communication [Satoh-Le Gall-Imai12] • uses only (single) EPR pairs between neighboring nodes and free classical communication (motivated by quantum repeaters); does not use any quantum channel • does not introduce ancilla at each node |Φ+ shared SLI not quantum channels Summary & Future Works • Basic setting – even the butterfly is not quantum solvable – seems “liquid flow” different from classical case (while there exists some exception) – routing seems optimal but open to show for general graphs • With extra resources – under free classical communication, • the underlying quantum network becomes undirected • classical network coding can be converted into the quantum case – sending classical bits on the quantum network under free entanglement seems equivalent to that on the classical network (up to factor 2) • Future works – general theory: complexity, security, lossy channels, … – application-oriented: quantum networks whose sources are restricted (say, the Bennett-Brassard quantum key distribution (BB84))