QuaCGR Fellowship: Adiabatic Quantum Algorithms; Final rept. 1 Aug 2004-31 Jan 2008

摘要

We studied the quantum adiabatic algorithm for combinatorial optimization. We obtained a simpler proof of the adiabatic theorem. However, we did not make much progress in developing new tools for rigorous analysis of the algorithm's performance on realistic optimization problems. This analysis seems to be substantially more difficult than for classical algorithms such as simulated annealing, because the ground state does not have a simple form. We also proved some interesting results about the complexity of the Local Consistency problem (deciding whether local density matrices that describe small pieces of a quantum system are consistent with a single overall state). In particular, we showed that this problem is QMA-complete. We also showed that N-representability, an important problem in quantum chemistry, is QMA-complete.