Simulating Quantum Computation by Contracting Tensor Networks
Open accessAbstract
The treewidth of a graph is a useful combinatorial measure of how close the graph is to a tree. We prove that a quantum circuit with T gates whose underlying graph has a treewidth d can be simulated deterministically in $T^{O(1)}\exp[O(d)]$ time, which, in particular, is polynomial in T if $d=O(\log T)$. Among many implications, we show efficient simulations for log-depth circuits whose gates apply to nearby qubits only, a natural constraint satisfied by most physical implementations. We also show that one-way quantum computation of Raussendorf and Briegel (Phys. Rev. Lett., 86 (2001), pp. 5188–5191), a universal quantum computation scheme with promising physical implementations, can be efficiently simulated by a randomized algorithm if its quantum resource is derived from a small-treewidth graph with a constant maximum degree. (The requirement on the maximum degree was removed in [I. L. Markov and Y. Shi, preprint:quant-ph/0511069].)
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
For the majority of states identified as not universal, efficient classical simulation is possible; specifically, the outcome probabilities of any sequence of single-qubit measurements can be efficiently and exactly computed.
“For example, for the majority of states which have been identified above as not being universal, one has shown that efficient classical simulation is possible. More precisely, for such states it is possible to efficiently and exactly compute the outcome probabilities of any sequence of single-qubit measurements.”
From Measurement-based quantum computation (2009) · cites this paper as [88]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
<i>Quantum Computation and Quantum Information</i>
Nielsen, M. A., Chuang, I., & Grover, L. K. (2002) · American Journal of Physics · doi:10.1119/1.1463744 · Cited by 21,895 · see citing works
Raussendorf, R., & Briegel, H. J. (2001) · Physical Review Letters · doi:10.1103/physrevlett.86.5188 · Cited by 4,477 · see citing works
Efficient Classical Simulation of Slightly Entangled Quantum Computations
Vidal, G. (2003) · Physical Review Letters · doi:10.1103/physrevlett.91.147902 · Cited by 2,368 · see citing works
Persistent Entanglement in Arrays of Interacting Particles
Briegel, H. J., & Raussendorf, R. (2001) · Physical Review Letters · doi:10.1103/physrevlett.86.910 · Cited by 1,950 · see citing works
Graph Minors. II. Algorithmic Aspects of Tree-Width
Robertson, N., & Seymour, P. (1986) · J. Algorithms · doi:10.1016/0196-6774(86)90023-4 · Cited by 1,872 · see citing works
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 · see citing works
Improved simulation of stabilizer circuits
Aaronson, S., & Gottesman, D. (2004) · Physical Review A · doi:10.1103/physreva.70.052328 · Cited by 1,515 · see citing works
Experimental one-way quantum computing
Walther, P., Resch, K. J., Rudolph, T., Schenck, E., Weinfurter, H., Vedral, V., Aspelmeyer, M., & Zeilinger, A. (2005) · Nature · doi:10.1038/nature03347 · Cited by 1,273 · cited 1× · see citing works
“An experimental demonstration of one-way quantum computation appeared in a recent Nature article [28].”
BackgroundComplexity of Finding Embeddings in a k -Tree
Arnborg, S., Corneil, D. G., & Proskurowski, A. (1987) · SIAM Journal on Algebraic and Discrete Methods · doi:10.1137/0608024 · Cited by 1,212 · see citing works
Matrix Product Density Operators: Simulation of Finite-Temperature and Dissipative Systems
Verstraete, F., García-Ripoll, J. J., & Cirac, J. I. (2004) · Physical Review Letters · doi:10.1103/physrevlett.93.207204 · Cited by 1,098 · see citing works
Lubotzky, A., Phillips, R. S., & Sarnak, P. (1988) · COMBINATORICA · doi:10.1007/bf02126799 · Cited by 1,013 · see citing works
On the role of entanglement in quantum-computational speed-up
Jozsa, R., & Linden, N. (2003) · Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.2002.1097 · Cited by 839 · see citing works
Bucket Elimination: A Unifying Framework for Reasoning
Dechter, R. (1999) · Artificial Intelligence · doi:10.1016/s0004-3702(99)00059-4 · Cited by 763 · see citing works
Graph minors. III. Planar tree-width
Robertson, N., & Seymour, P. D. (1984) · Journal of Combinatorial Theory Series B · doi:10.1016/0095-8956(84)90013-3 · Cited by 729 · see citing works
Renormalization algorithms for Quantum-Many Body Systems in two and higher dimensionsPreprint
Verstraete, F., & Cirac, J. I. (2004) · arXiv (Cornell University) · doi:10.48550/arxiv.cond-mat/0407066 · Cited by 672 · see citing works
Graph minors. X. Obstructions to tree-decomposition
Robertson, N., & Seymour, P. D. (1991) · Journal of Combinatorial Theory Series B · doi:10.1016/0095-8956(91)90061-n · Cited by 664 · see citing works
Zwolak, M. P., & Vidal, G. (2004) · Physical Review Letters · doi:10.1103/physrevlett.93.207205 · Cited by 658 · see citing works
Yao, A. C.-C. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1993.366852 · Cited by 639 · see citing works
Triangulated graphs and the elimination process
Rose, D. J. (1970) · Journal of Mathematical Analysis and Applications · doi:10.1016/0022-247x(70)90282-9 · Cited by 507 · see citing works
The Heisenberg Representation of Quantum Computers
Gottesman, D. (1998) · arXiv · doi:10.48550/arxiv.quant-ph/9807006 · Cited by 489 · see citing works
Quantum circuits with mixed states
Aharonov, D., Kitaev, A., & Nisan, N. (1998) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/276698.276708 · Cited by 442 · see citing works
The Heisenberg Representation of Quantum Computers
Gottesman, D. (1998) · University of North Texas Digital Library (University of North Texas) · Cited by 385 · see citing works
Efficient algorithms for combinatorial problems on graphs with bounded decomposability — A survey
Arnborg, S. (1985) · BIT Numerical Mathematics · doi:10.1007/bf01934985 · Cited by 362 · see citing works
Classical simulation of noninteracting-fermion quantum circuits
Terhal, B. M., & DiVincenzo, D. P. (2002) · Physical Review A · doi:10.1103/physreva.65.032325 · Cited by 329 · see citing works
Quantum Circuits That Can Be Simulated Classically in Polynomial Time
Valiant, L. G. (2002) · SIAM Journal on Computing · doi:10.1137/s0097539700377025 · Cited by 311 · see citing works
Fixed Parameter Algorithms for DOMINATING SET and Related Problems on Planar Graphs
Alber, J., Bodlaender, H. L., Fernau, H., Kloks, T., & Niedermeier, R. (2002) · Algorithmica · doi:10.1007/s00453-001-0116-5 · Cited by 304 · see citing works
Treewidth: Algorithmic techniques and results
Bodlaender, H. L. (1997) · Lecture notes in computer science · doi:10.1007/bfb0029946 · Cited by 291 · see citing works
Accurate Reliability Evaluation and Enhancement via Probabilistic Transfer Matrices
Krishnaswamy, S., Viamontes, G. F., Markov, I. L., et al. (2005) · Design, Automation, and Test in Europe · doi:10.1109/date.2005.47 · Cited by 278 · see citing works
Self-citationUniversal Resources for Measurement-Based Quantum Computation
Van den Nest, M., Miyake, A., Dür, W., & Briegel, H. J. (2006) · Physical Review Letters · doi:10.1103/physrevlett.97.150504 · Cited by 238 · see citing works
Efficient Quantum Computation with Probabilistic Quantum Gates
Duan, L.-M., & Raussendorf, R. (2005) · Physical Review Letters · doi:10.1103/physrevlett.95.080503 · Cited by 185 · see citing works
Adaptive Quantum Computation, Constant Depth Quantum Circuits and Arthur-Merlin Games
Terhal, B. M., & Divincenzo, D. P. (2004) · Quantum Information and Computation · doi:10.26421/qic4.2-5 · Cited by 124 · see citing works
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 · see citing works
Quantum Circuits with Mixed StatesPreprint
Aharonov, D., Kitaev, A., & Nisan, N. (1998) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/9806029 · Cited by 71 · see citing works
Measurement-based quantum computation with the toric code states
Bravyi, S., & Raussendorf, R. (2007) · Physical Review A · doi:10.1103/physreva.76.022304 · Cited by 69 · see citing works
Renormalization algorithm for the calculation of spectra of interacting quantum systems
Porras, D., Verstraete, F., & Cirac, J. I. (2006) · Physical Review B · doi:10.1103/physrevb.73.014410 · Cited by 62 · see citing works
Efficient classical simulation of the approximate quantum Fourier transform
Yoran, N., & Short, A. J. (2007) · Physical Review A · doi:10.1103/physreva.76.042321 · Cited by 57 · see citing works
On the simulation of quantum circuitsPreprint
Jozsa, R. (2006) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0603163 · Cited by 49 · see citing works
The quantum FFT can be classically simulatedPreprint
Aharonov, D., Landau, Z. A., & Makowsky, J. A. (2006) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0611156 · Cited by 40 · see citing works
Bounds on the Power of Constant-Depth Quantum Circuits
Fenner, S., Green, F., Homer, S., & Zhang, Y. (2005) · Lecture notes in computer science · doi:10.1007/11537311_5 · Cited by 29 · see citing works
Matrices and tensors in physics
Joshi, A. (1984) · Cited by 28 · see citing works
Quantum Formulas: A Lower Bound and Simulation
Roychowdhury, V., & Vatan, F. (2001) · SIAM Journal on Computing · doi:10.1137/s0097539700370965 · Cited by 6 · see citing works
Width-based algorithms for SAT and CIRCUIT-SAT (extended abstract)
Broering, E., & Lokam, S. V. (2003) · Theory and Applications of Satisfiability Testing · Cited by 3 · see citing works
Bounds on the Power of Constant-Depth Quantum CircuitsPreprint
Fenner, S., Green, F., Homer, S., et al. (2003) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0312209
Flagged first, then by citations
Research works printed but not linked: 1
- [20][20] I. L. Markov and Y. Shi. Simulating quantum computation by contracting tensor networks. Pre-print: quant-ph/0511069. - · arXiv
Cited by
Sorted by citations
Variational quantum algorithms
Cerezo, M., Arrasmith, A., Babbush, R., Benjamin, S. C., Endo, S., Fujii, K., McClean, J. R., Mitarai, K., Yuan, X., Cincio, L., et al. (2021) · Nature Reviews Physics · doi:10.1038/s42254-021-00348-9 · Cited by 3,385 · see citing works
“Moreover, as quantum circuits can be viewed as tensor networks [51], it is quite natural to combine the existing tensor network techniques with a quantum ansatz [52– 54].”
BackgroundCharacterizing quantum supremacy in near-term devices
Boixo, S., Isakov, S. V., Smelyanskiy, V. N., Babbush, R., Ding, N., Jiang, Z., Bremner, M. J., Martinis, J. M., & Neven, H. (2018) · Nature Physics · doi:10.1038/s41567-018-0124-x · Cited by 1,175 · see citing works
Measurement-based quantum computation
Briegel, H. J., Browne, D. E., Dür, W., Raussendorf, R., & Van den Nest, M. (2009) · Nature Physics · doi:10.1038/nphys1157 · Cited by 1,090 · see citing works
Strong Quantum Computational Advantage Using a Superconducting Quantum Processor
Wu, Y., Bao, W.-S., Cao, S., Chen, F., Chen, M.-C., Chen, X., Chung, T.-H., Deng, H., Du, Y., Fan, D., et al. (2021) · Physical Review Letters · doi:10.1103/physrevlett.127.180501 · Cited by 1,059 · see citing works
Validating quantum computers using randomized model circuits
Cross, A. W., Bishop, L. S., Sheldon, S., Nation, P. D., & Gambetta, J. M. (2019) · Physical Review A · doi:10.1103/physreva.100.032328 · Cited by 704 · see citing works
Quantum optimization of maximum independent set using Rydberg atom arrays
Ebadi, S., Keesling, A., Cain, M., Wang, T. T., Levine, H., Bluvstein, D., Semeghini, G., Omran, A., Liu, J.-G., Samajdar, R., et al. (2022) · Science · doi:10.1126/science.abo6587 · Cited by 430 · see citing works
Potential of quantum computing for drug discovery
Cao, Y., Romero, J., & Aspuru-Guzik, A. (2018) · IBM Journal of Research and Development · doi:10.1147/jrd.2018.2888987 · Cited by 357 · see citing works
Simulation of quantum circuits by low-rank stabilizer decompositions
Bravyi, S., Browne, D., Calpin, P., Campbell, E., Gosset, D., & Howard, M. (2019) · Quantum · doi:10.22331/q-2019-09-02-181 · Cited by 302 · see citing works
Information scrambling in quantum circuits
Mi, X., Roushan, P., Quintana, C., Mandrà, S., Marshall, J., Neill, C., Arute, F., Arya, K., Atalaya, J., Babbush, R., et al. (2021) · Science · doi:10.1126/science.abg5029 · Cited by 283 · see citing works
What Limits the Simulation of Quantum Computers?
Zhou, Y., Stoudenmire, E. M., & Waintal, X. (2020) · Physical Review X · doi:10.1103/physrevx.10.041038 · Cited by 254 · see citing works
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 · see citing works
Harnessing the Power of the Second Quantum Revolution
Deutsch, I. H. (2020) · PRX Quantum · doi:10.1103/prxquantum.1.020101 · Cited by 207 · see citing works
Achieving quantum supremacy with sparse and noisy commuting quantum computations
Bremner, M. J., Montanaro, A., & Shepherd, D. J. (2017) · Quantum · doi:10.22331/q-2017-04-25-8 · Cited by 191 · see citing works
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 · see citing works
Computational advantage of quantum random sampling
Hangleiter, D., & Eisert, J. (2023) · Reviews of Modern Physics · doi:10.1103/revmodphys.95.035001 · Cited by 145 · see citing works
Beyond-classical computation in quantum simulation
King, A. D., Nocera, A., Rams, M. M., Dziarmaga, J., Wiersema, R., Bernoudy, W., Raymond, J., Kaushal, N., Heinsdorf, N., Harris, R., et al. (2025) · Science · doi:10.1126/science.ado6285 · Cited by 138 · see citing works
Yao.jl: Extensible, Efficient Framework for Quantum Algorithm Design
Luo, X.-Z., Liu, J.-G., Zhang, P., & Wang, L. (2020) · Quantum · doi:10.22331/q-2020-10-11-341 · Cited by 157 · see citing works
Training the quantum approximate optimization algorithm without access to a quantum processing unit
Streif, M., & Leib, M. (2020) · Quantum Science and Technology · doi:10.1088/2058-9565/ab8c2b · Cited by 125 · see citing works
Begušić, T., Gray, J., & Chan, G. K.-L. (2024) · Science Advances · doi:10.1126/sciadv.adk4321 · Cited by 89 · see citing works
Ayral, T., Louvet, T., Zhou, Y., Lambert, C., Stoudenmire, E. M., & Waintal, X. (2023) · PRX Quantum · doi:10.1103/prxquantum.4.020304 · Cited by 66 · see citing works
Probabilistic simulation of quantum circuits using a deep-learning architecture
Carrasquilla, J., Luo, D., Pérez, F., Milsted, A., Clark, B. K., Volkovs, M., & Aolita, L. (2021) · Physical Review A · doi:10.1103/physreva.104.032610 · Cited by 53 · see citing works
Streif, M., Yarkoni, S., Skolik, A., Neukart, F., & Leib, M. (2021) · Physical Review A · doi:10.1103/physreva.104.012403 · Cited by 41 · see citing works
Density Matrix Renormalization Group with Tensor Processing Units
Ganahl, M., Beall, J., Hauru, M., Lewis, A. G. M., Wojno, T., Yoo, J. H., Zou, Y., & Vidal, G. (2023) · PRX Quantum · doi:10.1103/prxquantum.4.010317 · Cited by 37 · see citing works
Tensor networks contraction and the belief propagation algorithm
Alkabetz, R., & Arad, I. (2021) · Physical Review Research · doi:10.1103/physrevresearch.3.023073 · Cited by 27 · see citing works
- Authors
- Markov, I. L., & Shi, Y.
- Affiliations
- University of Michigan (US)
- Venue
- SIAM Journal on Computing
- Published
- 2008-01
- Volume
- 38
- Issue
- 3
- Pages
- 963-981
- ISSN
- 0097-5397 (ISSN-L)
- 1095-7111
- OpenAlex
- W2072969317
- Cited by
- 472
- References
- 43
- Citations by year
- 2026: 29 · 2025: 54 · 2024: 46 · 2023: 72 · 2022: 42 · 2021: 43 · 2020: 42 · 2019: 26 · 2018: 19 · 2017: 13 · 2016: 18 · 2015: 11 · 2014: 9 · 2013: 7 · 2012: 7
- FWCI
- 14.27
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- SIAM Journal on Computing (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- CERN Document Server (European Organization for Nuclear Research) (submittedVersion)
- arXiv (Cornell University)
- Funders
- National Science Foundation (0323555, 0347078, 0622033, 0208959)
- Defense Advanced Research Projects Agency
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Keywords
- quantum circuit simulation, tensor networks, treewidth, one-way quantum computation, randomized algorithms, deterministic simulation
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
