Numerical Studies of the Quantum Adiabatic Algorithm

26th IUPAP Conference on Computational Physics

物理学;计算机科学

Young, A.P.^1 ; Hen, Itay^2

Department of Physics, University of California, Santa Cruz

CA

95064, United States^1

Information Sciences Institute, University of Southern California, Marina del Rey

CA

90292, United States^2

关键词: Finite temperatures;    Minimum energy;    Optimization problems;    Quantum adiabatic algorithm;    Quantum monte carlo;    Quantum phase transitions;    Size dependence;    Very low temperatures;   

Others  :  https://iopscience.iop.org/article/10.1088/1742-6596/640/1/012038/pdf
DOI  :  10.1088/1742-6596/640/1/012038

学科分类：计算机科学（综合）

来源: IOP

【 摘 要 】

Quantum annealers promise to solve practical optimization problems potentially faster than conventional classical computers. One of the major ongoing debates in this context pertains to their robustness against the decohering effects of finite temperature and interactions with the environment. We argue that even in an ideal setting of very low temperatures and in the absence of a decohering environment, quantum annealers do not necessarily perform better than classical heuristic solvers. Here, we numerically study the performance of the quantum adiabatic algorithm (QAA) on a variety of constraint satisfaction problems and a spin glass problem by studying the size dependence of the minimum energy gap during the evolution of the QAA. We do so by employing Quantum Monte Carlo schemes as these allow us to study these problems at much larger scales than exact methods would allow. We find that in all cases a quantum phase transition occurs and the minimum gap decreases exponentially with system size, leading to an exponentially large running time for the QAA. Based on these and other results, we briefly discuss potential modifications to the QAA that may improve the scaling of the minimum gap, leading to faster quantum adiabatic algorithms.