# Abstract

In recent years, there has been a growing interest in optical simulation of lattice spin models for applications in unconventional computing. Here, we propose optical implementation of a three-state Potts spin model by using networks of coupled parametric oscillators with phase tristability. We first show that the cubic nonlinear process of spontaneous three-photon down-conversion is accompanied by a tristability in the phase of the subharmonic signal between three states with 2*π*/3 phase contrast. The phase of such a parametric oscillator behaves like a three-state spin system. Next, we show that a network of dissipatively coupled three-photon down-conversion oscillators emulates the three-state planar Potts model. We discuss potential applications of the proposed system for all-optical optimization of combinatorial problems such as graph 3-COL and MAX 3-CUT.

## 1 Introduction

Combinatorial optimization deals with minimizing (maximizing) a cost function over a finite and discrete set of objects. These problems appear in a wide range of applications and generally involve large configuration spaces, which makes an exhaustive search impractical [1]. As a result, over the years, a number of heuristic and unconventional methods are developed aiming to speed up the search process [1]. An interesting approach is to use physical systems as analog computing platforms that emulate spin lattice models, which allow for solving many computationally hard combinatorial problems [2]. Gain-dissipative optical systems have recently attracted much interest as a physical platform for simulating spin lattice models [3], [4], [5], [6], [7], [8], [9], [10], [11], [12], [13], [14]. In particular, networks of coupled optical parametric oscillators have been used for optically implementing the Ising Hamiltonian [5]. This Ising solver has been also utilized in conjunction with digital processing to implement a Potts model solver [15]. The core to physical realization of the Ising model is the inherent phase bistability of the two-photon down-conversion process in an optical parametric oscillator, which emulates the two states of a classical spin.

In principle, many NP-complete combinatorial problems can be mapped to the two-state Ising spin model [16]. Nonetheless, the formulation of the problem as an Ising Hamiltonian usually involves adding extra spin degrees of freedom to embed penalty terms to favor the solutions within the required constraints of the original problem. Therefore, solving problems that do not have the exact same cost function as the Ising energy function may become challenging as finding the optimal embedding parameters that can rule out invalid solutions becomes harder for larger problems [17]. Furthermore, the extra spins add to the complexity and density of the network, which makes their physical implementation more difficult. Therefore, it is of great interest to develop novel physical systems that allow for compact embeddings of the cost function of certain optimization problems. In this regard, as a generalization of the Ising model, the Potts model is an interesting candidate [18], [19].

The planar Potts model is a lattice spin model, in which the spins are confined in a plane and oriented along any of the *q* discrete uniformly distributed angles of *q*-state planar Potts Hamiltonian is defined as [20]:

where, *i*th and *j*th lattice sites, with *δ* is the Kronecker delta function. Clearly, for *q* = 2, this Hamiltonian reduces to that of the Ising model.

In this letter, we propose an optical three-state Potts machine through networks of coupled parametric three-photon down-conversion (3PDC) oscillators. The nonlinear process of 3PDC is schematically depicted in Figure 1A. In these

### Figure 1:

## 2 Phase tristability of the 3PDC oscillator

The nonlinear optical process of spontaneous parametric 3PDC has been theoretically explored and experimentally demonstrated in the bulk [21], in optical fibers [22], and in resonant cavities [23], [24], [25], [26]. However, the interesting phase tristability of the subharmonic signal seems to be overlooked in previous studies. Here, we derive a second-order nonlinear oscillator model for the subharmonic signal, which allows for analytical investigation of the 3PDC oscillations and its pertinent tristability.

Considering a doubly resonant cavity driven with a pump laser as depicted in Figure 1B, coupled mode equations for the complex modal amplitudes of the pump (*a*_{p}) and signal (*a*_{s}) can be written as [26]:

In these relations, *μ* describes the nonlinear interaction between the pump and the signal harmonics, *s*_{p} is the complex amplitude of the pump drive field. The fields are normalized such that

The phase tristability can be investigated analytically based on a reduced model. Here, we neglect the frequency detunings and the self- and cross-phase modulation terms. In addition, we assume that the lifetime of the signal photons is much longer than that of the pump photons, that is,

where the signal subscripts are removed for simplicity. In this relation, *A* is a positive root of the quartic equation

The three parameters involved are *κ*, *g*_{0}, and *g*_{s}, which, respectively, represent linear signal loss, small-signal gain, and gain saturation coefficients. It is straightforward to show that the onset of parametric oscillations at the ternary states occurs at the threshold gain level *g*_{th}, where

For gain levels above this threshold value, self-sustained oscillation of the signal becomes prominent. In this case, owing to the coexistence of the trivial solution, seeding is necessary to avoid death of the signal. However, by increasing the gain level, the seeding requirement becomes less critical and for large gain levels noise can trigger oscillations of the signal.

## 3 The optical Potts machine

By trapping into the triple attractors, the continuous phase of the 3PDC oscillator evolves into one of the three stable discrete values of *N* identical oscillators with pairwise dissipative coupling among the oscillators. The time evolution of the complex field amplitude of the *m*th oscillator is governed by

Here, *m*th and *n*th oscillators. The presence of the diagonal term in the summation is due to energy conservation. According to this term, the total loss of the *m*th cavity is

By defining *Q* is the coupling matrix, with off-diagonal elements

To reach a nontrivial equilibrium, the gain injected to the Potts machine should compensate the total of internal and interaction losses. Therefore, the threshold gain can be found in terms of the smallest modal loss of the coupled cavity network. Taking *Q*, the minimum network loss is

The equilibrium properties of the Potts machine can be best discussed in terms of a potential landscape function

By directly integrating Eq. (5), *F* is found to be

The functional *F* can be viewed as a potential defined over a 2*N*-dimensional space that involves all possible trajectories of the set of dynamical Eq. (5) for various initial conditions, while the fixed-points are located at the extrema (local or global) of this potential. It is straightforward to show that the total derivative of this function along the trajectories of Eq. (5) is negative semidefinite: *F*. The existence of the potential function *F* guarantees local stability of the network at equilibrium points.

The functional of Eq. (7) can be considered as a cost function for the Potts machine, that is, the evolution of the system is toward minimizing *F*. Therefore, it is of interest to show its connection with the Potts Hamiltonian. This cost function is composed of two terms associated with self-oscillations of individual oscillators and the interaction between oscillators. For a given gain level, the self-oscillation term is minimized when each oscillator stabilizes to its ternary state discussed in the previous section. The interaction term, on the other hand, is minimized when each pair of coupled oscillators are out of phase. The relative contribution of these two terms in the total cost function can be evaluated with the gain parameter *g*_{0} and the coupling coefficients

where,

To numerically investigate the Potts machine, we consider the example of a simple network with three equally coupled oscillators as shown in Figure 2. Here, we consider three different drive conditions and evaluate the dynamics of the amplitudes and phases of the oscillators. First, the gain is abruptly turned on and kept constant at a small value below the network threshold, which results in the death of all oscillators to zero amplitudes (Figure 2A). Next, for a gain higher than the total network loss (Figure 2B), the network reaches a nontrivial equilibrium, where all oscillators stabilize to constant amplitudes and phases. In this case, the equilibrium phase state of the network

### Figure 2:

## 4 Application to combinatorial optimization

Lattice spin models have been widely utilized as heuristics to solve computationally hard combinatorial optimization problems [16]. For this purpose, the cost function of the optimization problem is generally cast as the Hamiltonian of a spin model, which will then be solved for its ground state. The Potts model, in particular, is ideally suited for maximum *q*-cut (MAX *q*-CUT) and graph *q*-coloring (*q*-COL) problems [20], which belong to the class of NP-hard problems and arise in applications such as register allocation and timetable/examination scheduling [27], [28]. The MAX 3-CUT problem can be stated as partitioning a graph into three disjoint sets such that the number of edges between disjoint parts is maximized. This is also equivalent to finding a three-coloring of the graph vertices such that the number of connected vertices of the same color is minimized.

This problem can be readily formulated as finding the ground state of the Potts Hamiltonian (Eq. 1). For the antiferromagnetic case with *m*, *n*} pairs. The equivalence of these problems with the Potts Hamiltonian is particularly clear using the standard Potts Hamiltonian form *κ*, while the gain *g*_{0} is linearly increased from zero until the network stabilizes into an equilibrium state, where all intensities are equal and the phases remain constant. The oscillators are initialized with small amplitudes and random phases. For each network, the simulations are repeated for an ensemble of 1000 random initial conditions and a histogram of the equilibrium-state energy is plotted.

### Figure 3:

In all cases, the Potts machine shows good performance as an optimizer. However, in many incidents the systems is trapped into local minima and the global minimum is not found. This problem can be largely circumvented by injecting random fluctuations into the oscillators, which assist the network to escape from shallow local minima. The performance of the Potts machine for the two scenarios of without and with noise is compared through their associated histograms in Figure 3A–C. The time domain evolution of the intensities and phases of the Peterson network is depicted for these two scenarios in Figure 3D and E. As these figures clearly indicate, the phases undergo a complex dynamics in the scenario when noise is involved until the network settles into an equilibrium state that cannot be escaped with random fluctuations. Our simulations indicate that the performance of the Potts machine as an optimizer depends strongly on the pump and the coupling parameters. The pace of increasing the gain is found to play an important role in finding the optimal solution. In fact, depending on the network threshold and noise level, the gain should be increased fast enough to prevent death of oscillators. On the other hand, a rapid increase in the gain level to a large value may force the system into a local minimum without giving it enough time to search for states with lower energies.

## 5 Conclusion and discussion

In summary, we proposed optical implementation of the three-state Potts model by using a network of coupled 3PDC oscillators. The state of the proposed Potts machine is in general described by continuous intensities and phases of the governing oscillators. However, when reaching an equilibrium, the oscillators reach an equal intensity state and the phases take ternary discrete values. Thus, the equilibrium phase pattern of the Potts machine represents a valid spin configuration of the Potts model. In this case, the energy of the Potts spin model is mapped into the cost function of the oscillator network. By adiabatically increasing the gain, the oscillator network tends to evolve toward an equilibrium phase pattern associated with the ground state of the Potts Hamiltonian.

Our numerical simulations suggest that the Potts machine suffers from trapping into local minima, which is a challenge in many heuristic optimization techniques. In this regard, an important future direction is to find the optimal initialization and parameter tuning which allows for finding the global minimum for an arbitrary network. The parametric 3PDC oscillations which forms the basis of the proposed Potts machine is within experimental reach [26]. In addition, arbitrary network coupling topologies can be implemented through a time domain multiplexing technique similar to the scheme utilized in Ref. [5]. In principle, the proposed machine can be generalized to the *q*-state Potts model (for *q*-photon down-conversion processes. Such high-order nonlinear effects suffer from poor conversion efficiencies. However, an alternative approach is to implement subharmonic generation at more than one stage and through cascading of lower-order down-conversion processes.

**Author contribution**: All the authors have accepted responsibility for the entire content of this submitted manuscript and approved submission.**Research funding**: None declared.**Conflict of interest statement:**The authors declare no conflicts of interest regarding this article.

### References

[1] C. H. Papadimitriou and K. Steiglitz, *Combinatorial Optimization: Algorithms and Complexity*, Upper Saddle River NJ: Courier Dover, 1998. Search in Google Scholar

[2] J. J. Hopfield, “Neural networks and physical systems with emergent collective computational abilities,” *Proc. Natl. Acad. Sci. U. S. A.*, vol. 79, no. 8, pp. 2554–2558, 1982. https://doi.org/10.1073/pnas.79.8.2554. Search in Google Scholar

[3] S. Utsunomiya, K. Takata, and Y. Yamamoto, “Mapping of Ising models onto injection-locked laser systems,” *Opt. Express*, vol. 19, pp. 18091–18108, Sep. 2011. https://doi.org/10.1364/oe.19.018091. Search in Google Scholar

[4] Z. Wang, A. Marandi, K. Wen, R. L. Byer, and Y. Yamamoto, “Coherent Ising machine based on degenerate optical parametric oscillators,” *Phys. Rev. A*, vol. 88, p. 063853, Dec. 2013. https://doi.org/10.1103/physreva.88.063853. Search in Google Scholar

[5] A. Marandi, Z. Wang, K. Takata, R. L. Byer, and Y. Yamamoto, “Network of time-multiplexed optical parametric oscillators as a coherent Ising machine,” *Nat. Photon.*, vol. 8, pp. 937–942, Dec. 2014. https://doi.org/10.1038/nphoton.2014.249. Search in Google Scholar

[6] M. Nixon, E. Ronen, A. A. Friesem, and N. Davidson, “Observing geometric frustration with thousands of coupled lasers,” *Phys. Rev. Lett.*, vol. 110, p. 184102, May 2013. https://doi.org/10.1103/physrevlett.110.184102. Search in Google Scholar

[7] P. L. McMahon, A. Marandi, Y. Haribara, et al., “A fully programmable 100-spin coherent Ising machine with all-to-all connections,” *Science*, vol. 354, no. 6312, pp. 614–617, 2016. https://doi.org/10.1126/science.aah5178. Search in Google Scholar

[8] T. Inagaki, Y. Haribara, K. Igarashi, et al., “A coherent Ising machine for 2000-node optimization problems,” *Science*, vol. 354, no. 6312, pp. 603–606, 2016. https://doi.org/10.1126/science.aah4243. Search in Google Scholar

[9] Y. Takeda, S. Tamate, Y. Yamamoto, H. Takesue, T. Inagaki, and S. Utsunomiya, “Boltzmann sampling for an XY model using a non-degenerate optical parametric oscillator network,” *Quantum Sci. Technol.*, vol. 3, p. 014004, Nov. 2017. https://doi.org/10.1088/2058-9565/aa923b. Search in Google Scholar

[10] N. G. Berloff, M. Silva, K. Kalinin, et al., “Realizing the classical XY Hamiltonian in polariton simulators,” *Nat. Mater.*, vol. 16, pp. 1120–1126, Nov. 2017. https://doi.org/10.1038/nmat4971. Search in Google Scholar

[11] K. P. Kalinin and N. G. Berloff, “Simulating Ising and n-state planar potts models and external fields with nonequilibrium condensates,” *Phys. Rev. Lett.*, vol. 121, p. 235302, Dec. 2018. https://doi.org/10.1103/physrevlett.121.235302. Search in Google Scholar

[12] M. Parto, W. Hayenga, A. Marandi, D. N. Christodoulides, and M. Khajavikhan, “Realizing spin Hamiltonians in nanoscale active photonic lattices,” *Nat. Mater.*, vol. 19, pp. 725–731, Mar. 2020. https://doi.org/10.1038/s41563-020-0635-6. Search in Google Scholar

[13] D. Pierangeli, G. Marcucci, and C. Conti, “Large-scale photonic Ising machine by spatial light modulation,” *Phys. Rev. Lett.*, vol. 122, p. 213902, May 2019. https://doi.org/10.1103/physrevlett.122.213902. Search in Google Scholar

[14] F. Böhm, G. Verschaffelt, and G. Van der Sande, “A poor man’s coherent Ising machine based on opto-electronic feedback systems for solving optimization problems,” *Nat. Commun.*, vol. 10, p. 3538, Aug. 2019. https://doi.org/10.1038/s41467-019-11484-3. Search in Google Scholar

[15] T. Inagaki, K. Inaba, K. Igarashi, et al., “Potts model solver with coherent Ising machine,” in 49th Winter Colloquium on the Physics of Quantum Electronics, 2019. Search in Google Scholar

[16] A. Lucas, “Ising formulations of many NP problems,” *Front. Phys.*, vol. 2, p. 5, 2014. https://doi.org/10.3389/fphy.2014.00005. Search in Google Scholar

[17] G. V. Wilson and G. S. Pawley, “On the stability of the travelling salesman problem algorithm of Hopfield and tank,” *Biol. Cybern.*, vol. 58, pp. 63–70, 1988. https://doi.org/10.1007/bf00363956. Search in Google Scholar

[18] I. Kanter and H. Sompolinsky, “Graph optimisation problems and the Potts glass,” *J. Phys. Math. Gen.*, vol. 20, pp. L673–L679, Aug. 1987. https://doi.org/10.1088/0305-4470/20/11/001. Search in Google Scholar

[19] C. Peterson and B. Söderberg, “A new method for mapping optimization problems onto neural networks,” *Int. J. Neural Syst.*, vol. 1, no. 1, pp. 3–22, 1989. https://doi.org/10.1142/s0129065789000414. Search in Google Scholar

[20] F. Y. Wu, “The Potts model,” *Rev. Mod. Phys.*, vol. 54, pp. 235–268, Jan. 1982. https://doi.org/10.1103/revmodphys.54.235. Search in Google Scholar

[21] F. Gravier and B. Boulanger, “Triple-photon generation: comparison between theory and experiment,” *J. Opt. Soc. Am. B*, vol. 25, pp. 98–102, Jan. 2008. https://doi.org/10.1364/josab.25.000098. Search in Google Scholar

[22] S. Richard, K. Bencheikh, B. Boulanger, and J. A. Levenson, “Semi-classical model of triple photons generation in optical fibers,” *Opt. Lett.*, vol. 36, pp. 3000–3002, Aug. 2011. https://doi.org/10.1364/ol.36.003000. Search in Google Scholar

[23] T. Felbinger, S. Schiller, and J. Mlynek, “Oscillation and generation of non-classical states in three-photon down-conversion,” *Phys. Rev. Lett.*, vol. 80, pp. 492–495, Jan. 1998. https://doi.org/10.1103/physrevlett.80.492. Search in Google Scholar

[24] A. A. Kalachev and Y. Z. Fattakhova, “Generation of triphotons upon spontaneous parametric down-conversion in a resonator,” *Quantum Electron.*, vol. 37, pp. 1087–1090, Dec. 2007. https://doi.org/10.1070/qe2007v037n12abeh013671. Search in Google Scholar

[25] A. Hayat and M. Orenstein, “Photon conversion processes in dispersive microcavities: quantum-field model,” *Phys. Rev. A*, vol. 77, p. 013830, Jan. 2008. https://doi.org/10.1103/physreva.77.013830. Search in Google Scholar

[26] C. Zhou and P. Bermel, “High-efficiency cascaded up and down conversion in nonlinear Kerr cavities,” *Opt. Express*, vol. 23, pp. 24390–24406, Sep. 2015. https://doi.org/10.1364/oe.23.024390. Search in Google Scholar

[27] G. J. Chaitin, “Register allocation & spilling via graph coloring,” *SIGPLAN Not*, vol. 17, pp. 98–101, Jun. 1982. https://doi.org/10.1145/872726.806984. Search in Google Scholar

[28] A. Schaerf, “A survey of automated timetabling,” *Artif. Intell. Rev.*, vol. 13, pp. 87–127, Apr. 1999. https://doi.org/10.1023/a:1006576209967. Search in Google Scholar

**Received:**2020-04-27

**Accepted:**2020-07-13

**Published Online:**2020-07-29

© 2020 Mostafa Honari-Latifpour and Mohammad-Ali Miri, published by De Gruyter, Berlin/Boston

This work is licensed under the Creative Commons Attribution 4.0 International License.