(57)【要約】      （修正有）【課題】アニーリングを用いて格子問題を解く方法及びシステムを提供する。【解決手段】処理は、ｍ次元空間内の格子を規定する基底“Ａ”を取得し、ｍ次元空間内の特定の位置を規定する目標ベクトル“ｙ”を取得し、“Ａ”の転置（“ＡＴ”）に“Ａ”を乗算することによって、イジングモデル連結重み行列“Ｗ”を生成し、“ｙ”の転置（“ｙＴ”）に“Ａ”を乗算することによって、イジングモデルバイアスベクトル“ｂ”を生成し、イジングモデルに従って記述された問題を解くように構成されたアニーリングシステムに“Ｗ”及び“ｂ”を提供し、“ｙ”によって規定される特定の位置に最も近い格子点である特定の点の出力ベクトル“ｘ”を表す出力を、アニーリングシステムから取得し、“ｘ”を用いて最近ベクトル格子問題の解を得る。【選択図】図３
2020071877.tif 000002
【特許請求の範囲】
【請求項１】
ｍ次元空間内の格子を規定する基底“Ａ”を取得し、前記格子は、前記ｍ次元空間内の複数の点を含み、前記基底“Ａ”は、“ｎ”個の線形の独立したベクトルの行列であり、それぞれのベクトル各々が、前記ｍ次元空間における位置を規定する“ｍ”個の要素を有し、前記格子のそれぞれの点各々が、前記基底の前記ベクトルの線形結合に関して規定され、
前記ｍ次元空間内の特定の位置を規定する目標ベクトル“ｙ”を取得し、
“Ａ”の転置（“ＡＴ”）に“Ａ”を乗算することによって、イジングモデル連結重み行列“Ｗ”を生成し、
“ｙ”の転置（“ｙＴ”）に“Ａ”を乗算することによって、イジングモデルバイアスベクトル“ｂ”を生成し、
イジングモデルに従って記述された問題を解くように構成されたアニーリングシステムに“Ｗ”及び“ｂ”を提供し、
前記格子に含まれる特定の点の出力ベクトル“ｘ”を表す出力を前記アニーリングシステムから取得し、前記特定の点は、前記格子における、“ｙ”によって規定される前記特定の位置に最も近い点であり、
前記格子におけるどの点が、“ｙ”によって規定される前記特定の位置に最も近いかを見つけることとして定義される最近ベクトル問題に対する解を、“ｘ”を用いて得る、
ことを有する方法。
【請求項２】
前記ｍ次元空間内の別の格子を規定するイニシャル基底“ＡＩ”から“Ａ”を取得し、“ＡＩ”の特定のベクトル“ｉ”の要素が“Ａ”においては２倍にされていることを除いて“Ａ”は“ＡＩ”と同じであり、
前記特定のベクトル“ｉ”を目標ベクトル“ｉ”として用いることによって、“ＡＩ”から前記目標ベクトル“ｙ”を取得し、
前記目標ベクトル“ｙ”と前記出力ベクトル“ｘ”との間の距離を決定し、
前記別の格子におけるどの点が最短ベクトルを持つかを見つけることとして定義される最短ベクトル問題に対する解を求める際に、前記目標ベクトル“ｙ”と前記出力ベクトル“ｘ”との間の前記距離を使用する、
ことを更に有する請求項１に記載の方法。
【請求項３】
前記イニシャル基底“ＡＩ”の全ベクトルに対して請求項２の処理を繰り返して、各目標ベクトル“ｙ”とその対応する出力ベクトル“ｘ”との間の距離として複数の距離を取得し、
前記複数の距離のうちの最短距離に対応する特定の出力ベクトル“ｘ”を、前記最短ベクトル問題に対する前記解として使用する、
ことを更に有する請求項２に記載の方法。
【請求項４】
前記最短ベクトル問題に対する前記解を使用して、コンピュートアンドフォワード問題を解く、ことを更に有する請求項２に記載の方法。
【請求項５】
前記アニーリングシステムへの“Ｗ”及び“ｂ”の入力を可能にするために、“Ｗ”及び“ｂ”の値をバイナリフォーマットに変換する、ことを更に有する請求項１に記載の方法。
【請求項６】
前記格子の行列式に基づいて“Ｗ”及び“ｂ”のためのビット数を決定することを更に有する請求項５に記載の方法。
【請求項７】
前記行列式を、“Ａ”の行列式を求めることによって求める、ことを更に有する請求項６に記載の方法。
【請求項８】
誤差ベースの暗号システムによる特定の学習が安全であるかを、“ｘ”を用いて検査する、ことを更に有する請求項１に記載の方法。
【請求項９】
命令を格納した１つ以上のコンピュータ読み取り可能記憶媒体であって、前記命令は、実行されることに応答してシステムに処理を実行させ、前記処理は、
ｍ次元空間内の格子を規定する基底“Ａ”を取得し、前記格子は、前記ｍ次元空間内の複数の点を含み、前記基底“Ａ”は、“ｎ”個の線形の独立したベクトルの行列であり、それぞれのベクトル各々が、前記ｍ次元空間における位置を規定する“ｍ”個の要素を有し、前記格子のそれぞれの点各々が、前記基底の前記ベクトルの線形結合に関して規定され、
前記ｍ次元空間内の特定の位置を規定する目標ベクトル“ｙ”を取得し、
“Ａ”の転置（“ＡＴ”）に“Ａ”を乗算することによって、イジングモデル連結重み行列“Ｗ”を生成し、
“ｙ”の転置（“ｙＴ”）に“Ａ”を乗算することによって、イジングモデルバイアスベクトル“ｂ”を生成し、
イジングモデルに従って記述された問題を解くように構成されたアニーリングシステムに“Ｗ”及び“ｂ”を提供し、
前記格子に含まれる特定の点の出力ベクトル“ｘ”を表す出力を前記アニーリングシステムから取得し、前記特定の点は、前記格子における、“ｙ”によって規定される前記特定の位置に最も近い点であり、
前記格子におけるどの点が、“ｙ”によって規定される前記特定の位置に最も近いかを見つけることとして定義される最近ベクトル問題に対する解を、“ｘ”を用いて得る、
ことを有する、１つ以上のコンピュータ読み取り可能記憶媒体。
【請求項１０】
システムであって、
命令を格納した１つ以上のコンピュータ読み取り可能記憶媒体と、
前記１つ以上のコンピュータ読み取り可能記憶媒体に通信可能に結合され、前記命令の実行に応答して当該システムに処理を実行させるように構成された１つ以上のプロセッサと、
を有し、前記処理は、
ｍ次元空間内の格子を規定する基底“Ａ”を取得し、前記格子は、前記ｍ次元空間内の複数の点を含み、前記基底“Ａ”は、“ｎ”個の線形の独立したベクトルの行列であり、それぞれのベクトル各々が、前記ｍ次元空間における位置を規定する“ｍ”個の要素を有し、前記格子のそれぞれの点各々が、前記基底の前記ベクトルの線形結合に関して規定され、
前記ｍ次元空間内の特定の位置を規定する目標ベクトル“ｙ”を取得し、
“Ａ”の転置（“ＡＴ”）に“Ａ”を乗算することによって、イジングモデル連結重み行列“Ｗ”を生成し、
“ｙ”の転置（“ｙＴ”）に“Ａ”を乗算することによって、イジングモデルバイアスベクトル“ｂ”を生成し、
イジングモデルに従って記述された問題を解くように構成されたアニーリングシステムに“Ｗ”及び“ｂ”を提供し、
前記格子に含まれる特定の点の出力ベクトル“ｘ”を表す出力を前記アニーリングシステムから取得し、前記特定の点は、前記格子における、“ｙ”によって規定される前記特定の位置に最も近い点であり、
前記格子におけるどの点が、“ｙ”によって規定される前記特定の位置に最も近いかを見つけることとして定義される最近ベクトル問題に対する解を、“ｘ”を用いて得る、
ことを有する、システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示にて記載される実施形態は、アニーリングを用いて格子問題を解くことに関する。
【背景技術】
【０００２】
例えば最近ベクトル問題（closest  vector  problem）及び最短ベクトル問題（shortest  vector  problem）などの格子問題（lattice  problem）は、格子上での最適化問題の類である。格子問題を解くことは、例えば暗号技術及び通信中継技術などの様々な技術分野において適用可能であり得る。
【０００３】
本開示にて特許請求される事項は、上述のような環境でのみ問題を解決したり動作したりする実施形態に限定されるものではない。むしろ、この背景技術の説明は、本開示にて記載される実施形態が実施され得る技術領域の一例を示すために提供されているに過ぎないものである。
【発明の概要】
【０００４】
一実施形態の一態様によれば、処理は、ｍ次元空間内の格子を規定する基底“Ａ”を取得することを含むことができ、前記格子は、ｍ次元空間内の複数の点を含み、基底“Ａ”は、“ｎ”個の線形の独立したベクトルの行列であり、それぞれのベクトル各々が、ｍ次元空間における位置を規定する“ｍ”個の要素を有し、前記格子のそれぞれの点各々が、前記基底のベクトルの線形結合に関して規定される。処理は更に、ｍ次元空間内の特定の位置を規定する目標ベクトル“ｙ”を取得することを含み得る。加えて、処理は、“Ａ”の転置（“ＡＴ”）に“Ａ”を乗算することによって、イジングモデル連結重み行列“Ｗ”を生成することを含み得る。さらに、処理は、“ｙ”の転置（“ｙＴ”）に“Ａ”を乗算することによって、イジングモデルバイアスベクトル“ｂ”を生成することを含み得る。処理は更に、イジングモデルに従って記述された問題を解くように構成されたアニーリングシステムに“Ｗ”及び“ｂ”を提供することを含み得る。さらに、処理は、前記格子に含まれる特定の点の出力ベクトル“ｘ”を表す出力を前記アニーリングシステムから取得することを含むことができ、前記特定の点は、前記格子における、“ｙ”によって規定される前記特定の位置に最も近い点である。さらに、処理は、前記格子におけるどの点が、“ｙ”によって規定される前記特定の位置に最も近いかを見つけることとして定義される最近ベクトル問題に対する解を、“ｘ”を用いて得ることを含み得る。
【０００５】
実施形態の目的及び利点は、少なくとも請求項中に具体的に指し示される要素、機構及び組合せによって実現・達成されることになる。
【０００６】
以上の概略説明及び以下の詳細説明はどちらも、例として与えられ、説明的なものであり、特許請求される発明を限定するものではない。
【図面の簡単な説明】
【０００７】
以下の図を含む添付図面を使用して、実施形態例を更に具体的且つ詳細に記載・説明する。
【図１】格子問題を解くことに関する環境の一例を表す図である。
【図２】格子問題を解くように構成され得るコンピューティングシステムの一例を示す図である。
【図３】最近ベクトル格子問題を解く方法の一例を示すフローチャートである。
【図４】最短ベクトル格子問題を解く方法の一例を示すフローチャートである。
【発明を実施するための形態】
【０００８】
例えば最近ベクトル問題及び最短ベクトル問題などの格子問題は、例えば暗号技術及び無線通信中継技術などの多様な用途を有する最適化問題の類である。また、量子アニーリングシステムは、古典的なコンピューティングシステム及び技術よりも速い手法で最適化問題に対する解を得るために発見的アプローチを使用する。また、デジタルアニーリングシステムは、大規模な並列化によって量子アニーリングを模擬するために開発された古典的コンピューティングシステムである。従って、量子及びデジタルアニーリングシステムは、格子問題を解くのを助ける上で有用であり、それにより、例えば暗号化と暗号解析及び／又は無線通信などの幾つかの技術分野を向上させ得る。
【０００９】
しかしながら、格子問題で典型的に使用される入力は、アニーリングシステム（例えば、デジタルアニーリングシステム又は量子アニーリングシステム）の使用が格子問題を解くことを可能にするようには構成されていない。例えば、一部の例において、アニーリングシステムは、イジング（Ising）最適化モデルを用いて二次最適化問題を解くように構成され得る。しかしながら、格子問題で典型的に使用される入力は、当該入力をイジング最適化モデルに直接的に入力することを可能にするようには構成されていない。従って、アニーリングシステムは、伝統的に形成された格子問題を解決するために使用されることができない。
【００１０】
本開示の１つ以上の態様によれば、１つ以上の処理を格子問題入力値に対して実行して、アニーリングシステムのイジング最適化モデルに入力し得るイジングモデル入力を取得し得る。そして、アニーリングシステムは、イジング最適化モデルと取得されたイジングモデル入力とを使用して、対応する格子問題を解くために使用し得る出力ベクトルを生成し得る。
【００１１】
従って、本開示の１つ以上の実施形態によれば、ここに記載される処理が、アニーリングシステムが格子問題を解くことを可能にする機構を提供することによって、アニーリングシステムの改良を可能にし、それが、アニーリングシステムの新たな能力をもたらす。格子問題を解くことができるというアニーリングシステムの改良された能力はまた、例えば暗号及び無線通信などのその他の技術分野を、それらの分野で使用されるような格子問題を解くことを可能にする新たな機構（例えば、アニーリングシステム）を提供することによって向上させる。
【００１２】
本開示の実施形態を、添付の図面を参照して説明する。
【００１３】
図１は、本開示にて記載される少なくとも１つの実施形態に従って構成された、アニーリングシステムを用いて格子問題を解くことに関する環境１００の一例を表す図である。環境１００は、イジングモデル入力モジュール１０２（“入力モジュール１０２”）、イジングモデルモジュール１０６（“イジングモジュール１０６”）、及びイジングモデル出力モジュール１１２（“出力モジュール１１２”）を含み得る。
【００１４】
入力モジュール１０２、イジングモジュール１０６、及び／又は出力モジュール１１２は、それとともに記載される処理のうちの１つ以上をコンピューティング装置が実行することを可能にするように構成されたコード及びルーチンを含み得る。加えて、あるいは代えて、入力モジュール１０２、イジングモジュール１０６、及び／又は出力モジュール１１２は、あらゆるプロセッサ、（例えば、１つ以上の処理の実行を行う又は制御するための）マイクロプロセッサ、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、特定用途向け集積回路（ＡＳＩＣ）、又はこれらのうち２つ以上の好適な組み合わせを含むハードウェアを用いて実装されてもよい。一部の他の例において、入力モジュール１０２、イジングモジュール１０６、及び／又は出力モジュール１１２は、ハードウェアとソフトウェアとの組み合わせを用いて実装され得る。本開示において、入力モジュール１０２、イジングモジュール１０６、及び／又は出力モジュール１１２によって実行されるとして記述される処理は、入力モジュール１０２、イジングモジュール１０６、及び／又は出力モジュール１１２が対応するシステムに指示して実行させ得る処理を含み得る。
【００１５】
一部の実施形態において、入力モジュール１０２、イジングモジュール１０６、及び出力モジュール１１２は各々、アニーリングシステム（例えば、デジタルアニーリングシステム又は量子アニーリングシステム）に含められ得る。加えて、あるいは代えて、イジングモジュール１０６は、アニーリングシステムに含められ、入力モジュール１０２及び出力モジュール１１２のうちの１つ以上は、アニーリングシステムとインタフェースをとるように構成された別個のシステムに含められてもよい。また、入力モジュール１０２、イジングモジュール１０６、及び出力モジュール１１２は、本開示の説明を容易にするために、別々の要素として図示及び説明される。従って、入力モジュール１０２、イジングモジュール１０６、及び出力モジュール１１２によって実行されるとして記載される処理を実行するように構成される如何なる好適なハードウェア及び／又はソフトウェア構成も、本開示の範囲内である。
【００１６】
格子は、一般に、一組のｍ次元ベクトルの整数倍線形結合であるｍ次元空間内の一組の点として規定される。また、ｍ次元空間内の点の位置は、一般に、ｍ次元空間内の位置を規定する一組の線形の独立したベクトルに従って規定される。この一組の線形独立ベクトルは、一般に、格子の基底として参照されている。
【００１７】
基底を構成する各ベクトルは、ｍ次元空間内のそれぞれの点の位置の特定を可能にし得る座標を各々が与え得る“ｍ”個の要素を有し得る。例えば、デカルト座標系に従って規定される３次元空間では、特定の基底ベクトルは、１つの要素がｘ座標に対応し、別の１つの要素がｙ座標に対応し、そして別の１つの要素がｚ座標に対応するとし得る３つの要素を含み得る。基底内のベクトルの数は、ｍ次元空間内の格子のｎ次元空間を規定することができる。例えば、３次元空間の一部である２つのベクトルを持つ基底は、３次元空間内の２次元格子を規定し得る。一部の実施形態において、基底は従って、それぞれのベクトル各々がｍ次元空間内の位置を規定する“ｍ”個の要素を有する“ｎ”個の線形の独立したベクトルの行列として規定され得る。
【００１８】
また、格子点の位置は、特定の値空間内の値を持つ係数を用いて、基底ベクトルの線形結合に関して規定され得る。言い換えると、格子の点は、値空間の係数を用いて基底ベクトルの線形結合の組を得ることによって取得され得る。
【００１９】
例えば、数学用語において、格子は次のように定義されることがある：ｖ１，…，ｖｎ∈Ｒｍが格子“Ｌ”の基底である一組の線形独立ベクトルであるとして、ｖ１，…，ｖｎによって生成される格子Ｌは、ｍ次元空間“Ｒ”内の値の部分集合である値空間“Ｚ”内の係数ａ１，…，ａｎを有するｖ１，…，ｖｎの線形結合の組であり、
Ｌ＝｛ａ１ｖ１＋ａ２ｖ２＋…＋ａｎｖｎ：ａ１，ａ２，…，ａｎ∈Ｚ｝
として表される
最近ベクトル問題は、格子における、該格子と同じｍ次元空間にある目標位置に最も近い点を見つけることとして定義され得る。数学用語において、最近ベクトル問題は、次のように定義されることがある：特定のｍ次元空間内の“ｎ”個のｍ次元ベクトルを含む行列である基底“Ａ”によって規定される格子“Ｌ”を所与とするとともに、上記特定のｍ次元空間内の特定の位置を規定するベクトル“ｙ”を所与として、格子“Ｌ”における特定の点に対応するベクトル“ｘ”であって、“ｘ”と“ｙ”との間の距離（｜｜Ａｘ−ｙ｜｜２）が最小化されるようなベクトル“ｘ”を見付けよ。これは、次式（１）：
（１）  argminｘ｜｜Ａｘ−ｙ｜｜２＝argminｘ（ｘＴＡＴＡｘ−２ｙＴＡｘ）
にて表され得る。
【００２０】
上式において使用されている上付き文字の“Ｔ”は、対応する行列の転置を意味する。
【００２１】
一部の実施形態において、格子問題入力１０４（“格子入力１０４”）は、格子の最近ベクトル問題及び／又は格子の最短ベクトル問題を解くために使用され得る入力を含み得る。例えば、一部の実施形態において、格子入力１０４は、ｍ次元空間内の格子“Ｌ”を規定する基底“Ａ”を含み得る。さらに、格子入力１０４は、ｍ次元空間内の特定の位置を規定する目標ベクトル“ｙ”を含み得る（最近ベクトル問題に対する解は、格子“Ｌ”における、目標ベクトル“ｙ”によって規定される特定の位置に最も近い点、に対応するベクトル“ｘ”である）。
【００２２】
入力モジュール１０２は、イジングモデル入力１１０（“モデル入力１１０”）を生成するよう、格子入力１０４に対して１つ以上の処理を実行するように構成され得る。入力モジュール１０２は、最近ベクトル問題を解くためにイジングモジュール１０６によって使用されるようなモデル入力１１０を生成するように構成され得る。
【００２３】
例えば、イジングモジュール１０６は、次式（２）のイジングエネルギー：
（２）  Ｅ（ｘ）＝−ΣｘＴＷｘ−Σｂｘ
においてイジングエネルギーを最小化する出力ベクトル“ｘ”を見つけることによって、イジングエネルギーを最小化するために、マルコフチェーンモンテカルロ（Markov  Chain  Monte  Carlo；ＭＣＭＣ）確率的探索を実行するように構成され得る。
【００２４】
上式において、“Ｗ”は、出力ベクトル“ｘ”の要素間の連結を重み付けるイジングモデル連結重み行列であり、“ｂ”は、イジングエネルギーを最小化する際に使用される線形項のバイアスベクトルである。
【００２５】
一部の実施形態において、入力モジュール１０２は、格子入力１０４に基づいてイジングモデル連結重み行列“Ｗ”及びバイアスベクトル“ｂ”を生成するように構成され得る。例えば、上述の式（１）及び（２）に基づいて、格子入力１０４の基底“Ａ”によって規定される格子“Ｌ”のベクトル“ｘ”（ベクトル“ｘ”は、格子入力１０４の目標ベクトル“ｙ”に最も近い格子“Ｌ”の点に対応する）を見つけるために、“Ｗ”が、規定“Ａ”に関して、次式（３）：
（３）  Ｗ＝ＡＴＡ
によって表される。
【００２６】
従って、一部の実施形態において、入力モジュール１０２は、式（３）に従って、格子入力１０４の基底行列“Ａ”の転置（“ＡＴ”）に基底行列“Ａ”を乗算することによって、重み行列“Ｗ”を生成するように構成され得る。
【００２７】
さらに、上述の式（１）及び（２）に基づき、“ｂ”は、格子入力１０４の基底“Ａ”及び目標ベクトル“ｙ”に関して、次式（４）：
（４）  ｂ＝２ｙＴＡ
によって表され得る。
【００２８】
従って、一部の実施形態において、入力モジュール１０２は、式（４）に従って、格子入力１０４の目標ベクトル“ｙ”の転置（“ｙＴ”）に基底行列“Ａ”を乗算することによって、バイアスベクトル“ｂ”を生成するように構成され得る。
【００２９】
一部の実施形態において、イジングモジュール１０６は、バイナリ入力に基づいて処理を実行するように構成され得る。これら又は他の実施形態において、入力モジュール１０２は、生成した重み行列“Ｗ”及び生成したバイアスベクトル“ｂ”をバイナリフォーマットへと変換するように構成され得る。
【００３０】
加えて、あるいは代えて、イジングモジュール１０６は、入力として、最適化問題の出力“ｘ”のビット数を受信するように構成され得る。これら又は他の実施形態において、入力モジュール１０２は、イジングモジュール１０６に提供するビット数を決定するように構成され得る。例えば、一部の実施形態において、入力モジュール１０２は、出力ベクトル“ｘ”の大きさについての限度“ｒ”を決定するように構成され得る。限度“ｒ”は、出力ベクトル“ｘ”の大きさをそれ以下とし得るという量を表し得る。従って、限度“ｒ”を表すのに十分であるビット数は、出力ベクトル“ｘ”を表すのにも十分である。故に、一部の実施形態において、入力モジュール１０２は、限度“ｒ”のビット数を決定することによって、イジングモジュール１０６への入力として与えられるビット数“ｄ”を決定するように構成され得る。一部の実施形態において、入力モジュール１０２は、式（５）：
（５）  ｄ＝ｌｏｇ２ｒ
によって与えられる限度“ｒ”の対数（底２）をとることによって、ビット数を決定するように構成され得る。
【００３１】
一部の実施形態において、限度“ｒ”は、基底“Ａ”によって規定され得る格子“Ｌ”の行列式に基づいて決定されてもよい。行列式は、格子“Ｌ”によって占有され得るｍ次元空間内の空間量の指標とし得る。例えば、３次元格子の行列式は、３次元格子の体積であり得る。これら又は他の実施形態において、入力モジュール１０２は、基底“Ａ”の行列式を求めることによって格子“Ｌ”の行列式を求めるように構成されてもよい。
【００３２】
これら又は他の実施形態において、入力モジュール１０２は、求めた行列式を限度“ｒ”として使用するように構成されてもよい。例えば、格子“Ｌ”によって占有される空間内に出力ベクトル“ｘ”があることを考慮すると、イジングモジュール１０６によって生成され得る出力ベクトル“ｘ”の大きさは、格子“Ｌ”の行列式より小さいとし得る。従って、その行列式を表すのに十分であるビット数は、出力ベクトル“ｘ”を表すのにも十分である。
【００３３】
加えて、あるいは代えて、入力モジュール１０２は、格子“Ｌ”がそれとして規定された格子タイプに基づいて限度“ｒ”を決定するように構成されてもよい。例えば、（格子ベースの暗号で使用されるもののような）ｑ’−ａｒｙ格子の場合、ｒは、“（ｒ’）２”として設定され得る。
【００３４】
これら又は他の実施形態において、入力モジュール１０２は、決定したビット数に至るまでの“Ｗ”及び“ｂ”のバイナリ変換を実行するように構成され得る。加えて、あるいは代えて、入力モジュール１０２は、負数の使用を可能にするために、“Ｗ”の最後の行及び最後の列と“ｂ”の最後の行とを１の補数形式でフォーマットするように構成されてもよい。例として、入力モジュール１０２は、“Ｗ”を、基底“Ａ”及び決定したビット数“ｄ”に関して、次式（６）：
【数１】
2020071877.tif 000003
のように決定するよう構成され得る。
【００３５】
式（６）は、次式（７）：
【数２】
2020071877.tif 000004
のように展開され得る。
【００３６】
また、入力モジュール１０２は、“ｂ”を、基底“Ａ”、目標ベクトル“ｙ”、及び決定したビット数“ｄ”に関して、次式（８）：
【数３】
2020071877.tif 000005
のように決定するよう構成され得る。
【００３７】
入力モジュール１０２は、決定した重み行列“Ｗ”（例えば式（７）に示されるものなど）及び決定したバイアスベクトル“ｂ”（例えば式（８）に示されるものなど）を、モデル入力１１０に含めるように構成され得る。これら又は他の実施形態において、入力モジュール１０２は、決定したビット数“ｄ”をモデル入力１１０に含めるように構成されてもよい。これら又は他の実施形態において、入力モジュール１０２は、モデル入力１１０をイジングモジュール１０６に提供するように構成され得る。
【００３８】
上述のように、イジングモジュール１０６は、上述のイジング最適化モデルに従って記述される最適化問題を解くように構成され得る。また、上でも示したように、イジングモジュール１０６はアニーリングシステムの一部であってもよく、その結果、アニーリングシステムは、イジング最適化モデルを用いて、古典的に構成されたコンピューティングシステムよりも遥かに速い手法で最適化問題を解くことができる。これら又は他の実施形態において、イジングモジュール１０６は、最適化問題に対する解としてイジングモデル出力１０８（“モデル出力１０８”）を生成するように構成され得る。
【００３９】
一部の実施形態において、イジングモジュール１０６は、１つ以上のイジングユニットを含み得る情報処理装置を含むことができる。イジングユニットは、例えばＤｅＧｌｏｒｉａアルゴリズムなどのアルゴリズムに基づいて、小規模ハードウェアによってニューラルネットワークのイジング型エネルギー関数の処理を実行するように構成され得る。行列Ｗの要素は、ニューラルネットワークのニューロン間の重み付け値を含み得る。例えば、行列Ｗの要素は、行列Ｗ内での行番号によって表される第１のニューロンと行列Ｗ内での列番号によって表される第２のニューロンとの間の重み付け値を含むことができ、ここで、行番号と列番号とで要素が特定される。この情報処理装置は、ニューラルネットワーク内のエネルギーを最小化するように動作することで、行列Ｗ及びベクトルｂによって表される問題に対する解を決定し得る。
【００４０】
イジングユニットを含む情報処理装置の一例が、２０１７年８月３０日に出願された米国特許出願公開第２０１８／００７５３４２号にて提供されており、その全体を本開示に援用する。米国特許出願公開第２０１８／００７５３４２号に記載されているように、イジングユニットは、エネルギー値計算回路及び状態遷移決定回路を含み得る。エネルギー値計算回路は、行列“Ｗ”の要素のうちの１つ以上の要素の値に基づくエネルギー値を計算するように構成されることができ、それが、情報処理装置の出力を生成するために使用され得る。その出力は、行列Ｗ及びベクトルｂによって表される問題に対する解を含み得る。状態遷移決定回路の更なる情報及び例が、２０１７年９月２８日に出願された米国特許出願公開第２０１８／０１０７１７２号にて提供されており、その全体を本開示に援用する。
【００４１】
イジングモジュール１０６は、格子“Ｌ”の基底“Ａ”、目標ベクトル“ｙ”、及び最近ベクトル問題に従って上述のように決定されるものである決定された重み行列“Ｗ”及び決定されたバイアスベクトル“ｂ”に基づいて、目標ベクトル“ｙ”によって規定される特定の位置に最も近い格子“Ｌ”における点に対応する出力ベクトル“ｘ”を決定するように構成され得る。従って、このアニーリングシステムを使用することで、入力モジュール１０２によって生成されたモデル入力１１０とイジングモジュール１０６とを用いて、最近ベクトル問題を解き得る。これら又は他の実施形態において、出力ベクトル“ｘ”は、モデル出力１０８に含められ得る。
【００４２】
一部の実施形態において、出力モジュール１１２は、最近ベクトル問題に対する解を得るために、出力ベクトル“ｘ”に対して１つ以上の処理を実行するように構成され得る。例えば、一部の実施形態において、イジングモジュール１０６は、モデル出力１０８（例えば、出力ベクトル“ｘ”）をバイナリ表現で生成するように構成され得る。これら又は他の実施形態において、出力モジュール１１２は、モデル出力１０８をバイナリ表現から、格子問題解１１４として出力され得る１０進表現へと変換するように構成され得る。
【００４３】
一部の実施形態において、入力モジュール１０２及び出力モジュール１１２は、最近ベクトル問題演算を使用することに基づいて、最短ベクトル問題を解くための演算を実行するように構成されてもよい。例えば、最短ベクトルを持つ格子“Ｌ”における点が、しばしば、最短ベクトル問題に対する解として使用される。
【００４４】
一部の実施形態において、最短ベクトル問題を解くために、格子入力１０４は、複数の基底“Ａｉ”を生成するように変更され得るイニシャル基底“ＡＩ”を含み得る。また、最短ベクトル問題を解く一部の例では、格子入力１０４は、それ自体が具体的に数え上げられた目標ベクトル“ｙ”を含んでいなくてもよい。代わりに、入力モジュール１０２は、イニシャル基底“ＡＩ”に基づいて、それぞれの基底“Ａｉ”に対応する特定の目標ベクトル“ｙｉ”を取得するように構成され得る。
【００４５】
特に、基底“Ａｉ”を生成するために、入力モジュール１０２は、イニシャル基底“ＡＩ”の特定のベクトル“ｖｉ”の要素を２倍にして“Ａｉ”を取得するように構成され得る。さらに、特定のベクトル“ｖｉ”が目標ベクトル“ｙｉ”として使用され得る。
【００４６】
例えば、特定のイニシャル基底“ＡＩ”が、第１のベクトル（ｖ１）が“ＡＩ”の第１列の要素｛ａ，ｂ，ｃ｝を有し、第２のベクトル（ｖ２）が“ＡＩ”の第２列の要素｛ｄ，ｅ，ｆ｝を有し、第３のベクトル（ｖ３）が“ＡＩ”の第３列の要素｛ｇ，ｈ，ｉ｝を有し、そして、第４のベクトル（ｖ４）が“ＡＩ”の第４列の要素｛ｊ，ｋ，ｌ｝を有するという４つの３次元ベクトルを含むとし得る。基底“Ａ１”を得るため、入力モジュール１０２は、“Ａ１”の第１列のｖ１の要素を｛２ａ，２ｂ，２ｃ｝に変更し得るとともに、“Ａ１”の第２列の要素｛ｄ，ｅ，ｆ｝を保持し、“Ａ１”の第３列の要素｛ｇ，ｈ，ｉ｝を保持し、“Ａ１”の第４列の要素｛ｊ，ｋ，ｌ｝を保持し得る。さらに、基底“Ａ１”に対応する目標ベクトル“ｙ１”を得るため、入力モジュール１０２は、第１のベクトルｖ１（｛ａ，ｂ，ｃ｝）を目標ベクトル“ｙ１”として使用し得る。
【００４７】
一部の実施形態において、入力モジュール１０２は、基底“ＡＩ”の各ベクトルに対して、基底“Ａｉ”及び対応する目標ベクトル“ｙｉ”を取得するように構成され得る。例えば、前段落の例を続けるに、入力モジュール１０２は、特定のイニシャル基底“ＡＩ”に関する基底“Ａ２”を取得するように構成されることができ、ここで、“Ａ２”の第１列のｖ１の要素は｛ａ，ｂ，ｃ｝であり、“Ａ２”の第２列のｖ２の要素は｛２ｄ，２ｅ，２ｆ｝であり、“Ａ２”の第３列のｖ３の要素は｛ｇ，ｈ，ｉ｝であり、そして、“Ａ２”の第４列のｖ４の要素は｛ｊ，ｋ，ｌ｝である。さらに、基底“Ａ２”に対応する目標ベクトル“ｙ２”を得るため、入力モジュール１０２は、第２のベクトルｖ２（｛ｄ，ｅ，ｆ｝）を目標ベクトル“ｙ２”として使用し得る。入力モジュール１０２は、特定のイニシャル基底“ＡＩ”のｖ３について同様の手法で基底“Ａ３”及び目標ベクトル“ｙ３”を取得するように構成され得るとともに、特定のイニシャル基底“ＡＩ”のｖ４について同様の手法で基底“Ａ４”及び目標ベクトル“ｙ４”を取得するように構成され得る。
【００４８】
一部の実施形態において、入力モジュール１０２は、最近ベクトル問題の議論において重み行列“Ｗ”及びバイアスベクトル“ｂ”を取得することに関して上述したようにして、それぞれの基底“Ａｉ”及びそのそれぞれの目標ベクトル“ｙｉ”に基づいて、重み行列“Ｗｉ”及びバイアスベクトル“ｂｉ”を取得するように構成され得る。加えて、あるいは代えて、入力モジュール１０２は、各々それぞれの基底“Ａｉ”及びそのそれぞれの目標ベクトル“ｙｉ”に基づいて、重み行列“Ｗｉ”及びバイアスベクトル“ｂｉ”を取得するように構成されてもよい。
【００４９】
例えば、上であげた例を続けるに、入力モジュール１０２は、以下の各々を取得するように構成され得る：基底“Ａ１”及び目標ベクトル“ｙ１”に基づいて重み行列“Ｗ１”及びバイアスベクトル“ｂ１”；基底“Ａ２”及び目標ベクトル“ｙ２”に基づいて重み行列“Ｗ２”及びバイアスベクトル“ｂ２”；基底“Ａ３”及び目標ベクトル“ｙ３”に基づいて重み行列“Ｗ３”及びバイアスベクトル“ｂ３”；そして、基底“Ａ４”及び目標ベクトル“ｙ４”に基づいて重み行列“Ｗ４”及びバイアスベクトル“ｂ４”。
【００５０】
一部の実施形態において、取得された重み行列“Ｗｉ”及びバイアスベクトル“ｂｉ”は、モデルモジュール１０６に提供され得るモデル入力１１０に含められ得る。モデルモジュール１０６は、各重み行列“Ｗｉ”及びその対応するバイアスベクトル“ｂｉ”に対して、例えば上述したものなどの処理を実行して、対応する基底“Ａｉ”及び目標ベクトル“ｙｉ”に関する最近ベクトル問題の解とし得る対応する出力ベクトル“ｘｉ”を取得し得る。加えて、あるいは代えて、対応する出力ベクトル“ｘｉ”の各々がモデル出力１０８に含められ得る。
【００５１】
例えば、上であげた例を続けるに、モデルモジュール１０６は、以下の各々を取得するように構成され得る：重み行列“Ｗ１”及びバイアスベクトル“ｂ１”に基づくとともに、基底“Ａ１”によって規定される格子の、目標ベクトル“ｙ１”に対する最近ベクトルを表す出力ベクトル“ｘ１”；重み行列“Ｗ２”及びバイアスベクトル“ｂ２”に基づくとともに、基底“Ａ２”によって規定される格子の、目標ベクトル“ｙ２”に対する最近ベクトルを表す出力ベクトル“ｘ２”；重み行列“Ｗ３”及びバイアスベクトル“ｂ３”に基づくとともに、基底“Ａ３”によって規定される格子の、目標ベクトル“ｙ３”に対する最近ベクトルを表す出力ベクトル“ｘ３”；重み行列“Ｗ４”及びバイアスベクトル“ｂ４”に基づくとともに、基底“Ａ４”によって規定される格子の、目標ベクトル“ｙ４”に対する最近ベクトルを表す出力ベクトル“ｘ４”。これら又は他の実施形態において、生成された出力ベクトル“ｘ１”、“ｘ２”、“ｘ３”及び“ｘ４”は、モデル出力１０８に含められ得る。
【００５２】
一部の実施形態において、出力モジュール１１２は、生成された出力ベクトル“ｘｉ”及び対応する目標ベクトル“ｙｉ”に基づいて、最短ベクトル問題に対する解を決定するように構成され得る。例えば、出力モジュール１１２は、各出力ベクトル“ｘｉ”と、それぞれの出力ベクトル“ｘｉ”を得るために使用されたその対応する目標ベクトル“ｙｉ”との間の距離を決定するように構成され得る。これら又は他の実施形態において、出力モジュール１１２は、最短の決定された距離に対応する出力ベクトル“ｘｉ”が最短ベクトル問題に対する解であると決定し得る。これら又は他の実施形態において、出力モジュール１１２は、最短の決定された距離に対応する出力ベクトル“ｘｉ”を、対応するイニシャル基底に関する最短ベクトル問題の解として、格子問題解１１４に含めるように構成され得る。加えて、あるいは代えて、出力モジュール１１２は、距離決定を行う前又は後に、バイナリ変換を行うように構成され得る。
【００５３】
例えば、上であげた例を続けるに、出力モジュール１１２は、出力ベクトル“ｘ１”と目標ベクトル“ｙ１”との間の第１の距離と、出力ベクトル“ｘ２”と目標ベクトル“ｙ２”との間の第２の距離と、出力ベクトル“ｘ３”と目標ベクトル“ｙ３”との間の第３の距離と、出力ベクトル“ｘ４”と目標ベクトル“ｙ４”との間の第４の距離と、の各々を取得するように構成され得る。また、第１の距離が、最短の距離であることがある。出力モジュール１１２は、従って、出力ベクトル“ｘ１”を、最短ベクトル問題に対する解として提供するように構成され得る。これら又は他の実施形態において、出力モジュール１１２は、出力ベクトル“ｘ１”を、特定のイニシャル基底“ＡＩ”に関する最短ベクトル問題の解として、格子問題解１１４に含めるように構成され得る。
【００５４】
上で示したように、一部の実施形態において、環境１００は、格子問題を利用する特定の技術分野を向上させるように構成され得る。例えば、ＬＷＥ（learning  with  errors）ベースの暗号システムで、システムの安全性のレベルは、ＬＷＥ問題を解くことによって決定され得る。加えて、あるいは代えて、ＬＷＥ問題は、最近ベクトル問題として系統的に説明され得る。
【００５５】
一部の実施形態において、格子入力１０４は、特定のＬＷＥベースの暗号システムのＬＷＥ入力を含み得る。ＬＷＥ入力は、対応する暗号システムの有界誤差分布からのサンプルの行列と、有界誤差分布の行列を含むベクトル“ｃ”と、有界誤差分布から得られたサンプルのベクトル“ｅ”とを含み得る。一部の実施形態において、入力モジュール１０２は、任意の好適技術を用いてサンプルの行列及びベクトル“ｃ”から基底“Ａ”及び目標ベクトル“ｙ”を得ることによって、ＬＷＥ問題を最近ベクトル問題として策定するように構成され得る。何故なら、暗号の分野で知られているように、ＬＷＥは、特別な構造の最近ベクトル問題として見ることができるからである。規定“Ａ”及び目標ベクトル“ｙ”を得た後、入力モジュール１０２は、例えば上述したものなどの特定の最近ベクトル問題に対する解を得るために、上述のようにして、対応する“Ｗ”及び“ｂ”を生成するように構成され得る。この特定の最近ベクトル問題を解くことは、特定のＬＷＥベースの暗号システムの安全性に関する指標を提供するために使用されることができ、故に、可能性として、その特定のＬＷＥベースの暗号システムに変更を加えるために使用され得る。ＬＷＥベースの暗号システムに対する最近ベクトル問題の使用に関するもっと多くの情報は、２００９年５月２日付けのOdd  Regevによる“On  Lattices,  Learning  with  Errors,  Random  Linear  Codes,  and  Cryptography”と題された論文に見出すことができ、その全体を本開示に援用する。
【００５６】
例えば、特定の最近ベクトル問題を解くことができるということは、ＬＷＥベースの暗号システムによって実行される暗号化を破ることができるということにつながり得る。さらに、特定の最近ベクトル問題が解かれ得る速さがまた、対応するＬＷＥベースの暗号システムが解読され得る速さを指し示し得る。従って、アニーリングシステムを用いて、特定の最近ベクトル問題を解くこと、及び特定の最近ベクトル問題が解かれ得る速さは、関連する最近ベクトル問題を解くことの難しさを高めるためにＬＷＥベースの暗号システムにどのような変更を加え得るかを特定するために使用され得る。
【００５７】
また、他の一例として、環境１００は、格子問題を利用する無線通信を向上させるように構成され得る。例えば、中継機が複数の無線送信機から無線通信を受信する無線通信において、計算−転送（compute  and  forward）方式の中継技術がますます使用されるようになっている。中継機は、複数の伝送メッセージの線形結合を復号し、その線形結合を用いて個々のメッセージを再構成し得る。計算−転送技術の使用は、同じ物理層リソースを用いて複数のメッセージを伝送することを可能にし得る。一部の例において、最短ベクトル問題に対する解が、復号化を実行するために使用される係数ベクトルとして使用されることがある。最短ベクトル問題に対する解に基づいて決定された係数ベクトルは、中継機で実行され得る計算速度を向上又は最大化させ得る。
【００５８】
従って、一部の実施形態において、格子入力１０４は、計算−転送方式の中継に関して規定される特定の行列を含み得る。これら又は他の実施形態において、入力モジュール１０２は、その特定の行列を、例えば上述したものなどの、その特定の行列に関する特定の最短ベクトル問題を解くために環境１００によって使用され得るイニシャル基底“ＡＩ”として使用し得る。特定の最短ベクトル問題に対する解が、係数ベクトルとして使用され得る。
【００５９】
図１には、本開示の範囲を逸脱することなく、変更、付加又は省略が為され得る。例えば、環境１００は、本開示にて図示されて説明されるものよりも多い又は少ない要素を含み得る。
【００６０】
図２は、本開示の少なくとも１つの実施形態に従った、格子関連問題を解くように構成されたコンピューティングシステム２０２の一例のブロック図を示している。コンピューティングシステム２０２は、イジングモデル入力モジュール（例えば、図１の入力モジュール１０２）、イジングモデルモジュール（例えば、図１のモデルモジュール１０６）、及び／又はイジングモデル出力モジュール（例えば、図１の出力モジュール１１２）に関連する１つ以上の処理を実行又は指示するように構成され得る。一部の実施形態において、コンピューティングシステム２０２は、アニーリングシステムに含められてもよいし、その一部を形成してもよい。コンピューティングシステム２０２は、プロセッサ２５０、メモリ２５２、及びデータストレージ２５４を含み得る。プロセッサ２５０、メモリ２５２、及びデータストレージ２５４は、通信可能に結合され得る。
【００６１】
一般に、プロセッサ２５０は、様々なコンピュータハードウェア若しくはソフトウェアモジュールを含んだ、如何なる好適な専用又は汎用のコンピュータ、コンピューティングエンティティ又は処理装置を含んでいてもよく、何らかの適用可能なコンピュータ読み取り可能媒体に格納された命令を実行するように構成され得る。例えば、プロセッサ２５０は、マイクロプロセッサ、マイクロコントローラ、デジタル信号プロセッサ（ＤＳＰ）、特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、又はプログラム命令を解釈及び／又は実行し且つ／或いはデータを処理するように構成されたその他のデジタル回路若しくはアナログ回路を含み得る。図２では単一のプロセッサとして示されているが、プロセッサ２５０は、本開示に記載される任意数の処理を個々あるいは集合的に実行する又はそれらの実行を指示するように構成された任意数のプロセッサを含んでいてもよい。さらに、それらのプロセッサのうちの１つ以上が、例えば異なるサーバなどの、１つ以上の異なるエレクトロニクス装置上に存在してもよい。
【００６２】
一部の実施形態において、プロセッサ２５０は、メモリ２５２、データストレージ２５４、又はメモリ２５２とデータストレージ２５４、に格納されたプログラム命令及び／又はデータについて、プログラム命令を解釈及び／又は実行し且つ／或いはデータを処理するように構成され得る。一部の実施形態において、プロセッサ２５０は、データストレージ２５４からプログラム命令をフェッチして該プログラム命令をメモリ２５２にロードし得る。プログラム命令がメモリ２５２にロードされた後、プロセッサ２５０が該プログラム命令を実行し得る。
【００６３】
メモリ２５２及びデータストレージ２５４は、コンピュータ実行可能命令又はデータ構造を担持する、あるいは格納した、コンピュータ読み取り可能記憶媒体を含み得る。そのようなコンピュータ読み取り可能記憶媒体は、例えばプロセッサ２５０などの汎用又は専用のコンピュータによってアクセスされ得る如何なる入手可能な非一時的媒体をも含み得る。限定ではなく例として、そのようなコンピュータ読み取り可能記憶媒体は、ランダムアクセスメモリ（ＲＡＭ）、読み出し専用メモリ（ＲＯＭ）、電気的消去・プログラム可能型読み出し専用メモリ（ＥＥＰＲＯＭ）、コンパクトディスク読み出し専用メモリ（ＣＤ−ＲＯＭ）若しくはその他の光ディスクストレージ、磁気ディスクストレージ若しくはその他の磁気記憶装置、フラッシュメモリデバイス（例えば、ソリッドステートメモリデバイス）、又は、コンピュータ実行可能命令の形態の特定のプログラムコード若しくはデータ構造を担持あるいは格納するために使用されることができ且つ汎用若しくは専用のコンピュータによってアクセスされることが可能なその他の非一時的記憶媒体を含む、有形の又は非一時的なコンピュータ読み取り可能記憶媒体を含み得る。これら及び他の実施形態において、本開示にて説明される用語“非一時的な”は、Ｎｕｉｊｔｅｎ，５００  Ｆ．３ｄ  １３４６に関しての連邦巡回控訴裁判所の決定（Ｆｅｄ．Ｃｉｒ．２００７）において特許可能な主題の範囲外であることが判明したタイプの一時的媒体のみを除外するように解釈されるべきである。以上のものの組合せもコンピュータ読み取り可能媒体の範囲に含まれ得る。
【００６４】
以上のものの組合せもコンピュータ読み取り可能記憶媒体の範囲に含まれ得る。コンピュータ実行可能命令は、例えば、特定の処理又は処理群をプロセッサ２５０に実行させるように構成された命令及びデータを含み得る。
【００６５】
コンピューティングシステム２０２には、本開示の範囲を逸脱することなく、変更、付加又は省略が為され得る。例えば、一部の実施形態において、コンピューティングシステム２０２は、明示的には図示あるいは記載されていない任意数のその他のコンポーネントを含んでいてもよい。
【００６６】
図３は、本開示にて記載される少なくとも１つの実施形態に従った、最近ベクトル格子問題を解く方法３００の一例のフローチャートである。方法３００は、如何なる好適なシステム、機器、又は装置によって実行されてもよい。例えば、方法３００の１つ以上の動作は、図１の環境１００の１つ以上の要素によって、又は複数の図２のコンピューティングシステム２０２のうちの１つ以上によって実行され得る。別個のブロックとして図示されるが、具体的な実装に応じて、方法３００のブロックのうちの１つ以上と関連付けられるステップ及び処理が、更なるブロックへと分割され、より少ないブロックへと結合され、あるいは排除され得る。
【００６７】
方法３００は、ブロック３０２で開始することができ、そこで、ｍ次元空間内の格子を規定する基底“Ａ”が取得され得る。格子は、ｍ次元空間内の複数の点を含み得る。また、基底“Ａ”は、“ｎ”個の線形の独立したベクトルの行列とすることができ、それぞれのベクトル各々が、ｍ次元空間における位置を規定する“ｍ”個の要素を有し、格子のそれぞれの点各々が、基底の前記ベクトルの線形結合に関して規定される。ブロック３０４にて、ｍ次元空間内の特定の位置を規定する目標ベクトル“ｙ”が取得され得る。
【００６８】
一部の実施形態において、基底“Ａ”及び目標ベクトル“ｙ”は、例えば図１に関して上述したものなどの、ＬＷＥベースの暗号システムの安全性を決定することに対応するＬＷＥ問題のＬＷＥ入力に基づいて取得され得る。加えて、あるいは代えて、基底“Ａ”及び目標ベクトル“ｙ”は、例えば上述し且つ図４の方法４００に関して後述するものなどのイニシャル基底“ＡＩ”に対応する最短ベクトル問題を解くことに関して提供され得るイニシャル基底“ＡＩ”に基づいて取得され得る。これら又は他の実施形態において、イニシャル基底“ＡＩ”は、例えば上述したものなどの計算−転送中継スキームに関して取得されてもよい。
【００６９】
ブロック３０６にて、基底“Ａ”に基づいて、イジングモデル連結重み行列“Ｗ”が生成され得る。例えば、イジングモデル連結重み行列“Ｗ”は、上述したように、“Ａ”の転置（“ＡＴ”）に“Ａ”を乗算することによって生成され得る。
【００７０】
ブロック３０８にて、基底“Ａ”及び目標ベクトル“ｙ”に基づいて、イジングモデルバイアスベクトル“ｂ”が生成され得る。例えば、イジングモデルバイアスベクトル“ｂ”は、上述のように、“ｙ”の転置（“ｙＴ”）に“Ａ”を乗算することによって生成され得る。
【００７１】
一部の実施形態において、“Ｗ”及び“ｂ”の要素は、上述のように、イジングモデルへの“Ｗ”及び“ｂ”の入力を可能にするよう、バイナリフォーマットに変換され得る。これら又は他の実施形態において、上述のように、“Ｗ”及び“ｂ”の要素に関するビット数が、限度“ｒ”に基づいて決定され得る。例えば、一部の実施形態において、限度“ｒ”は、“Ａ”によって規定される行列式に基づいて決定され得る。これらの又は他の実施形態において、その行列式は、“Ａ”の行列式を求めることによって求められ得る。
【００７２】
ブロック３１０にて、“Ｗ”及び“ｂ”が、イジングモデルに従って記述された問題を解くように構成されたアニーリングシステムに提供され得る。上述したように格子の基底“Ａ”と、目標ベクトル“ｙ”と、最近ベクトル問題とに従って決定されたものである、決定された重み行列“Ｗ”及び決定されたバイアスベクトル“ｂ”に基づいて、アニーリングシステムは、格子における、目標ベクトル“ｙ”によって規定される特定の位置に最も近い点、に対応する出力ベクトル“ｘ”を決定するように構成され得る。
【００７３】
ブロック３１２にて、出力ベクトル“ｘ”を表す出力が、アニーリングシステムから取得され得る。ブロック３１４にて、出力ベクトル“ｘ”が用いて、最近ベクトル問題に対する解を取得し得る。例えば、一部の実施形態において、出力ベクトル“ｘ”が、アニーリングシステムによって出力されたままのバイナリ表現から、最近ベクトル問題に対する解として使用され得る１０進表現へと変換され得る。
【００７４】
方法３００には、本開示の範囲を逸脱することなく、変更、付加又は省略が為され得る。例えば、方法３００の処理は、異なる順序で実行されてもよい。加えて、あるいは代えて、２つ以上の処理が同時に実行されてもよい。また、概説した処理及びアクションは、単に例として提示したものであり、開示した実施形態の本質を逸脱することなく、これらの処理及びアクションの一部は、オプション必要に応じてのものにされ、より少ない処理やアクションへと結合され、あるいは更なる処理やアクションへと展開され得る。
【００７５】
加えて、あるいは代えて、２つ以上の処理が同時に実行されてもよい。また、概説した処理及びアクションは、単に例として提示したものであり、開示した実施形態の本質を逸脱することなく、これらの処理及びアクションの一部は、オプション必要に応じてのものにされ、より少ない処理やアクションへと結合され、あるいは更なる処理やアクションへと展開され得る。例えば、一部の実施形態において、方法３００は、出力ベクトル“ｘ”をバイナリフォーマットから別のフォーマット（例えば、１０進フォーマット）へと変換することに関係する１つ以上の処理を含み得る。
【００７６】
図４は、本開示にて記載される少なくとも１つの実施形態に従った、最短ベクトル格子問題を解く方法４００の一例のフローチャートである。方法４００は、如何なる好適なシステム、機器、又は装置によって実行されてもよい。例えば、方法４００の１つ以上の動作は、図１の環境１００の１つ以上の要素によって、又は複数の図２のコンピューティングシステム２０２のうちの１つ以上によって実行され得る。別個のブロックとして図示されるが、具体的な実装に応じて、方法４００のブロックのうちの１つ以上と関連付けられるステップ及び処理が、更なるブロックへと分割され、より少ないブロックへと結合され、あるいは排除され得る。
【００７７】
方法４００は、ブロック４０２で開始することができ、そこで、ｍ次元空間内の格子を規定するイニシャル基底“ＡＩ”が取得され得る。格子は、ｍ次元空間内の複数の点を含み得る。また、イニシャル基底“ＡＩ”は、“ｎ”個の線形の独立したベクトルの行列とすることができ、それぞれのベクトル各々が、ｍ次元空間における位置を規定する“ｍ”個の要素を有し、格子のそれぞれの点各々が、基底の前記ベクトルの線形結合に関して規定される。一部の実施形態において、イニシャル基底“ＡＩ”は、例えば上述したものなどの計算−転送中継に関連する最短ベクトル問題に対応し得る。
【００７８】
ブロック４０４にて、イニシャル基底“ＡＩ”から“Ａｉ”を取得することができ、“Ａｉ”は、“ＡＩ”の特定のベクトル“ｉ”の要素が“Ａｉ”においては２倍にされていることを除いて“ＡＩ”と同じである。一部の実施形態において、“ＡＩ”の全てのベクトルに対して基底“Ａｉ”が取得され得る。各基底“Ａｉ”は、一部の実施形態における図１の最短ベクトル問題の説明にて上述したようにして取得され得る。
【００７９】
ブロック４０６にて、それぞれの基底“Ａｉ”に対応する目標ベクトル“ｙｉ”が取得され得る。これらの又は他の実施形態において、各目標ベクトル“ｙｉ”がそれぞれの基底“Ａｉ”に対応する複数の目標ベクトル“ｙｉ”が取得され得る。一部の実施形態において、目標ベクトル“ｙｉ”は、一部の実施形態における図１の最短ベクトル問題の説明にて上述したように、対応する特定のベクトル“ｉ”をそれぞれの目標ベクトル“ｙｉ”として用いることによって取得され得る。
【００８０】
ブロック４０８にて、各基底“Ａｉ”及び対応する目標ベクトル“ｙｉ”に対して、最近ベクトル問題解出力ベクトル“ｘｉ”が取得され得る。例えば、一部の実施形態において、方法３００のブロック３０２及び３０４で、各基底“Ａｉ”及び対応する目標ベクトル“ｙｉ”が取得され、次いで、それに従ってブロック３０６、３０８、３１０、３１２、及び３１４の処理が実行されることで、各出力ベクトル“ｘｉ”が取得され得る。
【００８１】
ブロック４１０にて、各目標ベクトル“ｙｉ”とそれに対応する出力ベクトル“ｘｉ”との間の距離が決定され得る。ブロック４１２にて、ブロック４１０での決定に基づいて、どの出力ベクトル“ｘｉ”が最短の決定された距離に対応するかについて決定され得る。ブロック４１４にて、最短距離に対応する出力ベクトル“ｘｉ”を用いて、イニシャル基底“ＡＩ”に関する最短ベクトル問題の解を取得し得る。例えば、一部の実施形態において、出力ベクトル“ｘｉ”が、アニーリングシステムによって出力されたままのバイナリ表現から、最短ベクトル問題に対する解として使用され得る１０進表現へと変換され得る。これら又は他の実施形態において、イニシャル基底“ＡＩ”が計算−転送中継スキームに基づく場合、最短距離に対応する出力ベクトル“ｘｉ”が、対応する中継機の計算速度を最大化し得る係数ベクトルとして使用され得る。
【００８２】
方法４００には、本開示の範囲を逸脱することなく、変更、付加又は省略が為され得る。例えば、方法４００の処理は、異なる順序で実行されてもよい。加えて、あるいは代えて、２つ以上の処理が同時に実行されてもよい。また、概説した処理及びアクションは、単に例として提示したものであり、開示した実施形態の本質を逸脱することなく、これらの処理及びアクションの一部は、オプション必要に応じてのものにされ、より少ない処理やアクションへと結合され、あるいは更なる処理やアクションへと展開され得る。
【００８３】
上述のように、本開示にて記載された実施形態は、更に詳細に後述するような、様々なコンピュータハードウェア若しくはソフトウェアモジュールを含んだ、専用又は汎用のコンピュータ（例えば、図２のプロセッサ２５０）の使用を含み得る。また、上述のように、本開示にて記載される実施形態は、コンピュータ実行可能命令又はデータ構造を担持あるいは格納したコンピュータ読み取り可能媒体（例えば、図２のメモリ２５２又はデータストレージ２５４）を用いて実装され得る。
【００８４】
本開示にて使用されるとき、用語“モジュール”又は“コンポーネント”は、モジュール若しくはコンポーネントの動作を実行するように構成された特定のハードウェア実装、及び／又は、コンピュータシステムの汎用ハードウェア（例えば、コンピュータ読み取り可能媒体、処理装置など）に格納され且つ／或いはそれによって実行され得るソフトウェアオブジェクト若しくはソフトウェアルーチンを意味し得る。一部の実施形態において、本開示にて記載された様々なコンポーネント、モジュール、エンジン及びサービスは、コンピュータシステム上で（例えば、別々のスレッドとして）実行される複数のオブジェクト又はプロセスとして実装され得る。本開示にて記載されたシステム及び方法の一部は概して、（汎用ハードウェアに格納され且つ／或いはそれによって実行される）ソフトウェアにて実装されるとして記述されているが、特有のハードウェア実装、又はソフトウェアと特有のハードウェアとの組み合わせ実装も可能であり且つ企図される。この記載において、“コンピューティングエンティティ”は、本開示にて先に規定されるような何らかのコンピューティングシステム、又はコンピューティングシステム上で実行される何らかのモジュール若しくは複数のモジュールの組み合わせとし得る。
【００８５】
本開示及び特に添付の請求項（例えば、添付の請求項の本体）で使用される用語は概して、“オープン”用語として意図している（例えば、用語“・・・を含んでいる”は、“・・・を含んでいるが、それに限定されない”として解釈されるべきであり、用語“・・・を有している”は、“少なくとも・・・を有している”として解釈されるべきであり、用語“・・・を含む”は、“・・・を含むが、それに限定されない”と解釈されるべきであり、等々）。
【００８６】
また、導入されるクレーム記載の具体数が意図される場合、そのような意図は、請求項中に明示的に記載されることになり、そのような記載がない場合、そのような意図は存在しない。例えば、理解の助けとして、以下に添付される請求項は、クレーム記載を導入するために“少なくとも１つの”及び“１つ以上の”という前置きフレーズの使用を含むことがある。しかしながら、このようなフレーズの使用は、例え同じクレームが“少なくとも１つの”及び“１つ以上の”という前置きフレーズと“ａ”又は“ａｎ”などの不定冠詞とを含んでいるときであっても、不定冠詞“ａ”又は“ａｎ”によるクレーム記載の導入が、そのように導入されたクレーム記載を含む何れか特定の請求項を、唯一のそのような記載を含む実施形態に限定することを意味するようには、解釈されるべきでない（例えば、“ａ”及び／又は“ａｎ”は、“少なくとも１つの”又は“１つ以上の”を意味するように解釈されるべきである）。同じことが、クレーム記載を導入するために使用される定冠詞の使用にもあてはまる。
【００８７】
さらに、導入されるクレーム記載の具体数が明示的に記載されている場合であっても、当業者が認識するように、そのような記載は、少なくとも記載の数を意味するように解釈されるべきである（例えば、他の修飾語句のない、そのまま“２つのもの”なる記載は、少なくとも２つのもの、又は２つ以上のものを意味する）。また、“Ａ、Ｂ、及びＣなどのうちの少なくとも１つ”又は“Ａ、Ｂ、及びＣなどのうちの１つ以上”に似た伝統的表現が使用されるものにおいては、一般に、そのような構文は、Ａのみ、Ｂのみ、Ｃのみ、ＡとＢを共に、ＡとＣを共に、ＢとＣを共に、又は、ＡとＢとＣを共に、などを含むことを意図している。さらに、用語“及び／又は”の使用は、このように解釈されることを意図している。
【００８８】
また、２つ以上の別の用語を提示する離接的な用語又はフレーズは、実施形態の説明、特許請求の範囲、又は図面の中の何れであろうと、それらの用語のうちの１つ、それらの用語のうちの何れか、又は双方の用語を含む可能性を意図しているように理解されるべきである。例えば、フレーズ“Ａ又はＢ”は、用語“及び／又は”が別のところに使用されていたとしても、“Ａ”若しくは“Ｂ”又は“Ａ及びＢ”の可能性を含むように理解されるべきである。
【００８９】
本開示にて記載された全ての例及び条件付きの言葉は、本開示と技術を前進させるために本願の発明者によって与えられる概念とを読者が理解することを支援するための教育的な目的を意図したものであり、そのように具体的に記載した例及び条件への限定ではないと解釈されるべきである。本開示の実施形態を詳細に説明したが、これらの実施形態には、本開示の精神及び範囲を逸脱することなく、様々な変形、代用及び改変が為され得る。
【００９０】
以上の説明に関し、更に以下の付記を開示する。
（付記１）  ｍ次元空間内の格子を規定する基底“Ａ”を取得し、前記格子は、前記ｍ次元空間内の複数の点を含み、前記基底“Ａ”は、“ｎ”個の線形の独立したベクトルの行列であり、それぞれのベクトル各々が、前記ｍ次元空間における位置を規定する“ｍ”個の要素を有し、前記格子のそれぞれの点各々が、前記基底の前記ベクトルの線形結合に関して規定され、
前記ｍ次元空間内の特定の位置を規定する目標ベクトル“ｙ”を取得し、
“Ａ”の転置（“ＡＴ”）に“Ａ”を乗算することによって、イジングモデル連結重み行列“Ｗ”を生成し、
“ｙ”の転置（“ｙＴ”）に“Ａ”を乗算することによって、イジングモデルバイアスベクトル“ｂ”を生成し、
イジングモデルに従って記述された問題を解くように構成されたアニーリングシステムに“Ｗ”及び“ｂ”を提供し、
前記格子に含まれる特定の点の出力ベクトル“ｘ”を表す出力を前記アニーリングシステムから取得し、前記特定の点は、前記格子における、“ｙ”によって規定される前記特定の位置に最も近い点であり、
前記格子におけるどの点が、“ｙ”によって規定される前記特定の位置に最も近いかを見つけることとして定義される最近ベクトル問題に対する解を、“ｘ”を用いて得る、
ことを有する方法。
（付記２）  前記ｍ次元空間内の別の格子を規定するイニシャル基底“ＡＩ”から“Ａ”を取得し、“ＡＩ”の特定のベクトル“ｉ”の要素が“Ａ”においては２倍にされていることを除いて“Ａ”は“ＡＩ”と同じであり、
前記特定のベクトル“ｉ”を目標ベクトル“ｉ”として用いることによって、“ＡＩ”から前記目標ベクトル“ｙ”を取得し、
前記目標ベクトル“ｙ”と前記出力ベクトル“ｘ”との間の距離を決定し、
前記別の格子におけるどの点が最短ベクトルを持つかを見つけることとして定義される最短ベクトル問題に対する解を求める際に、前記目標ベクトル“ｙ”と前記出力ベクトル“ｘ”との間の前記距離を使用する、
ことを更に有する付記１に記載の方法。
（付記３）  前記イニシャル基底“ＡＩ”の全ベクトルに対して付記２の処理を繰り返して、各目標ベクトル“ｙ”とその対応する出力ベクトル“ｘ”との間の距離として複数の距離を取得し、
前記複数の距離のうちの最短距離に対応する特定の出力ベクトル“ｘ”を、前記最短ベクトル問題に対する前記解として使用する、
ことを更に有する付記２に記載の方法。
（付記４）  前記最短ベクトル問題に対する前記解を使用して、コンピュートアンドフォワード問題を解く、ことを更に有する付記２に記載の方法。
（付記５）  前記アニーリングシステムへの“Ｗ”及び“ｂ”の入力を可能にするために、“Ｗ”及び“ｂ”の値をバイナリフォーマットに変換する、ことを更に有する付記１に記載の方法。
（付記６）  前記格子の行列式に基づいて“Ｗ”及び“ｂ”のためのビット数を決定することを更に有する付記５に記載の方法。
（付記７）
前記行列式を、“Ａ”の行列式を求めることによって求める、ことを更に有する付記６に記載の方法。
（付記８）  誤差ベースの暗号システムによる特定の学習が安全であるかを、“ｘ”を用いて検査する、ことを更に有する付記１に記載の方法。
（付記９）  命令を格納した１つ以上のコンピュータ読み取り可能記憶媒体であって、前記命令は、実行されることに応答してシステムに処理を実行させ、前記処理は、
ｍ次元空間内の格子を規定する基底“Ａ”を取得し、前記格子は、前記ｍ次元空間内の複数の点を含み、前記基底“Ａ”は、“ｎ”個の線形の独立したベクトルの行列であり、それぞれのベクトル各々が、前記ｍ次元空間における位置を規定する“ｍ”個の要素を有し、前記格子のそれぞれの点各々が、前記基底の前記ベクトルの線形結合に関して規定され、
前記ｍ次元空間内の特定の位置を規定する目標ベクトル“ｙ”を取得し、
“Ａ”の転置（“ＡＴ”）に“Ａ”を乗算することによって、イジングモデル連結重み行列“Ｗ”を生成し、
“ｙ”の転置（“ｙＴ”）に“Ａ”を乗算することによって、イジングモデルバイアスベクトル“ｂ”を生成し、
イジングモデルに従って記述された問題を解くように構成されたアニーリングシステムに“Ｗ”及び“ｂ”を提供し、
前記格子に含まれる特定の点の出力ベクトル“ｘ”を表す出力を前記アニーリングシステムから取得し、前記特定の点は、前記格子における、“ｙ”によって規定される前記特定の位置に最も近い点であり、
前記格子におけるどの点が、“ｙ”によって規定される前記特定の位置に最も近いかを見つけることとして定義される最近ベクトル問題に対する解を、“ｘ”を用いて得る、
ことを有する、１つ以上のコンピュータ読み取り可能記憶媒体。
（付記１０）  前記処理は更に、
前記ｍ次元空間内の別の格子を規定するイニシャル基底“ＡＩ”から“Ａ”を取得し、“ＡＩ”の特定のベクトル“ｉ”の要素が“Ａ”においては２倍にされていることを除いて“Ａ”は“ＡＩ”と同じであり、
前記特定のベクトル“ｉ”を目標ベクトル“ｉ”として用いることによって、“ＡＩ”から前記目標ベクトル“ｙ”を取得し、
前記目標ベクトル“ｙ”と前記出力ベクトル“ｘ”との間の距離を決定し、
前記別の格子におけるどの点が最短ベクトルを持つかを見つけることとして定義される最短ベクトル問題に対する解を求める際に、前記目標ベクトル“ｙ”と前記出力ベクトル“ｘ”との間の前記距離を使用する、
ことを有する、付記９に記載の１つ以上のコンピュータ読み取り可能記憶媒体。
（付記１１）  前記処理は更に、
前記イニシャル基底“ＡＩ”の全ベクトルに対して付記１０の処理を繰り返して、各目標ベクトル“ｙ”とその対応する出力ベクトル“ｘ”との間の距離として複数の距離を取得し、
前記複数の距離のうちの最短距離に対応する特定の出力ベクトル“ｘ”を、前記最短ベクトル問題に対する前記解として使用する、
ことを有する、付記１０に記載の１つ以上のコンピュータ読み取り可能記憶媒体。
（付記１２）  前記処理は更に、前記最短ベクトル問題に対する前記解を使用して、計算−転送問題を解くことを有する、付記１０に記載の１つ以上のコンピュータ読み取り可能記憶媒体。
（付記１３）  前記処理は更に、前記アニーリングシステムへの“Ｗ”及び“ｂ”の入力を可能にするために、“Ｗ”及び“ｂ”の値をバイナリフォーマットに変換することを有する、付記９に記載の１つ以上のコンピュータ読み取り可能記憶媒体。
（付記１４）  前記処理は更に、前記格子の行列式に基づいて“Ｗ”及び“ｂ”のためのビット数を決定することを有する、付記１３に記載の１つ以上のコンピュータ読み取り可能記憶媒体。
（付記１５）  前記処理は更に、誤差ベースの暗号システムによる特定の学習が安全であるかを、“ｘ”を用いて検査することを有する、付記９に記載の１つ以上のコンピュータ読み取り可能記憶媒体。
（付記１６）  システムであって、
命令を格納した１つ以上のコンピュータ読み取り可能記憶媒体と、
前記１つ以上のコンピュータ読み取り可能記憶媒体に通信可能に結合され、前記命令の実行に応答して当該システムに処理を実行させるように構成された１つ以上のプロセッサと、
を有し、前記処理は、
ｍ次元空間内の格子を規定する基底“Ａ”を取得し、前記格子は、前記ｍ次元空間内の複数の点を含み、前記基底“Ａ”は、“ｎ”個の線形の独立したベクトルの行列であり、それぞれのベクトル各々が、前記ｍ次元空間における位置を規定する“ｍ”個の要素を有し、前記格子のそれぞれの点各々が、前記基底の前記ベクトルの線形結合に関して規定され、
前記ｍ次元空間内の特定の位置を規定する目標ベクトル“ｙ”を取得し、
“Ａ”の転置（“ＡＴ”）に“Ａ”を乗算することによって、イジングモデル連結重み行列“Ｗ”を生成し、
“ｙ”の転置（“ｙＴ”）に“Ａ”を乗算することによって、イジングモデルバイアスベクトル“ｂ”を生成し、
イジングモデルに従って記述された問題を解くように構成されたアニーリングシステムに“Ｗ”及び“ｂ”を提供し、
前記格子に含まれる特定の点の出力ベクトル“ｘ”を表す出力を前記アニーリングシステムから取得し、前記特定の点は、前記格子における、“ｙ”によって規定される前記特定の位置に最も近い点であり、
前記格子におけるどの点が、“ｙ”によって規定される前記特定の位置に最も近いかを見つけることとして定義される最近ベクトル問題に対する解を、“ｘ”を用いて得る、
ことを有する、システム。
（付記１７）  前記処理は更に、
前記ｍ次元空間内の別の格子を規定するイニシャル基底“ＡＩ”から“Ａ”を取得し、“ＡＩ”の特定のベクトル“ｉ”の要素が“Ａ”においては２倍にされていることを除いて“Ａ”は“ＡＩ”と同じであり、
前記特定のベクトル“ｉ”を目標ベクトル“ｉ”として用いることによって、“ＡＩ”から前記目標ベクトル“ｙ”を取得し、
前記目標ベクトル“ｙ”と前記出力ベクトル“ｘ”との間の距離を決定し、
前記別の格子におけるどの点が最短ベクトルを持つかを見つけることとして定義される最短ベクトル問題に対する解を求める際に、前記目標ベクトル“ｙ”と前記出力ベクトル“ｘ”との間の前記距離を使用する、
ことを有する、付記１６に記載のシステム。
（付記１８）  前記処理は更に、
前記イニシャル基底“ＡＩ”の全ベクトルに対して付記１７の処理を繰り返して、各目標ベクトル“ｙ”とその対応する出力ベクトル“ｘ”との間の距離として複数の距離を取得し、
前記複数の距離のうちの最短距離に対応する特定の出力ベクトル“ｘ”を、前記最短ベクトル問題に対する前記解として使用する、
ことを有する、付記１７に記載のシステム。
（付記１９）  前記処理は更に、前記最短ベクトル問題に対する前記解を使用して、計算−転送問題を解くことを有する、付記１７に記載のシステム。
（付記２０）  前記処理は更に、前記アニーリングシステムへの“Ｗ”及び“ｂ”の入力を可能にするために、“Ｗ”及び“ｂ”の値をバイナリフォーマットに変換することを有する、付記１６に記載のシステム。
【図１】
2020071877.tif 000006
【図２】
2020071877.tif 000007
【図３】
2020071877.tif 000008
【図４】
2020071877.tif 000009