Statistical Analysis of Quantum Annealing
arXiv:2101.06854
Abstract
Quantum computers use quantum resources to carry out computational tasks and may outperform classical computers in solving certain computational problems. Special-purpose quantum computers such as quantum annealers employ quantum adiabatic theorem to solve combinatorial optimization problems. In this paper, we compare classical annealings such as simulated annealing and quantum annealings that are done by the D-Wave machines both theoretically and numerically. We show that if the classical and quantum annealing are characterized by equivalent Ising models, then solving an optimization problem, i.e., finding the minimal energy of each Ising model, by the two annealing procedures, are mathematically identical. For quantum annealing, we also derive the probability lower-bound on successfully solving an optimization problem by measuring the system at the end of the annealing procedure. Moreover, we present the Markov chain Monte Carlo (MCMC) method to realize quantum annealing by classical computers and investigate its statistical properties. In the numerical section, we discuss the discrepancies between the MCMC based annealing approaches and the quantum annealing approach in solving optimization problems.
Withdrawn by the authors because the authorship attribution in version 1 does not accurately reflect the final agreed contributions to the work. Accordingly, this version should not be relied upon as an accurate record of authorship
References in corpus (5)
- Mathematical Foundation of Quantum Annealing
- Reexamining classical and quantum models for the D-Wave One processor
- Bayesian Network Structure Learning Using Quantum Annealing
- A Quantum Annealing Approach for Fault Detection and Diagnosis of Graph-Based Systems
- Computational Role of Collective Tunneling in a Quantum Annealer