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

Iterative Compression-Decimation Scheme for Tensor Network Optimization

Zhi-Cheng Yang, Stefanos Kourtis, Claudio Chamon, Eduardo R. Mucciolo, Andrei E. Ruckenstein

Published Aug 29, 2017• 3 citations
OpenAlex

Abstract

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.

Related papers

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

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

Tensor networks for p-spin models

Benjamin Lanthier, Jeremy Côté, Stefanos Kourtis

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.

arXiv:2405.08106•Frontiers in Physics•Oct 25, 2024•2 citations

Stochastic Path Compression for Spectral Tensor Networks on Cyclic Graphs

Ryan T. Grimm, Joel David Eaves

We develop a new approach to compress cyclic tensor networks called stochastic path compression (SPC) that uses an iterative importance sampling procedure to target edges with large bond-dimensions. Closed random walks in SPC form compression pathways that spatially localize large bond-dimensions in the tensor network. Analogous to the phase separation of two immiscible liquids, SPC separates the graph of bond-dimensions into spatially distinct high and low density regions. When combined with our integral decimation algorithm, SPC facilitates the accurate compression of cyclic tensor networks with continuous degrees of freedom. To benchmark and illustrate the methods, we compute the absolute thermodynamics of $q$-state clock models on two-dimensional square lattices and an XY model on a Watts-Strogatz graph, which is a small-world network with random connectivity between spins.

arXiv:2601.04172•Jan 7, 2026•0 citations

A Block Belief-Propagation Algorithm for the Contraction of Tensor-Networks

Nir Gutman

Simulating many-body quantum systems on a classical computer is difficult due to the large number of degrees of freedom, causing the computational complexity to grow exponentially with system size. Tensor Networks (TN) is a framework that breaks down large tensors into a network of smaller tensors, enabling efficient simulation of certain many-body quantum systems. To calculate expectation values of local observables or simulate nearest-neighbor interactions, a contraction of the entire network is needed. This is a known hard problem, which cannot be done exactly for systems with spatial dimension D>1 and is the major bottleneck in all tensor-network based algorithms. Various approximate-contraction algorithms have been suggested, all with their strengths and weaknesses. Nevertheless, contracting a 2D TN remains a major numerical challenge, limiting the use of TN techniques for many interesting systems. Recently, a close connection between TN and Probabilistic Graphical Models (PGM) has been shown. In the PGM framework, marginals of complicated probability distributions can be approximated using iterative message passing algorithms such as Belief Propagation (BP). The BP algorithm can be adapted to the TN framework as an efficient contraction algorithm. While BP is extremely efficient and easy to parallelize, it often yields inaccurate results for highly correlated quantum states or frustrated systems. To overcome this, we suggest the BlockBP algorithm, which coarse-grains the system into blocks and performs BP between them. This thesis focuses on: (i) development and implementation of the BlockBP algorithm for infinite lattices; (ii) using this algorithm to study the anti-ferromagnetic Heisenberg model on the Kagome lattice in the thermodynamic limit - a frustrated 2D model that is difficult to simulate using existing numerical methods.

quant-pharXiv:2603.13304•Mar 4, 2026•0 citations

Optimized decimation of tensor networks with super-orthogonalization for two-dimensional quantum lattice models

Shi-Ju Ran, Wei Li, Bin Xi +2 more

An algorithm based on the optimized decimation of tensor networks with super-orthogonalization (ODTNS) that can be applied to simulate efficiently and accurately not only the ground state but also the thermodynamic properties of two-dimensional (2D) quantum lattice models is proposed. By transforming the 2D quantum model into a three-dimensional (3D) closed tensor network (TN) comprised of the tensor product density operator and a 3D brick-wall TN, the free energy of the system can be calculated with the imaginary time evolution, in which the network Tucker decomposition is suggested for the first time to obtain the optimal lower-dimensional approximation on the bond space by transforming the TN into a super-orthogonal form. The efficiency and accuracy of this algorithm are testified, which are fairly comparable with the quantum Monte Carlo calculations. Besides, the present ODTNS scheme can also be applicable to the 2D frustrated quantum spin models with nice efficiency.

arXiv:1205.5636•Physical Review B•Oct 26, 2012•67 citations
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.
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
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.
We develop a new approach to compress cyclic tensor networks called stochastic path compression (SPC) that uses an iterative importance sampling procedure to target edges with large bond-dimensions. Closed random walks in SPC form compression pathways that spatially localize large bond-dimensions in the tensor network. Analogous to the phase separation of two immiscible liquids, SPC separates the graph of bond-dimensions into spatially distinct high and low density regions. When combined with our integral decimation algorithm, SPC facilitates the accurate compression of cyclic tensor networks with continuous degrees of freedom. To benchmark and illustrate the methods, we compute the absolute thermodynamics of qqq-state clock models on two-dimensional square lattices and an XY model on a Watts-Strogatz graph, which is a small-world network with random connectivity between spins.
Simulating many-body quantum systems on a classical computer is difficult due to the large number of degrees of freedom, causing the computational complexity to grow exponentially with system size. Tensor Networks (TN) is a framework that breaks down large tensors into a network of smaller tensors, enabling efficient simulation of certain many-body quantum systems. To calculate expectation values of local observables or simulate nearest-neighbor interactions, a contraction of the entire network is needed. This is a known hard problem, which cannot be done exactly for systems with spatial dimension D>1 and is the major bottleneck in all tensor-network based algorithms. Various approximate-contraction algorithms have been suggested, all with their strengths and weaknesses. Nevertheless, contracting a 2D TN remains a major numerical challenge, limiting the use of TN techniques for many interesting systems. Recently, a close connection between TN and Probabilistic Graphical Models (PGM) has been shown. In the PGM framework, marginals of complicated probability distributions can be approximated using iterative message passing algorithms such as Belief Propagation (BP). The BP algorithm can be adapted to the TN framework as an efficient contraction algorithm. While BP is extremely efficient and easy to parallelize, it often yields inaccurate results for highly correlated quantum states or frustrated systems. To overcome this, we suggest the BlockBP algorithm, which coarse-grains the system into blocks and performs BP between them. This thesis focuses on: (i) development and implementation of the BlockBP algorithm for infinite lattices; (ii) using this algorithm to study the anti-ferromagnetic Heisenberg model on the Kagome lattice in the thermodynamic limit - a frustrated 2D model that is difficult to simulate using existing numerical methods.
An algorithm based on the optimized decimation of tensor networks with super-orthogonalization (ODTNS) that can be applied to simulate efficiently and accurately not only the ground state but also the thermodynamic properties of two-dimensional (2D) quantum lattice models is proposed. By transforming the 2D quantum model into a three-dimensional (3D) closed tensor network (TN) comprised of the tensor product density operator and a 3D brick-wall TN, the free energy of the system can be calculated with the imaginary time evolution, in which the network Tucker decomposition is suggested for the first time to obtain the optimal lower-dimensional approximation on the bond space by transforming the TN into a super-orthogonal form. The efficiency and accuracy of this algorithm are testified, which are fairly comparable with the quantum Monte Carlo calculations. Besides, the present ODTNS scheme can also be applicable to the 2D frustrated quantum spin models with nice efficiency.