Adiabatic Grover's Algorithm and Graph Theory

Adiabatic Grover's Algorithm generally assumes the problem Hamiltonian is diagonal in the computational basis. In this talk, we will show how to reinterpret Grover's search algorithm as a Graph Theory problem, and conversely, we will show how to build the problem Hamiltonian for various graph search problems directly from the Graph Laplacian. Finally, we analyze the performance of the adiabatic algorithms under various graph constraints and provide evidence to suggest that the performance improves with the number of edges. We rigorously prove that the graph search algorithm is exactly Grover's algorithm when the graph is complete.