Quantum max-flow/min-cut

DOI10.1063/1.4954231zbMATH Open1341.90014arXiv1508.04644OpenAlexW2129971399MaRDI QIDQ3178315FDOQ3178315

Michael Freedman, Richard A. Stong, Shawn X. Cui, Or Sattath, Greg Minton

Publication date: 11 July 2016

Published in: Journal of Mathematical Physics (Search for Journal in Brave)

Abstract: The classical max-flow min-cut theorem describes transport through certain idealized classical networks. We consider the quantum analog for tensor networks. By associating an integral capacity to each edge and a tensor to each vertex in a flow network, we can also interpret it as a tensor network, and more specifically, as a linear map from the input space to the output space. The quantum max flow is defined to be the maximal rank of this linear map over all choices of tensors. The quantum min cut is defined to be the minimum product of the capacities of edges over all cuts of the tensor network. We show that unlike the classical case, the quantum max-flow=min-cut conjecture is not true in general. Under certain conditions, e.g., when the capacity on each edge is some power of a fixed integer, the quantum max-flow is proved to equal the quantum min-cut. However, concrete examples are also provided where the equality does not hold. We also found connections of quantum max-flow/min-cut with entropy of entanglement and the quantum satisfiability problem. We speculate that the phenomena revealed may be of interest both in spin systems in condensed matter and in quantum gravity.

Full work available at URL: https://arxiv.org/abs/1508.04644

Recommendations

• The asymptotics of quantum max-flow min-cut
• Matrix product states and the quantum max-flow/min-cut conjectures
• On quantum network coding
• Hypergraph min-cuts from quantum entropies
• A measure-theoretical max-flow-min-cut problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Quantum information, communication, networks (quantum-theoretic aspects) (81P45) Transportation, logistics and supply chain management (90B06)

Cites Work

• Maximal Flow Through a Network
• The large \(N\) limit of superconformal field theories and supergravity
• Black holes: complementarity or firewalls?
• Title not available (Why is that?)
• Title not available (Why is that?)
• Holographic Derivation of Entanglement Entropy from the anti–de Sitter Space/Conformal Field Theory Correspondence
• Finitely correlated states on quantum spin chains
• A practical introduction to tensor networks: Matrix product states and projected entangled pair states
• Positivity of the universal pairing in 3 dimensions
• A quantum Lovász local lemma
• Holographic quantum error-correcting codes: toy models for the bulk/boundary correspondence
• Bit threads and holographic entanglement
• Quantum Hamiltonian Complexity
• Title not available (Why is that?)

Cited In (8)

• Holographic duality from random tensor networks
• Theory behind quantum error correcting codes: an overview
• On the geometry of tensor network states of \(2\times N\) grids
• Matrix product states and the quantum max-flow/min-cut conjectures
• On two invariants of three manifolds from Hopf algebras
• Discrete bulk reconstruction
• The asymptotics of quantum max-flow min-cut
• Bit threads and holographic entanglement

This page was built for publication: Quantum max-flow/min-cut

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3178315)