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 $n$ , such that quantum max-flow equals quantum min-cut, after attaching dimension $n$ 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 $1$ as the dimension $n$ 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 ).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 $n$, such that quantum max-flow equals quantum min-cut, after attaching dimension $n$ 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 $1$ as the dimension $n$ 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:2110.00905Oct 3, 20211 citation

Almost optimal classical algorithms for a quantum generalization of Max Cut.

Ojas Parekh

Jul 30, 20200 citations

The Quantum Repeater Network Saturates the Entanglement Distribution Asymptotically

Nengkun Yu

Efficient and reliable entanglement distribution forms the core of quantum network architecture. The Quantum Max-Flow concept defines the upper boundary for efficiently transmitting entanglement within quantum tensor networks (Calegari, Freedman, and Walker, Journal of the American Mathematical Society, 2010). Despite the general invalidity of the Quantum analog of the Max-Flow Min-Cut theorem, this paper introduces a precise Quantum Max-Flow Min-Cut Theorem tailored to quantum tensor networks enhanced by ancilla entanglement. Specifically, our research establishes infinite ’n’ values for any quantum tensor network, where the Quantum Max-Flow matches the Quantum Min-Cut by attaching a maximally entangled state with dimension ’n’ to each edge. Our protocol exclusively relies on quantum teleportation and guarantees unambiguous success. This work highlights the potential of quantum repeaters, enabled by ancilla entanglement, to efficiently distribute entanglement throughout quantum networks.Efficient and reliable entanglement distribution forms the core of quantum network architecture. The Quantum Max-Flow concept defines the upper boundary for efficiently transmitting entanglement within quantum tensor networks (Calegari, Freedman, and Walker, Journal of the American Mathematical Society, 2010). Despite the general invalidity of the Quantum analog of the Max-Flow Min-Cut theorem, this paper introduces a precise Quantum Max-Flow Min-Cut Theorem tailored to quantum tensor networks enhanced by ancilla entanglement. Specifically, our research establishes infinite ’n’ values for any quantum tensor network, where the Quantum Max-Flow matches the Quantum Min-Cut by attaching a maximally entangled state with dimension ’n’ to each edge. Our protocol exclusively relies on quantum teleportation and guarantees unambiguous success. This work highlights the potential of quantum repeaters, enabled by ancilla entanglement, to efficiently distribute entanglement throughout quantum networks.

IEEE Transactions on Information TheoryJun 30, 20251 citation

Quantum Max-flow/Min-cut

Shawn Xingshan Cui, Michael Hartley Freedman, Or Sattath +2 more

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.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.

arXiv:1508.04644Journal of Mathematical PhysicsJun 1, 201626 citations

The Quantum and Classical Streaming Complexity of Quantum and Classical Max-Cut.

John Kallaugher, Ojas Parekh

Oct 1, 20220 citations

n

, such that quantum max-flow equals quantum min-cut, after attaching dimension

n

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

1

as the dimension

n

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 ).