The main objective of the project is to study the fundamental limits and possible modifications of the Adiabatic Quantum Optimization approach to the NP-complete computational problems. PI plans to use the connection of the Adiabatic Quantum Optimization with the theory of Anderson Localization, more precisely its recent extension to the Many-Body problems of Condensed Matter Physics and Statistical Mechanics. By applying techniques used in the Quantum Physics of Complex Systems, PI plans to analyze in details the distribution of small spectral gaps and their effect on the efficiency of the Adiabatic Quantum algorithms for various problems. The connection with the localization implies that the loss of the adiabaticity due to the existence of the exponentially small gaps is likely and the difficulty is fundamental. However, a better understanding of the adiabatic evolution of the complex quantum models, which arise in connection with NP-complete problems, may help to design a modified quantum algorithm that has advantages over known classical algorithms. For example, PI will study possibilities to design quantum algorithms that have advantages over classical heuristics or approximation algorithms, where a local minimum with energy close enough to the global minimum is an acceptable solution. The research under this award is on the edge of Computer Science, Quantum Physics of Complex Systems and Mathematical Physics.
