Physics – Quantum Physics
Scientific paper
2002-02-26
Physics
Quantum Physics
32 pages, 5 figures, 3 Appendices; List of additions compare to v.3: (i) numerical solution of the stationary Schroedinger equ
Scientific paper
We 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 auxilary 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_{\rm min}={\cal O}(n 2^{-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 simulteneous fipping 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-dimenssional quantum diffusion in the energy space. This effect provides a general limitation on the power of a quantum adiabatic computation in random optimization problems. Analytical results are in agreement with the numerical simulation of the algorithm.
Smelyanskiy Vadim N.
Timucin Dogan A.
Toussaint Udo v.
No associations
LandOfFree
Dynamics of quantum adiabatic evolution algorithm for Number Partitioning does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Dynamics of quantum adiabatic evolution algorithm for Number Partitioning, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamics of quantum adiabatic evolution algorithm for Number Partitioning will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-668238