Faster identification of optimal contraction sequences for tensor networks
Open accessThe DOI matches its Crossref record; 10 of the 10 references it cites were found in a registry or an index.
Abstract
The efficient evaluation of tensor expressions involving sums over multiple indices is of significant importance to many fields of research, including quantum many-body physics, loop quantum gravity, and quantum chemistry. The computational cost of evaluating an expression may depend strongly on the order in which the index sums are evaluated, and determination of the operation-minimizing contraction sequence for a single tensor network (single term, in quantum chemistry) is known to be NP-hard. The current preferred solution is an exhaustive search, using either an iterative depth-first approach with pruning or dynamic programming and memoization, but these approaches are impractical for many of the larger tensor network ansätze encountered in quantum many-body physics. We present a modified search algorithm with enhanced pruning which exhibits a performance increase of several orders of magnitude while still guaranteeing identification of an optimal operation-minimizing contraction sequence for a single tensor network. A reference implementation for matlab, compatible with the ncon() and multienv() network contractors of arXiv:1402.0939 and Evenbly and Pfeifer, Phys. Rev. B 89, 245118 (2014), respectively, is supplied.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Density matrix formulation for quantum renormalization groups
White, S. R. (1992) · Physical Review Letters · doi:10.1103/physrevlett.69.2863 · Cited by 7,702
The density-matrix renormalization group in the age of matrix product states
Schollwöck, U. (2011) · Annals of Physics · doi:10.1016/j.aop.2010.09.012 · Cited by 4,818
Efficient Simulation of One-Dimensional Quantum Many-Body Systems
Vidal, G. (2004) · Physical Review Letters · doi:10.1103/physrevlett.93.040502 · Cited by 1,779
Entanglement renormalization and holography
Swingle, B. (2012) · Physical Review D · doi:10.1103/physrevd.86.065007 · Cited by 915
Classical Simulation of Infinite-Size Quantum Lattice Systems in Two Spatial Dimensions
Jordan, J., Orús, R., Vidal, G., Verstraete, F., & Cirac, J. I. (2008) · Physical Review Letters · doi:10.1103/physrevlett.101.250602 · Cited by 710
Self-citationClassical simulation of quantum many-body systems with a tree tensor network
Shi, Y.-Y., Duan, L.-M., & Vidal, G. (2006) · Physical Review A · doi:10.1103/physreva.74.022320 · Cited by 577
Tagliacozzo, L., Evenbly, G., & Vidal, G. (2009) · Physical Review B · doi:10.1103/physrevb.80.235127 · Cited by 261
Simulating strongly correlated quantum systems with tree tensor networks
Murg, V., Verstraete, F., Legeza, Ö., & Noack, R. M. (2010) · Physical Review B · doi:10.1103/physrevb.82.205105 · Cited by 245
Self-citationStripes in the two-dimensionalt-Jmodel with infinite projected entangled-pair states
Corboz, P., White, S. R., Vidal, G., & Troyer, M. (2011) · Physical Review B · doi:10.1103/physrevb.84.041108 · Cited by 212
Constructing holographic spacetimes using entanglement renormalization
Swingle, B. (2012) · arXiv · doi:10.48550/arxiv.1209.3304 · Cited by 102
Cited by
The ITensor Software Library for Tensor Network Calculations
Fishman, M., White, S., & Stoudenmire, E. M. (2022) · SciPost Physics Codebases · doi:10.21468/scipostphyscodeb.4 · Cited by 1,084
Hand-waving and interpretive dance: an introductory course on tensor networks
Bridgeman, J. C., & Chubb, C. T. (2017) · Journal of Physics A: Mathematical and Theoretical · doi:10.1088/1751-8121/aa6dc3 · Cited by 407
Tensor Network Contractions: Methods and Applications to Quantum Many-Body Systems
Ran, S.-J., Tirrito, E., Peng, C., Chen, X., Tagliacozzo, L., Su, G., & Lewenstein, M. (2020) · Lecture Notes in Physics · doi:10.1007/978-3-030-34489-4 · Cited by 176
Quantum computational advantage via high-dimensional Gaussian boson sampling
Deshpande, A., Mehta, A., Vincent, T., Quesada, N., Hinsche, M., Ioannou, M., Madsen, L., Lavoie, J., Qi, H., Eisert, J., et al. (2022) · Science Advances · doi:10.1126/sciadv.abi7894 · Cited by 106
Metadata
- Authors
- Pfeifer, R. N. C., Haegeman, J., & Verstraete, F.
- Venue
- Physical Review E
- Publisher
- American Physical Society (APS)
- Published
- 2014-09-30
- Volume
- 90
- Issue
- 3
- Pages
- 033315-033315
- ISSN
- 1539-3755 (ISSN-L)
- 1550-2376
- OpenAlex
- W1975277392
- Cited by
- 80
- References
- 10
- FWCI
- 2.33
- Type
- journal article
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.