Classical and Quantum Complexity of the Sturm-Liouville Eigenvalue Problem

Abstract

The study of the potential power of quantum computers has been a major theoretical challenge. There will be an additional incentive to build a quantum computer if we can identify computationally important problems for which quantum computation offers significant speedups over computation on a classical computer. The Sturm-Liouville eigenvalue problem is defined in full generality. We study the approximation of the smallest eigenvalue of a Sturm-Liouville problem in the classical and quantum settings. We consider a univariate Sturm-Liouville eigenvalue problem with a nonnegative function q from the class C2(0; 1) and study the minimal number n(epsilon) of function evaluations or queries that are necessary to compute an epsilon-approximation of the smallest eigenvalue.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 03, 2005
Accession Number
ADA437678

Entities

People

  • A. Papageorgiou
  • H. Wozniakowski

Organizations

  • Columbia University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Computations
  • Differential Equations
  • Eigenvalues
  • Eigenvectors
  • Equations
  • Mathematics
  • Numbers
  • Probability
  • Quantum Algorithms
  • Quantum Bits
  • Quantum Computers
  • Quantum Computing
  • Quantum Information
  • Quantum Information Science
  • Random Variables
  • Real Numbers
  • Shor'S Algorithm

Fields of Study

  • Mathematics

Readers

  • Distributed Systems and Data Platform Development
  • Linear Algebra
  • Quantum Dot Semiconductor Device Photonics and Graphene Optoelectronic Materials and THz Physics.

Technology Areas

  • Quantum Computing