This article considers quantum annealing in the Ising framework for solving combinatorial optimization problems. The path-integral Monte Carlo simulation approach is often used to approximate quantum annealing and implement the approximation by classical computers, which refers to simulated quantum annealing (SQA). In this article, we introduce a data augmentation scheme into SQA and develop a new algorithm for its implementation. The proposed algorithm reveals new insights on the sampling behaviors in SQA. Theoretical analyses are established to justify the algorithm, and numerical studies are conducted to check its performance and to confirm the theoretical findings. Supplementary materials for this article are available online.
This article considers quantum annealing in the Ising framework for solving combinatorial optimization problems. The path-integral Monte Carlo simulation approach is often used to approximate quantum annealing and implement the approximation by classical computers, which refers to simulated quantum annealing (SQA). In this article, we introduce a data augmentation scheme into SQA and develop a new algorithm for its implementation. The proposed algorithm reveals new insights on the sampling behaviors in SQA. Theoretical analyses are established to justify the algorithm, and numerical studies are conducted to check its performance and to confirm the theoretical findings. Supplementary materials for this article are available online.
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.
Simulated quantum annealing (SQA) is a classical computational strategy that emulates a quantum annealing (QA) dynamics through a path-integral Monte Carlo whose parameters are changed during the simulation. Here we apply SQA to the one-dimensional transverse field Ising chain, where previous works have shown that, in the presence of disorder, a coherent QA provides a quadratic speedup with respect to classical simulated annealing, with a density of Kibble-Zurek defects decaying as ${\ensuremath{\rho}}_{\mathrm{KZ}}^{\mathrm{QA}}\ensuremath{\sim}{({log}_{10}\ensuremath{\tau})}^{\ensuremath{-}2}$ as opposed to ${\ensuremath{\rho}}_{\mathrm{KZ}}^{\mathrm{SA}}\ensuremath{\sim}{({log}_{10}\ensuremath{\tau})}^{\ensuremath{-}1}, \ensuremath{\tau}$ being the total annealing time, while for the ordered case both give the same power law ${\ensuremath{\rho}}_{\mathrm{KZ}}^{\mathrm{QA}}\ensuremath{\approx}{\ensuremath{\rho}}_{\mathrm{KZ}}^{\mathrm{SA}}\ensuremath{\sim}{\ensuremath{\tau}}^{\ensuremath{-}1/2}$. We show that the dynamics of SQA, while correctly capturing the Kibble-Zurek scaling ${\ensuremath{\tau}}^{\ensuremath{-}1/2}$ for the ordered case, is unable to reproduce the QA dynamics in the disordered case at intermediate $\ensuremath{\tau}$. We analyze and discuss several issues related to the choice of the Monte Carlo moves (local or global in space), the time-continuum limit needed to eliminate the Trotter-discretization error, and the long autocorrelation times shown by a local-in-space Monte Carlo dynamics for large disordered samples.
In recent years, the diversification of problems that require computers to solve has attracted attention to the construction of meta-heuristics that can be applied to a wide range of problems, and to specialized computers that implement these meta-heuristics in their devices. The representative meta-heuristics are Simulated Annealing (SA) and its extension to quantum computation, Quantum Annealing (QA), and its path-integral Monte Carlo method for classical simulation Crosson and Harrow showed that for certain problems where QA outperformed SA, SQA achieved performance close to that of QA, and SQA sometimes outperformed SA by an exponential time factor. On the other hand, it remains unclear whether SQA can work efficiently on a wide range of other problems. In this study, we experimentally compared SA and SQA on instances of the restricted Boltzmann machine RBM, known as a fundamental building block in deep learning, and 3SAT, a fundamental combinatorial optimization problem. The results show that SQA gives slightly better solutions than SA as the problem size increases for RBM in terms of both accuracy and computation time in our setting, but the opposite trend is observed for 3SAT, indicating that there is no significant difference between the two methods. From the viewpoint of artificial intelligence research, it is necessary to further examine whether deep learning can be made more efficient by applying QA and SQA to RBM.
The path integral Monte Carlo simulated quantum annealing algorithm is applied to the optimization of a large hard instance of the random satisfiability problem (N = 10,000). The dynamical behavior of the quantum and the classical annealing are compared, showing important qualitative differences in the way of exploring the complex energy landscape of the combinatorial optimization problem. At variance with the results obtained for the Ising spin glass and for the traveling salesman problem, in the present case the linear-schedule quantum annealing performance is definitely worse than classical annealing. Nevertheless, a quantum cooling protocol based on field-cycling and able to outperform standard classical simulated annealing over short time scales is introduced.
A numerical technique called Simulated Ising Annealing (SIA) uses digital computers to obtain approximations of the ground states of Ising models. The quadratic unconstrained binary optimization (QUBO) problem in combinatorial optimization, which is challenging to solve through exhaustive search, has significant linkages to the Ising model. Therefore, SIA's main objective is to identify a better solution in finite iterations. In order to enhance the performance of the simulated annealing procedure, we adopt a Gaussian augmented Hamiltonian Monte Carlo (GAHMC) method in this study. We contrasted our algorithm with Gibbs sampling and local quantum annealing method. Finally, we discuss its application on QUBO problem.
Simulated quantum annealing (SQA) is a probabilistic approximation method to find a solution for a combinatorial optimization problem using digital computers. The processing time of SQA increases exponentially with the number of variables. Therefore, acceleration of SQA is regarded as a very important topic. However, parallel implementation is difficult due to the serial nature of the quantum Monte Carlo algorithm used in SQA. In this paper, we propose a method to implement SQA in parallel on a GPU while preserving the data dependency. According to the experimental results, we have achieved over 97 times speed-up while maintaining the same accuracy-level compared to a single-core CPU implementation.