Quantum Max-flow/Min-cut

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.

added some motivations; added references on relevant work

References in corpus (6)

• Holographic quantum error-correcting codes: Toy models for the bulk/boundary correspondence
• Renormalization algorithms for Quantum-Many Body Systems in two and higher dimensions
• Causality & holographic entanglement entropy
• Bit threads and holographic entanglement
• When a local Hamiltonian must be frustration-free
• Unfrustration Condition and Degeneracy of Qudits on Trees

Cited by in corpus (18)

• Holographic duality from random tensor networks
• Quantum Entanglement in Deep Learning Architectures
• Bit threads and holographic entanglement
• Quantum Spectral Clustering
• Extracting entanglement geometry from quantum states
• Quantum bit threads of MERA tensor network in large $c$ limit
• Matrix product states and the quantum max-flow/min-cut conjectures
• The Asymptotics of Quantum Max-Flow Min-Cut
• Entanglement distillation toward minimal bond cut surface in tensor networks
• Quantum Compression of Tensor Network States
• On Two Invariants of Three Manifolds from Hopf Algebras
• At the Interface of Algebra and Statistics
• Discrete Bulk Reconstruction
• Quantum Max-Flow Min-Cut theorem
• Quantum max-flow in the bridge graph
• Quantum Capacities for Entanglement Networks
• Quantum Algorithms for Unsupervised Machine Learning and Neural Networks
• On the geometry of Tensor Network States of $2\times N$ Grids