| |
Online ISSN:1349-8606 |
| Progress in Informatics |
|
| No.8 March 2011 |
|
| Page 39-47 |
PDF(6,765KB) | References |
| doi:10.2201/NiiPi.2011.8.5 |
| Kinetic Monte Carlo study of accelerated optimization problem search using Bose-Einstein condensates |
| Kai YAN1, Tim BYRNES2 and Yoshihisa YAMAMOTO3 |
1,2,3National Institute of Informatics
2Institute of Industrial Science, University of Tokyo
3E.L. Ginzton Laboratory, Stanford University |
(Received: October 31,2010)
(Revised: December 27,2010)
(Accepted: January 5,2011) |
Abstract:
In a previous work [ArXiv:0909.2530] we proposed a method for accelerating optimization problem search using Bose-Einstein condensation (BEC). The system encodes an optimization problem into an Ising model and cools it down by the process of BEC to find its ground state spin configuration which corresponds to the solution of the problem. The system uses the final state stimulation (FSS) property of bosonic particles, an effect originating from the quantum indistinguishability of bosons, to provide speedups over the classical case. The speedup is typically ∝ N, where N is the number of bosons in the system per site. In this article we firstly review the proposed system, and give a more detailed numerical study of the equilibration time with the boson number and the number of sites M in the Ising model. We find that the equilibration time scales as τ ∼ exp(M)/N in agreement with previous arguments based on simulated annealing. A detailed description of the kinetic Monte Carlo method used for the study of the proposed system is also discussed.
|
Keywords:
Bose-Einstein condensation, optimization, kinetic Monte Carlo, quantum computing
|
|
|
| PDF(6,765KB) | References |
National Institute of Informatics is a member of CrossRef.
|
