Mind the gap. Solving optimization problems on a quantum computer
Peter Young (Physics Department, University of California, Santa Cruz)

It is known that an eventual quantum computer could solve certain specialized problems more efficiently than a classical computer running any known algorithm. The best-known example is Shor's algorithm for factoring large integers, which could be used to break the most popular method of encryption (known as RSA) for sending information on the internet. In this talk I will address the question of whether a quantum computer could, in addition, solve a broad range of optimization problems more efficiently than a classical computer. Motivated by an understanding of the adiabatic principle in quantum mechanics, Farhi et al (2001) proposed the "Quantum Adiabatic Algorithm" (QAA) as a way of solving optimization problems on a quantum computer. I will investigate the efficiency of the the QAA for several optimization problems as a function of the problem size. Since there is currently no quantum computer, in order to study large sizes, we have simulated the QAA on a classical computer using the Monte Carlo technique from statistical physics. A key quantity that we calculate is the evolution of the gap between the ground state and first excited state of a certain quantum Hamiltonian which changes during the running of the algorithm. The results of these studies will be described.