Quantum Max-flow/Min-cut
Xingshan Cui, University of California, Santa Barbara
The classical max-flow min-cut theorem describes transport through certain idealized classical networks. We consider the quantum analog for tensor networks. By associating a tensor to each node in an integral flow network, we can also interpret it as a tensor network, and more specifically, as a linear map.
The quantum max flow is defined to be the maximal rank of this linear map over all choices for the tensors in the tensor network. We show that every cut in the tensor network provides an upper-bound on this rank, and therefore the quantum max flow is no more than the quantum min cut. Unlike the classical case (where the converse is also true, i.e., max flow = min cut) we show examples where the quantum inequality is strict. We also found connections of quantum max-flow/min-cut with entropy of entanglement and the quantum satisfiability problem(QSAT). We speculate that the phenomena revealed may be of interest both in spin systems in condensed matter and in quantum gravity.