On Adiabatic Quantum Unordered Search
M. V. Panduranga Rao
IISc-CSA-TR-2005-17
(November 2005) Available formats: [ps] [ps.gz]
Filed on November 27, 2005
Updated on June 27, 2006
Robustness of adiabatic quantum computing against various decoherence
effects and implementational errors has been investigated in the past.
In this paper
we investigate the resilience of adiabatic unordered search of van Dam et al.˜\cite{DamVazirani}
and Roland and Cerf˜\cite{SearchLocalAdiabatic} when the non-zero entries of the diagonal final Hamiltonian are perturbed by a polynomial (in $\log N$, where $N$ is the length of the unordered list) amount. We show that
the gap between the
lowest and second lowest eigenvalues remains non-zero during
the entire course of adiabatic evolution, implying arbitrarily high success
probability for high delay schedules. We also obtain an upper bound on the
running time in terms of the minimum gap between the above eigenvalues for
local adiabatic evolution.
Please bookmark this technical report as http://aditya.csa.iisc.ernet.in/TR/2005/17/.Problems ? Contact techrep@csa.iisc.ernet.in
[Updated at 2009-10-22T06:42Z]