NASA Logo

NTRS

NTRS - NASA Technical Reports Server

Back to Results
Dynamics of Quantum Adiabatic Evolution Algorithm for Number PartitioningWe have developed a general technique to study the dynamics of the quantum adiabatic evolution algorithm applied to random combinatorial optimization problems in the asymptotic limit of large problem size n. We use as an example the NP-complete Number Partitioning problem and map the algorithm dynamics to that of an auxiliary quantum spin glass system with the slowly varying Hamiltonian. We use a Green function method to obtain the adiabatic eigenstates and the minimum excitation gap. g min, = O(n 2(exp -n/2), corresponding to the exponential complexity of the algorithm for Number Partitioning. The key element of the analysis is the conditional energy distribution computed for the set of all spin configurations generated from a given (ancestor) configuration by simultaneous flipping of a fixed number of spins. For the problem in question this distribution is shown to depend on the ancestor spin configuration only via a certain parameter related to 'the energy of the configuration. As the result, the algorithm dynamics can be described in terms of one-dimensional quantum diffusion in the energy space. This effect provides a general limitation of a quantum adiabatic computation in random optimization problems. Analytical results are in agreement with the numerical simulation of the algorithm.
Document ID
20030067983
Acquisition Source
Ames Research Center
Document Type
Preprint (Draft being sent to journal)
Authors
Smelyanskiy, V. N.
(NASA Ames Research Center Moffett Field, CA, United States)
Toussaint, U. V.
(Max-Planck-Inst. fuer Plasmaphysik Garching, Germany)
Timucin, D. A.
(NASA Ames Research Center Moffett Field, CA, United States)
Date Acquired
August 21, 2013
Publication Date
February 19, 2002
Subject Category
Mathematical And Computer Sciences (General)
Funding Number(s)
OTHER: 749-40-00
Distribution Limits
Public
Copyright
Public Use Permitted.
Document Inquiry

Available Downloads

There are no available downloads for this record.
No Preview Available