Accession Number:

ADA443817

Title:

Qubit Complexity of Continuous Problems

Descriptive Note:

Research rept.

Corporate Author:

COLUMBIA UNIV NEW YORK DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

2005-12-09

Pagination or Media Count:

7.0

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.

Subject Categories:

  • Information Science
  • Numerical Mathematics
  • Quantum Theory and Relativity

Distribution Statement:

APPROVED FOR PUBLIC RELEASE