JP7182173B2 - 変数埋込方法及び処理システム - Google Patents

Description

本発明は、ハードウェアグラフへの変数埋込方法及び処理システムに関する。

従来より、出願人は、複数の変数を組合せて構成される評価関数の大域的な最適値を探索する最適化問題を高速に解く手法を開発している。このような組合せ最適化問題を高速に解くため、専用のハードウェアが一般に開発されている。
このハードウェアは特定の固定アーキテクチャを備えており、通常の汎用コンピュータよりも組合せ最適化問題を高速に解くことができる。この種のハードウェアは特定の固定アーキテクチャを備えているため、組合せ最適化問題を解くために幾つか制約を生じる。第１制約は、一度に処理可能な変数の絶対数に限度があることである。また第２制約は、当該変数間の相互作用数に限度があることである。専用のハードウェアを用いて最適化問題を効率的に処理するためには、このような制約条件下にて処理を実行することが求められる。

前記の第１制約に対応するため、特許文献１記載の技術は、最適化問題の変数をハードウェアグラフに埋込むことが可能な部分問題に分割し、部分問題の最適化処理を繰り返すことで元の最適化問題の高精度解を取得しようとしている。しかしながら、ハードウェアグラフに可能な限り多くの変数を埋込むための具体的な方法は示されていない。与えられた最適化問題の変数をハードウェアグラフに埋め込むための具体的な方法は、特許文献２に挙げられている。

特許文献２記載の技術は、解きたい問題グラフとハードウェアグラフとを参照し当該ハードウェアグラフの各頂点に対し変数を埋込んでいる。この特許文献２記載の変数の埋込処理は前半と後半に分かれている。前半では、ハードウェアグラフの頂点に複数の変数を重複して割り当てることを許容しつつ与えられた問題の全変数を埋込んでいる。またその後半においては、一つの変数だけが、ハードウェアグラフの上の各頂点に割り当てられるようにしている。その他、非特許文献１も参考文献として挙げることができる。

米国公開２０１７－２５５６２９号明細書 米国特許９５０１７４７号明細書

奥山等，「イジング計算機に向けたグラフ埋め込みアルゴリズム」，一般社団法人電子情報通信学会，vol.116，no.116，IEICE Technical Report，COMP2016-11，pp.97-103，２０１６年６月

発明者は、背景技術欄に記載された特許文献２記載の技術を採用すると、特に後半の処理において多くの処理時間を要することを確認している。この特許文献２記載の技術は、前半において一旦重複を許容して埋込みしているため、後半にてその修正を図る必要があるためである。したがって、これらの全ての処理を完了するために多大な時間を要してしまう。特に、特許文献１記載の技術のように、大規模な問題を部分問題に分割しながらハードウェアグラフに繰り返し埋込む必要がある場合には、１回当たりの処理時間を短縮することが全体の処理時間を短縮するために重要である。
本発明の目的は、処理時間を短縮できるようにしたハードウェアグラフへの変数埋込方法及び処理システムを提供することにある。

請求項１、１３に記載した発明によれば、全ての変数のうち少なくとも一部を前記ハードウェアグラフの頂点に埋込むときに、最適化問題の変数をハードウェアグラフの頂点へ重複割当を必要とするか否かを判定し、重複割当を必要とする変数については部分問題の変数として用いることなく、重複割当の不要な変数を選択してハードウェアグラフの頂点に埋込んでいる。このため、重複割当の解消処理に時間を割く必要なく処理できるようになり、処理時間を短縮できるようになる。
例えば、重複割当を必要とするか否かの判断処理は、ハードウェアグラフの上で変数が割当てられていない頂点を始点とし、追加で埋め込みたい変数に隣接する埋込済変数に割当てられた頂点を終点とする経路を、未使用頂点のみを用いてハードウェアグラフ上で構成可能であるかを確認すれば良い。
例えば、上記の経路が存在する場合は、経路上の各頂点に対して追加で埋込みたい変数又は結合した埋込済変数を適切に埋め込むことで、問題グラフにおける変数間の相互作用を再現しながら、ハードウェアグラフに変数を埋込むことができる。この経路は可能な限り短い方が利用するハードウェアグラフ上の頂点数が少なくて済むため、ダイクストラ法等を用いて最短経路を求める方法が考えられる。

第１実施形態における電気的構成図 機能的構成図 最適化問題から部分問題への分割イメージ図 最適化問題の解導出処理を示すフローチャート 変数埋込処理を示すフローチャート ハードウェアグラフへの変数埋込処理の説明図（その１） ハードウェアグラフへの変数埋込処理の説明図（その２） 第２実施形態における完全グラフのハードウェアグラフへの埋込方法の説明図 ハードウェアグラフへの変数埋込処理の説明図（その３） ハードウェアグラフの頂点の予約処理を示すフローチャート キメラグラフにおける頂点の予約処理の説明図（その１） キメラグラフにおける頂点の予約処理の説明図（その２） キメラグラフにおける頂点の予約処理の説明図（その３） キメラグラフにおける頂点の予約処理の説明図（その４） 第３実施形態の最適化問題の解導出処理を示すフローチャート 問題グラフの内容説明図 問題グラフにおける埋込順序の説明図 第４実施形態において二値変数を用いて表現した多値問題の問題グラフ 二値変数を選択する選択方法の説明図（その１） 二値変数を選択する選択方法の説明図（その２） 多値変数の埋込処理を示すフローチャート 二値変数の選択優先順位を示す説明図 第５実施形態において２択最適化問題への変換処理を示すフローチャート ２択最適化問題への変換処理の内容説明図

以下、本発明の変数埋込方法及び処理システムの幾つかの実施形態について図面を参照して説明する。以下の実施形態中では、各実施形態間で同一機能又は類似機能を備えた部分に同一符号を付して説明を行い、同一又は類似機能を備えた構成及びその作用、連携動作説明等を必要に応じて省略する。

（第１実施形態）
図１Ａから図６は、第１実施形態の説明図を示している。図１Ａに示す量子イジングマシン１は、機能特化型のイジング型ハードウェア２を用いて構成され、複数の変数Ｘの間の相互作用をハードウェアの物理的な制約として構成し、物質の量子力学的な性質を利用して最適化問題と同じ状況を疑似的に再現してシミュレーションを実行するように構成されている。

イジング型ハードウェア２は、特定の固定アーキテクチャにより構成された専用ハードウェアとなる量子プロセッサにより構成されている。このイジング型ハードウェア２は、その仮想ハードウェア上に多数配列状に頂点Ｖ（Ｖ１～Ｖ９）を備え、仮想ハードウェアの頂点Ｖ（Ｖ１～Ｖ９）の間の相互作用に制約を有するようなハードウェアグラフＧ２により表すことが可能である。以下の説明において、これらの多数の頂点Ｖの一部を特定するときには、必要に応じて頂点Ｖに添え数字を付して説明を行う。また、多数の頂点Ｖの一部又は全部を総じて頂点Ｖと称することもある。

これらの頂点Ｖの間の相互作用の制約は、例えば図１Ａに示すように、縦横に隣接する頂点Ｖの間（例えばＶ１－Ｖ２間、Ｖ２－Ｖ３間、Ｖ１－Ｖ４間…）だけ結合し、これ以外の頂点Ｖの間は、非結合となるように構成する例を挙げることができる。

また、互いに全結合又は一部の相互作用を制約するように結合した複数の頂点Ｖを備えた単位セルＣを構成し、これらの単位セルＣを複数グリッド分だけ備えたハードウェアグラフＧ２を適用し、この場合、隣接するグリッド間において頂点Ｖの結合に制約を備えるように構成しても良い。

単位セルＣを複数グリッド分だけ備えたハードウェアグラフＧ２の代表例として、キメラグラフと称されるハードウェアグラフＧ２がある（図５の右側、図９、図１０等参照）。このキメラグラフは、例えば縦横方向（第１方向、第２方向相当）にｎ×ｍの頂点Ｖを備えた単位セルＣ（例えばＣ１１、Ｃ１２、Ｃ２１、Ｃ２２）を備え、この単位セルＣが、縦横方向に複数のグリッド備えられるハードウェアグラフＧ２である。以下の説明において、これらの単位セルＣの一部を特定するときには、必要に応じて単位セルＣに添え数字を付して説明を行う。また単位セルＣの一部又は全部を総じて単位セルＣと称することもある。

このキメラグラフは、図５の右側に示すように、各単位セルＣの第１列の各頂点Ｖ１１～Ｖ１４が第２列の各頂点Ｖ２１～Ｖ２４との間で互いに結合されており、各単位セルＣを構成する頂点Ｖが、他の縦横方向に連続して隣接した単位セルＣの対応した頂点Ｖに結合されることで構成されている。このキメラグラフは、前述した以外の他部分が非結合となる制約を備えるハードウェアグラフＧ２である。図５の右側に示すキメラグラフの結合関係を詳述する。キメラグラフは、第１列の複数の頂点Ｖ１１～Ｖ１４がそれぞれ第２列の複数の頂点Ｖ２１～Ｖ２４と結合し、第１列の複数の頂点Ｖ１１～Ｖ１４が互いに非結合であると共に、第２列の複数の頂点Ｖ２１～Ｖ２４が互いに非結合である単位セルＣ１１…Ｃ２２を縦横方向に沿って複数グリッド分だけ備えている。またこのとき、単位セルＣ１１、Ｃ１２の第１列の頂点Ｖ１１～Ｖ１４が縦方向に沿ってそれぞれ結合すると共に、単位セルＣ１１、Ｃ２１の第２列の頂点Ｖ２１～Ｖ２４が横方向に沿ってそれぞれ結合している。

図１Ａに示すコンピュータ３は変数埋込装置を構成するものであり、この量子イジングマシン１のイジング型ハードウェア２に適合した形態に変数Ｘを埋込むための機能を備えた装置である。このコンピュータ３は、ＣＰＵ４と、ＲＯＭ、ＲＡＭ等のメモリ５と、入出力インタフェース６とをバス接続した汎用コンピュータを用いて構成される。メモリ５は非遷移的実体的記録媒体として用いられる。このコンピュータ３は、ＣＰＵ４によりメモリ５に記憶された変数埋込用のプログラムを実行し、各種手順を実行することで最適な変数Ｘの埋込方法を探索し、量子イジングマシン１のイジング型ハードウェア２に変数Ｘを埋込む。

量子イジングマシン１により実行される最適化処理は、１以上のｎ次元を備えたユークリッド空間からなる探索空間を想定し、この探索空間の中で、複数の要求や制約によって生成された評価関数Ｈの最小値、又は、評価関数Ｈが最小値となる条件を満たす変数Ｘ、すなわち最適解を求める処理を示す。評価関数Ｈは、複数の要求や制約によって生成され、１以上のｎ個の変数Ｘに基づいて導出される数式による関数を示すものであり、例えば任意の多項式、有理関数、無理関数、指数関数、対数関数やその加減乗除等による組み合わせなどを挙げることができる。以下、ｎ次元問題における各変数をＸ１、Ｘ２…Ｘｎと示し、必要に応じて、これらの変数の一部又は各変数を総称して変数Ｘと称する。図１Ｂに示すように、コンピュータ３は、メモリ５に記憶されたプログラムを実行することで実現する機能として、判定部７及び埋込部８などの各種機能を備える。

図２は、評価関数Ｈの最適化問題の大規模問題（原問題）を部分問題に分けるイメージを示しており、図３は、コンピュータ３及び量子イジングマシン１により実行される最適化問題の一連の解導出方法をフローチャートにより示している。

図３に示すように、コンピュータ３は問題グラフＧ１を入力する（Ｓ１）。この問題グラフＧ１は、コンピュータ３が評価関数Ｈを解析した結果、評価関数Ｈに対する要求や制約により求められた各変数Ｘの相互作用の関係性を表している。この問題グラフＧ１の一例を図５の左側に示している。この問題グラフＧ１は、変数Ｘ１が変数Ｘ２～Ｘ９に結合する例を示し、他の変数Ｘ２～Ｘ９は互いに非結合である例を示している。

この後、コンピュータ３は問題グラフＧ１を構成する変数Ｘをイジング型ハードウェア２のハードウェアグラフＧ２に埋込む（Ｓ２）。同一の変数Ｘに対応した頂点Ｖは、ハードウェアグラフＧ２の上で連結した部分グラフを構成しなければならない。しかも、問題グラフＧ１にて結合する変数Ｘは、ハードウェアグラフＧ２の上では少なくとも一つ以上の結合を備えていなければならない。このルールを満たしていないと、量子イジングマシン１の上で適切に処理させることができない。このためコンピュータ３は、変数Ｘの埋込処理を適切に行うことが求められる。

図４に変数Ｘの埋込処理のフローチャートを示している。コンピュータ３が、量子イジングマシン１のハードウェアグラフＧ２に変数Ｘを埋込むときには、変数Ｘを選択して仮にハードウェアグラフＧ２に埋め込んだときに重複割当を生じるか否かを判定し（Ｓ１２）、重複割当を生じないときにはハードウェアグラフＧ２に変数Ｘを埋込み（Ｓ１３）、重複割当を生じるときにはハードウェアグラフＧ２に変数Ｘを埋込まない（Ｓ１４）。そして、終了条件を満たすまでＳ１１～Ｓ１４の処理を繰り返す。終了条件は、未埋込の変数Ｘがなくなったり、これらの処理Ｓ１１～Ｓ１４を予め定められた上限回数まで繰り返した結果、変数Ｘを追加で埋込み不能と判断することなどである。

例えば、図５には、コンピュータ３が問題グラフＧ１の変数Ｘを量子イジングマシン１のハードウェアグラフＧ２に埋込むときの例を示している。ハードウェアグラフＧ２は、図５の右側に示すように前述説明したキメラグラフを用いている。

このとき、コンピュータ３は、変数Ｘ１～Ｘ９をランダムで選択し、選択された変数Ｘから順にハードウェアグラフＧ２に変数Ｘを埋込む。実際には、変数Ｘ１～Ｘ９をランダムに選択して埋込むことになるが、ここでは、説明を理解しやすくするため、変数Ｘ１から変数Ｘ９を順に埋込むときの例を示す。
このとき、コンピュータ３は変数Ｘ１を埋め込んだ後、変数Ｘ２～Ｘ９を埋込む。前述したように、変数Ｘ２～Ｘ９は全て変数Ｘ１と結合する必要がある。このため、変数Ｘ７～Ｘ９より先に選択される変数Ｘ２～Ｘ６は、変数Ｘ１に結合した頂点Ｖに埋込まれることになる（図５の右側参照）。ここで変数Ｘ７～Ｘ９は、変数Ｘ２～Ｘ６が埋込まれた頂点Ｖに重複割当しなければ変数Ｘ１と結合できなくなるため、Ｓ１５において終了条件を満たしたと判定し、変数Ｘ７～Ｘ９を埋込むことなく終了する。

そして、変数Ｘの埋込処理を終了すると、量子イジングマシン１が、図３の処理に移行して最適化処理を実行する（Ｓ３）。量子イジングマシン１は、最適化処理において変数Ｘ１～Ｘ６を部分変数として評価関数Ｈに代入し、勾配法やその他の最適化手法を用いて評価関数Ｈが所定より低い条件（最適化条件）を満たすように変数Ｘ１～Ｘ６の値を求める（部分問題の解導出処理）。このとき、量子イジングマシン１は、処理を開始してから所定時間経過したり所定以上の試行回数繰り返したことを条件として変数Ｘ１～Ｘ６の最適値を決定し、変数Ｘ１～Ｘ６を更新する（Ｓ４）。この場合、他の変数Ｘ７～Ｘ９としては、固定値を用いて評価関数Ｈの評価値を求めると良い。これにより部分問題を解くことができる。

その後、Ｓ２に処理を戻し、コンピュータ３は、Ｓ２において変数Ｘを再度ランダムに選択し当該選択された変数ＸをハードウェアグラフＧ２に埋込み、量子イジングマシン１がこれらの変数Ｘによる最適化処理を実行し、当該変数Ｘの組合せの最適値を決定し、Ｓ４においてこれらの変数Ｘを更新する。なお、このとき選択されなかった変数Ｘは、当該処理以前に最適値として求められた変数Ｘ（ここでは、変数Ｘ１～Ｘ６）の最適値を用いると良い。一度も選択されていない変数Ｘは、固定値に設定して処理すると良い。そして、量子イジングマシン１は、処理を開始してから所定時間経過したり又は所定以上の試行回数繰り返したことを条件として終了条件を満たしたと判定し（Ｓ５でＹＥＳ）、この変数Ｘの結果又は評価関数Ｈの評価値などを出力する。これにより、全体の最適化問題を解くことができる。このように繰返し処理を行うことで、図２にイメージを示すように、原問題を部分問題に分割して解くことができる。

以上説明したように、本実施形態によれば、全ての変数Ｘのうち一部をハードウェアグラフＧ２の頂点Ｖに埋込むときに、最適化問題の変数ＸをハードウェアグラフＧ２の頂点Ｖへ重複割当を必要とするか否かを判定し（Ｓ１２）、重複割当を必要とする変数Ｘ７～Ｘ９については部分問題の変数Ｘ７～Ｘ９として用いることなく、重複割当の不要な変数Ｘ１～Ｘ６を選択してハードウェアグラフＧ２の頂点Ｖに埋込んでいる。したがって、ハードウェアグラフＧ２の頂点Ｖに全ての変数Ｘを埋込不可能な大規模な最適化問題について、当該最適化問題の変数Ｘの相互関係を問題グラフＧ１に表して当該大規模な最適化問題を解く場合、問題グラフＧ１の変数Ｘ１～Ｘ９をハードウェアグラフＧ２に埋込むことが可能な部分問題に分割し、部分問題の最適化処理を繰り返すことで大規模な最適化問題を解くことができる。
なお、図５には、説明を簡単化するため問題グラフＧ１の変数Ｘを９個とした例を示した。このため、ハードウェアグラフＧ２の上の頂点Ｖを一部しか利用できていない。しかし実際には、変数Ｘが多数存在する大規模な問題を解くときに、コンピュータ３が上記の埋込処理を実行するため、ハードウェアグラフＧ２の上の頂点Ｖをより多く利用でき、より大きな部分問題の変数Ｘを埋込み可能であることに留意する。

＜比較例＞
図６は、例えば特許文献２記載の技術を適用し、重複割当を許容した場合の比較例を示している。このようなとき、変数Ｘ１を埋込済の単位セルＣ１１の頂点Ｖ１１に結合した頂点Ｖは５つしかないため変数Ｘ２～Ｘ６を重複割当なくハードウェアグラフＧ２に埋込むことができる。しかし、変数Ｘ７～Ｘ９が頂点Ｖ２１～Ｖ２３に重複割当して埋込まれることになる。このような処理を適用すると、この重複割当を解消しながら最適値を算出するため、多大な時間を必要としてしまう。

＜本実施形態のまとめ、効果＞
本実施形態によれば、コンピュータ３は、変数Ｘの埋込処理を行うときに、重複割当を必要とするか否かを判定し（Ｓ１２）、重複割当を必要とする変数Ｘ７～Ｘ９を部分問題の変数Ｘとして用いることなく、重複割当の不要な変数Ｘ１～Ｘ６を選択してハードウェアグラフＧ２の頂点Ｖに埋込んでいる。このため、従来技術に示されるような重複割当を許容することなく処理できるようになり、重複割当の解消処理を一切行う必要がなくなり、処理時間を大幅に短縮できる。

（第２実施形態）
図７から図１０は、第２実施形態の追加説明図を示している。本実施形態では、コンピュータ３はメモリ５に記憶されたプログラムを実行することで予約部、選択部、禁止部、紐付け部、解消部として機能する。第１実施形態の方法によれば、問題グラフＧ１の結合数が比較的小さければ、重複割当が不要な変数Ｘだけを用いて、ハードウェアグラフＧ２の上に大きな部分問題を構成する変数Ｘを埋込むことが可能である。しかし、図５に示すように、多くの変数Ｘ２～Ｘ９と結合する変数Ｘ１が、問題グラフＧ１の中に多数存在するような場合には、ハードウェアグラフＧ２の上の頂点Ｖを使い切る前に部分問題の成長が止まってしまう。

コンピュータ３は、各変数ＸをハードウェアグラフＧ２の上に埋込むときに、各変数Ｘに割当てられたハードウェアグラフＧ２の上の部分グラフに含まれる頂点Ｖの中から少なくとも一つを選択し、選択した頂点ＶとハードウェアグラフＧ２の上で結合すると共に、ハードウェアグラフＧ２の上において他の変数Ｘとの結合数を効率的に増加させることができる方向に辿る頂点Ｖに対して該当変数Ｘ以外の変数Ｘの埋込みを禁止し、ハードウェアグラフＧ２の上で該当変数Ｘの連結した部分グラフを伸ばすことができる余地を残すことが望ましい。以降、この操作を「予約」と呼ぶ。
図８は、ハードウェアグラフＧ２の上の頂点Ｖの埋込処理のフローチャートを示している。図８に示すように、まずコンピュータ３は、完全グラフＧ１ａの変数ＸをハードウェアグラフＧ２への埋込方法を用いて（参考にして）予約方法(紐付方法）を設定する（Ｓ２１）。

具体的な予約方法、所謂紐付方法は、ハードウェアグラフＧ２の種類により異なる。問題グラフＧ１として想定される中で最も結合数が多い完全グラフＧ１ａ（図７Ａ参照）の変数ＸをハードウェアグラフＧ２に埋込む方法を用いる（すなわち参考にする）ことが望ましい。

図７Ａには、この予約方法の設定処理を理解し易くするため、完全グラフＧ１ａをハードウェアグラフＧ２（キメラグラフ）に埋込む一般的な方法を示しており、太線にて結合するグラフは各変数に割当てられた連結した部分グラフを表している。完全グラフＧ１ａの変数Ｘ１～Ｘ４は、単位セルＣ１１の頂点Ｖ２１～Ｖ２４を含む部分グラフに埋込まれる。変数Ｘ５～Ｘ８は、単位セルＣ２２の頂点Ｖ２１～Ｖ２４を含む部分グラフに埋込まれる。変数Ｘ９～Ｘ１２は、単位セルＣ３３の頂点Ｖ２１～Ｖ２４を含む部分グラフに埋め込まれる。
図７Ａに示すように、ハードウェアグラフＧ２の上で連結した部分グラフ（図７Ａ中の太線にて結合するグラフ）は単位セルＣの間を縦方向と横方向とに結合した構造となる。コンピュータ３は、この変数Ｘ１～Ｘ１２の埋込方法を用いて（参考にして）、Ｓ２１において単位セルＣの間を跨ぐ方向に辿った各頂点Ｖに紐付ける。言い換えると、コンピュータ３は、Ｓ２１においてある頂点Ｖに対応して縦方向又は／及び横方向の単位セルＣに含まれる頂点Ｖに紐付ける。

図７Ａの右図中に付した単位セルＣ１１の頂点Ｖ２１（変数Ｘ１の埋込頂点Ｖ）について、ハードウェアグラフＧ２へ紐付ける各単位セルＣの頂点Ｖ１１、Ｖ２１に符号を付すと共に、図７Ａの右図中に付した頂点Ｖ２２（変数Ｘ６の埋込頂点Ｖ）についてハードウェアグラフＧ２へ紐付ける各単位セルＣの頂点Ｖ１２、Ｖ２２に符号を付している。

コンピュータ３が、ハードウェアグラフＧ２の上で単位セルＣ１１の頂点Ｖ２１に対応して、単位セルＣ１１、Ｃ１２、Ｃ１３…の頂点Ｖ１１に紐付けると共に、単位セルＣ２１、Ｃ３１…の頂点Ｖ２１に紐付ける。またコンピュータ３は、ハードウェアグラフＧ２の上で単位セルＣ２２の頂点Ｖ２２に対応して、単位セルＣ２２、Ｃ２３…の頂点Ｖ１２に紐付けると共に、単位セルＣ３１、Ｃ４１…の頂点Ｖ２２に紐付ける。

さらにコンピュータ３は、このような完全グラフＧ１ａの変数ＸのハードウェアグラフＧ２への埋込方法を用いて（参考にして）、その埋込方法の一部を用いて頂点Ｖを紐付けるようにしても良い。この例を図９Ａ、図９Ｂ、図１０Ａ、図１０Ｂに示している。これらの図９Ａ～図１０Ｂは、２×４の頂点Ｖを結合した単位セルＣを４×４の複数グリッド分だけ備えたキメラグラフをハードウェアグラフＧ２として示しており、ハードウェアグラフＧ２の上における頂点Ｖの間を紐付ける例を示している。また図９Ａ、図９Ｂは、縦方向に跨ぐ方向に辿った頂点Ｖに紐付ける例を示しており、図１０Ａ、図１０Ｂは、横方向に跨ぐ方向に辿った頂点Ｖに紐付ける例を示している。

図９Ａに示すように、コンピュータ３は、基点として選択した単位セルＣ１１の頂点Ｖ１１（第１頂点相当）に対応して、隣接する方向（この場合、縦方向）に連続結合した単位セルＣ１２、Ｃ１３、Ｃ１４…の各頂点Ｖ１１（第２頂点相当）を紐付けても良いし、図９Ｂに示すように、コンピュータ３は、基点として選択した単位セルＣ３３の頂点Ｖ１３（第１頂点相当）に対応して、隣接する方向（この場合、縦方向）に連続結合した単位セルＣ３１、Ｃ３２、Ｃ３４の頂点Ｖ１３（第２頂点相当）に紐付けても良い。

また図１０Ａに示すように、コンピュータ３は、基点として選択した単位セルＣ１１の頂点Ｖ２１（第１頂点相当）に対応して、隣接する横方向に連続結合した単位セルＣ２１、Ｃ３１、Ｃ４１の各頂点Ｖ２１（第２頂点相当）に紐付けても良いし、図１０Ｂに示すように、コンピュータ３は、基点として選択した単位セルＣ２３の頂点Ｖ２２（第２頂点相当）に対応して、隣接する横方向に連続結合した単位セルＣ１３、Ｃ３３、Ｃ４３の各頂点Ｖ２２（第２頂点相当）に紐付けても良い。

すると、コンピュータ３が変数Ｘを選択し（図８のＳ２２）、重複割当を必要とするか否かを判定し（Ｓ２３）、重複割当を必要とする場合には変数Ｘを埋め込まない（Ｓ２４）が、重複割当を必要としないときに変数Ｘを埋め込んだ（Ｓ２５）としても、その後、変数Ｘを埋め込んだ頂点Ｖの中から一つ以上を選択し（Ｓ２６）、選択した頂点Ｖを基点として他の頂点Ｖを予約することになる（Ｓ２７）。そして、コンピュータ３は予約された頂点Ｖへの埋込禁止を解除（解消）するか否かを判定し（Ｓ２８）、予約解除するのであれば予約解除（解消）し（Ｓ２９）、終了条件を満たしたか否かを判定し（Ｓ３０）、条件を満たしていなければＳ２２に処理を戻して再度変数Ｘを選択してＳ２３～Ｓ３０の処理を実行する。

例えば、問題グラフＧ１が図７Ｂの左側の構成であった場合、コンピュータ３が、例えばハードウェアグラフＧ２の上の単位セルＣ１１の頂点Ｖ１１に変数Ｘ１を埋込むと、例えば、Ｓ２１において図９Ａに示すように各単位セルＣ１２、Ｃ１３、Ｃ１４の頂点Ｖ１１が紐付けられていたときには、単位セルＣ１１の頂点Ｖ１１に対し縦方向に隣接して連続結合した単位セルＣ１２、Ｃ１３、…の各頂点Ｖ１１（第２頂点相当）を変数Ｘ１の埋込用として予約できる（Ｓ２６～Ｓ２７）。

このため、例えば図７Ｂの右側に示すように、ハードウェアグラフＧ２の上で、単位セルＣ１１の頂点Ｖ１１が変数Ｘ１により埋込まれると、単位セルＣ１２の頂点Ｖ１１が変数Ｘ１用に予約、確保されることになる。このとき、変数Ｘ２～Ｘ９が全て埋め込まれるまで、単位セルＣ１２の頂点Ｖ１１には変数Ｘ１しか埋込みが許されない。
この後、コンピュータ３が、変数Ｘ１の埋込処理の後に例えば変数Ｘ２～Ｘ９をこの順に選択してハードウェアグラフＧ２の頂点Ｖに埋込むときには、図７Ｂの右側に示すように、単位セルＣ１１の頂点Ｖ１１に結合した頂点Ｖ２１～Ｖ２４に変数Ｘ２～Ｘ５を順に埋込む。

次に、コンピュータ３がハードウェアグラフＧ２に変数Ｘ６を埋込むときには、単位セルＣ１２の頂点Ｖ１１は変数Ｘ１用に予約されており、変数Ｘ６を単位セルＣ１２の頂点Ｖ１１に埋込むことが禁止されている。このため、コンピュータ３は、単位セルＣ１２の頂点Ｖ１１に変数Ｘ１を埋込むと共に、変数Ｘ６を単位セルＣ１２の頂点Ｖ２１に埋込む。これにより、変数Ｘ１が単位セルＣ１２の頂点Ｖ１１に埋込まれることにより、変数Ｘ１と結合可能な変数Ｘを増やすことができ、変数Ｘ７～Ｘ９を単位セルＣ１２の頂点Ｖ２２～Ｖ２４にそれぞれ埋込むことができる。

以上示したように、ハードウェアグラフＧ２の上の部分グラフを伸ばす余地を残しながら変数Ｘを埋込むことで、重複割当をしなくても変数Ｘ１～Ｘ９を埋込むことが可能となる。今回の例では、変数Ｘ１の予約のみに着目したが、変数Ｘ２～Ｘ９を追加で埋込むときには、Ｓ２５～Ｓ２７において全ての変数Ｘに対して頂点Ｖの予約を実行する。そして、コンピュータ３は予約を解除すべきときに該当変数Ｘの予約を解除すると良い（Ｓ２８～Ｓ２９）。この結果、結合数が多い問題グラフＧ１でも部分問題を効率的に成長させることが可能となる。

その後、図８には示していないが、図３のＳ３と同様に量子イジングマシン１が最適化処理を実行することで、これらの全変数Ｘ１～Ｘ９の最適値を素早く的確に求めることができる。本実施形態では説明を簡単化するため、９つの変数Ｘ１～Ｘ９を用いて説明した。このため、１ルーチンの埋込処理にて全変数Ｘ１～Ｘ９をハードウェアグラフＧ２に埋込可能な簡単な例を示したが、実際にはより多数の変数Ｘを用いて最適化問題の大規模問題（原問題）を解くことになる。

このとき、第１実施形態でも説明したように、多数の変数Ｘのうち一回の埋込処理において一部の変数Ｘを埋込んで部分問題を解くことになる。このような場合においても、本実施形態で説明した埋込方法を適用すれば、前述の第１実施形態に比較してより多くの変数Ｘを頂点Ｖに埋込むことができる。このため、ハードウェアリソースを有効活用できるようになり、最適値の計算時間を短縮できる。

＜本実施形態のまとめ、効果＞
以上説明したように、本実施形態によれば、完全グラフＧ１ａをハードウェアグラフＧ２に埋込むときの埋込方法に基づいてハードウェアグラフＧ２の頂点Ｖを紐付け（予約方法を設定し）ておき（Ｓ２１）、ハードウェアグラフＧ２上の頂点Ｖから部分グラフにより連結された少なくとも一つ以上の頂点Ｖを選択し（Ｓ２６）、ハードウェアグラフＧ２に各変数Ｘを埋込むときにこの紐付けの内容（予約方法）に基づいて、選択した単位セルＣ１１の頂点Ｖ１１から結合し且つその他の変数Ｘ２～Ｘ９との結合を増加させる単位セルＣ１２の頂点Ｖ１１を、Ｓ２５にて埋込む変数Ｘ１に対応して予約することで当該埋込む変数Ｘ１以外のその他の変数Ｘ２～Ｘ９の埋込みを禁止する（Ｓ２７）ようにしている。

このため、ハードウェアグラフＧ２上において変数Ｘの結合を伸長する余地が生まれる。また、紐付けられる頂点Ｖは、問題グラフＧ１の中で最も結合濃度が濃い完全グラフＧ１ａの埋込方法に基づいて予め定められるため、たとえ最適化問題の原問題が、結合濃度の高い問題であっても、部分問題を拡大、成長させることが可能となる。このため、部分問題を繰り返し解いて全体の大規模問題（原問題）を解くときに、第１実施形態の方法に比較しても一回の部分問題を解く際に変数Ｘをより多く頂点Ｖに埋込むことができ、原問題を解くための時間を削減できる。ハードウェアグラフＧ２としてキメラグラフを適用した例を示したが、他の構造のハードウェアグラフＧ２を用いても良く、紐付ける頂点Ｖは、各ハードウェアグラフＧ２に完全グラフＧ１ａを埋込む方法に基づいて決定すれば良い。

（第３実施形態）
図１１から図１３は、第３実施形態の追加説明図を示している。本実施形態においては、コンピュータ３が、評価関数Ｈの変数Ｘの相互関係を導出した結果、図１２に示すように、問題グラフＧ１における変数Ｘが格子状に互いに結合していることを想定して説明する。
またコンピュータ３及び量子イジングマシン１は、第１実施形態の変数Ｘの埋込処理、及び、第２実施形態にて説明したハードウェアグラフＧ２上の紐付け処理、及び予約処理を実行することを前提として説明する。本実施形態では、コンピュータ３はメモリ５に記憶されたプログラムを実行することで、禁止部、解消部、選択部として機能する。

初期状態において、コンピュータ３は、問題グラフＧ１を入力し（Ｓ３１）、問題グラフＧ１の変数Ｘをランダムに選択し（Ｓ３２）、ハードウェアグラフＧ２に埋込む（Ｓ３３）。このとき、ハードウェアグラフＧ２上においては、第２実施形態にて説明したように、頂点Ｖに対応した他の単位セルＣの頂点Ｖを予約、確保する。例えば、ハードウェアグラフＧ２が、図９又は図１０に示したキメラグラフにより構成されているときには、単位セルＣ１１の頂点Ｖ１１に変数Ｘａを埋込んだときに、選択した単位セルＣ１１の頂点Ｖ１１から結合し、その他の変数Ｘ（例えばＸｂ，Ｘｃ）との結合を増加させる単位セルＣ１２、Ｃ１３、…の頂点Ｖ１１を、埋込む変数Ｘａに対応して予約する。これにより、単位セルＣ１２、Ｃ１３、…の頂点Ｖ１１が変数Ｘａに対応して予約、確保されることになり、その他の変数Ｘ（例えばＸｂ，Ｘｃ）の埋込みを禁止する。

その後、コンピュータ３は、問題グラフＧ１の中で埋込済変数Ｘａを選択し（Ｓ３４）、この埋込済変数Ｘａに結合された未埋込の変数Ｘｂを選択し（Ｓ３５）、変数ＸｂをハードウェアグラフＧ２に埋込む（Ｓ３６）。図１２には、処理途中における埋込済変数Ｘａと追加する変数Ｘｂの候補を示している。この図１２に示すように、コンピュータ３は、問題グラフＧ１上の変数Ｘを選択するときに、Ｓ３５において埋込済変数Ｘａに結合する変数Ｘｂを選択しＳ３６においてハードウェアグラフＧ２に埋込む。このときコンピュータ３は、図４のＳ１２～Ｓ１４に示すように、重複割当するものについてハードウェアグラフＧ２に埋込みせず、重複割当していなければハードウェアグラフＧ２に埋込む。

また、コンピュータ３は、埋込済変数Ｘａに結合した全ての変数Ｘｂの埋込処理を完了したか否かを判定し（Ｓ３７）、完了していなければ（Ｓ３７でＮＯ）、埋込済変数Ｘａに結合された変数ＸｂがなくなるまでＳ３５にて変数Ｘｂを選択してＳ３６にて変数Ｘｂを埋込む。そしてコンピュータ３は、この変数Ｘｂがなくなると（Ｓ３７でＹＥＳ）、埋込済変数Ｘａに紐付けて予約された頂点Ｖへの埋込禁止を解除する（Ｓ３８）。すなわち、Ｓ３３においてハードウェアグラフＧ２の特定の頂点Ｖに対して埋込済変数Ｘａ以外のその他の変数Ｘの埋込みを禁止しているため、コンピュータ３がこのＳ３８の処理を実行する直前までは、Ｓ３４にて選択された埋込済変数Ｘａに予約された頂点Ｖにその他の変数Ｘを埋込むことが禁止されていたが、Ｓ３８の処理が実行された後は、その他の変数Ｘを埋込むことができる。

したがって、この時点で未埋込の変数Ｘｂ又はＸｃは、ハードウェアグラフＧ２において、Ｓ３８において予約解除（解消）された頂点Ｖを用いて埋込むことができ、ハードウェアグラフＧ２を効率良く利用できる。そして、コンピュータ３は、これらのＳ３４～Ｓ３８の処理を終了条件を満たすまで繰り返し実行する。このときの終了条件は、埋込済変数Ｘａがなくなる、未埋込の変数Ｘｂ，Ｘｃがなくなる、所定回数以上の試行を重ねた、などである。

これらのＳ３５～Ｓ３９の処理内容の具体例を図１３に示している。図１３の中央に示すように、コンピュータ３は、ある一つの埋込済変数Ｘａを選択し、この埋込済変数Ｘａに結合した変数Ｘｂを選択するが、これらの結合した変数Ｘｂを全て埋込んだ後、選択した埋込済変数Ｘａに対応したハードウェアグラフＧ２の頂点Ｖの予約を解消する。そして図１３の右側に示すように、コンピュータ３は、他の埋込済変数Ｘａを選択し、さらにこの他の埋込済変数Ｘａに結合した未埋込の変数Ｘｂをさらに選択する。これによりハードウェアグラフＧ２に設定された予約を解消しながら、未埋込の変数Ｘｂ、Ｘｃを埋込むことができ、第２実施形態に比較して部分問題の解導出処理における変数Ｘの埋込数を増やすことができる。

その後、量子イジングマシン１が部分問題に係る最適化処理を実行し（Ｓ４０）た後、コンピュータ３は、その量子イジングマシン１の処理結果に基づいて変数Ｘを更新し（Ｓ４１）、終了条件を満たすか否かを判定する（Ｓ４２）。終了条件を満たしていなければ、Ｓ３２に処理を戻し、コンピュータ３が、問題グラフＧ１の変数Ｘを新たに選択するところから再度繰り返し実行する。そしてコンピュータ３は、Ｓ４２の終了条件を満たしたときに変数Ｘの解を出力する（Ｓ４３）。Ｓ４２の終了条件としては、第１実施形態のＳ５の終了条件と同一条件を用いれば良いため説明を省略する。

＜本実施形態のまとめ、効果＞
本実施形態によれば、コンピュータ３は、埋込済変数Ｘａを一つ選択し、問題グラフＧ１の上で埋込済変数Ｘａに結合した全ての変数Ｘｂの埋込処理を一通り完了した後に予約を解消している。これにより、ハードウェアグラフＧ２における予約を効率的に解消しながら変数Ｘｂの埋込処理を実行でき、予約された頂点Ｖを減らすことでハードリソースを有効に活用できる。しかも、一回の部分問題の解導出処理においてより多くの変数Ｘｂ、ＸｃをハードウェアグラフＧ２に埋込むことができる。

またコンピュータ３が、追加して埋込む変数Ｘを選択するときには、すでに埋込みされた埋込済変数Ｘａに結合された未埋込の変数Ｘｂの中から選択するようにしているため、埋込済変数Ｘａに相互作用していない独立な変数Ｘｃを選択することがなくなる。この結果、フラストレーション等の最適化が難しい問題グラフＧ１の構造を残したまま、変数ＸをハードウェアグラフＧ２に埋込みできる。

（第４実施形態）
図１４から図１８は、第４実施形態の追加説明図を示している。本形態では、ワンホット（one-hot）表示を用いて多値問題を表現した場合の変数の埋込方法について説明するが、前述実施形態、特に第１実施形態と同一部分については同一符号を付して説明を省略し、前述実施形態と異なる部分を中心に説明する。コンピュータ３は、メモリ５に記憶されたプログラムを実行することで実現する機能として、無効化処理部、変換部としての各種機能を備える。

ワンホット表示手法は、多値変数Ｓ₁～Ｓ_Nを用いた大規模問題を２値表現する代表的な方法として知られている。以下では、多値変数Ｓ₁～Ｓ_Nの一部の変数又は全変数を必要に応じて、多値変数Ｓ_iと表記する。多値変数Ｓ₁～Ｓ_Nを二値変数ｘ₁ ^(q)～ｘ_N ^(q)を用いてワンホット表示する場合、各多値変数Ｓ_iがとり得る状態の数だけ二値変数ｘ_i ^(q)～ｘ_i ^(q)を設けることで実現できる。但しｑ＝１～Ｑである。以下では、二値変数ｘ_i ^(q)～ｘ_i ^(q)の一部の変数又は全変数を必要に応じて二値変数ｘ_iと表記する。簡単な例として、１次元のポッツ（Potts）模型の評価関数Ｈ₀を（１）式に示すが、評価関数Ｈ₀は、この例に限られるものではない。

（１）式の評価関数Ｈ₀は、多値変数Ｓ_iが１からＱのＱ個の状態を取ることが可能な制約の下で、評価関数Ｈ₀が最も小さくなるように１からＱのＱ個の中から１個の状態を多値変数Ｓ_iにより選択する最適化問題を表している。
下記の（２）式は、（１）式の評価関数Ｈ₀についてワンホット制約に基づき二値変数ｘ_iを用いて変換した変換式を表している。図１４は、（２）式の評価関数Ｈ₀に係る最適化問題の問題グラフＧ１を示す。評価関数Ｈ₀に係る最適化問題をワンホット表示するときに、評価関数Ｈ₀を表現するための二値変数ｘ_iは、図１４に示すようにＮ×Ｑ個存在する。

（２）式の評価関数Ｈ₀の右辺第１項は、図１４に示す問題グラフＧ１にて結合した多値変数Ｓ_i、Ｓ_jの同じ状態ｑを示す二値変数ｘ_i ^(q)、ｘ_j ^(q)がホット状態値「１」となる条件を満たす場合に積算される項であり、（１）式で表される多値最適化問題のコスト部分を示している。ここで、ｊ＝ｉ＋１又はｉ－１である。この（２）式の右辺第１項では、隣接する二値変数ｘ_i、ｘ_jの相互作用係数Ｊ_iが正のときに評価関数Ｈ₀を低下させることでより最適化できるようになっている。また（２）式の右辺第１項の相互作用係数Ｊ_iが負のときに、評価関数Ｈ₀を低下させるように（２）式中の符号を変更しても良い。また評価関数Ｈ₀が高い方がより最適化されるように数式を変更しても良い。

ワンホット制約は、各多値変数Ｓ_iを表す二値変数ｘ_iの中でホット状態値「１」がそれぞれ１つだけ現れる制約を示しており、評価関数Ｈ₀の右辺第２項が、この制約を表している。評価関数Ｈ₀の右辺第２項は、各多値変数Ｓ_iの中でそれぞれ二値変数ｘ_iを１つだけホット状態値「１」とした場合、評価関数Ｈ₀が最低となるように追加した制約項を示す。（２）式の右辺第２項のλは、当該（２）式の右辺第１項と右辺第２項との影響の割合を表すパラメータであり、パラメータλを大きく設定すれば右辺第２項の影響を大きくでき、二値変数ｘ_iを１つだけホット状態値「１」とする制約条件を強めることができ、逆にパラメータλを小さく設定することで、（２）式の右辺第１項の影響を大きくできる。

ワンホット制約を含む最適化問題の部分問題をハードウェアグラフＧ２に埋込む場合、部分問題が、ワンホット制約を満たす解を可能な限り多く含むように選択しないと最適解の探索を効率的に実行できなくなる。例えば図１５に示すように、コンピュータ３が、ある一つの多値変数Ｓ_iの中で全てコールド状態値「０」とされている二値変数ｘ_iを部分的に選択した場合、図１５に示すようにワンホット制約を満たす解が１個しか存在しない。図１５に示す二値変数ｘ_iの部分選択変数Ｓａを参照。このため、たとえ量子イジングマシン１が最適化処理を実行しても、全てコールド状態値「０」とされている二値変数ｘ_iに対応した解に部分問題の最適解が固定されてしまう。つまりこの場合、全体の二値変数ｘ_iのより良い解を探索できなくなる。

そこで、二値変数ｘ_iの最適化処理が繰り返される一連の処理の中で、図１６に示すように、コンピュータ３が多値変数Ｓ_iの二値変数ｘ_iを参照した時点において、ホット状態値「１」とされている二値変数ｘ_iを必ず含むように部分問題を選択することが望ましい。コンピュータ３は、ホット状態値「１」とされた二値変数ｘ_iを含むように二値変数ｘ_iを部分問題の変数として選択することで、部分問題がワンホット制約を満たす状態を多数含むように構成できる。図１６に示す二値変数ｘ_iの部分選択変数Ｓｂ１、Ｓｂ２、Ｓｂ３を参照。この結果、部分問題の最適化によりワンホット制約を満たすより高精度な解を効率的に探索できる。

以下、多値変数Ｓ_iの埋込方法について図３及び図１７を参照しながら説明する。
最初に、コンピュータ３は、図３のＳ１において問題グラフＧ１を入力し、Ｓ２において２値変数ｘ_iの埋込処理を実行する。図１７に２値変数ｘ_iの埋込処理のフローチャートを前述実施形態の図４に対応して示している。コンピュータ３が、量子イジングマシン１のハードウェアグラフＧ２に２値変数ｘ_iを埋込むときには、多値変数Ｓ₁～Ｓ_Nの中からランダムに一つの多値変数Ｓ_iを選択し、選択した多値変数Ｓ_iに割当てられた２値変数ｘ_iを埋込む（Ｓ６１）。ここでは、ｉ番目の多値変数Ｓ_iを選択する例を示す。なおコンピュータ３は、Ｓ６１において多値変数Ｓ_iを選択し、後述するＳ７０の終了条件でＮＯと判定してＳ６１に処理を戻した後に選択する多値変数Ｓ_jは、問題グラフＧ１上で埋込済の多値変数Ｓ_iに隣接、結合する未埋込の多値変数Ｓ_j（但しｊはｉ－１かｉ＋１）を対象とする。

ｉ番目の多値変数Ｓ_iの中の二値変数ｘ_iは、１からＱのＱ個存在するため、コンピュータ３は、Ｓ６２においてハードウェアグラフＧ２に対する二値変数ｘ_iの埋込順序を決定する。コンピュータ３が二値変数ｘ_iをハードウェアグラフＧ２に埋込みする優先順位は、次の制約に基づいて決定することが望ましい。
コンピュータ３が、ある多値変数Ｓ_iの中で最初に埋込むべき二値変数ｘ_iは、既に埋込済の二値変数ｘ_j（但しｊはｉ－１かｉ＋１）に隣接、結合している二値変数ｘ_iとすることが望ましい。コンピュータ３は、この結合条件を満たす二値変数ｘ_iの中でもホット状態値「１」とされている二値変数ｘ_iを最優先とし、コールド状態値「０」とされている二値変数ｘ_iを次の優先順位として選択すると良い。

また、コンピュータ３が、ある多値変数Ｓ_iの中で２番目以降に埋込むべき二値変数ｘ_iは、ホット状態値「１」とされている二値変数ｘ_iを最優先とし、コールド状態値「０」とされている二値変数ｘ_iを次の優先順位とすることが望ましい。コンピュータ３は、コールド状態値「０」の条件を満たす二値変数ｘ_iの中でも埋込済の二値変数ｘ_jに隣接、結合している二値変数ｘ_iを優先的に埋込対象とすることが望ましく、埋込済の二値変数ｘ_jに隣接、結合していない二値変数ｘ_iを次の優先順位として選択すると良い。なお、優先順位の具体例は後述する。

コンピュータ３は、Ｓ６３において前述した優先順位にて二値変数ｘ_iを選択した後、Ｓ６４において二値変数ｘ_iをハードウェアグラフＧ２に埋込む際に重複割当を生じるか否かを判定する。コンピュータ３は、対象となる二値変数ｘ_iをハードウェアグラフＧ２に埋込む際に、重複割当を必要とすればＳ６５においてハードウェアグラフＧ２に埋込みしない。逆に、コンピュータ３は、重複割当を必要としなければＳ６６においてハードウェアグラフＧ２に埋込む。コンピュータ３は重複割当を必要としなければ、前述実施形態にて説明したように、二値変数ｘ_iを埋め込んだ頂点Ｖを基点としてハードウェアグラフＧ２の他の頂点Ｖを予約することになる。

ここでコンピュータ３は、対象となる二値変数ｘ_iをハードウェアグラフＧ２に埋込む際に重複割当を必要とすればＳ６５において埋込みしないと判定するが、この埋込みしない二値変数ｘ_iがホット状態値「１」であった場合には、Ｓ６９において選択した多値変数Ｓ_iの埋込を無効、すなわちキャンセルとし、次の多値変数Ｓ_jの埋込処理に移ることが望ましい。すなわち、ホット状態値「１」の二値変数ｘ_iがハードウェアグラフＧ２に埋込不能であれば、コールド状態値「０」を満たす二値変数ｘ_iしか埋込不能となるためである。これにより、ワンホット制約を満たす状態を部分問題に一つしか含まない多値変数Ｓ_iを部分問題から排除できる。

そしてコンピュータ３は、Ｓ６７において、Ｓ６１にて選択した多値変数Ｓ_iに割当てられた全ての二値変数ｘ_iの埋込処理を終了したか否かを判定し、全ての二値変数ｘ_iの埋込処理を終了するまでＳ６３～Ｓ６６の処理を繰り返す。

コンピュータ３は、選択した多値変数Ｓ_iに割当てられた全ての二値変数ｘ_iの埋込処理を終了した結果、全ての二値変数ｘ_iの中で２つ以上埋込みできた場合には、そのままＳ７０に移行し処理を継続する。しかしコンピュータ３は、選択した多値変数Ｓ_iの中で二値変数ｘ_iを１つ以下、すなわちホット状態値「１」又はコールド状態値「０」を示す二値変数ｘ_iしか埋込みできないときには、Ｓ６９において選択した多値変数Ｓ_iの全ての埋込を無効、すなわちキャンセルする。このとき、コンピュータ３は、既に埋込まれた二値変数ｘ_iをハードウェアグラフＧ２の頂点Ｖから除去すると共に、他の頂点Ｖの予約を解除することで、量子イジングマシン１のハードウェアリソースの予約を取り消す。これにより、ワンホット制約を満たさない多値変数Ｓ_iを部分問題を表す変数から排除できる。

コンピュータ３は、Ｓ７０において終了条件を満たすか否かを判定し、終了条件を満たすまで多値変数Ｓ_iに隣接、結合した他の多値変数Ｓ_j（但しｊはｉ－１又はｉ＋１）を選択するところから処理を繰り返す。コンピュータ３が、多値変数Ｓ_jを表現する二値変数ｘ_jが、その前に埋込まれた多値変数Ｓ_iの二値変数ｘ_iにハードウェアグラフＧ２上で結合できなくなると、Ｓ７０において終了条件を満たしたと判定し、他の多値変数Ｓ_jの埋込みを終了する。

そしてコンピュータ３が、全ての多値変数Ｓ_iの埋込処理を終了すると、量子イジングマシン１は、図３のＳ３において最適化処理を実行する。量子イジングマシン１は、最適化処理において埋め込まれた部分問題を勾配法やその他の最適化手法を用いて最適化し、評価関数Ｈ₀が所定より低い最適化条件を満たすように二値変数ｘ_iの値を求める。このとき量子イジングマシン１は、処理を開始してから所定時間経過したり所定以上の試行回数繰り返したことを条件として二値変数ｘ_iの最適値を決定し更新する（Ｓ４）。この場合、他の埋込不能な二値変数ｘ_iとしては、これまでに得られた最適解又は初期値など固定値を用いて評価関数Ｈ₀の評価値を求めると良い。これにより、部分問題を解くことができる。

その後、コンピュータ３はＳ２に処理を戻し、Ｓ２において多値変数Ｓ_iを再度選択し当該選択された多値変数Ｓ_iの中の二値変数ｘ_iをハードウェアグラフＧ２に埋込むと、量子イジングマシン１がこれらの二値変数ｘ_iによる最適化処理を実行し、当該二値変数ｘ_iの組合せの最適値を決定し、Ｓ４においてこれらの二値変数ｘ_iを更新する。なお、このとき選択されなかった二値変数ｘ_iは、当該処理以前に最適値として求められた二値変数ｘ_iの最適値を用いると良い。一度も選択されていない多値変数Ｓ_iの中の二値変数ｘ_iは、固定値に設定して処理すると良い。

そして量子イジングマシン１は、処理を開始してから所定時間経過したり又は所定以上の試行回数繰り返したことを条件として終了条件を満たしたと判定し（Ｓ５でＹＥＳ）、これらの多値変数Ｓ_iの結果又は評価関数Ｈ₀の評価値などを出力する。これにより、全体の最適化問題を解くことができる。このように繰返し処理を行うことで、原問題を部分問題に分割して解くことができる。

＜ステップＳ６２の埋込方法の具体例＞
二値変数ｘ_iをハードウェアグラフＧ２へ埋込むときのステップＳ６２の具体例について図１８を参照しながら説明する。ここではＱ＝４の簡単な例を示している。コンピュータ３が、量子イジングマシン１のハードウェアグラフＧ２に多値変数Ｓ₁のうち二値変数ｘ₁ ⁽¹⁾、ｘ₁ ⁽²⁾を埋込んだものの、他の二値変数ｘ₁ ⁽³⁾、ｘ₁ ⁽⁴⁾をハードウェアグラフＧ２に埋込む際に重複割当が生じ、埋込不可能とされた場合を想定する。図１８の中には、ハードウェアグラフＧ２の頂点Ｖに埋込済の二値変数ｘ₁ ⁽¹⁾、ｘ₁ ⁽²⁾を「Ｚ１」と符号を付している。

このとき、埋込まれた二値変数ｘ₁ ⁽²⁾がホット状態値「１」とされていることを想定している。図１８の中には、コンピュータ３が、多値変数Ｓ₁に隣接して結合した多値変数Ｓ₂の中の二値変数ｘ₂ ⁽¹⁾、ｘ₂ ⁽²⁾、ｘ₂ ⁽³⁾、ｘ₂ ⁽⁴⁾を埋込む際の優先順位「１ｓｔ」～「４ｔｈ」を示している。

前述のＳ６２の説明でも示したように、最初に埋込むべき二値変数ｘ₂は、埋込済の二値変数ｘ₁に結合している二値変数ｘ₂とすることが望ましい。二値変数ｘ₂の中でもホット状態値「１」とされている二値変数ｘ₂を最優先とすることが望ましい。図１８に示す例の場合、埋込済の二値変数ｘ₁に結合している二値変数ｘ₂ ⁽¹⁾、ｘ₂ ⁽²⁾は両者共にコールド状態値「０」であるため、二値変数ｘ₂ ⁽¹⁾、ｘ₂ ⁽²⁾の何れの変数を選択しても良いが、ここでは二値変数ｘ₂ ⁽¹⁾をランダムで選択している例を示している。

また２番目以降に埋込むべき二値変数ｘ_iは、ホット状態値「１」とされている二値変数ｘ_iを最優先とし、コールド状態値「０」とされている二値変数ｘ_iを次の優先順位とすることが望ましい。図１８に示す例の場合、二値変数ｘ₂ ⁽⁴⁾がホット状態値「１」とされているため、ホット状態値「１」の二値変数ｘ₂ ⁽⁴⁾を２番目の埋込対象とする。またコンピュータ３は、コールド状態値「０」の条件を満たす二値変数ｘ_iの中でも埋込済の二値変数ｘ_jに結合している二値変数ｘ_iを優先的に埋込対象とする。このため図１８に示す例では、二値変数ｘ₂ ⁽²⁾を３番目の埋込対象とする。またコンピュータ３は、埋込済の二値変数ｘ_jに結合していない二値変数ｘ_iを次の優先順位として選択する。図１８に示す例の場合、二値変数ｘ₂ ⁽³⁾を最後の埋込対象としている。このような順序にて二値変数ｘ_iを埋込むことが望ましい。

＜本実施形態のまとめ、効果＞
本実施形態によれば、多値変数Ｓ_iにより定義された評価関数Ｈ₀をワンホット制約により２値変数ｘ_iを用いて表現した大規模な最適化問題を解く場合に、部分問題の変数として多値変数Ｓ_iの中の少なくとも一部の二値変数ｘ_iを含むように選択するときには、ホット状態値「１」（第一値相当）とされている二値変数ｘ_iが含まれるように選択してハードウェアグラフＧ２に埋込処理している。これにより、各多値変数Ｓ_iは複数個のワンホット制約を満たす状態を部分問題に含むようになり、より高精度な解を効率的に探索することが可能となる。

またコンピュータ３は、既に埋込まれた多値変数Ｓ₁に問題グラフ上で結合する多値変数Ｓ₂の二値変数ｘ₂を追加で埋込処理するときには、多値変数Ｓ₂を表現する二値変数ｘ₂の中で、埋込済の二値変数ｘ₁ ⁽¹⁾に問題グラフＧ１の上で結合している二値変数ｘ₂ ⁽¹⁾を優先的に埋込むようにしている。すると、問題グラフＧ１の上で結合する多値変数Ｓ_i、Ｓ_jの間の相互作用を可能な限り多く含むように部分問題を構築できる。

またコンピュータ３は、既に埋込まれた多値変数Ｓ₁に問題グラフ上で結合する多値変数Ｓ₂の二値変数ｘ₂を追加で埋込処理するときには、多値変数Ｓ₂を表現する二値変数ｘ₂の中で、ホット状態値「１」とされている条件を満たす二値変数ｘ₂ ⁽⁴⁾、を優先的に埋込むようにしている。すると、ホット状態値「１」とされている二値変数ｘ₂ ⁽⁴⁾を優先的にハードウェアグラフＧ２に対し優先的に埋込むことができる。

またコンピュータ３は、ホット状態値「１」とされている二値変数ｘ_iを埋込不能と判定した場合には、当該二値変数ｘ_iにより表現される多値変数Ｓ_iの全体の埋込みを無効とし、先に埋込まれた二値変数ｘ_iをハードウェアグラフＧ２の頂点Ｖから除去している。これにより、ワンホット制約を満たす状態を部分問題の中に１個しかもたない多値変数Ｓ_iを部分問題から除外できる。しかも量子イジングマシン１のハードウェアリソースの予約を取り消すことができる。

またコンピュータ３は、選択した多値変数Ｓ_iの全ての二値変数ｘ_iの中で２つ以上埋込不能と判定した場合には、当該二値変数ｘ_iにより表現される多値変数Ｓ_iの全体の埋込みを無効とし、先に埋込まれた二値変数ｘ_iをハードウェアグラフＧ２の頂点Ｖから除去している。ホット状態値「１」及びコールド状態値「０」の双方を埋込不能な多値変数Ｓ_iを部分問題から排除でき、ワンホット制約を満たす状態を部分問題の中に１個しかもたない多値変数Ｓ_iを部分問題から排除できる。

（第５実施形態）
図１９及び図２０は、第５実施形態の追加説明図を示している。評価関数Ｈ₀は、パラメータλを用いて（２）式のように構成すれば良いものの、（２）式の右辺第２項の影響の割合をパラメータλにより変数定義することは、量子イジングマシン１がワンホット制約を満たさない解も全体の最適化問題の解として導出する可能性を高くする。またパラメータλを最適値に調整するため、計算処理量がより増加してしまう可能性がある。

このようなことが想定されるときには、コンピュータ３が、量子イジングマシン１に部分問題を実装する前に、多値変数Ｓ_iの多値状態「１」～「Ｑ」を２択により選択する２択最適化問題に変換すると良い。コンピュータ３が、２択最適化問題への変換処理を事前に実行することで、ワンホット制約を満たさない多値変数Ｓ_iの解を排除した部分問題を量子イジングマシン１に実装できる。この場合、前述した（２）式の右辺第２項に相当する制約を排除でき、（２）式の右辺第２項のパラメータλを変数定義する必要がなくなる。コンピュータ３及び量子イジングマシン１は、（２）式の右辺第１項に相当するコスト部分の最適化処理を実行することで、二値変数ｘ_iの最適解を求めることができ、計算処理量を大幅に削減できるようになる。

例えばコンピュータ３は、図１９に示す手順を用いて、全多値変数Ｓ_iについて、現状の多値状態「１」～「Ｑ」を維持するか、現状の多値状態「１」～「Ｑ」を遷移させるか、を選択する２択最適化問題に変換した後に、当該２択最適化問題に係る部分問題を量子イジングマシン１に実装して最適化処理を実行させることが望ましい。

図１９に示すように、コンピュータ３は、Ｓ５１において多値変数Ｓ₁～Ｓ_Nを順番に選択し、Ｓ５２にて選択した多値変数Ｓ_iの中でホット状態値「１」の遷移先候補をランダムに選択する。コンピュータ３は、全ての多値変数Ｓ₁～Ｓ_NについてステップＳ５１～Ｓ５３の処理を繰り返すことで、最終的にＳ５４に示すように、多値変数Ｓ_iの現状の多値状態「１」～「Ｑ」を維持するか、現状の多値状態「１」～「Ｑ」を遷移させるか、を２択により選択する２択最適化問題に変換できる。

図２０に具体例を示す。コンピュータ３は、図１９に示す処理を実行する時点で多値変数Ｓ_iが多値状態「１」にされていると仮定した場合、遷移先の候補として多値状態「２」～「Ｑ」のうち一つをランダムに選択する。仮にコンピュータ３が、遷移先として多値状態「３」を選択した場合、多値変数Ｓ_iを現状の多値状態「１」か遷移先の多値状態「３」とするかの２択の判断を量子イジングマシン１に委ねることになる。この結果、多値変数Ｓ_iが現状の多値状態「１」を維持、又は、多値状態「３」に遷移、の２択による２択最適化問題に変換できる。この２択最適化問題は、二択変数ｙ_iにより定義され、例えば二択変数ｙ_i＝０は維持、二択変数ｙ_i＝１は遷移を表す。

またコンピュータ３は、問題グラフＧ１上で結合する多値変数Ｓ_i、Ｓ_jが同一の多値状態とされたときに評価関数Ｈ₀がより最適化されることを認識している場合、一の多値変数Ｓ_iの現状の多値状態「１」か遷移先の多値状態「３」の何れか少なくとも一以上が、一の多値変数Ｓ_iと結合する他の多値変数Ｓ_jの現状の多値状態又は遷移先の多値状態の何れか少なくとも一以上と同一状態となるように２択最適化問題を構築することが望ましい。すると、量子イジングマシン１が２択最適化問題を最適化したときに、評価関数Ｈ₀を最適化する二値変数ｘ_iを効率的に求めることができる。

多値変数Ｓ_iの表現に代えて、二値変数ｘ_iの２値状態値を用いて言い換えると、二値変数ｘ_iの２値状態値が問題グラフＧ１上で結合した二値変数ｘ_jと同一の２値状態値となる状態を２択最適化問題が含むように、二値変数ｘ_iが現状の２値状態値（ホット状態値「１」又はコールド状態値「０」）かこれとは異なる遷移先の２値状態値かが、隣接して結合した二値変数ｘ_jの現状の２値状態値かこれとは異なる遷移先の２値状態値の何れか少なくとも一以上と同一となるように選択すると良い。

逆に、コンピュータ３は、問題グラフＧ１上で隣接して結合する多値変数Ｓ_i、Ｓ_jが異なる多値状態とされたときに評価関数Ｈ₀が小さくなることを認識している場合、一の多値変数Ｓ_iの現状の多値状態「１」か遷移先の多値状態「３」の何れか又は双方が、隣接する他の多値変数Ｓ_jの現状の多値状態及び遷移先の多値状態の両方と異なる多値状態となるように２択最適化問題を構築することが望ましい。すると、量子イジングマシン１が２択最適化問題を最適化したときに、評価関数Ｈ₀を最適化した条件を満たした二値変数ｘ_iを高精度に求めることができる。

多値変数Ｓ_iの表現に代えて、二値変数ｘ_iの状態値を用いて言い換えると、二値変数ｘ_iの２値状態値が問題グラフＧ１上で結合した二値変数ｘ_jと異なる２値状態値を２択最適化問題が含むように、二値変数ｘ_iが現状の２値状態値（ホット状態値「１」又はコールド状態値「０」）か、これとは異なる遷移先の２値状態値かが、隣接して結合した二値変数ｘ_jの現状の２値状態値及び遷移先の２値状態値の両方と異なるように選択すると良い。

コンピュータ３は、二択変数ｙ_iにより定義される２択最適化問題の部分問題をハードウェアグラフＧ２に埋込むことで部分問題を実装する。そして、量子イジングマシン１が、埋込まれた２択最適化問題の部分問題を最適化し二択変数ｙ_iを決定する。コンピュータ３は、部分問題を最小化する量子イジングマシン１による二択変数ｙ_iの出力と、各変数の現状の２値状態と遷移先の２値状態を参照して二値変数ｘ_iを更新する。コンピュータ３とイジングマシン１により２択最適化問題を生成し、二値変数ｘ_iの更新処理を繰り返すことで、全体の二値変数ｘ_iの最適解を得ることができる。

多値問題の多値変数Ｓ_iを最適化する際に、コンピュータ３は多値変数Ｓ_iによる多値状態「１」～「Ｑ」を２択により選択する２択最適化問題に変換した後、２択最適化問題の二択変数ｙ_iを部分的にハードウェアグラフＧ２の頂点Ｖに埋込んでいる。コンピュータ３が、２択最適化問題への変換処理を事前に実行することで、ワンホット制約を満たさない多値変数Ｓ_iの解を排除した部分問題を構築でき、この結果、計算処理量を大幅に削減できる。さらに、部分問題は、ワンホット制約を満たした状態しか含まないため、ワンホット制約の強さを決定するパラメータλを調整する必要がなくなる。特に、現状の多値状態「１」～「Ｑ」を維持する(二択変数ｙ_i＝０）か、現状の多値状態「１」を遷移させる（二択変数ｙ_i＝１）か、を選択する２択最適化問題に変換することが望ましい。

また、問題グラフＧ１上で隣接して結合する多値変数Ｓ_i、Ｓ_jが同一の多値状態とされたときに評価関数Ｈ₀がより最適化される場合、一の多値変数Ｓ_iの現状の多値状態か遷移先の多値状態の何れか少なくとも一以上が、隣接する他の多値変数Ｓ_jの現状の多値状態又は遷移先の多値状態と同一状態となるように２択最適化問題を構築することが望ましい。これにより、量子イジングマシン１が２択最適化問題を最適化したときに評価関数Ｈ₀をより最適化できる。

また、問題グラフＧ１上で隣接して結合する多値変数Ｓ_i、Ｓ_jが異なる多値状態とされたときに評価関数Ｈ₀がより最適化される場合、一の多値変数Ｓ_iの現状の多値状態か遷移先の多値状態の何れか又は双方が、隣接する他の多値変数Ｓ_jの現状の多値状態及び遷移先の多値状態の両方と異なる多値状態となるように２択最適化問題を構築することが望ましい。これにより、量子イジングマシン１が２択最適化問題を最適化したときに評価関数Ｈ₀をより最適化できる。

（他の実施形態）
本開示は、前述実施形態に限定されるものではなく、例えば、以下に示す変形又は拡張が可能である。ハードウェアグラフＧ２は、キメラグラフを用いて説明したが、これに限定されるものではない。

第４実施形態では、ホット状態値「１」（第一値相当）が一つだけ設けられたワンホット制約を例に挙げて説明したが、逆に、コールド状態値「０」（第一値相当）が一つだけ設けられたワンコールド制約に適用しても良い。第４実施形態では、評価関数Ｈ₀の評価式として（２）式を例示したが、ワンコールド表示を適用した場合には、下記の（３）式のように第２項内の数式を変換すると良い。

第一値がその他全ての第二値と異なるように二値変数ｘ_iを表示できれば、どのような二値変数ｘ_iを用いても良い。なお、多値変数Ｓ_iがワンホット表示される場合にはホット状態値「１」が第一値に相当すると共にコールド状態値「０」が第二値に相当する。多値変数Ｓ_iがワンコールド表示される場合にはコールド状態値「０」が第一値に相当すると共にホット状態値「１」が第二値に相当する。

前述実施形態の構成、処理内容を組み合わせて構成することもできる。また、特許請求の範囲に記載した括弧内の符号は、本発明の一つの態様として前述する実施形態に記載の具体的手段との対応関係を示すものであって、本発明の技術的範囲を限定するものではない。前述実施形態の一部を、課題を解決できる限りにおいて省略した態様も実施形態と見做すことが可能である。また、特許請求の範囲に記載した文言によって特定される発明の本質を逸脱しない限度において、考え得るあらゆる態様も実施形態と見做すことが可能である。

また本発明は、前述した実施形態に準拠して記述したが、本発明は当該実施形態や構造に限定されるものではないと理解される。本発明は、様々な変形例や均等範囲内の変形をも包含する。加えて、様々な組み合わせや形態、さらには、それらに一要素、それ以上、あるいはそれ以下、を含む他の組み合わせや形態をも、本開示の範畴や思想範囲に入るものである。

図面中、１は量子イジングマシン（専用ハードウェア）、３はコンピュータ（予約部、禁止部、解消部、選択部、無効化処理部、変換部）、７は判定部、８は埋込部、Ｖ、Ｖ１１～１４、Ｖ２１～Ｖ２４は頂点、を示す。

Claims (24)

1. 頂点（Ｖ）の間の相互作用を表すハードウェアグラフ（Ｇ２）が特定の固定アーキテクチャにより構成された最適化問題の専用ハードウェア（１）を用いて、当該最適化問題の全ての変数を埋込不可能な大規模問題を解く場合について、当該最適化問題の変数の相互作用を問題グラフ（Ｇ１）に表して解く場合に、前記問題グラフの変数を前記専用ハードウェアの前記ハードウェアグラフの頂点に埋込むことが可能な部分問題に分割し、前記部分問題の最適化処理を繰り返すことで前記大規模問題を解くときに用いられる変数埋込方法であって、
   前記全ての変数のうち少なくとも一部を前記ハードウェアグラフの頂点に埋込むときに、
   前記最適化問題の変数を前記ハードウェアグラフの頂点へ重複割当を必要とするか否かを判定する過程（Ｓ１２）と、
   前記重複割当を必要とする前記変数については前記部分問題の変数として用いることなく、前記重複割当の不要な前記変数を選択して前記ハードウェアグラフの頂点に埋込む過程（Ｓ１３）と、
   を備える変数埋込方法。
2. 完全グラフ（Ｇ１ａ）を前記ハードウェアグラフに埋込むときの埋込方法に基づいて前記ハードウェアグラフの頂点を紐付ける過程（Ｓ２１）と、
   前記ハードウェアグラフの上に前記変数を埋込むときに、当該変数が埋込まれる前記ハードウェアグラフの上で連結された部分グラフの中から少なくとも一つ以上の前記頂点を選択する過程（Ｓ２６）と、
   前記ハードウェアグラフに前記変数（Ｘ１，Ｘａ）を埋込むときに、前記紐付けの内容に基づいて、前記選択した前記頂点から結合し且つその他の前記変数（Ｘ２～Ｘ９，Ｘｂ，Ｘｃ）との結合を増加させる前記頂点を、前記埋込む変数（Ｘ１，Ｘａ）に対応して予約することで当該埋込む変数（Ｘ１，Ｘａ）以外の前記その他の変数（Ｘ２～Ｘ９，Ｘ）の埋込みを禁止する過程（Ｓ２７）と、をさらに備える請求項１記載の変数埋込方法。
3. 前記その他の変数（Ｘ）の埋込みを禁止する過程を実行した後、前記問題グラフの上で埋込済の前記変数（Ｘａ）に結合した全ての前記変数（Ｘｂ）の埋込処理が完了した後に前記予約を解消する過程（Ｓ３７，Ｓ３８）、をさらに備える請求項２記載の変数埋込方法。
4. 前記ハードウェアグラフが、複数の頂点を備えた単位セル（Ｃ、Ｃ１１…Ｃ４４）を第１方向及び第２方向に沿って複数グリッド分だけ備えたキメラグラフにより構成される場合、一つの前記単位セル（Ｃ１１，Ｃ３３）の第１頂点（Ｖ１１，Ｖ１３）を基点として前記第１方向又は前記第２方向に結合する他の前記単位セル（Ｃ１２，Ｃ１３…，Ｃ３１，Ｃ３２，Ｃ３４…）に対応した頂点を第２頂点（Ｖ１１，Ｖ１３）として予約する過程（Ｓ２２）をさらに備える請求項２又は３記載の変数埋込方法。
5. 前記問題グラフの中で追加して埋込む前記変数を選択するときには、
   すでに埋込みされた埋込済の前記変数に結合された未埋込の前記変数の中から選択する請求項１から４の何れか一項に記載の変数埋込方法。
6. 前記問題グラフの中で追加して埋込む前記変数を選択して前記ハードウェアグラフに埋込むときには、
   すでに埋込みされた埋込済の前記変数（Ｘａ）を一つ選択し（Ｓ３４）、前記選択した埋込済の変数に結合した前記変数（Ｘｂ）を選択して埋込処理を完了した後（Ｓ３５～Ｓ３７）、他の埋込済の前記変数を選択し（Ｓ３４）、当該選択した埋込済の変数（Ｘａ）に結合した前記変数（Ｘｂ）の埋込処理を繰り返す請求項１から５の何れか一項に記載の変数埋込方法。
7. 前記大規模問題が、ワンホット（one-hot）制約又はワンコールド（one-cold）制約など一つだけ設けられた第一値がその他の全ての第二値と異なるように制約が設けられた二値変数（ｘ₁ ⁽¹⁾～ｘ₁ ^(Q)：ｘ_N ⁽¹⁾～ｘ_N ^(Q)）により表現される多値変数（Ｓ₁：Ｓ_N）を適用した多値問題であり、
   前記部分問題の変数として前記多値変数の中の少なくとも一部の前記二値変数を含むように選択して前記ハードウェアグラフの頂点に埋込むときには、前記第一値とされている前記二値変数が含まれるように前記二値変数を選択して前記ハードウェアグラフの頂点に埋込処理する請求項１から６の何れか一項に記載の変数埋込方法。
8. 既に埋込処理が実行された前記多値変数（Ｓ₁）に前記問題グラフ上で結合する前記多値変数（Ｓ₂）の二値変数（ｘ₂）を前記ハードウェアグラフの頂点に追加で埋込処理するときには、
   前記多値変数を表現する前記二値変数の中で、前記埋込済の前記二値変数に前記問題グラフ上で結合している前記二値変数、又は、前記第一値とされている条件を満たす前記二値変数、を優先的に埋込む請求項７記載の変数埋込方法。
9. 前記第一値とされている前記二値変数を埋込不能と判定した場合（Ｓ６５ａでＮＯ）、又は、前記選択した多値変数を表現する全ての前記二値変数の中で２つ以上埋込不能と判定した場合（Ｓ６８でＮＯ）には、当該二値変数により表現される前記多値変数の全体の埋込みを無効とし、先に埋込まれた前記二値変数を前記部分問題から除去する（Ｓ６９）請求項７又は８記載の変数埋込方法。
10. 前記大規模問題が、ワンホット（one-hot）制約又はワンコールド（one-cold）制約など一つだけ設けられた第一値がその他の全ての第二値と異なるように制約が設けられた二値変数（ｘ₁ ⁽¹⁾～ｘ₁ ^(Q)：ｘ_N ⁽¹⁾～ｘ_N ^(Q)）により表現される多値変数（Ｓ₁：Ｓ_N）を適用した多値問題であり、
    前記多値問題の多値変数（Ｓ_i）を最適化する際に、前記多値変数による多値状態を二択変数（ｙ_i）を用いて２択により選択する２択最適化問題に変換した（Ｓ５１～Ｓ５４）後、
    請求項１から６の何れか一項に示す変数埋込方法を用いて前記ハードウェアグラフの頂点に前記二択変数を前記変数として埋込む変数埋込方法。
11. 前記多値問題の各多値変数について現状の多値状態を維持するか、又は、各多値変数についてランダムに選択した他の多値状態に遷移するか（Ｓ５１、Ｓ５２）の２択による前記２択最適化問題に変換する請求項１０記載の変数埋込方法。
12. 前記問題グラフ上で結合する前記多値変数（Ｓ_i、Ｓ_j）が同一の値である方が前記多値問題を評価する評価関数が最適化される場合、一の多値変数（Ｓ_i）の前記現状の多値状態か遷移先の前記他の多値状態の何れか少なくとも一以上が、前記一の多値変数（Ｓ_i）と結合する他の多値変数（Ｓ_j）の現状の多値状態又は遷移先の多値状態の何れか少なくとも一以上と同一状態となるように前記２択最適化問題を構築し、
    前記問題グラフ上で結合する前記多値変数が異なる値である方が前記評価関数が最適化される場合、一の多値変数の現状の多値状態か遷移先の前記他の多値状態の何れか又は双方が、前記一の多値変数と結合する他の多値変数の現状の多値状態及び遷移先の多値状態の両方と異なる多値状態となるように前記２択最適化問題を構築する請求項１１記載の変数埋込方法。
13. 頂点（Ｖ）の間の相互作用を表すハードウェアグラフ（Ｇ２）が特定の固定アーキテクチャにより構成された最適化問題の専用ハードウェア（１）を用いて、当該最適化問題の全ての変数を埋込不可能な大規模問題を解く場合について、当該最適化問題の変数の相互作用を問題グラフ（Ｇ１）に表して解く場合に、前記問題グラフの変数を前記専用ハードウェアの前記ハードウェアグラフの頂点に埋込むことが可能な部分問題に分割し、前記部分問題の最適化処理を繰り返すことで前記大規模問題を解くときに用いられる前記変数の埋込に係る処理システムであって、
    前記全ての変数のうち少なくとも一部を前記ハードウェアグラフの頂点に埋込むときに、
    前記最適化問題の変数を前記ハードウェアグラフの頂点へ重複割当を必要とするか否かを判定する判定部（７，Ｓ１２）と、
    前記重複割当を必要とする前記変数については前記部分問題の変数として用いることなく、前記重複割当の不要な前記変数を選択して前記ハードウェアグラフの頂点に埋込む埋込部（８，Ｓ１３）と、を備える処理システム。
14. 完全グラフ（Ｇ１ａ）を前記ハードウェアグラフに埋込むときの埋込方法に基づいて前記ハードウェアグラフの頂点を紐付ける紐付け部（Ｓ２１）と、
    前記ハードウェアグラフの上に前記変数を埋込むときに、当該変数が埋込まれる前記ハードウェアグラフの上で連結された部分グラフの中から少なくとも一つ以上の前記頂点を選択する選択部（Ｓ２６）と、
    前記ハードウェアグラフに前記変数（Ｘ１，Ｘａ）を埋込むときに、前記紐付けの内容に基づいて、前記選択した前記頂点から結合し且つその他の前記変数（Ｘ２～Ｘ９，Ｘｂ，Ｘｃ）との結合を増加させる前記頂点を、前記埋込む変数（Ｘ１，Ｘａ）に対応して予約することで当該埋込む変数（Ｘ１，Ｘａ）以外の前記その他の変数（Ｘ２～Ｘ９，Ｘ）の埋込みを禁止する禁止部（Ｓ２７）と、
    をさらに備える請求項１３記載の処理システム。
15. 前記その他の変数（Ｘ）の埋込みを禁止する過程を実行した後、前記問題グラフの上で埋込済変数（Ｘａ）に結合した全ての変数（Ｘｂ）の埋込処理が完了した後に前記予約を解消する解消部（Ｓ３７，Ｓ３８）、
    をさらに備える請求項１４記載の処理システム。
16. 前記ハードウェアグラフが、複数の頂点を備えた単位セル（Ｃ、Ｃ１１…Ｃ４４）を第１方向及び第２方向に沿って複数グリッド分だけ備えたキメラグラフにより構成される場合、一つの前記単位セル（Ｃ１１，Ｃ３３）の第１頂点（Ｖ１１，Ｖ１３）を基点として前記第１方向又は前記第２方向に結合する他の前記単位セル（Ｃ１２，Ｃ１３…、Ｃ３１，Ｃ３２，Ｃ３４…）に対応した頂点を第２頂点（Ｖ１１，Ｖ１３）として予約する予約部（Ｓ２２）をさらに備える請求項１４又は１５記載の処理システム。
17. 前記問題グラフの中で追加して埋込む前記変数を選択するときには、
    すでに埋込みされた埋込済の前記変数に結合された未埋込の前記変数の中から選択する請求項１３から１６の何れか一項に記載の処理システム。
18. 前記問題グラフの中で追加して埋込む前記変数を選択して前記ハードウェアグラフに埋込むときには、
    すでに埋込みされた埋込済の前記変数（Ｘａ）を一つ選択し（Ｓ３４）、前記選択した埋込済の変数に結合した前記変数（Ｘｂ）を選択して埋込処理を完了した後（Ｓ３５～Ｓ３７）、他の埋込済の前記変数を選択し（Ｓ３４）、当該選択した埋込済の変数（Ｘａ）に結合した前記変数（Ｘｂ）の埋込処理を繰り返す請求項１３から１７の何れか一項に記載の処理システム。
19. 前記大規模問題が、ワンホット制約又はワンコールド制約など一つだけ設けられた第一値がその他の全ての第二値と異なるように制約が設けられた二値変数（ｘ₁ ⁽¹⁾～ｘ₁ ^(Q)：ｘ_N ⁽¹⁾～ｘ_N ^(Q)）により表現される多値変数（Ｓ₁：Ｓ_N）を適用した多値問題であり、
    前記埋込部は、前記部分問題の変数として前記多値変数の中の少なくとも一部の前記二値変数を含むように選択して前記ハードウェアグラフの頂点に埋込むときには、前記第一値とされている前記二値変数が含まれるように前記二値変数を選択して前記ハードウェアグラフの頂点に埋込処理する請求項１３から１８の何れか一項に記載の処理システム。
20. 前記埋込部は、
    既に埋込処理が実行された前記多値変数（Ｓ₁）に前記問題グラフ上で結合する前記多値変数（Ｓ₂）の二値変数（ｘ₂）を前記ハードウェアグラフの頂点に追加で埋込処理するときには、
    前記多値変数を表現する前記二値変数の中で、前記埋込済の前記二値変数に前記問題グラフ上で結合している前記二値変数、又は、前記第一値とされている条件を満たす前記二値変数、を優先的に埋込む請求項１９記載の処理システム。
21. 前記第一値とされている前記二値変数を埋込不能と判定した場合（Ｓ６５ａでＮＯ）、又は、前記選択した多値変数を表現する全ての前記二値変数の中で２つ以上埋込不能と判定した場合（Ｓ６８でＮＯ）には、当該二値変数により表現される前記多値変数の全体の前記埋込部による埋込みを無効とし、先に埋込まれた前記二値変数を前記部分問題から除去する無効化処理部（Ｓ６９）をさらに備える請求項１９又は２０記載の処理システム。
22. 前記大規模問題が、ワンホット（one-hot）制約又はワンコールド（one-cold）制約など一つだけ設けられた第一値がその他の全ての第二値と異なるように制約が設けられた二値変数（ｘ₁ ⁽¹⁾～ｘ₁ ^(Q)：ｘ_N ⁽¹⁾～ｘ_N ^(Q)）により表現される多値変数（Ｓ₁：Ｓ_N）を適用した多値問題であり、
    前記多値問題の多値変数（Ｓ_i）を最適化する際に、前記多値変数による多値状態を二択変数（ｙ_i）を用いて２択により選択する２択最適化問題に変換する変換部（Ｓ５１～Ｓ５４）を備え、
    前記変換部が前記多値問題を前記２択最適化問題に変換した後、前記埋込部は請求項１３から１８の何れか一項に示す処理システムを用いて前記ハードウェアグラフの頂点に前記二択変数を前記変数として埋込む処理システム。
23. 前記多値問題の各多値変数について現状の多値状態を維持するか、又は、各多値変数についてランダムに選択した他の多値状態に遷移するか（Ｓ５１、Ｓ５２）の２択による前記２択最適化問題に変換する請求項２２記載の処理システム。
24. 前記問題グラフ上で結合する前記多値変数が同一の値である方が前記多値問題を評価する評価関数が最適化される場合、前記一の多値変数（Ｓ_i）の現状の多値状態か遷移先の前記他の多値状態の何れか少なくとも一以上が、前記一の多値変数と結合する他の多値変数（Ｓ_j）の現状の多値状態又は遷移先の多値状態の何れか少なくとも一以上と同一状態となるように前記２択最適化問題を構築し、
    前記問題グラフ上で結合する前記多値変数が異なる値である方が前記評価関数が最適化される場合、一の多値変数の現状の多値状態か遷移先の前記他の多値状態の何れか又は双方が、前記一の多値変数と結合する他の多値変数の現状の多値状態及び遷移先の多値状態の両方と異なる多値状態となるように前記２択最適化問題を構築する請求項２３記載の処理システム。

Images