Qubit Complexity of Continuous Problems

Abstract

The number of qubits used by a quantum algorithm will be a crucial computational resource for the foreseeable future. The authors show how to obtain the classical query complexity for continuous problems. They then establish a simple formula for a lower bound on the qubit complexity in terms of the classical query complexity. Sections discuss classical information complexity, fundamental concepts and notation for quantum computation, and lower bound on qubit complexity.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 09, 2005
Accession Number
ADA443817

Entities

People

  • A. Papageorgiou
  • J. F. Traub

Organizations

  • Columbia University

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Accuracy
  • Algorithms
  • Computational Complexity
  • Computations
  • Computer Science
  • Computers
  • Databases
  • Digital Computers
  • Equations
  • Errors
  • Information Processing
  • Measurement
  • Quantum Algorithms
  • Quantum Computers
  • Quantum Computing
  • Quantum Information
  • Simulations

Readers

  • Approximation Theory.
  • Quantum Dot Semiconductor Device Photonics and Graphene Optoelectronic Materials and THz Physics.
  • Systems Analysis and Design

Technology Areas

  • Quantum Computing