Quantum Max-Flow Min-Cut theorem
arXiv:2110.00905 · doi:10.1109/TIT.2025.3584199
Abstract
The max-flow min-cut theorem is a cornerstone result in combinatorial optimization. Calegari et al. (arXiv:0802.3208) initialized the study of quantum max-flow min-cut conjecture, which connects the rank of a tensor network and the min-cut. Cui et al. (arXiv:1508.04644) showed that this conjecture is false generally. In this paper, we establish a quantum max-flow min-cut theorem for a new definition of quantum maximum flow. In particular, we show that for any quantum tensor network, there are infinitely many , such that quantum max-flow equals quantum min-cut, after attaching dimension maximally entangled state to each edge as ancilla. Our result implies that the ratio of the quantum max-flow to the quantum min-cut converges to as the dimension tends to infinity. As a direct application, we prove the validity of the asymptotical version of the open problem about the quantum max-flow and the min-cut, proposed in Cui et al. (arXiv:1508.04644 ).
arXiv commentComments are welcome
References in corpus (8)
- Holographic Derivation of Entanglement Entropy from AdS/CFT
- Holographic duality from random tensor networks
- Causality & holographic entanglement entropy
- Aggregating quantum repeaters for the quantum internet
- Linear programs for entanglement and key distribution in the quantum internet
- Quantum Max-flow/Min-cut
- The Asymptotics of Quantum Max-Flow Min-Cut
- Matrix product states and the quantum max-flow/min-cut conjectures