Linear programs for entanglement and key distribution in the quantum internet
Open Access
- 20 March 2020
- journal article
- research article
- Published by Springer Nature in Communications Physics
- Vol. 3 (1) , 1-12
Abstract
Quantum networks will allow to implement communication tasks beyond the reach of their classical counterparts. A pressing and necessary issue for the design of quantum network protocols is the quantification of the rates at which these tasks can be performed. Here, we propose a simple recipe that yields efficiently computable lower and upper bounds on the maximum achievable rates. For this we make use of the max-flow min-cut theorem and its generalization to multi-commodity flows to obtain linear programs. We exemplify our recipe deriving the linear programs for bipartite settings, settings where multiple pairs of users obtain entanglement in parallel as well as multipartite settings, covering almost all known situations. We also make use of a generalization of the concept of paths between user pairs in a network to Steiner trees spanning a group of users wishing to establish Greenberger-Horne-Zeilinger states.Keywords
All Related Versions
Funding Information
- MEXT | Japan Science and Technology Agency (PRESTO Grant Number JPMJPR1861.)
This publication has 55 references indexed in Scilit:
- Multipartite secret key distillation and bound entanglementPhysical Review A, 2009
- Packing the Steiner trees of a graphNetworks, 2009
- Hardness and approximation results for packing steiner treesAlgorithmica, 2006
- Cuts, Trees and ℓ1-Embeddings of Graphs*Combinatorica, 2004
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithmsJournal of the ACM, 1999
- Approximation Algorithms for Steiner and Directed MulticutsJournal of Algorithms, 1997
- The geometry of graphs and some of its algorithmic applicationsCombinatorica, 1995
- Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channelsPhysical Review Letters, 1993
- Quantum cryptography based on Bell’s theoremPhysical Review Letters, 1991
- Maximal Flow Through a NetworkCanadian Journal of Mathematics, 1956