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.
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.
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.
Abstract Modest statistical differences between the sampling performances of the D-Wave quantum annealer (QA) and the classical Markov Chain Monte Carlo (MCMC), when applied to Restricted Boltzmann Machines (RBMs), are explored to explain, and possibly address, the absence of significant and consistent improvements in RBM trainability when the D-Wave sampling was used in previous investigations. A novel hybrid sampling approach, combining the classical and the QA contributions, is investigated as a promising way to benefit from the modest differences between the two sampling methods. No improvements in the RBM training are achieved in this work, thereby suggesting that the differences between the QA-based and MCMC sampling, mainly found in the medium-to-low probability regions of the distribution, which are less important for the quality of the sample, are insufficient to benefit the training. Difficulties in achieving sufficiently high quality of embedding RBMs into the lattice of the newer generation of D-Wave hardware could be further complicating the task. On the other hand, the ability to generate samples of sufficient variety from lower-probability parts of the distribution has a potential to benefit other machine learning applications, such as the mitigation of catastrophic forgetting (CF) during incremental learning. The feasibility of using QA-generated patterns of desirable classes for CF mitigation by the generative replay is demonstrated in this work for the first time. While the efficiency of the CF mitigation using the D-Wave QA was comparable to that of the classical mitigation, both the speed of generating a large number of distinct desirable patterns and the potential for further improvement make this approach promising for a variety of challenging machine learning applications.
Quantum computing has emerged as a promising computational paradigm with the potential to solve problems that are intractable for classical computers. This paper provides an overview of the current state of quantum computing, including its historical development, hardware advancements, applications, and challenges. Special attention is given to combinatorial optimization, which is considered one of the most promising application domains. The limitations of current quantum systems and future research directions are also discussed. This paper presents a comparative study between a conventional D-Wave-based simulated annealing approach and a proposed hybrid optimization model for solving largescale combinatorial optimization problems. The study focuses on benchmark problems, including AES, TSP gr24, and a real-world load balancing problem, all formulated as QUBO models. The D-Wave approach employs the dwave-neal simulated annealing engine with various parameter settings, while the proposed model introduces a decomposition-based framework combined with adaptive parameter control and iterative refinement. The experimental results demonstrate that the proposed model consistently outperforms the conventional approach in terms of solution quality, achieving significantly lower energy values across all problem instances. In particular, for the TSP gr24 problem, the proposed model achieves near-optimal solutions with substantially reduced computation time. For large-scale problems such as AES and load balancing, the proposed model maintains scalability and robustness, whereas the conventional approach suffers from increased computational cost and performance degradation. Although the proposed method introduces additional computational steps, its hybrid structure effectively mitigates limitations related to local minima, parameter sensitivity, and scalability. These findings indicate that integrating classical optimization techniques with quantum-inspired methods is essential for practical applications. The proposed model provides a promising framework for solving complex real-world optimization problems and highlights the importance of hybrid approaches in advancing quantum annealing technologies.
It is well-known that quantum annealing (QA) is an excellent algorithm for solving combinatorial optimization problems (COPs). However, its hardware implementation poses challenges, requiring quantum devices. Therefore, a quantum Monte Carlo (QMC) method-based annealing approach called Simulated Quantum Annealing (SQA), which aims to emulate quantum annealing using classical computers, has been proposed. In the demo-night session, we will demonstrate a SQA based on stochastic computing (SC) on a standard FPGA board, called “PYNQ”. The use of SC-based data representation, along with the realization of SC-based spin-gate circuits, makes it possible to drastically reduce hardware costs compared to QA. This enhances the suitability for extending large-scale COPs.
We develop a quantum algorithm to solve combinatorial optimization problems through quantum simulation of a classical annealing process. Our algorithm combines techniques from quantum walks, quantum phase estimation, and quantum Zeno effect. It can be viewed as a quantum analogue of the discrete-time Markov chain Monte Carlo implementation of classical simulated annealing. Our implementation scales with the inverse of the square root of the minimum spectral gap of the stochastic matrix used in the classical simulation. The quantum algorithm outperforms the classical one, which scales with the inverse of the gap.
Quantum annealing is a promising tool for solving optimization problems, similar in some ways to the traditional (classical) simulated annealing of Kirkpatrick et al. Simulated annealing takes advantage of thermal fluctuations in order to explore the optimization landscape of the problem at hand, whereas quantum annealing employs quantum fluctuations. Intriguingly, quantum annealing has been proved to be more effective than its classical counterpart in many applications. We illustrate the theory and the practical implementation of both classical and quantum annealing – highlighting the crucial differences between these two methods – by means of results recently obtained in experiments, in simple toy-models, and more challenging combinatorial optimization problems (namely, Random Ising model and Travelling Salesman Problem). The techniques used to implement quantum and classical annealing are either deterministic evolutions, for the simplest models, or Monte Carlo approaches, for harder optimization tasks. We discuss the pro and cons of these approaches and their possible connections to the landscape of the problem addressed.