quantum-computing

On the quantum computational complexity of classical linear dynamics with geometrically local interactions: Dequantization and universality

Kazuki Sakamoto and Keisuke Fujii

26 min read

0 likes

⚡ Quantum Brief

AI Audio Summary

0:00 / 0:00

Click to play

Quantum News · Media Library

Understand this faster with AI

Ask ChatGPT

Research with Perplexity

Explain with Claude

Discuss on Grok

AbstractThe simulation of large-scale classical systems in exponentially small space on quantum computers has gained attention. The prior work demonstrated that a quantum algorithm offers an exponential speedup over any classical algorithm in simulating classical dynamics with long-range interactions. However, many real-world classical systems, such as those arising from partial differential equations, exhibit only local interactions. The question remains whether quantum algorithms can still provide exponential speedup under this condition. In this work, we thoroughly characterize the computational complexity of simulating such geometrically local systems on quantum computers. First, we dequantize the quantum algorithm for simulating short-time (polynomial-time) dynamics of such systems. This implies that the problem of simulating this dynamics does not yield any exponential quantum advantage. Second, we show that simulating short-time dynamics is at least as hard as polynomial-time and linear-space probabilistic classical computation. Third, we show that the computational complexity of simulating long-time (exponential-time) dynamics is captured by exponential-time and polynomial-space quantum computation. This suggests a super-polynomial time advantage when restricting the computation to polynomial-space, or an exponential space advantage otherwise. This work offers new insights into the complexity of classical dynamics governed by partial differential equations, providing a pathway for achieving quantum advantage in practical problems.Featured image: Computational models capturing the complexity of simulating classical linear dynamics with geometrically local interactions. $N=2^n$ is the system size.► BibTeX data@article{Sakamoto2026quantum, doi = {10.22331/q-2026-08-03-2182}, url = {https://doi.org/10.22331/q-2026-08-03-2182}, title = {On the quantum computational complexity of classical linear dynamics with geometrically local interactions: {D}equantization and universality}, author = {Sakamoto, Kazuki and Fujii, Keisuke}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2182}, month = aug, year = {2026} }► References [1] Richard P Feynman. ``Simulating physics with computers''. International Journal of Theoretical Physics 21, 467–488 (1982). https://doi.org/10.1007/BF02650179 [2] Richard P Feynman. ``Quantum mechanical computers.''. Found. Phys. 16, 507–532 (1986). https://doi.org/10.1007/BF01886518 [3] Seth Lloyd. ``Universal quantum simulators''. Science 273, 1073–1078 (1996). https://doi.org/10.1126/science.273.5278.1073 [4] Alexei Y. Kitaev, Alexander Shen, and Mikhail N. Vyalyi. ``Classical and quantum computation''.

American Mathematical Society. (2002). https://doi.org/10.1090/gsm/047 [5] Pedro CS Costa, Stephen Jordan, and Aaron Ostrander. ``Quantum algorithm for simulating the wave equation''. Physical Review A 99, 012323 (2019). https://doi.org/10.1103/PhysRevA.99.012323 [6] Ryan Babbush, Dominic W Berry, Robin Kothari, Rolando D Somma, and Nathan Wiebe. ``Exponential quantum speedup in simulating coupled classical oscillators''. Physical Review X 13, 041041 (2023). https://doi.org/10.1103/PhysRevX.13.041041 [7] Dominic W Berry. ``High-order quantum algorithm for solving linear differential equations''. Journal of Physics A: Mathematical and Theoretical 47, 105301 (2014). https://doi.org/10.1088/1751-8113/47/10/105301 [8] Dominic W Berry, Andrew M Childs, Aaron Ostrander, and Guoming Wang. ``Quantum algorithm for linear differential equations with exponentially improved dependence on precision''. Communications in Mathematical Physics 356, 1057–1081 (2017). https://doi.org/10.1007/s00220-017-3002-y [9] Hari Krovi. ``Improved quantum algorithms for linear and nonlinear differential equations''. Quantum 7, 913 (2023). https://doi.org/10.22331/q-2023-02-02-913 [10] Dominic W Berry and Pedro CS Costa. ``Quantum algorithm for time-dependent differential equations using dyson series''. Quantum 8, 1369 (2024). https://doi.org/10.22331/q-2024-06-13-1369 [11] Guang Hao Low and Yuan Su. ``Quantum eigenvalue processing''. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS). Pages 1051–1062. (2024). https://doi.org/10.1109/FOCS61266.2024.00070 [12] Aram W Harrow, Avinatan Hassidim, and Seth Lloyd. ``Quantum algorithm for linear systems of equations''. Physical review letters 103, 150502 (2009). https://doi.org/10.1103/PhysRevLett.103.150502 [13] Pedro CS Costa, Dong An, Yuval R Sanders, Yuan Su, Ryan Babbush, and Dominic W Berry. ``Optimal scaling quantum linear-systems solver via discrete adiabatic theorem''. PRX quantum 3, 040303 (2022). https://doi.org/10.1103/PRXQuantum.3.040303 [14] Alexander M Dalzell. ``A shortcut to an optimal quantum linear system solver'' (2024). arXiv:2406.12086. arXiv:2406.12086 [15] Guang Hao Low and Yuan Su. ``Quantum linear system algorithm with optimal queries to initial state preparation''. Quantum 10, 2041 (2026). https://doi.org/10.22331/q-2026-03-23-2041 [16] Mauro ES Morales, Lirandë Pira, Philipp Schleich, Kelvin Koor, Pedro CS Costa, Dong An, Alán Aspuru-Guzik, Lin Lin, Patrick Rebentrost, and Dominic W Berry. ``Quantum linear system solvers: A survey of algorithms and applications''. Reviews of Modern Physics 98, 025005 (2026). https://doi.org/10.1103/x6gh-d8gh [17] Shi Jin, Nana Liu, and Yue Yu. ``Quantum simulation of partial differential equations via schrödingerization''.

Physical Review Letters 133, 230602 (2024). https://doi.org/10.1103/PhysRevLett.133.230602 [18] Shi Jin, Nana Liu, and Yue Yu. ``Quantum simulation of partial differential equations: Applications and detailed analysis''. Physical Review A 108, 032603 (2023). https://doi.org/10.1103/PhysRevA.108.032603 [19] Guang Hao Low and Isaac L Chuang. ``Optimal hamiltonian simulation by quantum signal processing''. Physical review letters 118, 010501 (2017). https://doi.org/10.1103/PhysRevLett.118.010501 [20] Guang Hao Low and Isaac L Chuang. ``Hamiltonian simulation by qubitization''. Quantum 3, 163 (2019). https://doi.org/10.22331/q-2019-07-12-163 [21] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. ``Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics''. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. Pages 193–204. (2019). https://doi.org/10.1145/3313276.3316366 [22] Andrew M Childs and Jin-Peng Liu. ``Quantum spectral methods for differential equations''. Communications in Mathematical Physics 375, 1427–1457 (2020). https://doi.org/10.1007/s00220-020-03699-z [23] Di Fang, Lin Lin, and Yu Tong. ``Time-marching based quantum solvers for time-dependent linear differential equations''. Quantum 7, 955 (2023). https://doi.org/10.22331/q-2023-03-20-955 [24] Dong An, Jin-Peng Liu, and Lin Lin. ``Linear combination of hamiltonian simulation for nonunitary dynamics with optimal state preparation cost''.

Physical Review Letters 131, 150603 (2023). https://doi.org/10.1103/PhysRevLett.131.150603 [25] Dong An, Andrew M Childs, and Lin Lin. ``Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters''. Communications in Mathematical Physics 407, 19 (2026). https://doi.org/10.1007/s00220-025-05509-w [26] Adrien Suau, Gabriel Staffelbach, and Henri Calandra. ``Practical quantum computing: Solving the wave equation using a quantum approach''. ACM Transactions on Quantum Computing 2, 1–35 (2021). https://doi.org/10.1145/3430030 [27] Shi Jin, Nana Liu, and Chuwen Ma. ``Quantum simulation of maxwell’s equations via schrödingerisation''. ESAIM: Mathematical Modelling and Numerical Analysis 58, 1853–1879 (2024). https://doi.org/10.1051/m2an/2024046 [28] Junpeng Hu, Shi Jin, Nana Liu, and Lei Zhang. ``Quantum circuits for partial differential equations via schrödingerisation''. Quantum 8, 1563 (2024). https://doi.org/10.22331/q-2024-12-12-1563 [29] Chuwen Ma, Shi Jin, Nana Liu, Kezhen Wang, and Lei Zhang. ``Schrödingerization-based quantum circuits for maxwell’s equations with time-dependent source terms''. Journal of Scientific Computing 108, 43 (2026). https://doi.org/10.1007/s10915-026-03349-x [30] Yuki Sato, Ruho Kondo, Ikko Hamamura, Tamiya Onodera, and Naoki Yamamoto. ``Hamiltonian simulation for hyperbolic partial differential equations by scalable quantum circuits''.

Physical Review Research 6, 033246 (2024). https://doi.org/10.1103/PhysRevResearch.6.033246 [31] Malte Schade, Cyrill Bösch, Václav Hapla, and Andreas Fichtner. ``A quantum computing concept for 1-d elastic wave simulation with exponential speedup''.

Geophysical Journal International 238, 321–333 (2024). https://doi.org/10.1093/gji/ggae160 [32] Yuki Sato, Hiroyuki Tezuka, Ruho Kondo, and Naoki Yamamoto. ``Quantum algorithm for partial differential equations of nonconservative systems with spatially varying parameters''.

Physical Review Applied 23, 014063 (2025). https://doi.org/10.1103/PhysRevApplied.23.014063 [33] Cyrill Bösch, Malte Schade, Giacomo Aloisi, Scott D Keating, and Andreas Fichtner. ``Quantum wave simulation with sources and loss functions''.

Physical Review Research 7, 033225 (2025). https://doi.org/10.1103/t8wt-mp2l [34] Agi Villanyi, Yariv Yanay, and Ari Mizel. ``Exponential quantum advantage for simulating open classical systems'' (2025). arXiv:2503.11483. arXiv:2503.11483 [35] Xiantao Li. ``Exponential quantum speedup for simulating classical lattice dynamics''. Physical review letters 135, 080602 (2025). https://doi.org/10.1103/z2jq-1rxp [36] Sachin S Bharadwaj and Katepalli R Sreenivasan. ``Quantum computation of fluid dynamics''. Indian Academy of Sciences Conference Series 3, 77–96 (2020). https://doi.org/10.29195/iascs.03.01.0015 [37] Ilya Y Dodin and Edward A Startsev. ``On applications of quantum computing to plasma simulations''. Physics of Plasmas 28 (2021). https://doi.org/10.1063/5.0056974 [38] Ewin Tang. ``A quantum-inspired classical algorithm for recommendation systems''. In Proceedings of the 51st annual ACM SIGACT symposium on theory of computing. Pages 217–228. (2019). https://doi.org/10.1145/3313276.3316310 [39] Ewin Tang. ``Dequantizing algorithms to understand quantum advantage in machine learning''.

Nature Reviews Physics 4, 692–693 (2022). https://doi.org/10.1038/s42254-022-00511-w [40] Dhawal Jethwani, François Le Gall, and Sanjay K. Singh. ``Quantum-Inspired Classical Algorithms for Singular Value Transformation''.

In Javier Esparza and Daniel Král', editors, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Volume 170 of Leibniz International Proceedings in Informatics (LIPIcs), pages 53:1–53:14. Dagstuhl, Germany (2020). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.MFCS.2020.53 [41] Nai-Hui Chia, András Pal Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang, and Chunhao Wang. ``Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning''. Journal of the ACM 69, 1–72 (2022). https://doi.org/10.1145/3549524 [42] François Le Gall. ``Robust dequantization of the quantum singular value transformation and quantum machine learning algorithms''. computational complexity 34, 2 (2025). https://doi.org/10.1007/s00037-024-00262-3 [43] Ainesh Bakshi and Ewin Tang. ``An improved classical singular value transformation for quantum machine learning''. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Pages 2398–2453. SIAM (2024). https://doi.org/10.1137/1.9781611977912.86 [44] Sevag Gharibian and François Le Gall. ``Dequantizing the quantum singular value transformation: hardness and applications to quantum chemistry and the quantum pcp conjecture''. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. Pages 19–32. (2022). https://doi.org/10.1145/3519935.3519991 [45] Aram W Harrow and Ashley Montanaro. ``Quantum computational supremacy''. Nature 549, 203–209 (2017). https://doi.org/10.1038/nature23458 [46] Mile Gu, Karoline Wiesner, Elisabeth Rieper, and Vlatko Vedral. ``Quantum mechanics can reduce the complexity of classical models''. Nature communications 3, 762 (2012). https://doi.org/10.1038/ncomms1761 [47] Cina Aghamohammadi, John R Mahoney, and James P Crutchfield. ``Extreme quantum advantage when simulating classical systems with long-range interaction''. Scientific Reports 7, 6735 (2017). https://doi.org/10.1038/s41598-017-04928-7 [48] Kamil Korzekwa and Matteo Lostaglio. ``Quantum advantage in simulating stochastic processes''. Physical Review X 11, 021019 (2021). https://doi.org/10.1103/PhysRevX.11.021019 [49] Thomas J Elliott and Mile Gu. ``Superior memory efficiency of quantum devices for the simulation of continuous-time stochastic processes''. npj Quantum Information 4, 18 (2018). https://doi.org/10.1038/s41534-018-0064-4 [50] Souichi Takahira, Asuka Ohashi, Tomohiro Sogabe, and Tsuyoshi Sasaki Usuda. ``Quantum algorithm for matrix functions by cauchy's integral formula''. Quantum Information and Computation 20, 14–36 (2021). https://doi.org/10.26421/qic20.1-2-2 [51] Souichi Takahira, Asuka Ohashi, Tomohiro Sogabe, and Tsuyoshi Sasaki Usuda. ``Quantum algorithms based on the block-encoding framework for matrix functions by contour integrals''. Quantum Information and Computation (2021). https://doi.org/10.26421/qic22.11-12-4 [52] Dong An, Andrew M. Childs, Lin Lin, and Lexing Ying. ``Laplace transform–based quantum eigenvalue transformation via linear combination of hamiltonian simulation''. SIAM Journal on Computing 55, 376–409 (2026). https://doi.org/10.1137/24M1720160 [53] Yuto Ashida, Zongping Gong, and Masahito Ueda. ``Non-hermitian physics''. Advances in Physics 69, 249–435 (2020). https://doi.org/10.1080/00018732.2021.1876991 [54] Carl M Bender, Dorje C Brody, Hugh F Jones, and Bernhard K Meister. ``Faster than hermitian quantum mechanics''.

Physical Review Letters 98, 040403 (2007). https://doi.org/10.1103/PhysRevLett.98.040403 [55] Shantanav Chakraborty, András Gilyén, and Stacey Jeffery. ``The Power of Block-Encoded Matrix Powers: Improved Regression Techniques via Faster Hamiltonian Simulation''.

In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 33:1–33:14. Dagstuhl, Germany (2019). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2019.33 [56] John M Martyn, Zane M Rossi, Andrew K Tan, and Isaac L Chuang. ``Grand unification of quantum algorithms''. PRX quantum 2, 040203 (2021). https://doi.org/10.1103/PRXQuantum.2.040203 [57] Dong An, Jin-Peng Liu, Daochen Wang, and Qi Zhao. ``Quantum differential equation solvers: Limitations and fast-forwarding: D. an, j.-p. liu, d. wang, q. zhao''. Communications in Mathematical Physics 406, 189 (2025). https://doi.org/10.1007/s00220-025-05358-7 [58] Stephen Wiesner. ``Simulations of many-body quantum systems by a quantum computer'' (1996). arXiv:quant-ph/9603028. arXiv:quant-ph/9603028 [59] Christof Zalka. ``Simulating quantum systems on a quantum computer''. Fortschritte der Physik: Progress of Physics 46, 877–879 (1998). https://doi.org/10.1098/rspa.1998.0162 [60] Giuliano Benenti and Giuliano Strini. ``Quantum simulation of the single-particle schrödinger equation''. American Journal of Physics 76, 657–662 (2008). https://doi.org/10.1119/1.2894532 [61] Andrew M Childs, Jiaqi Leng, Tongyang Li, Jin-Peng Liu, and Chenyi Zhang. ``Quantum simulation of real-space dynamics''. Quantum 6, 860 (2022). https://doi.org/10.22331/q-2022-11-17-860 [62] Asher Peres. ``Reversible logic and quantum computers''. Physical review A 32, 3266 (1985). https://doi.org/10.1103/PhysRevA.32.3266 [63] Maarten Stroeks, Daan Lenterman, Barbara M Terhal, and Yaroslav Herasymenko. ``Solving free fermion problems on a quantum computer''.

Physical Review Research 7, 043176 (2025). https://doi.org/10.1103/zmwm-gdmw [64] Matthias Christandl, Nilanjana Datta, Artur Ekert, and Andrew J Landahl. ``Perfect state transfer in quantum spin networks''. Physical review letters 92, 187902 (2004). https://doi.org/10.1103/PhysRevLett.92.187902 [65] Alastair Kay. ``Perfect, efficient, state transfer and its application as a constructive tool''. International Journal of Quantum Information 8, 641–676 (2010). https://doi.org/10.1142/S0219749910006514 [66] Éric-Olivier Bossé, Luc Vinet, et al. ``Coherent transport in photonic lattices: a survey of recent analytic results''. SIGMA. Symmetry, Integrability and Geometry: Methods and Applications 13, 074 (2017). https://doi.org/10.3842/sigma.2017.074 [67] Ruggero Vaia and Lidia Spadini. ``Persymmetric jacobi matrices with square-integer eigenvalues and dispersionless mass-spring chains''. Linear Algebra and its Applications 585, 164–177 (2020). https://doi.org/10.1016/j.laa.2019.10.002 [68] Hugo Schérer, Luc Vinet, and Alexei Zhedanov. ``Analytic “newton’s cradles” with perfect transfer and fractional revival''. Annals of Physics 439, 168790 (2022). https://doi.org/10.1016/j.aop.2022.168790 [69] Jean-Michel Lemay, Luc Vinet, and Alexei Zhedanov. ``The para-racah polynomials''. Journal of Mathematical Analysis and Applications 438, 565–577 (2016). https://doi.org/10.1016/j.jmaa.2016.02.024 [70] M Nest. ``Classical simulation of quantum computation, the gottesman-knill theorem, and slightly beyond''. Quantum Information and Computation (2010). https://doi.org/10.26421/qic10.3-4-6 [71] Scott Aaronson and Lijie Chen. ``Complexity-Theoretic Foundations of Quantum Supremacy Experiments''. In Ryan O'Donnell, editor, 32nd Computational Complexity Conference (CCC 2017). Volume 79 of Leibniz International Proceedings in Informatics (LIPIcs), pages 22:1–22:67. Dagstuhl, Germany (2017). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.CCC.2017.22 [72] Yaoyun Shi. ``Both toffoli and controlled-not need little help to do universal quantum computation''. Quantum Information and Computation (2003). https://doi.org/10.26421/qic3.1-7 [73] Dorit Aharonov. ``A simple proof that toffoli and hadamard are quantum universal'' (2003). arXiv:quant-ph/0301040. arXiv:quant-ph/0301040 [74] Stephen P Jordan, David Gosset, and Peter J Love. ``Quantum-merlin-arthur–complete problems for stoquastic hamiltonians and markov matrices''. Physical Review A—Atomic, Molecular, and Optical Physics 81, 032331 (2010). https://doi.org/10.1103/PhysRevA.81.032331 [75] Andrew M Childs, David Gosset, and Zak Webb. ``The bose-hubbard model is qma-complete''. In Automata, Languages, and Programming: 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I 41. Pages 308–319. Springer (2014). https://doi.org/10.4086/toc.2015.v011a020 [76] Andrew M Childs. ``Universal computation by quantum walk''. Physical review letters 102, 180501 (2009). https://doi.org/10.1103/PhysRevLett.102.180501 [77] Benjamin A Blumer, Michael S Underwood, and David L Feder. ``Single-qubit unitary gates by graph scattering''. Physical Review A—Atomic, Molecular, and Optical Physics 84, 062302 (2011). https://doi.org/10.1103/PhysRevA.84.062302 [78] Andrew M Childs, David Gosset, and Zak Webb. ``Universal computation by multiparticle quantum walk''. Science 339, 791–794 (2013). https://doi.org/10.1126/science.1229957 [79] Ryan Babbush, Jarrod R McClean, Michael Newman, Craig Gidney, Sergio Boixo, and Hartmut Neven. ``Focus beyond quadratic speedups for error-corrected quantum advantage''. PRX quantum 2, 010103 (2021). https://doi.org/10.1103/PRXQuantum.2.010103 [80] Yufan Zheng, Jiaqi Leng, Yizhou Liu, and Xiaodi Wu. ``On the computational complexity of schrödinger operators'' (2024). arXiv:2411.05120. arXiv:2411.05120Cited by[1] Maarten Stroeks, Daan Lenterman, Barbara M. Terhal, and Yaroslav Herasymenko, "Solving free fermion problems on a quantum computer", Physical Review Research 7 4, 043176 (2025). [2] Yuki Sato, Jumpei Kato, Hiroshi Yano, Kosuke Ito, and Naoki Yamamoto, "Explicit block-encoding for partial differential equation-constrained optimization", arXiv:2511.14420, (2025). [3] Ioannis Kolotouros, Adithya Sireesh, Stuart Ferguson, Sean Thrasher, Petros Wallden, and Julien Michel, "Quantum Elastic Network Models and their Application to Graphene", arXiv:2601.05161, (2026). [4] Hidetaka Manabe, Takanori Sugimoto, and Keisuke Fujii, "Tensor Network Formulation of Dequantized Algorithms for Ground State Energy Estimation", arXiv:2512.13548, (2025). The above citations are from SAO/NASA ADS (last updated successfully 2026-08-03 12:08:34). The list may be incomplete as not all publishers provide suitable and complete citation data.Could not fetch Crossref cited-by data during last attempt 2026-08-03 12:08:27: Could not fetch cited-by data for 10.22331/q-2026-08-03-2182 from Crossref. This is normal if the DOI was registered recently.This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions. AbstractThe simulation of large-scale classical systems in exponentially small space on quantum computers has gained attention. The prior work demonstrated that a quantum algorithm offers an exponential speedup over any classical algorithm in simulating classical dynamics with long-range interactions. However, many real-world classical systems, such as those arising from partial differential equations, exhibit only local interactions. The question remains whether quantum algorithms can still provide exponential speedup under this condition. In this work, we thoroughly characterize the computational complexity of simulating such geometrically local systems on quantum computers. First, we dequantize the quantum algorithm for simulating short-time (polynomial-time) dynamics of such systems. This implies that the problem of simulating this dynamics does not yield any exponential quantum advantage. Second, we show that simulating short-time dynamics is at least as hard as polynomial-time and linear-space probabilistic classical computation. Third, we show that the computational complexity of simulating long-time (exponential-time) dynamics is captured by exponential-time and polynomial-space quantum computation. This suggests a super-polynomial time advantage when restricting the computation to polynomial-space, or an exponential space advantage otherwise. This work offers new insights into the complexity of classical dynamics governed by partial differential equations, providing a pathway for achieving quantum advantage in practical problems.Featured image: Computational models capturing the complexity of simulating classical linear dynamics with geometrically local interactions. $N=2^n$ is the system size.► BibTeX data@article{Sakamoto2026quantum, doi = {10.22331/q-2026-08-03-2182}, url = {https://doi.org/10.22331/q-2026-08-03-2182}, title = {On the quantum computational complexity of classical linear dynamics with geometrically local interactions: {D}equantization and universality}, author = {Sakamoto, Kazuki and Fujii, Keisuke}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2182}, month = aug, year = {2026} }► References [1] Richard P Feynman. ``Simulating physics with computers''. International Journal of Theoretical Physics 21, 467–488 (1982). https://doi.org/10.1007/BF02650179 [2] Richard P Feynman. ``Quantum mechanical computers.''. Found. Phys. 16, 507–532 (1986). https://doi.org/10.1007/BF01886518 [3] Seth Lloyd. ``Universal quantum simulators''. Science 273, 1073–1078 (1996). https://doi.org/10.1126/science.273.5278.1073 [4] Alexei Y. Kitaev, Alexander Shen, and Mikhail N. Vyalyi. ``Classical and quantum computation''.

Read Original

Source Information

Source: Quantum Journal

Website: https://quantum-journal.org/feed/

Discussion

0 professional contributions

Be the first to add a constructive contribution.

On the quantum computational complexity of classical linear dynamics with geometrically local interactions: Dequantization and universality

Tags

Source Information