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

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

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•1 citation

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•1 citation

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•136 citations

An Optimal Product-State Approximation for 2-Local Quantum Hamiltonians with Positive Terms

Ojas Parekh, Thompson, Kevin

We resolve the approximability of the maximum energy of the Quantum Max Cut (QMC) problem using product states. A classical 0.498-approximation, using a basic semidefinite programming relaxation, is known for QMC, paralleling the celebrated 0.878-approximation for classical Max Cut. For Max Cut, improving the 0.878-approximation is Unique-Games-hard (UG-hard), and one might expect that improving the 0.498-approximation is UG-hard for QMC. In contrast, we give a classical 1/2-approximation for QMC that is unconditionally optimal, since simple examples exhibit a gap of 1/2 between the energies of an optimal product state and general quantum state. Our result relies on a new nonlinear monogamy of entanglement inequality on a triangle that is derived from the second level of the quantum Lasserre hierarchy. This inequality also applies to the quantum Heisenberg model, and our results generalize to instances of Max 2-Local Hamiltonian where each term is positive and has no 1-local parts. Finally, we give further evidence that product states are essential for approximations of 2-Local Hamiltonian.

arXiv:2206.08342•Jun 16, 2022•6 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•9 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.
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 ).
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.
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.
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.
We resolve the approximability of the maximum energy of the Quantum Max Cut (QMC) problem using product states. A classical 0.498-approximation, using a basic semidefinite programming relaxation, is known for QMC, paralleling the celebrated 0.878-approximation for classical Max Cut. For Max Cut, improving the 0.878-approximation is Unique-Games-hard (UG-hard), and one might expect that improving the 0.498-approximation is UG-hard for QMC. In contrast, we give a classical 1/2-approximation for QMC that is unconditionally optimal, since simple examples exhibit a gap of 1/2 between the energies of an optimal product state and general quantum state. Our result relies on a new nonlinear monogamy of entanglement inequality on a triangle that is derived from the second level of the quantum Lasserre hierarchy. This inequality also applies to the quantum Heisenberg model, and our results generalize to instances of Max 2-Local Hamiltonian where each term is positive and has no 1-local parts. Finally, we give further evidence that product states are essential for approximations of 2-Local Hamiltonian.
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.