Size dependence of the minimum excitation gap in the Quantum Adiabatic Algorithm

Preprint

27 March 2008

preprint
Published by arXiv in arXiv

Abstract

We study the minimum gap in the quantum version of the Exact Cover problem using Quantum Monte Carlo simulations, with a view to understanding the complexity of the quantum adiabatic algorithm for much large sizes than was possible before. For a range of sizes, N <= 128, where the classical Davis-Putnam algorithm shows exponential complexity, the quantum adiabatic algorithm shows polynomial complexity. The bottleneck of the algorithm is an isolated avoided crossing point of a Landau-Zener type (collision between the two lowest energy levels only).

Keywords

QUANTUM ADIABATIC ALGORITHM
MONTE CARLO SIMULATIONS
MINIMUM EXCITATION
EXCITATION GAP
ENERGY LEVELS
MINIMUM GAP

All Related Versions

Version 1, 2008-03-27, ArXiv
Version 2, 2008-10-23, ArXiv
Published version: Physical Review Letters, 101 (17), 170503.

This publication has 0 references indexed in Scilit: