Joshua Ball with Harsh Mathur

The Efficiency of Adiabatic Quantum Computing

Adiabatic quantum computing is a newly proposed method developed to solve exact cover and other NP-complete problems. Classically, NP-complete problems can only be solved in exponential time. However, numerical simulations of the adiabatic quantum computer on a classical computer suggest that this method can solve exact cover in polynomial time. In this project we aim to improve the simulation of the adiabatic quantum computer in order to test the algorithm with larger input problems. We will also study exact cover or other NP-complete problems analytically and look for special cases where the method could fail to solve the problem in polynomial time.