Statistical Analysis of Quantum Annealing

一誠 佐藤

悟史 森田

Xinyu Song, Yazhen Wang, Shang Wu +1 more

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.

Yazhen Wang, Shang Wu, Jian Zou

Quantum computation performs calculations by using quantum devices instead of electronic devices following classical physics and used by classical computers. Although general purpose quantum computers of practical scale may be many years away, special purpose quantum computers are being built with capabilities exceeding classical computers. One prominent case is the so-called D-Wave quantum computer, which is a computing hardware device built to implement quantum annealing for solving combinatorial optimization problems. Whether D-Wave computing hardware devices display a quantum behavior or can be described by a classical model has attracted tremendous attention, and it remains controversial to determine whether quantum or classical effects play a crucial role in exhibiting the computational input–output behaviors of the D-Wave devices. This paper consists of two parts where the first part provides a review of quantum annealing and its implementations, and the second part proposes statistical methodologies to analyze data generated from annealing experiments. Specifically, we introduce quantum annealing to solve optimization problems and describe D-Wave computing devices to implement quantum annealing. We illustrate implementations of quantum annealing using Markov chain Monte Carlo (MCMC) simulations carried out by classical computers. Computing experiments have been conducted to generate data and compare quantum annealing with classical annealing. We propose statistical methodologies to analyze computing experimental data from a D-Wave device and simulated data from the MCMC based annealing methods, and establish asymptotic theory and check finite sample performances for the proposed statistical methodologies. Our findings confirm bimodal histogram patterns displayed in input–output data from the D-Wave device and both U-shape and unimodal histogram patterns exhibited in input–output data from the MCMC based annealing methods. Further statistical explorations reveal possible sources for the U-shape patterns. On the other hand, our statistical analysis produces statistical evidence to indicate that input–output data from the D-Wave device are not consistent with the stochastic behaviors of any MCMC based annealing models under the study. We present a list of statistical research topics for the future study on quantum annealing and MCMC simulations.

Wade DeGottardi, David Ferguson, С. А. Новиков +2 more

Alessandro Rizzo, Nicolò Parmiggiani, Andrea Bulgarelli +12 more

The detection and localization of gamma-ray sources via maximum-likelihood analysis is a complex parameter optimization problem. We address this challenge using quantum annealing, a computational approach that solves optimization tasks by encoding them into the ground state of an Ising Hamiltonian. Specifically, we apply this method to observations from AGILE's Gamma-Ray Imaging Detector (GRID) in the 30 MeV-50 GeV band. We reformulated the standard analysis as a Quadratic Unconstrained Binary Optimization (QUBO) problem. We tested this method on a set of AGILE observations generated with AGILEpy, solving the QUBO with simulated quantum annealing. The method reproduces the classical flux and position estimates within their statistical uncertainty and identifies the correct grid node among the candidate positions in 97% of the maps. These promising results demonstrate that quantum annealing could be used in this optimization problem, laying the ground for its deployment on actual quantum annealers.