## Abstract

In 2011, the fundamental gap conjecture for Schrödinger operators was proven. This can be used to estimate the ground state energy of the time-independent Schrödinger equation with a convex potential and relative error ε. Classical deterministic algorithms solving this problem have cost exponential in the number of its degrees of freedom d. We show a quantum algorithm, that is based on a perturbation method, for estimating the ground state energy with relative error ε. The cost of the algorithm is polynomial in d and ε-^{1}, while the number of qubits is polynomial in d and logε-^{1}. In addition, we present an algorithm for preparing a quantum state that overlaps within 1-δ,δ ∈ (0,1), with the ground state eigenvector of the discretized Hamiltonian. This algorithm also approximates the ground state with relative error ε. The cost of the algorithm is polynomial in d, ε-^{1} and δ-^{1}, while the number of qubits is polynomial in d, logε-^{1} and logδ-^{1}.

Original language | English (US) |
---|---|

Pages (from-to) | 469-494 |

Number of pages | 26 |

Journal | Journal of Complexity |

Volume | 30 |

Issue number | 4 |

DOIs | |

State | Published - Aug 2014 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Algebra and Number Theory
- Statistics and Probability
- Numerical Analysis
- Mathematics(all)
- Control and Optimization
- Applied Mathematics

## Keywords

- Eigenvalue problem
- Numerical approximation
- Quantum algorithms