Accelerated optimization using Bose-Einstein condensates

Accelerated optimization using Bose-Einstein condensates

Recently, physicists have been able to achieve Bose-Einstein condensates (BECs) using exciton-polaritons in semiconductor microcavities [1,2].  Exciton-polaritons are a type of bosonic quasiparticle, and can be described as a superposition of a photon and an exciton (a bound electron-hole pair).  Up until now, it is fair to say that the interest in BECs have been mainly academic.  With the advent of quantum computing however, people are now thinking more in terms of applications of these strange quantum effects.  Quantum simulation is a one promising application of such BECs, and is thought to be able to simulate complex quantum many body problems.

 
Figure 1: The real space image of a Bose-Einstein condensate of exciton-polaritons formed in a semiconductor.

This work focuses on a related but slightly different problem: optimization problems. Many of the computationally difficult problems, including NP-complete problems, can be thought of as an optimization problem in terms of some cost function.  If we regard the cost function to be a Hamiltonian, where the task is to minimize the energy, then this amounts to finding the ground state energy.  Now compare this to BECs, which of course have a macroscopic number of particles occupying the ground state.  Then if we could somehow harness this property and translate it to the optimization problem, then we should be able to find the solution of the optimization problem.

Not only does such a device find the ground state with high probability, we can also expect that there is a speedup in finding the solution of the problem.  The physical mechanism lies in the property of final state stimulation.  To understand this, consider two energy levels, which are occupied by a number of identical bosons.  Now consider a transition of a single boson between such levels.  In final state stimulation, when N bosons occupy the destination state, the transition probability is enhanced by a factor of N+1, due to the bosonic statistics.  This property is one of the effects than is experimentally used when forming BECs in both atomic and exciton-polaritons, in order to rapidly cool the condensate.

The kind of device we imagine is a series of traps, each containing a BEC (see figure 2).

Each boson can exist in two different states, which can be for example the spin of the exciton-polaritons.  We can control how many of the bosons exist in each of the two states, by controlling the energy difference locally on each site. By linking each of these sites via a feedback control loop, it is possible to make the sites interact with each other.  If the feedback parameters are controlled suitably, it becomes possible to simulate particular types of Hamiltonians that can encode a large class of optimization problems.

Figure 2: a) A set of traps with bosons occupying two states (shown as the colours) encodes a particular configuration of an optimization problem.  b) Schematic of the feedback circuitry used to induce the Hamiltonian.

In general it is not a trivial problem to see that the final state stimulation speedups that are present in each site of Figure 2 are carried over to the whole device.  To answer this, Kinetic Monte Carlo simulations were carried out to compare the speed of equilibration of the original system with only one particle in each site to the many boson system.  Even in the presence of local minima in the problem, we demonstrated that the N-fold speedup still exists in the system (see Ref. [1] for more details).  Considering that there can be of the order of 105 bosons in a typical BEC consisting of exciton-polaritons, and their equilibration time is generally extremely fast (of the order of picoseconds), this amounts to possibilities of speedups that are beyond currently available computers.

The above work was featured on the front page of the March 2011 issue of Nikkei Science, the Japanese version of Scientific American.

If you are interested in more details about this work, have a read of the Nikkei Science article (in Japanese) or Ref. [3] below.

References
[1] Kasprzak, J. et al. Bose–Einstein condensation of exciton polaritons.  Nature 443, 409 (2006).
[2] Deng, H. et al. Condensation of Semiconductor Microcavity Exciton Polaritons. Science 298,199 (2002)
[3] Tim Byrnes, Kai Yan, Yoshihisa Yamamoto, New. J. Phys. 13, 113025 (2011)
[4] Tim Byrnes and Yoshihisa Yamamoto, Nikkei Science March 2011 issue, 35-41.