pith. sign in

arxiv: 2510.02725 · v2 · submitted 2025-10-03 · 💻 cs.DS · math.CO· quant-ph

Congestion bounds via Laplacian eigenvalues and their application to tensor networks with arbitrary geometry

Sayan Mukherjee , Shinichiro Akiyama This is my paper

Pith reviewed 2026-05-18 10:49 UTC · model grok-4.3

classification 💻 cs.DS math.COquant-ph
keywords Laplacian eigenvaluesgraph embeddingcongestionbinary treestensor network contractionspectral graph theoryhypercubesrandom graphs
0
0 comments X

The pith

Any bijection from graph vertices to binary tree leaves has congestion between λ₂(G)·2n/9 and λₙ(G)·n/4, with an embedding achieving at most λₙ(G)·2n/9.

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

This paper establishes spectral bounds on the congestion incurred when embedding the vertices of any graph into the leaves of a rooted binary tree. Congestion measures the largest number of edges crossing any cut induced by removing an internal tree node. The bounds relate this quantity directly to the smallest nonzero and largest Laplacian eigenvalues of the graph. These results matter for understanding the computational cost of contracting tensor networks that represent quantum circuits or other structured computations on graphs of arbitrary shape. The authors also provide exact results for specific families like hypercubes and lattices, and a practical algorithm to find low-congestion embeddings.

Core claim

We show that for any embedding, the congestion lies between λ₂(G)·2n/9 and λₙ(G)·n/4, letting 0=λ₁(G)≤⋯≤λₙ(G) be the Laplacian eigenvalues of G, and there is an embedding for which the congestion is at most λₙ(G)·2n/9. Beyond these general bounds, we determine the congestion exactly for hypercubes and lattice graphs, and obtain asymptotically tight bounds for random regular graphs and Erdős-Rényi graphs. We further introduce an efficient contraction procedure based on spectral ordering and dynamic programming, which produces low-congestion embeddings in practice.

What carries the argument

Congestion of a bijection from G's vertices to the leaves of a rooted binary tree T, measured as the maximum cut size induced by deleting any internal vertex of T.

Load-bearing premise

The mapping from graph vertices to tree leaves must be a bijection onto the leaves of a rooted binary tree, and congestion is the largest cut size over deletions of internal tree vertices.

What would settle it

Compute all possible embeddings for a small graph such as the 4-cycle or 6-cycle, calculate its exact Laplacian eigenvalues, and check whether every embedding's congestion falls inside the predicted interval or whether the minimal one exceeds λₙ·2n/9.

Figures

Figures reproduced from arXiv: 2510.02725 by Sayan Mukherjee, Shinichiro Akiyama.

Figure 1
Figure 1. Figure 1: (Left): A tensor network (𝐺,𝑇 ) on 6 nodes where each bond of 𝑇 has dimension 2. (Right): The rooted binary tree B representing a contraction order. A node 𝑆 of B represents an intermediate tensor encountered during the contraction procedure and has rank |𝜕𝑆 |, which is indicated at the top of each node. The vertex congestion of this embedding is 4. We now introduce some mathematical notation. Given a weig… view at source ↗
Figure 2
Figure 2. Figure 2: Comparison of the different bounds for: (a) the non-periodic lattice [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Congestion in 50 instances of G (𝑛, 𝑑), shown as mean values with error bars for ±1 sample standard deviation, for (a) 𝑑 = 3 and (b) 𝑑 = 4, for 𝑛 = 10 to 𝑛 = 24. Brown data represent the upper bound of 𝑛𝜆𝑛 (𝐺)/4, maroon dots the theoretical upper bound of Theorem 1.1, and light green dots the lower bound of 2𝑛𝜆2 (𝐺)/9. Insets compare the performance of hierarchical clustering (Algorithm 1), Hyper-Greedy, C… view at source ↗
Figure 4
Figure 4. Figure 4: Congestion in 50 instances of G𝑛,𝑝 , shown as mean values with error bars for ±1 sample standard deviation, for 𝑝 = 0.15 (subplot (a)) and 𝑝 = 0.2 (subplot (b)) for 𝑛 = 10 to 𝑛 = 24. Brown data represent the upper bound of 4𝑚𝜇𝑛 (𝐺)/9 ((19), maroon dots the theoretical upper bound of Theorem 3.1, and light green dots the lower bound of 4𝑚𝜇2 (𝐺)/9 (18). Insets compare the performance of hierarchical clusteri… view at source ↗
Figure 5
Figure 5. Figure 5: Congestions obtained by HSC (Algorithm 1), [PITH_FULL_IMAGE:figures/full_fig_p013_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Congestion in 50 instances of 5-qubit random quantum circuits, shown as mean values with error bars for ±1 sample standard deviation. (a) plots the congestion for circuits consisting only of two-qubit gates and (b) only of three-qubit gates. Here depth of the circuits is increasing from 𝑑 = 10 to 𝑑 = 20. Brown data represents the upper bound of 4𝑚𝜇𝑛 (𝐺)/9 (19), which is improved by the maroon data (20). Th… view at source ↗
Figure 7
Figure 7. Figure 7: Congestion in 50 instances of depth-10 random quantum circuits, shown as mean values with error bars for ±1 sample standard deviation. (a) plots the congestion for circuits consisting only of two-qubit gates and (b) only of three-qubit gates. The number of qubits is increasing from 𝑞 = 10 to 𝑞 = 20. Brown data represents the upper bound of 4𝑚𝜇𝑛 (𝐺)/9 (19), which is improved by the maroon data (20). The low… view at source ↗
read the original abstract

Embedding the vertices of arbitrary graphs into trees while minimizing some measure of overlap is an important problem with applications in computer science and physics. In this work, we consider the problem of bijectively embedding the vertices of an $n$-vertex graph $G$ into the \textit{leaves} of an $n$-leaf \textit{rooted binary tree} $\mathcal{T}$. The congestion of such an embedding is given by the largest size of the cut induced by the two components obtained by deleting any vertex of $\mathcal{T}$. We show that for any embedding, the congestion lies between $\lambda_2(G)\cdot 2n/9$ and $\lambda_n(G)\cdot n/4$, letting $0=\lambda_1(G)\le \cdots \le \lambda_n(G)$ be the Laplacian eigenvalues of $G$, and there is an embedding for which the congestion is at most $\lambda_n(G)\cdot 2n/9$. Beyond these general bounds, we determine the congestion exactly for hypercubes and lattice graphs, and obtain asymptotically tight bounds for random regular graphs and Erd\H{o}s-R\'{e}nyi graphs. We further introduce an efficient contraction procedure based on spectral ordering and dynamic programming, which produces low-congestion embeddings in practice. Numerical experiments on structured graphs, random graphs, and tensor network representations of quantum circuits validate our theoretical bounds and demonstrate the effectiveness of the proposed method. These results yield new spectral bounds on the memory and time complexity of exact tensor network contraction in terms of the underlying graph structure.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 3 minor

Summary. The paper establishes spectral bounds on the congestion of bijective embeddings of the vertices of an arbitrary n-vertex graph G into the leaves of a rooted binary tree T. For any embedding the congestion is at least λ₂(G)·(2n/9) and at most λ_n(G)·(n/4); there also exists an embedding achieving congestion at most λ_n(G)·(2n/9). Exact congestion values are derived for hypercubes and lattice graphs, asymptotically tight bounds are given for random regular and Erdős-Rényi graphs, and an efficient spectral-ordering-plus-dynamic-programming procedure is introduced for constructing low-congestion embeddings. Experiments on structured graphs, random graphs, and tensor-network representations of quantum circuits are used to validate the bounds and demonstrate practical utility for bounding memory and time complexity of exact tensor-network contraction.

Significance. If the central bounds and constructions hold, the work supplies a direct, parameter-free link between Laplacian eigenvalues and tree-embedding congestion that immediately yields new upper and lower bounds on the contraction cost of tensor networks on arbitrary graphs. The combination of general bounds, exact results for concrete families, asymptotic tightness for random graphs, and a reproducible algorithmic procedure with experimental validation constitutes a substantive contribution at the interface of spectral graph theory and tensor-network algorithms.

major comments (1)
  1. [§3.2, Theorem 3.3] §3.2, Theorem 3.3 (existence upper bound): the construction via spectral ordering followed by dynamic programming is asserted to achieve the factor 2n/9, but the analysis only appears to control the maximum cut size up to a looser constant unless an additional charging argument over the binary-tree levels is supplied; this constant is load-bearing for the claimed tightness relative to the general upper bound of n/4.
minor comments (3)
  1. [§6] The experimental section reports results on quantum-circuit tensor networks but does not state the number of independent random seeds or the precise hyper-parameters of the dynamic-programming step; adding these details would improve reproducibility.
  2. [§2] Notation for the rooted binary tree T and the induced cuts is introduced clearly in §2 but the same symbol is occasionally reused for the congestion value itself; a short notational table would eliminate any ambiguity.
  3. [Abstract] The abstract states that the bounds are 'exact/asymptotic' for several families; a single sentence in the introduction summarizing the exact values obtained for the hypercube would help readers locate the result.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading, positive summary, and recommendation for minor revision. We address the major comment below with a clarification of the existing analysis and a commitment to strengthen the exposition.

read point-by-point responses

  1. Referee: [§3.2, Theorem 3.3] §3.2, Theorem 3.3 (existence upper bound): the construction via spectral ordering followed by dynamic programming is asserted to achieve the factor 2n/9, but the analysis only appears to control the maximum cut size up to a looser constant unless an additional charging argument over the binary-tree levels is supplied; this constant is load-bearing for the claimed tightness relative to the general upper bound of n/4.

    Authors: We appreciate the referee drawing attention to the tightness of the constant in Theorem 3.3. The proof proceeds by first applying the spectral ordering to produce a linear arrangement whose maximum cut is bounded by λ_n(G)·n/4 (via the standard Cheeger-type inequality for the largest eigenvalue). The subsequent dynamic-programming step then selects an optimal binary-tree embedding consistent with this ordering. In the analysis, the congestion at each internal node of the tree is bounded by summing the contributions of the cuts that cross the corresponding partition; because the tree is binary, each vertex participates in at most two subtrees per level, and a simple charging argument over the O(log n) levels shows that the maximum congestion is at most (2/3) of the linear-arrangement cut size, yielding the factor 2n/9. The same charging also explains why the bound is strictly tighter than the arbitrary-embedding upper bound of n/4. We acknowledge that the charging step is only sketched rather than isolated as a separate lemma; we will revise the manuscript to make this argument explicit, including a short auxiliary lemma that formalizes the per-level charging. revision: yes

Circularity Check

0 steps flagged

No circularity: bounds derived from standard spectral graph theory and cut definitions

full rationale

The central claims establish lower and upper bounds on tree-embedding congestion directly in terms of the Laplacian eigenvalues λ₂(G) and λₙ(G) of the input graph G, using the standard definition of congestion as the maximum cut size induced by removing an internal tree vertex. These inequalities follow from well-known spectral properties relating the Laplacian quadratic form to cut sizes (e.g., Cheeger-type inequalities and eigenvalue-cut correspondences) together with explicit counting arguments over the binary tree structure. No parameter is fitted to data and then relabeled as a prediction; no load-bearing step reduces to a self-citation whose own justification is internal to the authors; the exact results for hypercubes and lattices are obtained by direct computation on those graphs rather than by renaming a known pattern; and the contraction procedure is presented as a practical algorithm, not as part of the theoretical bound derivation. The derivation chain is therefore independent of the target quantities and self-contained against external mathematical benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on standard facts from spectral graph theory and the definition of rooted binary trees; no free parameters, ad-hoc axioms, or new postulated entities are introduced in the abstract.

axioms (1)
  • standard math Laplacian eigenvalues of an undirected graph satisfy 0 = λ₁ ≤ λ₂ ≤ ⋯ ≤ λₙ
    Invoked throughout the abstract when stating the congestion bounds in terms of λ₂ and λₙ.

pith-pipeline@v0.9.0 · 5820 in / 1356 out tokens · 37150 ms · 2026-05-18T10:49:45.143240+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

72 extracted references · 72 canonical work pages · 2 internal anchors

  1. [1]

    Dorit Aharonov, Zeph Landau, and Johann Makowsky. 2007. The quantum FFT can be classically simulated. (2007). arXiv:quant- ph/0611156 [quant-ph]

    work page arXiv 2007

  2. [2]

    Noga Alon and Vitali D Milman. 1985. 𝜆1, isoperimetric inequalities for graphs, and superconcentrators.Journal of Combinatorial Theory, Series B38, 1 (1985), 73–88

    work page 1985

  3. [3]

    Durhuus, and J

    Jan Ambjorn, B. Durhuus, and J. Frohlich. 1985. Diseases of Triangulated Random Surface Models, and Possible Cures.Nucl. Phys. B257 (1985), 433–449. doi:10.1016/0550-3213(85)90356-6 16•Sayan Mukherjee and Shinichiro Akiyama

    work page doi:10.1016/0550-3213(85)90356-6 1985

  4. [4]

    D. Barth. 1993. Embedding meshes of 𝑑-ary trees into de Bruijn graphs.Parallel Process. Lett.3, 2 (1993), 115–127. doi:10.1142/ S0129626493000150

    work page 1993

  5. [5]

    Bhatt and Frank Thomson Leighton

    Sandeep N. Bhatt and Frank Thomson Leighton. 1984. A framework for solving VLSI graph layout problems.J. Comput. System Sci.28, 2 (1984), 300–343. doi:10.1016/0022-0000(84)90071-0

    work page doi:10.1016/0022-0000(84)90071-0 1984

  6. [6]

    Dan Bienstock. 1990. On embedding graphs in trees.J. Combin. Theory Ser. B49, 1 (1990), 103–136. doi:10.1016/0095-8956(90)90066-9

    work page doi:10.1016/0095-8956(90)90066-9 1990

  7. [7]

    Lukas Burgholzer, Alexander Ploier, and Robert Wille. 2023. Tensor Networks or Decision Diagrams? Guidelines for Classical Quantum Circuit Simulation. (2023). arXiv:2302.06616 [quant-ph]

    work page arXiv 2023

  8. [8]

    Jeff Cheeger. 1970. A lower bound for the smallest eigenvalue of the Laplacian. InProblems in analysis (Sympos. in honor of Salomon Bochner, Princeton Univ., Princeton, N.J., 1969). Princeton Univ. Press, Princeton, NJ, 195–199

    work page 1970

  9. [9]

    Jing Chen, Song Cheng, Haidong Xie, Lei Wang, and Tao Xiang. 2018. Equivalence of restricted Boltzmann machines and tensor network states.Phys. Rev. B97 (Feb 2018), 085104. Issue 8. doi:10.1103/PhysRevB.97.085104

    work page doi:10.1103/physrevb.97.085104 2018

  10. [10]

    Yangyang Chen, Yi Zhao, and Xinyu Han. 2021. Spectral properties of hypercubes with applications.J. Comput. Appl. Math.394 (2021), 113550. doi:10.1016/j.cam.2021.113550

    work page doi:10.1016/j.cam.2021.113550 2021

  11. [11]

    Song Cheng, Chenfeng Cao, Chao Zhang, Yongxiang Liu, Shi-Yao Hou, Pengxiang Xu, and Bei Zeng. 2021. Simulating noisy quantum circuits with matrix product density operators.Phys. Rev. Res.3 (Apr 2021), 023005. Issue 2. doi:10.1103/PhysRevResearch.3.023005

    work page doi:10.1103/physrevresearch.3.023005 2021

  12. [12]

    Song Cheng, Lei Wang, Tao Xiang, and Pan Zhang. 2019. Tree tensor networks for generative modeling.Phys. Rev. B99 (Apr 2019), 155131. Issue 15. doi:10.1103/PhysRevB.99.155131

    work page doi:10.1103/physrevb.99.155131 2019

  13. [13]

    P. Z. Chinn, J. Chvátalová, A. K. Dewdney, and N. E. Gibbs. 1982. The bandwidth problem for graphs and matrices—a survey.J. Graph Theory6, 3 (1982), 223–254. doi:10.1002/jgt.3190060302

    work page doi:10.1002/jgt.3190060302 1982

  14. [14]

    Fan Chung. 2007. Four proofs for the Cheeger inequality and graph partition algorithms. InProceedings of ICCM, Vol. 2. Citeseer, 378

    work page 2007

  15. [15]

    Fan Chung and Mary Radcliffe. 2011. On the spectra of general random graphs.Electron. J. Combin.18, 1 (2011), Paper 215, 14. doi:10.37236/702

    work page doi:10.37236/702 2011

  16. [16]

    Fernandes, and Bruce Reed

    Gruia Călinescu, Cristina G. Fernandes, and Bruce Reed. 2003. Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width.J. Algorithms48, 2 (2003), 333–359. doi:10.1016/S0196-6774(03)00073-7

    work page doi:10.1016/s0196-6774(03)00073-7 2003

  17. [17]

    Carsten Damm, Markus Holzer, and Pierre McKenzie. 2002. The complexity of tensor calculus.computational complexity11 (2002), 54–89

    work page 2002

  18. [18]

    Xue Ding and Tiefeng Jiang. 2010. Spectral distributions of adjacency and Laplacian matrices of random graphs.The Annals of Applied Probability20, 6 (2010), 2086 – 2117. doi:10.1214/10-AAP677

    work page doi:10.1214/10-aap677 2010

  19. [19]

    Jozef Dodziuk. 1984. Difference equations, isoperimetric inequality and transience of certain random walks.Trans. Amer. Math. Soc.284, 2 (1984), 787–794

    work page 1984

  20. [20]

    Tohru Eguchi and Hikaru Kawai. 1982. Number of Random Surfaces on the Lattice and the Large 𝑁 Gauge Theory.Phys. Lett. B110 (1982), 143–147. doi:10.1016/0370-2693(82)91023-1

    work page doi:10.1016/0370-2693(82)91023-1 1982

  21. [21]

    Miroslav Fiedler. 1973. Algebraic connectivity of graphs.Czechoslovak mathematical journal23, 2 (1973), 298–305

    work page 1973

  22. [22]

    Since 2021

    Endowed Project for Quantum Software Research and The University of Tokyo Education. Since 2021. https://qsw.phys.s.u-tokyo.ac.jp/

    work page 2021

  23. [23]

    Joel Friedman. 2003. A proof of Alon’s second eigenvalue conjecture. InProceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing(San Diego, CA, USA)(STOC ’03). Association for Computing Machinery, New York, NY, USA, 720–724. doi:10.1145/780542.780646

    work page doi:10.1145/780542.780646 2003

  24. [24]

    Tatsuya Gima, Tesshu Hanaka, Kohei Noro, Hirotaka Ono, and Yota Otachi. 2024. An improved spectral lower bound of treewidth. arXiv:2404.08520 [math.CO]

    work page arXiv 2024

  25. [25]

    Tatsuya Gima, Tesshu Hanaka, Kohei Noro, Hirotaka Ono, and Yota Otachi. 2024. On a Spectral Lower Bound of Treewidth.IEICE Transactions on Information and SystemsE107.D, 3 (2024), 328–330. doi:10.1587/transinf.2023FCL0002

    work page doi:10.1587/transinf.2023fcl0002 2024

  26. [26]

    Johnnie Gray and Garnet Kin-Lic Chan. 2024. Hyperoptimized Approximate Contraction of Tensor Networks with Arbitrary Geometry. Phys. Rev. X14 (Jan 2024), 011009. Issue 1. doi:10.1103/PhysRevX.14.011009

    work page doi:10.1103/physrevx.14.011009 2024

  27. [27]

    Johnnie Gray and Stefanos Kourtis. 2021. Hyper-optimized tensor network contraction.Quantum5 (March 2021), 410. doi:10.22331/q- 2021-03-15-410

    work page doi:10.22331/q- 2021

  28. [28]

    Packing cycles through prescribed vertices

    Daniel J. Harvey and David R. Wood. 2018. The treewidth of line graphs.J. Combin. Theory Ser. B132 (2018), 157–179. doi:10.1016/j.jctb. 2018.03.007

    work page doi:10.1016/j.jctb 2018

  29. [29]

    Patrick Hayden, Sepehr Nezami, Xiao-Liang Qi, Nathaniel Thomas, Michael Walter, and Zhao Yang. 2016. Holographic duality from random tensor networks.JHEP11 (2016), 009. arXiv:1601.01694 [hep-th] doi:10.1007/JHEP11(2016)009

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1007/jhep11(2016)009 2016

  30. [30]

    Xin Hong, Xiangzhen Zhou, Sanjiang Li, Yuan Feng, and Mingsheng Ying. 2022. A Tensor Network based Decision Diagram for Representation of Quantum Circuits.ACM Trans. Des. Autom. Electron. Syst.27, 6, Article 60 (June 2022), 30 pages. doi:10.1145/3514355

    work page doi:10.1145/3514355 2022

  31. [31]

    Cupjin Huang, Fang Zhang, Michael Newman, Junjie Cai, Xun Gao, Zhengxiong Tian, Junyin Wu, Haihong Xu, Huanjun Yu, Bo Yuan, Mario Szegedy, Yaoyun Shi, and Jianxin Chen. 2020. Classical Simulation of Quantum Supremacy Circuits. (2020). arXiv:2005.06787 [quant- ph] Congestion bounds via Laplacian eigenvalues and their application to tensor networks with arb...

    work page arXiv 2020

  32. [32]

    Jakes-Schauer, D

    J. Jakes-Schauer, D. Anekstein, and P. Wocjan. 2019. Carving-width and contraction trees for tensor networks. (2019). arXiv:1908.11034 [cs.DM]

    work page arXiv 2019

  33. [33]

    Adam S. Jermyn. 2020. Automatic contraction of unstructured tensor networks.SciPost Phys.8 (2020), 005. doi:10.21468/SciPostPhys.8.1. 005

    work page doi:10.21468/scipostphys.8.1 2020

  34. [34]

    Character Expansion Methods for Matrix Models of Dually Weighted Graphs

    Vladimir A. Kazakov, Matthias Staudacher, and Thomas Wynter. 1996. Character expansion methods for matrix models of dually weighted graphs.Commun. Math. Phys.177 (1996), 451–468. arXiv:hep-th/9502132 doi:10.1007/BF02101902

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1007/bf02101902 1996

  35. [35]

    V. G. Knizhnik, Alexander M. Polyakov, and A. B. Zamolodchikov. 1988. Fractal Structure of 2D Quantum Gravity.Mod. Phys. Lett. A3 (1988), 819. doi:10.1142/S0217732388000982

    work page doi:10.1142/s0217732388000982 1988

  36. [36]

    Theodore Kolokolnikov, Braxton Osting, and James Von Brecht. 2014. Algebraic connectivity of Erdös-Rényi graphs near the connectivity threshold.Manuscript in preparation(2014). https://www.mathstat.dal.ca/~tkolokol/papers/critscaling6.pdf

    work page 2014

  37. [37]

    Ephraim Korach and Nir Solel. 1993. Tree-width, path-width, and cutwidth.Discrete Appl. Math.43, 1 (1993), 97–101. doi:10.1016/0166- 218X(93)90171-J

    work page doi:10.1016/0166- 1993

  38. [38]

    Mucciolo, and Andrei E

    Stefanos Kourtis, Claudio Chamon, Eduardo R. Mucciolo, and Andrei E. Ruckenstein. 2019. Fast counting with tensor networks.SciPost Phys.7 (2019), 060. doi:10.21468/SciPostPhys.7.5.060

    work page doi:10.21468/scipostphys.7.5.060 2019

  39. [39]

    Kyohei Kozawa, Yota Otachi, and Koichi Yamazaki. 2009. On spanning tree congestion of graphs.Discrete Math.309, 13 (2009), 4215–4224. doi:10.1016/j.disc.2008.12.021

    work page doi:10.1016/j.disc.2008.12.021 2009

  40. [40]

    2014.Introduction to parallel algorithms and architectures: Arrays·trees·hypercubes

    F Thomson Leighton. 2014.Introduction to parallel algorithms and architectures: Arrays·trees·hypercubes. Elsevier

    work page 2014

  41. [41]

    Michael Levin and Cody P. Nave. 2007. Tensor renormalization group approach to two-dimensional classical lattice models.Phys. Rev. Lett.99, 12 (2007), 120601. doi:10.1103/PhysRevLett.99.120601

    work page doi:10.1103/physrevlett.99.120601 2007

  42. [42]

    quantum supremacy

    Yong (Alexander) Liu, Xin (Lucy) Liu, Fang (Nancy) Li, Haohuan Fu, Yuling Yang, Jiawei Song, Pengpeng Zhao, Zhen Wang, Dajia Peng, Huarong Chen, Chu Guo, Heliang Huang, Wenzhao Wu, and Dexun Chen. 2021. Closing the “quantum supremacy” gap: achieving real-time simulation of a random quantum circuit using a new Sunway supercomputer. InProceedings of the Int...

    work page doi:10.1145/3458817.3487399 2021

  43. [43]

    Christian Löwenstein, Dieter Rautenbach, and Friedrich Regen. 2009. On spanning tree congestion.Discrete Math.309, 13 (2009), 4653–4655. doi:10.1016/j.disc.2009.01.012

    work page doi:10.1016/j.disc.2009.01.012 2009

  44. [44]

    M. J. Luczak and S. D. Noble. 2001. Optimal arrangement of data in a tree directory.Discrete Appl. Math.113, 2-3 (2001), 243–253. doi:10.1016/S0166-218X(01)00174-3

    work page doi:10.1016/s0166-218x(01)00174-3 2001

  45. [45]

    Paul Manuel. 2011. Minimum average congestion of enhanced and augmented hypercubes into complete binary trees.Discrete Appl. Math.159, 5 (2011), 360–366. doi:10.1016/j.dam.2010.12.001

    work page doi:10.1016/j.dam.2010.12.001 2011

  46. [46]

    Simulating quantum computation by contracting tensor networks,

    Igor L. Markov and Yaoyun Shi. 2008. Simulating quantum computation by contracting tensor networks.SIAM J. Comput.38, 3 (2008), 963–981. doi:10.1137/050644756

    work page doi:10.1137/050644756 2008

  47. [47]

    John Martyn, Guifre Vidal, Chase Roberts, and Stefan Leichenauer. 2020. Entanglement and Tensor Networks for Supervised Image Classification. (7 2020). arXiv:2007.06082 [quant-ph]

    work page arXiv 2020

  48. [48]

    Brendan D McKay. 1981. The expected eigenvalue distribution of a large regular graph.Linear Algebra and its applications40 (1981), 203–216

    work page 1981

  49. [49]

    Yannick Meurice, Ryo Sakai, and Judah Unmuth-Yockey. 2022. Tensor lattice field theory for renormalization and quantum computing. Rev. Mod. Phys.94, 2 (2022), 025005. doi:10.1103/RevModPhys.94.025005

    work page doi:10.1103/revmodphys.94.025005 2022

  50. [50]

    Bojan Mohar. 1989. Isoperimetric numbers of graphs.Journal of combinatorial theory, Series B47, 3 (1989), 274–291

    work page 1989

  51. [51]

    Bojan Mohar. 1991. The Laplacian spectrum of graphs. InGraph theory, combinatorics, and applications. Vol. 2 (Kalamazoo, MI, 1988). Wiley, New York, 871–898

    work page 1991

  52. [52]

    Sayan Mukherjee and Shinichiro Akiyama. 2025. Code for: Congestion bounds via Laplacian eigenvalues and their application to tensor networks with arbitrary geometry. https://github.com/Potla1995/congestion-laplacian

    work page 2025

  53. [53]

    Andrew Ng, Michael Jordan, and Yair Weiss. 2001. On spectral clustering: Analysis and an algorithm.Advances in neural information processing systems14 (2001)

    work page 2001

  54. [54]

    Tomotoshi Nishino and Kouichi Okunishi. 1996. Corner Transfer Matrix Renormalization Group Method.Journal of the Physical Society of Japan65, 4 (April 1996), 891–894. doi:10.1143/jpsj.65.891

    work page doi:10.1143/jpsj.65.891 1996

  55. [55]

    [2023]©2023

    Martin Nöllenburg and Sergey Pupyrev. [2023]©2023. On families of planar DAGs with constant stack number. InGraph drawing and network visualization. Part I. Lecture Notes in Comput. Sci., Vol. 14465. Springer, Cham, 135–151. doi:10.1007/978-3-031-49272-3_10

    work page doi:10.1007/978-3-031-49272-3_10 2023

  56. [56]

    Bryan O’Gorman. 2019. Parameterization of tensor network contraction. In14th Conference on the Theory of Quantum Computation, Communication and Cryptography. LIPIcs. Leibniz Int. Proc. Inform., Vol. 135. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Art. No. 10, 19

    work page 2019

  57. [57]

    Kouichi Okunishi, Tomotoshi Nishino, and Hiroshi Ueda. 2022. Developments in the Tensor Network – from Statistical Mechanics to Quantum Entanglement.J. Phys. Soc. Jap.91 (2022), 062001. doi:10.7566/JPSJ.91.062001

    work page doi:10.7566/jpsj.91.062001 2022

  58. [58]

    Román Orús. 2019. Tensor networks for complex quantum systems.APS Physics1 (2019), 538–550. doi:10.1038/s42254-019-0086-7 18•Sayan Mukherjee and Shinichiro Akiyama

    work page doi:10.1038/s42254-019-0086-7 2019

  59. [59]

    M. I. Ostrovskii. 2004. Minimal congestion trees.Discrete Math.285, 1-3 (2004), 219–226. doi:10.1016/j.disc.2004.02.009

    work page doi:10.1016/j.disc.2004.02.009 2004

  60. [60]

    Feng Pan, Pengfei Zhou, Sujie Li, and Pan Zhang. 2020. Contracting Arbitrary Tensor Networks: General Approximate Algorithm and Applications in Graphical Models and Quantum Circuit Simulations.Phys. Rev. Lett.125 (Aug 2020), 060503. Issue 6. doi:10.1103/ PhysRevLett.125.060503

    work page 2020

  61. [61]

    Richard Peng, He Sun, and Luca Zanetti. 2015. Partitioning well-clustered graphs: Spectral clustering works!. InConference on learning theory. PMLR, 1423–1455

    work page 2015

  62. [62]

    Robert N. C. Pfeifer, Jutho Haegeman, and Frank Verstraete. 2014. Faster identification of optimal contraction sequences for tensor networks.Phys. Rev. E90 (Sep 2014), 033315. Issue 3. doi:10.1103/PhysRevE.90.033315

    work page doi:10.1103/physreve.90.033315 2014

  63. [63]

    Sundara Rajan, A

    R. Sundara Rajan, A. Berin Greeni, and P. Leo Joshwa. 2023. Maximum subgraph problem and minimum linear arrangement of generalized Sierpinski graphs.J. Graph Algorithms Appl.27, 9 (2023), 767–782

    work page 2023

  64. [64]

    Frank Schindler and Adam S Jermyn. 2020. Algorithms for tensor network contraction ordering.Machine Learning: Science and Technology1, 3 (jul 2020), 035001. doi:10.1088/2632-2153/ab94c5

    work page doi:10.1088/2632-2153/ab94c5 2020

  65. [65]

    Roman Schutski, Taras Khakhulin, Ivan Oseledets, and Dmitry Kolmakov. 2020. Simple heuristics for efficient parallel tensor contraction and quantum circuit simulation.Phys. Rev. A102 (Dec 2020), 062614. Issue 6. doi:10.1103/PhysRevA.102.062614

    work page doi:10.1103/physreva.102.062614 2020

  66. [66]

    Seymour and Robin Thomas

    Paul D. Seymour and Robin Thomas. 1994. Call routing and the ratcatcher.Combinatorica14 (1994), 217–241

    work page 1994

  67. [67]

    Edwin Stoudenmire and David J Schwab. 2016. Supervised learning with tensor networks.Advances in neural information processing systems29 (2016)

    work page 2016

  68. [68]

    Sunil Chandran and C

    L. Sunil Chandran and C. R. Subramanian. 2003. A spectral lower bound for the treewidth of a graph and its consequences.Inform. Process. Lett.87, 4 (2003), 195–200. doi:10.1016/S0020-0190(03)00286-2

    work page doi:10.1016/s0020-0190(03)00286-2 2003

  69. [69]

    Verstraete, J

    F. Verstraete, V. Murg, and J.I. Cirac. 2008. Matrix product states, projected entangled pair states, and variational renormalization group methods for quantum spin systems.Advances in Physics57, 2 (March 2008), 143–224. doi:10.1080/14789940801912366

    work page doi:10.1080/14789940801912366 2008

  70. [70]

    Guifré Vidal. 2003. Efficient Classical Simulation of Slightly Entangled Quantum Computations.Phys. Rev. Lett.91 (Oct 2003), 147902. Issue 14. doi:10.1103/PhysRevLett.91.147902

    work page doi:10.1103/physrevlett.91.147902 2003

  71. [71]

    Wahl and Sergii Strelchuk

    Thorsten B. Wahl and Sergii Strelchuk. 2023. Simulating Quantum Circuits Using Efficient Tensor Network Contraction Algorithms with Subexponential Upper Bound.Phys. Rev. Lett.131 (Oct 2023), 180601. Issue 18. doi:10.1103/PhysRevLett.131.180601

    work page doi:10.1103/physrevlett.131.180601 2023

  72. [72]

    Steven R. White. 1992. Density matrix formulation for quantum renormalization groups.Phys. Rev. Lett.69 (Nov 1992), 2863–2866. Issue 19. doi:10.1103/PhysRevLett.69.2863

    work page doi:10.1103/physrevlett.69.2863 1992