(57)【要約】【課題】格子問題を効率的に解く。【解決手段】まず、古典計算によって基底Ｂについての双対基底Ｂ−を得る。次に、複数の整数について格子Ｌ（Ｂ）をｔの整数倍分平行移動させて得られる集合の和集合に含まれる点列の周期性を利用した量子計算を行い、ｊ＝１，…，ｍについて、ｎ次元ベクトルｒｊ＝（ｒｊ１，…，ｒｊｎ）およびｒｊ０を得る。その後、古典計算によってｎ次元ベクトルｒｊに最も近い最近ベクトルｒｊ（ｃ）＝（ｒｊ１（ｃ），…，ｒｊｎ（ｃ））∈Ｌ（Ｂ−）およびｒｊ（ｃ）に対応する差分ベクトルｒｊ（ｄ）＝ｒｊ−ｒｊ（ｃ）＝（ｒｊ１（ｄ），…，ｒｊｎ（ｄ））を得る。【選択図】図４
2019079226.tif 000002
【特許請求の範囲】
【請求項１】
ｎ，ｍ，Ｍ，Ｎが正の整数であり、Ｍ＜Ｎであり、ｉ＝１，…，ｎであり、ｊ＝１，…，ｍであり、ηＴがηの転置であり、｜Λ｜がΛの要素数であり、ｒｏｕｎｄ（μ）がμに最も近い整数であり、ｆｌｏｏｒ（μ）がμ以下の最大の整数であり、ｃｅｉｌ（μ）がμ以上の最小の整数であり、ｄｅｔ（η）がηの行列式であり、Ｂ＝｛ｂ１，…，ｂｎ｝が一次独立なｎ個のｎ次元ベクトルｂｉからなる基底であり、前記ｎ次元ベクトルｂｉのそれぞれがｎ個の整数要素からなり、βが前記基底Ｂの前記ｎ次元ベクトルｂ１，…，ｂｎを要素とするｎ行ｎ列の基底行列であり、ｔ＝（ｔ１，…，ｔｎ）Ｔがｎ個の整数要素ｔｉからなる目標ベクトルであり、ｘｉが整数であり、Ｌ（Ｂ）が格子｛Σｉ＝１，…，ｎ  ｘｉｂｉ｜ｘｉ∈Ｚ，ｂｉ∈Ｂ｝であり、τがｎ次元ベクトルであり、τ＋Ｌ（Ｂ）＝Ｌ（Ｂ）＋τ＝｛τ＋χ｜χ∈Ｌ（Ｂ）｝であり、ｒｊｉ（ｃ），ｒｊｉ（ｄ），ｒｊ０，ｅｊが整数であり、ｔ（ｄ）が前記目標ベクトルｔと前記目標ベクトルｔに最も近い最近ベクトルｔ（ｃ）∈Ｌ（Ｂ）との差分ベクトルｔ（ｄ）＝ｔ−ｔ（ｃ）＝（ｔ１（ｄ），…，ｔｎ（ｄ））Ｔであり、ｓが整数要素からなるｎ次元ベクトルであり、
前記基底Ｂおよび前記目標ベクトルｔの入力に対し、
【数２２】
2019079226.tif 000024
を満たす｛ｒｊｉ（ｃ），ｒｊｉ（ｄ），ｒｊ０｝およびｍ，Ｍ，Ｎを出力する変換装置であって、
前記基底行列βの逆行列β−１の要素の分母の最小公倍数Ｎ’の倍数Ｎを選択し、前記基底ＢのＮ’に関する双対基底Ｂ−’＝｛ｂ１−’，…，ｂｎ−’｝についてＮに関する双対基底Ｂ−＝｛（Ｎ／Ｎ’）ｂ１−’，…，（Ｎ／Ｎ’）ｂｎ−’｝を得る第１古典計算部と、
ＢＲが［０，Ｎ）ｎに含まれる点の集合であり、ｃｅｉｌ（ｌｏｇ２ Ｍ）個の量子ビットからなるインデックスレジスタと、ｎ×ｃｅｉｌ（ｌｏｇ２ Ｎ）個の量子ビットからなるデータレジスタと、ｎ×ｃｅｉｌ（ｌｏｇ２ ｄｅｔ（β））個の量子ビットからなるワークレジスタとからなるレジスタ列の量子状態を
【数２３】
2019079226.tif 000025
にする量子状態生成部と、
前記インデックスレジスタに対するＭ次元量子フーリエ変換を実行し、前記レジスタ列の量子状態を
【数２４】
2019079226.tif 000026
にする第１量子フーリエ変換部と、
ｘ−ｗｔ＝ｙｗ，ｘ，１ｂ１＋…＋ｙｗ，ｘ，ｎｂｎを満たし、前記第１量子フーリエ変換部で得られた量子状態の前記レジスタ列に対して量子状態｜ｗ＞｜ｘ＞｜０＞を量子状態｜ｗ＞｜ｘ＞｜ｄｅｔ（β）（ｙｗ，ｘ，１−ｆｌｏｏｒ（ｙｗ，ｘ，１）），…，ｄｅｔ（β）（ｙｗ，ｘ，ｎ−ｆｌｏｏｒ（ｙｗ，ｘ，ｎ））＞にする量子操作を実行する操作部と、
前記操作部で得られた量子状態の前記ワークレジスタを観測し、前記インデックスレジスタおよび前記データレジスタの量子状態を
【数２５】
2019079226.tif 000027
にする第１観測部と、
前記第１観測部での観測後の量子状態の前記データレジスタに対するＮ次元量子フーリエ変換を実行する第２量子フーリエ変換部と、
前記第２量子フーリエ変換部で得られた量子状態の前記データレジスタを観測して観測結果（ｒｊ１，…，ｒｊｎ）を得る第２観測部と、
前記第２観測部での観測後の量子状態の前記インデックスレジスタに対するＭ次元逆量子フーリエ変換を実行する逆量子フーリエ変換部と、
前記逆量子フーリエ変換部で得られた量子状態の前記インデックスレジスタを観測して観測結果ｒｊ０を得る第３観測部と、
前記第１古典計算部で得られた前記双対基底Ｂ−、および、前記量子状態生成部と前記第１量子フーリエ変換部と前記操作部と前記第１観測部と前記第２量子フーリエ変換部と前記第２観測部と前記第３観測部の処理をｊ＝１，…，ｍについて行って得られた前記観測結果（ｒｊ１，…，ｒｊｎ）およびｒｊ０を入力とし、双対格子Ｌ（Ｂ−）＝｛Σｉ＝１，…，ｎ  ｘｉｂ−ｉ｜ｘｉ∈Ｚ，ｂ−ｉ∈Ｂ−｝およびｎ次元ベクトルｒｊ＝（ｒｊ１，…，ｒｊｎ）について、前記ｎ次元ベクトルｒｊに最も近い最近ベクトルｒｊ（ｃ）＝（ｒｊ１（ｃ），…，ｒｊｎ（ｃ））∈Ｌ（Ｂ−）および差分ベクトルｒｊ（ｄ）＝ｒｊ−ｒｊ（ｃ）＝（ｒｊ１（ｄ），…，ｒｊｎ（ｄ））を得る第２古典計算部と、
を有する変換装置。
【請求項２】
ｎ，ｍ，ｍ’，Ｍ，Ｎ，Ｎ’が正の整数であり、Ｍ＜Ｎであり、ｉ＝１，…，ｎであり、ｊ＝１，…，ｍであり、ｕ＝１，…，ｎであり、ηＴがηの転置であり、｜Λ｜がΛの要素数であり、ｒｏｕｎｄ（μ）がμに最も近い整数であり、ｆｌｏｏｒ（μ）がμ以下の最大の整数であり、ｃｅｉｌ（μ）がμ以上の最小の整数であり、ｄｅｔ（η）がηの行列式であり、Ｂ＝｛ｂ１，…，ｂｎ｝が一次独立なｎ個のｎ次元ベクトルｂｉからなる基底であり、前記ｎ次元ベクトルｂｉのそれぞれがｎ個の整数要素からなり、βが前記基底Ｂの前記ｎ次元ベクトルｂ１，…，ｂｎを要素とするｎ行ｎ列の基底行列であり、ｔ＝（ｔ１，…，ｔｎ）Ｔがｎ個の整数要素ｔｉからなる目標ベクトルであり、ｘｉが整数であり、Ｌ（Ｂ）が格子｛Σｉ＝１，…，ｎ  ｘｉｂｉ｜ｘｉ∈Ｚ，ｂｉ∈Ｂ｝であり、τがｎ次元ベクトルであり、τ＋Ｌ（Ｂ）＝Ｌ（Ｂ）＋τ＝｛τ＋χ｜χ∈Ｌ（Ｂ）｝であり、ｒｊｉ（ｃ），ｒｊｉ（ｄ），ｒｊ０，ｅｊ，Ｘｊ，ｄｉが整数であり、ｔ（ｄ）が前記目標ベクトルｔと前記目標ベクトルｔに最も近い最近ベクトルｔ（ｃ）∈Ｌ（Ｂ）との差分ベクトルｔ（ｄ）＝ｔ−ｔ（ｃ）＝（ｔ１（ｄ），…，ｔｎ（ｄ））Ｔであり、ｓが整数要素からなるｎ次元ベクトルであり、ａｊがｎ個の整数要素ａ１ｊ，…，ａｎｊからなるｎ次元ベクトルａｊ＝（ａ１ｊ，…，ａｎｊ）Ｔであり、ｇがｎ個の要素ｇ１，…，ｇｎからなるｎ次元ベクトルｇ＝（ｇ１，…，ｇｎ）Ｔであり、εｕがｕ番目の要素が１で他の要素が０のｎ次元単位ベクトルεｕ＝（０，…，１，０，…，０）Ｔであり、
【数２６】
2019079226.tif 000028
を満たす前記ｎ次元ベクトルａｊ，ｇおよび前記整数Ｎ’の入力に対し、
【数２７】
2019079226.tif 000029
を満たす｛ｒｊｉ（ｃ），ｒｊｉ（ｄ），ｒｊ０｝およびｍ，Ｍ，Ｎを出力する変換装置であって、
｛ａ１，…，ａｍ’，Ｎ’ε１，…，Ｎ’εｎ｝から計算したＬＬＬ既約基底を前記基底Ｂとし、前記基底ＢのＮ’に関する双対基底Ｂ−’＝｛ｂ１−’，…，ｂｎ−’｝についてＮに関する双対基底Ｂ−＝｛（Ｎ／Ｎ’）ｂ１−’，…，（Ｎ／Ｎ’）ｂｎ−’｝を得、ｔ＝ｇとする第１古典計算部と、
ＢＲが［０，Ｎ）ｎに含まれる点の集合であり、ｃｅｉｌ（ｌｏｇ２ Ｍ）個の量子ビットからなるインデックスレジスタと、ｎ×ｃｅｉｌ（ｌｏｇ２ Ｎ）個の量子ビットからなるデータレジスタと、ｎ×ｃｅｉｌ（ｌｏｇ２ ｄｅｔ（β））個の量子ビットからなるワークレジスタとからなるレジスタ列の量子状態を
【数２８】
2019079226.tif 000030
にする量子状態生成部と、
前記インデックスレジスタに対するＭ次元量子フーリエ変換を実行し、前記レジスタ列の量子状態を
【数２９】
2019079226.tif 000031
にする第１量子フーリエ変換部と、
ｘ−ｗｔ＝ｙｗ，ｘ，１ｂ１＋…＋ｙｗ，ｘ，ｎｂｎを満たし、前記第１量子フーリエ変換部で得られた量子状態の前記レジスタ列に対して量子状態｜ｗ＞｜ｘ＞｜０＞を量子状態｜ｗ＞｜ｘ＞｜ｄｅｔ（β）（ｙｗ，ｘ，１−ｆｌｏｏｒ（ｙｗ，ｘ，１）），…，ｄｅｔ（β）（ｙｗ，ｘ，ｎ−ｆｌｏｏｒ（ｙｗ，ｘ，ｎ））＞にする量子操作を実行する操作部と、
前記操作部で得られた量子状態の前記ワークレジスタを観測し、前記インデックスレジスタおよび前記データレジスタの量子状態を
【数３０】
2019079226.tif 000032
にする第１観測部と、
前記第１観測部での観測後の量子状態の前記データレジスタに対するＮ次元量子フーリエ変換を実行する第２量子フーリエ変換部と、
前記第２量子フーリエ変換部で得られた量子状態の前記データレジスタを観測して観測結果（ｒｊ１，…，ｒｊｎ）を得る第２観測部と、
前記第２観測部での観測後の量子状態の前記インデックスレジスタに対するＭ次元逆量子フーリエ変換を実行する逆量子フーリエ変換部と、
前記逆量子フーリエ変換部で得られた量子状態の前記インデックスレジスタを観測して観測結果ｒｊ０を得る第３観測部と、
前記第１古典計算部で得られた前記双対基底Ｂ−、および、前記量子状態生成部と前記第１量子フーリエ変換部と前記操作部と前記第１観測部と前記第２量子フーリエ変換部と前記第２観測部と前記第３観測部の処理をｊ＝１，…，ｍについて行って得られた前記観測結果（ｒｊ１，…，ｒｊｎ）およびｒｊ０を入力とし、格子Ｌ（Ｂ−）＝｛Σｉ＝１，…，ｎ  ｘｉｂ−ｉ｜ｘｉ∈Ｚ，ｂ−ｉ∈Ｂ−｝およびｎ次元ベクトルｒｊ＝（ｒｊ１，…，ｒｊｎ）について、前記ｎ次元ベクトルｒｊに最も近い最近ベクトルｒｊ（ｃ）＝（ｒｊ１（ｃ），…，ｒｊｎ（ｃ））∈Ｌ（Ｂ−）および差分ベクトルｒｊ（ｄ）＝ｒｊ−ｒｊ（ｃ）＝（ｒｊ１（ｄ），…，ｒｊｎ（ｄ））を得る第２古典計算部と、
を有する変換装置。
【請求項３】
ｎ，ｍ，Ｎ，Ｍが正の整数であり、Ｍ＜Ｎであり、ｉ＝１，…，ｎであり、ｊ＝１，…，ｍであり、ηＴがηの転置であり、ｒｏｕｎｄ（μ）がμに最も近い整数であり、ｆｌｏｏｒ（μ）がμ以下の最大の整数であり、ｃｅｉｌ（μ）がμ以上の最小の整数であり、ＡＢＳ（μ）がμの絶対値であり、||η||がηのユークリッドノルムであり、Ｂ＝｛ｂ１，…，ｂｎ｝が一次独立なｎ個のｎ次元ベクトルｂｉからなる基底であり、前記ｎ次元ベクトルｂｉのそれぞれがｎ個の整数要素からなり、ｔ＝（ｔ１，…，ｔｎ）Ｔがｎ個の整数要素ｔｉからなる目標ベクトルであり、ｘｉが整数であり、Ｌ（Ｂ）が格子｛Σｉ＝１，…，ｎ  ｘｉｂｉ｜ｘｉ∈Ｚ，ｂｉ∈Ｂ｝であり、τがｎ次元ベクトルであり、τ＋Ｌ（Ｂ）＝Ｌ（Ｂ）＋τ＝｛τ＋χ｜χ∈Ｌ（Ｂ）｝であり、Ｂ−が｛τ｜＜τ，χ＞＝０ ｍｏｄ Ｎ  ｆｏｒ  ａｌｌ  χ∈Ｌ（Ｂ）｝のＬＬＬ既約基底であるＮに関する双対基底であり、＜τ，χ＞がτとχとの内積であり、Ｌ（Ｂ−）が双対格子Ｌ（Ｂ−）＝｛Σｉ＝１，…，ｎ  ｘｉｂ−ｉ｜ｘｉ∈Ｚ，ｂ−ｉ∈Ｂ−｝であり、ｒｊｉ（ｃ），ｒｊｉ（ｄ），ｒｊ０，ｅｊが整数であり、ｒｊ（ｃ）がｎ次元ベクトルｒｊ（ｃ）＝（ｒｊ１（ｃ），…，ｒｊｎ（ｃ））∈Ｌ（Ｂ−）であり、ｒｊ（ｄ）がｎ次元ベクトルｒｊ（ｄ）＝（ｒｊ１（ｄ），…，ｒｊｎ（ｄ））であり、ｔ（ｄ）が前記目標ベクトルｔと前記目標ベクトルｔに最も近い最近ベクトルｔ（ｃ）∈Ｌ（Ｂ）との差分ベクトルｔ（ｄ）＝ｔ−ｔ（ｃ）＝（ｔ１（ｄ），…，ｔｎ（ｄ））Ｔであり、Ｌ，γが正の実数であり、
【数３１】
2019079226.tif 000033
を満たす前記差分ベクトルｔ（ｄ）が||ｔ（ｄ）||≦Ｌを満たすか||ｔ（ｄ）||＞γＬを満たすかを表す情報を出力する判定装置であって、
ｒｊ＝ｒｊ（ｃ）＋ｒｊ（ｄ）＝ｓｊ＝ｓｊ（ｃ）＋ｓｊ（ｄ）およびｓｊ（ｃ）∈Ｌ（Ｂ−）を満たすｎ次元ベクトルｓｊ（ｄ）を法線ベクトルとする有限個の超平面に含まれる何れかの超平面が前記差分ベクトルｔ（ｄ）に対応しており、前記有限個の超平面に含まれる超平面のうち最も原点に近い超平面と前記原点との距離に基づく評価値Ｅｖａｌｑを得る超平面距離推定部と、
Ｅｖａｌｑ≦Ｌを満たすと判定した場合に||ｔ（ｄ）||≦Ｌを満たす旨の情報を出力し、Ｅｖａｌｑ＞Ｌを満たすと判定した場合に||ｔ（ｄ）||＞γＬを満たす旨の情報を出力する判定部と、
を有する判定装置。
【請求項４】
請求項３の判定装置であって、
αが正の実数であり、νが整数要素からなるｎ次元ベクトルであり、ｓｊ０＝ｒｊ０であり、
前記超平面距離推定部は、
前記ｎ次元ベクトルｓｊについて格子｛ν∈Ｚｎ｜＜ｓｊ，ν＞＝０ ｍｏｄ Ｎ｝の基底Ｂｓｊを得る超平面基底生成部と、
＜ｓｊ（ｄ），ｂｓｊ（ｄ），Ｎ＞＝Ｎを満たすｎ次元ベクトルｂｓｊ（ｄ），Ｎを得るベクトル生成部と、
ｙ０＝ｆｌｏｏｒ（（ｓｊ０−α）Ｎ／Ｍ）＋１およびｙ１＝ｃｅｉｌ（（ｓｊ０＋α）Ｎ／Ｍ）−１について、
（i）＜ｓｊ，ｔｓｊ，ｙ０＞＝ｙ０ ｍｏｄ Ｎおよび＜ｓｊ，ｔｓｊ，ｙ１＞＝ｙ１ｍｏｄ Ｎを満たすｎ次元ベクトルｔｓｊ，ｙ０およびｔｓｊ，ｙ１を得、
（ii）ｔ’ｓｊ，ｙ０∈（ｓｊ＋Ｌ（Ｂ））∩（ｔｓｊ，ｙ０＋Ｌ（Ｂｓｊ））およびｔ’ｓｊ，ｙ１∈（ｓｊ＋Ｌ（Ｂ））∩（ｔｓｊ，ｙ１＋Ｌ（Ｂｓｊ））を満たすｎ次元ベクトルｔ’ｓｊ，ｙ０およびｔ’ｓｊ，ｙ１を得、
（iii）ＡＢＳ（＜ｓｊ（ｄ），ｔ’ｓｊ，ｙ０＋ｋｂｓｊ（ｄ），Ｎ＞）を最小にするｋをｋｙ０とし、ＡＢＳ（＜ｓｊ（ｄ），ｔ’ｓｊ，ｙ１＋ｋｂｓｊ（ｄ），Ｎ＞）を最小にするｋをｋｙ１とし、ｔ”ｓｊ，ｙ０＝ｔ’ｓｊ，ｙ０＋ｋｙ０ｂｓｊ（ｄ），Ｎおよびｔ”ｓｊ，ｙ１＝ｔ’ｓｊ，ｙ１＋ｋｙ１ｂｓｊ（ｄ），Ｎを得、
（iv）＜ｓｊ（ｄ），ｔ”ｓｊ，ｙ０＞≦０≦＜ｓｊ（ｄ），ｔ”ｓｊ，ｙ１＞または＜ｓｊ（ｄ），ｔ”ｓｊ，ｙ１＞≦０≦＜ｓｊ（ｄ），ｔ”ｓｊ，ｙ０＞ならば距離ｄｉｓｔｊ＝０とし、＜ｓｊ（ｄ），ｔ”ｓｊ，ｙ０＞および＜ｓｊ（ｄ），ｔ”ｓｊ，ｙ１＞が共に正または共に負ならばＡＢＳ（＜ｓｊ（ｄ），ｔ”ｓｊ，ｙ０＞）およびＡＢＳ（＜ｓｊ（ｄ），ｔ”ｓｊ，ｙ１＞）のうち小さい方を距離ｄｉｓｔｊ＝ｍｉｎ（ＡＢＳ（＜ｓｊ（ｄ），ｔ”ｓｊ，ｙ０＞），ＡＢＳ（＜ｓｊ（ｄ），ｔ”ｓｊ，ｙ１＞））として得る超平面距離候補設定部と、
設定された確率ｑについて、前記距離ｄｉｓｔ１，…，ｄｉｓｔｍを小さい順に並べた場合にｆｌｏｏｒ（ｑｍ）番目の値を前記評価値Ｅｖａｌｑ∈｛ｄｉｓｔ１，…，ｄｉｓｔｍ｝として得る超平面距離選択部と、を含む判定装置。
【請求項５】
ｎ，ｍ，Ｍ，Ｎ，ρ（ｖ）が正の整数であり、Ｍ＜Ｎであり、ｉ＝１，…，ｎであり、ｊ＝１，…，ｍであり、ｖ＝０，…，ｎ−１であり、ηＴがηの転置であり、ｒｏｕｎｄ（μ）がμに最も近い整数であり、Ｂ＝｛ｂ１，…，ｂｎ｝が一次独立なｎ個のｎ次元ベクトルｂｉからなる基底であり、前記ｎ次元ベクトルｂｉのそれぞれがｎ個の整数要素からなり、ｔ＝（ｔ１，…，ｔｎ）Ｔがｎ個の整数要素ｔｉからなる目標ベクトルであり、ｘｉが整数であり、Ｌ（Ｂ）が格子｛Σｉ＝１，…，ｎ  ｘｉｂｉ｜ｘｉ∈Ｚ，ｂｉ∈Ｂ｝であり、ｒｊｉ（ｃ），ｒｊｉ（ｄ），ｒｊ０，ｅｊが整数であり、ｔ（ｄ）が前記目標ベクトルｔと前記目標ベクトルｔに最も近い最近ベクトルｔ（ｃ）∈Ｌ（Ｂ）との差分ベクトルｔ（ｄ）＝ｔ−ｔ（ｃ）＝（ｔ１（ｄ），…，ｔｎ（ｄ））Ｔであり、Ｂ−が｛τ｜＜τ，χ＞＝０ ｍｏｄ Ｎ  ｆｏｒ  ａｌｌ  χ∈Ｌ（Ｂ）｝のＬＬＬ既約基底であるＮに関する双対基底であり、＜τ，χ＞がτとχとの内積であり、Ｌ（Ｂ−）が双対格子Ｌ（Ｂ−）＝｛Σｉ＝１，…，ｎ  ｘｉｂ−ｉ｜ｘｉ∈Ｚ，ｂ−ｉ∈Ｂ−｝であり、ｒｊ（ｃ）がｎ次元ベクトルｒｊ（ｃ）＝（ｒｊ１（ｃ），…，ｒｊｎ（ｃ））∈Ｌ（Ｂ−）であり、ｒｊ（ｄ）がｎ次元ベクトルｒｊ（ｄ）＝（ｒｊ１（ｄ），…，ｒｊｎ（ｄ））であり、ｔ（ｄ）が前記目標ベクトルｔと前記目標ベクトルｔに最も近い最近ベクトルｔ（ｃ）∈Ｌ（Ｂ）との差分ベクトルｔ（ｄ）＝ｔ−ｔ（ｃ）＝（ｔ１（ｄ），…，ｔｎ（ｄ））Ｔであり、前記差分ベクトルｔ（ｄ）が
【数３２】
2019079226.tif 000034
を満たし、Ｌ，γが正の実数であり、
前記基底Ｂおよび前記目標ベクトルｔとの組（Ｂ，ｔ）に対して前記差分ベクトルｔ（ｄ）を出力する計算装置であって、
前記実数Ｌを初期値Ｌ１に設定する初期設定部と、
基底Ｂ０と目標ベクトルｔ０との組からなるノード（Ｂ０，ｔ０）＝（Ｂ，ｔ）を得る第２初期設定部と、
基底Ｂｖ＋１に対応する格子Ｌ（Ｂｖ＋１）が基底Ｂｖに対応する格子Ｌ（Ｂｖ）の部分格子であり、いずれかのι’∈｛１，…，ρ（ｖ）｝について目標ベクトルｔｖ，ι’と前記目標ベクトルｔｖ，ι’に最も近い最近ベクトルｔｖ，ι’（ｃ）∈Ｌ（Ｂｖ＋１）との差分ベクトルｔｖ，ι’−ｔｖ，ι’（ｃ）が、目標ベクトルｔｖと前記目標ベクトルｔｖに最も近い最近ベクトルｔｖ（ｃ）∈Ｌ（Ｂｖ）との差分ベクトルｔｖ−ｔｖ（ｃ）に等しく、ノード（Ｂｖ，ｔｖ）を用い、ι＝１，…，ρ（ｖ）について、前記基底Ｂｖ＋１と、目標ベクトルｔｖ，ιと、の組であるノード（Ｂｖ＋１，ｔｖ，１），…，（Ｂｖ＋１，ｔｖ，ρ（ｖ））を生成する子ノード生成部と、
ι＝１，…，ρ（ｖ）について、請求項３または４に記載の前記判定装置の処理をＢ＝Ｂｖ＋１かつｔ＝ｔｖ，ιとして実行する判定処理部と、
前記判定処理部がすべてのι＝１，…，ρ（ｖ）についてＥｖａｌｑ＞Ｌを満たすと判定した場合に、前記実数Ｌを増加させて、前記初期設定部、前記子ノード生成部、および前記判定処理部の処理を再び実行させ、前記判定処理部がいずれかのι＝１，…，ρ（ｖ）についてＥｖａｌｑ≦Ｌを満たすと判定した場合に、最小のＥｖａｌｑに対応するノード（Ｂｖ＋１，ｔｖ，ι’）（ただし、ι’∈｛１，…，ρ（ｖ）｝）をノード（Ｂｖ＋１，ｔｖ＋１）に設定するノード選択部と、
ｖ＝０からｖ＝ｎ−１まで各ｖ＝０，…，ｎ−１について前記子ノード生成部と前記判定処理部と前記ノード選択部の処理を実行して得られたノード（Ｂｎ，ｔｎ）の目標ベクトルｔｎを差分ベクトルｔＬ１（ｄ）として得る差分ベクトル生成部と、
何れかの前記初期値Ｌ１に対応する前記差分ベクトルｔＬ１（ｄ）を前記差分ベクトルｔ（ｄ）として出力する出力部と、
を有する計算装置。
【請求項６】
ｎ，ｍ，ｍ’，Ｍ，Ｎ，Ｎ’が正の整数であり、Ｍ＜Ｎであり、ｉ＝１，…，ｎであり、ｊ＝１，…，ｍであり、ｖ＝０，…，ｎ−１であり、ηＴがηの転置であり、ｒｏｕｎｄ（μ）がμに最も近い整数であり、Ｂ＝｛ｂ１，…，ｂｎ｝が一次独立なｎ個のｎ次元ベクトルｂｉからなる基底であり、前記ｎ次元ベクトルｂｉのそれぞれがｎ個の整数要素からなり、ｔ＝（ｔ１，…，ｔｎ）Ｔがｎ個の整数要素ｔｉからなる目標ベクトルであり、ｘｉが整数であり、Ｌ（Ｂ）が格子｛Σｉ＝１，…，ｎ  ｘｉｂｉ｜ｘｉ∈Ｚ，ｂｉ∈Ｂ｝であり、ｒｊｉ（ｃ），ｒｊｉ（ｄ），ｒｊ０，Ｘｊ，ｄｉ，ｇｉが整数であり、ｔ（ｄ）が前記目標ベクトルｔと前記目標ベクトルｔに最も近い最近ベクトルｔ（ｃ）∈Ｌ（Ｂ）との差分ベクトルｔ（ｄ）＝ｔ−ｔ（ｃ）＝（ｔ１（ｄ），…，ｔｎ（ｄ））Ｔであり、Ｂ−が｛τ｜＜τ，χ＞＝０ ｍｏｄ Ｎ  ｆｏｒ  ａｌｌ  χ∈Ｌ（Ｂ）｝のＬＬＬ既約基底であるＮに関する双対基底であり、＜τ，χ＞がτとχとの内積であり、Ｌ（Ｂ−）が双対格子Ｌ（Ｂ−）＝｛Σｉ＝１，…，ｎ  ｘｉｂ−ｉ｜ｘｉ∈Ｚ，ｂ−ｉ∈Ｂ−｝であり、ｒｊ（ｃ）がｎ次元ベクトルｒｊ（ｃ）＝（ｒｊ１（ｃ），…，ｒｊｎ（ｃ））∈Ｌ（Ｂ−）であり、ｒｊ（ｄ）がｎ次元ベクトルｒｊ（ｄ）＝（ｒｊ１（ｄ），…，ｒｊｎ（ｄ））であり、ｔ（ｄ）が前記目標ベクトルｔと前記目標ベクトルｔに最も近い最近ベクトルｔ（ｃ）∈Ｌ（Ｂ）との差分ベクトルｔ（ｄ）＝ｔ−ｔ（ｃ）＝（ｔ１（ｄ），…，ｔｎ（ｄ））Ｔであり、ａｊがｎ個の整数要素ａ１ｊ，…，ａｎｊからなるｎ次元ベクトルａｊ＝（ａ１ｊ，…，ａｎｊ）Ｔであり、ｇがｎ個の要素ｇ１，…，ｇｎからなるｎ次元ベクトルｇ＝（ｇ１，…，ｇｎ）Ｔであり、εｕがｕ番目の要素が１で他の要素が０のｎ次元単位ベクトルεｕ＝（０，…，１，０，…，０）Ｔであり、Ｌ，γが正の実数であり、前記ｎ次元ベクトルａｊ，ｇおよび前記整数Ｎ’の入力に対して
【数３３】
2019079226.tif 000035
を満たす（ｄ１，…，ｄｎ）Ｔを前記差分ベクトルｔ（ｄ）として出力する計算装置であって、
前記実数Ｌを初期値Ｌ１に設定する初期設定部と、
｛ａ１，…，ａｍ’，Ｎ’ε１，…，Ｎ’εｎ｝から計算したＬＬＬ既約基底を前記基底Ｂとし、ｔ＝ｇとし、基底Ｂ０と目標ベクトルｔ０との組からなるノード（Ｂ０，ｔ０）＝（Ｂ，ｔ）を得る第２初期設定部と、
基底Ｂｖ＋１に対応する格子Ｌ（Ｂｖ＋１）が基底Ｂｖに対応する格子Ｌ（Ｂｖ）の部分格子であり、いずれかのι’∈｛１，…，ρ（ｖ）｝について目標ベクトルｔｖ，ι’と前記目標ベクトルｔｖ，ι’に最も近い最近ベクトルｔｖ，ι’（ｃ）∈Ｌ（Ｂｖ＋１）との差分ベクトルｔｖ，ι’−ｔｖ，ι’（ｃ）が、目標ベクトルｔｖと前記目標ベクトルｔｖに最も近い最近ベクトルｔｖ（ｃ）∈Ｌ（Ｂｖ）との差分ベクトルｔｖ−ｔｖ（ｃ）に等しく、ノード（Ｂｖ，ｔｖ）を用い、ι＝１，…，ρ（ｖ）について、前記基底Ｂｖ＋１と、目標ベクトルｔｖ，ιと、の組であるノード（Ｂｖ＋１，ｔｖ，１），…，（Ｂｖ＋１，ｔｖ，ρ（ｖ））を生成する子ノード生成部と、
ι＝１，…，ρ（ｖ）について、請求項３または４に記載の前記判定装置の処理をＢ＝Ｂｖ＋１かつｔ＝ｔｖ，ιとして実行する判定処理部と、
前記判定処理部がすべてのι＝１，…，ρ（ｖ）についてＥｖａｌｑ＞Ｌを満たすと判定した場合に、前記実数Ｌを増加させて、前記初期設定部、前記子ノード生成部、および前記判定処理部の処理を再び実行させ、前記判定処理部がいずれかのι＝１，…，ρ（ｖ）についてＥｖａｌｑ≦Ｌを満たすと判定した場合に、最小のＥｖａｌｑに対応するノード（Ｂｖ＋１，ｔｖ，ι’）（ただし、ι’∈｛１，…，ρ（ｖ）｝）をノード（Ｂｖ＋１，ｔｖ＋１）に設定するノード選択部と、
ｖ＝０からｖ＝ｎ−１まで各ｖ＝０，…，ｎ−１について前記子ノード生成部と前記判定処理部と前記ノード選択部の処理を実行して得られたノード（Ｂｎ，ｔｎ）の目標ベクトルｔｎを差分ベクトルｔＬ１（ｄ）として得る差分ベクトル生成部と、
何れかの前記初期値Ｌ１に対応する前記差分ベクトルｔＬ１（ｄ）を前記差分ベクトルｔ（ｄ）として出力する出力部と、
を有する計算装置。
【請求項７】
ｎが正の整数であり、Ｂ＝｛ｂ１，…，ｂｎ｝が一次独立なｎ個のｎ次元ベクトルｂｉからなる基底であり、前記ｎ次元ベクトルｂｉのそれぞれがｎ個の整数要素からなり、Ｌ（Ｂ）が格子｛Σｉ＝１，…，ｎ  ｘｉｂｉ｜ｘｉ∈Ｚ，ｂｉ∈Ｂ｝であり、
前記基底Ｂを入力として、前記格子Ｌ（Ｂ）の中で最も原点に近い格子点への最短ベクトルを出力する計算装置であって、
すべてのｉ＝１，…，ｎについて、Ｂｉ＝｛ｂ１，…，ｂｉ−１，２ｂｉ，ｂｉ＋１，…，ｂｎ｝に設定する基底生成部と、
請求項５に記載の前記計算装置の処理をＢ＝Ｂｉかつｔ＝ｂｉとして実行して得られた前記差分ベクトルｔ（ｄ）をｔｉ（ｄ）に設定する設定部と、
前記設定部で得られたｔ１（ｄ），…，ｔｎ（ｄ）の中で最短ものを前記最短ベクトルとして出力する選択部と、
を有する計算装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は量子計算技術に関する。
【背景技術】
【０００２】
1994年、Shorは因数分解と離散対数問題を効率的に解く量子アルゴリズムを発見し、RSA暗号やElGamal暗号など、因数分解や離散対数問題の難しさを安全性の根拠とする公開鍵暗号にとって、量子コンピュータが深刻な脅威となることを明らかにした。この発見がきっかけとなり、現在、耐量子暗号（ポスト量子暗号とも呼ばれる）の研究が盛んに行われている。これらの公開鍵暗号は、格子問題、多変数多項式問題、符号問題など、量子コンピュータにとって困難と思われている問題をベースに設計されている。中でも、最短ベクトル問題（SVP）、最近ベクトル問題（CVP）、Learning with Errors（LWE）、Short Integer Solution（SIS）など、格子問題の難しさを安全性の根拠とする公開鍵暗号は、格子暗号と呼ばれ、耐量子暗号研究において最も有望視されている暗号群である。その理由は、格子暗号の一部について量子コンピュータに対する条件付き安全性証明が知られていることに加えて、完全準同型暗号が構成できることによる。ここで、完全準同型暗号とは、暗号化したまま無制限に情報処理を行うことができる暗号のことである。完全準同型暗号は、クラウドからの情報漏えいに対抗する有力手段と考えられており、クラウドの一般化に伴い、近年、その重要性が急速に高まっている。
【０００３】
一方、量子アルゴリズムの研究分野では、Shorのアルゴリズムを拡張する研究が行われてきた。Shorのアルゴリズムの自然な拡張は、隠れ部分群問題に応用できる。隠れ部分群問題は、群を替えるとさまざまな問題と関係することが知られている。例えば、対称群に対する隠れ部分群問題が解ければ、グラフ同型性判定問題も解ける。また、二面体群に対する隠れ部分群問題は格子問題と密接に関係している。こうしたことから、Shorのアルゴリズムを拡張し、新しい量子アルゴリズムを開発する努力が続けられてきた。この背景には、近年の人工知能ブームも関係している。Shorのアルゴリズムは周期発見問題に応用できるが、人工知能で問題となっている組み合わせ最適化問題には適用できない。一方、Shorのアルゴリズム発見以降に提案されたGroverのアルゴリズムや量子ウォークアルゴリズムなどは、組み合わせ最適化問題に適用できるが、問題を効率的に解くことができない。そこで、組み合わせ最適化問題を効率的に解く量子アルゴリズムの開発が待ち望まれてきた。
【０００４】
組み合わせ最適化問題のうち最短ベクトル問題などに代表される格子問題は、人工知能の他、次世代暗号に利用されるため、その解法が詳しく研究されている。以下、古典、量子についてそれぞれ記す。
【０００５】
格子問題を解くために用いられる最も一般的な古典アルゴリズムは格子簡約化アルゴリズムである。格子簡約化アルゴリズムとは、与えられたベクトル空間の基底から、全ての基底が互いに直行に近くなるような新しい基底を計算する。そのために、全ての基底ベクトルの組み合わせに対して、グラム−シュミットの直交化法に近い操作を繰り返し施す。格子簡約化アルゴリズムの結果得られる最も短いベクトルの長さは、最悪の場合、求めたい最短ベクトルの長さに対して指数的に大きくなる。
【０００６】
格子問題を解く量子アルゴリズムとして、例えば、非特許文献１，２の方法が提案されている。非特許文献１では、最近ベクトル問題をもとに、Dihedral Coset Stateと呼ばれる量子状態を作り、量子フーリエ変換を利用して解を得る。非特許文献２では、確率振幅増幅を用いて解を探索する。しかし、格子問題を効率的に解く量子アルゴリズムは見つかっていない。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Oded Regev, Quantum Computation and Lattice Problems, SIAM Journal on Computing, Vol 33, No. 3, pp. 738-760, (2004).
【非特許文献２】T. Laarhoven and M. Mosca and J. van de Pol, Finding shortest lattice vectors faster using quantum search, Designs, Codes and Cryptography, Vol 7. No 2, pp. 375-400(2015).
【発明の概要】
【発明が解決しようとする課題】
【０００８】
本発明は格子問題を効率的に解くことを目的とする。
【課題を解決するための手段】
【０００９】
基底Ｂおよび目標ベクトルｔの入力、または、
【数１】
2019079226.tif 000003
を満たすｎ次元ベクトルａｊ＝（ａ１ｊ，…，ａｎｊ）Ｔ，ｔ＝ｇ＝（ｇ１，…，ｇｎ）Ｔおよび整数Ｎ’の入力に対し、
【数２】
2019079226.tif 000004
を満たす｛ｒｊｉ（ｃ），ｒｊｉ（ｄ），ｒｊ０｝およびｍ，Ｍ，Ｎを得て出力する。まず、古典計算によって基底Ｂについての双対基底Ｂ−を得る。次に、複数の整数について格子Ｌ（Ｂ）をｔの整数倍分平行移動させて得られる集合の和集合に含まれる点列の周期性を利用した量子計算を行い、ｊ＝１，…，ｍについて、ｎ次元ベクトルｒｊ＝（ｒｊ１，…，ｒｊｎ）およびｒｊ０を得る。その後、古典計算によってｎ次元ベクトルｒｊに最も近い最近ベクトルｒｊ（ｃ）＝（ｒｊ１（ｃ），…，ｒｊｎ（ｃ））∈Ｌ（Ｂ−）およびｒｊ（ｃ）に対応する差分ベクトルｒｊ（ｄ）＝ｒｊ−ｒｊ（ｃ）＝（ｒｊ１（ｄ），…，ｒｊｎ（ｄ））を得る。
【発明の効果】
【００１０】
このように、基底Ｂおよび目標ベクトルｔについての最近ベクトル問題（CVP）や式（１）のLearning with Errors（LWE）を式（２）の問題に効率的に変形できる。式（２）の問題の解（差分ベクトルｔ（ｄ））は古典計算によって得ることができる。そのため、本発明では格子問題を効率的に解くことができる。
【図面の簡単な説明】
【００１１】
【図１】図１は実施形態の原理を説明するための概念図である。
【図２】図２は各実施形態の対応関係を表す概念図である。
【図３】図３は各実施形態の対応関係を表す概念図である。
【図４】図４は実施形態の変換装置の機能構成を例示したブロック図である。
【図５】図５は図４の量子計算部の機能構成を例示したブロック図である。
【図６】図６は図５の量子計算部の量子回路を例示した図である。
【図７】図７は量子計算を説明するための概念図である。
【図８】図８は実施形態の判定装置の機能構成を例示したブロック図である。
【図９】図９は図８の超平面距離推定部３３の機能構成を例示したブロック図である。
【図１０】図１０は解と超平面との関係を例示した概念図である。
【図１１】図１１Ａおよび図１１Ｂは解と超平面との関係を例示した概念図である。
【図１２】図１２はＥｖａｌｑと解との関係を例示した実験結果である。
【図１３】図１３は実施形態の計算装置の機能構成を例示したブロック図である。
【図１４】図１４Ａおよび図１４Ｂは子ノード生成を説明するための概念図である。
【図１５】図１５は実施形態の計算方法を説明するための概念図である。
【図１６】図１６は実施形態の計算装置の機能構成を例示したブロック図である。
【発明を実施するための形態】
【００１２】
以下、図面を参照して本発明の実施形態を説明する。
［定義］
実施形態で用いる用語を定義する。
ｎ，ｍ，ｍ’，Ｍ，Ｎ，Ｎ’は正の整数である。ｉ＝１，…，ｎであり、ｊ＝１，…，ｍであり、ｕ＝１，…，ｎである。ｓは整数要素からなるｎ次元ベクトルである。ｒｊｉ（ｃ），ｒｊｉ（ｄ），ｒｊ０，Ｘｊ，ｄｉ，ｇｉ，ｅｊは整数である。Ｌ，γが正の実数である。ａｊはｎ個の整数要素ａ１ｊ，…，ａｎｊからなるｎ次元ベクトルａｊ＝（ａ１ｊ，…，ａｎｊ）Ｔである。ｇはｎ個の要素ｇ１，…，ｇｎからなるｎ次元ベクトルｇ＝（ｇ１，…，ｇｎ）Ｔである。εｕはｕ番目の要素が１で他の要素が０のｎ次元単位ベクトルεｕ＝（０，…，１，０，…，０）Ｔである。
【００１３】
ηＴはηの転置を表す。ηはベクトルまたは行列である。｜Λ｜は集合Λの要素数を表す。ＡＢＳ（μ）はμの絶対値を表す。||η||はηのユークリッドノルムを表す。すなわち、||η||はηの長さを表す。ｒｏｕｎｄ（μ）はμに最も近い整数である。すなわち、ｒｏｕｎｄは丸め関数を表す。ｆｌｏｏｒ（μ）はμ以下の最大の整数である。すなわち、ｆｌｏｏｒは床関数を表す。ｃｅｉｌ（μ）はμ以上の最小の整数である。すなわち、ｃｅｉｌは天井関数を表す。λ∈Λはλが集合Λの要素であることを意味する。＜τ，χ＞はベクトルτとベクトルχとの内積を表す。ｄｅｔ（η）はηの行列式を表す。｜δ〉はδに対応する量子状態を示す縦ベクトルを表す。|δ1>|δ2>は|δ1>と|δ2>とのテンソル積を表す。
【００１４】
Ｂ＝｛ｂ１，…，ｂｎ｝は一次独立なｎ個のｎ次元ベクトルｂｉからなる基底である。ｎ次元ベクトルｂｉ＝（ｂｉ１，…，ｂｉｎ）∈Ｚｎのそれぞれはｎ個の整数要素ｂｉ１，…，ｂｉｎ∈Ｚからなる。Ｚは整数を表す。βは基底Ｂのｎ次元ベクトルｂ１，…，ｂｎを要素とするｎ行ｎ列の基底行列である。例えば、βはｎ次元ベクトルｂｉをｉ行目の成分とする以下の行列である。
【数３】
2019079226.tif 000005
【００１５】
ｔ＝（ｔ１，…，ｔｎ）Ｔはｎ個の整数要素ｔｉ∈Ｚからなる目標ベクトルである。
【００１６】
Ｌ（Ｂ）は格子｛Σｉ＝１，…，ｎ  ｘｉｂｉ｜ｘｉ∈Ｚ，ｂｉ∈Ｂ｝である。ただし、ｘｉは整数である。すなわち、
【数４】
2019079226.tif 000006
である。
【００１７】
ｎ次元ベクトルｔおよび格子Ｌ（Ｂ）についてτ＋Ｌ（Ｂ）は、格子Ｌ（Ｂ）のすべての格子点をｎ次元ベクトルτ分平行移動させて得られる集合を表す。すなわち、τ＋Ｌ（Ｂ）＝｛τ＋χ｜χ∈Ｌ（Ｂ）｝である。またτ＋Ｌ（Ｂ）＝Ｌ（Ｂ）＋τである。
【００１８】
基底Ｂの部分集合Ｂ’が作る超平面をＨ（Ｂ’）と表記する。超平面Ｈ（Ｂ’）は、部分集合Ｂ’の要素であるベクトルｂｉ’∈Ｂ’によって張られるベクトル空間｛Σｉ＝１，…，ｎ  ζｉｂｉ’｜ζｉ∈Ｒｅ，ｂｉ’∈Ｂ’｝を意味する。ただし、ζｉは実数である。すなわち、
【数５】
2019079226.tif 000007
である。Ｒｅは実数を表す。
【００１９】
ｔはｎ個の整数要素ｔ１，…，ｔｎからなるｎ次元ベクトルｔ＝（ｔ１，…，ｔｎ）Ｔである。原点から格子点（格子Ｌ（Ｂ）上の点）へ向かうベクトルを格子点ベクトルと呼ぶことにする。
【００２０】
＜格子問題＞
実施形態で扱う格子問題を簡単に説明する。より詳しい内容については参考文献１，２参照。
［参考文献１］Daniele Micciancio and Shafi Goldwasser, Complexity of Lattice Problems: a cryptographic perspective, Kluwer Academic Publishers, The Kluwer International Series in Engineering and Computer Science, vol. 671 (2002).
［参考文献２］Cohen, Henri, A Course in Computational Algebraic Number Theory, Springer-Verlag New York, Inc., ISBN 0-387-55640-0 (1993).
【００２１】
≪最短ベクトル問題（ＳＶＰ）≫
最短ベクトル問題とは、基底Ｂが与えられたとき、格子Ｌ（Ｂ）の中で最も原点に近い格子点（原点から最も当該原点に近い格子点へ向かうベクトル、すなわち最短ベクトル）を求める問題である。最短ベクトルの長さと、格子Ｌ（Ｂ）の中で二番目に原点に近いベクトルの長さとの比がγ以上のとき、最短ベクトル問題はγ−ｕｎｉｑｕｅ  ＳＶＰと呼ばれる。最短ベクトル問題はＮＰ困難であり、γを変えることにより、問題の難しさを調整することができる。最短ベクトル問題は、次に示す最近ベクトル問題に帰着できることが知られている。したがって、最近ベクトル問題は、最短ベクトル問題以上に難しい。
【００２２】
≪最近ベクトル問題（ＣＶＰ）≫
最近ベクトル問題とは、基底Ｂと目標ベクトルｔとの組（Ｂ，ｔ）が与えられたとき、目標ベクトルｔとの差分ベクトルが最短となるような格子Ｌ（Ｂ）の最近ベクトルｔ（ｃ）∈Ｌ（Ｂ）を求める問題である。組（Ｂ，ｔ）についての最近ベクトル問題をＣＶＰ（Ｂ，ｔ）と表記する。最近ベクトルｔ（ｃ）∈Ｌ（Ｂ）は目標ベクトルｔに最も近い格子点ベクトルである。ｔ（ｄ）は目標ベクトルｔと最近ベクトルｔ（ｃ）∈Ｌ（Ｂ）との差分ベクトルｔ（ｄ）＝ｔ−ｔ（ｃ）＝（ｔ１（ｄ），…，ｔｎ（ｄ））Ｔを表す。このような差分ベクトルｔ（ｄ）を最短差分ベクトルと呼ぶ。最短差分ベクトルｔ（ｄ）＝ｔ−ｔ（ｃ）と、目標ベクトルｔと目標ベクトルｔに２番目に近い格子点ベクトルとの差分ベクトルと、の長さの比がγ以上のとき、最近ベクトル問題をγ−ｇａｐ  ＣＶＰと呼ぶ。最近ベクトル問題を近似的に解く古典アルゴリズムとして，Babaiが提案したRounding-Off アルゴリズムやNearest Planeアルゴリズムが知られている。
［参考文献３］L. Babai, On Lovasz Lattice Reduction and the Nearest Lattice Point Problem, Combinatorica, Vol. 6, No. 1, pp.1-13, (1986).
しかし、これらのアルゴリズムによって得られる解の近似率は、それぞれ１＋２ｎ（９／２）ｎ／２，２ｎ／２であり、両者とも次元の指数的な近似率しか保証しない。
【００２３】
最近ベクトル問題よりも基本的な問題として、次のＧａｐＣＶＰγが知られている。最近ベクトル問題が探索問題なのに対して、ＧａｐＣＶＰγは決定問題（Ｙｅｓ／Ｎｏを答える問題）である。
【００２４】
≪ＧａｐＣＶＰγ≫
ＧａｐＣＶＰγとは、基底Ｂと目標ベクトルｔとの組（Ｂ，ｔ）と長さＬが与えられたとき、ｄｉｓｔ（Ｂ，ｔ）≦Ｌかｄｉｓｔ（Ｂ，ｔ）＞γＬのどちらかが必ず正しいという約束の下、ｄｉｓｔ（Ｂ，ｔ）≦Ｌ（Yes instance）か、ｄｉｓｔ（Ｂ，ｔ）＞γＬ（No instance）かを判定する決定問題である。ここで、ｄｉｓｔ（Ｂ，ｔ）とは、最短差分ベクトルｔ（ｄ）の長さ（すなわち||ｔ（ｄ）||）のことである。γが小さくなるほどＧａｐＣＶＰγは難しくなる。
【数６】
2019079226.tif 000008
以下なら、ＧａｐＣＶＰγはＮＰ困難であることが知られている。
［参考文献４］Dinur, I. and Kindler, G. and Safra, S., Approximating-CVP to Within Almost-Polynomial Factors is NP-Hard, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, FOCS '98, IEEE Computer Society, Washington, DC, USA, pp.99-111 (1998).
逆にγ≧√ｎの場合、ＧａｐＣＶＰγはＮＰ困難でないと予想されている。
［参考文献５］岡本龍明，“応用数理の散歩道(79) これからの暗号”， 応用数理， Vol. 24, No. 3, pp. 36-39, December, (2014).
【００２５】
ＳＶＰ，ＣＶＰ，ＧａｐＣＶＰγは古くから研究されている格子問題であるのに対して、次のＬＷＥは比較的最近提案された問題である。ＬＷＥは、有望な次世代暗号で用いられるため、上記の問題と並んで詳しく研究されている。
［参考文献６］Oded Regev, On Lattices, Learning with Errors, Random Linear Codes, and Cryptography, J. ACM,, Vol 56, No. 6, 34：1‐34:40 (2009).
【００２６】
≪ＬＷＥ（Learning with Errors）≫
ＬＷＥとは、正の整数ｍ，ｎ，Ｎ、整数要素のｎ×ｍランダム行列Ａ＝（ａｉｊ）（ｉ＝１，…，ｎ、ｊ＝１，…，ｍ）、ｍ次元ランダムベクトルＸ＝（Ｘ１，…，Ｘｍ）Ｔ、および各要素がガウス分布に従う短いベクトルｄ＝（ｄ１，…，ｄｎ）Ｔから
【数７】
2019079226.tif 000009
によりｇ＝（ｇ１，…，ｇｎ）Ｔを定めたとき、（Ａ，ｇ，Ｎ）からＸを求める問題である。ただし、Ｘｊは整数である。ｄが分かれば（３）からＸも計算できるため、ｄを求めてもよい。
【００２７】
一般に、｛ｘ∈Ｚｎ｜＜ｘ，ｂ＞∈Ｚ  ｆｏｒ  ａｌｌ  ｂ∈Ｌ（Ｂ）｝は、格子Ｌ（Ｂ）の「双対格子」と呼ばれる。
［参考文献７］Daniele Micciancio and Shafi Goldwasser, Complexity of Lattice Problems: a cryptographic perspective, Kluwer Academic Publishers, The Kluwer International Series in Engineering and Computer Science, vol. 671 (2002).
【００２８】
各実施形態で導入する「Ｎに関する双対格子」は、この一般的な「双対格子」とは異なる。Ｎに関する双対格子を導入するのは、格子の重ね合せ状態の全座標軸に対してＮ次元の量子フーリエ変換を実行した結果が、Ｎに関する双対格子の重ね合わせになることによる。Ｎに関する双対格子のＬＬＬ既約基底を「Ｎに関する双対基底」と呼ぶことにする。ここで、ＬＬＬ既約基底の定義については、参考文献１の３３−３５ページを参照のこと。任意の基底にＬＬＬアルゴリズムを適用すると、ＬＬＬ規約基底の定義を満たす基底が得られることが知られている（参考文献１、２．２章）。従って、Ｎに関する双対格子の基底に、ＬＬＬアルゴリズムを適用することにより、Ｎに関する既約基底が得られる。Ｎに関する双対基底はエルミート標準形を用いて効率的に計算できる。
【００２９】
≪Ｎに関する双対格子≫
基底Ｂと整数Ｎに対して｛τ∈Ｚｎ｜＜τ，χ＞＝０ ｍｏｄ Ｎ  ｆｏｒ  ａｌｌ  χ∈Ｌ（Ｂ）｝で定義される格子を「Ｎに関する双対格子」と呼ぶ。Ｎに関する格子Ｌ（Ｂ）の双対格子のＬＬＬ既約基底をＢ−と書き、双対基底と呼ぶ。なお、「Ｂ−」の右上添え字の「−」は本来「Ｂ」の真上に記載すべきであるが記載表記の制約上「Ｂ」の右上に表記する場合がある。
【００３０】
各実施形態では、Ｎに関する双対基底の概念を用いて「変形ＬＷＥ」の概念を導入する。後述のように、量子コンピュータを用いて、ＣＶＰやＬＷＥから変形ＬＷＥを効率的に求めることができ、古典コンピュータを用いて、変形ＬＷＥの解の長さがＬ以下かγＬよりも大きいかを効率的に判定することができる。
【００３１】
≪変形ＬＷＥ≫
変形ＬＷＥとは、正の整数ｍ，ｎ，Ｎ、ｍ×ｎ行列
【数８】
2019079226.tif 000010
（ただし、すべてのｊ＝１，…，ｍに対して（ａｊ１（ｃ），…ａｊｎ（ｃ））∈Ｌ（Ｂ−）、かつ、（ａｊ１（ｄ），…ａｊｎ（ｄ））は短いベクトル）を満たす整数要素のｍ×ｎ行列Ａ＝（ａｊｉ）（ｊ＝１，…，ｍ、ｉ＝１，…，ｎ）、ｎ次元ベクトルＸ＝（Ｘ１，…，Ｘｎ）Ｔ、および各要素がガウス分布に従う短いベクトルｄ＝（ｄ１，…，ｄｍ）Ｔから
【数９】
2019079226.tif 000011
によりｇ＝（ｇ１，…，ｇｍ）Ｔを定めたとき、（Ａ，ｇ，Ｎ）からＸを求める問題である。ｄが分かれば（４）からＸも計算できるため、ｄを求めてもよい。
【００３２】
拡張ユークリッド互除法やスミス標準形やエルミート標準形の詳細は例えば以下の文献に記載されている。
［参考文献８］Cohen, Henri, A Course in Computational Algebraic Number Theory, Springer-Verlag New York, Inc., ISBN 0-387-55640-0 (1993).
［参考文献９］Ravindran Kannan and Achim Bachem, Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix, SIAM Journal on Computing, vol. 8, No. 4, pp. 499-507, (1979).
［参考文献１０］Storjohann, Arne, Near Optimal Algorithms for Computing Smith Normal Forms of Integer Matrices, Proceedings of the 1996 International Symposium on Symbolic and Algebraic Computation, ISSAC '96, pp. 267-274 (1996).
【００３３】
［第１実施形態］
第１実施形態では、量子計算と古典計算とによってＣＶＰを変形ＬＷＥに変換する（図２）。
【００３４】
基本となるアイデアについて説明する。一般に、格子問題が量子コンピュータにとって困難な問題であると考えられているのは、格子問題には解に関する周期性がないとされているからである。しかし、格子は各格子点に関して対称な構造をしており、解に関する周期性を作ることは可能である。本実施形態では、この解の周期性を利用した量子計算を行う。
【００３５】
具体的には、以下のような方法をとる。基本となるのはＣＶＰに対する解法である。組（Ｂ，ｔ）についてのＣＶＰの解を差分ベクトルｔ（ｄ）とする。図１に例示するように、Ｌ（Ｂ），ｔ＋Ｌ（Ｂ），２ｔ＋Ｌ（Ｂ），３ｔ＋Ｌ（Ｂ），…の和集合Ｌ（Ｂ）∪（ｔ＋Ｌ（Ｂ））∪（２ｔ＋Ｌ（Ｂ））∪（３ｔ＋Ｌ（Ｂ））∪…は、点列がｔ（ｄ）の間隔で並んだ集合となる。図１では、図の見やすさを考慮し、１個の格子点に基づく点列のみを例示しているが、実際にはすべての格子点に基づく点列がｔ（ｄ）の間隔で並ぶ。本形態の量子計算では、この等間隔に並んだ点列の情報を量子フーリエ変換を利用して取り出す。その後、取り出した情報に関するＣＶＰを古典計算によって解き、変形ＬＷＥを得る。
【００３６】
＜構成＞
図４に例示するように、本形態の変換装置１は、古典計算部１１，１３（第１，２古典計算部）、量子計算部１２、および制御部１４を有する。変換装置１は、制御部１４の制御のもとで各処理を実行する。古典計算部１１，１３は複数の演算部を有する（図示せず）。図５および図６に例示するように、量子計算部１２は、インデックスレジスタ１２１ａ、データレジスタ１２１ｂ、ワークレジスタ１２１ｃ、量子状態生成部１２２、量子フーリエ変換部１２３ａ，１２３ｂ（第１，２量子フーリエ変換部）、操作部１２４、観測部１２５ａ〜１２５ｃ、および逆量子フーリエ変換部１２６を有する。
【００３７】
＜処理＞
本形態の処理を説明する。本形態の変換装置１は、ＣＶＰ（Ｂ，ｔ）についての基底Ｂおよび目標ベクトルｔを入力とし、変形ＬＷＥを表す
【数１０】
2019079226.tif 000012
を満たす｛ｒｊｉ（ｃ），ｒｊｉ（ｄ），ｒｊ０｝およびｍ，Ｍ，Ｎを出力する。本形態の処理は古典計算部１１による古典計算（前処理）、量子計算部１２による量子計算、および古典計算部１３による古典計算（後処理）からなる。
【００３８】
≪古典計算部１１による古典計算（前処理）≫
古典計算部１１（図４）は、組（Ｂ，ｔ）を入力とし、以下の処理を実行する。
１．古典計算部１１の演算部は、基底Ｂに対応する基底行列βの逆行列β−１の要素の分母の最小公倍数Ｎ’を計算して出力する（ステップＳ１１１）。
２．古典計算部１１の演算部は、基底ＢのＮ’に関する双対基底Ｂ−’＝｛ｂ１−’，…，ｂｎ−’｝を計算して出力する（ステップＳ１１２）。
３．古典計算部１１の演算部は、Ｎ’の倍数Ｎを選択して出力する（ステップＳ１１３）。
４．古典計算部１１の演算部は、双対基底Ｂ−’についてＮに関する双対基底Ｂ−＝（Ｎ／Ｎ’）Ｂ−’＝｛（Ｎ／Ｎ’）ｂ１−’，…，（Ｎ／Ｎ’）ｂｎ−’｝を得て出力する。双対基底Ｂ−は基底Ｂの「Ｎに関する双対基底」となる（ステップＳ１１４）。
５．古典計算部１１の演算部は、正の整数Ｍを選択して出力する。Ｍ＜Ｎであり、ＭはＮに対して十分に小さい（ステップＳ１１５）。
６．古典計算部１１の演算部は、２Ｒ≦Ｎ＜４Ｒを満たす実数Ｒを選択して出力する（ステップＳ１１６）。
７．古典計算部１１の演算部は、正の実数Ｌを選択して出力する。Ｌは最短差分ベクトルｔ（ｄ）の長さ||ｔ（ｄ）||の推定値である。例えば、Ｌ×Ｍ＜Ｎを満たす（ステップＳ１１７）。
８．古典計算部１１の演算部は、正の整数ｍを選択して出力する（ステップＳ１１８）。
９．古典計算部１１は、（Ｌ，ｎ，Ｍ，Ｎ，Ｒ，Ｂ，ｔ）を出力する（ステップＳ１１９）。
【００３９】
≪量子計算部１２による量子計算≫
量子計算部１２（図４から図６）は、（Ｌ，ｎ，Ｍ，Ｎ，Ｒ，Ｂ，ｔ）を入力とし、ｃｅｉｌ（ｌｏｇ２ Ｍ）個の量子ビットからなるインデックスレジスタ１２１ａと、ｎ×ｃｅｉｌ（ｌｏｇ２ Ｎ）個の量子ビットからなるデータレジスタ１２１ｂと、ｎ×ｃｅｉｌ（ｌｏｇ２ ｄｅｔ（β））個の量子ビットからなるワークレジスタ１２１ｃとからなるレジスタ列を設定し、これらに対して以下の量子計算をｍ回実行する。量子計算部１２は、ｊ回目の量子計算でｎ次元ベクトルｒｊ＝（ｒｊ１，…，ｒｊｎ）∈［０，Ｎ）ｎおよびｒｊ０∈［０，Ｍ）を得て出力する。ただし、ｉ＝１，…，ｎ，ｊ＝１，…，ｍである。以下にｊ回目の量子計算を説明する。
【００４０】
１．量子状態生成部１２２は、インデックスレジスタ１２１ａとデータレジスタ１２１ｂとワークレジスタ１２１ｃとからなるレジスタ列の量子状態を
【数１１】
2019079226.tif 000013
に初期化する。ただし、ＢＲは［０，Ｎ）ｎに含まれる点ｘ∈Ｚｎの集合を表す。例えば、ＢＲは［０，Ｎ）ｎの一部の領域である。ＢＲは例えば実数Ｒによって定められる。なお、［０，Ｎ）は０以上Ｎ未満の半開区間を表す。例えば、ＢＲは所定のｎ次元の基準点ＮＶ／２＝（Ｎ／２，…，Ｎ／２）からの距離がＲ以下の点ｘ∈Ｚｎの集合を表す。言い換えると、例えば、ＢＲは原点から当該点ｘ∈Ｚｎへ向かうベクトルの集合を表す。すなわち、ＢＲ＝｛ｘ∈Ｚｎ｜||ｘ−ＮＶ／２||≦Ｒ｝である。図７Ａにｎ＝２の場合のＢＲを概念的に示す。ｎ＝２の場合、ＢＲは（Ｎ／２，Ｎ／２）を中心とした半径Ｒの円で囲まれた領域に属する点の集合である。なお、式（６）の３つの縦ベクトルのうち左側の｜０＞はインデックスレジスタ１２１ａの量子状態を表し、真ん中の｜ｘ＞はデータレジスタ１２１ｂの量子状態を表し、右側の｜０＞はワークレジスタ１２１ｃの量子状態を表す（ステップＳ１２２）。
【００４１】
２．量子フーリエ変換部１２３ａは、インデックスレジスタ１２１ａに対するＭ次元量子フーリエ変換を実行し、レジスタ列の量子状態を
【数１２】
2019079226.tif 000014
にする。なお、式（７）の３つの縦ベクトルのうち左側の｜ｗ＞はインデックスレジスタ１２１ａの量子状態を表し、真ん中の｜ｘ＞はデータレジスタ１２１ｂの量子状態を表し、右側の｜０＞はワークレジスタ１２１ｃの量子状態を表す（ステップＳ１２３ａ）。
【００４２】
３．ｗ∈ＺＭおよびｘ∈ＺＮｎに対して、（ｙｗ，ｘ，１，…，ｙｗ，ｘ，ｎ）をｘ−ｗｔ＝ｙｗ，ｘ，１ｂ１＋…＋ｙｗ，ｘ，ｎｂｎを満たす有理数ｙｗ，ｘ，１，…，ｙｗ，ｘ，ｎを要素とするｎ次元ベクトルとする。操作部１２４は、量子フーリエ変換部１２３ａで得られた式（７）の量子状態のレジスタ列に対して量子状態｜ｗ＞｜ｘ＞｜０＞を量子状態
｜ｗ＞｜ｘ＞｜ｄｅｔ（β）（ｙｗ，ｘ，１−ｆｌｏｏｒ（ｙｗ，ｘ，１）），…，ｄｅｔ（β）（ｙｗ，ｘ，ｎ−ｆｌｏｏｒ（ｙｗ，ｘ，ｎ））＞  （８）
にする量子操作を実行する（ステップＳ１２４）。観測部１２５ｃは、操作部１２４で得られた式（８）の量子状態のワークレジスタ１２１ｃを観測し、インデックスレジスタ１２１ａおよびデータレジスタ１２１ｂの量子状態を
【数１３】
2019079226.tif 000015
にする。ただし、ｓは不定なｎ次元ベクトルである。式（９）の２つの縦ベクトルのうち左側の｜ｗ＞はインデックスレジスタ１２１ａの量子状態を表し、右側の｜ｘ＞はデータレジスタ１２１ｂの量子状態を表す。このデータレジスタ１２１ｂの量子状態は、ＢＲにおける前述の和集合Ｌ（Ｂ）∪（ｔ＋Ｌ（Ｂ））∪（２ｔ＋Ｌ（Ｂ））∪（３ｔ＋Ｌ（Ｂ））∪…をｎ次元ベクトルｓだけ平行移動したものを表している（図１）。ｓは不定であるものの、この量子状態はＢＲの中で点列がｔ（ｄ）の間隔で並んだものを示している。図７Ｂにｎ＝２の場合の当該量子状態を概念的に示す（ステップＳ１２５ｃ）。
【００４３】
４．量子フーリエ変換部１２３ｂは、観測部１２５ｃでの観測後の式（９）の量子状態のデータレジスタ１２１ｂに対するＮ次元量子フーリエ変換を実行する。前述のようにデータレジスタ１２１ｂはｎ×ｃｅｉｌ（ｌｏｇ２ Ｎ）個の量子ビットからなる。このｎ×ｃｅｉｌ（ｌｏｇ２ Ｎ）個の量子ビットをｃｅｉｌ（ｌｏｇ２ Ｎ）個ごとの量子ビットに区分し、各ｃｅｉｌ（ｌｏｇ２ Ｎ）個の量子ビットからなるデータレジスタ１２１ｂの部分集合をデータサブレジスタ１２１ｂ−ｉと呼ぶ。データレジスタ１２１ｂはｎ個のデータサブレジスタ１２１ｂ−１，…，１２１ｂ−ｎからなる。量子フーリエ変換部１２３ｂは、式（９）の量子状態のデータレジスタ１２１ｂに対し、データレジスタ１２１ｂの各データサブレジスタ１２１ｂ−ｉごとに当該Ｎ次元量子フーリエ変換を実行する。これにより、双対格子Ｌ（Ｂ−）＝｛Σｉ＝１，…，ｎ  ｘｉｂ−ｉ｜ｘｉ∈Ｚ，ｂ−ｉ∈Ｂ−｝の格子点ベクトルｔ（ｃ）と、差分ベクトルｔ（ｄ）のベクトル和ｔ（ｃ）＋ｔ（ｄ）の重ね合わせ状態が得られる。図７Ｃにｎ＝２の場合の当該量子状態を概念的に示す（ステップＳ１２３ｂ）。観測部１２５ｂは、量子フーリエ変換部１２３ｂで得られた量子状態のデータレジスタ１２１ｂを観測して観測結果（ｒｊ１，…，ｒｊｎ）を得る。ｒｊｉはデータサブレジスタ１２１ｂ−ｉの観測結果である（ステップＳ１２５ｂ）。
【００４４】
５．逆量子フーリエ変換部１２６は、観測部１２５ｂでの観測後の量子状態のインデックスレジスタ１２１ａに対するＭ次元逆量子フーリエ変換を実行する（ステップＳ１２６）。観測部１２５ａは、逆量子フーリエ変換部１２６で得られた量子状態のインデックスレジスタ１２１ａを観測して観測結果ｒｊ０を得る。量子計算部１２は、ｊ回目の量子計算で得られたｒｊ＝（ｒｊ１，…，ｒｊｎ）∈［０，Ｎ）ｎおよびｒｊ０∈［０，Ｍ）を出力する（ステップＳ１２６）。
【００４５】
上記の量子計算がｊ＝１，…，ｍについて実行されることでｊ＝１，…，ｍについてのｒｊ＝（ｒｊ１，…，ｒｊｎ）およびｒｊ０が得られる。量子計算は以上の観測結果であるｒｊ，ｒｊ０を出力する。
【００４６】
≪古典計算部１３による古典計算（後処理）≫
古典計算部１３は、ｒｊおよびＮに関する双対基底Ｂ−を入力とし、双対格子Ｌ（Ｂ−）＝｛Σｉ＝１，…，ｎ  ｘｉｂ−ｉ｜ｘｉ∈Ｚ，ｂ−ｉ∈Ｂ−｝およびｎ次元ベクトルｒｊ＝（ｒｊ１，…，ｒｊｎ）について、当該ｎ次元ベクトルｒｊに最も近い最近ベクトルｒｊ（ｃ）＝（ｒｊ１（ｃ），…，ｒｊｎ（ｃ））∈Ｌ（Ｂ−）および差分ベクトルｒｊ（ｄ）＝ｒｊ−ｒｊ（ｃ）＝（ｒｊ１（ｄ），…，ｒｊｎ（ｄ））を得て出力する（ｒｊ（ｃ）およびｒｊ（ｄ）はいずれもｎ次元ベクトルである）。すなわち、古典計算部１３は、Ｎに関する双対基底Ｂ−とｎ次元ベクトルｒｊ＝（ｒｊ１，…，ｒｊｎ）との組（Ｂ−，ｒｊ）についてのＣＶＰ（Ｂ−，ｒｊ）を解く。Ｎの値が次元数ｎに対して大きいとき（例えば、Ｎの値が次元数ｎに対して指数的に大きいとき）、Ｎに関する双対基底Ｂ−について上述のように得られたｎ次元ベクトルｒｊのＣＶＰ（Ｂ−，ｒｊ）を、古典アルゴリズムを用いて厳密に解くことは可能である（ここでは証明を省略する）。古典計算部１３は、例えば、Nearest Planeアルゴリズムなどを用いてこのＣＶＰ（Ｂ−，ｒｊ）を厳密に解き、最近ベクトルｒｊ（ｃ）および差分ベクトルｒｊ（ｄ）を得て出力する。Ｎをｎに対して大きくすると高い確率で||ｒｊ（ｄ）||＜ｎとなることが証明できる。よってNearest Planeアルゴリズムによって最近ベクトルｒｊ（ｃ）および差分ベクトルｒｊ（ｄ）を求めることができる（ステップＳ１３）。
【００４７】
以上のように得られた整数Ｎ，Ｍ，ｍ、観測結果ｒｊ０、最近ベクトルｒｊ（ｃ）＝（ｒｊ１（ｃ），…，ｒｊｎ（ｃ））、差分ベクトルｒｊ（ｄ）＝（ｒｊ１（ｄ），…，ｒｊｎ（ｄ））が、ＣＶＰ（Ｂ，ｔ）の解である差分ベクトルｔ（ｄ）＝ｔ−ｔ（ｃ）＝（ｔ１（ｄ），…，ｔｎ（ｄ））Ｔおよびエラーに対応する小さな整数要素のベクトルｅ＝（ｅ１，…，ｅｍ）Ｔについて式（５）を満たすことを証明できる（ここでは証明を省略する）。変換装置１は、整数Ｎ，Ｍ，ｍ、観測結果ｒｊ０、最近ベクトルｒｊ（ｃ）＝（ｒｊ１（ｃ），…，ｒｊｎ（ｃ））、差分ベクトルｒｊ（ｄ）＝（ｒｊ１（ｄ），…，ｒｊｎ（ｄ））を変形ＬＷＥを表す情報として出力する。
【００４８】
［第２実施形態］
第２実施形態では、量子計算と古典計算とによってＬＷＥを変形ＬＷＥに変換する（図３）。以下では第１実施形態との相違点を中心に説明し、既に説明した事項については同じ参照番号を用いて説明を省略する。
【００４９】
図４に例示するように、本形態の変換装置２は、古典計算部２１，１３（第１，２古典計算部）、量子計算部１２、および制御部１４を有する。
【００５０】
＜処理＞
本形態の処理を説明する。本形態の変換装置２は、ＬＷＥを表す
【数１４】
2019079226.tif 000016
を満たすｎ次元ベクトルａｊ＝（ａ１ｊ，…，ａｎｊ）Ｔ，ｇ＝（ｇ１，…，ｇｎ）Ｔおよび整数Ｎ’の入力に対し、ｔ＝ｇとして前述の式（５）を満たす｛ｒｊｉ（ｃ），ｒｊｉ（ｄ），ｒｊ０｝およびｍ，Ｍ，Ｎを出力する。本形態の処理は古典計算部２１による古典計算（前処理）、量子計算部１２による量子計算、および古典計算部１３による古典計算（後処理）からなる。第１実施形態との相違点は、古典計算部２１による古典計算（前処理）のみである。以下、この前処理のみを説明する。
【００５１】
≪古典計算部２１による古典計算（前処理）≫
古典計算部２１（図４）は、ＬＷＥを特定する（ａ１，…，ａｍ’，ｇ，Ｎ’）を入力とし、以下の処理を実行する。
１．古典計算部２１の演算部は、｛ａ１，…，ａｍ’，Ｎ’ε１，…，Ｎ’εｎ｝から計算したＬＬＬ既約基底を基底Ｂとし、ｔ＝（ｔ１，…，ｔｎ）Ｔ＝ｇ＝（ｇ１，…，ｇｎ）Ｔとして出力する。ただし、εｕはｕ番目の要素が１で他の要素が０のｎ次元単位ベクトルεｎ＝（０，…，１，０，…，０）Ｔである（ｕ＝１，…，ｎ）（ステップＳ２１１）。
２．古典計算部２１の演算部は、基底ＢのＮ’に関する双対基底Ｂ−’＝｛ｂ１−’，…，ｂｎ−’｝を計算して出力する（ステップＳ１１２）。
３．古典計算部２１の演算部は、Ｎ’の倍数Ｎを選択して出力する（ステップＳ１１３）。
４．古典計算部２１の演算部は、双対基底Ｂ−’についてＮに関する双対基底Ｂ−＝（Ｎ／Ｎ’）Ｂ−’＝｛（Ｎ／Ｎ’）ｂ１−’，…，（Ｎ／Ｎ’）ｂｎ−’｝を得て出力する（ステップＳ１１４）。
５．古典計算部２１の演算部は、正の整数Ｍを選択して出力する。Ｍ＜Ｎであり、ＭはＮに対して十分に小さい（ステップＳ１１５）。
６．古典計算部２１の演算部は、２Ｒ≦Ｎ＜４Ｒを満たす実数Ｒを選択して出力する（ステップＳ１１６）。
７．古典計算部２１の演算部は、正の実数Ｌを選択して出力する。例えば、Ｌ×Ｍ＜Ｎを満たす（ステップＳ１１７）。
８．古典計算部２１の演算部は、正の整数ｍを選択（設定）して出力する（ステップＳ１１８）。
９．古典計算部２１は、（Ｌ，ｎ，Ｍ，Ｎ，Ｒ，Ｂ，ｔ）を出力する（ステップＳ１１９）。
【００５２】
その後、第１実施形態で説明した量子計算部１２による量子計算、および古典計算部１３による古典計算（後処理）が行われる。
【００５３】
［第３実施形態］
第３実施形態では、古典計算により、第１実施形態または第２実施形態で変換された変形ＬＷＥについてのＧａｐＣＶＰγを解く（図２および図３）。すなわち、第１実施形態または第２実施形態で得られた｛ｒｊｉ（ｃ），ｒｊｉ（ｄ），ｒｊ０｝およびｍ，Ｍ，Ｎで特定される式（５）を満たす差分ベクトルｔ（ｄ）が||ｔ（ｄ）||≦Ｌを満たすか||ｔ（ｄ）||＞γＬを満たすかを判定する。
【００５４】
＜構成＞
図８に例示するように、本形態の判定装置３は、ベクトル生成部３１、確率選択部３２、超平面距離推定部３３、判定部３４、および制御部３５を有する。判定装置３は、制御部３５の制御のもとで各処理を実行する。図９に例示するように、本形態の超平面距離推定部３３は、基底生成部３３１、ベクトル生成部３３２、超平面距離候補設定部３３３、および超平面距離選択部３３４を有する。
【００５５】
＜処理＞
本形態の処理を説明する。本形態の判定装置３は、｛ｒｊｉ（ｃ），ｒｊｉ（ｄ），ｒｊ０｝およびｍ，Ｍ，Ｎを入力とし、これらによって特定される式（５）を満たす差分ベクトルｔ（ｄ）が||ｔ（ｄ）||≦Ｌを満たすか||ｔ（ｄ）||＞γＬを満たすかを判定する。｛ｒｊｉ（ｃ），ｒｊｉ（ｄ），ｒｊ０｝およびｍ，Ｍ，Ｎは、第１実施形態または第２実施形態で説明した処理によって得られたものである。
【００５６】
１．ベクトル生成部３１は、ｒｊ（ｃ）＝（ｒｊ１（ｃ），…，ｒｊｎ（ｃ））およびｒｊ（ｄ）＝（ｒｊ１（ｄ），…，ｒｊｎ（ｄ））を入力とし、ｒｊ＝ｒｊ（ｃ）＋ｒｊ（ｄ）＝ｓｊ（ｃ）＋ｓｊ（ｄ）およびｓｊ（ｃ）∈Ｌ（Ｂ−）を満たすｎ次元ベクトルｓｊ（ｃ）＝（ｓｊ１（ｃ），…，ｓｊｎ（ｃ）），ｓｊ（ｄ）＝（ｓｊ１（ｄ），…，ｓｊｎ（ｄ））を選び、ｓｊ＝ｓｊ（ｃ）＋ｓｊ（ｄ）と設定する。本形態では||ｒｊ（ｄ）||≦||ｓｊ（ｄ）||≦２ＬＮを満たすようにｓｊ（ｄ）が選択される。また、ｓｊ０＝ｒｊ０と定義する（ステップＳ３１）。
【００５７】
２．確率選択部３２は、正の実数αおよび確率ｑを選択して出力する。本形態では、確率選択部３２は、
【数１５】
2019079226.tif 000017
を満たす確率ｑを選択して出力する（ステップＳ３２）。
【００５８】
３．ｎ次元ベクトルｓｊ（ｄ）を法線ベクトルとする有限個（複数個）の超平面Ｈｊに含まれる何れかの超平面Ｈｊが差分ベクトルｔ（ｄ）に対応することを証明できる（ここでは証明を省略する）。なお、ｓｊ（ｄ）を法線ベクトルとする超平面Ｈｊの集合は、格子Ｌ（Ｂ）の部分集合の要素であるベクトルによって張られるベクトル空間の平行移動であり、各ｊに対して有限個の超平面からなる。図１０に例示するように（ｎ＝２の例）、このような有限個の超平面Ｈｊの集合は互いに１／||ｓｊ（ｄ）||の間隔で並び、全体として２αＮ／Ｍ||ｓｊ（ｄ）||の範囲に配置されている。同じように互いに１／||ｓｊ（ｄ）||の間隔で並び、全体として２αＮ／Ｍ||ｓｊ（ｄ）||の範囲に配置される他の超平面も存在し、それらはＮ／||ｓｊ（ｄ）||の間隔で繰り返し配置されている。ただし、αは正の実数である。超平面距離推定部３３は、ｎ次元ベクトルｓｊ（ｄ）を法線ベクトルとする有限個の超平面Ｈｊに含まれる超平面Ｈｊのうち最も原点Ｏに近い超平面Ｈｊと原点Ｏとの距離ｄｉｓｔｊに基づく評価値Ｅｖａｌｑを得る（この処理の詳細は後述する）。図１１Ａおよび図１１Ｂに例示するように（ｎ＝２の例）、ｎ次元ベクトルｓｊ（ｄ）を法線ベクトルとする有限個の超平面Ｈｊに含まれる何れかの超平面Ｈｊに差分ベクトルｔ（ｄ）の先端が位置している。これらの図から分かるように、最も原点に近い超平面Ｈｊと原点との距離ｄｉｓｔｊは差分ベクトルｔ（ｄ）の長さと相関を持つ。そのため、たとえ差分ベクトルｔ（ｄ）が分からなくても、距離ｄｉｓｔｊに基づいて差分ベクトルｔ（ｄ）の長さを評価することができる。この評価を行うため、超平面距離推定部３３は、ｊ＝１，…，ｍの距離ｄｉｓｔｊに基づく評価値Ｅｖａｌｑを得る。本形態の評価値Ｅｖａｌｑは距離ｄｉｓｔ１，…，ｄｉｓｔｍの何れかである。本形態では、距離ｄｉｓｔｊがあまりにも大きなものをエラーとして排除し、残りの距離ｄｉｓｔｊのうち最も大きなものを評価値Ｅｖａｌｑに設定する。前述の確率ｑはこのエラーとして排除する距離ｄｉｓｔｊを選択するための基準となる。図１２に評価値Ｅｖａｌｑと||ｔ（ｄ）||／Ｌとの関係を例示する。図１２の縦軸は評価値Ｅｖａｌｑを表し、横軸は||ｔ（ｄ）||／Ｌを表す。この図から分かるように、評価値Ｅｖａｌｑの大きさを評価することで||ｔ（ｄ）||≦Ｌを満たすか||ｔ（ｄ）||＞γＬを満たすかを判定できる（ステップＳ３３）。
【００５９】
４．判定部３４は、評価値Ｅｖａｌｑを入力とし、Ｅｖａｌｑ≦Ｌを満たすと判定した場合に||ｔ（ｄ）||≦Ｌを満たす旨の情報を出力し、Ｅｖａｌｑ＞Ｌを満たすと判定した場合に||ｔ（ｄ）||＞γＬを満たす旨の情報を出力する（ステップＳ３４）。
【００６０】
≪超平面距離推定部３３の処理の詳細≫
超平面距離推定部３３の処理の詳細を例示する。
まず、超平面距離推定部３３は、各ｊ＝１，…，ｍについて以下の（ａ）〜（ｃ）の計算を行い、各距離ｄｉｓｔｊを決める。
【００６１】
（ａ）基底生成部３３１（超平面基底生成部）は、ｎ次元ベクトルｓｊについて格子｛ν∈Ｚｎ｜＜ｓｊ，ν＞＝０ ｍｏｄ Ｎ｝の基底Ｂｓｊを得て出力する。基底Ｂｓｊの計算にはエルミート標準形が用いられる（ステップＳ３３１）。
【００６２】
（ｂ）ベクトル生成部３３２は、＜ｓｊ（ｄ），ｂｓｊ（ｄ），Ｎ＞＝Ｎを満たすｎ次元ベクトルｂｓｊ（ｄ），Ｎを得て出力する。この計算には拡張ユークリッド互除法が用いられる（ステップＳ３３２）。
【００６３】
（ｃ）超平面距離候補設定部３３３は、ｙ０＝ｆｌｏｏｒ（（ｓｊ０−α）Ｎ／Ｍ）＋１およびｙ１＝ｃｅｉｌ（（ｓｊ０＋α）Ｎ／Ｍ）−１について、以下の（i）〜（iv）の処理を行う（ステップＳ３３３）。
（i）超平面距離候補設定部３３３は、＜ｓｊ，ｔｓｊ，ｙ０＞＝ｙ０ｍｏｄ Ｎおよび＜ｓｊ，ｔｓｊ，ｙ１＞＝ｙ１ ｍｏｄ Ｎを満たすｎ次元ベクトルｔｓｊ，ｙ０およびｔｓｊ，ｙ１を得て出力する。この計算には拡張ユークリッド互除法が用いられる。
（ii）超平面距離候補設定部３３３は、ｔ’ｓｊ，ｙ０∈（ｓｊ＋Ｌ（Ｂ））∩（ｔｓｊ，ｙ０＋Ｌ（Ｂｓｊ））およびｔ’ｓｊ，ｙ１∈（ｓｊ＋Ｌ（Ｂ））∩（ｔｓｊ，ｙ１＋Ｌ（Ｂｓｊ））を満たすｎ次元ベクトルｔ’ｓｊ，ｙ０およびｔ’ｓｊ，ｙ１を得て出力する。この計算にはスミス標準形が用いられる。
（iii）超平面距離候補設定部３３３は、ＡＢＳ（＜ｓｊ（ｄ），ｔ’ｓｊ，ｙ０＋ｋｂｓｊ（ｄ），Ｎ＞）を最小にするｋをｋｙ０とし、ＡＢＳ（＜ｓｊ（ｄ），ｔ’ｓｊ，ｙ１＋ｋｂｓｊ（ｄ），Ｎ＞）を最小にするｋをｋｙ１とし、ｔ”ｓｊ，ｙ０＝ｔ’ｓｊ，ｙ０＋ｋｙ０ｂｓｊ（ｄ），Ｎおよびｔ”ｓｊ，ｙ１＝ｔ’ｓｊ，ｙ１＋ｋｙ１ｂｓｊ（ｄ），Ｎを得て出力する。
（iv）超平面距離候補設定部３３３は、＜ｓｊ（ｄ），ｔ”ｓｊ，ｙ０＞≦０≦＜ｓｊ（ｄ），ｔ”ｓｊ，ｙ１＞または＜ｓｊ（ｄ），ｔ”ｓｊ，ｙ１＞≦０≦＜ｓｊ（ｄ），ｔ”ｓｊ，ｙ０＞ならば超平面距離候補ｄｉｓｔｊ＝０として出力する。それ以外の場合、すなわち＜ｓｊ（ｄ），ｔ”ｓｊ，ｙ０＞および＜ｓｊ（ｄ），ｔ”ｓｊ，ｙ１＞が共に正（＜ｓｊ（ｄ），ｔ”ｓｊ，ｙ０＞および＜ｓｊ（ｄ），ｔ”ｓｊ，ｙ１＞が０よりも大きい）または共に負（＜ｓｊ（ｄ），ｔ”ｓｊ，ｙ０＞および＜ｓｊ（ｄ），ｔ”ｓｊ，ｙ１＞が０よりも小さい）ならば、超平面距離候補設定部３３３は、ＡＢＳ（＜ｓｊ（ｄ），ｔ”ｓｊ，ｙ０＞）およびＡＢＳ（＜ｓｊ（ｄ），ｔ”ｓｊ，ｙ１＞）のうち小さい方を距離ｄｉｓｔｊ＝ｍｉｎ（ＡＢＳ（＜ｓｊ（ｄ），ｔ”ｓｊ，ｙ０＞），ＡＢＳ（＜ｓｊ（ｄ），ｔ”ｓｊ，ｙ１＞））として得て出力する。
【００６４】
ステップＳ３２で設定された確率ｑおよびステップＳ３３１〜Ｓ３３３で得られた距離ｄｉｓｔ１，…ｄｉｓｔｍは、超平面距離選択部３３４に入力される。超平面距離選択部３３４は、確率ｑについて、距離ｄｉｓｔ１，…，ｄｉｓｔｍを小さい順に並べた場合にｆｌｏｏｒ（ｑｍ）番目の値を評価値Ｅｖａｌｑ∈｛ｄｉｓｔ１，…，ｄｉｓｔｍ｝として得て出力する。すなわち、平面距離選択部３３４は、
Ｅｖａｌｑ＝ｍａｘ（｛ｄｉｓｔｊ｜ｊ＝１，…，ｍ｝，ｑ）
を計算する（ステップＳ３３４）。
【００６５】
［第４実施形態］
第４実施形態では、量子計算および古典計算により、第１実施形態で変換された変形ＬＷＥについてのＧａｐＣＶＰγを解く処理（第３実施形態）をサブルーチンとして利用してＣＶＰ（Ｂ，ｔ）を解く（図２）。
【００６６】
＜構成＞
図１３に例示するように、本形態の計算装置４は、初期設定部４１，４２１、子ノード生成部４２２、判定処理部４２３、ノード選択部４２４、差分ベクトル生成部４３、出力部４４、および制御部４５を有する。計算装置４は、制御部４５の制御のもとで各処理を実行する。
【００６７】
＜処理＞
本形態の処理を説明する。本形態の計算装置４は、ＣＶＰ（Ｂ，ｔ）についての基底Ｂおよび目標ベクトルｔとの組（Ｂ，ｔ）を入力とし、目標ベクトルｔと目標ベクトルｔに最も近い最近ベクトルｔ（ｃ）∈Ｌ（Ｂ）との差分ベクトルｔ（ｄ）＝ｔ−ｔ（ｃ）を得て出力する。この差分ベクトルは式（５）に示した変形ＬＷＥの解である。
【００６８】
初期設定部４１は、実数Ｌを初期値Ｌ１＝１，√２，√３，√４，√５，…，（Ｌ１ｍａｘ）１／２に設定し（ステップＳ４１）、制御部４５はそれぞれのＬ＝Ｌ１について、以下のステップＳ４２１〜Ｓ４２４、Ｓ４３の処理を実行させる。なお、Ｌ１ｍａｘは予め定められた正の整数である。
【００６９】
１．初期設定部４２１は、組（Ｂ，ｔ）を入力とし、基底Ｂ０と目標ベクトルｔ０との組からなるノード（Ｂ０，ｔ０）＝（Ｂ，ｔ）を得て出力する。また初期設定部４２１は、ｖ＝０に設定する（ステップＳ４２１）。
【００７０】
２．制御部４５はｖについて以下の処理を実行させる。
（ａ）子ノード生成部４２２は、ノード（Ｂｖ，ｔｖ）を用い、ι＝１，…，ρ（ｖ）について、基底Ｂｖ＋１と、目標ベクトルｔｖ，ιと、の組であるノード（Ｂｖ＋１，ｔｖ，１），…，（Ｂｖ＋１，ｔｖ，ρ（ｖ））（子ノード）を生成する。ただし、ρ（ｖ）は正の整数である。基底Ｂｖ＋１に対応する格子Ｌ（Ｂｖ＋１）＝｛Σｉ＝１，…，ｎ  ｘｉｂｉ｜ｘｉ∈Ｚ，ｂｉ∈Ｂｖ＋１｝は、基底Ｂｖに対応する格子Ｌ（Ｂｖ）＝｛Σｉ＝１，…，ｎ  ｘｉｂｉ｜ｘｉ∈Ｚ，ｂｉ∈Ｂｖ｝の部分格子である。いずれかのι’∈｛１，…，ρ（ｖ）｝について目標ベクトルｔｖ，ι’と当該目標ベクトルｔｖ，ι’に最も近い最近ベクトルｔｖ，ι’（ｃ）∈Ｌ（Ｂｖ＋１）との差分ベクトルｔｖ，ι’（ｄ）＝ｔｖ，ι’−ｔｖ，ι’（ｃ）（図１４Ｂ）は、目標ベクトルｔｖと当該目標ベクトルｔｖに最も近い最近ベクトルｔｖ（ｃ）∈Ｌ（Ｂｖ）との差分ベクトルｔｖ（ｄ）＝ｔｖ−ｔｖ（ｃ）（図１４Ａ）に等しい。この処理の詳細は後述する（ステップＳ４２２）。
【００７１】
（ｂ）判定処理部４２３は、実数Ｌ、ノード（Ｂｖ＋１，ｔｖ，１），…，（Ｂｖ＋１，ｔｖ，ρ（ｖ））を入力とし、第１実施形態で説明した変換装置１および第３実施形態で説明した判定装置３を用い、ι＝１，…，ρ（ｖ）についてＢ＝Ｂｖ＋１かつｔ＝ｔｖ，ιとして判定装置３の処理を実行する。これにより、判定処理部４２３は、ι＝１，…，ρ（ｖ）の各ノード（Ｂｖ＋１，ｔｖ，ι）について、||ｔｖ，ι（ｄ）||≦Ｌ（すなわち、Ｅｖａｌｑ≦Ｌ）を満たすか||ｔｖ，ι（ｄ）||＞γＬ（すなわち、Ｅｖａｌｑ＞Ｌ）を満たすかの判定結果を得ることができる（ステップＳ４２３）。
【００７２】
ここで、すべてのι＝１，…，ρ（ｖ）についてＥｖａｌｑ＞Ｌを満たすと判定された場合（すなわち、すべてのι＝１，…，ρ（ｖ）について||ｔｖ，ι（ｄ）||＞γＬと判定された場合）には設定した実数Ｌが小さ過ぎたとして、ノード選択部４２４は、実数Ｌを増加させて初期設定部４２１、子ノード生成部４２２、および判定処理部４２３の処理を再び実行させる。例えば、すべてのι＝１，…，ρ（ｖ）についてＥｖａｌｑ＞Ｌを満たすと判定された場合、ノード選択部４２４は、Ｌを（Ｌ２＋１）１／２に置き換えて（すなわち、（Ｌ２＋１）１／２を新たなＬとして）、処理をステップＳ４２１に戻す。一方、いずれかのι＝１，…，ρ（ｖ）についてＥｖａｌｑ≦Ｌを満たすと判定された場合（すなわち、||ｔｖ，ι（ｄ）||≦Ｌと判定された場合）、ノード選択部４２４は、最小のＥｖａｌｑに対応するノード（Ｂｖ＋１，ｔｖ，ι’）（ただし、ι’∈｛１，…，ρ（ｖ）｝）をノード（Ｂｖ＋１，ｔｖ＋１）に設定して出力する。このように選択されたノード（Ｂｖ＋１，ｔｖ，ι’）の目標ベクトルｔｖ，ι’に対応する差分ベクトルｔｖ，ι’（ｄ）は、差分ベクトルｔｖ（ｄ）＝ｔｖ−ｔｖ（ｃ）に等しい（図１４Ａおよび図１４Ｂ）。従って、このように選択されたノード（Ｂｖ＋１，ｔｖ，ι’）の目標ベクトルｔｖ，ι’に対応する差分ベクトルｔｖ，ι’（ｄ）は、最初の格子Ｌ（Ｂ）＝Ｌ（Ｂ０）における差分ベクトルｔ（ｄ）に等しい（図１５：ステップＳ４２４）。
【００７３】
制御部４５はｖ＝ｎ−１であるかを判定する。ｖ＝ｎ−１でなければ、制御部４５はｖ＋１を新たなｖとして処理をステップＳ４２２に戻す。一方、ｖ＝ｎ−１であれば、差分ベクトル生成部４３は、ノード（Ｂｖ＋１，ｔｖ＋１）＝（Ｂｎ，ｔｎ）の目標ベクトルｔｎを差分ベクトルｔＬ１（ｄ）として得て出力する。すなわち、差分ベクトル生成部４３は、ｖ＝０からｖ＝ｎ−１まで各ｖ＝０，…，ｎ−１について子ノード生成部４２２と判定処理部４２３とノード選択部４２４の処理（ステップＳ４２２〜４２４）を実行して得られたノード（Ｂｎ，ｔｎ）の目標ベクトルｔｎを差分ベクトルｔＬ１（ｄ）として得て出力する（ステップＳ４３）。
【００７４】
それぞれのＬ＝Ｌ１＝１，√２，√３，√４，√５，…，（Ｌ１ｍａｘ）１／２について、上述のステップＳ４２１〜Ｓ４２４、Ｓ４３の処理が行われることにより、各Ｌ１に対応する差分ベクトルの集合
【数１６】
2019079226.tif 000018
が得られる。出力部４４は、これらの集合に属する差分ベクトルのうち、何れかの初期値Ｌ１に対応する差分ベクトルｔＬ１（ｄ）を差分ベクトルｔ（ｄ）として出力する。例えば、出力部４４は、これらの集合に属する差分ベクトルのうち、最も短い差分ベクトルを差分ベクトルｔ（ｄ）として出力する（ステップＳ４４）。
【００７５】
≪子ノード生成部４２２の処理（ステップＳ４２２）の詳細≫
子ノード生成部４２２の処理（ステップＳ４２２）の詳細を例示する。
子ノード生成部４２２は、ノード（Ｂｖ，ｔｖ）を用いて、例えば、以下のようにノード（Ｂｖ＋１，ｔｖ，１），…，（Ｂｖ＋１，ｔｖ，ρ（ｖ））を生成する。
【００７６】
まず、子ノード生成部４２２は、Ｂ＝Ｂｖ、ｔ＝ｔｖ、ｍ＝１、かつＬ＝Ｌ１として、第１実施形態で説明した変換装置１の古典計算部１１に処理を依頼する。これにより、古典計算部１１は以下の処理を実行する。
１．古典計算部１１の演算部は、基底Ｂｖに対応する基底行列βｖの逆行列βｖ−１の要素の分母の最小公倍数Ｎｖ’を計算して出力する。ただし、βｖは基底Ｂｖ＝｛ｂｖ１，…，ｂｖｎ｝のｎ次元ベクトルｂｖ１，…，ｂｖｎを要素とするｎ行ｎ列の基底行列である。例えば、βｖはｎ次元ベクトルｂｖｉをｖｉ行目の成分とする行列である（ステップＳ１１１）。
２．古典計算部１１の演算部は、基底ＢｖのＮｖ’に関する双対基底Ｂｖ−’を計算して出力する（ステップＳ１１２）。
３．古典計算部１１の演算部は、Ｎｖ’の倍数Ｎｖを選択して出力する（ステップＳ１１３）。
４．古典計算部１１の演算部は、双対基底Ｂｖ−’についてＮｖに関する双対基底Ｂｖ−＝（Ｎｖ／Ｎｖ’）Ｂｖ−’を得て出力する（ステップＳ１１４）。
５．古典計算部１１の演算部は、正の整数Ｍｖを選択して出力する（ステップＳ１１５）。
６．古典計算部１１の演算部は、２Ｒｖ≦Ｎｖ＜４Ｒｖを満たす実数Ｒｖを選択して出力する（ステップＳ１１６）。
古典計算部１１は、（Ｌ，ｎ，Ｍｖ，Ｎｖ，Ｒｖ，Ｂｖ，ｔｖ）を出力する（ステップＳ１１９）。
なお、ｍ＝１かつＬ＝Ｌ１と定められているため、ステップＳ１１７およびＳ１１８は実行されない。
【００７７】
７．子ノード生成部４２２は、Ｂ＝Ｂｖ、ｔ＝ｔｖ、ｍ＝１、Ｌ＝Ｌ１、かつ（Ｌ，ｎ，Ｍ，Ｎ，Ｒ，Ｂ，ｔ）＝（Ｌ，ｎ，Ｍｖ，Ｎｖ，Ｒｖ，Ｂｖ，ｔｖ）とし、第１実施形態で説明した変換装置１の量子計算部１２に処理を依頼する。これにより、量子計算部１２は、Ｂ＝Ｂｖ、ｔ＝ｔｖ、ｍ＝１、Ｌ＝Ｌ１、かつ（Ｌ，ｎ，Ｍ，Ｎ，Ｒ，Ｂ，ｔ）＝（Ｌ，ｎ，Ｍｖ，Ｎｖ，Ｒｖ，Ｂｖ，ｔｖ）として第１実施形態で説明した量子計算を１回実行する。これにより、量子計算部１２は、ｊ＝ｍ＝１について、ｎ次元ベクトルｒ１＝（ｒ１１，…，ｒ１ｎ）∈［０，Ｎ）ｎおよびｒ１０∈［０，Ｍ）を得て出力する。以降、本形態では、このベクトルｒ１＝（ｒ１１，…，ｒ１ｎ）をｒ（ｖ）＝（ｒｖ，１，…，ｒｖ，ｎ）と表記し、ｒ１０をｒｖ，０と表記する。
【００７８】
８．子ノード生成部４２２は、ｒｊ＝ｒ（ｖ）、Ｎ＝Ｎｖ、Ｂ−＝Ｂｖ−とし、第１実施形態で説明した変換装置１の古典計算部１３に処理を依頼する。古典計算部１３は、Nearest Planeアルゴリズムなどを用いて、ＣＶＰ（Ｂｖ−，ｒ（ｖ））を解く。これにより、古典計算部１３は、ｒ（ｖ）に最も近い最近ベクトルｒ（ｖ）（ｃ）∈Ｌ（Ｂｖ−）および差分ベクトルｒ（ｖ）（ｄ）＝ｒ（ｖ）−ｒ（ｖ）（ｃ）を得て出力する。
【００７９】
９．子ノード生成部４２２の演算部は、ｎ次元ベクトルｒ（ｖ）について格子｛ν∈Ｚｎ｜＜ｒ（ｖ），ν＞＝０ ｍｏｄ Ｎｖ｝の基底Ｂｒ（ｖ）を得て出力する。基底Ｂｒ（ｖ）の計算にはエルミート標準形が用いられる。
【００８０】
１０．子ノード生成部４２２の演算部は、Ｌ（Ｂｖ）∩Ｌ（Ｂｒ（ｖ））（＝｛ｘ∈Ｌ（Ｂｖ）｜＜ｒ（ｖ）（ｄ），ν＞＝０ ｍｏｄ Ｎｖ｝）の基底Ｂ’ｒ（ｖ）を得て出力する。
【００８１】
１１．子ノード生成部４２２の演算部は、＜ｒ（ｖ）（ｄ），ｂｒ（ｖ）（ｄ），Ｎｖ＞＝Ｎｖを満たすｎ次元ベクトルｂｒ（ｖ）（ｄ），Ｎｖを得て出力する。この計算には拡張ユークリッド互除法が用いられる。
【００８２】
１２．子ノード生成部４２２の演算部は、ｚ（ｖ）＝ｒｏｕｎｄ（ｒｖ，０Ｎｖ／Ｍｖ）に対して、＜ｒ（ｖ），ｔｒ（ｖ），ｚ（ｖ）＞＝ｚ（ｖ） ｍｏｄ Ｎｖを満たすｎ次元ベクトルｔｒ（ｖ），ｚ（ｖ）を得て出力する。この計算には拡張ユークリッド互除法が用いられる。
【００８３】
１３．子ノード生成部４２２の演算部は、ｔ’ｒ（ｖ），ｚ（ｖ）∈（ｔｖ＋Ｌ（Ｂｖ））∩（ｔｒ（ｖ），ｚ（ｖ）＋Ｌ（Ｂｒ（ｖ）））を満たすｎ次元ベクトルｔ’ｒ（ｖ），ｚ（ｖ）を得て出力する。この計算にはスミス標準形が用いられる。
【００８４】
１４．子ノード生成部４２２の演算部は、ＡＢＳ（＜ｒ（ｖ）（ｄ），ｔ’ｒ（ｖ），ｚ（ｖ）＋ｋｂｒ（ｖ）（ｄ），Ｎｖ＞）を最小にするｋをｋｚ（ｖ）とし、ｔ”ｒ（ｖ），ｚ（ｖ）＝ｔ’ｒ（ｖ），ｚ（ｖ）＋ｋｚ（ｖ）ｂｒ（ｖ）（ｄ），Ｎｖを得て出力する。
【００８５】
１５．子ノード生成部４２２の演算部は、集合Ｃｖを以下のように設定する。
【数１７】
2019079226.tif 000019
【００８６】
１６．子ノード生成部４２２の演算部は、すべてのｙ∈Ｃｖに対して、以下のステップＳ４２２ａからＳ４２２ｄの操作を実行する。
（ａ）子ノード生成部４２２の演算部は、＜ｒ（ｖ），ｔｒ（ｖ），ｙ＞＝ｙ ｍｏｄ Ｎｖを満たすベクトルｔｒ（ｖ），ｙを得て出力する。この計算には拡張ユークリッド互除法が用いられる（ステップＳ４２２ａ）。
（ｂ）子ノード生成部４２２の演算部は、ｔ’ｒ（ｖ），ｙ∈（ｔｖ＋Ｌ（Ｂｖ））∩（ｔｒ（ｖ），ｙ＋Ｌ（Ｂｒ（ｖ）））を満たすベクトルｔ’ｒ（ｖ），ｙを得て出力する。この計算にはスミス標準形が用いられる（ステップＳ４２２ｂ）。
（ｃ）ｖ＋１次元超平面Ｈ（ｖ）をｓｐａｎ（ｒ（０）（ｄ），…，ｒ（ｖ）（ｄ））⊆Ｒｅｎで定義する。すなわち、ｒ（０）（ｄ），…，ｒ（ｖ）（ｄ）で張られる実数係数のｎ次元ベクトル空間がＨ（ｖ）である。ＰＨ（ｖ）（Ｂ’ｒ（ｖ）），ＰＨ（ｖ）（ｔ’ｒ（ｖ），ｙ）をそれぞれ、Ｂ’ｒ（ｖ），ｔ’ｒ（ｖ），ｙのＨ（ｖ）への射影とする。子ノード生成部４２２の演算部は、Nearest Planeアルゴリズムなどを用いて、ＣＶＰ（ＰＨ（ｖ）（Ｂ’ｒ（ｖ）），ＰＨ（ｖ）（ｔ’ｒ（ｖ），ｙ））を解く。これにより、子ノード生成部４２２の演算部は、ＰＨ（ｖ）（ｔ’ｒ（ｖ），ｙ）に最も近い最近ベクトルＰＨ（ｖ）（ｔ’ｒ（ｖ），ｙ）（ｃ）∈Ｌ（ＰＨ（ｖ）（Ｂ’ｒ（ｖ）））を得て出力する（ステップＳ４２２ｃ）。
（ｄ）ＰＨ（ｖ）（ｔ’ｒ（ｖ），ｙ）（ｃ）は、ＰＨ（ｖ）（Ｂ’ｒ（ｖ））の線形結合として表現できる。子ノード生成部４２２の演算部は、
【数１８】
2019079226.tif 000020
を満たすｃｖ，ｙ，ｘを計算し、
【数１９】
2019079226.tif 000021
を得て出力する（ステップＳ４２２ｄ）。
【００８７】
１７．子ノード生成部４２２の演算部は、集合Ｃｖ’を以下のように設定する。
【数２０】
2019079226.tif 000022
子ノード生成部４２２の演算部は、
【数２１】
2019079226.tif 000023
を｛（Ｂｖ＋１，ｔｖ，１），…，（Ｂｖ＋１，ｔｖ，ρ（ｖ））｝
として出力する。
【００８８】
［第５実施形態］
第５実施形態では、量子計算および古典計算により、第２実施形態で変換された変形ＬＷＥについてのＧａｐＣＶＰγを解く処理（第３実施形態）をサブルーチンとして利用してＬＷＥを解く（図３）。
【００８９】
＜構成＞
図１３に例示するように、本形態の計算装置５は、初期設定部４１，４２１、基底設定部５１、子ノード生成部４２２、判定処理部４２３、ノード選択部４２４、差分ベクトル生成部４３、出力部４４、および制御部４５を有する。計算装置４は、制御部４５の制御のもとで各処理を実行する。
【００９０】
＜処理＞
本形態の処理を説明する。本形態の計算装置５は、ｎ次元ベクトルａｊ＝（ａ１ｊ，…，ａｎｊ）Ｔ，ｇ＝（ｇ１，…，ｇｎ）Ｔおよび整数Ｎ’を入力とし、ＬＷＥを表す前述の式（１０）を満たす（ｄ１，…，ｄｎ）Ｔを差分ベクトルｔ（ｄ）として得て出力する。この差分ベクトルｔ（ｄ）は式（５）に示した変形ＬＷＥの解である。
【００９１】
初期設定部４１は、実数Ｌを初期値Ｌ１＝１，√２，√３，√４，√５，…，（Ｌ１ｍａｘ）１／２に設定し（ステップＳ４１）、制御部４５はそれぞれのＬ＝Ｌ１について、以下のステップＳ５１、Ｓ４２１〜Ｓ４２４、Ｓ４３の処理を実行させる。なお、Ｌ１ｍａｘは予め定められた正の整数である。
【００９２】
０．基底設定部５１は、｛ａ１，…，ａｍ，Ｎ’ε１，…，Ｎ’εｎ｝から計算したＬＬＬ既約基底を基底Ｂとし、さらにｔ＝ｇ＝（ｇ１，…，ｇｎ）Ｔとして出力する（ステップＳ５１）。以降は第４実施形態と同じである。以下概要を示す。
【００９３】
初期設定部４２１は、基底Ｂおよびｔ＝ｇを入力とし、基底Ｂ０と目標ベクトルｔ０との組からなるノード（Ｂ０，ｔ０）＝（Ｂ，ｔ）を得て出力する。また初期設定部４２１は、ｖ＝０に設定する（ステップＳ４２１）。
【００９４】
（ａ）子ノード生成部４２２は、ノード（Ｂｖ，ｔｖ）を用い、ι＝１，…，ρ（ｖ）について、基底Ｂｖ＋１と、目標ベクトルｔｖ，ιと、の組であるノード（Ｂｖ＋１，ｔｖ，１），…，（Ｂｖ＋１，ｔｖ，ρ（ｖ））（子ノード）を生成する。ただし、ρ（ｖ）は正の整数である。基底Ｂｖ＋１に対応する格子Ｌ（Ｂｖ＋１）＝｛Σｉ＝１，…，ｎ  ｘｉｂｉ｜ｘｉ∈Ｚ，ｂｉ∈Ｂｖ＋１｝は、基底Ｂｖに対応する格子Ｌ（Ｂｖ）＝｛Σｉ＝１，…，ｎ  ｘｉｂｉ｜ｘｉ∈Ｚ，ｂｉ∈Ｂｖ｝の部分格子である。いずれかのι’∈｛１，…，ρ（ｖ）｝について目標ベクトルｔｖ，ι’と当該目標ベクトルｔｖ，ι’に最も近い最近ベクトルｔｖ，ι’（ｃ）∈Ｌ（Ｂｖ＋１）との差分ベクトルｔｖ，ι’（ｄ）＝ｔｖ，ι’−ｔｖ，ι’（ｃ）は、目標ベクトルｔｖと当該目標ベクトルｔｖに最も近い最近ベクトルｔｖ（ｃ）∈Ｌ（Ｂｖ）との差分ベクトルｔｖ（ｄ）＝ｔｖ−ｔｖ（ｃ）に等しい（ステップＳ４２２）。
（ｂ）判定処理部４２３は、ι＝１，…，ρ（ｖ）の各ノード（Ｂｖ＋１，ｔｖ，ι）について、||ｔｖ，ι（ｄ）||≦Ｌ（すなわち、Ｅｖａｌｑ≦Ｌ）を満たすか||ｔｖ，ι（ｄ）||＞γＬ（すなわち、Ｅｖａｌｑ＞Ｌ）を満たすかの判定結果を得る（ステップＳ４２３）。
ここで、すべてのι＝１，…，ρ（ｖ）についてＥｖａｌｑ＞Ｌを満たすと判定された場合、ノード選択部４２４は、実数Ｌを増加させてステップＳ４２１からＳ４２３の処理を再び実行させる。一方、いずれかのι＝１，…，ρ（ｖ）についてＥｖａｌｑ≦Ｌを満たすと判定された場合、ノード選択部４２４は、最小のＥｖａｌｑに対応するノード（Ｂｖ＋１，ｔｖ，ι’）をノード（Ｂｖ＋１，ｔｖ＋１）に設定して出力する（ステップＳ４２４）。
【００９５】
制御部４５はｖ＝ｎ−１であるかを判定する。ｖ＝ｎ−１でなければ、制御部４５はｖ＋１を新たなｖとして処理をステップＳ４２２に戻す。一方、ｖ＝ｎ−１であれば、差分ベクトル生成部４３は、ノード（Ｂｖ＋１，ｔｖ＋１）＝（Ｂｎ，ｔｎ）の目標ベクトルｔｎを差分ベクトルｔＬ１（ｄ）として得て出力する（ステップＳ４３）。
【００９６】
出力部４４は、各Ｌ１に対応する差分ベクトルの集合に属する差分ベクトルのうち、何れかの初期値Ｌ１に対応する差分ベクトルｔＬ１（ｄ）を差分ベクトルｔ（ｄ）として出力する。例えば、出力部４４は、これらの集合に属する差分ベクトルのうち、最も短い差分ベクトルを差分ベクトルｔ（ｄ）として出力する（ステップＳ４４）。
【００９７】
［第６実施形態］
本形態は、第４実施形態の処理をサブルーチンとして利用してＳＶＰを解く。
【００９８】
＜構成＞
図１６に例示するように、本形態の計算装置６は、基底生成部６１、設定部６２、選択部６３、および制御部６５を有する。
【００９９】
＜処理＞
本形態の計算装置６は、基底Ｂを入力として、格子Ｌ（Ｂ）の中で最も原点に近い格子点への最短ベクトルｔ（ｃ）を出力する。
【０１００】
まず、基底生成部６１が、すべてのｉ＝１，…，ｎについて、Ｂｉ＝｛ｂ１，…，ｂｉ−１，２ｂｉ，ｂｉ＋１，…，ｂｎ｝に設定する（ステップＳ６１）。
【０１０１】
次に、設定部６２が、ｉ＝１，…，ｎについて、Ｂ＝Ｂｉかつｔ＝ｂｉとし、第４実施形態で説明した計算装置４に処理を依頼する。計算装置４は、Ｂ＝Ｂｉかつｔ＝ｂｉとして第４実施形態で説明した処理を行って差分ベクトルｔ（ｄ）を得て出力する。設定部６２は、Ｂ＝Ｂｉおよびｔ＝ｂｉ対して得られた当該差分ベクトルｔ（ｄ）をｔｉ（ｄ）に設定する。これにより、設定部６２はｔ１（ｄ），…，ｔｎ（ｄ）を得る（ステップＳ６２）。
【０１０２】
選択部６３は、設定部６２で得られたｔ１（ｄ），…，ｔｎ（ｄ）を入力とし、ｔ１（ｄ），…，ｔｎ（ｄ）の中で最短もの（長さが最も短いベクトル）を最短ベクトルｔ（ｃ）として出力する（ステップＳ６３）。
【０１０３】
［その他の変形例等］
なお、本発明は上述の実施形態に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０１０４】
古典計算部１１，２１，１３、制御部１４、判定装置３、および計算装置４〜６は、例えば、ＣＰＵ（central processing unit）等のプロセッサ（ハードウェア・プロセッサ）およびＲＡＭ（random-access memory）・ＲＯＭ（read-only memory）等のメモリ等を備える汎用または専用のコンピュータが所定のプログラムを実行することで構成される。このコンピュータは１個のプロセッサやメモリを備えていてもよいし、複数個のプロセッサやメモリを備えていてもよい。このプログラムはコンピュータにインストールされてもよいし、予めＲＯＭ等に記録されていてもよい。また、ＣＰＵのようにプログラムが読み込まれることで機能構成を実現する電子回路（circuitry）ではなく、プログラムを用いることなく処理機能を実現する電子回路を用いて一部またはすべての演算部が構成されてもよい。また、１個の装置を構成する電子回路が複数のＣＰＵを含んでいてもよい。量子計算部１２は、公知の量子コンピュータによって構成される。
【０１０５】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。
【０１０６】
このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１０７】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。処理の実行時、このコンピュータは、自己の記憶装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。
【０１０８】
コンピュータ上で所定のプログラムを実行させて本装置の処理機能が実現されるのではなく、これらの処理機能の少なくとも一部がハードウェアで実現されてもよい。
【産業上の利用可能性】
【０１０９】
本発明を用いることにより、組み合わせ最適化問題の一種である格子問題の部分問題を効率的に解くことができる。これにより、例えば２つの産業分野に影響を及ぼす。人工知能分野と耐量子暗号分野である。
【０１１０】
本発明を適用することで、人工知能分野での組み合わせ最適化問題の部分問題を効率的に解くことができる。Shorのアルゴリズムは周期発見問題に応用できるが，人工知能で問題となっている組み合わせ最適化問題には適用できない。一方、Shor のアルゴリズム発見以降に提案されたGroverのアルゴリズムや量子ウォークアルゴリズムなどは、組み合わせ最適化問題に適用できるが、問題を効率的に解くことができない。本発明は、両者の欠点を補い、量子コンピュータの人工知能への応用に新たな可能性をもたらす。例えば、本発明をゲート型量子コンピュータ上および古典コンピュータで実装することにより、人工知能を用いて工業・材料・医療・医薬・エネルギー・物理・化学・経済・実社会等の様々な事象を高速にシミュレーションすることが可能となり、各分野の急激な進歩発展に貢献する。
【０１１１】
また、耐量子暗号分野においては、本発明によって従来の格子暗号の安全性が損なわれる可能性がある。脆弱性を補うために鍵長を長くする等の対策が必要になるが、鍵長の変更は暗号効率の悪化を招きかねない。本発明を格子暗号の安全性評価と暗号効率との評価に利用すれば、これらの問題を共に解決する暗号方式の開発に貢献することも期待される。
【符号の説明】
【０１１２】
１，２  変換装置
３  判定装置
４〜６  計算装置
【図１】
2019079226.tif 000036
【図２】
2019079226.tif 000037
【図３】
2019079226.tif 000038
【図４】
2019079226.tif 000039
【図５】
2019079226.tif 000040
【図６】
2019079226.tif 000041
【図７】
2019079226.tif 000042
【図８】
2019079226.tif 000043
【図９】
2019079226.tif 000044
【図１０】
2019079226.tif 000045
【図１１】
2019079226.tif 000046
【図１２】
2019079226.tif 000047
【図１３】
2019079226.tif 000048
【図１４】
2019079226.tif 000049
【図１５】
2019079226.tif 000050
【図１６】
2019079226.tif 000051