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:2611.15508

A Max-Flow Min-Cut Theorem for Quantum Graphs

Gian Luca Spitzer, Ion Nechita

Published Nov 11, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2611.15508

Related papers

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

Unification of Quantum Graph Properties

Gian Luca Spitzer

Many properties of classical graphs are defined in terms of subsets of the vertex set. Examples include connected components, which are subsets $X \subseteq V(G)$ such that $X \times X^c$ and $E(G)$ are disjoint, or independent sets, for which $X \times X$ and $E(G)$ are disjoint. Direct generalisations of these definitions to quantum graphs are difficult to achieve, since the natural notion of subsets of a quantum set is much too rigid. As a consequence, approaches to generalising these classical properties to the quantum setting have been eclectic. In some cases, multiple inequivalent definitions of the same notion are in use. We introduce a natural and well-motivated alternative definition of subsets of a quantum set. Building on this, we propose unified definitions of quantum graph properties as straightforward generalisations of the classical definitions. We recover this way the established notions of colourings and connected components. For independent sets and cliques, our approach suggests variations that diverge from existing definitions, but address some of their counterintuitive properties. We nevertheless show how to recover an important existing definition of independent sets in our framework.

math.OACross-listedarXiv:2607.28024•Jul 31, 2026

Quantum Max-Flow Min-Cut theorem

Nengkun Yu

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.00905•Oct 3, 2021•1 citation

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•36 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 sublinear query quantum algorithm for s-t minimum cut on dense simple graphs

Simon Apers, Arinta Auza, Troy Lee

An $s{\operatorname{-}}t$ minimum cut in a graph corresponds to a minimum weight subset of edges whose removal disconnects vertices $s$ and $t$. Finding such a cut is a classic problem that is dual to that of finding a maximum flow from $s$ to $t$. In this work we describe a quantum algorithm for the minimum $s{\operatorname{-}}t$ cut problem on undirected graphs. For an undirected graph with $n$ vertices, $m$ edges, and integral edge weights bounded by $W$, the algorithm computes with high probability the weight of a minimum $s{\operatorname{-}}t$ cut after $\widetilde O(\sqrt{m} n^{5/6} W^{1/3})$ queries to the adjacency list of $G$. For simple graphs this bound is always $\widetilde O(n^{11/6})$, even in the dense case when $m = Ω(n^2)$. In contrast, a randomized algorithm must make $Ω(m)$ queries to the adjacency list of a simple graph $G$ even to decide whether $s$ and $t$ are connected.

arXiv:2110.15587•Oct 29, 2021•4 citations
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.
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.
Many properties of classical graphs are defined in terms of subsets of the vertex set. Examples include connected components, which are subsets X⊆V(G)X \subseteq V(G)X⊆V(G) such that X×XcX \times X^cX×Xc and E(G)E(G)E(G) are disjoint, or independent sets, for which X×XX \times XX×X and E(G)E(G)E(G) are disjoint. Direct generalisations of these definitions to quantum graphs are difficult to achieve, since the natural notion of subsets of a quantum set is much too rigid. As a consequence, approaches to generalising these classical properties to the quantum setting have been eclectic. In some cases, multiple inequivalent definitions of the same notion are in use. We introduce a natural and well-motivated alternative definition of subsets of a quantum set. Building on this, we propose unified definitions of quantum graph properties as straightforward generalisations of the classical definitions. We recover this way the established notions of colourings and connected components. For independent sets and cliques, our approach suggests variations that diverge from existing definitions, but address some of their counterintuitive properties. We nevertheless show how to recover an important existing definition of independent sets in our framework.
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 ).
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.
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.
An s-⁡ts{\operatorname{-}}ts-t minimum cut in a graph corresponds to a minimum weight subset of edges whose removal disconnects vertices sss and ttt. Finding such a cut is a classic problem that is dual to that of finding a maximum flow from sss to ttt. In this work we describe a quantum algorithm for the minimum s-⁡ts{\operatorname{-}}ts-t cut problem on undirected graphs. For an undirected graph with nnn vertices, mmm edges, and integral edge weights bounded by WWW, the algorithm computes with high probability the weight of a minimum s-⁡ts{\operatorname{-}}ts-t cut after O~(mn5/6W1/3)\widetilde O(\sqrt{m} n^{5/6} W^{1/3})O(m​n5/6W1/3) queries to the adjacency list of GGG. For simple graphs this bound is always O~(n11/6)\widetilde O(n^{11/6})O(n11/6), even in the dense case when m=Ω(n2)m = Ω(n^2)m=Ω(n2). In contrast, a randomized algorithm must make Ω(m)Ω(m)Ω(m) queries to the adjacency list of a simple graph GGG even to decide whether sss and ttt are connected.