Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2110.00905

Quantum Max-Flow Min-Cut theorem

Nengkun Yu

Published Oct 3, 2021• 1 citation
arXivHTMLPDF

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

DOI
10.48550/arxiv.2110.00905

Related papers

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.

IEEE Transactions on Information Theory•Jun 30, 2025•1 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.

arXiv:1508.04644•Journal of Mathematical Physics•Jun 1, 2016•28 citations

Canonical partial ordering from min-cuts and quantum entanglement in random tensor networks

Hu, Miao, Ion Nechita

The \emph{max-flow min-cut theorem} has been recently used in the theory of random tensor networks in quantum information theory, where it is helpful for computing the behavior of important physical quantities, such as the entanglement entropy. In this paper, we extend the max-flow min-cut theorem to a relation among different \emph{partial orders} on the set of vertices of a network and introduce a new partial order for the vertices based on the \emph{min-cut structure} of the network. We apply the extended max-flow min-cut theorem to random tensor networks and find that the \emph{finite correction} to the entanglement Rényi entropy arising from the degeneracy of the min-cuts is given by the number of \emph{order morphisms} from the min-cut partial order to the partial order induced by non-crossing partitions on the symmetric group. Moreover, we show that the number of order morphisms corresponds to moments of a graph-dependent measure which generalizes the free Bessel law in some special cases in free probability theory.

arXiv:2506.23894•Jun 30, 2025•1 citation

A Max-Flow Min-Cut Theorem for Quantum Graphs

Gian Luca Spitzer, Ion Nechita

We propose natural definitions of cuts and flows for quantum graphs. For cuts we consider two notions: ordinary cuts, which partition the vertex set into two parts; and generalised cuts, defined as a continuous relaxation of the binary partition function. We show that our definitions satisfy a max-flow min-cut theorem: For any disjoint terminal sets $S$ and $T$, the maximum value of an $S$-$T$-flow of a quantum graph equals the minimum value of a generalised $S$-$T$ cut, while the minimum value of an ordinary $S$-$T$ cut can be larger. While for classical graphs the values of the minimum generalised cut and the minimum ordinary cut coincide---recovering the classical max-flow min-cut theorem---we also show how it is more natural to think of flows as duals of generalised cuts instead of ordinary cuts.

arXiv:2611.15508•Nov 11, 2026•0 citations

Matrix product states and the quantum max-flow/min-cut conjectures

Fulvio Gesmundo, Joseph M. Landsberg, Michael Walter

In this note, we discuss the geometry of matrix product states with periodic boundary conditions and provide three infinite sequences of examples where the quantum max-flow is strictly less than the quantum min-cut. In the first, we fix the underlying graph to be a 4-cycle and verify a prediction of Hastings that inequality occurs for infinitely many bond dimensions. In the second, we generalize this result to a 2d-cycle. In the third, we show that the 2d-cycle with periodic boundary conditions gives inequality for all d when all bond dimensions equal two, namely, a gap of at least 2d−2 between the quantum max-flow and the quantum min-cut.

arXiv:1801.09106•Journal of Mathematical Physics•Oct 1, 2018•9 citations

Quantum-Enhanced Network Flow Optimization: A Max-Flow Min-Cut Perspective

Gagan Guruprasad Phadke, Vandana M. Ladwani

This paper is a comparison between classical and quantum inspired methods for solving the max-flow problem, which is commonly a foundational challenge in optimization and graph theory. This study will investigate the feasibility and performance of applying the Quantum Approximate Optimization Algorithm (QAOA) and other hybrid quantum-classical approaches to address the max-flow problem. This paper starts with comparing quantum approaches with well-established classical methods such as the Ford-Fulkerson and Edmonds-Karp.The main aim of this work is to asses how close quantum-inspired formulations can get to classical approaches in terms of their flow value as well as their runtime. Implementations are developed using the Qiskit framework on simulated quantum backends and compared against classical baselines across synthetic graph instances of varying sizes and densities. Experimentally, it can be seen that quantum approaches implemented using the QAOA technique managed to attain flow solutions comparable to classical ones, demonstrating similar accuracy, and in certain very dense graph configurations, competitive runtime performance due to parallelization in state-vector computing.These findings suggest that although current quantum-inspired approaches may not yet surpass classical algorithms in efficiency, but they can replicate their outcomes with reasonable fidelity. This provides an important validation of their applicability to combinatorial optimization. This study also lays groundwork for future research to explore hardware-level implementations, scalability enhancements, and also hybrid integration strategies for quantum optimization in network flow problems.

International Conference on Next-Gen Quantum and Advanced Computing: Algorithms, Security, and Beyond (NQComp)•Mar 5, 2026•0 citations
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 nnn, such that quantum max-flow equals quantum min-cut, after attaching dimension nnn 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 111 as the dimension nnn 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 ).
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.
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 \emph{max-flow min-cut theorem} has been recently used in the theory of random tensor networks in quantum information theory, where it is helpful for computing the behavior of important physical quantities, such as the entanglement entropy. In this paper, we extend the max-flow min-cut theorem to a relation among different \emph{partial orders} on the set of vertices of a network and introduce a new partial order for the vertices based on the \emph{min-cut structure} of the network. We apply the extended max-flow min-cut theorem to random tensor networks and find that the \emph{finite correction} to the entanglement Rényi entropy arising from the degeneracy of the min-cuts is given by the number of \emph{order morphisms} from the min-cut partial order to the partial order induced by non-crossing partitions on the symmetric group. Moreover, we show that the number of order morphisms corresponds to moments of a graph-dependent measure which generalizes the free Bessel law in some special cases in free probability theory.
We propose natural definitions of cuts and flows for quantum graphs. For cuts we consider two notions: ordinary cuts, which partition the vertex set into two parts; and generalised cuts, defined as a continuous relaxation of the binary partition function. We show that our definitions satisfy a max-flow min-cut theorem: For any disjoint terminal sets SSS and TTT, the maximum value of an SSS-TTT-flow of a quantum graph equals the minimum value of a generalised SSS-TTT cut, while the minimum value of an ordinary SSS-TTT cut can be larger. While for classical graphs the values of the minimum generalised cut and the minimum ordinary cut coincide---recovering the classical max-flow min-cut theorem---we also show how it is more natural to think of flows as duals of generalised cuts instead of ordinary cuts.
In this note, we discuss the geometry of matrix product states with periodic boundary conditions and provide three infinite sequences of examples where the quantum max-flow is strictly less than the quantum min-cut. In the first, we fix the underlying graph to be a 4-cycle and verify a prediction of Hastings that inequality occurs for infinitely many bond dimensions. In the second, we generalize this result to a 2d-cycle. In the third, we show that the 2d-cycle with periodic boundary conditions gives inequality for all d when all bond dimensions equal two, namely, a gap of at least 2d−2 between the quantum max-flow and the quantum min-cut.
This paper is a comparison between classical and quantum inspired methods for solving the max-flow problem, which is commonly a foundational challenge in optimization and graph theory. This study will investigate the feasibility and performance of applying the Quantum Approximate Optimization Algorithm (QAOA) and other hybrid quantum-classical approaches to address the max-flow problem. This paper starts with comparing quantum approaches with well-established classical methods such as the Ford-Fulkerson and Edmonds-Karp.The main aim of this work is to asses how close quantum-inspired formulations can get to classical approaches in terms of their flow value as well as their runtime. Implementations are developed using the Qiskit framework on simulated quantum backends and compared against classical baselines across synthetic graph instances of varying sizes and densities. Experimentally, it can be seen that quantum approaches implemented using the QAOA technique managed to attain flow solutions comparable to classical ones, demonstrating similar accuracy, and in certain very dense graph configurations, competitive runtime performance due to parallelization in state-vector computing.These findings suggest that although current quantum-inspired approaches may not yet surpass classical algorithms in efficiency, but they can replicate their outcomes with reasonable fidelity. This provides an important validation of their applicability to combinatorial optimization. This study also lays groundwork for future research to explore hardware-level implementations, scalability enhancements, and also hybrid integration strategies for quantum optimization in network flow problems.