Efficient Classical Simulation of Slightly Entangled Quantum Computations
Open accessAbstract
We present a classical protocol to efficiently simulate any pure-state quantum computation that involves only a restricted amount of entanglement. More generally, we show how to classically simulate pure-state quantum computations on n qubits by using computational resources that grow linearly in n and exponentially in the amount of entanglement in the quantum computer. Our results imply that a necessary condition for an exponential computational speedup (with respect to classical computations) is that the amount of entanglement increases with the size n of the computation, and provide an explicit lower bound on the required growth.
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?
Statistics converge smoothly to an asymptote, consistent with an exponential tail of truncated singular values.
“Statistics converge smoothly to an asymptote as shown, consistent with an exponential tail of truncated singular values 59 .”
From Beyond-classical computation in quantum simulation (2025) · cites this paper as [59]
The discussion of truncated Schmidt decompositions (p. 4) explains that discarding small Schmidt coefficients can yield an accurate approximation. It does not describe an exponential tail of those coefficients. The sentence presents the smooth convergence of statistics as the citing authors’ observation, rather than a result attributed to Vidal. (LLM, conf=0.82)
Experimental — accuracy not yet measuredThe parameterized quantum circuit features a one-dimensional connectivity pattern, making it suitable for representation using a Matrix Product State (MPS).
“The parameterized quantum circuit in our study features a one-dimensional connectivity pattern, making it suitable for representation using a Matrix Product State (MPS) [56], [57], [58].”
From Towards secondary structure prediction of longer mRNA sequences using a quantum-centric optimization scheme (2025) · cites this paper as [58]
In this work, the multiplicative inverse of α is calculated with seven multipliers, verified by quantum circuit simulation by matrix product state.
“Slight modification of previous method is found in this work with seven multipliers being used, verified by the quantum circuit simulation by matrix product state [52].”
From Time–space complexity of quantum search algorithms in symmetric cryptanalysis: applying to AES and SHA-2 (2018) · cites this paper as [52]
χ_Q shows exponential dependence on L, consistent with area-law scaling.
“Crucially, we observe exponential dependence on L, which is consistent with area-law scaling 59 .”
From Beyond-classical computation in quantum simulation (2025) · cites this paper as [59]
The paper defines Schmidt rank χ as an entanglement measure (p. 1) and discusses exponential dependence of simulation resources on entanglement (p. 3). It does not address χ_Q, exponential scaling with L, or whether that scaling is consistent with an area law; searches for area-law and boundary-size scaling found no such passage. (LLM, conf=0.72)
Experimental — accuracy not yet measuredSeries methods (Taylor, Padé, Chebyshev) are accurate for small matrices but prohibitively expensive for larger systems.
“The Taylor expansion, Pad´ e approximant, and Chebyshev approximant are series methods based on powers of the Hamiltonian 150,151 to approximate the evolution operator. They are accurate for small matrices but prohibitively expensive for larger systems.”
From Quantum Chemistry in the Age of Quantum Computing (2019) · cites this paper as [151]
Using a global quench but starting from a thermal initial state, tDMRG becomes efficient for high temperatures, but becomes exponentially inefficient with time for low-temperature initial states.
“Using the same setup with a global quench, but starting from a thermal initial state, tDMRG becomes efficient for high temperatures [192] where the state and its correlations are almost classical. However, it becomes exponentially inefficient with time for low-temperature initial states.”
From Can one trust quantum simulators? (2012) · cites this paper as [192]
As with classical algorithms, the AQS remains faithful when the state is almost classical (high temperatures); the simulator fidelity decreases rapidly for low temperatures, although it saturates at a fairly high value.
“As with the classical algorithms [192], the AQS remains faithful when the state is almost classical (high temperatures). The simulator fidelity decreases rapidly for low temperatures, although it saturates at a fairly high value.”
From Can one trust quantum simulators? (2012) · cites this paper as [192]
If the quench is global, the computational resources needed to keep a fixed amount of error grow exponentially with time.
“However, if the quench is global, it has been shown that the computational resources needed to keep a fixed amount of error grow exponentially with time [192, 193].”
From Can one trust quantum simulators? (2012) · cites this paper as [192]
Oblivious Schmidt decomposition via QDP may not attain the optimal asymptotic rates as derived from Ref. [51], but it provides a constructive approach to oblivious entanglement distillation with explicit circuit implementations.
“While oblivious Schmidt decomposition via QDP may not attain the optimal asymptotic rates as derived from Ref. [51], it provides a constructive approach to oblivious entanglement distillation with explicit circuit implementations.”
From Quantum Dynamic Programming (2025) · cites this paper as [51]
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
Quantum computation and quantum information
Law, J. (2001) · ACM SIGSOFT Software Engineering Notes · doi:10.1145/505482.505499 · Cited by 20,449 · see citing works
Concentrating partial entanglement by local operations
Bennett, C. H., Bernstein, H. J., Popescu, S., & Schumacher, B. W. (1996) · Physical Review A · doi:10.1103/physreva.53.2046 · Cited by 3,051 · see citing works
Entanglement in Quantum Critical Phenomena
Vidal, G., Latorre, J. I., Rico, E., & Kitaev, A. (2003) · Physical Review Letters · doi:10.1103/physrevlett.90.227902 · Cited by 2,793 · see citing works
Self-citationQuantum Theory: Concepts and Methods
Peres, A., & Ballentine, L. E. (1995) · American Journal of Physics · doi:10.1119/1.17946 · Cited by 2,561 · see citing works
Proceedings 35th Annual Symposium on Foundations of Computer Science
(1994) · doi:10.1109/sfcs.1994 · Cited by 1,133 · see citing works
Zur Theorie der linearen und nichtlinearen Integralgleichungen
Schmidt, E. (1907) · Mathematische Annalen · doi:10.1007/bf01449770 · Cited by 977 · see citing works
Power of One Bit of Quantum Information
Knill, E. H., & Laflamme, R. (1998) · Physical Review Letters · doi:10.1103/physrevlett.81.5672 · Cited by 880 · 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
Entangled quantum systems and the Schmidt decomposition
Ekert, A., & Knight, P. L. (1995) · American Journal of Physics · doi:10.1119/1.17904 · Cited by 453 · 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
Vidal, G. (2000) · Journal of Modern Optics · doi:10.1080/095003400148268 · Cited by 134 · see citing works
Self-citationGood Dynamics versus Bad Kinematics: Is Entanglement Needed for Quantum Computation?
Linden, N., & Popescu, S. (2001) · Physical Review Letters · doi:10.1103/physrevlett.87.047901 · Cited by 113 · see citing works
Efficient Classical Simulation of Optical Quantum Information Circuits
Bartlett, S. D., & Sanders, B. C. (2002) · Physical Review Letters · doi:10.1103/physrevlett.89.207903 · Cited by 68 · see citing works
Quantum Information is Incompressible Without Errors
Koashi, M., & Imoto, N. (2002) · Physical Review Letters · doi:10.1103/physrevlett.89.097904 · Cited by 13 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
Entanglement in many-body systems
Amico, L., Fazio, R., Osterloh, A., & Vedral, V. (2008) · Reviews of Modern Physics · doi:10.1103/revmodphys.80.517 · Cited by 3,745 · see citing works
The density-matrix renormalization group
Schollwöck, U. (2005) · Reviews of Modern Physics · doi:10.1103/revmodphys.77.259 · Cited by 3,323 · see citing works
Ultracold atomic gases in optical lattices: mimicking condensed matter physics and beyond
Lewenstein, M., Sanpera, A., Ahufinger, V., Damski, B., Sen(De), A., & Sen, U. (2007) · Advances in Physics · doi:10.1080/00018730701223200 · Cited by 2,104 · see citing works
Orús, R. (2014) · Annals of Physics · doi:10.1016/j.aop.2014.06.013 · Cited by 2,255 · see citing works
Noisy intermediate-scale quantum algorithms
Bharti, K., Cervera-Lierta, A., Kyaw, T. H., Haug, T., Alperin-Lea, S., Anand, A., Degroote, M., Heimonen, H., Kottmann, J. S., Menke, T., et al. (2022) · Reviews of Modern Physics · doi:10.1103/revmodphys.94.015004 · Cited by 1,726 · see citing works
The classical-quantum boundary for correlations: Discord and related measures
Modi, K., Brodutch, A., Cable, H., Paterek, T., & Vedral, V. (2012) · Reviews of Modern Physics · doi:10.1103/revmodphys.84.1655 · Cited by 1,600 · 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
Quantum Chemistry in the Age of Quantum Computing
Cao, Y., Romero, J., Olson, J. P., Degroote, M., Johnson, P. D., Kieferová, M., Kivlichan, I. D., Menke, T., Peropadre, B., Sawaya, N. P. D., et al. (2019) · Chemical Reviews · doi:10.1021/acs.chemrev.8b00803 · Cited by 1,560 · see citing works
Quantum convolutional neural networks
Cong, I., Choi, S., & Lukin, M. D. (2019) · Nature Physics · doi:10.1038/s41567-019-0648-8 · Cited by 1,517 · see citing works
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 · see citing works
Jaksch, D., & Zoller, P. (2005) · Annals of Physics · doi:10.1016/j.aop.2004.09.010 · Cited by 976 · see citing works
Experimental Quantum Computing without Entanglement
Lanyon, B. P., Barbieri, M., Almeida, M. P., & White, A. G. (2008) · Physical Review Letters · doi:10.1103/physrevlett.101.200501 · Cited by 874 · see citing works
Holographic quantum error-correcting codes: toy models for the bulk/boundary correspondence
Pastawski, F., Yoshida, B., Harlow, D., & Preskill, J. (2015) · Journal of High Energy Physics · doi:10.1007/jhep06(2015)149 · Cited by 958 · see citing works
Towards quantum chemistry on a quantum computer
Lanyon, B. P., Whitfield, J. D., Gillett, G. G., Goggin, M. E., Almeida, M. P., Kassal, I., Biamonte, J. D., Mohseni, M., Powell, B. J., Barbieri, M., et al. (2010) · Nature Chemistry · doi:10.1038/nchem.483 · Cited by 796 · see citing works
Matrix product states represent ground states faithfully
Verstraete, F., & Cirac, J. I. (2006) · Physical Review B · doi:10.1103/physrevb.73.094423 · Cited by 730 · see citing works
FIDELITY APPROACH TO QUANTUM PHASE TRANSITIONS
GU, S.-J. (2010) · International Journal of Modern Physics B · doi:10.1142/s0217979210056335 · Cited by 663 · see citing works
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 · see citing works
Self-citationSimulating Quantum Computation by Contracting Tensor Networks
Markov, I. L., & Shi, Y. (2008) · SIAM Journal on Computing · doi:10.1137/050644756 · Cited by 472 · see citing works
Measuring Entanglement Growth in Quench Dynamics of Bosons in an Optical Lattice
Daley, A. J., Pichler, H., Schachenmayer, J., & Zoller, P. (2012) · Physical Review Letters · doi:10.1103/physrevlett.109.020505 · Cited by 393 · see citing works
Valence-bond states for quantum computation
Verstraete, F., & Cirac, J. I. (2004) · Physical Review A · doi:10.1103/physreva.70.060302 · Cited by 333 · see citing works
Variational quantum algorithms for nonlinear problems
Lubasch, M., Joo, J., Moinier, P., Kiffner, M., & Jaksch, D. (2020) · Physical Review A · doi:10.1103/physreva.101.010301 · Cited by 331 · see citing works
Tensor product methods and entanglement optimization for<i>ab initio</i>quantum chemistry
Szalay, S., Pfeffer, M., Murg, V., Barcza, G., Verstraete, F., Schneider, R., & Legeza, Ö. (2015) · International Journal of Quantum Chemistry · doi:10.1002/qua.24898 · Cited by 314 · see citing works
Can one trust quantum simulators?
Hauke, P., Cucchietti, F. M., Tagliacozzo, L., Deutsch, I., & Lewenstein, M. (2012) · Reports on Progress in Physics · doi:10.1088/0034-4885/75/8/082401 · Cited by 315 · see citing works
Tagliacozzo, L., Evenbly, G., & Vidal, G. (2009) · Physical Review B · doi:10.1103/physrevb.80.235127 · Cited by 261 · see citing works
Self-citationNovel Schemes for Measurement-Based Quantum Computation
Gross, D., & Eisert, J. (2007) · Physical Review Letters · doi:10.1103/physrevlett.98.220503 · Cited by 255 · 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
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 · see citing works
Universal 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
Measurement-based quantum computation beyond the one-way model
Gross, D., Eisert, J., Schuch, N., & Perez-Garcia, D. (2007) · Physical Review A · doi:10.1103/physreva.76.052315 · Cited by 236 · see citing works
Algorithms for finite projected entangled pair states
Lubasch, M., Cirac, J. I., & Bañuls, M.-C. (2014) · Physical Review B · doi:10.1103/physrevb.90.064425 · Cited by 205 · see citing works
Cincio, L., Dziarmaga, J., Rams, M. M., & Zurek, W. H. (2007) · Physical Review A · doi:10.1103/physreva.75.052321 · Cited by 182 · 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
Legeza, Ö., & Sólyom, J. (2004) · Physical Review B · doi:10.1103/physrevb.70.205118 · Cited by 167 · see citing works
Variational quantum eigensolver with fewer qubits
Liu, J.-G., Zhang, Y.-H., Wan, Y., & Wang, L. (2019) · Physical Review Research · doi:10.1103/physrevresearch.1.023025 · Cited by 166 · see citing works
Quantum Hamiltonian Complexity
Gharibian, S., Huang, Y., Landau, Z., & Shin, S. W. (2015) · Foundations and Trends® in Theoretical Computer Science · doi:10.1561/0400000066 · Cited by 144 · see citing works
Is the efficiency of classical simulations of quantum dynamics related to integrability?
Prosen, T., & Žnidarič, M. (2007) · Physical Review E · doi:10.1103/physreve.75.015202 · Cited by 138 · 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
Parallel quantum simulation of large systems on small NISQ computers
Barratt, F., Dborin, J., Bal, M., Stojevic, V., Pollmann, F., & Green, A. G. (2021) · npj Quantum Information · doi:10.1038/s41534-021-00420-3 · Cited by 111 · 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
Self-citationComplete-graph tensor network states: a new fermionic wave function ansatz for molecules
Marti, K. H., Bauer, B., Reiher, M., Troyer, M., & Verstraete, F. (2010) · New Journal of Physics · doi:10.1088/1367-2630/12/10/103008 · Cited by 87 · see citing works
Quantum Approach to Classical Statistical Mechanics
Somma, R. D., Batista, C. D., & Ortiz, G. (2007) · Physical Review Letters · doi:10.1103/physrevlett.99.030603 · Cited by 87 · see citing works
Kim, P., Han, D., & Jeong, K. C. (2018) · Quantum Information Processing · doi:10.1007/s11128-018-2107-3 · Cited by 80 · see citing works
Classical variational simulation of the Quantum Approximate Optimization Algorithm
Medvidović, M., & Carleo, G. (2021) · npj Quantum Information · doi:10.1038/s41534-021-00440-z · Cited by 79 · see citing works
Benchmarking highly entangled states on a 60-atom analogue quantum simulator
Shaw, A. L., Chen, Z., Choi, J., Mark, D. K., Scholl, P., Finkelstein, R., Elben, A., Choi, S., & Endres, M. (2024) · Nature · doi:10.1038/s41586-024-07173-x · Cited by 64 · see citing works
Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage
Gao, X., Kalinowski, M., Chou, C.-N., Lukin, M. D., Barak, B., & Choi, S. (2021) · arXiv · doi:10.48550/arxiv.2112.01657 · Cited by 54 · see citing works
Classical simulability, entanglement breaking, and quantum computation thresholds
Virmani, S., Huelga, S. F., & Plenio, M. B. (2005) · Physical Review A · doi:10.1103/physreva.71.042328 · Cited by 51 · see citing works
Entanglement growth and simulation efficiency in one-dimensional quantum lattice systems
Perales, Á., & Vidal, G. (2008) · Physical Review A · doi:10.1103/physreva.78.042337 · Cited by 49 · see citing works
Self-citationParallel time-dependent variational principle algorithm for matrix product states
Secular, P., Gourianov, N., Lubasch, M., Dolgov, S., Clark, S. R., & Jaksch, D. (2020) · Physical Review B · doi:10.1103/physrevb.101.235123 · Cited by 40 · 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
Self-citationClassical Simulation of Limited-Width Cluster-State Quantum Computation
Yoran, N., & Short, A. J. (2006) · Physical Review Letters · doi:10.1103/physrevlett.96.170503 · Cited by 33 · 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
Gate-based quantum computing for protein design
Khatami, M. H., Mendes, U. C., Wiebe, N., & Kim, P. M. (2023) · PLOS Computational Biology · doi:10.1371/journal.pcbi.1011033 · Cited by 26 · see citing works
Quantum Adiabatic Computation with a Constant Gap Is Not Useful in One Dimension
Hastings, M. B. (2009) · Physical Review Letters · doi:10.1103/physrevlett.103.050502 · Cited by 22 · see citing works
Measurement-Based Quantum Computation and Undecidable Logic
Van den Nest, M., & Briegel, H. J. (2008) · Foundations of Physics · doi:10.1007/s10701-008-9212-6 · Cited by 17 · see citing works
Son, J., Gluza, M., Takagi, R., & Ng, N. H. Y. (2025) · Physical Review Letters · doi:10.1103/physrevlett.134.180602 · Cited by 6 · see citing works
Kumar, V., Alevras, D., Metkar, M., Welling, E., Cade, C., Niesen, I., Friedhoff, T., Park, J.-E., Shivpuje, S., LaDue, M., et al. (2025) · arXiv · doi:10.48550/arxiv.2505.05782 · Cited by 3 · see citing works
“The parameterized quantum circuit in our study features a one-dimensional connectivity pattern, making it suitable for representation using a Matrix Product State (MPS) [56], [57], [58].”
- Authors
- Vidal, G.
- Affiliations
- California Institute of Technology (US)
- Corresponding author
- Vidal, Guifré
- ORCID
- Vidal, Guifré
- Venue
- Physical Review Letters
- Publisher
- American Physical Society (APS)
- Published
- 2003-10-01
- Volume
- 91
- Issue
- 14
- Pages
- 147902-147902
- ISSN
- 0031-9007 (ISSN-L)
- 1079-7114
- OpenAlex
- W2036604884
- Cited by
- 2,368
- References
- 14
- Citations by year
- 2026: 113 · 2025: 201 · 2024: 152 · 2023: 133 · 2022: 151 · 2021: 170 · 2020: 148 · 2019: 133 · 2018: 100 · 2017: 120 · 2016: 94 · 2015: 114 · 2014: 109 · 2013: 92 · 2012: 81
- FWCI
- 36.79
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- Physical Review Letters (publishedVersion)
- PubMed (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
- Keywords
- classical simulation of quantum computation, entanglement, linear optical quantum computation, exponential speedup, entanglement growth, lower bounds
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
