Carving-width and contraction trees for tensor networks

D. Anekstein; J. Jakes-Schauer; P. Wocjan

REVIEW 4 major objections 6 minor 29 references

Carving-width and contraction trees for tensor networks

T0 review · 4 major / 6 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper argues that carving-width, computed by the Ratcatcher algorithm for planar graphs, is a practical heuristic for near-optimal tensor-network contraction orders.

desk verdict A genuinely useful contraction-tree framing and a working Ratcatcher implementation, but the headline 'generally effective heuristic' claim is undercut by timeouts excluded from the reported ratios. read the letter →

arxiv 1908.11034 v1 pith:IFU64LOF submitted 2019-08-29 cs.DM cond-mat.str-elquant-ph

J. Jakes-Schauer , D. Anekstein , P. Wocjan This is my paper · ORCID

classification cs.DMcond-mat.str-elquant-ph MSC 05C8505C1068R10

keywords tensornetworkscontractionorderingcarving-widthtreesRatcatcherplanargraphsPEPSexact

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tries to establish that carving-width, a graph measure of the largest cut a binary routing tree must make, is a practical guide to the cost of contracting a tensor network. It introduces the contraction tree as a shared data type: arc labels record the size of intermediate tensors (space) and node labels record the arithmetic cost of each pairwise contraction (time), so the same tree encodes both bottlenecks. The authors implement the Ratcatcher algorithm to compute carving-width in polynomial time for planar networks and use it to build contraction orders, a pipeline they call Ratcon. On planar square half-grids meant to resemble PEPS states, Ratcon finds orders whose total contraction cost is typically within a factor of about three to four of the exact optimum, while the search itself becomes much faster than exact search as the grids grow.

What carries the argument

The load-bearing object is the free contraction tree, a full binary tree whose leaves are the tensors of the network. Removing an arc splits the leaves into two sets and labels the arc with the product of the weights of the edges crossing that split, giving the space bottleneck $B_s^T$; each internal node has three incident subtrees and its label is the product over the 3-cut, giving time cost $w_n = \sqrt{w_a w_{a'} w_{a''}}$ in terms of its three adjacent arc labels. This identity plus the bounds $B_s\le B_t\le (B_s)^{1.5}$ ties the spatial measure to total time, and the isomorphism between contraction trees and carving-decompositions lets the polynomial-time Ratcatcher decision procedure for planar graphs compute the optimal space bottleneck. The remaining machinery turns the width into an order: an edge-contraction construction of the decomposition, repeated random trials to choose among equally space-optimal trees, rooting at the cheapest edge, and a linear-time recursive sequencing algorithm that conserves memory.

What would settle it

Let Netcon run to completion, or with a much larger budget, on the sixteen $L=10$ half-grids that were stopped at 7200 seconds, and compute Ratcon's total-time ratio $\rho$ on those graphs alone; if their mean $\rho$ is far above the 3.36 reported for the fourteen finished instances, the claim that carving-width is generally effective at limiting total contraction time would be refuted. A complementary check: find a planar weighted grid on which every minimum-carving decomposition forces one internal node whose weight far exceeds the optimal total time.

Watch

Extended reading notes

Core claim

The central claim is that minimizing the space bottleneck, not the total time directly, is a viable route to near-optimal contraction orders on planar tensor networks. Formally, a free contraction tree is a carving-decomposition: the label of an arc is the product of bond dimensions crossing a 2-cut, and the label of an internal node is the product crossing the corresponding 3-cut. With edge weights mapped to logarithms, the carving-width of the graph equals $\log_2 B_s^G$, the logarithm of the smallest achievable space bottleneck. Ratcon computes that width with the Ratcatcher, assembles a carving-decomposition through random edge contractions, roots the tree at a minimum-weight edge, and emits a concrete contraction sequence. Benchmarks on $L\times L$ half-grids, $L=5,\dots,10$, with lognormal bond dimensions show that Ratcon's sequences have total time within a small constant factor of the exact Netcon optimum on the instances Netcon can finish (mean $\rho\approx 3.36$ at $L=10$), while Ratcon's running-time advantage grows with $L$; one $L=9$ outlier has error factor 249, and the sixteen hardest $L=10$ instances are excluded from the reported ratios.

Load-bearing premise

The experimental case assumes that the $L=10$ graphs on which the exact optimizer Netcon finished within two hours represent the full distribution; if the sixteen unfinished graphs are exactly the cases where space-optimal orders are time-wasteful, the reported error ratios overstate how generally effective carving-width is.

Editorial extensions

If this is right

On planar grid-like networks, near-optimal contraction orders can be found in polynomial time, roughly $O(N|V|^4\log B_s^G)$ with $N$ random trials, rather than by the exponential branch-and-bound search used by exact optimizers.
The search-time advantage grows with grid size: Ratcon is slower than Netcon for small $L$ but about ten times faster on the completed $L=10$ subset, so the heuristic pays off exactly in the regime where exact search begins to time out.
Space-optimality does not imply time-optimality, as the paper's $K_4$ example shows, so the practical recipe is to hedge by running a Netcon-style exact search in parallel with the Ratcon order.
For the tested $L=10$ instances, the break-even point is about 500 GFLOPS: on faster machines the extra arithmetic of a Ratcon order is outweighed by the reduced search time.
Because any tree-decomposition of the line graph (the graph whose vertices are the original edges) can be converted into a contraction tree without increasing width, advances in weighted treewidth computation translate directly into better contraction orders.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

An extension the paper does not run: applying Ratcon to other planar network families, such as hexagonal PEPS half-lattices or random planar graphs with lognormal weights, would test whether the factor-3-to-4 ratio is a property of planar carving-width generally or of square-grid geometry.
The single error factor of 249 hints that pure space-bottleneck minimization can occasionally miss a time-dominant contraction; a local post-pass that swaps sibling subtrees or evaluates total time among a handful of equally $B_s$-optimal trees might remove such outliers while staying polynomial, but this is not tested in the paper.
Full PEPS bra-ket networks are non-planar, so the paper's stated motivation of hundreds-of-tensors exact contractions is not yet delivered; a planarization that avoids squaring bond dimensions would be the natural next step, and the paper explicitly defers it.
Since the Ratcatcher phase runs in time proportional to $\log_2 B_s^G$ rather than to $B_s^G$, the width-finding part stays cheap even for memory-heavy networks; in practice the edge-contraction sampling factor $N$, not the width computation, is likely to dominate preprocessing cost.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The paper is worth a look for two reasons. First, it gives a clean, systematic development of the contraction-tree datatype and shows how the space and time bottlenecks map onto carving-width and weighted treewidth of the line graph. The bounds Bs ≤ Bt ≤ Bs^1.5 are simple but useful, and the proof that a tree-decomposition can be transformed into a contraction tree is reasonable. Second, they actually implemented the Seymour–Thomas Ratcatcher and evaluated it against Netcon, an external exact optimizer. That is real work, and the code is on GitHub. For planar grid-like networks, the heuristic does appear to produce contraction orders within a small factor of optimal on the instances that were compared, in a fraction of the time.

The soft spots are mostly about the empirical claim. The abstract says carving-width makes a 'generally effective heuristic' for limiting total contraction time, but the supporting table excludes 16 of 30 L=10 samples and 1 of 30 L=9 samples because Netcon timed out. Those timeouts are not random: Netcon's runtime tracks instance difficulty, so the missing cases are likely the hard ones. Section 4.6 even reports a separate L=9 outlier with ρ ≈ 249. The reported means and medians are therefore conditional on Netcon finishing, and the headline conclusion does not follow from the data. The authors should have provided a complete-case analysis, or at least clearly labeled the ratios as conditional. Also, the experiments are on planar half-grids only; full PEPS bra-ket networks are non-planar, and the paper defers those tests. That is fine as a limitation, but it should temper the 'generally effective' phrasing.

There are minor mathematical rough edges: the proof of Lemma 2 is compressed, and Theorem 3's 'up to logarithmic concavity' is imprecise. These are not fatal; a referee should ask the authors to tighten them, not to redo the paper. The novelty is moderate—the connection between carving-width and contraction order was already noted by Aharonov–Landau–Makowsky and de Oliveira Oliveira—but the contraction-tree framing and the first benchmark of a Ratcatcher-based tensor-network heuristic are worth publishing after revision.

For a practitioner working with planar networks, this is a useful benchmarking tool against approximate contraction methods. I would send it to peer review: the theory is sound enough, the code is real, and the empirical weakness is fixable with a revised analysis and a more careful abstract.

Referee Report

4 major / 6 minor

Summary. The paper introduces a contraction-tree abstraction for tensor-network contraction orders, in which arc labels encode space costs and node labels encode time costs, and proves bounds relating the space bottleneck Bs, the time bottleneck Bt, and the total contraction time Ct. It establishes equivalences between contraction trees and tree decompositions of line graphs (Theorems 1-2) and between contraction trees and carving decompositions (Theorem 3), and derives the bound Bs <= Bt <= Bs^1.5. The authors implement the Seymour-Thomas Ratcatcher algorithm ('Ratcon') to compute carving-width-optimal contraction trees for planar networks and benchmark them against Netcon on planar square half-grids with lognormal bond dimensions. The reported empirical claim is that Ratcon yields contraction orders whose total time is typically within a small factor of the exact optimum.

Significance. If the theoretical claims hold, the paper provides a useful datatype for tensor-network contraction, polynomial-time computation of space-optimal contraction orders for planar networks, and an open-source implementation at https://github.com/TensorCon. The equivalence results and the Bs-Bt-Ct bounds are clean contributions that connect carving-width and treewidth to a concrete contraction-cost model. The empirical evidence, however, currently supports only a restricted version of the abstract's claim, because the benchmark statistics are incomplete-case estimates and the experiments cover only planar half-grids rather than the motivating PEPS bra-ket networks.

major comments (4)

[Section 4.6 and Table 1] The reported L=9 and L=10 statistics are not complete-case estimates. The text states that one of thirty L=9 samples and sixteen of thirty L=10 samples were terminated after 7200 seconds, and that asterisked cells exclude these incomplete samples. Because Netcon's runtime is longer for harder instances, the 17 excluded cases are not missing at random; they are likely the instances where exact optimization is most difficult, so the mean/median rho values (12.28/3.36 for L=9 and 3.11/2.74 for L=10) may substantially understate Ratcon's error factor on the full sample. The 'generally effective heuristic' claim in the abstract requires either a complete-case analysis, an imputation or documented bound for the excluded cases, or a qualified restatement of the claim.
[Section 4.2] The motivating PEPS bra-ket networks are non-planar, and the paper states that tests on full PEPS forms are deferred. The experiments only cover planar half-grids without free edges. Thus the empirical part of the claim is limited to planar grid-like networks, and the abstract's 'generally effective heuristic' is not directly supported for the motivating workloads. Please either restrict the claim accordingly or provide a concrete argument why the planar half-grid results transfer to the non-planar full PEPS setting.
[Section 3.2, Theorem 3] The statement 'carw(G) = log Bs_G' is imprecise. Carving-width is defined for additive edge weights, whereas Bs is defined via products of bond dimensions; the equality can hold only after applying a logarithmic transformation to the edge weights, and 'up to logarithmic concavity' is not a defined concept. The one-sentence proof, which refers to transferring between the groups (N,+) and (R*,x), does not specify the exact mapping between carving decompositions and contraction trees for weighted graphs. Please restate Theorem 3 with explicit weights and a definition of the transformed carving-width, since Section 4.3 relies on this logarithmic mapping.
[Section 3.3, Lemma 2] The proof of Eq. (7), on which the Bt <= Bs^1.5 bound depends, is too compressed and contains an apparent typo: 'delta_a' union delta_a'' = delta_a union delta_a'' = delta_a intersection delta_a' = delta_n' cannot hold as written, since the last equality uses an intersection sign where a union is intended. The inclusion-exclusion argument appears to be correct, but the derivation needs to be expanded and the set equalities corrected so that the lemma is verifiable.

minor comments (6)

[Definition 4 and Remark] The remark that node labels could be identified with subsets of V but that this identification is not required is confusing, because the free contraction tree constructed later does identify nodes with subsets of V; please clarify what freedom the definition is intended to allow.
[Theorem 1 proof] The phrase 'modulo its 2-cuts delta_a' is unclear; I think the intended meaning is that the node labels alone define the tree-decomposition, while the arc labels are ignored or redundant.
[Theorem 2, step 3] The split rule writes edges(m') = {a',a'',a'''} but edges(m'') = {a'''} union (edges(n) \ {a,a'}); the removed arcs are inconsistent between the two nodes, which makes the splitting step difficult to follow.
[Section 4.2] Square grids are planar and have genus 0; the phrase 'high genera' is inaccurate and should be reworded.
[Algorithm 1] The variables C_s and c_s are not defined inside the algorithm; please clarify that c_s(node) is the single-arc space cost and C_s is the accumulated space bottleneck.
[Section 4.6] The sentence 'Ratcon underperforms for small L, where the time lost in repeated ECs dominates, then becomes exponentially faster at L=9 or 10' is at odds with Table 1, where tau for L=5 is 47.87 (mean) and 35.11 (median); the intended comparison should be stated more carefully.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: the theoretical bounds are proved from explicit definitions and the heuristic is benchmarked against an external exact optimizer.

full rationale

The paper's central theoretical content is self-contained rather than circular. The contraction-tree labels, cut-weights, and the bottleneck measures Bs, Bt, and Ct are explicitly defined in Section 2, and the main inequalities in Section 3 (Bs <= Bt <= Bs^1.5 and the Ct bounds) are proved from those definitions, including the inclusion-exclusion calculation in Lemma 2. The identification between carving-width and log Bs is an exact consequence of the additive-vs-multiplicative group isomorphism stated in Theorem 3, not a hidden restatement of the desired conclusion. The empirical claim that carving-width is a useful heuristic for contraction time is tested by comparing Ratcon's resulting total contraction cost Ct against Netcon, an independent exact optimizer from Pfeifer et al. [21]; the reported ratios are direct comparisons of computed costs and are not quantities that Ratcon was fitted to reproduce. The experimental limitations are real but are not circularity: Section 4.6 excludes the 1/30 L=9 and 16/30 L=10 instances on which Netcon timed out, and Section 4.2 explicitly says tests on full non-planar PEPS bra-ket networks are deferred. These caveats weaken the empirical generalization, but they do not indicate that any derivation reduces to its own inputs.

Assumptions & free parameters 3 free parameters · 4 assumptions · 1 invented entities

The theoretical contribution rests only on standard graph-theoretic definitions and prior algorithmic results. The empirical effectiveness claim, however, depends on several hand-chosen sampling and search parameters (N, memory bound, lognormal priors) and on an untested representativeness assumption about planar half-grids. No new physical entities are introduced.

free parameters (3)

Edge-contraction sample size N = Set to 100 attempts per graph.
Number of random edge-contraction trials used to reduce total time variance; chosen as a practical compromise between runtime and solution quality (Section 4.6).
Memory bound for sampled graphs = Set to 5 TiB, following Pednault et al.
Rejection criterion for generated samples, used to keep networks contractible within stated memory limits (Section 4.2.1).
Lognormal prior parameters mu and sigma = Mu and sigma upper bounds vary with L and were selected by visual inspection of Bs plots.
Choice of sampling distribution determines the difficulty of test instances; the authors tune these parameters so that samples are challenging but feasible (Section 4.2.1).

assumptions (4)

domain assumption A tensor network can be represented as an undirected weighted graph without self-loops or parallel edges, with free indices bound and contracted preliminarily.
Section 2 states this modeling choice and asserts that loop and parallel-edge eliminations never harm efficiency; this excludes hypergraph edges from the analysis.
domain assumption The RAM-model time and space needed for a contraction sequence are proportional, up to multiplicative constants, to Ct and Bs as defined via cut-weights.
Definitions 5 through 9 establish the complexity metrics; the proportionality to actual operation counts is a standard big-Theta assumption for this literature.
domain assumption The Seymour-Thomas Ratcatcher and the edge-contraction algorithm correctly compute carving-width and construct a carving-decomposition for planar graphs.
Section 4.1 and cited references [25, 11, 12] supply the algorithmic correctness; the authors rely on Hicks's reference implementation for their own code.
ad hoc to paper The tested planar half-grids with lognormal edge weights are representative of realistic PEPS-like tensor-network workloads.
Section 4.2 explicitly defers testing on full PEPS bra-ket networks because they are non-planar; the empirical claim of general effectiveness depends on this representativeness.

invented entities (1)

Contraction tree data structure
purpose: Used to unify space and time complexity measures for contraction orders and to drive the Ratcon heuristic.
A formal datatype defined in Section 2.1 that repackages known treewidth and carving-width concepts; it has no falsifiable handle outside this paper, but it organizes the benchmark and the theoretical bounds.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Carving-width and contraction trees for tensor networks." pith.science (2026). https://pith.science/paper/IFU64LOF

@misc{pith2026190811034,
  author       = {Pith},
  title        = {Pith review of: Carving-width and contraction trees for tensor networks},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IFU64LOF}},
  note         = {Machine review of arXiv:1908.11034}
}

abstract

We study the problem of finding contraction orderings on tensor networks for physical simulations using a syncretic abstract data type, the $\textit{contraction-tree}$, and explain its connection to temporal and spatial measures of tensor contraction computational complexity (nodes express time; arcs express space). We have implemented the Ratcatcher of Seymour and Thomas for determining the carving-width of planar networks, in order to offer experimental evidence that this measure of spatial complexity makes a generally effective heuristic for limiting their total contraction time.

Figures

Figures reproduced from arXiv: 1908.11034 by the authors.

**Figure 1.** A 2 × 3-tensor network A, B, . . . , F to label vertices and miniscules a, b, . . . , g for edges. For instance, the index joining tensors A and B, a, is equivalent to the edge {A, B}, and has dimension wa = w({A, B}), with w : E → N + denoting the weight function. 2.1 Contraction [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗

**Figure 2.** A succession of graph minors of fig. 1, showing a full contraction and the accompanying summations. [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗

**Figure 3.** Example rooted contraction tree for fig. 1, with additional labels in boldface. [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗

Figures from the paper (4 more)

**Figure 4.** Figure 4: Contraction tree on fig. 1 (‘free’ version of fig. 3). [PITH_FULL_IMAGE:figures/full_fig_p005_4.png]

**Figure 5.** Figure 5: Bs and Bt uncorrelated. Edge labels are bond dimensions. 4 Efficient computation of contraction orders for planar tensor networks 4.1 ‘Ratcon’ The Ratcatcher algorithm, which gets its name from a game theory analogy the authors of [25] use in their verification proof, …

**Figure 6.** Figure 6: Ket tensor network for a PEPS state. ψ ψ = ψ O ψ = [PITH_FULL_IMAGE:figures/full_fig_p010_6.png]

**Figure 7.** Figure 7: Bra-ket tensor network for a PEPS state. [PITH_FULL_IMAGE:figures/full_fig_p010_7.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

29 extracted references · 20 canonical work pages

[1]

The quantum FFT can be classically simulated

D. Aharonov, Z. Landau, and J. Makowsky. “The quantum FFT can be classically simulated”. In: eprint arXiv:quant-ph/0611156 (Nov. 2006). eprint: quant-ph/0611156

work page Pith review arXiv 2006
[2]

Complexity of ﬁnding embeddings in a k-tree

Stefan Arnborg, Derek G. Corneil, and Andrzej Proskurowski. “Complexity of ﬁnding embeddings in a k-tree”. In: SIAM JOURNAL OF DISCRETE MATHEMATICS 8.2 (1987), pp. 277–284

work page 1987
[3]

Weighted Treewidth: Algorithmic Techniques and Results

Emgad Bachoore and Hans L. Bodlaender. “Weighted Treewidth: Algorithmic Techniques and Results”. In: Algorithms and Computation: 18th International Symposium, ISAAC 2007, Sendai, Japan, December 17-19, 2007. Proceedings. Ed. by Takeshi Tokuyama. Berlin, Heidelberg: Springer Berlin Heidelberg, 2007, pp. 893–903. isbn: 978-3-540-77120-3. doi: 10.1007/978-3-...

work page doi:10.1007/978-3-540-77120- 2007
[4]

Tensor Networks in a Nutshell

J. Biamonte and V. Bergholm. “Tensor Networks in a Nutshell”. In: ArXiv e-prints (July 2017). arXiv: 1708.00006 [quant-ph]

arXiv 2017
[5]

Practical algorithms for branch-decompositions of planar graphs

Zhengbing Bian, Qian-Ping Gu, and Mingzhe Zhu. “Practical algorithms for branch-decompositions of planar graphs”. In: Discrete Applied Mathematics 199 (2016), pp. 156–171

work page 2016
[6]

Hand-waving and interpretive dance: an intro- ductory course on tensor networks

Jacob C Bridgeman and Christopher T Chubb. “Hand-waving and interpretive dance: an intro- ductory course on tensor networks”. In: Journal of Physics A: Mathematical and Theoretical 50.22 (2017), p. 223001. url: http://stacks.iop.org/1751-8121/50/i=22/a=223001

work page 2017
[7]

On the Satisfiability of Quantum Circuits of Small Treewidth

M. de Oliveira Oliveira. “On the Satisﬁability of Quantum Circuits of Small Treewidth”. In: ArXiv e-prints (Apr. 2014). arXiv: 1404.5565 [cs.CC]. 14

work page Pith review arXiv 2014
[8]

Tree-decompositions with Bags of Small Diameter

Yon Dourisboure and Cyril Gavoille. “Tree-decompositions with Bags of Small Diameter”. In: Discrete Math. 307.16 (July 2007), pp. 2008–2029. issn: 0012-365X. doi: 10.1016/j.disc.2005. 12.060. url: http://dx.doi.org/10.1016/j.disc.2005.12.060

work page doi:10.1016/j.disc.2005 2007

Show all 29 references

[9]

Benchmarking treewidth as a practical component of tensor network simulations

Eugene F. Dumitrescu et al. “Benchmarking treewidth as a practical component of tensor network simulations”. In: PLoS ONE 13.12 (Dec. 2018), e0207827. doi: 10.1371/journal.pone.0207827. arXiv: 1807.04599 [cs.DS]

2018 arXiv
[10]

url: https : / / aws

EC2 Instance Types . url: https : / / aws . amazon . com / ec2 / instance - types/ (visited on 07/27/2018)

2018
[11]

Planar branch decompositions I: The ratcatcher

Illya V Hicks. “Planar branch decompositions I: The ratcatcher”. In: INFORMS Journal on Com- puting 17.4 (2005), pp. 402–412

2005
[12]

Planar branch decompositions II: The cycle method

Illya V Hicks. “Planar branch decompositions II: The cycle method”. In: INFORMS Journal on Computing 17.4 (2005), pp. 413–421

2005
[13]

Designing Multi-Commodity Flow Trees

Samir Khuller, Balaji Raghavachari, and Neal E. Young. “Designing Multi-Commodity Flow Trees”. In: CoRR cs.DS/0205077 (2002). url: http://arxiv.org/abs/cs.DS/0205077

2002
[14]

On Optimizing A Class Of Multi-Dimensional Loops With Reductions For Parallel Execution

Chi-Chung Lam, P. Sadayappan, and Rephael Wenger. “On Optimizing A Class Of Multi-Dimensional Loops With Reductions For Parallel Execution”. In: Parallel Processing Letters 7 (1997), pp. 157– 168

1997
[15]

Memory-Optimal Evaluation of Expression Trees Involving Large Objects

Chi-Chung Lam et al. “Memory-Optimal Evaluation of Expression Trees Involving Large Objects”. In: High Performance Computing – HiPC’99 . Ed. by Prith Banerjee, Viktor K. Prasanna, and Bhabani P. Sinha. Berlin, Heidelberg: Springer Berlin Heidelberg, 1999, pp. 103–110. isbn: 97...

1999
[16]

Simulating Quantum Computation by Contracting Tensor Net- works

Igor L. Markov and Yaoyun Shi. “Simulating Quantum Computation by Contracting Tensor Net- works”. In: SIAM Journal on Computing 38.3 (2008), pp. 963–981. doi: 10 . 1137 / 050644756. eprint: https://doi.org/10.1137/050644756. url: https://doi.org/10.1137/050644756

2008 doi
[17]

On the Satisﬁability of Quantum Circuits of Small Treewidth

Mateus de Oliveira Oliveira. “On the Satisﬁability of Quantum Circuits of Small Treewidth”. In: Theory of Computing Systems 61.2 (Aug. 2017), pp. 656–688. issn: 1433-0490. doi: 10.1007 / s00224-016-9727-8 . url: https://doi.org/10.1007/s00224-016-9727-8

2017 doi
[18]

A practical introduction to tensor networks: Matrix product states and projected en- tangled pair states

R. Or´ us. “A practical introduction to tensor networks: Matrix product states and projected en- tangled pair states”. In: Annals of Physics 349 (Oct. 2014), pp. 117–158. doi: 10.1016/j.aop. 2014.06.013. arXiv: 1306.2164 [cond-mat.str-el]

2014 arXiv
[19]

Breaking the 49-Qubit Barrier in the Simulation of Quantum Circuits

E. Pednault et al. “Breaking the 49-Qubit Barrier in the Simulation of Quantum Circuits”. In: ArXiv e-prints (Oct. 2017). arXiv: 1710.05867 [quant-ph]

2017 arXiv
[20]

Matrix Product State Representations

D. Perez-Garcia et al. “Matrix Product State Representations”. In: eprint arXiv:quant-ph/0608197 (Aug. 2006). eprint: quant-ph/0608197

2006 arXiv
[21]

Faster identiﬁcation of optimal con- traction sequences for tensor networks

Robert NC Pfeifer, Jutho Haegeman, and Frank Verstraete. “Faster identiﬁcation of optimal con- traction sequences for tensor networks”. In: Physical Review E 90.3 (2014), p. 033315

2014
[22]

Fast convergence of imaginary time evolution tensor network algorithms by recycling the environment

Ho N. Phien, Ian P. McCulloch, and Guifr´ e Vidal. “Fast convergence of imaginary time evolution tensor network algorithms by recycling the environment”. In: Phys. Rev. B 91.11, 115137 (Mar. 2015), p. 115137. doi: 10.1103/PhysRevB.91.115137. arXiv: 1411.0391 [quant-ph]

2015 arXiv
[23]

Review of Tensor Network Contraction Approaches

S.-J. Ran et al. “Review of Tensor Network Contraction Approaches”. In: ArXiv e-prints (Aug. 2017). arXiv: 1708.09213 [physics.comp-ph]

2017 arXiv
[24]

Simulation of Quantum Many-Body Systems on Amazon Cloud

Justin A. Reyes, Eduardo R. Mucciolo, and Dan Marinescu. “Simulation of Quantum Many-Body Systems on Amazon Cloud”. In: arXiv e-prints , arXiv:1908.08553 (Aug. 2019), arXiv:1908.08553. arXiv: 1908.08553 [cs.DC]

1908 arXiv
[25]

Call routing and the ratcatcher

P. D. Seymour and R. Thomas. “Call routing and the ratcatcher”. In: Combinatorica 14.2 (June 1994), pp. 217–241. issn: 1439-6912. doi: 10.1007/BF01215352 . url: https://doi.org/10. 1007/BF01215352

1994 doi
[26]

N. J. A. Sloane, ed. The On-Line Encyclopedia of Integer Sequences . Sequence A001147. url: https://oeis.org/A001147 (visited on 02/28/2018). 15

2018
[27]

A massively parallel tensor contraction framework for coupled-cluster computations

Edgar Solomonik et al. “A massively parallel tensor contraction framework for coupled-cluster computations”. In: Journal of Parallel and Distributed Computing 74.12 (2014). Domain-Speciﬁc Languages and High-Level Frameworks for High-Performance Computing, pp. 3176–3190. issn: ...

2014
[28]

Classical simulation of quantum computation, the Gottesman-Knill theorem, and slightly beyond

M. Van den Nest. “Classical simulation of quantum computation, the Gottesman-Knill theorem, and slightly beyond”. In: ArXiv e-prints (Nov. 2008). arXiv: 0811.0898 [quant-ph]

2008 arXiv
[29]

Renormalization algorithms for quantum-many body systems in two and higher dimensions

F. Verstraete and J. I. Cirac. “Renormalization algorithms for quantum-many body systems in two and higher dimensions”. In: (2004). arXiv: cond-mat/0407066 [cond-mat] . 16

2004 arXiv

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

The quantum FFT can be classically simulated

D. Aharonov, Z. Landau, and J. Makowsky. “The quantum FFT can be classically simulated”. In: eprint arXiv:quant-ph/0611156 (Nov. 2006). eprint: quant-ph/0611156

work page Pith review arXiv 2006

[2] [2]

Complexity of ﬁnding embeddings in a k-tree

Stefan Arnborg, Derek G. Corneil, and Andrzej Proskurowski. “Complexity of ﬁnding embeddings in a k-tree”. In: SIAM JOURNAL OF DISCRETE MATHEMATICS 8.2 (1987), pp. 277–284

work page 1987

[3] [3]

Weighted Treewidth: Algorithmic Techniques and Results

Emgad Bachoore and Hans L. Bodlaender. “Weighted Treewidth: Algorithmic Techniques and Results”. In: Algorithms and Computation: 18th International Symposium, ISAAC 2007, Sendai, Japan, December 17-19, 2007. Proceedings. Ed. by Takeshi Tokuyama. Berlin, Heidelberg: Springer Berlin Heidelberg, 2007, pp. 893–903. isbn: 978-3-540-77120-3. doi: 10.1007/978-3-...

work page doi:10.1007/978-3-540-77120- 2007

[4] [4]

Tensor Networks in a Nutshell

J. Biamonte and V. Bergholm. “Tensor Networks in a Nutshell”. In: ArXiv e-prints (July 2017). arXiv: 1708.00006 [quant-ph]

arXiv 2017

[5] [5]

Practical algorithms for branch-decompositions of planar graphs

Zhengbing Bian, Qian-Ping Gu, and Mingzhe Zhu. “Practical algorithms for branch-decompositions of planar graphs”. In: Discrete Applied Mathematics 199 (2016), pp. 156–171

work page 2016

[6] [6]

Hand-waving and interpretive dance: an intro- ductory course on tensor networks

Jacob C Bridgeman and Christopher T Chubb. “Hand-waving and interpretive dance: an intro- ductory course on tensor networks”. In: Journal of Physics A: Mathematical and Theoretical 50.22 (2017), p. 223001. url: http://stacks.iop.org/1751-8121/50/i=22/a=223001

work page 2017

[7] [7]

On the Satisfiability of Quantum Circuits of Small Treewidth

M. de Oliveira Oliveira. “On the Satisﬁability of Quantum Circuits of Small Treewidth”. In: ArXiv e-prints (Apr. 2014). arXiv: 1404.5565 [cs.CC]. 14

work page Pith review arXiv 2014

[8] [8]

Tree-decompositions with Bags of Small Diameter

Yon Dourisboure and Cyril Gavoille. “Tree-decompositions with Bags of Small Diameter”. In: Discrete Math. 307.16 (July 2007), pp. 2008–2029. issn: 0012-365X. doi: 10.1016/j.disc.2005. 12.060. url: http://dx.doi.org/10.1016/j.disc.2005.12.060

work page doi:10.1016/j.disc.2005 2007