Nonlinear Theory and Its Applications IEICE

Swarm-like ground-state searching based on a path-integral quantum Monte Carlo method for automatically fluctuation-controlled simulated annealing

Akio Yoshizawa

Published Jan 1, 2023• 0 citations

Abstract

The path-integral quantum Monte Carlo (PIQMC) method is widely used as a classical simulation algorithm for quantum annealing. Replicas represent different points in imaginary time. We propose and demonstrate a swarm-like ground-state searching algorithm based on the PIQMC method for automatically fluctuation-controlled simulated annealing. Replicas help one another to search for the ground state of an Ising system as if forming a swarm and working cooperatively. Their interactions are local, simple and fluctuate to a certain degree. Such fluctuations are necessary to escape local minima, but the fluctuations do not need to be explicitly controlled. The size of fluctuations is automatically adjusted as annealing proceeds. We solve max-cut problems for algorithm evaluation, each of which corresponds to a graph of 100 vertices. We also solve the same problems using a conventional method based on the Metropolis algorithm for comparison.

DOI: 10.1587/nolta.14.152

Related papers

An Ising Computer Based on Simulated Quantum Annealing by Path Integral Monte Carlo Method

Takuya Okuyama, Masato Hayashi, Masanao Yamaoka

In the near future, one of the main processes is solving large combinatorial optimization problems. However, the performance growth of von Neumann architecture will slow due to the end of semiconductor scaling. To resolve this problem, we propose an Ising computer that maps the optimization problems to the ground state search of Ising models. We previously proposed a computer that finds the ground state of Ising models by simulated annealing (SA) approximately. Though the solution quality of the previous prototype is comparable to that of SA, enhancing the solution quality will be required to solve real-world applications. In this paper, we present our FPGA-based Ising computer that executes simulated quantum annealing by using a path integral quantum Monte Carlo method for Ising models on a 48-by-48 king graph with 8-bit couplings. We also propose a shared random number supply, which contributes to decrease the number of random number generators to two. Experimental results indicate that the proposed Ising computer is more than 15 times faster to obtain 99.9%-solution with a probability of 99% than SA running on a state-of-the-art CPU.

IEEE International Conference on Rebooting Computing (ICRC)Nov 1, 201747 citations

Study of Optimization Problems by Quantum Annealing

Tadashi Kadowaki

We introduce quantum fluctuations into the simulated annealing process of optimization problems, aiming at faster convergence to the optimal state. The idea is tested by the two models, the transverse Ising model and the traveling salesman problem (TSP). Adding the transverse field to the Ising model is a simple way to introduce quantum fluctuations. The strength of the transverse field is controlled as a function of time similarly to the temperature in the conventional method. TSP can be described by the Ising spin, so that we also apply the same technique to TSP. We directory solve the time-dependent Schrödinger equation for small-size systems and perform the quantum Monte Carlo simulation for large-size systems. Comparison with the results of the corresponding classical (thermal) method reveals that the quantum method leads to the ground state with much larger probability in almost all cases if we use the same annealing schedule of the control parameters. We also find that the relaxation time is quite short for quantum systems by numerical simulations. We consider this is one of the reasons why the annealing in quantum systems have a better performance of finding the optimal state in comparison with classical systems.

arXiv:quant-ph/0205020May 5, 200239 citations

Simulating quantum annealing via projective quantum Monte Carlo algorithms

Estelle M. Inack

In this thesis, we implement projective quantum Monte Carlo (PQMC) methods to simulate quantum annealing on classical computers. A detailed derivation of the algorithm is presented. We show that in the regime where the systematic errors are well controlled, PQMC algorithms are indeed capable of simulating the imaginary-time dynamics of the Schroedinger equation both on continuous space models and discrete basis systems. We also demonstrate that the tunneling time of the PQMC method is quadratically faster than the one of incoherent quantum tunneling. It also shows remarkable stability when applied to frustrated systems compared to the path integral Monte Carlo algorithm, the algorithm mostly chosen to do comparisons with quantum annealers. However, a major drawback of the method comes from the finite number of random walkers needed to implement the simulations. It grows exponentially with the system size when no or poor guiding wave-functions are utilized. Nevertheless, we demonstrated that when good enough guiding wave-functions are used -- in our case we choose artificial neural networks -- the computational complexity seems to go from exponential to polynomial in the system size. We advocate for a search of more efficient guiding wave functions since they determine when and how feasible the PQMC simulations are on classical computers, a question closely related to a provable need or speed-up of a quantum computer.

Oct 26, 20180 citations

Enhancing the efficiency of quantum annealing via reinforcement: A path-integral Monte Carlo simulation of the quantum reinforcement algorithm

Abolfazl Ramezanpour

The standard quantum annealing algorithm tries to approach the ground state of a classical system by slowly decreasing the hopping rates of a quantum random walk in the configuration space of the problem, where the on-site energies are provided by the classical energy function. In a quantum reinforcement algorithm, the annealing works instead by increasing gradually the strength of the on-site energies according to the probability of finding the walker on each site of the configuration space. Here, by using the path-integral Monte Carlo simulations of the quantum algorithms, we show that annealing via reinforcement can significantly enhance the success probability of the quantum walker. More precisely, we implement a local version of the quantum reinforcement algorithm, where the system wave function is replaced by an approximate wave function using the local expectation values of the system. We use this algorithm to find solutions to a prototypical constraint satisfaction problem (XORSAT) close to the satisfiability to unsatisfiability phase transition. The study is limited to small problem sizes (a few hundreds of variables), nevertheless, the numerical results suggest that quantum reinforcement may provide a useful strategy to deal with other computationally hard problems and larger problem sizes even as a classical optimization algorithm.

arXiv:1812.02569Physical Review ADec 6, 20188 citations

Simulated Ising Annealing Algorithm with Gaussian Augmented Hamiltonian Monte Carlo

Langyu Li, Hao Wang, Zhixin Xie +3 more

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.

Chinese Control Conference (CCC)Jul 24, 20232 citations

量子アニーリングによる最適化問題の研究

門脇正史

We introduce quantum fluctuations into the simulated annealing process of optimization problems, aiming at faster convergence to the optimal state.Quantum fluctuations cause transitions between states and thus play the same role as thermal fluctuations in the conventional approach.The idea is tested by the two models, the transverse Ising model and the traveling salesman problem.Adding the transverse field to the Ising model is a simple way to introduce quantum fluctuations.The strength of the transverse field is controlled as a function of time similarly to the temperature in the conventional method.The goal is to find the ground state of the diagonal part of the Hamiltonian with high accuracy as quickly as possible.We also consider the traveling salesman problem.This model can be described by the Ising spin, so that we also apply the same technique to the transverse Ising model.We solve the time-dependent Schrödinger equation numerically for small size systems with various types of exchange interactions of the Ising model.Comparison with the results of the corresponding classical (thermal) method reveals that the quantum method leads to the ground state with much larger probability in almost all cases if we use the same annealing schedule of the control parameters.We check the case of large-size systems by using the quantum Monte Carlo method.The simulation supports the results of the small-size systems, while the dynamics of the Schrödinger equation and the quantum Monte Carlo method are not the same.We find that the simulated annealing by quantum fluctuations has a better performance than the conventional method for the ground state search of the Ising-spin systems.The calculation of the traveling salesman problem is also performed as A.3 Case of Γ(t) = c/ √ t . . . . . . . . . . . . . . . . . . . . . . . .

Mar 1, 19990 citations