Max-Cut Solver

Here, we can solve a MAX-CUT problem using the QNN machine and QNN simulator. The MAX-CUT problem presented here can be stated as follows. Given a group of vertices and the edges that connect those vertices (graph), divide the vertices into two groups, A and B, and find the division of vertices (A, B) called a cut for which the weight is maximum. Given that weight wij for the edge between vertices i and j can take on the value {1, 0, -1} (with wij = 0 corresponding to no edge), the cut can be given by the following expression:

The number of summed weights wij of edges straddling groups A and B of the divided vertices is the “cut number.” Now, if we allocate binary variable σi to each vertex with each group-A vertex taking on the value of “1” and each group-B vertex taking on the value of “-1,” the above expression can be rewritten as shown on the right of the above equation. In the case of the QNN machine and QNN simulator, an OPU pulse corresponds to a vertex while each optical parametric oscillator (OPO) phase (0, π) corresponds to binary variable σi (1, -1).

Here, Jij is the coupling constant between the ith and jth Ising spin having the relationship Jij = -Wij .

We use the graph-generation program “rudy” to generate a weighted graph (wij = wji). Details can be found here (link: https://web.stanford.edu/~yyye/yyye/Gset/).

Four types of graphs can be experimented with here: complete graph, random graph, scale-free graph, and toroidal graph.

Complete graph： | All edges of the graph are given a weight of “1” or “-1” randomly. |

Measurement

Here, we can make use of G-set graphs, which are used as standard for comparing solver performance in the MAX-CUT problem. That is, we can evaluate maximum cut by the QNN machine and QNN simulator on G-set graphs with up to 2000 vertices. We use “rudy” to generate G-set graphs the same as with the MAX-CUT solver.

Ising Solver

Size

Indicates the number of vertices in the problem graph.

The allowable range is from 100 to 2000 vertices.

Density[%]

Indicates the edge density of the problem graph. Allowable range is from 0.5 to 50%.

Multiplying the total possible number of edges by edge density gives the number of edges for the problem graph.

Connectivity

Indicates the random-number seed value given to a random number generator when randomly assigning weight wij of each edge a value of “1” or “-1.”

If selecting Auto, the system sets an appropriate random-number seed value. You can check this value by opening the Comment column on the project list. If selecting Custom, you may set the random-number seed value to a number from 1 to 99999.

The same group of weighted edges can be obtained and an identical graph generated with the same random-number seed value.

G Set Number

Indicates the G-set number. A number from 1 to 54 (excluding 48 49, and 50) may be set.

The character string displayed constitutes options given to the graph-generation program “rudy.”

Download

The Jij matrix of the given problem. This is an NxN matrix for a N-size problem. Each Jij matrix has the relationship Jij = -Wij with the weight matrix wij.

Calculation results of 100 trials from the QNN machine. This is an Nx100 matrix for a N-size problem.

The base data of the cut-number histogram calculated using Jij(wij) and Row Results.

Details on the format of downloaded data and a user guide (Python Script) can be found here.

Problem Instance

Indicates a visual representation of the given problem graph. In cases other than a toroidal graph, the system places each vertex on a spherical surface in the form of a white circle and represents the weight {1, -1} of each edge by red and blue lines. In the case of a large number of vertices or edges, a fixed proportion of them will be omitted due to display limitations.

Machine's Result

Indicates a visual representation of the results of the QNN machine. In this representation, the system places a red or blue point corresponding to each vertex and its binary variable σi {1, -1} on a spherical surface and represents an edge between different-colored points (a cut edge) in green and all other edges in white. In the case of a large number of vertices or edges, a fixed proportion of them will be omitted due to display limitations.

Cut Histogram

Indicates a histogram display of the cut number using the calculation results of 100 trials from the QNN machine.

The BEST CUT is the maximum number of cuts from this set of 100 calculation results.

Edge Degree

Sum total of the weights of the edges stemming from the vertex

Weight Sum

Number of edges stemming from the vertex (degree distribution)

Average photon numbers in OPO cavities

Displays the temporal development of the number of photons in OPO cavities. The vertical axis represents the number of photons while the horizontal axis represents the number of OPO round trips.

The bar at the bottom shows the range of the number of round trips to be displayed. Sliding this bar changes the display range.

Measured values of OPO in-phase component

Indicates the approximate measured values of the OPO in-phase component using a homodyne detector.

Cut

The sign of the measured value of each OPO in-phase component determines the value of binary variable σi (1 or -1). The cut value of each round trip is calculated by the following equation.

Expectation values of In-phase component in OPO cavities

Displays the temporal development of expectation values of the in-phase component in OPO cavities.

Variances of In-phase component in OPO cavities

Displays the temporal development of variances of the in-phase component in OPO cavities.

Uncertainty relationship between in-phase and quadrature-phase components in OPO cavities

Displays a locus of amplitude variance using number of round trips as a parameter. The horizontal axis represents the variance of the amplitude’s in-phase component and the vertical axis the variance of the amplitude’s quadrature-phase component. The red line shows the minimum uncertainty product and the blue line the standard quantum limit (SQL).

Wavepacket expanded by the in-phase amplitude eigenstates

Displays the temporal development of the probability distribution for finding an OPO by in-phase amplitude X. The in-phase amplitude X on the vertical axis shifts such that amplitude X = 0 becomes the expectation value of the in-phase component in each round trip. The temporal development of the probability distribution P_r(X) of each OPO is evaluated on the basis of the following equation using several thousand Brownian particles having the same measured value in each round trip.

Here, P(α,β) is the positive P function.

We use cookies to understand how people visit and use our site and share content through it so we can improve everyone’s experience. By using our site, you agree to the use of these cookies. See our Site Policy to read more.

エラーのタイトル

エラーの詳細を説明するダイアログです。エラーの詳細を説明するダイアログです。エラーの詳細を説明するダイアログです。