Are quantum computers powerful enough to solve efficiently hard
instances of random NP-complete problems? We analyze this question using as an example quantum adiabatic evolution algorithms for combinatorial search and optimization. We propose a theoretical framework which is based on the connection between the neighborhood properties in random optimization problems and
physical picture of a quantum diffusion in disorder medium.
Effective dimensionality of the diffusion process and the form of transition probabilities depend on a given NP-complete problem and determine the complexity of the quantum algorithm.
Copyright. All Rights Reserved.