Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture

Abstract

The Quantum Singular Value Transformation (QSVT) is a recent technique that gives a unified framework to describe most quantum algorithms discovered so far, and may lead to the development of novel quantum algorithms. In this paper we investigate the hardness of classically simulating the QSVT. A recent result by Chia, Gilyén, Li, Lin, Tang and Wang (STOC 2020) showed that the QSVT can be efficiently "dequantized" for low-rank matrices, and discussed its implication to quantum machine learning. In this work, motivated by establishing the superiority of quantum algorithms for quantum chemistry and making progress on the quantum PCP conjecture, we focus on the other main class of matrices considered in applications of the QSVT, sparse matrices. We first show how to efficiently "dequantize", with arbitrarily small constant precision, the QSVT associated with a low-degree polynomial. We apply this technique to design classical algorithms that estimate, with constant precision, the singular values of a sparse matrix. We show in particular that a central computational problem considered by quantum algorithms for quantum chemistry (estimating the ground state energy of a local Hamiltonian when given, as an additional input, a state sufficiently close to the ground state) can be solved efficiently with constant precision on a classical computer. As a complementary result, we prove that with inverse-polynomial precision, the same problem becomes BQP-complete. This gives theoretical evidence for the superiority of quantum algorithms for chemistry, and strongly suggests that said superiority stems from the improved precision achievable in the quantum setting. We also discuss how this dequantization technique may help make progress on the central quantum PCP conjecture.

arXiv comment34 pages, presented at STOC 2022; v2: minor corrections and revisions (especially in Section 4.2); v3: minor edits; v4: slightly updated parameters in Theorem 2; v5: final journal version

References in corpus (29)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum algorithm for solving linear systems of equations
• Variational Quantum Algorithms
• Simulated Quantum Computation of Molecular Energies
• Quantum Amplitude Amplification and Estimation
• Fermionic quantum computation
• Hamiltonian Simulation by Qubitization
• A quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors
• Quantum algorithms for quantum chemistry and quantum materials science
• Elucidating Reaction Mechanisms on Quantum Computers
• Even more efficient quantum computations of chemistry through tensor hypercontraction
• Search via Quantum Walk
• Quantum Supremacy and the Complexity of Random Circuit Sampling
• Computational Complexity of interacting electrons and fundamental limitations of Density Functional Theory
• Mapping local Hamiltonians of fermions to local Hamiltonians of spins
• Hamiltonian complexity
• Quantum Hamiltonian Complexity
• Exploiting locality in quantum computation for quantum chemistry
• A mathematical and computational review of Hartree-Fock SCF methods in Quantum Chemistry
• A Compact Fermion to Qubit Mapping
• Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
• Superfast encodings for fermionic quantum simulation
• Local spin operators for fermion simulations
• Computational Complexity in Electronic Structure
• Quantum codes for quantum simulation of Fermions on a square lattice of qubits
• Majorana loop stabilizer codes for error correction of fermionic quantum simulations
• Approximation algorithms for QMA-complete problems
• The complexity of simulating local measurements on quantum systems
• Approximating Hamiltonian dynamics with the Nyström method