Access by Xinjiang University

Combinatorial optimization using dynamical phase transitions in driven-dissipative systems

Timothée Leleu^1,*, Yoshihisa Yamamoto^2,3, Shoko Utsunomiya⁴, and Kazuyuki Aihara¹

¹Institute of Industrial Science, The University of Tokyo, 4-6-1 Komaba, Meguro-ku, Tokyo 153-8505, Japan
²ImPACT program, The Japan Science and Technology Agency, Gobancho 7, Chiyoda-ku, Tokyo 102-0076, Japan
³E. L. Ginzton Laboratory, Stanford University, Stanford, California 94305, USA
⁴National Institute of Informatics, 2-1-2 Hitotsubashi, Chiyoda, Tokyo 101-0003, Japan

^*timothee@sat.t.u-tokyo.ac.jp

Phys. Rev. E 95, 022118 – Published 14 February, 2017

DOI: https://doi.org/10.1103/PhysRevE.95.022118

Abstract

The dynamics of driven-dissipative systems is shown to be well-fitted for achieving efficient combinatorial optimization. The proposed method can be applied to solve any combinatorial optimization problem that is equivalent to minimizing an Ising Hamiltonian. Moreover, the dynamics considered can be implemented using various physical systems as it is based on generic dynamics—the normal form of the supercritical pitchfork bifurcation. The computational principle of the proposed method relies on an hybrid analog-digital representation of the binary Ising spins by considering the gradient descent of a Lyapunov function that is the sum of an analog Ising Hamiltonian and archetypal single or double-well potentials. By gradually changing the shape of the latter potentials from a single to double well shape, it can be shown that the first nonzero steady states to become stable are associated with global minima of the Ising Hamiltonian, under the approximation that all analog spins have the same amplitude. In the more general case, the heterogeneity in amplitude between analog spins induces the stabilization of local minima, which reduces the quality of solutions to combinatorial optimization problems. However, we show that the heterogeneity in amplitude can be reduced by setting the parameters of the driving signal near a regime, called the dynamic phase transition, where the analog spins' DC components map more accurately the global minima of the Ising Hamiltonian which, in turn, increases the quality of solutions found. Last, we discuss the possibility of a physical implementation of the proposed method using networks of degenerate optical parametric oscillators.

Physics Subject Headings (PhySH)

Article Text

References (73)

A. Lucas, Frontiers Phys. 2, 5 (2014).
N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, and E. Teller, J. Chem. Phys. 21, 1087 (1953).
R. J. Glauber, J. Math. Phys. 4, 294 (1963).
S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi et al., Science 220, 671 (1983).
E. Marinari and G. Parisi, Europhys. Lett. 19, 451 (1992).
K. Hukushima and K. Nemoto, J. Phys. Soc. Jpn. 65, 1604 (1996).
Note that various combinations of the simulated annealing and replica exchange methods have also been proposed such as population annealing that uses both annealing and replicas of the system [62, 63].
L. Chen and K. Aihara, Neural Networks 8, 915 (1995).
C.-s. Zhou and T.-l. Chen, Phys. Rev. E 55, 2580 (1997).
T. Kadowaki and H. Nishimori, Phys. Rev. E 58, 5355 (1998).
G. Zarand, F. Pazmandi, K. F. Pal, and G. T. Zimanyi, Phys. Rev. Lett. 89, 150201 (2002).
F. Belletti, M. Cotallo, A. Cruz, L. A. Fernandez, A. Gordillo, A. Maiorano, F. Mantovani, E. Marinari, V. Martin-Mayor, A. Muñoz-Sudupe et al., Comput. Phys. Commun. 178, 208 (2008).
M. Yamaoka, C. Yoshimura, M. Hayashi, T. Okuyama, H. Aoki, and H. Mizuno, in Solid- State Circuits Conference (ISSCC), 2015 IEEE International (IEEE, NYC, 2015), pp. 1–3.
K. Aihara, Proc. IEEE 90, 919 (2002).
Y. Horio and K. Aihara, Physica D: Nonlin. Phenom. 237, 1215 (2008).
H. G. Katzgraber, F. Hamze, and R. S. Andrist, Phys. Rev. X 4, 021008 (2014).
X. Ke, J. Li, C. Nisoli, P. E. Lammert, W. McConville, R. F. Wang, V. H. Crespi, and P. Schiffer, Phys. Rev. Lett. 101, 037205 (2008).
S. Utsunomiya, K. Takata, and Y. Yamamoto, Opt. Express 19, 18091 (2011).
Z. Wang, A. Marandi, K. Wen, R. L. Byer, and Y. Yamamoto, Phys. Rev. A 88, 063853 (2013).
A. Marandi, Z. Wang, K. Takata, R. L. Byer, and Y. Yamamoto, Nature Photon. 8, 937 (2014).
J. A. Hertz and R. A. Klemm, Phys. Rev. B 20, 316 (1979).
T. R. Kirkpatrick and D. Thirumalai, Phys. Rev. B 36, 5388 (1987).
F. C. Hoppensteadt and E. M. Izhikevich, Weakly Connected Neural Networks (Springer-Verlag New York, Inc., Secaucus, NJ, 1997).
T. Inagaki, K. Inaba, R. Hamerly, K. Inoue, Y. Yamamoto, and H. Takesue, Nature Photon. 10, 415 (2016).
T. Inagaki, Y. Haribara, K. Igarashi, T. Sonobe, S. Tamate, T. Honjo, A. Marandi, P. L. McMahon, T. Umeki, K. Enbutsu, O. Tadanaga, H. Takenouchi, K. Aihara, K.-i. Kawarabayashi, K. Inoue, S. Utsunomiya, and H. Takesue, Science 354, 603 (2016).
P. L. McMahon, A. Marandi, Y. Haribara, R. Hamerly, C. Langrock, S. Tamate, T. Inagaki, H. Takesue, S. Utsunomiya, K. Aihara, R. L. Byer, M. M. Fejer, H. Mabuchi, and Y. Yamamoto, Science 354, 614 (2016).
Z. Wang, Coherent Computation in Degenerate Optical Parametric Oscillators, Ph.D. thesis, Stanford University, 2015.
S. W. Sides, P. A. Rikvold, and M. A. Novotny, Phys. Rev. Lett. 81, 834 (1998).
G. Korniss, C. J. White, P. A. Rikvold, and M. A. Novotny, Phys. Rev. E 63, 016120 (2000).
H. Fujisaka, H. Tutu, and P. A. Rikvold, Phys. Rev. E 63, 036109 (2001).
L. M. Sieberer, S. D. Huber, E. Altman, and S. Diehl, Phys. Rev. Lett. 110, 195301 (2013).
S. F. Edwards and P. W. Anderson, J. Phys. F 5, 965 (1975).
This choice is motivated by the fact that there is an important theoretical overlap between spin-glass theory and combinatorial optimization [64, 65, 66] linking the glassy behavior of spin glasses to computational complexity [65]. Moreover, the solutions of spin-glass problems are known in some particular cases such as the Sherrington-Kirkpatrick model using the Replica method [67, 68] and the cavity approach [69, 70] or spin glass on a Bethe lattice [71, 72], and allow for a better understanding of the glassy state.
In the case of the three-dimensional EA model, it is known that a continuous phase transition [46, 73] to a glassy phase occurs at $T_{c} = 1.1019 (29)$ [46] in the absence of an external field. The dynamic phase transition described in this paper should not be confused with the aforementioned continuous phase transition.
P. Drummond, K. McNeil, and D. Walls, J. Mod. Opt. 27, 321 (1980).
K. Takata, A. Marandi, and Y. Yamamoto, Phys. Rev. A 92, 043821 (2015).
In particular, the dynamical system described in Eq. (1) models the dynamics of degenerate optical parametric oscillator networks. Indeed, an equivalent system to $N$ Ising spins can be constructed by $N$ pulses of light, or DOPO, that propagate along an optical ring cavity with a second-order nonlinear crystal [19]. Using truncated Wigner representation of the field-density operator and the $c$ -number stochastic differential equations (CSDE) derived by the Ito rule, each pulse can be described by a single $c$ -number excitation amplitude. This approach is almost equivalent to a more rigorous method based on the positive $P$ -representation (or off-diagonal coherent state expansion) [35]. If we neglect the imaginary part of the complex amplitude that converges to zero due to phase-sensitive deamplification, the real part of the complex excitation amplitude, also called in-phase amplitude and noted by $x_{j}$ , obeys Eq. (1) with $α = - 1 + p$ , where $p$ is the normalized pump rate. In this case, time $t$ and amplitudes $x_{i}$ are normalized using the photon field lifetime $\frac{2}{γ_{s}}$ and the saturation amplitude $A_{s} = \sqrt{\frac{γ_{s} γ_{p}}{2 κ^{2}}}$ , respectively, where $γ_{s}$ and $γ_{p}$ are the signal and pump photon decay rates, respectively, and $κ$ is the parametric gain due to the second-order susceptibility of the nonlinear crystal. The computational principle of such a coherent Ising machine relies on mapping of the overall photon decay rate in a network of mutually coupled DOPO to the Ising Hamiltonian [19].
Note that the parameter $1 + α$ and the function $N + 2 ε H$ have be interpreted as the gain and loss function of the DOPOs network in Ref. [19]. The computational principle of the coherent Ising machine can thus be understood as setting the DOPO networks at proximity of a phase transition for which the gain is equal to the minimal value of the total loss.
Y. Haribara, Y. Yamamoto, K.-i. Kawarabayashi, and S. Utsunomiya, in Encyclopedia of Spectroscopy and Spectrometry III, edited by J. C. Lindon (Elvesier, Amsterdam, Netherlands, 2016).
We have added the dependence of the frequency on $α$ at which the dynamic phase transition occurs. When $α = - 1$ , the critical frequency is the one given in Ref. [30] .
Note that the shifting of phase occurs at every period so that the carrier signal of the digital modulation has a central peak in its spectrum at the frequency $f^{*}$ .
Y. A. Kuznetsov, Elements of Applied Bifurcation Theory, Vol. 112 (Springer Science & Business Media, Berlin, 2013).
The condition for the dynamic phase transition given in Eq. (27) implicitly assumes that the largest eigenvalue ${\tilde{λ}}_{1}$ of the Jacobian matrix $\tilde{J}$ is a continuous function of the parameters $p, ε, f^{*}$ , and $h$ . However, because $\tilde{α}$ is the solution of a nonlinear equation [see Eq. (28)], the eigenvalue ${\tilde{λ}}_{1}$ may change discontinuously. This is a consequence of the fact that the system can be described by differential algebraic equations [see Eqs. (21) and (22)]. The case of a discontinuous change in ${\tilde{λ}}_{1}$ is not considered in this paper and will be the subject of future investigations.
In Fig. 4, the Ising Hamiltonian is calculated using the instantaneous values of the spins $σ_{j} (t)$ rather than ${\tilde{σ}}_{j}$ .
Note that $α_{c}$ is determined using Eq. (31) in the driven case.
M. Baity-Jesi, R. A. Baños, A. Cruz, L. A. Fernandez, J. M. Gil-Narvion, A. Gordillo-Guerrero, D. Iñiguez, A. Maiorano, F. Mantovani, E. Marinari, V. Martin-Mayor, J. Monforte-Garcia, A. M. Sudupe, D. Navarro, G. Parisi, S. Perez-Gaviro, M. Pivanti, F. Ricci-Tersenghi, J. J. Ruiz-Lorenzo, S. F. Schifano, B. Seoane, A. Tarancon, R. Tripiccione, and D. Yllanes (Janus Collaboration), Phys. Rev. B 88, 224416 (2013).
M. Hasenbusch, A. Pelissetto, and E. Vicari, Phys. Rev. B 78, 214205 (2008).
H. G. Katzgraber, M. Körner, and A. P. Young, Phys. Rev. B 73, 224432 (2006).
K. F. Pál, Physica A: Stat. Mech. Appl. 223, 283 (1996).
K. F. Pál, Physica A: Stat. Mech. Appl. 233, 60 (1996).
M. Palassini and A. P. Young, Phys. Rev. Lett. 83, 5126 (1999).
F. Romá, S. Risau-Gusman, A. J. Ramirez-Pastor, F. Nieto, and E. E. Vogel, Physica A: Stat. Mech. Appl. 388, 2821 (2009).
We use a very slow decrease of the temperature of the simulated annealing, which requires time-consuming computation while increasing the probability of finding the ground states.
C. De Simone, M. Diehl, M. Jünger, P. Mutzel, G. Reinelt, and G. Rinaldi, J. Stat. Phys. 80, 487 (1995).
For $N = 343$ , the time to generate the correlated driving signal using the method described in Appendix pp3 on a 2.99 $G h z$ Intel Core is 0.2472 $s$ in average, which is much smaller than the time $t_{0}$ to find the ground state in the case of an implementation of the proposed method using DOPOs.
K. Takata, A. Marandi, R. Hamerly, Y. Haribara, D. Maruo, S. Tamate, H. Sakaguchi, S. Utsunomiya, and Y. Yamamoto, Sci. Rep. 6, 34089 (2016).
J. J. Hopfield and D. W. Tank, Biol. Cybern. 52, 141 (1985).
T. Rizzo and A. Crisanti, Phys. Rev. Lett. 90, 137201 (2003).
H. G. Katzgraber and F. Krzakala, Phys. Rev. Lett. 98, 017201 (2007).
M. J. Alava, V. Basso, F. Colaiori, L. Dante, G. Durin, A. Magni, and S. Zapperi, Phys. Rev. B 71, 064423 (2005).
G. Buzsáki and A. Draguhn, Science 304, 1926 (2004).
K. Hukushima and Y. Iba, The Monte Carlo Method in the Physical Sciences: Celebrating the 50th Anniversary of the Metropolis Algorithm, Vol. 690 (AIP, Melville, NY, 2003).
W. Wang, J. Machta, and H. G. Katzgraber, Phys. Rev. E 92, 013303 (2015).
G. Parisi, M. Mézard, and M. Virasoro, World Scientific, Singapore 187, 202 (1987).
M. Mézard, G. Parisi, and R. Zecchina, Science 297, 812 (2002).
M. Mezard, Statistical Physics, Optimization, Inference, and Message-Passing Algorithms: Lecture Notes of the Les Houches School of Physics: Special Issue, October 2013 (Oxford University Press, Oxford, UK, 2015), Chap. 4.
D. Sherrington and S. Kirkpatrick, Phys. Rev. Lett. 35, 1792 (1975).
G. Parisi, J. Phys. A: Math. Gen. 13, 1887 (1980).
M. Mézard, G. Parisi, and M. Virasoro, Europhys. Lett. 1, 77 (1986).
M. Mézard and G. Parisi, Europhys. Lett. 3, 1067 (1987).
M. Mézard and G. Parisi, Eur. Phys. J. B: Cond. Matter Complex Syst. 20, 217 (2001).
M. Mézard and G. Parisi, J. Stat. Phys. 111, 1 (2003).
M. Palassini and S. Caracciolo, Phys. Rev. Lett. 82, 5128 (1999).

Physical Review E

Export citation

Export citation

Combinatorial optimization using dynamical phase transitions in driven-dissipative systems

Abstract

Physics Subject Headings (PhySH)

Article Text

References (73)

Outline

Information

Filter

Filter

Article Lookup

Enter a citation