---
res:
  bibo_abstract:
  - "The Quantum Singular Value Transformation (QSVT) is a recent technique that\r\ngives
    a unified framework to describe most quantum algorithms discovered so\r\nfar,
    and may lead to the development of novel quantum algorithms. In this paper\r\nwe
    investigate the hardness of classically simulating the QSVT. A recent result\r\nby
    Chia, Gily\\'en, Li, Lin, Tang and Wang (STOC 2020) showed that the QSVT can\r\nbe
    efficiently \"dequantized\" for low-rank matrices, and discussed its\r\nimplication
    to quantum machine learning. In this work, motivated by\r\nestablishing the superiority
    of quantum algorithms for quantum chemistry and\r\nmaking progress on the quantum
    PCP conjecture, we focus on the other main class\r\nof matrices considered in
    applications of the QSVT, sparse matrices.\r\n  We first show how to efficiently
    \"dequantize\", with arbitrarily small\r\nconstant precision, the QSVT associated
    with a low-degree polynomial. We apply\r\nthis technique to design classical algorithms
    that estimate, with constant\r\nprecision, the singular values of a sparse matrix.
    We show in particular that a\r\ncentral computational problem considered by quantum
    algorithms for quantum\r\nchemistry (estimating the ground state energy of a local
    Hamiltonian when\r\ngiven, as an additional input, a state sufficiently close
    to the ground state)\r\ncan be solved efficiently with constant precision on a
    classical computer. As a\r\ncomplementary result, we prove that with inverse-polynomial
    precision, the same\r\nproblem becomes BQP-complete. This gives theoretical evidence
    for the\r\nsuperiority of quantum algorithms for chemistry, and strongly suggests
    that\r\nsaid superiority stems from the improved precision achievable in the quantum\r\nsetting.
    We also discuss how this dequantization technique may help make\r\nprogress on
    the central quantum PCP conjecture.@eng"
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Sevag
      foaf_name: Gharibian, Sevag
      foaf_surname: Gharibian
      foaf_workInfoHomepage: http://www.librecat.org/personId=71541
    orcid: 0000-0002-9992-3379
  - foaf_Person:
      foaf_givenName: François Le
      foaf_name: Gall, François Le
      foaf_surname: Gall
  dct_date: 2022^xs_gYear
  dct_language: eng
  dct_title: 'Dequantizing the Quantum Singular Value Transformation: Hardness and  Applications
    to Quantum Chemistry and the Quantum PCP Conjecture@'
...