Adiabatic Quantum Computing and Quantum Walks: Algorithms and Architectures
Edward Farhi · 2011
Abstract : During the period of this grant, there were a many significant results on quantum adiabatic algorithms and quantum walks. On the adiabatic front, there were papers showing how to design error correcting codes specifically for these Hamiltonian based algorithms. There was also a paper showing in detail how poor choices in the design of the Hamiltonian controlling the adiabatic evolution could lead to algorithmic failure, but that these choices could be avoided. In general there was excellent progress in our understanding of the capabilities of the adiabatic algorithm. On the quantum walk front there was a breakthrough result demonstrating a quantum algorithm which can evaluate a NAND tree with fewer queries than the best possible classical algorithm. This result sparked a series of papers by other authors on this subject. In addition, during the course of the grant period, experimental evidence made it clear that quantum walks play an important role in biological systems, notably in photosynthesis.