Complexity Bounds for Quantum Computation

Abstract

This project focused on upper and lower bounds for quantum computability using constant depth quantum circuits, and on the complexity theory of such circuits. It established significant differences between resource bounded quantum and classical computation models, particularly emphasizing new examples of where quantum circuits are more powerful than their classical counterparts. A second focus and outgrowth of this work was the creation of efficient quantum algorithms for specific problems and central combinatorial functions. Recent finding include upper bounds for the computational power of constant depth circuits composed of single qubit and CNOT gates, and lower bounds for the computational power of constant depth circuits with single qubit, CNOT and fanout gates. These results represent the power and the limits of small, possibly realizable quantum circuits. Also examined were bounds on computations with additional storage qubits (ancillae), and natural simple functions (realized by small depth circuits) which require ancillae for their computation.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 22, 2007
Accession Number
ADB329046

Entities

People

  • Steven Homer

Organizations

  • Boston University

Tags

Communities of Interest

  • Advanced Electronics

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Computational Complexity
  • Computational Science
  • Computations
  • Computer Science
  • Department Of Defense
  • Governments
  • Information Processing
  • Language
  • Mathematics
  • Polynomials
  • Quantum Algorithms
  • Quantum Circuits
  • Quantum Computing
  • Quantum Information
  • Students

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Integrated Circuit Design and Technology.
  • Quantum Dot Semiconductor Device Photonics and Graphene Optoelectronic Materials and THz Physics.

Technology Areas

  • Quantum Computing