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:2405.08106 · Frontiers in Physics

Tensor networks for p-spin models

Benjamin Lanthier, Jeremy Côté, Stefanos Kourtis

Published Oct 25, 2024• 2 citations
arXivHTMLPDF

Abstract

We introduce a tensor network algorithm for the solution of p-spin models. We show that bond compression through rank-revealing decompositions performed during the tensor network contraction resolves logical redundancies in the system exactly and is thus lossless, yet leads to qualitative changes in runtime scaling in different regimes of the model. First, we find that bond compression emulates the so-called leaf-removal algorithm, solving the problem efficiently in the “easy” phase. Past a dynamical phase transition, we observe superpolynomial runtimes, reflecting the appearance of a core component. We then develop a graphical method to study the scaling of contraction for a minimal ensemble of core-only instances. We find subexponential scaling, improving on the exponential scaling that occurs without compression. Our results suggest that our tensor network algorithm subsumes the classical leaf removal algorithm and simplifies redundancies in the p-spin model through lossless compression, all without explicit knowledge of the problem’s structure.

DOI
10.3389/fphy.2024.1431810

Related papers

Iterative Compression-Decimation Scheme for Tensor Network Optimization

Zhi-Cheng Yang, Stefanos Kourtis, Claudio Chamon +2 more

Motivated by statistical physics models connected to computation problems, we devise a tensor network technique that is suited to problems with or without translation invariance and with arbitrary boundary conditions. We introduce a compression-decimation algorithm as an efficient iterative scheme to optimize tensor networks that encode generalized vertex models on regular lattices. The algorithm first propagates local constraints to longer ranges via repeated contraction-decomposition sweeps over all lattice bonds, thus achieving compression on a given length scale. It then decimates the lattice via coarse-graining tensor contractions. Repeated iterations of these two steps allow us to gradually collapse the tensor network while keeping the tensor dimensions under control, such that ultimately the full tensor trace can be taken for relatively large systems. As a benchmark, we demonstrate the efficiency of the algorithm by computing the ground state entropy density of the planar ice model and the eight-vertex model. We then apply it to reversible classical computational problems based on a recently proposed vertex model representation of classical computations [Nat. Commun. 8, 15303 (2017)]. Our protocol allows us to obtain the exact number of solutions for computations where a naive enumeration would take astronomically long times, suggesting that the algorithm is a promising practical tool for the solution of a plethora of problems in physics and computer science.

•Aug 29, 2017•3 citations

Tensor network method for reversible classical computation

Zhi-Cheng Yang, Stefanos Kourtis, Claudio Chamon +2 more

We develop a tensor network technique that can solve universal reversible classical computational problems, formulated as vertex models on a square lattice [Nat. Commun. 8, 15303 (2017)2041-172310.1038/ncomms15303]. By encoding the truth table of each vertex constraint in a tensor, the total number of solutions compatible with partial inputs and outputs at the boundary can be represented as the full contraction of a tensor network. We introduce an iterative compression-decimation (ICD) scheme that performs this contraction efficiently. The ICD algorithm first propagates local constraints to longer ranges via repeated contraction-decomposition sweeps over all lattice bonds, thus achieving compression on a given length scale. It then decimates the lattice via coarse-graining tensor contractions. Repeated iterations of these two steps gradually collapse the tensor network and ultimately yield the exact tensor trace for large systems, without the need for manual control of tensor dimensions. Our protocol allows us to obtain the exact number of solutions for computations where a naive enumeration would take astronomically long times.

arXiv:1708.08932•Physical review. E•Mar 8, 2018•7 citations

Toward Using Matrix-free Tensor Decompositions to Systematically Improve Approximate Tensor-Networks

Karl Pierce

We investigate a novel approach to approximate tensor-network contraction via the exact, matrix-free decomposition of full tensor-networks. We study this method as a means to eliminate the propagation of error in the approximation of tensor-networks. Importantly, this decomposition-based approach is generic, i.e., it does not depend on a specific tensor-network, the tensor index (physical) ordering, or the choice of tensor decomposition. Careful consideration should be made to determine the best decomposition strategy. Furthermore, this method does not rely on robust cancellation of errors (i.e., the Taylor expansion). As a means to study the effectiveness of the approach, we replace the exact contraction of the particle–particle ladder (PPL) tensor diagram in the popular coupled-cluster with single and double excitation (CCSD) method with a low-rank tensor decomposition, namely the canonical polyadic decomposition (CPD). With this approach, we replace an O ( N 6 ) tensor contractions with a potentially reduced-scaling O ( N 4 R ) optimization problem, where R is the CP rank, and we reduce the computational storage of the PPL tensor from O ( N 4 ) to O ( N R ), although we do not take advantage of this compression in this study. To minimize the cost of the CPD optimization, we utilize the iterative structure of CCSD to efficiently initialize the CPD optimization. We show that accurate chemically relevant energy values can be computed with an error of less than 1 kcal/mol using a relatively low CP rank.

Journal of Chemical Theory and Computation•Jun 26, 2025•3 citations

Towards Using Matrix-Free Tensor Decompositions to Systematically Improve Approximate Tensor-Networks

Karl Pierce

We investigate a novel approach to approximate tensor-network contraction via the exact, matrix-free decomposition of full tensor-networks. We study this method as a means to eliminate the propagation of error in the approximation of tensor-networks. Importantly, this decomposition-based approach is generic, i.e. it does not depend on a specific tensor-network, the tensor index (physical) ordering, or the choice of tensor decomposition. Careful consideration should be made to determine the best decomposition strategy. Furthermore, this method does not rely on robust cancellation of errors (i.e. the Taylor expansion). As a means to study the effectiveness of the approach, we replace the exact contraction of the particle particle ladder (PPL) tensor diagram in the popular coupled-cluster with single and double excitation (CCSD) method with a low-rank tensor decomposition, namely the canonical polyadic decomposition (CPD). With this approach, we replace an $\mathcal{O}(N^6)$ tensor contractions with a potentially reduced-scaling $\mathcal{O}(N^4R)$ optimization problem, where $R$ is the CP rank, and we reduce the computational storage of the PPL tensor from $\mathcal{O}(N^4)$ to $\mathcal{O}(NR)$, although we do not take advantage of this compression in this study. To minimize the cost of the CPD optimization, we utilize the iterative structure of CCSD to efficiently initialize the CPD optimization. We show that accurate chemically-relevant energy values can be computed with an error of less than 1 kcal/mol using a relatively low CP rank.

arXiv:2503.10380•Mar 13, 2025•0 citations

Hyperoptimized Approximate Contraction of Tensor Networks with Arbitrary Geometry

Johnnie Gray, Garnet Kin‐Lic Chan

Tensor network contraction is central to problems ranging from many-body physics to computer science. We describe how to approximate tensor network contraction through bond compression on arbitrary graphs. In particular, we introduce a hyperoptimization over the compression and contraction strategy itself to minimize error and cost. We demonstrate that our protocol outperforms both handcrafted contraction strategies in the literature as well as recently proposed general contraction algorithms on a variety of synthetic and physical problems on regular lattices and random regular graphs. We further showcase the power of the approach by demonstrating approximate contraction of tensor networks for frustrated three-dimensional lattice partition functions, dimer counting on random regular graphs, and to access the hardness transition of random tensor network models, in graphs with many thousands of tensors. Published by the American Physical Society 2024

arXiv:2206.07044•Physical Review X•Jan 26, 2024•29 citations

Resource Optimization for Quantum Dynamics with Tensor Networks: Quantum and Classical Algorithms

Anurag Dwivedi, Miguel Angel Lopez-Ruiz, Srinivasan S. Iyengar

The exponential scaling of the quantum degrees of freedom with the size of the system is one of the biggest challenges in computational chemistry and particularly in quantum dynamics. We present a tensor network approach for the time-evolution of the nuclear degrees of freedom of multiconfigurational chemical systems at a reduced storage and computational complexity. We also present quantum algorithms for the resultant dynamics. To preserve the compression advantage achieved via tensor network decompositions, we present an adaptive algorithm for the regularization of nonphysical bond dimensions, preventing the potentially exponential growth of these with time. While applicable to any quantum dynamical problem, our method is particularly valuable for dynamical simulations of nuclear chemical systems. Our algorithm is demonstrated using ab initio potentials obtained for a symmetric hydrogen-bonded system, namely, the protonated 2,2'-bipyridine, and compared to exact diagonalization numerical results.

The Journal of Physical Chemistry A•Aug 5, 2024•5 citations
We introduce a tensor network algorithm for the solution of p-spin models. We show that bond compression through rank-revealing decompositions performed during the tensor network contraction resolves logical redundancies in the system exactly and is thus lossless, yet leads to qualitative changes in runtime scaling in different regimes of the model. First, we find that bond compression emulates the so-called leaf-removal algorithm, solving the problem efficiently in the “easy” phase. Past a dynamical phase transition, we observe superpolynomial runtimes, reflecting the appearance of a core component. We then develop a graphical method to study the scaling of contraction for a minimal ensemble of core-only instances. We find subexponential scaling, improving on the exponential scaling that occurs without compression. Our results suggest that our tensor network algorithm subsumes the classical leaf removal algorithm and simplifies redundancies in the p-spin model through lossless compression, all without explicit knowledge of the problem’s structure.
Motivated by statistical physics models connected to computation problems, we devise a tensor network technique that is suited to problems with or without translation invariance and with arbitrary boundary conditions. We introduce a compression-decimation algorithm as an efficient iterative scheme to optimize tensor networks that encode generalized vertex models on regular lattices. The algorithm first propagates local constraints to longer ranges via repeated contraction-decomposition sweeps over all lattice bonds, thus achieving compression on a given length scale. It then decimates the lattice via coarse-graining tensor contractions. Repeated iterations of these two steps allow us to gradually collapse the tensor network while keeping the tensor dimensions under control, such that ultimately the full tensor trace can be taken for relatively large systems. As a benchmark, we demonstrate the efficiency of the algorithm by computing the ground state entropy density of the planar ice model and the eight-vertex model. We then apply it to reversible classical computational problems based on a recently proposed vertex model representation of classical computations [Nat. Commun. 8, 15303 (2017)]. Our protocol allows us to obtain the exact number of solutions for computations where a naive enumeration would take astronomically long times, suggesting that the algorithm is a promising practical tool for the solution of a plethora of problems in physics and computer science.
We develop a tensor network technique that can solve universal reversible classical computational problems, formulated as vertex models on a square lattice [Nat. Commun. 8, 15303 (2017)2041-172310.1038/ncomms15303]. By encoding the truth table of each vertex constraint in a tensor, the total number of solutions compatible with partial inputs and outputs at the boundary can be represented as the full contraction of a tensor network. We introduce an iterative compression-decimation (ICD) scheme that performs this contraction efficiently. The ICD algorithm first propagates local constraints to longer ranges via repeated contraction-decomposition sweeps over all lattice bonds, thus achieving compression on a given length scale. It then decimates the lattice via coarse-graining tensor contractions. Repeated iterations of these two steps gradually collapse the tensor network and ultimately yield the exact tensor trace for large systems, without the need for manual control of tensor dimensions. Our protocol allows us to obtain the exact number of solutions for computations where a naive enumeration would take astronomically long times.
We investigate a novel approach to approximate tensor-network contraction via the exact, matrix-free decomposition of full tensor-networks. We study this method as a means to eliminate the propagation of error in the approximation of tensor-networks. Importantly, this decomposition-based approach is generic, i.e., it does not depend on a specific tensor-network, the tensor index (physical) ordering, or the choice of tensor decomposition. Careful consideration should be made to determine the best decomposition strategy. Furthermore, this method does not rely on robust cancellation of errors (i.e., the Taylor expansion). As a means to study the effectiveness of the approach, we replace the exact contraction of the particle–particle ladder (PPL) tensor diagram in the popular coupled-cluster with single and double excitation (CCSD) method with a low-rank tensor decomposition, namely the canonical polyadic decomposition (CPD). With this approach, we replace an O ( N 6 ) tensor contractions with a potentially reduced-scaling O ( N 4 R ) optimization problem, where R is the CP rank, and we reduce the computational storage of the PPL tensor from O ( N 4 ) to O ( N R ), although we do not take advantage of this compression in this study. To minimize the cost of the CPD optimization, we utilize the iterative structure of CCSD to efficiently initialize the CPD optimization. We show that accurate chemically relevant energy values can be computed with an error of less than 1 kcal/mol using a relatively low CP rank.
We investigate a novel approach to approximate tensor-network contraction via the exact, matrix-free decomposition of full tensor-networks. We study this method as a means to eliminate the propagation of error in the approximation of tensor-networks. Importantly, this decomposition-based approach is generic, i.e. it does not depend on a specific tensor-network, the tensor index (physical) ordering, or the choice of tensor decomposition. Careful consideration should be made to determine the best decomposition strategy. Furthermore, this method does not rely on robust cancellation of errors (i.e. the Taylor expansion). As a means to study the effectiveness of the approach, we replace the exact contraction of the particle particle ladder (PPL) tensor diagram in the popular coupled-cluster with single and double excitation (CCSD) method with a low-rank tensor decomposition, namely the canonical polyadic decomposition (CPD). With this approach, we replace an O(N6)\mathcal{O}(N^6)O(N6) tensor contractions with a potentially reduced-scaling O(N4R)\mathcal{O}(N^4R)O(N4R) optimization problem, where RRR is the CP rank, and we reduce the computational storage of the PPL tensor from O(N4)\mathcal{O}(N^4)O(N4) to O(NR)\mathcal{O}(NR)O(NR), although we do not take advantage of this compression in this study. To minimize the cost of the CPD optimization, we utilize the iterative structure of CCSD to efficiently initialize the CPD optimization. We show that accurate chemically-relevant energy values can be computed with an error of less than 1 kcal/mol using a relatively low CP rank.
Tensor network contraction is central to problems ranging from many-body physics to computer science. We describe how to approximate tensor network contraction through bond compression on arbitrary graphs. In particular, we introduce a hyperoptimization over the compression and contraction strategy itself to minimize error and cost. We demonstrate that our protocol outperforms both handcrafted contraction strategies in the literature as well as recently proposed general contraction algorithms on a variety of synthetic and physical problems on regular lattices and random regular graphs. We further showcase the power of the approach by demonstrating approximate contraction of tensor networks for frustrated three-dimensional lattice partition functions, dimer counting on random regular graphs, and to access the hardness transition of random tensor network models, in graphs with many thousands of tensors. Published by the American Physical Society 2024
The exponential scaling of the quantum degrees of freedom with the size of the system is one of the biggest challenges in computational chemistry and particularly in quantum dynamics. We present a tensor network approach for the time-evolution of the nuclear degrees of freedom of multiconfigurational chemical systems at a reduced storage and computational complexity. We also present quantum algorithms for the resultant dynamics. To preserve the compression advantage achieved via tensor network decompositions, we present an adaptive algorithm for the regularization of nonphysical bond dimensions, preventing the potentially exponential growth of these with time. While applicable to any quantum dynamical problem, our method is particularly valuable for dynamical simulations of nuclear chemical systems. Our algorithm is demonstrated using ab initio potentials obtained for a symmetric hydrogen-bonded system, namely, the protonated 2,2'-bipyridine, and compared to exact diagonalization numerical results.