EN JP
QNN-Machine
Available
Busy
Maintenance
QNN MACHINES
Max-Cut Solver

ここでは、最大カット問題(MAX-CUT problem)をQNN計算装置とQNNシミュレータを使って解くことができます。ここで体験できる最大カット問題は、頂点とそれら頂点を結ぶ枝の集まり(グラフ)が与えれた時に、頂点を二つのグループAとBに分け、カットと呼ばれる量が最大となる頂点の分割(A,B) を探し出す問題です。頂点iとjの間の枝には{1,0,-1}を取る重みwijが与えられ、(wij=0であれば枝が無いことに相当します)

カットは以下の式で与えられます。

分割された頂点の集まりAとBをまたぐ枝の重みwijを足し上げたものがカット数になります。各頂点にAグループであれば”1”、Bグループであれば”-1”となる二値変数σiを割り当てると右式のように書き直すことができます。 QNN計算装置とQNNシミュレータではOPOパルスが頂点に、OPOの各位相(0、π)が二値変数σi の(1,-1)にそれぞれ相当します。
QNN計算装置とQNNシミュレータは、二値変数σi をイジンスピンとみなした時のイジングエネルギーが最小になるイジンスピンの組み合わせを探し出します。カットとイジングエネルギーは以下の関係があり、イジングエネルギーが最小となるイジンスピンの組み合わせの時にカット数は最大値を取ります。

ここで、 Jij はi番目とj番目のイジングスピンの間の結合定数で、 Jij = -Wij の関係があります。

重み付グラフ(wij=wji)の生成には”rudy”を使っています。詳しくはこちら(リンク:https://web.stanford.edu/~yyye/yyye/Gset/)を参照してください。
体験可能なグラフの種類は、完全グラフ、ランダムグラフ、スケールフリーグラフ、トロイダルグラフの4種類です。

完全グラフ: 全ての枝に”1”か”-1”の重みがランダムに与えられている。
MaxCutSolver -
PROJECTS
Remaining --/100
Title
Comment
Size
Density
QNN
Date
Title
Comment
Gset
QNN
Date
MaxCutSolver -
Title
0/40
Comment
0/100
Size
× 10
=
Density[%]
Connectivity
-Random seed
Edge type
G Set Number

Gsetの内容

Problem Instance
Edge Degree

QNN-Machine

Machine's Result
Cut Histogram
[BEST CUT : ]
Max-Cut Solver

ここでは、最大カット問題(MAX-CUT problem)をQNN計算装置とQNNシミュレータを使って解くことができます。ここで体験できる最大カット問題は、頂点とそれら頂点を結ぶ枝の集まり(グラフ)が与えれた時に、頂点を二つのグループAとBに分け、カットと呼ばれる量が最大となる頂点の分割(A,B) を探し出す問題です。頂点iとjの間の枝には{1,0,-1}を取る重みwijが与えられ、(wij=0であれば枝が無いことに相当します)

カットは以下の式で与えられます。

分割された頂点の集まりAとBをまたぐ枝の重みwijを足し上げたものがカット数になります。各頂点にAグループであれば”1”、Bグループであれば”-1”となる二値変数σiを割り当てると右式のように書き直すことができます。 QNN計算装置とQNNシミュレータではOPOパルスが頂点に、OPOの各位相(0、π)が二値変数σi の(1,-1)にそれぞれ相当します。
QNN計算装置とQNNシミュレータは、二値変数σi をイジンスピンとみなした時のイジングエネルギーが最小になるイジンスピンの組み合わせを探し出します。カットとイジングエネルギーは以下の関係があり、イジングエネルギーが最小となるイジンスピンの組み合わせの時にカット数は最大値を取ります。

ここで、 Jij はi番目とj番目のイジングスピンの間の結合定数で、 Jij = -Wij の関係があります。

重み付グラフ(wij=wji)の生成には”rudy”を使っています。詳しくはこちら(リンク:https://web.stanford.edu/~yyye/yyye/Gset/)を参照してください。
体験可能なグラフの種類は、完全グラフ、ランダムグラフ、スケールフリーグラフ、トロイダルグラフの4種類です。

完全グラフ: 全ての枝に”1”か”-1”の重みがランダムに与えられている。
Measurement

ここでは、最大カット問題においてソルバーの性能比較を行うために標準的に用いられているG-setグラフを使うことができます。頂点数が2000までのG-setグラフ上で最大カットをQNN計算装置とQNNシミュレータで評価できます。G-setグラフの生成にはMAC-CUT SOLVERと同様に”rudy”を使っています。

Ising Solver

Size

与える問題グラフの頂点数。
設定範囲は、100から2000まで。

Density[%]

与える問題グラフの各頂点から出ている辺の密度。
頂点数がN、各頂点から出ている辺の平均数がkの場合、密度はk/(N-1)。

Connectivity

各枝の重みwijにランダムに1か-1を与える時に使う乱数生成器に与える乱数シード値。

Auto選択時は、システムが適当な乱数シード値を設定する。プロジェクトリストでComment欄をOpenすれば乱数シード値を確認できる。Custom選択時の設定範囲は、1から99999まで。

乱数シード値が同じであれば全く同じ重みの枝の集まりが与えられ同一グラフを生成できる。

G Set Number

G-setの番号、設定可能範囲は 1から54 まで(48,49,50を除く)。
表示されている文字列はグラフ生成プログラム”rudy”に与えるオプション。

ダウンロード

Jij:

与えられた問題のJijマトリクス。サイズがNの問題ではNxNの行列。各Jijマトリクスは重みの行列wijとJij = - Wijの関係がある。

Row Results:

QNN計算装置からの100回分の計算結果。サイズNの問題の場合はNx100の行列。

Histogram:

カット数ヒストグラムの元データ。Jij(wij)とRow Resultsを用いて計算したもの。

ダウンロードデータの形式・利用ガイド(Python Script)についてはこちら。

Problem Instance

与える問題グラフを視覚的に表現したもの。トロイダルグラフ以外では、各頂点を白丸で球面上に配置し、各枝の重み{1,-1}を赤と青の線で表している。表示上の制約上、頂点数または枝が多い場合は、一定の割合で間引いている。

Machine's Result

QNN計算装置の結果を視覚的に表現したもの。各頂点での二値変数σiの値{1,-1}に応じて赤、青の点を球面上に配置し、異なる色の間の枝(カットされている枝) を緑で、それ以外の枝は白で表している。表示上の制約上、頂点数または枝が多い場合は、一定の割合で間引いている。

Cut Histogram

QNN計算装置からの100回分の計算結果使ってカット数を計算しヒストグラム表示したもの。

BEST CUTは100回の計算結果の中での最大のカット数。

Edge Degree

各頂点での頂点から出ている枝数(次数分布)の値をヒストグラム表示したもの。

Weight Sum

各頂点での頂点から出ている枝の重みの総和の値をヒストグラム表示したもの。

OPO共振器内の平均光子数

OPO共振器中の光子数の時間発展。縦軸は光子数、横軸はOPOの周回数。
下部バーは表示する周回数の範囲を示しており、スライドさせて表示領域を変えることができる。

OPO同位相成分の測定値

ホモダイン検出器によるOPOの同位相成分の近似測定値。

カット

各OPO同位相成分の測定値の符号に応じて二値変数σiの値を1,か-1に決め、各周回でカット値を以下の式で計算したもの。

OPO共振器中の同位相成分の期待値

OPOの同位相成分の共振器中の期待値の時間発展。

OPO共振器中の同位相成分の分散

OPOの同位相成分の共振器中の分散の時間発展。

OPOの同位相と直交位相成分間の不確定性関係

周回数をパラメータとした振幅の分散の軌跡。横軸に振幅の同位相成分の分散、縦軸に振幅の直交位相成分の分散を表示したもの。赤線は最小不確定性積を示す。青線は標準量子限界(SQL)を示している。

同位相振幅基底での波束

OPOを同位相振幅Xで見出したヒストグラム。縦軸の同位相振幅は、振幅0がそれぞれの周回での同位相成分の期待値となるようにシフトしてある。

より良い利用者体験へと改善していくために我々はCookieを使用します。本サイトを利用することで、Cookie使用に同意することとなります。詳しくはサイトポリシーをご覧ください。