OPTICAL ISING-MODEL SOLVER USING QUANTUM ANNEALING

Abstract

A method implemented by an optical circuit, including beam splitter, phase shifters and cross-phase modulators, for solving Ising-model using quantum annealing discretizes a continuous time-dependent Hamiltonian function over a time period T, into a plurality of smaller portions; implements each of said smaller portions with a non-linear optical medium, and iterates over said smaller portions to output a solution of the Ising Hamiltonian problem, using the optical components.

Claims

1. An optical circuit for solving Ising-model using quantum annealing comprising: a plurality of optical input ports for receiving a plurality of single photons, respectively; a first plurality of optical programmable beam splitters for splitting the plurality of single photons, respectively to generate a first plurality of split photons; a plurality of optical switches for selecting the first plurality of split photons or output photons output from respective optical output ports of the optical circuit, respectively to generate a plurality of selected photons; a second plurality of optical programmable beam splitters for splitting the plurality of selected photons, respectively to generate a second plurality of split photons; a first plurality of optical linear photon shifting devices for phase shifting of the second plurality of split photons, respectively to generate a first plurality of phase shifted photons; a third plurality of optical programmable beam splitters for splitting the first plurality of phase shifted photons, respectively to generate a third plurality of split photons; a second plurality of optical linear photon shifting devices for phase shifting of the third plurality of split photons, respectively to generate a second plurality of phase shifted photons; and a plurality of optical cross-phase modulators for implementing a quadratic portion of the Ising-model, wherein outputs of the plurality of optical cross-phase modulators are switched by the plurality of optical switches to respective inputs of the second plurality of optical programmable beam splitters or to respective inputs of the optical output ports to be output from the optical circuit, respectively.

2. The optical circuit of claim 1, wherein plurality of single photons are generated by single-photon source are either in a “1” state or a “0” state.

3. The optical circuit of claim 1, wherein first, second and third plurality of optical programmable beam splitters are programmable by thermal tuners.

4. The optical circuit of claim 1, further comprising a counter for keeping track of the number of iterations of the optical circuit and deciding which of the two inputs each of the plurality of the optical switches selects.

5. The optical circuit of claim 1, wherein each of the first plurality of optical linear photon shifting devices implement a same constant phase shift.

6. The optical circuit of claim 1, wherein the second plurality of optical linear photon shifting devices implement a phase shift Φ.sub.m, i according to ${\phi }_{m,i}=B_i.Math.\frac{\mathrm{Tk}.Math..Math.\pi }{m^2}$ where B.sub.i is the number of constraints that a bit i is contained in, m is the number of first plurality of split photons, k is a particular piece of the spit photons and T is the time period in which the Ising-model is adiabatically tuned.

7. The optical circuit of claim 1, wherein each of the plurality of optical cross-phase modulators performs a phase shift proportional to the number of photons in each mode of said each cross-phase modulator.

8. The optical circuit of claim 1, wherein each of the plurality of optical cross-phase modulators imparts a phase to a state in each photon mode that depends on the number of photons in each photon mode.

9. A method implemented by an optical circuit for solving Ising-model using quantum annealing, the method comprising: discretizing a continuous time-dependent Hamiltonian function over a time period T, into a plurality of smaller portions; implementing each of said smaller portions with a non-linear optical medium, and iterating over said smaller portions to output a solution of the Ising Hamiltonian problem.

10. The optical circuit of claim 9, wherein the Hamiltonian function is discretized into said smaller portions, using a Trotter approximation

11. The optical circuit of claim 9, wherein the non-linear optical medium is an optical medium within which a multi-spatial-mode dual-rail-encoded beam propagates.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0018] A more complete appreciation of the present invention, and many of the attendant features and aspects thereof, will become more readily apparent as the invention becomes better understood by reference to the following detailed description when considered in conjunction with the accompanying drawings in which like reference symbols indicate like components.

[0019] FIG. 1 is a simplified block diagram of a system for solving Ising-model using quantum annealing, according to some embodiments of the disclosed invention.

[0020] FIG. 2 is a block diagram of an optical circuit for solving Ising-model using quantum annealing, according to some embodiments of the disclosed invention.

[0021] FIG. 3 is a block diagram of an exemplary single-mode (linear) phase shifter, according to some embodiments of the disclosed invention.

[0022] FIG. 4 is a block diagram of an exemplary programmable beamsplitter, according to some embodiments of the disclosed invention.

[0023] FIG. 5 is a block diagram of an exemplary single-photon detector, according to some embodiments of the disclosed invention.

[0024] FIG. 6 is a block diagram of an exemplary single-photon source, according to some embodiments of the disclosed invention.

[0025] FIG. 7 is a block diagram of an exemplary cross-phase modulator, according to some embodiments of the disclosed invention.

[0026] FIG. 8 is a block diagram of an exemplary optical switch, according to some embodiments of the disclosed invention.

DETAILED DESCRIPTION

[0027] Devices that can solve the Ising model via quantum annealing—a restricted class of adiabatic quantum computers—have recently gained popularity, since the Ising model can encode many interesting NP hard optimization problems. It is however not yet clear if quantum annealing provides speed up in terms of how the number of computational steps scale as the size of the problem grows, as compared to the best classical algorithms. All quantum annealing architectures realized to date employ ‘matter’ qubits, such as superconducting, Nuclear Magnetic Resonance (NMR) and Bose-Einstein condensates. Even in the absence of a computational complexity advantage, an all-optical quantum annealer is attractive due to both its ability to gain a large constant-factor speedup, and a potentially large power saving, over conventional electronic-computing solutions.

[0028] The Ising model can be used to solve a number of constraint satisfaction problems, which are problems of finding solutions that satisfy all the given constraints. Here we give an example with Exact Cover 3 (EC3), which is a constraint satisfaction problem similar to the more well known 3-SAT. In this problem there are a set of clauses or constraints and each clause contains three bits. The clause is said to satisfied if only one of the three bits is a one and the other two are zero. This problem can be expressed using the Ising model as the following quadratic function of a set of n binary-valued variables (sometimes referred to as ‘spins’) s.sub.i=+−1:

H(s.sub.1, . . . , s.sub.n)=Σ.sub.i=1.sup.nB.sub.is.sub.i+Σ.sub.i,j=1.sup.nJ.sub.ijs.sub.is.sub.j,   (1)

[0029] where i and j are the indices for spins. Here B.sub.i is the number of clauses or constraints that contain the bit i in the exact cover 3 (EC3) optimization problem and J.sub.ij is the number of clauses that i and j occur together. The spin configuration is then to be found (out of all 2.sup.n possible such configurations), i.e., values of s.sub.1, . . . , s.sub.n, that minimizes the ‘energy’ H(s.sub.1, . . . , s.sub.n). That is, with given B, and J.sub.ij, find s.sub.i that minimize H. The spin-to-spin couplings is typically chosen to be non-zero only on some pairs (i,j). On these pairs, the strength of the couplings J.sub.ij are usually not the same. In order to map this problem to a Hamiltonian, we need to map the bits (B.sub.i) into spins (qubits).

[0030] For example, in the case of a small instance of EC3 on five bits and three clauses, problem specification of the Ising model includes

[00001]$\left\{\begin{array}{c}{B}_i,1\le \mathrm{is}=n\\ J_{\mathrm{ij}},1\le i,j\le n\\ \mathrm{and}.Math..Math.n\left(\#.Math..Math.\mathrm{of}.Math..Math.\mathrm{bits}\right)\end{array}\right\}$$\mathrm{where},.Math.[\begin{array}{c}{B}_1=2,B_2=2,B_3=3,B_4=1,B_5=1\\ J_{12}=1,J_{13}=2,J_{15}=1,J_{23}=1,J_{24}=1,J_{34}=1,J_{45}\\ n=5\end{array}$

[0031] Now, a bit assignment for the Ising model is calculated as: [0032] x.sub.1, x.sub.2, x.sub.3, x.sub.4, x.sub.5 (each of these being ±1), where

[00002]$s.t..Math.E=\underset{i=1}{\overset{5}{.Math.}}.Math..Math.B_i.Math.x_i+\underset{i,j}{.Math.}.Math..Math.J_{\mathrm{ij}}.Math.x_i.Math.x_j$

is minimized.

[0033] This problem is NP hard in general and can be mapped to many interesting problems.

[0034] In some embodiments, the disclosed invention breaks up the Hamiltonian into smaller more manageable pieces. For example, [0035] Theorem 1 Let H.sub.QI(t) denote the quantum Ising Hamiltonian defined above, then it can be approximated to within an error ε by an evolution of the form U.sub.1 . . . U.sub.m, where

[00003]$\begin{array}{cc}{U}_k=H^{.Math.n}.Math.\exp \left(-{\mathrm{iH}}_{\mathrm{init}}^{\prime }.Math.\frac{T}{m}.Math.\left(1-\frac{k}{m}\right)\right).Math.H^{.Math.n}.Math.\exp \left(-{\mathrm{iH}}_{\mathrm{final}}.Math.\frac{T}{m}.Math.\frac{k}{m}\right),& \left(17\right)\end{array}$ [0036] where H′.sub.init=Σ.sub.iσ.sub.z.sup.(i)). Here m=O(T.sup.2n.sup.d/c), where n is the number of bits in the input and d is a constant that depends on the number of clauses.

[0037] “Clauses” in the above theorem refers to the constraints of the EC3 or any other constraint satisfaction problem. Here, H.sub.final can be broken into two portions: B.sub.i and J.sub.ij, as described in Equation (1).

[0038] This theorem follows from the known Trotter approximation (also known as split-step Fourier) to break up the Hamiltonian into manageable pieces. Given a cross-Kerr strength x.sub.0, the number of steps needed to break up the Hamiltonian evolution and the eventual error are obtained as follow: [0039] m=O(T/x.sub.0), where m is the number of terms (iterations) needed (i≦k≦m). [0040] ε≦x.sub.0Tn.sup.3π, where x is cross-phase modulation strength (non-linear phase), ε is the error probability in the computation, T is the time needed to run the adiabatic computation (time of evolution), where T≈1/g.sub.min.sup.3, n is the number of qubits in the instance, and g.sub.min is minimum energy gap (depends on problem spec.). x can also be specified as available resource.fwdarw.highest x achievable) as ε being specified as the achievable error. For example, m may be about 40,000, x.sub.0=10.sup.−4, n=5, T˜4, g˜0.647, and ε less than or equal to 0.003.

[0041] In some embodiments, the optical circuit of the disclosed invention uses linear optical gates such as beamsplitters and phase shifters and also cross-phase modulators (e.g., cross-Kerr gates). Beamsplitters and phase shifters are generally called passive linear optical elements. They are given by the following Hamiltonians.

H.sub.BS=exp(−i eta(â b+b̂ a)), H.sub.PS=exp(−i theta âa)

[0042] where a and b are the annihilation operators of the two modes. It can be shown that any passive mode transformation can be decomposed into a network of beamsplitters and phase shifters. Here, a cross-phase modulation (XPM) gate may be used to act on two Hamiltonian modes.

[0043] In some embodiments, the disclosed invention is an all-optical implementation of quantum annealing machine including programmable linear optics, for example, beamsplitters, optical tunable phase shifters, and optical in-line cross-phase modulators across pairs of spatial modes, with very small yet tunable non-linear phases. The disclosed invention encodes the general quantum Ising model, and thus converges it to the optimal solution. One way to implement such cross-phase modulation is to employ the optical cross-Kerr effect. Although implementing an in-line cross-Kerr over a pair of single-photon-intensity optical modes propagating in an optical waveguide may be forbidding, the strength of the per-mode cross-phase-modulation can be taken to be very small for the disclosed invention. (See for example, J. H. Shapiro, “Single-photon Kerr nonlinearities do not help quantum computation,” Phys. Rev. A 73, 062305 (2006)”, the entire contents of which is expressly incorporated by reference herein.). Given a cross-phase modulation strength that is realizable, one can make the discretization of the Hamiltonian finer, while still ensuring that the error obtained (due to the space-discretized implementation) remains negligible. In some embodiments, the disclosed invention can be realized scalably using recently proposed designs in integrated photonics.

[0044] In some embodiments, the disclosed invention discretizes the tuned Hamiltonian slowly over a time period H(t), into many small pieces using a Trotter approximation, and maps the evolution time T to a spatial extent within a non-linear optical medium within which a multi-spatial-mode dual-rail-encoded beam propagates. In other words, the disclosed invention is based on a discretized adiabatic evolution of the transverse Ising model, rather than the continuous one. It has been shown that the error obtained is negligible as long as certain conditions on the granularity of the discretization are met. An exemplary optical circuit described according to the disclosed invention is capable of solving a 5-bit instance of the exact cover 3 (EC3) optimization problem, although the disclosed invention is not limited to such 5-bit instance and is capable of solving a higher or lower bit instance of the EC3 problem.

[0045] Now, in order to implement the Ising Hamiltonian, one needs to first decide on an encoding of the qubits into optical states. In some embodiments, the standard dual-rail-encoding, which encodes each qubit into two modes that share a single photon, is used. This map sends the qubit zero into the state where the photon is in the first mode and the qubit one to the state where the photon is in the second mode. To implement the Hamiltonian, each of the terms of the Hamiltonian is put together. The final Hamiltonian comprises of diagonal terms that can be implemented using phase shifters and cross-Kerr gates.

[0046] The first term of the final Hamiltonian is Σ.sub.iB.sub.iZ.sub.i. The action of this term in the dual-rail encoding is the same as that of a phase shifter. Recall that a qubit is mapped to a photon being in one of two modes; first mode for qubit zero and second mode for qubit one. Now, since the σ.sub.z gate acts on the zero qubit as the identity and the one qubit as the negative identity, only one phase shifter is needed to implement it optically. The phase shifter is only on the second mode and puts a phase of π in order to act as the negative identity θ=B.sub.iπ.

[0047] The cross-phase modulator (cross-Kerr gate) simulates the second term of the final Hamiltonian. The second term is Σ.sub.ijZ.sub.iZ.sub.j. This acts on a pair of qubits and in the computational basis, it is essentially a CPHASE gate, i.e., only if both the qubits are one, then it applies a phase of π This means that optically, this can be implemented by applying a cross-phase modulator (cross-Kerr gate) on the second modes of the two qubits with a phase of π i.e., x=J.sub.ijπ.

[0048] In some embodiments, to simulate the initial Hamiltonian, optical beamsplitters are used in the optical circuit of the disclosed invention. The initial Hamiltonian, which on any qubit is σ.sub.z, can be re-written as H σ.sub.z H, where H is the Hadamard gate. The Hadamard gate is a one-qubit rotation, mapping the qubit-basis states and to two superposition states with equal weight of the computational basis states and . How to implement a σ.sub.z on any qubit is explained above. To implement the initial Hamiltonian, the Hadamard gate needs to be implemented. In the dual-rail basis, the Hadamard gate is a 50:50 beamsplitter on the two modes that make up the qubit. This means that we start with n pairs of modes with a single photon in the first mode and apply 50:50 beamsplitters to all the pairs. An example of this is shown in FIG. 2.

[0049] To demonstrate an exemplary optical circuit, a small instance of EC3 on five bits and three clauses is chosen as an example. Suppose the bits are labeled x.sub.1 through x.sub.5 and consider the three clauses on bits (1,2,3), (2,3,4) and (1,3,5). That is, B.sub.1 to B.sub.5 are 1, 2, 3, 1 and 1. Similarly, J.sub.12=1, J.sub.13=2, J.sub.15=1, J.sub.23=1, J.sub.24=1, J.sub.34=1 and J.sub.45=1. Then the Ising problem Hamiltonian is:

H=2s.sub.1+2s.sub.2+3s.sub.3+s.sub.4+s.sub.5+s.sub.1s.sub.2+2s.sub.1s.sub.3+s.sub.1s.sub.5+s.sub.2s.sub.3+s.sub.2s.sub.4+s.sub.3s.sub.4+s.sub.4s.sub.5    Eq. (16)

[0050] It turns out that numerically, one can obtain that the minimum gap of the adiabatic interpolation is 0.647 and this indicates that T must be approximately equal to 4. If one chooses m to be 40,000 (for x.sub.0=10.sup.−4), then the error in this implementation when compared to the continuous implementation is ε less than or equal to 0.0034. This can be implemented by the optical circuit in FIG. 2.

[0051] The method finds the ground state of an Ising model Hamiltonian (which is a function of the spins by creating a time-dependent Hamiltonian, breaking it up into smaller pieces that can be assumed to be time-independent and implementing each of these pieces using a multi-spatial mode dual-rail encoded optical circuit consisting of beamsplitters, phase shifters, cross-Kerr devices, optical switches and photon detectors.

[0052] FIG. 1 is a simplified block diagram of a system for solving Ising-model using quantum annealing, according to some embodiments of the disclosed invention. As described above, the problem specification for Ising problem may be specified as: problems {B.sub.i}, {J.sub.ij}, N. This problems specification provides d, g, and n as inputs 102 to the system 104 of the disclosed invention, which in turn, provides the input to the optical circuit depicted in FIG. 2. As explained above, g is the minimum gap between the energy of the ground state and the first excited state of H(t) over the interval tin (0, T), and n is the number of qubits in the instance. The error probability c is also input 106 to the system 104. X in block 110 determines the number of smaller pieces that the problem will be broken into, based on the given parameters.

[0053] The optical circuit of the disclosed invention provides a solution to the Ising problem as an output 108 the bit string that corresponds to the solution of the Ising problem and the run time scales as

[00004]$T\sim \frac{1}{g^3},$

as described above. In some embodiments, the optical circuit may include “cross-phase modulation” of adjustable strength, which may be included in the system 104.

[0054] FIG. 2 is a circuit block diagram of an optimal receiver, according to some embodiments of the disclosed invention. As illustrated, this example is for a 5-bit EC3 problem, however, as one skilled in the art would recognize, other number of bits are also possible and are within the scope of the disclosed invention. As shown, single photons 202a-202e are input to the optical optimal receiver 200, for example, by a plurality of optical input ports, respectively. The single photons may be generated by a single-photon source and can be in a “1” state meaning a photon in present (e.g., above a threshold value), or in a “0” state meaning the photon is not present (e.g., lower than a threshold value).

[0055] FIG. 6 is a block diagram of an exemplary single-photon source, according to some embodiments of the disclosed invention. Single-photon sources are available as optical components. Parameters characterizing a single-photon source include:

[0056] g.sup.(2)(0): Purity (g.sup.(2)(0)=0 is ideal),

[0057] η.sub.s: efficiency (η.sub.s=1 is ideal), and

[0058] bandwidth (at what rate photons in |1> state can be produced).

[0059] The output shown is the quantum state of the output mode â. |1> means the mode â is occupied by exactly 1 photon.

[0060] Referring back to FIG. 2, the single photons 202a-202e are then split by respective linear programmable beam splitters 204a-204e to modify the initial state to create a superimposition of the single photon inputs.

[0061] FIG. 4 is a block diagram of an exemplary programmable beamsplitter, according to some embodiments of the disclosed invention. Programmable beamsplitters are also available as optical components/devices. The depicted 2-mode-input, 2-mode output beam splitter is standard, where η is transmissivity and ηε[0,1]. The inputs and outputs of FIG. 4 are the modes of optical fields. The beamsplitter essentially relates the input modes to the output modes in a linear fashion.

[0062] Having linear programmable beam splitters allow encoding different instances of the Ising problem into one programmable (special-purpose) optical computer. In some embodiments, the beamsplitter circuits can be programmed by using thermal tuners (localized heaters that tune the phases).

[0063] Referring back to FIG. 2, the split photons are then input to respective optical switches (or optical multiplexors) 206a.sub.1-206e.sub.2. Each of the optical switches 206a.sub.1-206e.sub.2 select either the split input photon or the output photon output from the respective optical output ports 220.sub.1-220.sub.10 to go through the required interactions to solve the problem.

[0064] FIG. 8 is a block diagram of an exemplary optical switch, according to some embodiments of the disclosed invention. As shown, the optical switch selects one of its inputs, â or {circumflex over (b)} as its output depending on a signal. In some embodiments, a counter that keeps track of the number of iterations of the circuit decides which of the inputs the optical switch selects. The optical switch may be a switchable mirror known in the art.

[0065] Referring back to FIG. 2, the split photon (input photons, or output photons from the previous iteration) are then input to a second set of linear programmable beam splitters 208a-208e to implement the first in Equation (17). The second set of linear programmable beam splitters 208a-208e are similar to exemplary programmable beamsplitters of FIG. 4. The output of the second set of beam splitters 208a-208e are then input to respective linear photon shifting elements/devices 210a-210e. Each of the linear photon shifting device 210a-210e imposes a phase shift of θm, which is given by

[00005]${\theta }_m=\frac{T}{m}\left[1-\frac{k}{m}\right].Math.\pi$

[0066] Here, the Hamiltonian is broken up into m manageable (smaller) pieces (portions) and each piece is labelled by an index k. The phase shift imparted in this piece depends on m and k.

[0067] FIG. 3 is a block diagram of an exemplary single-mode (linear) phase shifter, according to some embodiments of the disclosed invention. Single-mode (linear) phase shifter are also available as optical components/devices. They can also be implemented by various known methods in integrated photonics, for example, by thermoelectric/piezoelectric timing components. The output is represented as {circumflex over (b)}=e.sup.iθâ. Input-output relation (â, {circumflex over (b)}) are field operators of the input and output modes, respectively. θ is the phase shift, where θ ε[0,2).

[0068] Referring back to FIG. 2, the phase shifted photons are then input to a third set of (linear programmable) beam splitters 212a-212e. This third set of beam splitters implement the second in Equation (17). The third set of (linear programmable) beam splitters 212a-212e are similar to exemplary programmable beamsplitters of FIG. 4. The output of the third set of beam splitters 212a-212e are then input to respective linear photon phase shifting elements 214a-214e. The photon shifting elements 214a-214e shift the respective photons by:

[00006]${\phi }_{m,i}=B_i.Math.\frac{\mathrm{Tk}.Math..Math.\pi }{m^2}$

where B.sub.i is the number of constraints that the bit i is contained in.

[0069] This phase implements the first portion, that is, B.sub.i of H.sub.final in Equation (17) and is dependent on the total number of pieces (portions) the Hamiltonian is being broken up into, i.e., m and B.sub.i, as well as the particular piece labelled k.

[0070] The output of the photon shifting elements 214a-214e are then input to respective optical cross-phase modulators (cross-Kerr gates) 216a-216g. The cross-phase modulators implement the quadratic part of the Ising Hamiltonian, that is, the second portion, J.sub.ij of H.sub.final in Equation (17). Such quadratic terms need non-linear interaction between pairs of photons and cross-phase modulation is one way of achieving this.

[00007]${\chi }_{\mathrm{ij}}=J_{\mathrm{ij}}.Math.\frac{\mathrm{Tk}.Math..Math.\pi }{m^2}$

[0071] The strength of the cross-phase modulation depends on the number of pieces that the Hamiltonian is broken up into (i.e., m), the particular piece k and J.sub.ij, which are the strength of the quadratic term in the Ising Hamiltonian (for the application to EC3, it comes from the number of constraints in which bits i and j appear together).

[0072] FIG. 7 is a block diagram of an implementation of a cross-phase modulator, according to some embodiments of the disclosed invention. Note that the phase shift performed by a cross-phase modulator on one optical mode (the modulator takes as input two optical modes) is proportional to the intensity (number of photons) of each of its input modes. Cross-phase modulation is a non-linear operation unlike beamsplitters and phase shifters. The effect of cross-phase modulation (which is a two mode operation) imparts a phase to the state in each (photon) mode that depends on the number of photons in each mode i.e., a non-linear phase. The embodiment imparts phases that have a strength x in the two modes.

[0073] Referring back to FIG. 2, the outputs of the cross-phase modulators (cross-Kerr gates) 216a-216g are then switched back (or multiplexed) to the respective inputs of the second set of beam splitters 208a-208e as a feedback, or are output by the respective optical ports 220.sub.1-220.sub.10. Each of the optical switches 218a.sub.1-218e.sub.2 direct the output of it respective cross-phase modulators to the respective optical output ports 220.sub.1-220.sub.10 or back to the optical switches 206a.sub.1-206e.sub.2 to go through the required interactions to solve the problem. The optical ports 220.sub.1-220.sub.10 are similar to the single photon detectors depicted in FIG. 5.

[0074] In some embodiments, the disclosed invention discretizes a continuous time-dependent Hamiltonian function over a time period T, into a plurality of smaller portions; implements each of said smaller portions with a non-linear optical medium, and iterates over the smaller portions to output a solution of the Ising Hamiltonian problem.

[0075] In some embodiments, the all-optical quantum annealer implementation of the disclosed invention utilizes some of the advances in quantum non-linear integrated photonics, programmable linear optics and tunable quantum non-linear optics in a cavity QED system.

[0076] In some embodiments, the disclosed invention is an all-photonic implementation of quantum annealing, a restricted form of quantum computing that can encode the Ising model and thus solve many NP hard optimization and NP complete decision problems, which are computationally hard to do on a classical computer. In some embodiments, the solver according to the disclosed invention converges to the optimal solution. In some embodiments, the optical Ising solver is implementable on an integrated photonic chip, using on-chip programmable linear optics and on-chip quantum non-linear optics. This provides a substantial speed up over classical computing solutions, due to the computations being performed at the speed of light. Some applications of this optical circuit are in solving machine learning, job scheduling and resource allocation problems.

[0077] It will be recognized by those skilled in the art that various modifications may be made to the illustrated and other embodiments of the invention described above, without departing from the broad inventive step thereof. It will be understood therefore that the invention is not limited to the particular embodiments or arrangements disclosed, but is rather intended to cover any changes, adaptations or modifications which are within the scope of the invention as defined by the appended drawings and claims.