The Complexity of the Quantum Adiabatic Algorithm

Abstract

The Quantum Adiabatic Algorithm has been proposed as a general purpose algorithm for solving hard optimization problems on a quantum computer. Early work on very small sizes indicated that the running time (complexity) only increased as a (quite small) power of the problem size N. We report results of Quantum Monte Carlo simulations, using parallel tempering, with which we determine the minimum energy gap (and hence get information the complexity) for much bigger sizes than was possible before. The aim is to see if there is a "crossover" to exponential complexity at large N. We present data for the typical (median) complexity as a function of N, which indicate a crossover to a first order transition at large sizes. This implies that the complexity is exponential at large N, at least for the problem studied.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 2011
Accession Number
ADA585713

Entities

People

  • Adam P. Young
  • S. Knysh
  • V. N. Smelyanskiy

Organizations

  • University of California, Santa Cruz

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Computers
  • Electronic Mail
  • Energy Gaps
  • Ground State
  • Information Operations
  • Military Research
  • Monte Carlo Method
  • National Security
  • Optimization
  • Phase Transformations
  • Polynomials
  • Quantum Computers
  • Quantum Computing
  • Shor'S Algorithm
  • Simulations
  • Transitions

Fields of Study

  • Computer science

Readers

  • Approximation Theory.
  • Parallel and Distributed Computing.
  • Systems Analysis and Design

Technology Areas

  • Quantum Computing