Linear programs for entanglement and key distribution in the quantum internet
Authors:
Preprint
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
This publication has 55 references indexed in Scilit:
- Relative Entropy Bounds on Quantum, Private and Repeater CapacitiesCommunications in Mathematical Physics, 2017
- Squashed entanglement and approximate private statesQuantum Information Processing, 2016
- Path selection for quantum repeater networksNetworking Science, 2013
- 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
- Primal-dual approximation algorithms for integral flow and multicut in treesAlgorithmica, 1997
- Approximation Algorithms for Steiner and Directed MulticutsJournal of Algorithms, 1997
- The geometry of graphs and some of its algorithmic applicationsCombinatorica, 1995
- An O(n 3 L) potential reduction algorithm for linear programmingMathematical Programming, 1991