#
Simulation of Quantum Adiabatic Search in the Presence of Noise

*
Frank Gaitan, of Physics, Southern Illinois University, Carbondale
*

Results are presented of a large-scale simulation of the quantum adiabatic search (QuAdS) algorithm in the presence of noise applied to the NP-Complete
problem N-Bit Exact Cover 3 (EC3). The noise is assumed to Zeeman-couple to the
qubits and its effects on the algorithm's performance is studied for various
levels of noise power and for 4 different types of noise polarization. We
examine the scaling relation between the number of bits N (EC3 problem-size) and
the algorithm's noise-averaged median run-time . Clear evidence is found
of the algorithm's sensitivity to noise. The sensitivity of the scaling exponent
to noise polarization allows a relative assessment of which noise polarization
is most problematic for QuAdS. We show how noise leads to decoherence in QuAdS
and estimate the amount of decoherence present in our simulations. An upper
bound is also derived for the noise-averaged QuAdS success probability in the
limit of weak noise that is appropriate for our simulations.