Cover Image

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

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Sakamoto, Kazuki, Fujii, Keisuke
Format:	Preprint
Published:	2025
Subjects:	Quantum Physics Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Computational complexity of Berry phase estimation in topological phases of matter
by: Hayakawa, Ryu, et al.
Published: (2025)

Improved separation between quantum and classical computers for sampling and functional tasks
by: Marshall, Simon C., et al.
Published: (2024)

Physical complexity and black hole quantum computers
by: Reilly, Michele, et al.
Published: (2025)

Lower bounds for quantum-inspired classical algorithms via communication complexity
by: Mande, Nikhil S., et al.
Published: (2024)

Quantum advantage from random geometrically-two-local Hamiltonian dynamics
by: Quek, Yihui
Published: (2025)

Dequantization and Hardness of Spectral Sum Estimation
by: Edenhofer, Roman, et al.
Published: (2025)

Dequantization Barriers for Guided Stoquastic Hamiltonians
by: Hamoudi, Yassine, et al.
Published: (2026)

Dequantizing Short-Path Quantum Algorithms
by: Gall, François Le, et al.
Published: (2026)

Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture
by: Gharibian, Sevag, et al.
Published: (2021)

Quantum and classical query complexities of functions of matrices
by: Montanaro, Ashley, et al.
Published: (2023)

Robust and optimal loading of general classical data into quantum computers
by: Zhang, Xiao-Ming
Published: (2024)

Quantum computational complexity of matrix functions
by: Cifuentes, Santiago, et al.
Published: (2024)

Classical versus quantum queries in quantum PCPs with classical proofs
by: Buhrman, Harry, et al.
Published: (2024)

On classical advice, sampling advice and complexity assumptions for learning separations
by: Pérez-Guijarro, Jordi
Published: (2024)

Symmetric quantum computation
by: Castro-Silva, Davi, et al.
Published: (2025)

Collapses in quantum-classical probabilistically checkable proofs and the quantum polynomial hierarchy
by: Anand, Kartik, et al.
Published: (2025)

On the complexity of unique quantum witnesses and quantum approximate counting
by: Anshu, Anurag, et al.
Published: (2024)

Classical simulability of quantum circuits followed by sparse classical post-processing
by: Takahashi, Yasuhiro, et al.
Published: (2026)

A full dichotomy for Holant$^c$, inspired by quantum computation
by: Backens, Miriam
Published: (2022)

Space-bounded quantum interactive proof systems
by: Gall, François Le, et al.
Published: (2024)

Whether a quantum computation employs nonlocal resources is operationally undecidable
by: Fields, Chris, et al.
Published: (2025)

Quantum interactive proofs using quantum energy teleportation
by: Ikeda, Kazuki, et al.
Published: (2023)

Expansion of higher-dimensional cubical complexes with application to quantum locally testable codes
by: Dinur, Irit, et al.
Published: (2024)

Quantum Kolmogorov complexity and quantum correlations in deterministic-control quantum Turing machines
by: Lemus, Mariano, et al.
Published: (2023)

How hard is it to verify a classical shadow?
by: Karaiskos, Georgios, et al.
Published: (2025)

On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{EXACT}_{k,l}^n$
by: Yao, Penghui, et al.
Published: (2023)

A note on quantum lower bounds for local search via congestion and expansion
by: Brânzei, Simina, et al.
Published: (2024)

Quantum algorithms to simulate quadratic classical Hamiltonians and optimal control
by: Krovi, Hari
Published: (2024)

On the hardness of learning ground state entanglement of geometrically local Hamiltonians
by: Bouland, Adam, et al.
Published: (2024)

End-to-end complexity for simulating the Schwinger model on quantum computers
by: Sakamoto, Kazuki, et al.
Published: (2023)

Magic and communication complexity
by: Girish, Uma, et al.
Published: (2025)

Bounding the computational power of bosonic systems
by: Upreti, Varun, et al.
Published: (2025)

Quantum computation with indefinite causal structures
by: Araújo, Mateus, et al.
Published: (2017)

Learning quantum states and unitaries of bounded gate complexity
by: Zhao, Haimeng, et al.
Published: (2023)

Polynomial time classical versus quantum algorithms for representation theoretic multiplicities
by: Panova, Greta
Published: (2025)

On the average-case complexity of learning output distributions of quantum circuits
by: Nietner, Alexander, et al.
Published: (2023)

A simple lower bound for the complexity of estimating partition functions on a quantum computer
by: Chen, Zherui, et al.
Published: (2024)

Towards a universal gateset for $\mathsf{QMA}_1$
by: Rudolph, Dorian
Published: (2024)

Computational complexity of isometric tensor network states
by: Malz, Daniel, et al.
Published: (2024)

On query complexity measures and their relations for symmetric functions
by: Mittal, Rajat, et al.
Published: (2021)