Quantum Computation and the Evaluation of 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
We present a quantum algorithm that additively approximates the value of a tensor network to a certain scale. When combined with existing results, this provides a complete problem for quantum computation. The result is a simple new way of looking at quantum computation in which unitary gates are replaced by tensors and time is replaced by the order in which the tensor network is “swallowed.” We use this result to derive new quantum algorithms that approximate the partition function of a variety of classical statistical mechanical models, including the Potts model.
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
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539795293172 · Cited by 8,472
Efficient Classical Simulation of Slightly Entangled Quantum Computations
Vidal, G. (2003) · Physical Review Letters · doi:10.1103/physrevlett.91.147902 · Cited by 2,368
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
Classical 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
A Modular Functor Which is Universal¶for Quantum Computation
Freedman, M. H., Larsen, M., & Wang, Z. (2002) · Communications in Mathematical Physics · doi:10.1007/s002200200645 · Cited by 573
Simulating Quantum Computation by Contracting Tensor Networks
Markov, I. L., & Shi, Y. (2008) · SIAM Journal on Computing · doi:10.1137/050644756 · Cited by 472
Dawson, C. M., & Nielsen, M. A. (2006) · Quantum Information and Computation · doi:10.26421/qic6.1-6 · Cited by 288
Classical simulation versus universality in measurement-based quantum computation
Van den Nest, M., Dür, W., Vidal, G., & Briegel, H. J. (2007) · Physical Review A · doi:10.1103/physreva.75.012337 · Cited by 95
Completeness of the Classical 2D Ising Model and Universal Quantum Computation
Van den Nest, M., Dür, W., & Briegel, H. J. (2008) · Physical Review Letters · doi:10.1103/physrevlett.100.110501 · Cited by 63
Classical Spin Models and the Quantum-Stabilizer Formalism
den Nest, M. V., Dür, W., & Briegel, H. J. (2007) · Physical Review Letters · doi:10.1103/physrevlett.98.117207 · Cited by 56
Cited by
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
Quantum algorithms for algebraic problems
Childs, A. M., & van Dam, W. (2010) · Reviews of Modern Physics · doi:10.1103/revmodphys.82.1 · Cited by 344
“More generally, there are efficient quantum algorithms to compute additive approximations of tensor networks (Arad and Landau, 2008).”
MethodQuantum speedup of Monte Carlo methods
Montanaro, A. (2015) · Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.2015.0301 · Cited by 334
Simulating Large Quantum Circuits on a Small Quantum Computer
Peng, T., Harrow, A. W., Ozols, M., & Wu, X. (2020) · Physical Review Letters · doi:10.1103/physrevlett.125.150504 · Cited by 267
Differentiable Programming Tensor Networks
Liao, H.-J., Liu, J.-G., Wang, L., & Xiang, T. (2019) · Physical Review X · doi:10.1103/physrevx.9.031041 · Cited by 251
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
Contracting projected entangled pair states is average-case hard
Haferkamp, J., Hangleiter, D., Eisert, J., & Gluza, M. (2020) · Physical Review Research · doi:10.1103/physrevresearch.2.013010 · Cited by 62
Metadata
- Authors
- Arad, I., & Landau, Z.
- Venue
- SIAM Journal on Computing
- Published
- 2010-01
- Volume
- 39
- Issue
- 7
- Pages
- 3089-3121
- ISSN
- 0097-5397 (ISSN-L)
- 1095-7111
- OpenAlex
- W2023644179
- Cited by
- 70
- References
- 10
- FWCI
- 3.40
- Type
- journal article
- Language
- en
- Open access
- green
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.