Measures of quantum computing speedup
arXiv:1307.7488 · doi:10.1103/PhysRevA.88.022316
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 degrees of freedom, 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.
arXiv comment5 pages, to appear in Phys. Rev. A
References in corpus (14)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Simulated Quantum Computation of Molecular Energies
- Quantum Amplitude Amplification and Estimation
- A quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors
- Quantum Algorithms for Quantum Field Theories
- Simulation of Electronic Structure Hamiltonians Using Quantum Computers
- Computational Complexity of interacting electrons and fundamental limitations of Density Functional Theory
- Calculating the Thermal Rate Constant with Exponential Speed-Up on a Quantum Computer
- Quantum Algorithm for Obtaining the Energy Spectrum of Molecular Systems
- Limitations of Quantum Simulation Examined by Simulating a Pairing Hamiltonian using Nuclear Magnetic Resonance
- Interacting boson problems are QMA-hard
- Eigenvector Approximation Leading to Exponential Speedup of Quantum Eigenvalue Calculation
- QMA-complete problems for stoquastic Hamiltonians and Markov matrices
- A fast algorithm for approximating the ground state energy on a quantum computer
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