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

• URL: http://arxiv.org/abs/2111.09079v5
• Date: Thu, 4 Jan 2024 01:25:30 GMT
• Title: Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture
• Authors: Sevag Gharibian and Fran\c{c}ois Le Gall
• Abstract summary: We show that the Quantum Singular Value Transformation can be efficiently "dequantized" We show that with inverse-polynomial precision, the same problem becomes BQP-complete. We also discuss how this dequantization technique may help make progress on the central quantum PCP.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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\'en, 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.

Related papers

• Truncation technique for variational quantum eigensolver for Molecular Hamiltonians [0.0]
  variational quantum eigensolver (VQE) is one of the most promising quantum algorithms for noisy quantum devices. We propose a physically intuitive truncation technique that starts the optimization procedure with a truncated Hamiltonian. This strategy allows us to reduce the required number of evaluations for the expectation value of Hamiltonian on a quantum computer.
  arXiv  Detail & Related papers  (2024-02-02T18:45:12Z)
• Variational-quantum-eigensolver-inspired optimization for spin-chain work extraction [39.58317527488534]
  Energy extraction from quantum sources is a key task to develop new quantum devices such as quantum batteries. One of the main issues to fully extract energy from the quantum source is the assumption that any unitary operation can be done on the system. We propose an approach to optimize the extractable energy inspired by the variational quantum eigensolver (VQE) algorithm.
  arXiv  Detail & Related papers  (2023-10-11T15:59:54Z)
• Quantum Machine Learning: from physics to software engineering [58.720142291102135]
  We show how classical machine learning approach can help improve the facilities of quantum computers. We discuss how quantum algorithms and quantum computers may be useful for solving classical machine learning tasks.
  arXiv  Detail & Related papers  (2023-01-04T23:37:45Z)
• Quantum Computing Quantum Monte Carlo [8.69884453265578]
  We propose a hybrid quantum-classical algorithm that integrates quantum computing and quantum Monte Carlo. Our work paves the way to solving practical problems with intermediatescale and early-fault tolerant quantum computers.
  arXiv  Detail & Related papers  (2022-06-21T14:26:24Z)
• Recent Advances for Quantum Neural Networks in Generative Learning [98.88205308106778]
  Quantum generative learning models (QGLMs) may surpass their classical counterparts. We review the current progress of QGLMs from the perspective of machine learning. We discuss the potential applications of QGLMs in both conventional machine learning tasks and quantum physics.
  arXiv  Detail & Related papers  (2022-06-07T07:32:57Z)
• Theory of Quantum Generative Learning Models with Maximum Mean Discrepancy [67.02951777522547]
  We study learnability of quantum circuit Born machines (QCBMs) and quantum generative adversarial networks (QGANs) We first analyze the generalization ability of QCBMs and identify their superiorities when the quantum devices can directly access the target distribution. Next, we prove how the generalization error bound of QGANs depends on the employed Ansatz, the number of qudits, and input states.
  arXiv  Detail & Related papers  (2022-05-10T08:05:59Z)
• Parametrized Complexity of Quantum Inspired Algorithms [0.0]
  Two promising areas of quantum algorithms are quantum machine learning and quantum optimization. Motivated by recent progress in quantum technologies and in particular quantum software, research and industrial communities have been trying to discover new applications of quantum algorithms.
  arXiv  Detail & Related papers  (2021-12-22T06:19:36Z)
• On exploring practical potentials of quantum auto-encoder with advantages [92.19792304214303]
  Quantum auto-encoder (QAE) is a powerful tool to relieve the curse of dimensionality encountered in quantum physics. We prove that QAE can be used to efficiently calculate the eigenvalues and prepare the corresponding eigenvectors of a high-dimensional quantum state. We devise three effective QAE-based learning protocols to solve the low-rank state fidelity estimation, the quantum Gibbs state preparation, and the quantum metrology tasks.
  arXiv  Detail & Related papers  (2021-06-29T14:01:40Z)
• Towards a NISQ Algorithm to Simulate Hermitian Matrix Exponentiation [0.0]
  A practical fault-tolerant quantum computer is worth looking forward to as it provides applications that outperform their known classical counterparts. It would take decades to make it happen, exploiting the power of noisy intermediate-scale quantum(NISQ) devices, which already exist, is becoming one of current goals. In this article, a method is reported as simulating a hermitian matrix exponentiation using parametrized quantum circuit.
  arXiv  Detail & Related papers  (2021-05-28T06:37:12Z)
• Electronic structure with direct diagonalization on a D-Wave quantum annealer [62.997667081978825]
  This work implements the general Quantum Annealer Eigensolver (QAE) algorithm to solve the molecular electronic Hamiltonian eigenvalue-eigenvector problem on a D-Wave 2000Q quantum annealer. We demonstrate the use of D-Wave hardware for obtaining ground and electronically excited states across a variety of small molecular systems.
  arXiv  Detail & Related papers  (2020-09-02T22:46:47Z)
• Simulating quantum chemistry in the seniority-zero space on qubit-based quantum computers [0.0]
  We combine the so-called seniority-zero, or paired-electron, approximation of computational quantum chemistry with techniques for simulating molecular chemistry on gate-based quantum computers. We show that using the freed-up quantum resources for increasing the basis set can lead to more accurate results and reductions in the necessary number of quantum computing runs.
  arXiv  Detail & Related papers  (2020-01-31T19:44:37Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.