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.
arXiv commentWithdrawn 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 (20)
- Quantum Annealing in the Transverse Ising Model
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Adiabatic Quantum Computing
- Characterizing Quantum Supremacy in Near-Term Devices
- Engineered 2D Ising interactions on a trapped-ion quantum simulator with hundreds of spins
- Defining and detecting quantum speedup
- Mathematical Foundation of Quantum Annealing
- Computational Role of Multiqubit Tunneling in a Quantum Annealer
- A case study in programming a quantum annealer for hard operational planning problems
- Understanding Quantum Tunneling through Quantum Monte Carlo Simulations
- Experimental determination of Ramsey numbers
- Reexamining classical and quantum models for the D-Wave One processor
- Evidence for Non-Random Hydrophobicity Structures in Protein Chains
- Bayesian Network Structure Learning Using Quantum Annealing
- Quantum Adiabatic Evolution Algorithms versus Simulated Annealing
- A Quantum Annealing Approach for Fault Detection and Diagnosis of Graph-Based Systems
- Quantum Monte Carlo Simulations of Tunneling in Quantum Adiabatic Optimization
- Optimal large-scale quantum state tomography with Pauli measurements
- Computational Role of Collective Tunneling in a Quantum Annealer
- Asymptotic equivalence of quantum state tomography and noisy matrix completion