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•26 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•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•10 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

Solving the Max-Flow Problem on a Quantum Annealing Computer

Thomas Krauss, Joey McCollum, Chapman Pendery +2 more

This article addresses the question of implementing a maximum flow algorithm on directed graphs in a formulation suitable for a quantum annealing computer. Three distinct approaches are presented. In all three cases, the flow problem is formulated as a quadratic unconstrained binary optimization (QUBO) problem amenable to quantum annealing. The first implementation augments a graph with integral edge capacities into a multigraph with unit-capacity edges and encodes the fundamental objective and constraints of the maximum flow problem using a number of qubits equal to the total capacity of the graph $\sum _i{c_i}$. The second implementation, which encodes flows through edges using a binary representation, reduces the required number of qubits to $\mathcal {O}(|E| \log C_{\max })$, where $|E|$ and $C_{\max }$ denote the number of edges and maximum edge capacity of the graph, respectively. The third implementation adapts the dual minimum cut formulation and encodes the problem instance using $|V|$ qubits, where $|V|$ is the number of vertices in the graph. Scaling factors for penalty terms and coupling matrix construction times are made explicit in this article.

IEEE Transactions on Quantum Engineering•Jan 1, 2020•30 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.
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.
This article addresses the question of implementing a maximum flow algorithm on directed graphs in a formulation suitable for a quantum annealing computer. Three distinct approaches are presented. In all three cases, the flow problem is formulated as a quadratic unconstrained binary optimization (QUBO) problem amenable to quantum annealing. The first implementation augments a graph with integral edge capacities into a multigraph with unit-capacity edges and encodes the fundamental objective and constraints of the maximum flow problem using a number of qubits equal to the total capacity of the graph ∑ici\sum _i{c_i}∑i​ci​. The second implementation, which encodes flows through edges using a binary representation, reduces the required number of qubits to O(∣E∣log⁡Cmax⁡)\mathcal {O}(|E| \log C_{\max })O(∣E∣logCmax​), where ∣E∣|E|∣E∣ and Cmax⁡C_{\max }Cmax​ denote the number of edges and maximum edge capacity of the graph, respectively. The third implementation adapts the dual minimum cut formulation and encodes the problem instance using ∣V∣|V|∣V∣ qubits, where ∣V∣|V|∣V∣ is the number of vertices in the graph. Scaling factors for penalty terms and coupling matrix construction times are made explicit in this article.