Measures of quantum computing speedup

Abstract

We introduce the concept of strong quantum speedup. We prove that approximating the ground state energy of an instance of the time-independent Schrödinger equation, with $d$ degrees of freedom, $d$ large, enjoys strong exponential quantum speedup. It can be easily solved on a quantum computer. Some researchers in discrete complexity theory believe that quantum computation is not effective for eigenvalue problems. One of our goals in this paper is to explain this dissonance.

5 pages, to appear in Phys. Rev. A

References in corpus (2)

• Simulated Quantum Computation of Molecular Energies
• Quantum Algorithms for Quantum Field Theories

Cited by in corpus (12)

• Adiabatic Quantum Computing
• Defining and detecting quantum speedup
• Strengths and weaknesses of weak-strong cluster problems: A detailed overview of state-of-the-art classical heuristics vs quantum approaches
• Algorithm for the solution of the Dirac equation on digital quantum computers
• Quantum Zeno effect in correlated qubits
• A Derivative-free Method for Quantum Perceptron Training in Multi-layered Neural Networks
• Cluster state generation in one-dimensional Kitaev honeycomb model via shortcut to adiabaticity
• Many-Qudit representation for the Travelling Salesman Problem Optimisation
• The superconducting circuit companion -- an introduction with worked examples
• Universal framework for simultaneous tomography of quantum states and SPAM noise
• Superposition of Macroscopically Distinct States in Adiabatic Quantum Computation
• Approximating Ground and Excited State Energies on a Quantum Computer