NOISE AMPLIFICATION IN COMMERCIAL QUANTUM ANNEALERS

The state-of-the-art in commerical quantum computing technology is currently restricted to machines which perform quantum annealing. However, the time-complexityof quantum annealing, that is, how the required resources for running the algorithm scale with problem size, is currently unknown. Research groups at DWave, NASA and Google, among others, over the past decade, have dedicated considerable resources to computing this scaling behavior, which to this date remains an outstanding open problem at the intersection of theoretical physics and computer science. Although analyzing a noisy annealing process for a general high-dimensional spin glass is theoretically intractible, we can restrict our attention to the case of one dimensional graphs, where the annealing model becomes an integrable system, and consequently mathematical tools become powerful enough to analyze the asymptotic properties exactly. What we find is that, for one-dimensional graphs, the nature of spin glass bottlenecks is such that the noise of each individual qubit interferes constructively, causing an unintended linear scaling of noise strength with the number of qubits. Therefore, we theoretically predict, at least for generic one dimensional problems, complete thermalization of low energy states. As an illustrative example, in the simple case of one two-state bottleneck, we predict an asymptotic success rate of 50% for a commerical annealer achieving a global minimum, independent of qubit fidelity. Although the mathematics gives a detailed and rigorous prediction for the performance of annealing technology in the one-dimensional case, further research must be done on whether this constructive interference phenomenon persists in higher dimensions.