Can boundary MPS on contraction trees approximate tensor network contraction?

Boundary MPS messages replace dense boundary tensors

Exact contraction of a general tensor network is #P-hard, so approximation becomes necessary once exact contraction exceeds available resources. CT-bMPS targets general closed tensor networks rather than one geometry or ansatz. It follows a binary contraction tree, the order of pairwise tensor contractions, and represents each boundary tensor as a matrix product state (MPS) with virtual bond dimension bounded by chi.

The key structural choice is that every edge of an unrooted contraction tree separates the network into two complementary parts. CT-bMPS keeps a forward MPS for one side and a backward MPS for the other. Pairing the two messages recovers the scalar result, and the opposite message serves as an environment for local truncation. This is what allows environment information to be incorporated along arbitrary contraction trees instead of only along a fixed geometry.

Environment updates raise accuracy at the same bond dimension

Ordinary CT-bMPS combines two incoming MPS into one outgoing MPS one site at a time, following a global index order from right to left. A core tensor handles four local index patterns: indices present only in the first input, only in the second, shared and summed, or shared and retained as a hyperedge. Each singular value decomposition acts on a matrix of size at most chi-squared by d times chi, costing O(d squared chi to the fourth) time; for binary indices this is a chi-squared by 2 chi matrix with O(chi to the fourth) cost.

Environment CT-bMPS adds a backward MPS from the opposite side of the tree edge and uses it to guide truncation through a reduced transition matrix construction. The environment is held fixed while an outgoing message is built, and messages are updated by sweeping through the entire contraction tree. The paper reports that environment updates yield substantially higher accuracy at the same bond dimension, at the cost of additional time and memory. Optimized contraction trees and environment updates also substantially improve accuracy without increasing the bond dimension.

Four benchmark families test generality, not one geometry

The method is benchmarked on Ising partition functions, random tensor networks, kicked Ising dynamics, and quantum error correction decoding. These span statistical mechanics, random network structure, quantum circuit simulation, and a decoding application, which is the evidence base for calling CT-bMPS general-purpose.

The kicked Ising benchmark uses the IBM heavy-hex circuit. Starting from the all-zero state on 127 qubits, the circuit applies a transverse rotation and commuting Ising interactions on the 144 edges of the heavy-hex graph at each time step. The five-step example measures a weight-17 Pauli string whose light cone contains 68 qubits; the deeper example measures Z62 after twenty complete steps and involves all 127 qubits. Gates outside the observable light cone are removed, two-qubit gates are decomposed into rank-three tensors connected by a bond of dimension two, and the tensor network is folded by combining ket and bra tensors.

Chi equals 64 tracks references that used much larger bond dimensions

For the twenty-step kicked Ising circuit, environment CT-bMPS with chi equal to 64 and ten sweeps agrees more closely overall with the mixed-picture reference than the MPS simulation with chi equal to 1024 and the MPO simulation with chi equal to 512. The paper cautions that because the algorithms differ, their bond dimensions alone do not provide a direct comparison of total computational cost.

The paper's own interpretation is that such small boundary bond dimensions can substantially reduce the arithmetic cost of local updates. For the folded tensor network with physical dimension four, ordinary truncation uses matrices of size at most chi-squared by 4 chi, while the environment-assisted SVD acts on smaller matrices of size at most chi by 4 chi. The authors identify these local contractions and SVDs as natural candidates for GPU acceleration, which could reduce runtime and make larger bond dimensions accessible. That is a stated possibility, not a demonstrated speedup in this paper.

Decoding depends on the sign of F1, not on its numerical value

In the quantum error correction application, logical-class probabilities are written as closed tensor network contractions. For a single logical bit, the unnormalized probability of class l sums over faults consistent with the observed detector syndrome and the logical class. Logical maximum-likelihood decoding selects the class with the larger probability, which differs from most-likely-error decoding that selects one compatible fault configuration and returns its logical class. Degeneracy matters: many individually unlikely configurations can together outweigh the class containing the most likely individual configuration.

The decision uses the Fourier coefficient F1, equal to Z0 minus Z1, with the decision set to class 0 when F1 is positive and class 1 when F1 is negative. Accuracy is measured as the absolute difference between the estimated and exact F1 divided by F0. The paper stresses that contraction accuracy and decoding performance are not in one-to-one correspondence, because the decision depends only on the sign of F1. Improving its numerical value does not change the decision as long as the sign is preserved; conversely, when the absolute approximation error exceeds the magnitude of F1, it can reverse the sign and change the inferred logical class.

Lower logical error rates than a published TN decoder

For the distance-five surface code at p equal to 0.009, the detector error model contains 1,679 fault mechanisms and its tensor network representation consists of 120 detector-parity tensors connected by 1,607 binary fault indices after single-detector faults are absorbed locally. Fault indices can be shared by up to four tensors, giving an irregular hypergraph rather than a regular lattice. Each parity tensor has an exact MPS representation with bond dimension two, so CT-bMPS takes these parity MPS directly as inputs and keeps intermediate tensors as MPS; a dense detector tensor with m binary indices would require 2 to the m entries, which the paper says makes direct application of dense-tensor methods such as HAC prohibitively expensive here.

Logical error rates are evaluated for the rotated surface code at p equal to 0.009 for distances 3, 5, and 7 with d syndrome rounds. Ordinary CT-bMPS with chi equal to 32 is used at distances 3 and 5, and environment CT-bMPS with chi equal to 16 and two sweeps at distance 7. The distance-7 tensor network forms a large irregular hypergraph with 336 detector-parity tensors and 5,833 binary fault indices, including 3,931 hyperedges. The CT-bMPS decoder achieves lower logical error rates than the published tensor-network decoder, with a substantial improvement at distances 5 and 7. Observed logical error rates are also lower than Tesseract's, but the differences are small, and the paper describes the gain over the tested most-likely-error decoder as modest.

The same procedure transfers to a more complex fault hypergraph

The superdense color code memory-X circuit at p equal to 0.0025 is also tested. Tensor-network decoding is exact at distances 3 and 5, while distance 7 uses environment CT-bMPS with chi equal to 16 and five sweeps. The distance-7 tensor network contains 252 detector-parity tensors and 9,869 binary fault indices, including 9,015 hyperedges. Although it contains fewer tensors than the surface code network, it has more fault indices and higher-order hyperedges connecting up to seven tensors rather than four, so its connectivity is more complex. As for the surface code, tensor-network decoding gives slightly lower observed logical error rates than Tesseract at each displayed distance.

The paper reports that the tensor-network calculations required substantially longer runtimes than Tesseract. It also notes that for nonuniform tensor networks such as the kicked Ising circuit, neither a geometric sweep nor a tree optimized for exact-contraction FLOPs necessarily gives the most accurate approximation; multiple candidate trees were generated through independently seeded simulated-annealing searches and screened at small bond dimension, and developing contraction tree optimization for such nonuniform networks remains future work.

Watch the sign of F1 and the tree, not just chi

The most decision-relevant distinction in this paper is that a smaller bond dimension is not automatically worse and a more accurate contraction is not automatically a better decoder. In the kicked Ising benchmark, environment CT-bMPS at chi equal to 64 tracked references using chi equal to 1024 and 512, but the paper explicitly declines to treat bond dimension as a direct cost comparison across different algorithms. In decoding, the decision threshold is the sign of F1, so the quantity to watch is whether approximation error stays below the magnitude of F1 rather than whether the numerical value of F1 improves.

The second priority is the contraction tree itself. The paper reports that optimized contraction trees and environment updates substantially improve accuracy without increasing bond dimension, and that for nonuniform networks tree selection was handled by screening simulated-annealing candidates at small bond dimension rather than by a settled optimization rule. For readers judging whether CT-bMPS applies to a new closed tensor network, the practical question is therefore whether a workable global index order and contraction tree can be found, and whether the environment sweep budget is available, since environment updates buy accuracy at the cost of additional time and memory.

Sources used in this answer