QuaCGR Fellowship: Adiabatic Quantum Algorithms

Abstract

We studied the quantum adiabatic algorithm for combinatorial optimization. We obtained a simpler proof of the adiabatic theorem. However, we did not make much progress in developing new tools for rigorous analysis of the algorithm's performance on realistic optimization problems. This analysis seems to be substantially more difficult than for classical algorithms such as simulated annealing, because the ground state does not have a simple form. We also proved some interesting results about the complexity of the Local Consistency problem (deciding whether local density matrices that describe small pieces of a quantum system are consistent with a single overall state). In particular, we showed that this problem is QMA-complete. We also showed that N-representability, an important problem in quantum chemistry, is QMA-complete.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Feb 04, 2008
Accession Number
ADA482339

Entities

People

  • Yi-Kai Liu

Organizations

  • University of California, San Diego

Tags

Communities of Interest

  • Energy and Power Technologies
  • Human Systems

DTIC Thesaurus Topics

  • Algorithms
  • Computational Complexity
  • Computer Science
  • Eigenvalues
  • Engineering
  • Equations
  • Fermions
  • Ground State
  • Probability
  • Probability Distributions
  • Quantum Algorithms
  • Quantum Chemistry
  • Quantum Computing
  • Quantum Information
  • Quantum States
  • Random Variables
  • Students

Readers

  • Operations Research
  • Quantum spin resonance or Electron Paramagnetic Resonance spectroscopy.

Technology Areas

  • Quantum Computing