  What are the conditions for adiabatic quantum computation (AQC) to outperform
classical computation? Although there exist several quantum adiabatic
algorithms achieving the strong quantum speedup, the essential keys to their
speedups are still unclear. Here, we investigate the connection between
superpositions of macroscopically distinct states and known examples of the
speedup in AQC. To formalize this notion we consider an index $p$ that
quantifies a superposition of macroscopically distinct states from the
asymptotic behaviors of fluctuations of additive observables. We determine this
index for five examples of adiabatic algorithms exhibiting various degrees of
the speedup. The results suggest that the superposition of macroscopically
distinct states is an appropriate indicator of entanglement crucial to the
strong quantum speedup in AQC.

Quantum Physics;Statistical Mechanics