期刊
INTERNATIONAL JOURNAL OF QUANTUM INFORMATION
卷 4, 期 5, 页码 843-870出版社
WORLD SCIENTIFIC PUBL CO PTE LTD
DOI: 10.1142/S0219749906002213
关键词
quantum adiabatic search; quantum algorithms; computational complexity; noise; decoherence
Results are presented of a large-scale simulation of the quantum adiabatic search (QuAdS) algorithm in the presence of noise. The algorithm is 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 four 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 (T(N)). Clear evidence is found of the algorithm's sensitivity to noise. Two fits to the simulation results were done: (i) power-law scaling (T(N)) = aN(b); and (ii) exponential scaling (T(N)) = a[exp(bN) - 1]. Both types of scaling relations provided excellent fits, although the scaling parameters a and b varied with noise power, and with the type of noise polarization. The sensitivity of the scaling exponent b to noise polarization allows a relative assessment of which noise polarizations are most problematic for quantum adiabatic search. We demonstrate how the 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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据