(57)【要約】【課題】デジタルアニーリングまたは量子アニーリングを用いて多変数二次問題を解く方法および／またはシステムを提供する。【解決手段】  本方法は、多変数二次問題に関連する一連の多変数二次多項式を取得することと、多変数二次多項式に基づいてイジングモデル結合重み行列Ｗとイジングモデルバイアスベクトルｂとを生成することとを含んでも良い。また、本方法は、行列Ｗおよびベクトルｂを、イジングモデルによって記述された問題を解くように構成されたアニーリングシステムに提供することと、一組の整数を表すアニーリングシステムからの出力を取得することとを含んでもよい。また、本方法は、一組の整数を多変数二次問題に対する解として用いることを含んでもよい。【選択図】図１
2020119548.tif 000002
【特許請求の範囲】
【請求項１】
多変数二次問題に関連する一連の多変数二次多項式を取得することと、
イジングモデル重み行列とイジングモデルバイアスベクトルとを生成する、前記行列の少なくとも１つの要素は一組の多変数二次多項式に基づいて決定されることと、
前記行列およびベクトルを、イジングモデルによって記述された問題を解くように構成されたアニーリングシステムに提供することと、
一組の整数を表す前記アニーリングシステムからの出力を取得することと、
前記一組の整数を、前記一組の多変数二次多項式によって定められる前記多変数二次問題の解として使用することとを含む、
方法。
【請求項２】
前記アニーリングシステムは、前記出力を生成するために使用されるエネルギー値を計算するように構成されたエネルギー値計算回路を含み、前記エネルギー値は、前記行列の前記要素の１つ以上の値に基づく、
請求項１に記載の方法。
【請求項３】
イジングモデル結合重み行列とイジングモデルバイアスベクトルとを生成することは、
前記一組の多変数二次多項式の各多項式を線形化することを含む、
請求項１に記載の方法。
【請求項４】
イジングモデル結合重み行列とイジングモデルバイアスベクトルとを生成することは、
線形化された多項式の十分な倍数（ｓｕｆｆｉｃｉｅｎｔ  ｍｕｌｔｉｐｌｅｓ）を除去することにより丸めるために、線形化された多項式を調整することをさらに含む、
請求項３に記載の方法。
【請求項５】
イジングモデル結合重み行列とイジングモデルバイアスベクトルとを生成することは、
線形化され調整された多項式のエネルギー関数を計算することをさらに含む、
請求項４に記載の方法。
【請求項６】
前記一組の多変数二次多項式の集合は、多変数暗号方式に基づき、前記多変数二次問題に対する解を用いて、前記多変数暗号方式に対するチャレンジを実行することをさらに含む、
請求項１に記載の方法。
【請求項７】
システムの１つ以上のプロセッサに、
多変数二次問題に関連する一連の多変数二次多項式を取得することと、
イジングモデル重み行列とイジングモデルバイアスベクトルとを生成する、前記行列の少なくとも１つの要素は一組の多変数二次多項式に基づいて決定されることと、
前記行列およびベクトルを、イジングモデルによって記述された問題を解くように構成されたアニーリングシステムに提供することと、
一組の整数を表す前記アニーリングシステムからの出力を取得することと、
前記一組の整数を、前記一組の多変数二次多項式によって定められる前記多変数二次問題の解として使用することとを実行させる、
コンピュータプログラム。
【請求項８】
システムであって、
命令を記憶するように構成された１つ以上のコンピュータ可読記憶媒体と、
システムに動作を実行させるように構成された、前記１つ以上のコンピュータ可読記憶媒体に通信可能に結合され、前記命令の実行に応答して、前記システムに動作を実行させる１つ以上のプロセッサとを有し、
前記動作は、
多変数二次問題に関連する一連の多変数二次多項式を取得することと、
イジングモデル重み行列とイジングモデルバイアスベクトルとを生成する、前記行列の少なくとも１つの要素は一組の多変数二次多項式に基づいて決定されることと、
前記行列およびベクトルを、イジングモデルによって記述された問題を解くように構成されたアニーリングシステムに提供することと、
一組の整数を表す前記アニーリングシステムからの出力を取得することと、
前記一組の整数を、前記一組の多変数二次多項式によって定められる前記多変数二次問題の解として使用することとを含む、
システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本明細書で説明する実施形態は、デジタルアニーリングまたは量子アニーリングを用いて多変数二次問題を解く方法および／またはシステムに関する。
【背景技術】
【０００２】
多変数二次多項式は、解くのが難しい問題のクラスに含まれる。結果として、多変数二次多項式問題と対応するそれらの解は、暗号学や暗号解析などの種々の技術分野で使用され得る。
【０００３】
特許請求の範囲に記載した主題は、何らかの欠点を解消する実施形態や、上記のような環境のみで動作する実施形態に限定されない。むしろ、この背景技術は、この明細書に説明する幾つかの実施形態を実施できる技術分野例を示すだけである。
【発明の概要】
【０００４】
一実施形態の一態様では、方法は、一組の多変数二次多項式を取得することと、イジングモデル結合重み行列Ｗを生成することとを含んでもよい。幾つかの実施形態では、行列「Ｗ」およびイジングモデルバイアス係数「ｂ」の少なくともいくつかの要素は、一組の二次多項式に基づいて決定されてもよい。また、本方法は、前記行列Ｗおよびベクトルｂを、前記イジングモデルによって記述された問題を解くように構成されたアニーリングシステムに提供することと、一組の値を表す前記アニーリングシステムからの出力を取得することとを含んでもよい。また、本方法は、前記一組の値を前記多変数二次多項式問題に対する解として用いることを含んでもよい。
【０００５】
実施形態の目的と利点は、少なくとも、特許請求の範囲に具体的に記載した要素、特徴、及び組み合わせにより実現及び達成される。
【０００６】
上記の概要と、下記の詳細な説明とは、例であり、説明をするためのものであり、特許請求の範囲に記載された発明を制限するものではない。
【図面の簡単な説明】
【０００７】
添付した図面を用いて、実施形態の例をさらに具体的に詳しく説明する。
【０００８】
【図１】多変数二次多項式問題の解法に関する例示的な環境を示す。
【０００９】
【図２】多変数二次多項式問題を解くように構成することができる計算システムの例を示す。
【００１０】
【図３】多変数二次多項式問題を解く例示的な方法を示すフローチャートである。
【００１１】
【図４】一組の多変数二次多項式に基づいて、イジングモデル結合重み行列Ｗおよびイジングモデルバイアスベクトルｂを生成する例示的な方法を示すフローチャートである。
【発明を実施するための形態】
【００１２】
多変数二次（ＭＱ）多項式問題は、暗号システム、暗号解析その他を含む種々の応用を有する最適化問題のクラスを含み得る。より具体的には、ＭＱ問題を解くことが困難であり、その結果として多くの暗号システムがＭＱ問題に基づいている。それらは一般に、攻撃を成功させるにはあまりにも難しく、計算コストがかかるからである。しかしながら、近年、デジタルアニーリングシステムおよび量子アニーリングシステムが提案されている。これらは、発見的アプローチを用いて、古典的なコンピューティングシステムおよび技術よりも高速に、ＭＱ問題のような最適化問題に対する解を得ることができる。このように、デジタルまたは量子アニーリングシステムは、ＭＱ問題を解くのに役立ち、暗号解析などのいくつかの技術分野を改善する可能性がある。簡潔にするために、デジタルアニーラーおよび／または量子アニーラーを参照するときは、併せて「アニーラー」と呼ぶ。
【００１３】
いくつかの実施形態において、ＭＱ問題を解くために典型的に使用される入力は、アニーリングシステムがＭＱ問題を効率的に解くことを可能にするような方法では構成されないことがある。いくつかの実施形態において、ＭＱ問題を解くためにイジングモデルを使用してもよいが、ＭＱおよびイジングモデル問題は、入力を効率的にリダクション（ｒｅｄｕｃｅ）する方法で変換される必要がある場合がある。従って、本開示の１つ以上の態様によれば、ＭＱ問題を解くために再入力され得るイジングモデル入力を得るために、ＭＱ問題に関して１つ以上の操作を実行することができる。
【００１４】
このように、本開示の１つ以上の実施形態によれば、本明細書で説明する操作により、アニーリングシステムが元のＭＱ方程式およびイジングモデル問題の両方を効率的にリダクションすることを用いて、ＭＱ問題を解くことを可能にするメカニズムを提供することによって、アニーリングシステムを改良することができる。いくつかの実施態様において、本方法の効率は、アニーラーの効率に関連する。本明細書で説明する方法は、一般的なリダクションを組み込むことなく、インスタンスサイズにおける多項式のブローアップを最小限に抑える。これは効率の指数関数的な劣化を生じさせる可能性がある。しかしながら、以下に説明する他の実施形態では、本方法は、効率を増加させるリダクションを含んでもよい。
【００１５】
本開示の実施形態を、添付した図面を参照して説明する。
【００１６】
図１は、本開示で説明する少なくとも１つの実施形態により構成される、アニーリングシステムを用いてＭＱ問題を解くのに関する例示的な環境１００を示す図である。環境１００は、イジングモデル入力モジュール１０２（「入力モジュール１０２」）、イジングモデルモジュール１０６（「イジングモジュール１０６」）、およびイジングモデル出力モジュール１１２（「出力モジュール１１２」）を含んでもよい。
【００１７】
入力モジュール１０２、イジングモジュール１０６、および／または出力モジュール１１２は、コード及びルーチンで記述された動作の１つ以上を計算装置が実行することを可能にするように構成されたコードおよびルーチンを含んでもよい。追加的にまたは代替的に、入力モジュール１０２、イジングモジュール１０６、および／または出力モジュール１１２は、任意の数のプロセッサ、（例えば、１つ以上の動作のパフォーマンスを実行または制御するため）マイクロプロセッサ、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、特定用途向け集積回路（ＡＳＩＣ）、またはそれらの２つ以上の任意の適切な組み合わせを含むハードウェアを使用して実装されてもよい。
【００１８】
代替的または追加的に、入力モジュール１０２、イジングモジュール１０６、および／または出力モジュール１１２は、ハードウェアおよびソフトウェアの組み合わせを使用して実装されてもよい。本開示において、入力モジュール１０２、イジングモジュール１０６、および／または出力モジュール１１２によって実行されると説明する動作は、入力モジュール１０２、イジングモジュール１０６、および／または出力モジュール１１２が、対応するシステムに実行を指示する動作を含んでもよい。
【００１９】
いくつかの実施形態では、入力モジュール１０２、イジングモジュール１０６、および出力モジュール１１２は、それぞれ、アニーリングシステム（例えば、デジタルアニーリングシステムまたは量子アニーリングシステム）に含まれてもよい。追加的にまたは代替的に、イジングモジュール１０６はアニーリングシステムに含まれてもよく、入力モジュール１０２および出力モジュール１１２のうちの１つ以上はアニーリングシステムとインターフェースするように構成された別個のシステムに含まれてもよい。さらに、入力モジュール１０２、イジングモジュール１０６、および出力モジュール１１２は、本開示の説明を容易にするために、別個の要素として図示され説明される。このように、入力モジュール１０２、イジングモジュール１０６、および出力モジュール１１２によって実行されると説明する動作を実行するように構成された任意の適切なハードウェアおよび／またはソフトウェア構成は、本開示の範囲内にある。
【００２０】
多変数二次多項式方程式系は、ｍ個の同時二次多項式の集合Ｓであり、ここでｍ個の二次多項式はいくつかの体（ｆｉｅｌｄ）ｋにわたる、ｘ１、．．．、ｘｎのようないくつかの変数を含む。多項式系の解は、ｋのいくつかの代数的に閉じた体の拡大Ｋに属するｘｉの値の集合であり、すべての方程式を真にする。ｋが有理数体であるとき、Ｋは一般に複素数体であると仮定される。なぜなら、各解は、ｋの体拡大に属し、複素数の部分体（ｓｕｂｆｉｅｌｄ）と同型だからである。
【００２１】
いくつかの実施形態において、ＭＱ問題は、非決定性多項式時間完全（ＮＰ完全）問題であり得る。これらの実施形態および他の実施形態において、ＭＱ問題に関して、提案された解が正しいかどうかを確認することは容易であるが、解が存在するかどうかを判断することは困難である。より詳細には、ＮＰ完全問題に対する解は検証が容易であるが、迅速に解を見つけることは困難である。このように、既知のアルゴリズムを用いて問題を解くのに必要な時間は、問題のサイズが大きくなるにつれて急速に増加する。
【００２２】
いくつかの実施形態では、ＭＱ問題入力１０４は、ｍ個の二次多変数多項式の集合Ｓを含んでいてもよい。いくつかの例では、ＭＱ問題入力１０４を入力モジュール１０２に提供してもよい。
【００２３】
入力モジュール１０２は、イジングモデル入力１１０を生成するために、ＭＱ問題入力１０４に関して１つ以上の動作を実行するように構成されてもよい。入力モジュール１０２は、イジングモデル入力１１０がＭＱ問題を解くためにイジングモジュール１０６によって使用されるように、イジングモデル入力１１０を生成するように構成してもよい。
【００２４】
例えば、イジングモジュール１０６は、Ｍａｒｋｏｖチェーンモンテカルロ（ＭＣＭＣ）確率的探索を実行して、イジングエネルギーを最小化するイジングエネルギーの次の式
【数１】
2020119548.tif 000003
において出力ベクトル「Ｘ」を見つけることによって、イジングエネルギーを最小化するように構成することができる。ここで、ｘｉ∈｛０，１｝は状態変数またはビットであり、Ｘ＝（ｘ１，ｘ２，．．．ｘＮ）は状態変数のベクトル表示であり、Ｎはビット数であり、「Ｗ」は出力ベクトル「ｘ」の複数の要素間の結合を重み付けるイジングモデル結合重み行列であり、「ｂ」はイジングエネルギー決定に使われるバイアスベクトルである。
【００２５】
いくつかの実施形態において、イジングモジュール１０６は、１つ以上のイジングユニットを含んでもよい情報処理装置を含んでもよい。イジングユニットは、ＤｅＧｌｏｒｉａアルゴリズムなどのアルゴリズムに基づく小規模ハードウェアによってニューラルネットワークのイジング型エネルギー関数の動作を実行するように構成されてもよい。行列Ｗの要素は、ニューラルネットワークのニューロン間の重み付け値を含んでもよい。例えば、行列Ｗの要素は、行列Ｗの行数で表される第１のニューロンと、行列Ｗの列数で表される第２のニューロンとの間の重み付け値を含んでもよく、行列番号および列番号は要素を特定する。情報処理装置は、ニューラルネットワークのエネルギーを最小化して、行列Ｗおよびベクトルｂによって表される問題に対する解を決定するように動作することができる。
【００２６】
イジングユニットを含む情報処理装置の例は、２０１７年８月３０日に出願された米国公開第２０１８／００７５３４２号に記載されている。その全体を本開示に参照援用する。米国公開第２０１８／００７５３４２号に記載されているように、イジングユニットは、エネルギー値計算回路および状態遷移決定回路を含んでもよい。エネルギー値計算回路は、エネルギー値を計算するように構成されてもよい。これは情報処理装置の出力を生成するために使用され得る行列「Ｗ」の１つ以上の要素の値に基づく。出力は、行列Ｗおよびベクトルｂによって表される問題に対する解を含んでもよい。状態遷移決定回路のさらなる情報および例は、２０１７年９月２８日に出願された米国公開第２０１８／０１０７１７２号に記載されている。その全体は本開示に参照援用する。
【００２７】
いくつかの実施形態では、入力モジュール１０２は、ＭＱ問題入力１０４に基づいて、イジングモデル結合重み行列「Ｗ」およびバイアスベクトル「ｂ」を生成するように構成されてもよい。どのようにしてイジングモデル結合重み行列「Ｗ」およびバイアスベクトル「ｂ」が生成され得るかの一例を、図４を参照して以下により詳細に説明する。
【００２８】
計算された行列Ｗおよびベクトルｂは、イジングモデル入力１１０として計算されてもよい。イジングモデル入力１１０を、イジングモジュール１０６に提供してもよい。
【００２９】
これらまたは他の実施形態では、入力モジュール１０２は、イジングモデル入力１１０をイジングモジュール１０６に提供するように構成されてもよい。イジングモジュール１０６は、上述のイジング最適化モデルに従って書かれた最適化問題を解くように構成することができる。加えて、上述したように、イジングモジュール１０６は、アニーリングシステムの一部であってもよく、その結果、アニーリングシステムは、イジング最適化モデルを使用して、古典的に構成された計算システムよりもはるかに速い方法で最適化問題を解くことができる。これらの実施形態または他の実施形態では、イジングモジュール１０６は、最適化問題の解としてイジングモデル出力１０８を生成するように構成されてもよい。
【００３０】
上述のようにＭＱ問題の多変数二次多項式の集合Ｓに従って決定される、決定された重み行列「Ｗ」および決定されたバイアスベクトル「ｂ」に基づいて、イジングモジュール１０６は、ｎｌｏｇｑビットを有する出力ベクトル
（外１）
2020119548.tif 000004
を決定するように構成されてもよく、ここでビットの整数への二値再構成はＭＱ問題の解を表す。このように、アニーリングシステムは、イジングモジュール１０６と、入力モジュール１０２によって生成されたモデル入力１１０とを使用して、ＭＱ問題を解くことができる。これらの実施形態または他の実施形態では、出力ベクトルは、イジングモデル出力１０８に含まれてもよい。
【００３１】
いくつかの実施形態において、イジングモジュール１０６は、２進表現でイジングモデル出力１０８を生成するように構成されてもよい。これらの実施形態または他の実施形態では、出力モジュール１１２は、イジングモデル出力１０８を受け取ってもよい。出力モジュール１１２は、イジングモデル出力１０８をバイナリ表現から一連の整数に変換するように構成することができ、この整数はＭＱ問題解１１４として出力することができる。
【００３２】
いくつかの実施形態では、ＭＱ問題解１１４は、様々な状況で使用され得る。例えば、ＭＱ問題は、暗号学において使用され得る。図１を参照して説明したプロセスを用いて、多変数二次多項式の集合に対するＭＱ問題の解を決定してもよい。解と乱数整数集合とを一緒に、暗号構成における公開鍵／秘密鍵として用いてもよい。
【００３３】
代替的にまたは追加的に、ＭＱ解を使用する暗号構成を研究するために、ＭＱ問題解１１４を暗号解析に使用することができる。これらの実施形態及びその他の実施形態では、なかんずく、ＭＱ問題解１１４を用いて暗号構成に対する代替的な可能性のある解を決定してもよい。
【００３４】
本開示の範囲から逸脱することなく、図１に修正、追加、または削除をすることができる。例えば、環境１００が含む要素は、本開示で例示及び説明した要素より多くても少なくてもよい。
【００３５】
図２は、本開示の少なくとも１つの実施形態による、ＲＭＳＳ関連問題を解くように構成された例示的な計算システム２０２のブロック図を示す。計算システム２０２は、イジングモデル入力モジュール（例えば、図１の入力モジュール１０２）、イジングモデルモジュール（例えば、図１のイジングモジュール１０６）、および／またはイジングモデル出力モジュール（例えば、図１の出力モジュール１１２）に関連する１つ以上の動作を実装または指示するように構成されてもよい。いくつかの実施形態において、計算システム２０２は、アニーリングシステムに含まれてもよく、またはアニーリングシステムの一部を形成してもよい。計算システム２０２は、プロセッサ２５０、メモリ２５２、およびデータストレージ２５４を含んでいてもよい。プロセッサ２５０、メモリ２５２、およびデータストレージ２５４は、通信できるように結合されていてもよい。
【００３６】
一般的に、プロセッサ２５０は、任意の好適な特定目的又は汎用コンピュータ、計算エンティティ、又は様々なコンピュータハードウェア又はソフトウェアモジュールを含む処理デバイスを含んでもよく、任意の適用し得るコンピュータ読み取り可能ストレージメディアに格納された命令を実行するように構成されていてもよい。例えば、プロセッサ２５０は、マイクロプロセッサ、マイクロコントローラ、デジタル信号プロセッサ（ＤＳＰ）、特定用途集積回路（ＡＳＩＣ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、又はプログラム命令を解釈及び／又は実行する、及び／又はデータを処理するように構成されたその他のデジタル又はアナログ回路を含んでもよい。図２には１つのプロセッサとして例示したが、プロセッサ２５０は、本開示で説明した任意数の動作を個別に又は集合的に実行するように構成された、又はその実行を命令するように構成された任意数のプロセッサを含んでいてもよい。さらに、１つ以上のプロセッサが、１つ以上の異なる電子デバイス、例えば、異なるサーバ上にあってもよい。
【００３７】
幾つかの実施形態では、プロセッサ２５０は、プログラム命令を解釈及び／又は実行し、及び／又はメモリ２５２に、データストレージ２５４に、又はメモリ２５２とデータストレージ２５４とに格納されたデータを処理してもよい。幾つかの実施形態では、プロセッサ２５０は、データストレージ２５４からプログラム命令をフェッチし、そのプログラム命令をメモリ２５２にロードしてもよい。プログラム命令がメモリ２５２にロードされた後、プロセッサ２５０は、そのプログラム命令を実行してもよい。
【００３８】
メモリ２５２とデータストレージ２５４は、コンピュータ実行可能命令またはデータ構造を担うまたは有するコンピュータ可読記憶媒体を含んでいてもよい。かかるコンピュータ可読記憶媒体は、汎用又は特定用途コンピュータシステム、例えばプロセッサ２５０によりアクセスできる利用可能などんな媒体であってもよい。限定ではなく一例として、かかるコンピュータ読み取り可能媒体は、有形または非一時的コンピュータ読み取り可能記憶媒体を含み、これはランダムアクセスメモリ（ＲＡＭ）、リードオンリーメモリ（ＲＯＭ）、電気的消去可能プログラマブルリードオンリーメモリ（ＥＥＰＲＯＭ）、コンパクトディスクリードオンリーメモリ（ＣＤ−ＲＯＭ）、又はその他の光ディスクストレージ、磁気ディスクストレージ、その他の磁気ストレージデバイス、フラッシュメモリデバイス（例えば、ソリッドステートメモリデバイス）、又はその他の任意の非一時的ストレージ媒体であってプログラムコードを、汎用又は特殊用途コンピュータによりアクセスしてもよいコンピュータ実行可能命令又はデータ構造の形式で担う又は格納するのに用いられるものを含む。これらおよび他の実施形態では、本開示で説明する「非一時的」という用語は、連邦巡回裁判所決定Ｉｎ  ｒｅ  Ｎｕｉｊｔｅｎ（５００  Ｆ．３ｄ  １３４６  （Ｆｅｄ．  Ｃｉｒ．  ２００７））において特許可能な主題の範囲外にあるとされた一時的媒体の種類のみを排除すると解釈されるべきである。上記のものの組合せは、コンピュータ可読媒体の範囲内に含まれていてもよい。
【００３９】
上記のものの任意の組合せを、コンピュータ読み取り可能ストレージ媒体の範囲内に含んでもよい。コンピュータ実行可能命令は、例えば、プロセッサ２５０に、ある動作又は動作のグループを実行させるように構成された命令及びデータを含んでも良い。
【００４０】
本開示の範囲から逸脱することなく、計算システム２０２に修正、追加、または削除をすることができる。例えば、幾つかの実施形態では、計算システム２０２は、明示的には図示または説明しないその他の任意数のコンポーネントを含んでいてもよい。
【００４１】
図３は、本開示に記載される少なくとも１つの実施形態によるＭＱ問題を解く例示的方法３００のフローチャートを示す。方法３００は、好適なシステム、装置またはデバイスにより実行されてもよい。例えば、図１の環境１００、又は図２の計算システム２００は、方法３００に関連する複数の動作の１つ以上を実行してもよい。離散的なブロックで図示したが、方法３００の複数のブロックの１つ以上に関連するステップ及び動作は、具体的な実装に応じて、複数の追加ブロックに分割されても、結合されてより少数のブロックになっても、削除されてもよい。
【００４２】
方法３００はブロック３０２で開始してもよく、ある体ｋ上のｍ個の同時二次多項式方程式の集合Ｓが得られてもよい。ブロック３０４では、イジングモデル結合重み行列「Ｗ」およびイジングモデルバイアス係数「ｂ」が生成されてもよい。いくつかの実施形態において、行列「Ｗ」およびイジングモデルバイアス係数「ｂ」の少なくともいくつかの要素は、一組の二次多項式方程式に基づいて決定されてもよい。
【００４３】
ブロック３０６において、行列「Ｗ」およびベクトル「ｂ」を、イジングモデルによって記述された問題を解くように構成されたアニーリングシステムに提供してもよい。ブロック３０８では、多変数二次多項式の集合によって定義されるＭＱ問題の解として使用され得る整数の集合に対応するベクトルを表す出力が、アニーリングシステムから得ることができる。いくつかの実施形態では、一組（ｓｅｔ）の多変数二次多項式は、暗号ハッシュ技術から得られてもよく、一組（ｓｅｔ）の整数を使用することは、暗号ハッシュ技術を適用するシステムにその一組の整数を提供して、そのシステムにアクセスすることを含んでもよい。
【００４４】
図４は、本開示で説明する少なくとも１つの実施形態による、イジングモデル重みマトリックス「Ｗ」およびイジングモデルバイアスベクトル「ｂ」を生成する例示的方法４００のフローチャートを示す。方法４００は、好適なシステム、装置またはデバイスにより実行されてもよい。例えば、図１の環境１００または図２の計算システム２００は、方法４００に関連する複数の動作のうちの１つ以上を実行してもよく、言うまでもなく図４の方法４００は、図３の方法３００に関連して使用され得る。離散的なブロックで図示したが、方法４００の複数のブロックの１つ以上に関連するステップ及び動作は、具体的な実装に応じて、複数の追加ブロックに分割されても、結合されてより少数のブロックになっても、削除されてもよい。
【００４５】
方法４００はブロック４０２で開始してもよく、ある体ｋ上のｎ個の変数ｘ１，・・・ｘｎのｍ個の同時二次多項式方程式の集合Ｓが得られてもよい。この場合、集合Ｓは、基礎体上でＦ２上のｐｉ，ｉ∈［ｍ］と定義することができる。ブロック４０４において、集合Ｓの各多項式は線形化される。例えば、各ｊ，ｋ∈［ｎ］に対して、各多項式ｐｉが
【数２】
2020119548.tif 000005
と表されるように、変数ｙｊｋ＝ｘｊｘｋを導入する。
【００４６】
ブロック４０４では、線形展開（ｌｉｎｅａｒ  ｅｘｐａｎｔｉｏｎ）されたｐｉは、ｐｉの集合から十分な２の倍数を削除することにより丸めるよう調整される。より具体的には、ブロック４０４で以下の操作を行う：
【数３】
2020119548.tif 000006
【００４７】
幾つかの実施形態では、丸め（ｒｏｕｎｄｉｎｇ）のために適切に調節するにはｔ＝３［ｌｏｇｎ］で十分であると判定されてもよいが、他の値のｔを使ってもよい。ブロック４０４において実行される動作において、ｂｊ項はアニーラーにより割り当てられる二値変数である。それらは、アニーラーに送られる多項式方程式に含まれるビットであり、それらの値により、絶対解からモジュラー解への動きが可能になる。
【００４８】
一実施形態では、ブロック４０４における変数の展開の後、多項式は、特性ｑのモジュロで低減される。当業者には言うまでもなく、これにより、ステップ４０６の丸め調整を実行するために必要なビット数を減少させる。
【００４９】
別の実施形態では、基礎体Ｆ２に対して、
（外２）
2020119548.tif 000007
の係数値を表すように、［−１，１］から均一サンプルを選択してもよい。ｑを奇素数として基礎体Ｆｑに対して、Ｆｑにおける値の表現は
（外３）
2020119548.tif 000008
から選択してもよい。平均して、この動作により丸め調整を実行するのに必要なビット数が削減される。
【００５０】
言うまでもなく、このプロセスは、ＭＱ問題の絶対解を要求するのではなく、ｍｏｄ（２）のみで解を要求することによって、イジングモデルによって要求される計算を最小化するように実行され得る。ある場合には、多項式はｍｏｄ（３１）のような拡大体上で定義することもできる。このように、単に２の倍数を除去する代わりに、
【数４】
2020119548.tif 000009
を行うことにより、３１の倍数も除去することができる。このような場合、各多項式方程式は、ｒ個の別個の多項式に分解され得る。ここで、ｒは拡大度（ｄｅｇｒｅｅ  ｏｆ  ｅｘｔｅｎｓｉｏｎ）である。具体的に、２度拡大体
（外４）
2020119548.tif 000010
を考える。Ｆの任意の要素はα２＝−α−１および
（外５）
2020119548.tif 000011
として、＝ｘ１α１＋ｘ０と書くことができる。（ｘ１α＋ｘ２）、（ｘ３α＋ｘ４）∈Ｆをかけると、
【数５】
2020119548.tif 000012
となる。
【００５１】
結果として、各二次多項式ｐはｐ１α＋ｐ２と分解される。このように、ｐ１およびｐ２は基礎体Ｆ（２）において別個の二次多項式として扱ってもよい。
【００５２】
図４に戻り、ブロック４０８において、すべてのｉ＜ｊ∈［ｎ］に対して、多項式ｐｉのエネルギー関数を
【数６】
2020119548.tif 000013
により定義し、次のエネルギー関数
【数７】
2020119548.tif 000014
を計算する。
【００５３】
ステップ４１０において、イジングモデル重み行列「Ｗ」とイジングモデルバイアスベクトル「ｂ」がエネルギー関数Ｈを展開（ｅｘｐａｎｄ）して計算される。このように、図３のステップ３０６で説明したように、イジングモデル重み行列「Ｗ」とイジングモデルバイアスベクトル「ｂ」をアニーリングシステムに提供することができる。
【００５４】
本開示の範囲から逸脱することなく、方法４００に修正、追加、または削除をすることができる。例えば、方法４００の動作（ｏｐｅｒａｔｉｏｎｓ）は異なる順序で実装してもよい。追加的にまたは代替的に、２つ以上の動作を同時に実行してもよい。さらに、概要を述べた動作とアクションは、単なる例であり、開示された実施形態の本質を損なうことなく、その動作とアクションのうち幾つかは、任意的であり、結合されてより少ない動作とアクションにされてもよく、拡張されてより多くの動作とアクションにされてもよい。
【００５５】
ここで、「モジュール」又は「コンポーネント」との用語は、計算システムの汎用ハードウェア（例えば、コンピュータ読み取り可能媒体、プロセッサデバイスなど）により格納及び／又は実行され得るモジュール又はコンポーネント、及び／又はソフトウェアオブジェクト又はソフトウェアルーチンを実行するように構成されたハードウェア実施形態を指してもよい。幾つかの実施形態では、ここに説明する異なるコンポーネント、モジュール、エンジン、及びサービスは、（例えば、別のスレッドとして）計算システム上で実行されるオブジェクト又はプロセスとして実施してもよい。ここに説明のシステムと方法の幾つかは、概して（汎用ハードウェアにより格納及び／又は実行される）ソフトウェアで実装されると説明したが、ハードウェアの実施形態、又はソフトウェアとハードウェアの実施形態の組み合わせも可能であり、想定されている。本明細書において、「計算エンティティ（ｃｏｍｐｕｔｉｎｇ  ｅｎｔｉｔｙ）」とは、ここで定義したどの計算システムであってもよく、計算システム上で実行されているどのモジュール又はモジュールの組み合わせであってもよい。
【００５６】
本開示に用い、特に添付した特許請求の範囲で用いる用語は、一般的に「オープン」タームであることが意図されている（例えば、用語「含む」は「含むが限定されない」と解釈すべきであり、用語「有する」は「少なくとも〜を有する」と解釈すべきであり、用語「含む」は「含むが限定されない」と解釈すべきである。
【００５７】
また、請求項において数を特定しようと意図する場合は、請求項中に明示的に記載し、そうでなければ、そのような意図はない。例えば、理解の助けとして、下記に添付した特許請求の範囲は、その記載に「少なくとも１つの」や「１つ以上の」との導入句を含んでいることがある。しかし、かかるフレーズの使用は、不定冠詞「ａ」または「ａｎ」を付けることが、たとえ同じ請求項が「１つ以上の」又は「少なくとも１つの」という導入句と「ａ」や「ａｎ」などの不定冠詞を含んでいたとしても、かかる請求項記載を含む請求項を、かかる記載を１つだけ含む実施形態に限定することを示唆していると解してはならない。（例えば、「ａ」及び／又は「ａｎ」は「少なくとも１つの」又は「１つ以上の」を意味するものと解釈すべきである）；請求項記載を導入する定冠詞の使用についても同様である。
【００５８】
また、導入された請求項記載について特定の数が明示的に記載されていたとしても、当業者には言うまでもなく、かかる記載は少なくとも記載された数という意味と解釈すべきである（例えば、他の修飾語を付けずに「２つの」と言った場合、これは少なくとも２つ、すなわち２以上を意味する）。さらに、「Ａ，Ｂ，及びＣなどのうち少なくとも１つ」又は「Ａ，Ｂ、及びＣなどのうち１つ以上」などの表現を用いる場合、一般的に、かかる表現は、Ａのみ、Ｂのみ、Ｃのみ、ＡとＢ、ＡとＣ、ＢとＣ、又はＡとＢとＣなどを含むことを意図している。また「及び／又は」との言葉の使用は、このように解釈することを意図している。
【００５９】
さらに、２以上の代替的用語を提示する宣言的単語又は句は、明細書、特許請求の範囲、又は図面にかかわらず、その用語のうち一つ、その用語のどちらか、又は両方の用語を含む可能性を想定していると理解すべきである。例えば、「及び／又は」と言う用語が他で使われていても、「ＡまたはＢ」は、「Ａ」、または「Ｂ」、又は「Ａ及びＢ」の可能性を含むと理解すべきである。
【００６０】
本開示に記載したすべての例と条件付きの言葉は、発明者が技術発展に対してなした本開示とコンセプトとを、読者が理解しやすいようにするためのものであり、その解釈は具体的に記載した実施例や条件に限定されるべきではない。本開示の実施形態を詳細に説明したが、言うまでもなく、本開示の精神と範囲から逸脱することなく、これらの実施形態に変更、置換、代替を施すことができる。
【００６１】
上記の実施形態について付記する。
（付記１）
多変数二次問題に関連する一連の多変数二次多項式を取得することと、
イジングモデル重み行列Ｗとイジングモデルバイアスベクトルｂとを生成する、前記行列Ｗの少なくとも１つの要素は一組の多変数二次多項式に基づいて決定されることと、
前記行列Ｗおよびベクトルｂを、イジングモデルによって記述された問題を解くように構成されたアニーリングシステムに提供することと、
一組の整数を表す前記アニーリングシステムからの出力を取得することと、
前記一組の整数を、前記一組の多変数二次多項式によって定められる前記多変数二次問題の解として使用することとを含む、
方法。
（付記２）
前記アニーリングシステムは、前記出力を生成するために使用されるエネルギー値を計算するように構成されたエネルギー値計算回路を含み、前記エネルギー値は、前記行列Ｗの前記要素の１つ以上の値に基づく、
付記１に記載の方法。
（付記３）
イジングモデル結合重み行列Ｗとイジングモデルバイアスベクトルｂとを生成することは、
前記一組の多変数二次多項式の各多項式を線形化することを含む、
付記１に記載の方法。
（付記４）
イジングモデル結合重み行列Ｗとイジングモデルバイアスベクトルｂとを生成することは、
線形化された多項式の十分な倍数（ｓｕｆｆｉｃｉｅｎｔ  ｍｕｌｔｉｐｌｅｓ）を除去することにより丸めるために、線形化された多項式を調整することをさらに含む、
付記３に記載の方法。
（付記５）
イジングモデル結合重み行列Ｗとイジングモデルバイアスベクトルｂとを生成することは、
線形化され調整された多項式のエネルギー関数を計算することをさらに含む、
付記４に記載の方法。
（付記６）
前記一組の多変数二次多項式の集合は、多変数暗号方式に基づき、前記多変数二次問題に対する解を用いて、前記多変数暗号方式に対するチャレンジを実行することをさらに含む、
付記１に記載の方法。
（付記７）
実行されることに応じて、システムに動作を実行させる命令を格納するように構成された１つ以上の非一時的コンピュータ可読記憶媒体であって、前記動作は、
多変数二次問題に関連する一連の多変数二次多項式を取得することと、
イジングモデル重み行列Ｗとイジングモデルバイアスベクトルｂとを生成する、前記行列Ｗの少なくとも１つの要素は一組の多変数二次多項式に基づいて決定されることと、
前記行列Ｗおよびベクトルｂを、イジングモデルによって記述された問題を解くように構成されたアニーリングシステムに提供することと、
一組の整数を表す前記アニーリングシステムからの出力を取得することと、
前記一組の整数を、前記一組の多変数二次多項式によって定められる前記多変数二次問題の解として使用することとを含む、
１つ以上の非一時的コンピュータ可読記憶媒体。
（付記８）
前記一組の多変数二次多項式は暗号技術から得られる、
付記７に記載の１つ以上の非一時的コンピュータ可読記憶媒体。
（付記９）
前記動作は、前記多変数二次問題に対する解を使用して、前記暗号技術に対するチャレンジを実行することをさらに含む、
付記８に記載の１つ以上の非一時的コンピュータ可読記憶媒体。
（付記１０）
前記アニーリングシステムは、前記出力を生成するために使用されるエネルギー値を計算するように構成されたエネルギー値計算回路を含み、前記エネルギー値は、前記行列Ｗの前記要素の１つ以上の値に基づく、
付記７に記載の１つ以上の非一時的コンピュータ可読記憶媒体。
（付記１１）
イジングモデル結合重み行列Ｗとイジングモデルバイアスベクトルｂとを生成することは、
前記一組の多変数二次多項式の各多項式を線形化することを含む、
付記８に記載の１つ以上の非一時的コンピュータ可読記憶媒体。
（付記１２）
イジングモデル結合重み行列Ｗとイジングモデルバイアスベクトルｂとを生成することは、
線形化された多項式の十分な倍数（ｓｕｆｆｉｃｉｅｎｔ  ｍｕｌｔｉｐｌｅｓ）を除去することにより丸めるために、線形化された多項式を調整することをさらに含む、
付記１１に記載の１つ以上の非一時的コンピュータ可読記憶媒体。
（付記１３）
イジングモデル結合重み行列Ｗとイジングモデルバイアスベクトルｂとを生成することは、
線形化され調整された多項式のエネルギー関数を計算することをさらに含む、
付記１２に記載の１つ以上の非一時的コンピュータ可読記憶媒体。
（付記１４）
システムであって、
命令を記憶するように構成された１つ以上のコンピュータ可読記憶媒体と、
システムに動作を実行させるように構成された、前記１つ以上のコンピュータ可読記憶媒体に通信可能に結合され、前記命令の実行に応答して、前記システムに動作を実行させる１つ以上のプロセッサとを有し、
前記動作は、
多変数二次問題に関連する一連の多変数二次多項式を取得することと、
イジングモデル重み行列Ｗとイジングモデルバイアスベクトルｂとを生成する、前記行列Ｗの少なくとも１つの要素は一組の多変数二次多項式に基づいて決定されることと、
前記行列Ｗおよびベクトルｂを、イジングモデルによって記述された問題を解くように構成されたアニーリングシステムに提供することと、
一組の整数を表す前記アニーリングシステムからの出力を取得することと、
前記一組の整数を、前記一組の多変数二次多項式によって定められる前記多変数二次問題の解として使用することとを含む、
システム。
（付記１５）
前記一組の多変数二次多項式は暗号技術から得られ、前記動作は、前記多変数二次問題の解を用いて、前記暗号技術へのチャレンジを実行することをさらに含む、
付記１４に記載のシステム。
（付記１７）
前記アニーリングシステムは、前記出力を生成するために使用されるエネルギー値を計算するように構成されたエネルギー値計算回路を含み、前記エネルギー値は、前記行列Ｗの前記要素の１つ以上の値に基づく、
付記１４に記載のシステム。
（付記１８）
イジングモデル結合重み行列Ｗとイジングモデルバイアスベクトルｂとを生成することは、
前記一組の多変数二次多項式の各多項式を線形化することを含む、
付記１４に記載のシステム。
（付記１９）
イジングモデル結合重み行列Ｗとイジングモデルバイアスベクトルｂとを生成することは、
線形化された多項式の十分な倍数（ｓｕｆｆｉｃｉｅｎｔ  ｍｕｌｔｉｐｌｅｓ）を除去することにより丸めるために、線形化された多項式を調整することをさらに含む、
付記１４に記載のシステム。
（付記２０）
イジングモデル結合重み行列Ｗとイジングモデルバイアスベクトルｂとを生成することは、
線形化され調整された多項式のエネルギー関数を計算することをさらに含む、
付記１４に記載のシステム。
【図１】
2020119548.tif 000015
【図２】
2020119548.tif 000016
【図３】
2020119548.tif 000017
【図４】
2020119548.tif 000018