Correction to "The quantum adiabatic optimization algorithm and local minima"
The Adiabatic Theorem given in the paper is incorrect; see [ASY93]. A corrected version has been given in
[JRS06]. Written in my notation, [JRS06, Theorem 3] gives an error bound of O( h^2/(tau gamma^3) ), and
their Theorem 4 has an error bound of O( (h^2/(tau gamma^3))^2 ).
For k'th-order analysis, Theorem 2 of [JRS06] gives a bound of O(1/tau^{k-1}), with the dependence on the
Hamiltonian hidden. Putting that dependence back, using Lemma 4, gives O( (h^2/(tau gamma^3))^{k-1} ).
However this calculation is not made in [JRS06].
Note that the [ASY87] proof technique only gives 1/gamma^3 dependence, similar to the theorem in [AR04],
even at higher orders. Each induction step does give an additional integral, however. [LRH08] recover
this behavior, and also show that the error can be made to drop exponentially fast beyond a threshold
evolution time.
[ASY87] J. E. Avron, R. Seiler, and L. G. Yaffe. Adiabatic theorems and applications to the quantum Hall
effect. Communications in Mathematical Physics 110 (1987), pp. 33-49.
[ASY93] J. E. Avron, R. Seiler, and L. G. Yaffe. Erratum: ``Adiabatic theorems and applications to the
quantum Hall effect.'' Communications in Mathematical Physics 156 (1993), pp. 649-650.
[AR04] A. Ambainis, O. Regev. An Elementary Proof of the Quantum Adiabatic Theorem, quant-ph/0411152.
[JRS06] S. Jansen, M. Ruskai, and R. Seiler. Bounds for the adiabatic approximation with applications to
quantum computation, J. Math. Phys. 48, 102111 (2007), quant-ph/0603175.
[LRH08] D. Lidar, A. Rezakhani, and A. Hamma. Adiabatic approximation with exponential accuracy for
many-body systems and quantum computation, arXiv:0808.2697, 2008.