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:1801.09106 · Journal of Mathematical Physics

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

Fulvio Gesmundo, Joseph M. Landsberg, Michael Walter

Published Oct 1, 2018• 9 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1063/1.5026985

Related papers

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

On Translation-Invariant Matrix Product States and advances in MPS representations of the $W$-state

Klimov, Petr, Richik Sengupta, Jacob Biamonte

This work is devoted to the study Translation-Invariant (TI) Matrix Product State (MPS) representations of quantum states with periodic boundary conditions (PBC). We pursue two directions: we introduce new methods for constructing TI MPS representations of a certain class of TI states and study their optimality in terms of their bond dimension. We pay particular attention to the $n$-party $W$-state and construct a TI MPS representation of bond dimension $\left \lfloor \dfrac{n}{2} \right \rfloor +1$ for it. We further study properties of this class and show that we can can always achieve a bond dimension of $n$ for TI MPS representation of states in this class. In the framework of studying optimality of TI MPS representations with PBC, we study the optimal bond dimension $d(ψ)$ for a given state $ψ$. In particular we introduce a deterministic algorithm for the search of $d(ψ)$ for an arbitary state. Using numerical methods, we verify the optimality of our previous construction for the $n$-party $W$-state for small $n$.

arXiv:2306.16456•Jun 28, 2023•7 citations

Uniform matrix product states with a boundary

Marta Florido-Llinàs, Álvaro M. Alhambra, David Pérez-García +1 more

Canonical forms are central to the analytical understanding of tensor network states, underpinning key results such as the complete classification of one-dimensional symmetry-protected topological phases within the matrix product state (MPS) framework. Yet, the established theory applies only to uniform MPS with periodic boundary conditions, leaving many physically relevant states beyond its reach. Here we introduce a generalized canonical form for uniform MPS with a boundary matrix, thus extending the analytical MPS framework to a more general setting of wider physical significance. This canonical form reveals that any such MPS can be represented as a block-invertible matrix product operator acting on a structured class of algebraic regular language states that capture its essential long-range and scale-invariant features. Our construction builds on new algebraic results of independent interest that characterize the span and algebra generated by non-semisimple sets of matrices, including a generalized quantum Wielandt's inequality that gives an explicit upper bound on the blocking length at which the fixed-length span stabilizes to an algebra. Together, these results establish a unified theoretical foundation for uniform MPS with boundaries, bridging the gap between periodic and arbitrary-boundary settings, and providing the basis for extending key analytical and classification results of matrix product states to a much broader class of states and operators.

quant-pharXiv:2512.11968•Dec 16, 2025•9 citations

Matrix product states for critical spin chains: Finite-size versus finite-entanglement scaling

B. Pirvu, Guifré Vidal, Frank Verstraete +1 more

We investigate the use of matrix product states (MPS) to approximate ground states of critical quantum spin chains with periodic boundary conditions (PBC). We identify two regimes in the $(N,D)$ parameter plane, where $N$ is the size of the spin chain and $D$ is the dimension of the MPS matrices. In the first regime, MPS can be used to perform finite size scaling (FSS). In the complementary regime, the MPS simulations show instead the clear signature of finite entanglement scaling (FES). In the thermodynamic limit (or large $N$ limit), only MPS in the FSS regime maintain a finite overlap with the exact ground state. This observation has implications on how to correctly perform FSS with MPS as well as on the performance of recent MPS algorithms for systems with PBC. It also gives clear evidence that critical models can actually be simulated very well with MPS by using the right scaling relations; in the appendixes, we give an alternative derivation of the result of Pollmann et al. [Phys. Rev. Lett. 102, 255701 (2009)] relating the bond dimension of the MPS to an effective correlation length.

arXiv:1204.3934•Physical Review B•Aug 13, 2012•149 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•36 citations

On matrix product states for periodic boundary conditions

Klaus Krebs

The possibility of a matrix product representation for eigenstates with energy and momentum zero of a general m -state quantum spin Hamiltonian with nearest-neighbour interaction and periodic boundary condition is considered. For this representation we use the quadratic algebra defined in Krebs and Sandow ( 1997 J. Phys. A: Math. Gen. 30 3165 ), which is generated by 2 m operators which fulfil m 2 quadratic relations, endowed with a trace-like function reflecting periodic boundary conditions. It is shown that not every eigenstate with energy and momentum zero can be written in this way. An explicit counter-example is given. This is in contrast to the case of open boundary conditions where every zero-energy eigenstate can be written as a matrix product state using a Fock-like representation of the same quadratic algebra.

arXiv:cond-mat/9910452•Journal of Physics A Mathematical and General•Mar 31, 2000•11 citations
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.
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.
On Translation-Invariant Matrix Product States and advances in MPS representations of the WWW-state
This work is devoted to the study Translation-Invariant (TI) Matrix Product State (MPS) representations of quantum states with periodic boundary conditions (PBC). We pursue two directions: we introduce new methods for constructing TI MPS representations of a certain class of TI states and study their optimality in terms of their bond dimension. We pay particular attention to the nnn-party WWW-state and construct a TI MPS representation of bond dimension ⌊n2⌋+1\left \lfloor \dfrac{n}{2} \right \rfloor +1⌊2n​⌋+1 for it. We further study properties of this class and show that we can can always achieve a bond dimension of nnn for TI MPS representation of states in this class. In the framework of studying optimality of TI MPS representations with PBC, we study the optimal bond dimension d(ψ)d(ψ)d(ψ) for a given state ψψψ. In particular we introduce a deterministic algorithm for the search of d(ψ)d(ψ)d(ψ) for an arbitary state. Using numerical methods, we verify the optimality of our previous construction for the nnn-party WWW-state for small nnn.
Canonical forms are central to the analytical understanding of tensor network states, underpinning key results such as the complete classification of one-dimensional symmetry-protected topological phases within the matrix product state (MPS) framework. Yet, the established theory applies only to uniform MPS with periodic boundary conditions, leaving many physically relevant states beyond its reach. Here we introduce a generalized canonical form for uniform MPS with a boundary matrix, thus extending the analytical MPS framework to a more general setting of wider physical significance. This canonical form reveals that any such MPS can be represented as a block-invertible matrix product operator acting on a structured class of algebraic regular language states that capture its essential long-range and scale-invariant features. Our construction builds on new algebraic results of independent interest that characterize the span and algebra generated by non-semisimple sets of matrices, including a generalized quantum Wielandt's inequality that gives an explicit upper bound on the blocking length at which the fixed-length span stabilizes to an algebra. Together, these results establish a unified theoretical foundation for uniform MPS with boundaries, bridging the gap between periodic and arbitrary-boundary settings, and providing the basis for extending key analytical and classification results of matrix product states to a much broader class of states and operators.
We investigate the use of matrix product states (MPS) to approximate ground states of critical quantum spin chains with periodic boundary conditions (PBC). We identify two regimes in the (N,D)(N,D)(N,D) parameter plane, where NNN is the size of the spin chain and DDD is the dimension of the MPS matrices. In the first regime, MPS can be used to perform finite size scaling (FSS). In the complementary regime, the MPS simulations show instead the clear signature of finite entanglement scaling (FES). In the thermodynamic limit (or large NNN limit), only MPS in the FSS regime maintain a finite overlap with the exact ground state. This observation has implications on how to correctly perform FSS with MPS as well as on the performance of recent MPS algorithms for systems with PBC. It also gives clear evidence that critical models can actually be simulated very well with MPS by using the right scaling relations; in the appendixes, we give an alternative derivation of the result of Pollmann et al. [Phys. Rev. Lett. 102, 255701 (2009)] relating the bond dimension of the MPS to an effective correlation length.
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 possibility of a matrix product representation for eigenstates with energy and momentum zero of a general m -state quantum spin Hamiltonian with nearest-neighbour interaction and periodic boundary condition is considered. For this representation we use the quadratic algebra defined in Krebs and Sandow ( 1997 J. Phys. A: Math. Gen. 30 3165 ), which is generated by 2 m operators which fulfil m 2 quadratic relations, endowed with a trace-like function reflecting periodic boundary conditions. It is shown that not every eigenstate with energy and momentum zero can be written in this way. An explicit counter-example is given. This is in contrast to the case of open boundary conditions where every zero-energy eigenstate can be written as a matrix product state using a Fock-like representation of the same quadratic algebra.