Dequantizing the Quantum singular value transformation: hardness and applications to Quantum chemistry and the Quantum PCP conjecture
DOI10.1145/3519935.3519991zbMath1520.68041arXiv2111.09079WikidataQ122911151 ScholiaQ122911151MaRDI QIDQ6083456
François Le Gall, Sevag Gharibian
Publication date: 8 December 2023
Published in: SIAM Journal on Computing, Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2111.09079
quantum chemistrydequantizationBQPlocal Hamiltonianquantum PCPquantum PCP conjecturequantum singular value transformquantum singular-value transform
Quantum computation (81P68) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Molecular physics (81V55) Theory of computing (68Qxx) Quantum algorithms and complexity in the theory of computing (68Q12)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fermionic quantum computation
- Random generation of combinatorial structures from a uniform distribution
- QMA with Subset State Witnesses
- Hardness of Approximation for Quantum Problems
- EXPONENTIAL IMPROVEMENT IN PRECISION FOR SIMULATING SPARSE HAMILTONIANS
- Search via Quantum Walk
- Universal Quantum Simulators
- Approximation Algorithms for QMA-Complete Problems
- Quantum Hamiltonian Complexity
- Adiabatic quantum state generation and statistical zero knowledge
- Mapping local Hamiltonians of fermions to local Hamiltonians of spins
- Quantum Supremacy and the Complexity of Random Circuit Sampling
- Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing Quantum machine learning
- Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
- A quantum-inspired classical algorithm for recommendation systems
- Quantum speedup of Monte Carlo methods
- The computational complexity of linear optics
- Fast monte-carlo algorithms for finding low-rank approximations
- Product-state approximations to quantum ground states
- The complexity of theorem-proving procedures
- Dequantizing the Quantum singular value transformation: hardness and applications to Quantum chemistry and the Quantum PCP conjecture
