(57)【要約】【課題】距離比較問題の解法を提供する。【解決手段】量子状態｜φ＞０のレジスタと各量子状態｜φ＞ｔ１のレジスタとの各ペアに対してスワップテストを実行し、量子状態｜φ＞０と量子状態｜φ＞ｔ１とのペアに対するスワップテストの結果が受理となるか拒否となるかを判定し、量子状態｜φ＞０のレジスタと量子状態｜φ＞ｔ２のレジスタとの各ペアに対してスワップテストを実行し、量子状態｜φ＞０と量子状態｜φ＞ｔ２とのペアに対するスワップテストの結果が受理となるか拒否となるかを判定する。それぞれのスワップテストが受理となる確率を比較し、距離比較問題の解を得る。【選択図】図３
2020149523.tif 000002
【特許請求の範囲】
【請求項１】
判定装置であって、
第１古典計算部と第１量子状態生成部と第２量子状態生成部と第１スワップテスト部と第３量子状態生成部と第４量子状態生成部と第２スワップテスト部と第２古典計算部とを有し、
ｎ，Ｎが正の整数であり、ｉ＝１，…，ｎであり、ｉｍが虚数単位であり、ηＴがηの転置であり、｜Λ｜がΛの要素数であり、||η||がηの長さであり、＜τ，χ＞がτとχとの内積であり、η１⊆η２はη１がη２の部分集合であることを表し、Ｂ＝｛ｂ１，…，ｂｎ｝が一次独立なｎ次元ベクトルｂｉからなる基底であり、前記ｎ次元ベクトルｂｉのそれぞれがｎ個の整数要素からなり、Ｌ（Ｂ）が格子｛Σｉ＝１，…，ｎ  ｘｉｂｉ｜ｘｉ∈Ｚ，ｂｉ∈Ｂ｝であり、Ｌ（Ｂ−）が前記基底Ｂと前記整数Ｎとに対して定義されるＮに関する双対格子であり、ｘｉが整数であり、Ｂ−がＢのＮに関する双対基底であり、Ｒ⊆Ｚｎが整数要素からなるｎ次空間に属する部分領域であり、ｔ１＝（ｔ１，１，…，ｔ１，ｎ）Ｔがｎ個の整数要素ｔ１，ｉからなる目標ベクトルであり、ｔ２＝（ｔ２，１，…，ｔ２，ｎ）Ｔがｎ個の整数要素ｔ２，ｉからなる目標ベクトルであり、ｔ１（ｄ）が前記目標ベクトルｔ１と前記目標ベクトルｔ１の最近ベクトルｔ１（ｃ）∈Ｌ（Ｂ）との差分ベクトルｔ１（ｄ）＝ｔ１−ｔ１（ｃ）＝（ｔ１，１（ｄ），…，ｔ１，ｎ（ｄ））であり、ｔ２（ｄ）が前記目標ベクトルｔ２と前記目標ベクトルｔ２の最近ベクトルｔ２（ｃ）∈Ｌ（Ｂ）との差分ベクトルｔ２（ｄ）＝ｔ２−ｔ２（ｃ）＝（ｔ２，１（ｄ），…，ｔ２，ｎ（ｄ））であり、
前記第１古典計算部は、前記基底Ｂおよび前記整数Ｎを用い、前記双対基底Ｂ−を得て出力し、
前記第１量子状態生成部は、
【数１９２】
2020149523.tif 000194
の量子状態からなるレジスタを複数個生成し、
前記第２量子状態生成部は、一部の量子状態｜φ＞０のレジスタに量子操作を行い、前記量子操作が施されたレジスタの量子状態を
【数１９３】
2020149523.tif 000195
に遷移させ、
前記第１スワップテスト部は、量子状態｜φ＞０のレジスタと各量子状態｜φ＞ｔ１のレジスタとの各ペアに対してスワップテストを実行し、前記量子状態｜φ＞０と前記量子状態｜φ＞ｔ１とのペアに対するスワップテストの結果が受理となるか拒否となるかを判定し、
前記第３量子状態生成部は、
【数１９４】
2020149523.tif 000196
の量子状態からなるレジスタを複数個生成し、
前記第４量子状態生成部は、一部の量子状態｜φ＞０のレジスタに量子操作を行い、前記量子操作が施されたレジスタの量子状態を
【数１９５】
2020149523.tif 000197
に遷移させ、
前記第２スワップテスト部は、量子状態｜φ＞０のレジスタと量子状態｜φ＞ｔ２のレジスタとの各ペアに対してスワップテストを実行し、前記量子状態｜φ＞０と前記量子状態｜φ＞ｔ２とのペアに対するスワップテストの結果が受理となるか拒否となるかを判定し、
前記第２古典計算部は、前記スワップテストの結果を用いて、量子状態｜φ＞０と量子状態｜φ＞ｔ１とのペアに対するスワップテストの結果が受理となる確率ｐ１と、量子状態｜φ＞０と量子状態｜φ＞ｔ２とのペアに対するスワップテストの結果が受理となる確率ｐ２を計算し、ｐ１≧ｐ２の場合に||ｔ１（ｄ）||≦||ｔ２（ｄ）||であることを表す情報を出力し、ｐ１＜ｐ２の場合に||ｔ１（ｄ）||＞||ｔ２（ｄ）||であることを表す情報を出力するか、または、ｐ１＞ｐ２の場合に||ｔ１（ｄ）||＜||ｔ２（ｄ）||であることを表す情報を出力し、ｐ１≦ｐ２の場合に||ｔ１（ｄ）||≧|ｔ２（ｄ）||であることを表す情報を出力する、判定装置。
【請求項２】
計算装置であって、
初期設定部と基底選択部と代表元選択部と子ノード生成部と古典計算部とノード選択部と制御部と第１量子状態生成部と第２量子状態生成部とスワップテスト部とを有し、
ｎ，Ｎ，ν（Ｄ），Ｄが正の整数であり、ｉ＝１，…，ｎであり、ｉｍが虚数単位であり、ηＴがηの転置であり、｜Λ｜がΛの要素数であり、||η||がηの長さであり、η１⊆η２はη１がη２の部分集合であることを表し、η１⊂η２はη１がη２の真部分集合であることを表し、＜τ，χ＞がτとχとの内積であり、Ｂ＝｛ｂ１，…，ｂｎ｝が一次独立なｎ次元ベクトルｂｉからなる基底であり、前記ｎ次元ベクトルｂｉのそれぞれがｎ個の整数要素からなり、Ｌ（Ｂ）が格子｛Σｉ＝１，…，ｎ  ｘｉｂｉ｜ｘｉ∈Ｚ，ｂｉ∈Ｂ｝であり、Ｌ（Ｂ−）が前記基底Ｂと前記整数Ｎとに対して定義されるＮに関する双対格子Ｌ（Ｂ−）であり、ｘｉが整数であり、Ｂ−がＢのＮに関する双対基底であり、Ｒ⊆Ｚｎが整数要素からなるｎ次空間に属する部分領域であり、ｔ＝（ｔ１，…，ｔｎ）Ｔがｎ個の整数要素ｔｉからなる目標ベクトルであり、
前記初期設定部は、組（Ｂ，ｔ）を入力とし、基底Ｂ０と目標ベクトルｔ（０）との組からなるノード（Ｂ０，ｔ（０））＝（Ｂ，ｔ）を設定し、
前記基底選択部は、格子Ｌ（ＢＤ−１）の部分格子Ｌ（ＢＤ）⊂Ｌ（ＢＤ−１）の基底ＢＤを選択し、
前記代表元選択部は、（ｃＤ，０＋Ｌ（ＢＤ））∪（ｃＤ，１＋Ｌ（ＢＤ））∪・・・∪（ｃＤ，ν（Ｄ）−１＋Ｌ（ＢＤ））＝Ｌ（ＢＤ−１）であり、０以上ν（Ｄ）以下の任意のκ１，κ２について、κ１≠κ２である場合に（ｃＤ，κ１＋Ｌ（ＢＤ））∩（ｃＤ，κ２＋Ｌ（ＢＤ））が空であるとの条件を満たす、代表元ｃＤ，０，ｃＤ，１，・・・，ｃＤ，ν（Ｄ）−１を選択し、前記代表元ｃＤ，０，ｃＤ，１，・・・，ｃＤ，ν（Ｄ）−１のそれぞれが整数要素からなるｎ次元ベクトルであり、
前記子ノード生成部は、ノード（ＢＤ−１，ｔ（Ｄ−１））の子ノードとして、ｋ’＝０，１，…，ν（Ｄ）−１についてノード（ＢＤ，ｔ（Ｄ−１）−ｃＤ，ｋ’）を選択し、
前記古典計算部は、前記基底ＢＤおよび前記整数Ｎを用い、前記双対基底ＢＤ−を得て出力し、
前記第１量子状態生成部は、
【数１９６】
2020149523.tif 000198
の量子状態からなるレジスタを複数個生成し、
前記第２量子状態生成部は、一部の量子状態｜φ＞Ｄ，０のレジスタに量子操作を行い、前記量子操作が施されたレジスタの量子状態を
【数１９７】
2020149523.tif 000199
に遷移させ、
前記スワップテスト部は、ｋ’＝０，１，…，ν（Ｄ）−１について、量子状態｜φ＞Ｄ，０のレジスタと量子状態｜φ＞ｔ（Ｄ，ｋ’）のレジスタとの各ペアに対してスワップテストを実行し、前記量子状態｜φ＞０と前記量子状態｜φ＞ｔ（Ｄ，ｋ’）とのペアに対するスワップテストの結果が受理となるか拒否となるかを判定し、
前記ノード選択部は、前記スワップテストの結果を用いて、量子状態｜φ＞Ｄ，０と量子状態｜φ＞ｔ（Ｄ，ｋ’）とのペアに対するスワップテストの結果が受理となる確率ｐＤ，ｋ’を計算し、前記確率ｐＤ，０，…，ｐＤ，ν（Ｄ）−１のうち最も高い確率ｐＤ，ｋｍａｘに対応するノード（ＢＤ，ｔ（Ｄ−１）−ｃＤ，ｋｍａｘ）を選択し、ｋｍａｘ∈｛０，１，…，ν（Ｄ）−１｝であり、
前記制御部は、ｔ（Ｄ−１）−ｃＤ，ｋｍａｘと格子Ｌ（ＢＤ）との間の最短の差分ベクトルｔ（ＢＤ，ｄ）を得、前記差分ベクトルｔ（ＢＤ，ｄ）の長さが基準値よりも小さい場合に前記差分ベクトルｔ（ＢＤ，ｄ）を差分ベクトルｔ（ｄ）として出力し、最近ベクトルｔ（ＢＤ，ｃ）＝ｔ−ｔ（ＢＤ，ｄ）∈Ｌ（ＢＤ）を最近ベクトルｔ（ｃ）として出力し、前記差分ベクトルｔ（ＢＤ，ｄ）の長さが前記基準値以上の場合に、Ｄ＋１を新たなＤとし、さらにｔ（Ｄ）＝ｔ（Ｄ−１）−ｃＤ，ｋｍａｘとして、前記基底選択部と前記代表元選択部と前記子ノード生成部と前記古典計算部と前記第１量子状態生成部と前記第２量子状態生成部と前記スワップテスト部と前記ノード選択部と前記制御部との各処理を再び実行する制御を行う、計算装置。
【請求項３】
基底Ｂを入力として、格子Ｌ（Ｂ）の中で最も原点に近い格子点への最短ベクトルを出力する計算装置であって、
基底生成部と設定部と選択部とを有し、
ｎが正の整数であり、Ｂ＝｛ｂ１，…，ｂｎ｝が一次独立なｎ個のｎ次元ベクトルｂｉからなる基底であり、前記ｎ次元ベクトルｂｉのそれぞれがｎ個の整数要素からなり、Ｌ（Ｂ）が格子｛Σｉ＝１，…，ｎ  ｘｉｂｉ｜ｘｉ∈Ｚ，ｂｉ∈Ｂ｝であり、
前記基底生成部は、すべてのｉ＝１，…，ｎについて、Ｂｉ＝｛ｂ１，…，ｂｉ−１，２ｂｉ，ｂｉ＋１，…，ｂｎ｝に設定し、
前記設定部は、請求項２に記載の前記計算装置の処理をＢ＝Ｂｉかつｔ＝ｂｉとして実行して得られた前記差分ベクトルｔ（ｄ）をｔｉ（ｄ）に設定し、
前記選択部は、前記設定部で得られたｔ１（ｄ），…，ｔｎ（ｄ）の中で最短のものを前記最短ベクトルとして出力する、計算装置。
【請求項４】
ｎ次元ベクトルａｊ，ｇおよび整数Ｎの入力に対して
【数１９８】
2020149523.tif 000200
を満たす（Ｘ１，…，Ｘｍ）Ｔを出力する計算装置であって、
第１古典計算部と第１量子状態生成部と第２量子状態生成部とスワップテスト部と選択部と第２古典計算部とを有し、
ｎ，ｍ，Ｎが正の整数であり、ｉ＝１，…，ｎであり、ｊ＝１，…，ｍであり、ｉｍが虚数単位であり、ηＴがηの転置であり、｜Λ｜がΛの要素数であり、＜τ，χ＞がτとχとの内積であり、η１⊆η２はη１がη２の部分集合であることを表し、Ｂ＝｛ｂ１，…，ｂｎ｝が一次独立なｎ次元ベクトルｂｉからなる基底であり、前記ｎ次元ベクトルｂｉのそれぞれがｎ個の整数要素からなり、Ｌ（Ｂ）が格子｛Σｉ＝１，…，ｎ  ｘｉｂｉ｜ｘｉ∈Ｚ，ｂｉ∈Ｂ｝であり、Ｌ（Ｂ−）が前記基底Ｂと前記整数Ｎとに対して定義されるＮに関する双対格子Ｌ（Ｂ−）であり、ｘｉが整数であり、Ｂ−がＢのＮに関する双対基底であり、Ｒ⊆Ｚｎが整数要素からなるｎ次空間に属する部分領域であり、ａｊがｎ個の整数要素ａ１ｊ，…，ａｎｊからなるｎ次元ベクトルａｊ＝（ａ１ｊ，…，ａｎｊ）Ｔであり、ｇがｎ個の要素ｇ１，…，ｇｎからなるｎ次元ベクトルｇ＝（ｇ１，…，ｇｎ）Ｔであり、ｄがｎ個の要素ｄ１，…，ｄｎからなるｎ次元ベクトルｄ＝（ｄ１，…，ｄｎ）Ｔであり、εｕがｕ番目の要素が１で他の要素が０のｎ次元単位ベクトルεｕ＝（０，…，１，０，…，０）Ｔであり、
Ｘ１，…，Ｘｍのそれぞれが深さＤ＝１，…，ｍの何れかに対応する処理で得られ、深さＤに対応する処理で得られるＸｊがＸｊ（Ｄ）∈｛Ｘ１，…，Ｘｍ｝であり、深さＤに対応する処理で得られるＸｊ（Ｄ）の値がαｊ（Ｄ）であり、深さＤに対応する処理で得られるＸｊに対応する前記ｎ次元ベクトルａｊがａｊ（Ｄ）∈｛ａ１，…，ａｍ｝であり、ＡＤ−１＝（ａｊ（Ｄ）  ａｊ（Ｄ＋１）… ａｊ（ｍ））であり、Ｘ’Ｄ−１＝（Ｘｊ（Ｄ），Ｘｊ（Ｄ＋１），…，Ｘｊ（ｍ））Ｔであり、
【数１９９】
2020149523.tif 000201
であり、
前記第１古典計算部は、深さＤに対応する処理において、｛ａｊ（Ｄ＋１）Ｔ  ａｊ（Ｄ＋２）Ｔ… ａｊ（ｍ）Ｔ  Ｎε１Ｔ…ＮεｎＴ｝で定義される格子のＬＬＬ既約基底ＢＤのＮに関する双対基底ＢＤ−を得て出力し、
前記第１量子状態生成部は、前記深さＤに対応する処理において、
【数２００】
2020149523.tif 000202
の量子状態からなるレジスタを複数個生成し、
前記第２量子状態生成部は、前記深さＤに対応する処理において、一部の量子状態｜φ＞Ｄ，０のレジスタに量子操作を行い、ｊ’＝０，１，２…，Ｎ−１について、前記量子操作が施されたレジスタの量子状態を
【数２０１】
2020149523.tif 000203
に遷移させ、
前記スワップテスト部は、前記深さＤに対応する処理において、ｊ’＝０，１，２…，Ｎ−１について、量子状態｜φ＞Ｄ，０のレジスタと量子状態｜φ＞ｔ（Ｄ，ｊ’）のレジスタとの各ペアに対してスワップテストを実行し、前記量子状態｜φ＞Ｄ，０と前記量子状態｜φ＞ｔ（Ｄ，ｊ’）とのペアに対するスワップテストの結果が受理となるか拒否となるかを判定し、
前記選択部は、前記深さＤに対応する処理において、前記スワップテストの結果を用いて、量子状態｜φ＞Ｄ，０と量子状態｜φ＞ｔ（Ｄ，ｊ’）とのペアに対するスワップテストの結果が受理となる確率ｐＤ，ｊ’を計算し、前記確率ｐＤ，０，ｐＤ，１，…，ｐＤ，Ｎ−１のうち最も高い確率ｐＤ，ｊｍａｘに対応するｊｍａｘ∈｛０，１，２…，Ｎ−１｝をαｊ（Ｄ）として出力し、さらにｇＤ’＝ｇＤ−１’−αｊ（Ｄ）・ａｊ（Ｄ）を出力し、
前記第２古典計算部は、前記選択部がすべてのＤ＝１，…，ｍについてαｊ（Ｄ）を出力している場合には、αｊ（１），…，αｊ（ｍ）を整列して得られる（Ｘ１，…，Ｘｍ）Ｔを出力し、前記選択部が何れかのＤ＝１，…，ｍについてαｊ（Ｄ）を出力していない場合には、前記第１古典計算部と前記第１量子状態生成部と前記第２量子状態生成部と前記スワップテスト部と前記選択部と前記第２古典計算部の各処理を再び実行させる制御を行う、計算装置。
【請求項５】
判定装置であって、
第１古典計算部と第１量子状態生成部と第２量子状態生成部と第１スワップテスト部と第３量子状態生成部と第４量子状態生成部と第２スワップテスト部と第２古典計算部とを有し、
ｎ，ｎ’が正の整数であり、ｎ’＞ｎであり、ｉ＝１，…，ｎであり、ｉ’＝１，…，ｎ’であり、ｉｍが虚数単位であり、ηＴがηの転置であり、｜Λ｜がΛの要素数であり、||η||がηの長さであり、＜τ，χ＞がτとχとの内積であり、η１⊆η２はη１がη２の部分集合であることを表し、Ｂ＝｛ｂ１，…，ｂｎ｝が一次独立なｎ次元ベクトルｂｉからなる基底であり、前記ｎ次元ベクトルｂｉのそれぞれがｎ個の整数要素からなり、Ｌ（Ｂ）が格子｛Σｉ＝１，…，ｎ  ｘｉｂｉ｜ｘｉ∈Ｚ，ｂｉ∈Ｂ｝であり、ｘｉが整数であり、βが前記基底Ｂの前記ｎ次元ベクトルｂ１，…，ｂｎを要素とするｎ行ｎ列の基底行列であり、αがｎ行の整数要素からなる行列であり、ｔ１＝（ｔ１，１，…，ｔ１，ｎ）Ｔがｎ個の整数要素ｔ１，ｉからなる目標ベクトルであり、ｔ２＝（ｔ２，１，…，ｔ２，ｎ）Ｔがｎ個の整数要素ｔ２，ｉからなる目標ベクトルであり、ｔ１（ｄ）が前記目標ベクトルｔ１と前記目標ベクトルｔ１の最近ベクトルｔ１（ｃ）∈Ｌ（Ｂ）との差分ベクトルｔ１（ｄ）＝ｔ１−ｔ１（ｃ）＝（ｔ１，１（ｄ），…，ｔ１，ｎ（ｄ））であり、ｔ２（ｄ）が前記目標ベクトルｔ２と前記目標ベクトルｔ２の最近ベクトルｔ２（ｃ）∈Ｌ（Ｂ）との差分ベクトルｔ２（ｄ）＝ｔ２−ｔ２（ｃ）＝（ｔ２，１（ｄ），…，ｔ２，ｎ（ｄ））であり、
前記第１古典計算部は、前記行列αと前記基底行列βとを行方向に並べた行列β’＝（α  β）の転置行列β’Ｔのエルミート標準形が対角成分１の行列となる前記行列αを選択し、エルミート標準形の行列Ｈ’に対してβ−’β’Ｔ＝Ｈ’を満たすユニモジュラ行列β−’を得、前記行列β’＝（ｂ１’，…，ｂｎ’）Ｔの行ベクトルｂ１’，…，ｂｎ’からなる基底をＢ’とし、前記ユニモジュラ行列β−’＝（ｂ１−’，…，ｂｎ’−’）Ｔの行ベクトルｂ１−’，…，ｂｎ’−’からなる基底をＢ−’とし、前記基底Ｂ’が張る空間ｓｐａｎ（Ｂ’）に属するｎ’個の整数要素ｔ’１，ｉ’からなる目標ベクトルｔ１’＝（ｔ’１，１，…，ｔ’１，ｎ’）Ｔ∈ｓｐａｎ（Ｂ’）およびｎ’個の整数要素ｔ’２，ｉ’からなる目標ベクトルｔ２’＝（ｔ’２，１，…，ｔ’２，ｎ’）Ｔ∈ｓｐａｎ（Ｂ’）を得、
Ｐｒｏｊ（ｔ１’）＝（０，ｔ１）、Ｐｒｏｊ（ｔ２’）＝（０，ｔ２）であり、Ｐｒｏｊ（μ）がμの最初のｎ’−ｎ個の要素が０であるｎ次元ベクトル空間への射影を表し、Ｌ（Ｂ−’）が格子Ｌ（Ｂ−’）＝｛Σｉ’＝１，…，ｎ’  ｘｉ’ｂ−’ｉ’｜ｘｉ’∈Ｚ，ｂ−’ｉ’∈Ｂ−’｝であり、ｘｉ’が整数であり、Ｒ⊆Ｚｎ’が整数要素からなるｎ’次空間に属する部分領域であり、
前記第１量子状態生成部は、
【数２０２】
2020149523.tif 000204
の量子状態からなるレジスタを複数個生成し、
前記第２量子状態生成部は、一部の量子状態｜φ＞０のレジスタに量子操作を行い、前記量子操作が施されたレジスタの量子状態を
【数２０３】
2020149523.tif 000205
に遷移させ、
前記第１スワップテスト部は、量子状態｜φ＞０のレジスタと量子状態｜φ＞ｔ１’のレジスタとの各ペアに対してスワップテストを実行し、前記量子状態｜φ＞０と前記量子状態｜φ＞ｔ１’とのペアに対するスワップテストの結果が受理となるか拒否となるかを判定する、
前記第３量子状態生成部は、
【数２０４】
2020149523.tif 000206
の量子状態からなるレジスタを複数個生成し、
前記第４量子状態生成部は、一部の量子状態｜φ＞０のレジスタに量子操作を行い、前記量子操作が施されたレジスタの量子状態を
【数２０５】
2020149523.tif 000207
に遷移させ、
前記第２スワップテスト部は、量子状態｜φ＞０のレジスタと量子状態｜φ＞ｔ２’ のレジスタとの各ペアに対してスワップテストを実行し、前記量子状態｜φ＞０と前記量子状態｜φ＞ｔ２’とのペアに対するスワップテストの結果が受理となるか拒否となるかを判定し、
前記第２古典計算部は、前記スワップテストの結果を用いて、量子状態｜φ＞０と量子状態｜φ＞ｔ１とのペアに対するスワップテストの結果が受理となる確率ｐ１と、量子状態｜φ＞０と量子状態｜φ＞ｔ２とのペアに対するスワップテストの結果が受理となる確率ｐ２を計算し、ｐ１≧ｐ２の場合に||ｔ１（ｄ）||≦||ｔ２（ｄ）||であることを表す情報を出力し、ｐ１＜ｐ２の場合に||ｔ１（ｄ）||＞||ｔ２（ｄ）||であることを表す情報を出力するか、または、ｐ１＞ｐ２の場合に||ｔ１（ｄ）||＜||ｔ２（ｄ）||であることを表す情報を出力し、ｐ１≦ｐ２の場合に||ｔ１（ｄ）||≧|ｔ２（ｄ）||であることを表す情報を出力する、判定装置。
【請求項６】
計算装置であって、
初期設定部と基底選択部と代表元選択部と子ノード生成部と古典計算部とノード選択部と制御部と第１量子状態生成部と第２量子状態生成部とスワップテスト部とを有し、
ｎ，ｎ’，Ｎ，ν（Ｄ），Ｄが正の整数であり、ｎ’＞ｎであり、ｉ＝１，…，ｎであり、ｉ’＝１，…，ｎ’であり、ｉｍが虚数単位であり、ηＴがηの転置であり、｜Λ｜がΛの要素数であり、||η||がηの長さであり、η１⊆η２はη１がη２の部分集合であることを表し、＜τ，χ＞がτとχとの内積であり、η１⊂η２はη１がη２の真部分集合であることを表し、Ｂ＝｛ｂ１，…，ｂｎ｝が一次独立なｎ次元ベクトルｂｉからなる基底であり、前記ｎ次元ベクトルｂｉのそれぞれがｎ個の整数要素からなり、Ｌ（Ｂ）が格子｛Σｉ＝１，…，ｎ  ｘｉｂｉ｜ｘｉ∈Ｚ，ｂｉ∈Ｂ｝であり、ｘｉが整数であり、Ｒ⊆Ｚｎ’が整数要素からなるｎ’次空間に属する部分領域であり、ｔ＝（ｔ１，…，ｔｎ）Ｔがｎ個の整数要素ｔｉからなる目標ベクトルであり、
前記初期設定部は、組（Ｂ，ｔ）を入力とし、基底Ｂ０と目標ベクトルｔ（０）との組からなるノード（Ｂ０，ｔ（０））＝（Ｂ，ｔ）を設定し、
前記基底選択部は、格子Ｌ（ＢＤ−１）の部分格子Ｌ（ＢＤ）⊂Ｌ（ＢＤ−１）の基底ＢＤを選択し、βＤが基底ＢＤ＝｛ｂＤ，１，…，ｂＤ，ｎ｝のｎ次元ベクトルｂＤ，１，…，ｂＤ，ｎを行ベクトルとするｎ行ｎ列の基底行列であり、αＤがｎ行の整数要素からなる行列であり、
前記代表元選択部は、（ｃＤ，０＋Ｌ（ＢＤ））∪（ｃＤ，１＋Ｌ（ＢＤ））∪・・・∪（ｃＤ，ν（Ｄ）−１＋Ｌ（ＢＤ））＝Ｌ（ＢＤ−１）であり、０以上ν（Ｄ）以下の任意のκ１，κ２について、κ１≠κ２である場合に（ｃＤ，κ１＋Ｌ（ＢＤ））∩（ｃＤ，κ２＋Ｌ（ＢＤ））が空であるとの条件を満たす、代表元ｃＤ，０，ｃＤ，１，・・・，ｃＤ，ν（Ｄ）−１を選択し、前記代表元ｃＤ，０，ｃＤ，１，・・・，ｃＤ，ν（Ｄ）−１のそれぞれが整数要素からなるｎ次元ベクトルであり、
前記子ノード生成部は、ノード（ＢＤ−１，ｔ（Ｄ−１））の子ノードとして、ｋ’＝０，１，…，ν（Ｄ）−１についてノード（ＢＤ，ｔ（Ｄ−１）−ｃＤ，ｋ’）を選択し、
前記古典計算部は、前記行列αＤと前記基底行列βＤとを行方向に並べた行列βＤ’＝（αＤ  βＤ）の転置行列βＤ’Ｔのエルミート標準形が対角成分１の行列となる前記行列αＤを選択し、エルミート標準形の行列Ｈ’に対してβＤ−’βＤ’Ｔ＝Ｈ’を満たすユニモジュラ行列βＤ−’を得、前記行列βＤ’＝（ｂＤ，１’，…，ｂＤ，ｎ’’）Ｔの行ベクトルｂＤ，１’，…，ｂＤ，ｎ’’からなる基底をＢＤ’とし、前記ユニモジュラ行列βＤ−’＝（ｂＤ，１−’，…，ｂＤ，ｎ’−’）Ｔの行ベクトルｂＤ，１−’，…，ｂＤ，ｎ’−’からなる基底をＢＤ−’とし、前記基底ＢＤ’が張る空間ｓｐａｎ（ＢＤ’）に属するｎ’個の整数要素ｔ’Ｄ，ｉ’からなる目標ベクトルｔ（Ｄ）’＝（ｔ’Ｄ，１，…，ｔ’Ｄ，ｎ’）Ｔ∈ｓｐａｎ（ＢＤ’）を得、
Ｐｒｏｊ（ｔ’Ｄ−１，ｋ’）＝（０，ｔ（Ｄ−１）−ｃＤ，ｋ’）であり、Ｐｒｏｊ（μ）がμの最初のｎ’−ｎ個の要素が０であるｎ次元ベクトル空間への射影を表し、Ｌ（Ｂ−’）が格子Ｌ（Ｂ−’）＝｛Σｉ’＝１，…，ｎ’  ｘｉ’ｂ−’ｉ’｜ｘｉ’∈Ｚ，ｂ−’ｉ’∈Ｂ−’｝であり、ｘｉ’が整数であり、Ｒ⊆Ｚｎ’が整数要素からなるｎ’次空間に属する部分領域であり、
前記第１量子状態生成部は、
【数２０６】
2020149523.tif 000208
の量子状態からなるレジスタを複数個生成し、
前記第２量子状態生成部は、一部の量子状態｜φ＞Ｄ，０のレジスタに量子操作を行い、前記量子操作が施されたレジスタの量子状態を
【数２０７】
2020149523.tif 000209
に遷移させ、
前記スワップテスト部は、ｋ’＝０，１，…，ν（Ｄ）−１について、量子状態｜φ＞Ｄ，０のレジスタと量子状態｜φ＞ｔ（Ｄ，ｋ’）のレジスタとの各ペアに対してスワップテストを実行し、前記量子状態｜φ＞０と前記量子状態｜φ＞ｔ（Ｄ，ｋ’）とのペアに対するスワップテストの結果が受理となるか拒否となるかを判定し、
前記ノード選択部は、前記スワップテストの結果を用いて、量子状態｜φ＞Ｄ，０と量子状態｜φ＞ｔ（Ｄ，ｋ’）とのペアに対するスワップテストの結果が受理となる確率ｐＤ，ｋ’を計算し、前記確率ｐＤ，０，…，ｐＤ，ν（Ｄ）−１のうち最も高い確率ｐＤ，ｋｍａｘに対応するノード（ＢＤ，ｔ（Ｄ−１）−ｃＤ，ｋｍａｘ）を選択し、ｋｍａｘ∈｛０，１，…，ν（Ｄ）−１｝であり、
前記制御部は、ｔ（Ｄ−１）−ｃＤ，ｋｍａｘと格子Ｌ（ＢＤ）との間の最短の差分ベクトルｔ（ＢＤ，ｄ）を得、前記差分ベクトルｔ（ＢＤ，ｄ）の長さが基準値よりも小さい場合に前記差分ベクトルｔ（ＢＤ，ｄ）を差分ベクトルｔ（ｄ）として出力し、最近ベクトルｔ（ＢＤ，ｃ）＝ｔ−ｔ（ＢＤ，ｄ）∈Ｌ（ＢＤ）を最近ベクトルｔ（ｃ）として出力し、前記差分ベクトルｔ（ＢＤ，ｄ）の長さが前記基準値以上の場合に、Ｄ＋１を新たなＤとし、さらにｔ（Ｄ）＝ｔ（Ｄ−１）−ｃＤ，ｋｍａｘとして、前記基底選択部と前記代表元選択部と前記子ノード生成部と前記古典計算部と前記第１量子状態生成部と前記第２量子状態生成部と前記スワップテスト部と前記ノード選択部と前記制御部との各処理を再び実行する制御を行う、計算装置。
【請求項７】
基底Ｂを入力として、格子Ｌ（Ｂ）の中で最も原点に近い格子点への最短ベクトルを出力する計算装置であって、
基底生成部と設定部と選択部とを有し、
ｎが正の整数であり、Ｂ＝｛ｂ１，…，ｂｎ｝が一次独立なｎ個のｎ次元ベクトルｂｉからなる基底であり、前記ｎ次元ベクトルｂｉのそれぞれがｎ個の整数要素からなり、Ｌ（Ｂ）が格子｛Σｉ＝１，…，ｎ  ｘｉｂｉ｜ｘｉ∈Ｚ，ｂｉ∈Ｂ｝であり、
前記基底生成部は、すべてのｉ＝１，…，ｎについて、Ｂｉ＝｛ｂ１，…，ｂｉ−１，２ｂｉ，ｂｉ＋１，…，ｂｎ｝に設定し、
前記設定部は、請求項６に記載の前記計算装置の処理をＢ＝Ｂｉかつｔ＝ｂｉとして実行して得られた前記差分ベクトルｔ（ｄ）をｔｉ（ｄ）に設定し、
前記選択部は、前記設定部で得られたｔ１（ｄ），…，ｔｎ（ｄ）の中で最短のものを前記最短ベクトルとして出力する、計算装置。
【請求項８】
ｎ次元ベクトルａｊ，ｇおよび整数Ｎの入力に対して
【数２０８】
2020149523.tif 000210
を満たす（Ｘ１，…，Ｘｍ）Ｔを出力する計算装置であって、
第１古典計算部と第１量子状態生成部と第２量子状態生成部とスワップテスト部と選択部と第２古典計算部とを有し、
ｎ，ｎ’，ｍ，Ｎが正の整数であり、ｎ’＞ｎであり、ｉ＝１，…，ｎであり、ｉ’＝１，…，ｎ’であり、ｊ＝１，…，ｍであり、ｉｍが虚数単位であり、ηＴがηの転置であり、｜Λ｜がΛの要素数であり、＜τ，χ＞がτとχとの内積であり、η１⊆η２はη１がη２の部分集合であることを表し、Ｂ＝｛ｂ１，…，ｂｎ｝が一次独立なｎ次元ベクトルｂｉからなる基底であり、前記ｎ次元ベクトルｂｉのそれぞれがｎ個の整数要素からなり、Ｌ（Ｂ）が格子｛Σｉ＝１，…，ｎ  ｘｉｂｉ｜ｘｉ∈Ｚ，ｂｉ∈Ｂ｝であり、ｘｉが整数であり、Ｒ⊆Ｚｎ’が整数要素からなるｎ’次空間に属する部分領域であり、ａｊがｎ個の整数要素ａ１ｊ，…，ａｎｊからなるｎ次元ベクトルａｊ＝（ａ１ｊ，…，ａｎｊ）Ｔであり、ｇがｎ個の要素ｇ１，…，ｇｎからなるｎ次元ベクトルｇ＝（ｇ１，…，ｇｎ）Ｔであり、ｄがｎ個の要素ｄ１，…，ｄｎからなるｎ次元ベクトルｄ＝（ｄ１，…，ｄｎ）Ｔであり、
Ｘ１，…，ＸｍのそれぞれがＤ＝１，…，ｍの何れかに対応する処理で得られ、深さＤに対応する処理で得られるＸｊがＸｊ（Ｄ）∈｛Ｘ１，…，Ｘｍ｝であり、深さＤに対応する処理で得られるＸｊ（Ｄ）の値がαｊ（Ｄ）であり、深さＤに対応する処理で得られるＸｊに対応する前記ｎ次元ベクトルａｊがａｊ（Ｄ）∈｛ａ１，…，ａｍ｝であり、ＡＤ−１＝（ａｊ（Ｄ）  ａｊ（Ｄ＋１）… ａｊ（ｍ））であり、Ｘ’Ｄ−１＝（Ｘｊ（Ｄ），Ｘｊ（Ｄ＋１），…，Ｘｊ（ｍ））Ｔであり、
【数２０９】
2020149523.tif 000211
であり、
前記第１古典計算部は、深さＤに対応する処理において、｛ａｊ（Ｄ＋１）Ｔ  ａｊ（Ｄ＋２）Ｔ… ａｊ（ｍ）Ｔ  Ｎε１Ｔ…ＮεｎＴ｝で定義される格子のＬＬＬ既約基底ＢＤの基底行列βＤを得、ｎ列の整数要素からなる行列αＤと前記基底行列βＤとを行方向に並べた行列βＤ’＝（αＤ  βＤ）の転置行列βＤ’Ｔのエルミート標準形が対角成分１の行列となる前記行列αＤを選択し、エルミート標準形の行列Ｈ’に対してβＤ−’βＤ’Ｔ＝Ｈ’を満たすユニモジュラ行列βＤ−’を得、前記行列βＤ’＝（ｂＤ，１’，…，ｂＤ，ｎ’’）Ｔの行ベクトルｂＤ，１’，…，ｂＤ，ｎ’’からなる基底をＢＤ’とし、前記ユニモジュラ行列βＤ−’＝（ｂＤ，１−’，…，ｂＤ，ｎ’−’）Ｔの行ベクトルｂＤ，１−’，…，ｂＤ，ｎ’−’からなる基底をＢＤ−’とし、前記基底ＢＤ’が張る空間ｓｐａｎ（ＢＤ’）に属するｎ’個の整数要素ｔ’Ｄ，ｉ’からなる目標ベクトルｔ（Ｄ）’＝（ｔ’Ｄ，１，…，ｔ’Ｄ，ｎ’）Ｔ∈ｓｐａｎ（ＢＤ’）を得、
Ｐｒｏｊ（ｔ’Ｄ−１，ｊ’）＝（０，ｇＤ−１’Ｔ−ｊ’・ａｊ（Ｄ）Ｔ）であり、Ｐｒｏｊ（μ）がμの最初のｎ’−ｎ個の要素が０であるｎ’次元ベクトル空間への射影を表し、Ｌ（Ｂ−’）が格子Ｌ（Ｂ−’）＝｛Σｉ’＝１，…，ｎ’  ｘｉ’ｂ−’ｉ’｜ｘｉ’∈Ｚ，ｂ−’ｉ’∈Ｂ−’｝であり、ｘｉ’が整数であり、Ｒ⊆Ｚｎ’が整数要素からなるｎ’次空間に属する部分領域であり、
前記第１量子状態生成部は、前記深さＤに対応する処理において、
【数２１０】
2020149523.tif 000212
の量子状態からなるレジスタを複数個生成し、
前記第２量子状態生成部は、前記深さＤに対応する処理において、一部の量子状態｜φ＞Ｄ，０のレジスタに量子操作を行い、ｊ’＝０，１，２，…，Ｎ−１について、前記量子操作が施されたレジスタの量子状態を
【数２１１】
2020149523.tif 000213
に遷移させ、
前記スワップテスト部は、前記深さＤに対応する処理において、ｊ’＝０，１，２，…，Ｎ−１について、量子状態｜φ＞Ｄ，０のレジスタと量子状態｜φ＞ｔ（Ｄ，ｊ’）のレジスタとの各ペアに対してスワップテストを実行し、前記量子状態｜φ＞Ｄ，０と前記量子状態｜φ＞ｔ（Ｄ，ｊ’）とのペアに対するスワップテストの結果が受理となるか拒否となるかを判定し、
前記選択部は、前記深さＤに対応する処理において、前記スワップテストの結果を用いて、量子状態｜φ＞Ｄ，０と量子状態｜φ＞ｔ（Ｄ，ｊ’）とのペアに対するスワップテストの結果が受理となる確率ｐＤ，ｊ’を計算し、前記確率ｐＤ，０，ｐＤ，１，…，ｐＤ，Ｎ−１のうち最も高い確率ｐＤ，ｊｍａｘに対応するｊｍａｘ∈｛０，１，２，…，Ｎ−１｝をαｊ（Ｄ）として出力し、さらにｇＤ’＝ｇＤ−１’−αｊ（Ｄ）・ａｊ（Ｄ）を出力し、
前記第２古典計算部は、前記選択部がすべてのＤ＝１，…，ｍについてαｊ（Ｄ）を出力している場合には、αｊ（１），…，αｊ（ｍ）を整列して得られる（Ｘ１，…，Ｘｍ）Ｔを出力し、前記選択部が何れかのＤ＝１，…，ｍについてαｊ（Ｄ）を出力していない場合には、前記第１古典計算部と前記第１量子状態生成部と前記第２量子状態生成部と前記スワップテスト部と前記選択部と前記第２古典計算部の各処理を再び実行させる制御を行う、計算装置。
【請求項９】
順伝播型ニューラルネットワークの教師あり学習を行う学習装置と請求項４または８の計算装置とを有する学習システムであって、
前記学習装置は、初期設定部とＬＷＥ問題処理部と活性化関数演算部とを有し、
ｎ，ｍ，ｓ”，ｄｉが正の整数であり、ｉ＝１，２，３，…，ｎであり、Ｄ”が２以上の整数であり、ａ”ｉ，１，…，ａ”ｉ，ｍおよびｇ”ｉが実数であり、Ψが活性化関数であり、
前記学習装置には、トレーニングデータであるｎ組のｍ次元データセット｛ａ”ｉ，１，…，ａ”ｉ，ｍ｝からなる行列
【数２１２】
2020149523.tif 000214
および各データセット｛ａ”ｉ，１，…，ａ”ｉ，ｍ｝に対するクラスラベルｇ”ｉからなるベクトル
【数２１３】
2020149523.tif 000215
と、順伝播型ニューラルネットワークの深さＤ”とが入力され、
前記初期設定部は、行列Ａｔを用いて
【数２１４】
2020149523.tif 000216
に設定し、
Ｌ”＝１，２，…，Ｄ”−２の順序で、
（ａ）前記ＬＷＥ問題処理部は、第１ＬＷＥ問題
【数２１５】
2020149523.tif 000217
を前記計算装置に送り、
（ｂ）前記計算装置は前記第１ＬＷＥ問題の解Ｘ＝（Ｘ０，Ｘ１，…，Ｘｍ）Ｔの候補値を生成して出力し、
（ｃ）前記ＬＷＥ問題処理部は、長さ||ｄ||が短い順で１番目からｍ番目までである差分ベクトルｄ＝（ｄ１，…，ｄｎ）Ｔに対応するｍ組の前記第１ＬＷＥ問題の解Ｘの候補値を選択し、κ”（１≦κ”≦ｍ）番目の解Ｘの候補値を（Ｗ０，κ”（Ｌ”），Ｗ１，κ”（Ｌ”），…，Ｗｍ，κ”（Ｌ”））Ｔとし、
【数２１６】
2020149523.tif 000218
に設定し、
（ｄ）前記活性化関数演算部は、
【数２１７】
2020149523.tif 000219
を満たすａ”ｊ，κ”（Ｌ”＋１）（１≦ｊ，κ”≦ｍ）を設定し、
Ｌ”＝１，２，…，Ｄ”−２の順序で上記（ａ），（ｂ），（ｃ），（ｄ）の処理が行われた後、
前記ＬＷＥ問題処理部は、第２ＬＷＥ問題
【数２１８】
2020149523.tif 000220
を前記計算装置に送り、
前記計算装置は前記第２ＬＷＥ問題の解Ｘ＝（Ｘ０，Ｘ１，…，Ｘｍ）Ｔを生成して出力し、
前記ＬＷＥ問題処理部は、前記第２ＬＷＥ問題の解Ｘ＝（Ｘ０，Ｘ１，…，Ｘｍ）Ｔを（Ｗ０，１（Ｄ”−１），Ｗ１，１（Ｄ”−１），…，Ｗｍ，１（Ｄ”−１））Ｔとし、
【数２１９】
2020149523.tif 000221
を設定し、
Ｗ（１），…，Ｗ（Ｄ”−１）が前記ニューラルネットワークの重みとして出力される、学習システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は量子コンピュータにより演算を行う量子計算技術に関する。
【背景技術】
【０００２】
量子コンピュータは、一部の応用分野において、現在のコンピュータをはるかに凌駕する計算能力を有するとして期待されている。有名な量子アルゴリズムの一つが、1994年、Shorにより発表された因数分解と離散対数問題を効率的に解く量子アルゴリズムである。この発表が契機となり、量子コンピュータの計算能力を引き出すさまざまな量子アルゴリズムが研究されてきた。特に、古典コンピュータでは効率的に解けない、組み合わせ最適化問題を高速に解く量子アルゴリズムの研究が盛んである。また、最近では、近年の人工知能ブームに後押しされ、量子コンピュータを用いた機械学習（量子機械学習）の研究が注目されている。非特許文献１は、量子機械学習に関する最新の研究成果をレビューした論文である。
【０００３】
非特許文献１のBox 1 Tableには、量子機械学習と古典機械学習との比較がまとめられている。中には、線形サポートベクトルマシンの学習のような、量子コンピュータを用いて効率的に学習できることが示された機械学習システムもある。これらのシステムへの応用で中心的な役割を果たすのは、ＨＨＬ（Harrow-Hassidim-Lloyd）アルゴリズムと呼ばれる量子アルゴリズムである。
ＨＨＬアルゴリズムは、Shorのアルゴリズムでも用いられる位相推定アルゴリズムが基礎となっており、線形システムの効率的な学習を可能にする。しかし、産業上の応用範囲が広く、高速アルゴリズムの開発が社会に与える影響が大きい深層ニューラルネットワークのようなシステムは、一般に非線形であり、ＨＨＬアルゴリズムを用いて効率的に学習することができない。
【０００４】
非特許文献１では、量子コンピュータの非線形システムの学習への応用として、古典ボルツマンマシンや量子ボルツマンマシンの学習が紹介されている。古典ボルツマンマシンの量子コンピュータによる学習は限定的な操作だけで実現できるため、すでに商用化されている量子アニーリングマシン（quantum annealers）を用いて実験が行われている。また、量子ボルツマンマシンの学習は、ハードウェアを用いた実験はまだ準備段階だが、学習にかかる計算量およびデータサンプル数が√Ｎとなることが理論的に証明されている。しかし、ボルツマンマシンは確率リカレントニューラルネットワーク（stochastic recurrent neural network）の一種であり、ニューラルネットワークとしては特殊なシステムである。上記の量子学習アルゴリズムを、深層ニューラルネットワークとして一般的に使用されている順伝播型ニューラルネットワーク（feed-forword neural network）の学習に適用することはできない。
【０００５】
順伝播型ニューラルネットワークにおける各層の重みの学習は、誤差を持つ線型方程式を解く問題に帰着できる。これは、次世代の耐量子公開鍵暗号（post-quantum public-key cryptography）などに用いられる、ＬＷＥ（Learning with Errors）と呼ばれる格子問題と類似の問題である。最短ベクトル問題などに代表される格子問題は、人工知能の他、次世代暗号に利用される基本的な問題である。これを現在のコンピュータ（以下、「古典コンピュータ」とも言う）および量子コンピュータ上で扱う手法が詳しく研究されている。以下、古典コンピュータによる手法、量子コンピュータによる手法についてそれぞれ記す。
【０００６】
格子問題を解くための最も一般的な古典アルゴリズムは格子簡約化アルゴリズムである。格子簡約化アルゴリズムとは、与えられたベクトル空間の基底から、全ての基底が互いに略直交となるような新しい基底を計算する。そのために、全ての基底ベクトルの組み合わせに対して、グラム−シュミットの直交化法（Gram-Schmidt orthogonalization）に似た操作を繰り返し施す。格子簡約化アルゴリズムにより得られる最も短いベクトルの長さは、最悪の場合、求めたい最短ベクトルの長さに対して指数的に大きくなる。
【０００７】
格子問題を解く量子アルゴリズムとしては、例えば、非特許文献３，４の方法が提案されている。非特許文献３では、最近ベクトル問題をもとに、Dihedral Coset Stateと呼ばれる量子状態を作り、量子フーリエ変換を利用して解を得る。非特許文献４では、確率振幅増幅を用いて解を探索する。しかし、いずれの手法も格子問題を効率的に解くことは保証されていない。つまり、格子問題を効率的に解く量子アルゴリズムは見つかっていない。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, Seth Lloyd, Quantum Machine Learning, Nature 549, pp. 195-202. (2017). doi:10.1038/nature23474.
【非特許文献２】Aram W. Harrow, Avinatan Hassidim, Seth Lloyd, Quantum algorithm for solving linear systems of equations, Phys. Rev. Lett. vol. 15, no. 103, pp. 150502 (2009)
【非特許文献３】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).
【発明の概要】
【発明が解決しようとする課題】
【０００９】
本発明は、古典コンピュータと量子コンピュータをハイブリッドに組み合わせ、格子問題を従来よりも高速に解くための要素手法となる距離比較問題の解法の提供を目的とする。例えば、計算処理全体のうち軽いタスクを古典コンピュータが担い、重いタスクを量子コンピュータが担うことにより、ノイズによるデコヒーレンスのため実行時間を長くできない量子コンピュータでも実現可能、かつ、従来よりも短い時間で格子問題の解を求めるために適用できる距離比較問題の解法を提供する。
【課題を解決するための手段】
【００１０】
第１古典計算部は、基底Ｂおよび整数Ｎを用い、双対基底Ｂ−を得て出力する。第１量子状態生成部は、
【数１】
2020149523.tif 000003
の量子状態からなるレジスタを複数個生成する。第２量子状態生成部は、一部の量子状態｜φ＞０のレジスタに量子操作を行い、量子操作が施されたレジスタの量子状態を
【数２】
2020149523.tif 000004
に遷移させる。第１スワップテスト部は、量子状態｜φ＞０のレジスタと各量子状態｜φ＞ｔ１のレジスタとの各ペアに対してスワップテストを実行し、量子状態｜φ＞０と量子状態｜φ＞ｔ１とのペアに対するスワップテストの結果が受理となるか拒否となるかを判定する。第３量子状態生成部は、
【数３】
2020149523.tif 000005
の量子状態からなるレジスタを複数個生成する。第４量子状態生成部は、一部の量子状態｜φ＞０のレジスタに量子操作を行い、量子操作が施されたレジスタの量子状態を
【数４】
2020149523.tif 000006
に遷移させる。第２スワップテスト部は、量子状態｜φ＞０のレジスタと量子状態｜φ＞ｔ２のレジスタとの各ペアに対してスワップテストを実行し、量子状態｜φ＞０と量子状態｜φ＞ｔ２とのペアに対するスワップテストの結果が受理となるか拒否となるかを判定する。第２古典計算部は、スワップテストの結果を用いて、量子状態｜φ＞０と量子状態｜φ＞ｔ１とのペアに対するスワップテストの結果が受理となる確率ｐ１と、量子状態｜φ＞０と量子状態｜φ＞ｔ２とのペアに対するスワップテストの結果が受理となる確率ｐ２を計算し、ｐ１≧ｐ２の場合に||ｔ１（ｄ）||≦||ｔ２（ｄ）||であることを表す情報を出力し、ｐ１＜ｐ２の場合に||ｔ１（ｄ）||＞||ｔ２（ｄ）||であることを表す情報を出力するか、または、ｐ１＞ｐ２の場合に||ｔ１（ｄ）||＜||ｔ２（ｄ）||であることを表す情報を出力し、ｐ１≦ｐ２の場合に||ｔ１（ｄ）||≧|ｔ２（ｄ）||であることを表す情報を出力する。ただし、ｎ，Ｎが正の整数であり、ｉ＝１，…，ｎであり、ｉｍが虚数単位であり、ηＴがηの転置であり、｜Λ｜がΛの要素数であり、||η||がηの長さであり、＜τ，χ＞がτとχとの内積であり、η１⊆η２はη１がη２の部分集合であることを表し、Ｂ＝｛ｂ１，…，ｂｎ｝が一次独立なｎ次元ベクトルｂｉからなる基底であり、ｎ次元ベクトルｂｉのそれぞれがｎ個の整数要素からなり、Ｌ（Ｂ）が格子｛Σｉ＝１，…，ｎ  ｘｉｂｉ｜ｘｉ∈Ｚ，ｂｉ∈Ｂ｝であり、Ｌ（Ｂ−）が基底Ｂと整数Ｎとに対して定義されるＮに関する双対格子であり、ｘｉが整数であり、Ｂ−がＢのＮに関する双対基底であり、Ｒ⊆Ｚｎが整数要素からなるｎ次空間に属する部分領域であり、ｔ１＝（ｔ１，１，…，ｔ１，ｎ）Ｔがｎ個の整数要素ｔ１，ｉからなる目標ベクトルであり、ｔ２＝（ｔ２，１，…，ｔ２，ｎ）Ｔがｎ個の整数要素ｔ２，ｉからなる目標ベクトルであり、ｔ１（ｄ）が目標ベクトルｔ１と目標ベクトルｔ１の最近ベクトルｔ１（ｃ）∈Ｌ（Ｂ）との差分ベクトルｔ１（ｄ）＝ｔ１−ｔ１（ｃ）＝（ｔ１，１（ｄ），…，ｔ１，ｎ（ｄ））であり、ｔ２（ｄ）が目標ベクトルｔ２と目標ベクトルｔ２の最近ベクトルｔ２（ｃ）∈Ｌ（Ｂ）との差分ベクトルｔ２（ｄ）＝ｔ２−ｔ２（ｃ）＝（ｔ２，１（ｄ），…，ｔ２，ｎ（ｄ））である。
【発明の効果】
【００１１】
このように本発明では距離比較問題を解くことができる。これを利用することで格子問題を高速に解くこともできる。
【図面の簡単な説明】
【００１２】
【図１】図１は各実施形態の対応関係を表す概念図である。
【図２】図２は各実施形態の対応関係を表す概念図である。
【図３】図３は実施形態の判定装置の機能構成を例示したブロック図である。
【図４】図４は実施形態の量子計算部の機能構成を例示したブロック図である。
【図５】図５は実施形態のスワップテストを行う量子回路を例示した図である。
【図６】図６は実施形態の具体例を説明するための図である。
【図７】図７は実施形態の計算装置の機能構成を例示したブロック図である。
【図８】図８は実施形態の子ノード生成を説明するための概念図である。
【図９】図９は実施形態の子ノード生成を説明するための概念図である。
【図１０】図１０は実施形態の計算装置の機能構成を例示したブロック図である。
【図１１】図１１は実施形態の計算装置の機能構成を例示したブロック図である。
【図１２】図１２は実施形態の具体例を説明するための図である。
【図１３】図１３は実施形態の具体例を説明するための図である。
【図１４】図１４は各実施形態の対応関係を表す概念図である。
【図１５】図１５は順伝播型ニューラルネットワークの構成を例示した概念図である。
【図１６】図１６は実施形態の学習装置の機能構成を例示したブロック図である。
【発明を実施するための形態】
【００１３】
以下、図面を参照して本発明の実施形態を説明する。
実施形態では、例えば、順伝播型ニューラルネットワークの学習を高速化する、新しい量子計算手法を提供する。順伝播型ニューラルネットワークにおける各層の重みの学習は、誤差を持つ線型方程式を解く問題に帰着できる。これは、次世代の耐量子公開鍵暗号（post-quantum public-key cryptography）などに用いられる、ＬＷＥ（Learning with Errors）と呼ばれる格子問題と類似の問題である。そのため、まず量子計算装置で格子問題を高速に解くために用いる要素手法およびそれを用いた格子問題の解法について説明し（第１実施形態〜第８実施形態）、その量子計算装置を応用して順伝播型ニューラルネットワークの学習を行う学習システムについて説明する（第９実施形態）。順伝播型ニューラルネットワークの学習で一般に用いられるバックプロパゲーションが、学習過程において局所最適解から容易に抜け出せないのに対して、第９実施形態で提案する学習システムは、量子物理の特性を生かして大域的に最適解を探索することにより高速化を実現する。なお、本実施形態で扱う格子問題はＮＰ困難問題であるため、提案手法を、順伝播型ニューラルネットワークの学習だけでなく、組み合わせ最適化問題全般に広く適用することが可能である。
【００１４】
［定義］
実施形態で用いる用語を定義する。
ｎ，ｍ，ｍ’，Ｍ，Ｎ，Ｎ’は正の整数である。ｉ＝１，…，ｎであり、ｊ＝１，…，ｍであり、ｕ＝１，…，ｎである。ｓは整数要素からなるｎ次元ベクトルである。ｒｊｉ（ｃ），ｒｊｉ（ｄ），ｒｊ０，Ｘｊ，ｄｉ，ｇｉ，ｅｊは整数である。Ｌ，γが正の実数である。ａｊはｎ個の整数要素ａ１ｊ，…，ａｎｊからなるｎ次元ベクトルａｊ＝（ａ１ｊ，…，ａｎｊ）Ｔである。ｇはｎ個の要素ｇ１，…，ｇｎからなるｎ次元ベクトルｇ＝（ｇ１，…，ｇｎ）Ｔである。εｕはｕ番目の要素が１で他の要素が０のｎ次元単位ベクトルεｕ＝（０，…，１，０，…，０）Ｔである。
【００１５】
ηＴはηの転置を表す。ηはベクトルまたは行列である。｜Λ｜は集合Λの要素数を表す。ＡＢＳ（μ）はμの絶対値を表す。||η||はηのノルムを表す。例えば、||η||はηのユークリッドノルム（長さ）を表す。ｒｏｕｎｄ（μ）はμに最も近い整数である。すなわち、ｒｏｕｎｄは丸め関数を表す。ｆｌｏｏｒ（μ）はμ以下の最大の整数である。すなわち、ｆｌｏｏｒは床関数を表す。ｃｅｉｌ（μ）はμ以上の最小の整数である。すなわち、ｃｅｉｌは天井関数を表す。λ∈Λはλが集合Λの要素であることを意味する。＜τ，χ＞はベクトルτとベクトルχとの内積を表す。ｄｅｔ（η）はηの行列式を表す。｜δ〉はδに対応する量子状態を示す縦ベクトルを表す。|δ1>|δ2>は|δ1>と|δ2>とのテンソル積を表す。
【００１６】
Ｂ＝｛ｂ１，…，ｂｎ｝は一次独立なｎ個のｎ次元ベクトルｂｉからなる基底である（すなわち、Ｂは一次独立なｎ個のｎ次元ベクトルｂ１，…，ｂｎの集合である）。ｎ次元ベクトルｂｉ＝（ｂｉ１，…，ｂｉｎ）∈Ｚｎのそれぞれはｎ個の整数要素ｂｉ１，…，ｂｉｎ∈Ｚからなる。Ｚは整数の集合を表す。βは基底Ｂのｎ次元ベクトルｂ１，…，ｂｎを要素とするｎ行ｎ列の行列である。このβを、基底Ｂの基底行列と呼ぶ。例えば、βはｎ次元ベクトルｂｉをｉ行目の成分（行ベクトル）とする以下の行列である。
【数５】
2020149523.tif 000007
【００１７】
ｔ＝（ｔ１，…，ｔｎ）Ｔはｎ個の整数要素ｔｉ∈Ｚからなる目標ベクトルである。
【００１８】
Ｌ（Ｂ）は格子｛Σｉ＝１，…，ｎ  ｘｉｂｉ｜ｘｉ∈Ｚ，ｂｉ∈Ｂ｝である。ただし、ｘｉは整数である。すなわち、
【数６】
2020149523.tif 000008
である。
【００１９】
ｎ次元ベクトルｔおよび格子Ｌ（Ｂ）についてτ＋Ｌ（Ｂ）は、格子Ｌ（Ｂ）のすべての格子点をｎ次元ベクトルτ分平行移動させて得られる集合を表す。すなわち、τ＋Ｌ（Ｂ）＝｛τ＋χ｜χ∈Ｌ（Ｂ）｝である。またτ＋Ｌ（Ｂ）＝Ｌ（Ｂ）＋τである。
【００２０】
基底Ｂの部分集合Ｂ’が作る超平面をＨ（Ｂ’）と表記する。超平面Ｈ（Ｂ’）は、部分集合Ｂ’の要素であるベクトルｂｉ’∈Ｂ’によって張られるベクトル空間｛Σｉ＝１，…，ｎ  ζｉｂｉ’｜ζｉ∈Ｒｅ，ｂｉ’∈Ｂ’｝を意味する。ただし、ζｉは実数である。すなわち、
【数７】
2020149523.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).
［参考文献２］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）かを判定する決定問題である。ここで、ｄｉｓｔ（Ｂ，ｔ）とは、最短差分ベクトルｔ（ｄ）の長さ（すなわち||ｔ（ｄ）||）のことである。γが小さくなるほどＧａｐＣＶＰγは難しくなる。
【数８】
2020149523.tif 000010
なら、ＧａｐＣＶＰγはＮＰ困難であることが知られている。
［参考文献４］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）≫
ＬＷＥとは、正の整数ｍ，ｎ，Ｎ、整数要素のｎ×ｍランダム行列Ａ＝（ａｉｊ）（ｉ＝１，…，ｎ、ｊ＝１，…，ｍ）、ｍ次元ランダムベクトルＸ＝（Ｘ１，…，Ｘｍ）Ｔ、および各要素がガウス分布に従う短いベクトルｄ＝（ｄ１，…，ｄｎ）Ｔから
【数９】
2020149523.tif 000011
によりｇ＝（ｇ１，…，ｇｎ）Ｔを定めたとき、（Ａ，ｇ，Ｎ）からＸを求める問題である。ただし、Ｘｊは整数である。ｄが分かれば（３）からＸも計算できるため、ｄを求めてもよい。
【００２９】
一般に、｛ｘ∈Ｚｎ｜＜ｘ，ｂ＞∈Ｚ  ｆｏｒ  ａｌｌ  ｂ∈Ｌ（Ｂ）｝は、格子Ｌ（Ｂ）の「双対格子」と呼ばれる。
［参考文献７］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).
【００３０】
各実施形態で導入する「Ｎに関する双対格子」は、この一般的な「双対格子」とは異なる。Ｎに関する双対格子を導入するのは、格子の重ね合せ状態の全座標軸に対してＮ次元の量子フーリエ変換を実行した結果が、Ｎに関する双対格子の重ね合わせになることによる。Ｎに関する双対格子のＬＬＬ既約基底を「Ｎに関する双対基底」と呼ぶことにする。ここで、ＬＬＬ既約基底の定義については、参考文献１の３３−３５ページを参照のこと。任意の基底にＬＬＬアルゴリズムを適用すると、ＬＬＬ既約基底の定義を満たす基底が得られることが知られている（参考文献１、２．２章）。従って、Ｎに関する双対格子の基底に、ＬＬＬアルゴリズムを適用することにより、Ｎに関する既約基底が得られる。Ｎに関する双対基底はエルミート標準形（Hermite Normal Form）を用いて効率的に計算できる。
【００３１】
≪Ｎに関する双対格子≫
基底Ｂと整数Ｎに対して｛τ∈Ｚｎ｜＜τ，χ＞＝０ ｍｏｄ Ｎ  ｆｏｒ  ａｌｌ  χ∈Ｌ（Ｂ）｝で定義される格子を「Ｎに関する双対格子（法Ｎにおける双対格子）」と呼ぶ。Ｎに関する格子Ｌ（Ｂ）の双対格子のＬＬＬ既約基底をＢ−と書き、双対基底（Ｎに関する双対基底）と呼ぶ。なお、「Ｂ−」の右上添え字の「−」は本来「Ｂ」の真上に記載すべきであるが記載表記の制約上「Ｂ」の右上に表記する場合がある。
【００３２】
各実施形態では、Ｎに関する双対基底の概念を用いて「変形ＬＷＥ」の概念を導入する。後述のように、量子コンピュータを用いて、ＣＶＰやＬＷＥから変形ＬＷＥを効率的に求めることができ、古典コンピュータを用いて、変形ＬＷＥの解の長さがＬ以下かγＬよりも大きいかを効率的に判定することができる。
【００３３】
拡張ユークリッド互除法（Extended Euclidean algorithm）やスミス標準形（Smith Normal Form）やエルミート標準形の詳細は例えば以下の文献に記載されている。
［参考文献８］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).
［参考文献１１］Galbraith, Steven D., Mathematics of Public Key Cryptography, Cambridge University Press, ISBN 978-1107013926 (2012).
エルミート標準形とスミス標準形について説明を加える。
ランダムなｎ次元格子の最短ベクトルの長さは、
【数１０】
2020149523.tif 000012
で近似できることが知られている。ここで、ｄｅｔ（Ｂ）は格子の基底が作る行列の行列式である。この値
【数１１】
2020149523.tif 000013
はGaussian heuristicと呼ばれる（例えば、参考文献１１の３４４ページを参照）。ｍ”とｎ”をｍ”≧ｎ”を満たす正の整数とする。ｍ”×ｎ”整数行列Ａ”＝（ａ”σξ）１≦σ≦ｍ”，１≦ξ≦ｎ”が（行）エルミート標準形（HNFと略される）とは、整数１≦ｒ”≦ｎ”と単調増加関数ｆ：｛１，…，ｎ”−ｒ”｝→｛１，…，ｍ”｝（すなわちｆ（σ＋１）＞ｆ（σ））が存在して以下が成立することである。
１．最後のｒ”行の要素が０である。
２．１≦ξ＜σに対して０≦ａ”ξｆ（σ）＜ａ”σｆ（σ）であり、σ＜ξ≦ｎ”に対してａ”ξｆ（σ）＝０である。したがって、エルミート標準形は次の形で書ける。
【数１２】
2020149523.tif 000014
ｍ”×ｎ”整数行列Ａ”＝（ａ”σξ）１≦σ≦ｍ”，１≦ξ≦ｎ”に対して、唯一のエルミート標準形のｍ”×ｎ”整数行列ＡＨと、ｍ×ｍユニモジュラ（unimodular）行列Ｕ（唯一とは限らない）が存在し、
ＵＡ”＝ＡＨ
が成立する。ここで、ユニモジュラ行列とは、行列式が＋１または−１（ゆえに可逆）な整数要素の正方行列である。Ｕは変換行列（transforming matrix）と呼ばれる。エルミート標準形の整数行列ＡＨと変換行列Ｕは、整数行列Ａ”から効率的に計算できることが知られている。
ｍ”とｎ”がｍ”≧ｎ”を満たす正の整数であるとき、ｍ”×ｎ”整数行列Ａ”＝（ａ”σξ）１≦σ≦ｍ”，１≦ξ≦ｎ”がスミス標準形であるとは、この整数行列Ａ”が以下の形に書けることをいう。
【数１３】
2020149523.tif 000015
ただし、ｋ”はｎ”以下の整数であり、ａ”１１，…，ａ”ｋ”ｋ”はすべての１≦σ”＜ｋ”に対してａ”σσ｜ａ”σ＋１  σ＋１を満足する。またこの行列の空白部分の要素はすべて０である。なお、「γ１｜γ２」はγ２がγ１で割り切れることを表す。例えば、整数行列Ａ”の対角要素が 1, 1, 3, 6, 24, 168, 0, 0, 0ならばすべてのσ=1,2,…,8に対してａ”σσ｜ａ”σ＋１  σ＋１を満たすためＡ”はスミス標準形であるが、整数行列Ａ”の対角要素が1, 1, 3, 6, 24, 128 , 0, 0, 0ならσ=5に対してａ”σσ｜ａ”σ＋１  σ＋１を満たさないためＡ”はスミス標準形ではない。
ｍ”×ｎ”整数行列Ａ”＝（ａ”σξ）１≦σ≦ｍ”，１≦ξ≦ｎ”に対して唯一のスミス標準形ＡＳとユニモジュラ行列Ｕ，Ｖ（唯一とは限らない）が存在して
ＵＡ”Ｖ＝ＡＳ
が成り立つことが知られている。Ｕ，Ｖは変換行列と呼ばれる。エルミート標準形と同様、Ａ”からスミス標準形と変換行列Ｕ，Ｖを効率的に計算できることが知られている。
【００３４】
［第１実施形態］
第１実施形態では、量子コンピュータによる計算（量子計算）と古典コンピュータによる計算（古典計算）とによって距離比較問題を解く（図１および図２）。距離比較問題とは、２つのベクトルのうち、最も近いＬ（Ｂ）中のベクトルまでの距離が近い方を判定（決定）する問題である。
【００３５】
＜構成＞
図３に例示するように、本形態の判定装置７は古典計算部７１，７３（第１，２古典計算部）、量子計算部７２、および制御部７４を有する。図４に例示するように、本形態の量子計算部７２は、量子状態生成部７２ａ，７２ｂ（第１から第４量子状態生成部）、およびスワップテスト部７２ｃ（第１，２スワップテスト部）を有する。判定装置７は、制御部７４の制御のもとで各処理を実行する。古典計算部７１，７３は複数の演算部を有し、量子状態生成部７２ａ，７２ｂおよびスワップテスト部７２ｃは複数の量子計算部を有する（図示せず）。
【００３６】
＜処理＞
本形態の処理を説明する。
本形態の判定装置７は、基底Ｂ、ｎ個の整数要素ｔ１，ｉからなる目標ベクトルｔ１＝（ｔ１，１，…，ｔ１，ｎ）Ｔ、およびｎ個の整数要素ｔ２，ｉからなる目標ベクトルｔ２＝（ｔ２，１，…，ｔ２，ｎ）Ｔを入力とし、以下に説明する古典計算および量子計算を行い、||ｔ１（ｄ）||と||ｔ２（ｄ）||の何れが大きいかを判定する。なお、ｔ１（ｄ）は目標ベクトルｔ１と目標ベクトルｔ１の最近ベクトルｔ１（ｃ）∈Ｌ（Ｂ）との差分ベクトルｔ１（ｄ）＝ｔ１−ｔ１（ｃ）＝（ｔ１，１（ｄ），…，ｔ１，ｎ（ｄ））である。ｔ２（ｄ）は目標ベクトルｔ２と目標ベクトルｔ２の最近ベクトルｔ２（ｃ）∈Ｌ（Ｂ）との差分ベクトルｔ２（ｄ）＝ｔ２−ｔ２（ｃ）＝（ｔ２，１（ｄ），…，ｔ２，ｎ（ｄ））である。ｎ，Ｎは正の整数であり、ｉ＝１，…，ｎであり、ηＴがηの転置であり、||η||がηの長さであり、Ｂ＝｛ｂ１，…，ｂｎ｝は一次独立なｎ次元ベクトルｂｉからなる基底であり、ｎ次元ベクトルｂｉのそれぞれはｎ個の整数要素からなる。βは基底Ｂのｎ次元ベクトルｂ１，…，ｂｎを要素とするｎ行ｎ列の基底行列（ｎ×ｎ行列）である。例えば、βはｎ次元ベクトルｂｉをｉ行目の成分（行ベクトル）とする以下の行列である。
【数１４】
2020149523.tif 000016
【００３７】
≪古典計算部７１の処理≫
判定装置７の古典計算部７１（図３）の演算部は整数Ｎを選択する（ステップＳ７１１）。例えば、古典計算部７１は、基底行列βの逆行列β−１のゼロではない要素の分母の公倍数を整数Ｎに設定する。そのような公倍数は無限に存在するが、任意に選択した数を整数Ｎに固定すればよい。例えば、古典計算部７１は、基底行列βの逆行列β−１のゼロではない要素の分母の最小公倍数を整数Ｎに設定する。
【００３８】
さらに古典計算部７１の演算部は、基底Ｂおよび整数Ｎを用い、ＢのＮに関する双対基底Ｂ−を得て出力する（ステップＳ７１２）。なお、Ｌ（Ｂ）が格子｛Σｉ＝１，…，ｎ  ｘｉｂｉ｜ｘｉ∈Ｚ，ｂｉ∈Ｂ｝であり、ｘｉが整数であり、Ｌ（Ｂ−）が基底Ｂと整数Ｎとに対して定義されるＮに関する双対格子である。また、「Ｂ−」の上付き添え字「−」は「Ｂ」の真上に記載されるべきものであるが、記載表記の制約上、「Ｂ」の右斜め上に記載している。例えば古典計算部７１は、以下のように双対基底Ｂ−を計算する。古典計算部７１は、ＮＩとＢとを行方向に並べて得られるｎ行２ｎ列行列（ｎ×２ｎ行列）であり、（ＮＩ  Ｂ）と表記する。ただし、Ｉはｎ次元単位行列である。古典計算部７１は、この行列（ＮＩ  Ｂ）の転置行列
【数１５】
2020149523.tif 000017
をエルミート分解し、
【数１６】
2020149523.tif 000018
を満たす２ｎ×２ｎユニモジュラ行列Ｕと、エルミート標準形の２ｎ×ｎ行列Ｈを計算する。さらに古典計算部７１は、ユニモジュラ行列Ｕの右下ｎ×ｎ部分行列を
【数１７】
2020149523.tif 000019
と設定する。ただし、ｕｉはｎ次元ベクトル（ｎ次元行ベクトル）である。古典計算部７１は、｛ｕ１，…，ｕｎ｝のＬＬＬ既約基底を計算し、このＬＬＬ既約基底を双対基底Ｂ−＝｛ｂ−１，…，ｂ−ｎ｝として出力する。双対基底Ｂ−のｎ次元ベクトルｂ−１，…，ｂ−ｎを要素とするｎ行ｎ列の基底行列（ｎ×ｎ行列）をβ−と表記する。例えば、β−はｎ次元ベクトルｂ−ｉをｉ行目の成分（行ベクトル）とする以下の行列である。
【数１８】
2020149523.tif 000020
【００３９】
≪量子計算部７２の処理≫
量子計算部７２（図４）は、双対基底Ｂ−および目標ベクトルｔ１，ｔ２を入力とし、ｎ次元空間における適当な領域（整数要素からなるｎ次空間に属する部分領域）Ｒ⊆Ｚｎに対して以下に示す処理を実行し、スワップテストの結果を出力する（ステップＳ７２）。例えば、Ｒ⊂Ｚｎである。η１⊆η２はη１がη２の部分集合であることを表し、η１⊂η２はη１がη２の真部分集合であることを表す。
【００４０】
例えば、以下の領域Ｒ（ΓＢ−）を領域Ｒとすることができる。
【数１９】
2020149523.tif 000021
ただし、Ｒ[０，Γ）は０以上Γ未満の実数を表し、ｘ"j"は実数であり、Γは２以上の整数であり、例えばΓ＝２である。
あるいは、例えば、以下の領域Ｒ（ΓＢ−*）を領域Ｒとしてもよい。
【数２０】
2020149523.tif 000022
ただし、Ｂ−*は双対基底Ｂ−のGram-Schmidt非正規化直交ベクトルｂ−*１，…，ｂ−*ｎからなる基底Ｂ−*＝｛ｂ−*１，…，ｂ−*ｎ｝を表す。ｂ−*１，・・・，ｂ−*ｎはｂ−１，・・・，ｂ−ｎを適当な順序に並べ、Gram-Schmidt直交化法を使って直交化することで得られる。ｂ−*ｉのそれぞれはｎ個の整数要素からなるｎ次元ベクトルである。なお、これらの領域Ｒは本発明を限定するものではない。
【００４１】
量子計算部７２は以下の計算を行う。
（ａ−１）量子計算部７２の量子状態生成部７２ａは、量子状態が
【数２１】
2020149523.tif 000023
である量子状態（通常、複数の量子ビットで構成される）からなるレジスタを複数個生成（準備）する。ただし、｜Λ｜はΛの要素数を表す（ステップＳ７２ａ−１）。
【００４２】
（ｂ−１）量子状態生成部７２ｂは、一部の量子状態｜φ＞０のレジスタに量子操作を行う（ステップＳ７２ｂ−１）。これにより、量子操作が施されたレジスタの量子状態は以下の状態に遷移（変化）する。
【数２２】
2020149523.tif 000024
例えば、量子状態生成部７２ｂは、ステップＳ７２ａ−１で作成された量子状態｜φ＞０のレジスタのうち半分のレジスタに量子操作を行う。ただし、＜τ，χ＞はτとχとの内積であり、ｉｍは虚数単位を表す。ここで用いる量子操作とは、例えば、ｉ＝１，…，ｎについて以下で表される量子回転ゲート、つまりｎ種類の量子回転ゲートである。
【数２３】
2020149523.tif 000025
以上により、量子操作がされないレジスタは量子状態｜φ＞０であり、量子操作がされたレジスタは量子状態｜φ＞ｔ１となる。以下、便宜上、量子状態｜φ＞０のレジスタを第１レジスタ、量子状態｜φ＞ｔ１のレジスタを第２レジスタと呼ぶこととすると、第１レジスタと第２レジスタはそれぞれ複数あってもよく、第１レジスタと第２レジスタの数が同数であることが好ましい。
【００４３】
（ｃ−１）スワップテスト部７２ｃは、量子状態｜φ＞０のレジスタと、量子状態｜φ＞ｔ１のレジスタとをペアとして、各ペアに対してスワップテストを実行し、各ペアに対するスワップテストの結果が受理（０，Ｙｅｓ）となるか拒否（１，Ｎｏ）となるかを判定する。スワップテストは周知のテスト方法であるため詳細な説明を省略するが、例えば、スワップテスト部７２ｃは、図５に例示するようなアダマールゲート７２１ｃ，７２３ｃと制御スワップゲート７２２ｃと観測ゲート７２４ｃとを含む量子回路に対応する量子操作により、スワップテストを実行する。具体的には、スワップテスト部７２ｃは、量子状態｜０＞の量子ビットＩ（１個の量子ビット）にアダマールゲート７２１ｃを適用し、量子状態｜φ＞０の量子ビットＩＩ（通常、複数の量子ビット）と量子状態｜φ＞ｔ＝｜φ＞ｔ１の量子ビットＩＩＩ（通常、複数の量子ビット）と量子ビットＩとに対し、量子ビットＩＩと量子ビットＩＩＩを制御ビットとし、量子ビットＩを目標ビットとした制御スワップゲート７２２ｃを適用し、さらに量子ビットＩにアダマールゲート７２３ｃを適用し、観測ゲート７２４ｃで量子ビットＩを観察することで、受理（０，Ｙｅｓ）または拒否（１，Ｎｏ）との結果を得て出力する。
【００４４】
また、量子計算部７２は以下のように確率ｐ２を計算する。
（ａ−２）量子計算部７２の量子状態生成部７２ａは、量子状態が
【数２４】
2020149523.tif 000026
である量子状態（通常、複数の量子ビットで構成される）からなるレジスタを複数個生成（準備）して出力する（ステップＳ７２ａ−２）。
【００４５】
（ｂ−２）量子状態生成部７２ｂは、一部の量子状態｜φ＞０のレジスタに量子操作を行う（ステップＳ７２ｂ−２）。これにより、量子操作が施されたレジスタの量子状態は以下の状態に遷移（変化）する。
【数２５】
2020149523.tif 000027
例えば、量子状態生成部７２ｂは、量子状態｜φ＞０のレジスタのうち半分のレジスタに量子操作を行うことで量子状態｜φ＞ｔ２のレジスタを得る。ここでの量子操作は、例えば以下で表される量子回転ゲートである。
【数２６】
2020149523.tif 000028
以上により、量子操作がされないレジスタは量子状態｜φ＞０であり、量子操作がされたレジスタは量子状態｜φ＞ｔ２となる。以下、量子状態｜φ＞０のレジスタを第１レジスタ、量子状態｜φ＞ｔ２のレジスタを第３レジスタと呼ぶこととすると、第１レジスタと第３レジスタはそれぞれ複数あってもよく、第１レジスタと第３レジスタの数が同数であることが好ましい。
【００４６】
（ｃ−２）スワップテスト部７２ｃは、量子状態｜φ＞０のレジスタと、量子状態｜φ＞ｔ２のレジスタとをペアとして、各ペアに対してスワップテストを実行し、各ペアに対するスワップテストの結果が受理（０，Ｙｅｓ）となるか拒否（１，Ｎｏ）となるかを判定する。スワップテスト部７２ｃは、複数個のペアの各々に対してスワップテストを行うことで得られた結果を出力する。
【００４７】
≪古典計算部７３の処理≫
古典計算部７３は、量子計算部７２から出力された結果を用いて、量子状態｜φ＞０と量子状態｜φ＞ｔ１とのペアに対するスワップテストの結果が受理となる確率ｐ１と、量子状態｜φ＞０と量子状態｜φ＞ｔ２とのペアに対するスワップテストの結果が受理となる確率ｐ２を計算する。そして、古典計算部７３は、ｐ１≧ｐ２の場合は||ｔ１（ｄ）||≦||ｔ２（ｄ）||であることを表す情報を出力し、ｐ１＜ｐ２の場合は||ｔ１（ｄ）||＞||ｔ２（ｄ）||であることを表す情報を出力する。あるいは、古典計算部７３は、ｐ１＞ｐ２の場合に||ｔ１（ｄ）||＜||ｔ２（ｄ）||であることを表す情報を出力し、ｐ１≦ｐ２の場合に||ｔ１（ｄ）||≧|ｔ２（ｄ）||であることを表す情報を出力する（ステップＳ７３）。
【００４８】
＜領域Ｒの選択とそれに対応する量子状態｜φ＞０の効率的作成方法の例示＞
次に、領域Ｒとそれに対応する量子状態｜φ＞０の効率的作成方法を例示する。
以下では領域Ｒを以下の例１，２のように定義する場合を例示する。
≪領域の例１≫
【数２７】
2020149523.tif 000029
この領域Ｒ（２Ｂ−）は基底Ｂ−が張るｎ次元空間におけるｎ次元平行多面体の内部領域である。
≪領域の例２≫
【数２８】
2020149523.tif 000030
この領域Ｒ（２Ｂ−*）は基底Ｂ−が張るｎ次元空間におけるｎ次元立方体の内部領域である。
以下では、上記の２種類の領域Ｒ＝Ｒ（２Ｂ−），Ｒ（２Ｂ−*）について
【数２９】
2020149523.tif 000031
で定義された量子状態｜φ＞０の効率的な生成方法を例示する。
【００４９】
≪領域の例１における量子状態｜φ＞０の効率的な生成方法の一例≫
古典計算部７１の演算部は、基底行列βの逆行列β−１のゼロではない要素の分母の公倍数を整数Ｎに設定する。例えば、古典計算部７１は、基底行列βの逆行列β−１のゼロではない要素の分母の最小公倍数を整数Ｎに設定する（ステップＳ７１１）。さらに古典計算部７１の演算部は、基底Ｂおよび整数Ｎを用い、前述のようにＢのＮに関する双対基底Ｂ−を得て出力する（ステップＳ７１２）。
【００５０】
量子状態生成部７２ａは、以下の手順により量子状態｜φ＞０を生成する（ステップＳ７２ａ−１）。
１．量子状態生成部７２ａは、Ｎｎ次元を持つ量子状態空間において、以下の量子重ね合わせ状態からなる量子ビット列（第１レジスタ）を準備する。
【数３０】
2020149523.tif 000032
これは、Ｌ（Ｂ−）の格子点を重ね合せ状態で表現したものに相当する。
【００５１】
２．量子状態生成部７２ａは、式（１１）の量子状態の第１レジスタと、新たに用意した１個の初期化された量子状態｜０＞の量子ビット（第２レジスタ）に対し、以下の変換に対応する量子操作を行う。
【数３１】
2020149523.tif 000033
ここで、
【数３２】
2020149523.tif 000034
とは、
【数３３】
2020149523.tif 000035
を満たす唯一の行ベクトルｙのことである。したがって、
【数３４】
2020149523.tif 000036
は基底Ｂ−が張る空間の座標系におけるベクトルｘの終点の座標である。この量子操作により第１レジスタと第２レジスタの量子状態は以下の状態に変換される。
【数３５】
2020149523.tif 000037
【数３６】
2020149523.tif 000038
とすると、式（１２）は
【数３７】
2020149523.tif 000039
と書ける。
【００５２】
３．量子状態生成部７２ａは、式（１３）の量子状態の第１レジスタおよび第２レジスタと、新たに用意したｎ個の初期化された量子ビット列（第３レジスタ）に対し、さらに以下で表される量子操作を行う。
【数３８】
2020149523.tif 000040
これにより、第１レジスタと第２レジスタと第３レジスタの量子状態は以下の状態に変換される。
【数３９】
2020149523.tif 000041
【００５３】
４．量子状態生成部７２ａは、式（１４）の第３レジスタ
【数４０】
2020149523.tif 000042
を観測し、観測値をｚ１，…，ｚｎを得る。観測後の第１レジスタと第２レジスタの量子状態は以下の状態となる。
【数４１】
2020149523.tif 000043
ここで
【数４２】
2020149523.tif 000044
とすると、
【数４３】
2020149523.tif 000045
である。すると、以下の性質が成立する。
R(2B-)∩L (B-)=[0,N)n∩Ln+1(B-)   (15A)
【００５４】
５．量子状態生成部７２ａは、式（１５）の量子状態の第１レジスタと第２レジスタに対して
【数４４】
2020149523.tif 000046
で表される量子操作を行う。これにより、第２レジスタが消去され、第１レジスタは以下の量子状態となる。
【数４５】
2020149523.tif 000047
【００５５】
６．量子状態生成部７２ａは、第１レジスタに対して
【数４６】
2020149523.tif 000048
で表される量子操作を行う。これにより、第１レジスタの量子状態は以下の状態となる。
【数４７】
2020149523.tif 000049
式(15A)の性質により、式（１７）の量子状態は
【数４８】
2020149523.tif 000050
と等しいことが言える。つまり、以上の操作により、量子状態｜φ＞０が得られたことになる。
【００５６】
≪領域の例２における量子状態｜φ＞０の効率的な生成方法の一例≫
領域Ｒ（２Ｂ−*）の定義は、双対基底Ｂ−のｎ次元ベクトルｂ−１，…，ｂ−ｎに対する直交化の順序に依存する。この例では、簡単のため、逆順、すなわちｂ−ｎ，…，ｂ−１の順序でｂ−１，…，ｂ−ｎを直交化したものをｂ−*１，…，ｂ−*ｎとし、量子状態｜φ＞０の生成方法を例示する。ｂ−*１，…，ｂ−*ｎの定義より、
【数４９】
2020149523.tif 000051
【数５０】
2020149523.tif 000052
が成り立つ。ただし、ｊ”＝ｎ−１，ｎ−２，…，１である。また
【数５１】
2020149523.tif 000053
はベクトルｂ−ｊ”のｂ−*ｊ”への射影である。したがって、
【数５２】
2020149523.tif 000054
【数５３】
2020149523.tif 000055
である。ただし、Ｑは有理数の集合を表す。有理数を要素とする上半三角行列Ａ”を以下のように定義する。
【数５４】
2020149523.tif 000056
すると、式（１９）より、
【数５５】
2020149523.tif 000057
が成立する。ｂ−*１，…，ｂ−*ｎは直交ベクトルなので、これらを正規化した要素を行ベクトルとした行列
【数５６】
2020149523.tif 000058
は直交行列である。
【００５７】
古典計算部７１の演算部は、基底行列βの逆行列β−１（基底行列β−の逆行列β−−１でもよい）のゼロではない要素の分母の公倍数を整数Ｎに設定する。例えば、古典計算部７１は、基底行列βの逆行列β−１のゼロではない要素の分母の最小公倍数を整数Ｎに設定する（ステップＳ７１１）。さらに古典計算部７１の演算部は、基底Ｂおよび整数Ｎを用い、前述のようにＢのＮに関する双対基底Ｂ−を得て出力する（ステップＳ７１２）。
【００５８】
量子状態生成部７２ａは、以下の手順により量子状態｜φ＞０を生成する（ステップＳ７２ａ−１）。
１．量子状態生成部７２ａは、Ｎｎ次元を持つ量子状態空間において、以下の量子重ね合わせ状態の量子ビット列（第１レジスタ）を用意する。
【数５７】
2020149523.tif 000059
これは、Ｌ（Ｂ−）の格子点を重ね合せ状態で表現したものに相当する。
【００５９】
２．量子状態生成部７２ａは、式（２３）の量子状態の第１レジスタと、新たに用意した初期化された１個の量子ビット（第２レジスタ）に対し、
【数５８】
2020149523.tif 000060
で表される量子操作を行う。ここで、ｘ＝（ｘ１，…，ｘｎ）のとき
【数５９】
2020149523.tif 000061
であるとする。この量子操作によって第１レジスタと第２レジスタの量子状態は以下の状態となる。
【数６０】
2020149523.tif 000062
ｙ＝（ｙ'ｘ，１，…，ｙ'ｘ，ｎ）＝ｘ・Ｕとすると、この量子状態は
【数６１】
2020149523.tif 000063
と表現できる。式（２４）の量子状態を｜Ψ１＞と表記する。
【００６０】
３．量子状態生成部７２ａは、以下の操作（ａ）（ｂ）をｉ＝１，…，ｎに対して実行し、｜Ψ１＞を｜Ψ２＞，｜Ψ３＞，・・・と順番に量子状態を変換していくことで、最後に量子状態｜Ψｎ＋１＞を得る。ここで｜Ψｉ＞とは、前述の式（１４）の第３レジスタを観測して得られる観測値ｚ１，…，ｚｎを用いれば
【数６２】
2020149523.tif 000064
と表現される量子状態である。ただし、
【数６３】
2020149523.tif 000065
とする。
（ａ）量子状態生成部７２ａは、量子状態｜Ψｉ＞の第１レジスタおよび第２レジスタと、新たに用意した１個の初期化された量子ビット（第３レジスタ）に対し、以下の量子状態に変換する量子操作を行う。
【数６４】
2020149523.tif 000066
（ｂ）量子状態生成部７２ａは、第３レジスタの量子ビットを観測する。観測により得られる観測値をｚｉとし、観測後の第１レジスタおよび第２レジスタからなる量子状態を｜Ψｉ＋１＞とする。
【００６１】
４．量子状態生成部７２ａは、得られた量子状態｜Ψｎ＋１＞に対して
【数６５】
2020149523.tif 000067
で表される量子操作を行う。これにより、第２レジスタが消去され、第１レジスタは以下の量子状態となる。
【数６６】
2020149523.tif 000068
【００６２】
５．量子状態生成部７２ａは、第１レジスタに対して
【数６７】
2020149523.tif 000069
で表される量子操作を実行する。これにより、第１レジスタの量子状態は以下の状態に変化する。
【数６８】
2020149523.tif 000070
式（２７）の量子状態は
【数６９】
2020149523.tif 000071
と等しいため、以上の操作により、量子状態｜φ＞０が得られたことになる。
【００６３】
＜具体例＞
次に、本実施形態の具体例を示す。ここでは、ｎ＝２、Ｂ＝｛（８，４），（６，−５）｝，ｔ１＝（４１，２２），ｔ２＝（２９，５７）に対する確率ｐ１，ｐ２の計算例を示す。ただし、基底行列は
【数７０】
2020149523.tif 000072
であり、最近ベクトルｔ１（ｃ）＝（４０，２０），ｔ２（ｃ）＝（３４，５７）、差分ベクトル（最短差分ベクトル）ｔ１（ｄ）＝（１，２），ｔ２（ｄ）＝（−５，０）である。
【００６４】
≪古典計算部７１の処理≫
古典計算部７１は、基底行列βの逆行列β−１を計算し、
【数７１】
2020149523.tif 000073
を得る。６４の倍数なら整数Ｎとして何を選んでもよいが、最も簡単な例としてＮ＝６４が選択されたとする（ステップＳ７１１）。
【００６５】
さらに古典計算部７１の演算部は、基底Ｂ＝｛（８，４），（６，−５）｝および整数Ｎ＝６４を用い、ＢのＮに関する双対基底Ｂ−を以下のように得て出力する。Ａ’を行列（Ｎ Ｉ Ｂ）Ｔとする。すなわち、
【数７２】
2020149523.tif 000074
である。行列Ａ’のエルミート標準形は上半三角行列
【数７３】
2020149523.tif 000075
であり、ユニモジュラ行列
【数７４】
2020149523.tif 000076
に対してＵ・Ａ’＝Ａ”が成立する。このＵの右下の２×２部分行列の行ベクトルの集合｛（１，１４），（０，６４）｝は、格子Ｌ（Ｂ）のＮに関する双対格子（法Ｎにおける双対格子）の基底である。ＬＬＬアルゴリズムを用いて｛（１，１４），（０，６４）｝のＬＬＬ既約基底を計算すると｛（５，６），（４，−８）｝が得られる。従って、双対基底Ｂ−＝｛（５，６），（４，−８）｝とする。また双対基底Ｂ−の基底ベクトル（５，６），（４，−８）を行ベクトルとする行列を
【数７５】
2020149523.tif 000077
と表現する（ステップＳ７１２）。
【００６６】
≪量子計算部７２の処理≫
量子計算部７２は、双対基底Ｂ−および目標ベクトルｔ１，ｔ２を入力とし、領域Ｒ＝Ｒ（２Ｂ−）に対して以下に示す処理を実行し、０（受理，Ｙｅｓ）が得られる確率ｐ１，ｐ２を計算して出力する（ステップＳ７２）。Ｒ＝Ｒ（２Ｂ−）の場合、以下が成り立つ。
【数７６】
2020149523.tif 000078
【００６７】
量子計算部７２は以下のように確率ｐ１を計算する。
（ａ−１）量子計算部７２の量子状態生成部７２ａは、
【数７７】
2020149523.tif 000079
の量子状態がエンコードされた６個の量子ビットからなるレジスタを２個生成（合計１２個の量子ビットを生成）して出力する。ただし、−８や−２はそれぞれ５６（＝−８ ｍｏｄ ６４），６２（＝−２ ｍｏｄ ６４）としてエンコードされる（ステップＳ７２ａ−１）。
【００６８】
（ｂ−１）量子状態生成部７２ｂは、量子状態が｜φ＞０である１個のレジスタに対し、以下の２種類（格子の次元数ｎと同じ数）の量子回転ゲートを適用する。
【数７８】
2020149523.tif 000080
【数７９】
2020149523.tif 000081
これにより、回転ゲートを適用したレジスタの量子状態は、
【数８０】
2020149523.tif 000082
となる。ただし、ｔ１＝（ｔ１，１，ｔ１，２）＝（４１，２２）である（ステップＳ７２ｂ−１）。
【００６９】
（ｃ−１）スワップテスト部７２ｃは、量子状態｜φ＞０のレジスタと、量子状態｜φ＞ｔ１のレジスタとの各ペアに対してスワップテストを実行し、結果が受理（０，Ｙｅｓ）となるか不受理（１，Ｎｏ）となるかの判定結果を得て出力する（ステップＳ７２ｃ−１）。
【００７０】
量子計算部７２は以下の計算を行う。
（ａ−２）量子計算部７２の量子状態生成部７２ａは、
【数８１】
2020149523.tif 000083
の量子状態がエンコードされた６個の量子ビットであるレジスタを２個生成（合計１２個の量子ビットを生成）して出力する。ただし、−８や−２はそれぞれ５６（＝−８ ｍｏｄ ６４），６２（＝−２ ｍｏｄ ６４）としてエンコードされる（ステップＳ７２ａ−２）。
【００７１】
（ｂ−２）量子状態生成部７２ｂは、量子状態が｜φ＞０である１個のレジスタ（６個の量子ビット）に対し、以下の２種類（次元数分）の量子回転ゲートを適用する。
【数８２】
2020149523.tif 000084
【数８３】
2020149523.tif 000085
これにより、量子回転ゲートを適用したレジスタの量子状態は以下のようになる。
【数８４】
2020149523.tif 000086
ただし、ｔ２＝（ｔ２，１，ｔ２，２）＝（２９，５７）である（ステップＳ７２ｂ−２）。
【００７２】
（ｃ−２）スワップテスト部７２ｃは、レジスタの量子状態｜φ＞０と、レジスタの量子状態｜φ＞ｔ２との各ペアに対してスワップテストを実行し、結果が受理（０，Ｙｅｓ）となるか不受理（１，Ｎｏ）となるかの判定結果を得て出力する（ステップＳ７２ｃ−２）。
【００７３】
≪古典計算部７３の処理≫
古典計算部７３は、スワップテスト部７２ｃの判定結果を用いて、上述の確率ｐ１，ｐ２の値を計算する。目標ベクトルｔ１は（４１，２２）であるため、以下が成り立つ。
【数８５】
2020149523.tif 000087
ただし、前述のようにｉｍは虚数単位である。また、Δ(B-)はL(B-)の単位平行多面体の頂点座標を列挙した行列である。よって以下が成り立つ。
【数８６】
2020149523.tif 000088
目標ベクトルｔ２は（２９，５７）であるため、以下が成り立つ。
【数８７】
2020149523.tif 000089
よって以下が成り立つ。
【数８８】
2020149523.tif 000090
【００７４】
古典計算部７３は、ステップＳ７２ｃ−１およびＳ７２ｃ−２で得られた確率ｐ１，ｐ２を入力としてこれらを比較する。この例ではｐ１＞ｐ２であるため、古典計算部７３は、||ｔ１（ｄ）||＜||ｔ２（ｄ）||であることを表す情報を出力する（ステップＳ７３）。図６に、この具体例での確率ｐ＝ｐ１，ｐ２の密度分布と目標ベクトルｔ１，ｔ２との関係を例示する。格子Ｌ（Ｂ）（Ｂ＝（８，４），（６，−５））の格子点に近いほどｐの値が大きくなる。図６ではｐが大きい領域ほど濃い色を付してある。図６からも||ｔ１（ｄ）||＜||ｔ２（ｄ）||であることが分かる。
【００７５】
［第２実施形態］
第２実施形態では、第１実施形態の手法を用い、与えられたｎ次元の最近ベクトル問題（Ｂ，ｔ）の解を計算する（図１）。すなわち、与えられたｎ次元の最近ベクトル問題（Ｂ，ｔ）に対し、第１実施形態の手法を用い、格子Ｌ（Ｂ）上で最近ベクトルｔ（Ｂ，ｃ）∈Ｌ（Ｂ）を求める。最近ベクトルは、目標ベクトルｔとの差分ベクトルｔ（Ｂ，ｄ）＝ｔ−ｔ（Ｂ，ｃ）が最短となるようなベクトルである。ただし、ｔ＝（ｔ１，…，ｔｎ）Ｔはｎ個の整数要素ｔｉからなる目標ベクトルである。なお、ｔ（Ｂ，ｃ）およびｔ（Ｂ，ｄ）においてＢを表記しなくても混乱が生じない場合には、ｔ（Ｂ，ｃ）およびｔ（Ｂ，ｄ）をそれぞれｔ（ｃ）およびｔ（ｄ）と表記する。また（Ｂ，ｔ）＝（Ｂ０，ｔ（０））である。
【００７６】
本実施形態では、差分ベクトルｔ（ｄ）を計算するために、計算装置が、格子Ｌ（Ｂ）の部分格子の列
Ｌ（Ｂ）＝Ｌ（Ｂ０）⊃Ｌ（Ｂ１）⊃Ｌ（Ｂ２）⊃・・・   (30)
を適当に選び（η２⊃η１はη１がη２の真部分集合であることを表す）、Ｌ（ＢＤ−１）／Ｌ（ＢＤ）（ただし、Ｄは正の整数、すなわちＤ＝１，２，…）におけるcosetの代表元｛ｃＤ，０，ｃＤ，１，・・・，ｃＤ，ν（Ｄ）−１｝の中から、以下を満たすようなα（Ｄ）（ただし、０≦α（Ｄ）＜ν（Ｄ））を探す。
ｔ（Ｂ，ｄ）＝（ｔ（Ｄ−１）−ｃＤ，α（Ｄ））（ＢＤ，ｄ）   (31)
ただしν（Ｄ）は正の整数である。また、上付き添え字「（ＢＤ，ｄ）」に含まれる「ＢＤ」は本来「ＢＤ」と記載すべきであるが、記載表記の制約上、「ＢＤ」と記載している。すなわち、上付き添え字「（ＢＤ，ｄ）」は「（ＢＤ，ｄ）」を表す。ここで、｛ｃＤ，０，ｃＤ，１，・・・，ｃＤ，ν（Ｄ）−１｝がＬ（ＢＤ−１）／Ｌ（ＢＤ）におけるcosetであるとは、｛ｃＤ，０，ｃＤ，１，・・・，ｃＤ，ν（Ｄ）−１｝が以下の条件１，２を満たすことである。
条件１：（ｃＤ，０＋Ｌ（ＢＤ））∪（ｃＤ，１＋Ｌ（ＢＤ））∪・・・∪（ｃＤ，ν（Ｄ）−１＋Ｌ（ＢＤ））＝Ｌ（ＢＤ−１）
条件２：０以上ν（Ｄ）以下の任意のκ１，κ２（０≦∀κ１，κ２≦ν（Ｄ））について、κ１≠κ２である場合に（ｃＤ，κ１＋Ｌ（ＢＤ））∩（ｃＤ，κ２＋Ｌ（ＢＤ））が空である。
探索によって選ばれたα（Ｄ）に対してｔ（Ｄ）＝ｔ（Ｄ−１）−ｃＤ，ｋ’と定義する。ただし、ｋ’＝０，１，…，ν（Ｄ）−１である。すると式（３１）から、差分ベクトルｔ（Ｂ，ｄ）は以下のように表現できる。
ｔ（Ｂ，ｄ）＝ｔ（０）（Ｂ０，ｄ）＝ｔ（１）（Ｂ１，ｄ）＝ｔ（２）（Ｂ２，ｄ）・・・       (32)
すなわち、最近ベクトル問題（Ｂ０，ｔ（０）），（Ｂ１，ｔ（１）），（Ｂ２，ｔ（２）），・・・における最近ベクトルｔ（Ｂ０，ｃ），ｔ（Ｂ１，ｃ），ｔ（Ｂ２，ｃ），・・・が不変になるようにｔ（０），ｔ（１），ｔ（２），・・・の列が選択されている。一般に、格子間の距離が大きくなるほど、最近ベクトルの計算は容易になる。そこで、十分な深さＤまで探索を実行すれば（ＢＤ，ｔ（Ｄ））を古典アルゴリズムによって短時間で解くことができるので、式（３２）を利用して最近ベクトル問題（Ｂ，ｔ）の解を古典コンピュータにより計算すればよい。
【００７７】
本実施形態では、第１実施形態で説明したスワップテストの結果から得られる確率を評価関数とし、探索区間０≦α（Ｄ）＜ν（Ｄ）において、式（３０）を満たすようなα（Ｄ）を探索する。なお、最初に、式（３０）の格子Ｌ（Ｂ）の部分格子の列Ｌ（Ｂ）＝Ｌ（Ｂ０）⊃Ｌ（Ｂ１）⊃Ｌ（Ｂ２）⊃・・・を選択してしまうと、部分格子の列の選択誤りに起因する探索誤りが起こるため、各深さＤにおいて、複数の部分格子Ｌ（ＢＤ）の候補に対して探索を実行し、最もよい部分格子ＢＤとα（Ｄ）を選ぶ。すなわち、式（３０）の格子Ｌ（Ｂ）の部分格子の列は最初に決定するのではなく、各深さＤ＝１，２，・・・の探索処理で逐次決定していく。
【００７８】
＜構成＞
図７に例示するように、本形態の計算装置８は、初期設定部８１、基底選択部８２、代表元選択部８３、子ノード生成部８４、古典計算部８７、ノード選択部８５、制御部８６、量子計算部７２を有する。初期設定部８１、基底選択部８２、代表元選択部８３、子ノード生成部８４、古典計算部７１、ノード選択部８５、および制御部８６は、複数の演算部を有し、量子計算部７２は、複数の量子計算部を有する（図示せず）。
【００７９】
＜処理＞
本形態の処理を説明する。
≪初期設定部８１の処理≫
初期設定部８１は、最近ベクトル問題（Ｂ，ｔ）に対応する組（Ｂ，ｔ）を入力とし、基底Ｂ０と目標ベクトルｔ（０）との組からなるノード（Ｂ０，ｔ（０））＝（Ｂ，ｔ）を設定して出力する。初期設定部８１は、生成したノード（Ｂ０，ｔ（０））に（Ｂ０，ｔ（０））を表すラベルを付与し、それらをメモリ（図示せず）に格納する。またＤ＝１に設定される（ステップＳ８１）。
【００８０】
≪基底選択部８２の処理≫
基底選択部８２は、基底ＢＤ−１を入力とし、格子Ｌ（ＢＤ−１）の部分格子Ｌ（ＢＤ）⊂Ｌ（ＢＤ−１）の基底ＢＤを選択して出力する（ステップＳ８２）。
【００８１】
≪代表元選択部８３の処理≫
代表元選択部８３は、格子Ｌ（ＢＤ），Ｌ（ＢＤ−１）を入力とし、前述の条件１，２を満たすＬ（ＢＤ−１）／Ｌ（ＢＤ）におけるcosetの代表元ｃＤ，０，ｃＤ，１，・・・，ｃＤ，ν（Ｄ）−１を選択して出力する（ステップＳ８３）。なお、各代表元ｃＤ，０，ｃＤ，１，・・・，ｃＤ，ν（Ｄ）−１は整数要素からなるｎ次元ベクトルである。
【００８２】
≪子ノード生成部８４の処理≫
図８および図９に例示するように、子ノード生成部８４は、ＢＤ，ｔ（Ｄ−１），ｃＤ，０，ｃＤ，１，・・・，ｃＤ，ν（Ｄ）−１を入力とし、ノード（ＢＤ−１，ｔ（Ｄ−１））の子ノードとして、ｋ’＝０，１，…，ν（Ｄ）−１についてノード（ＢＤ，ｔ（Ｄ−１）−ｃＤ，ｋ’）を生成する。子ノード生成部８４は、生成したノード（ＢＤ，ｔ（Ｄ−１）−ｃＤ，ｋ’）に（ＢＤ，ｔ（Ｄ−１）−ｃＤ，ｋ’）を表すラベルを付与し、それらをメモリ（図示せず）に格納する（ステップＳ８４）。
【００８３】
≪古典計算部８７の処理≫
古典計算部８７は、基底ＢＤおよび整数Ｎを用い、ＢＤのＮに関する双対基底ＢＤ−を生成して出力する（ステップＳ８７）。
【００８４】
量子状態生成部７２は、第１実施形態の量子計算部７２の処理と同じ処理を行って、スワップテストの結果である観測値を得て出力する。ただし、第１実施形態では基底Ｂとしていたが、本実施形態の量子状態生成部７２では基底Ｂの代わりに基底ＢＤを用いる。
第１実施形態の基底Ｂについて生成した量子状態｜φ＞０、｜φ＞ｔ１の代わりに、本実施形態において基底ＢＤについて第１実施形態の量子状態生成部７２の処理を実行することで得られる量子状態を｜φ＞Ｄ，０、｜φ＞ｔ（Ｄ，ｋ´）と表記すると、各量子状態は以下のように表せる。
【数８９】
2020149523.tif 000091
【数９０】
2020149523.tif 000092
量子計算部７２は、第１実施形態のスワップテスト部７２ｃと同様の処理により、ｋ’＝０，１，…，ν（Ｄ）−１について、量子状態｜φ＞Ｄ，０のレジスタと、量子状態｜φ＞ｔ（Ｄ，ｋ’）のレジスタとの各ペアに対してスワップテストを実行し、量子状態｜φ＞Ｄ，０と量子状態｜φ＞ｔ（Ｄ，ｋ’）とのペアに対するスワップテストの結果が受理となるか不受理となるかの結果を得て出力する（ステップＳ８７２）。
【００８５】
≪ノード選択部８５の処理≫
ノード選択部は、ｋ’＝０，１，…，ν（Ｄ）−１について、量子計算部７２の出力であるスワップテストの結果から量子状態｜φ＞Ｄ，０と量子状態｜φ＞ｔ（Ｄ，ｋ’）とのペアに対するスワップテストの結果が受理となる確率ｐＤ，０，…，ｐＤ，ν（Ｄ）−１を求め、確率ｐＤ，０，…，ｐＤ，ν（Ｄ）−１のうち最も高い確率ｐＤ，ｋｍａｘに対応するノード（ＢＤ，ｔ（Ｄ−１）−ｃＤ，ｋｍａｘ）を選択して出力する。ただし、ｋｍａｘ∈｛０，１，…，ν（Ｄ）−１｝である（ステップＳ８５）。
【００８６】
≪制御部８６の処理≫
制御部８６は、nearest planeアルゴリズムなどの周知の古典アルゴリズムにより、最近ベクトル問題（ＢＤ，ｔ（Ｄ−１）−ｃＤ，ｋｍａｘ）を解き、ｔ（Ｄ−１）−ｃＤ，ｋｍａｘと格子Ｌ（ＢＤ）との間の最短の差分ベクトルｔ（ＢＤ，ｄ）を得る。制御部８６は、差分ベクトルｔ（ＢＤ，ｄ）の長さが基準値よりも小さい場合に、得られた差分ベクトルｔ（ＢＤ，ｄ）が正しいと判断し、そうでない場合に差分ベクトルｔ（ＢＤ，ｄ）が正しくないと判断する。例えば、制御部８６は、差分ベクトルｔ（ＢＤ，ｄ）の長さが、ＢＤのＬＬＬ既約基底の最短ベクトルの２ｎ／２倍より小さいとき、得られた差分ベクトルｔ（ＢＤ，ｄ）が正しいと判断し、そうでない場合に差分ベクトルｔ（ＢＤ，ｄ）が正しくないと判断する。制御部８６は、得られた差分ベクトルｔ（ＢＤ，ｄ）が正しいと判断した場合（差分ベクトルｔ（ＢＤ，ｄ）の長さが基準値よりも小さい場合）、差分ベクトルｔ（ＢＤ，ｄ）を差分ベクトルｔ（ｄ）として出力し、最近ベクトルｔ（ＢＤ，ｃ）＝ｔ−ｔ（ＢＤ，ｄ）∈Ｌ（ＢＤ）を最近ベクトルｔ（ｃ）（すなわち、最近ベクトル問題（Ｂ，ｔ）の解）として出力する（図８：Ｄ＝θ）。一方、制御部８６は、得られた差分ベクトルｔ（ＢＤ，ｄ）が正しくないと判断した場合（差分ベクトルｔ（ＢＤ，ｄ）の長さが基準値以上の場合）に、Ｄ＋１を新たなＤとし、さらにｔ（Ｄ）＝ｔ（Ｄ−１）−ｃＤ，ｋｍａｘとして、基底選択部８２と代表元選択部８３と子ノード生成部８４と古典計算部８７と量子計算部７２とノード選択部８５と制御部８６との各処理（ステップＳ８２，Ｓ８３，Ｓ８４，Ｓ８７，Ｓ８７２，Ｓ８５，Ｓ８６）を再び実行する制御を行う（ステップＳ８６）。すなわち、Ｄ＋１を新たなＤとし、さらにｔ（Ｄ）＝ｔ（Ｄ−１）−ｃＤ，ｋｍａｘとして、ステップＳ８２，Ｓ８３，Ｓ８４，Ｓ８７，Ｓ８７２，Ｓ８５，Ｓ８６の処理が繰り返される。つまり、探索木の探索が継続される。
【００８７】
[ステップＳ８２，Ｓ８３の標準的な方法]
上述したステップＳ８２，Ｓ８３はどのような手法によっても実行されてもよいが、ステップＳ８２，Ｓ８３の標準的な方法として以下を例示できる。ただし、これは本発明を限定するものではない。ＢＤ−１＝｛ｂＤ−１，１，…，ｂＤ−１，ｎ｝とする。ただし、ｉ＝１，…，ｎについてｂＤ−１，ｉは一次独立なｎ次元ベクトルであり、ｎ次元ベクトルｂＤ−１，ｉのそれぞれがｎ個の整数要素からなる。基底選択部８２は、任意な正整数ρ’（ただし、１≦ρ’≦ｎ）と素数ｐ’を選んで、ＢＤ＝｛ｂＤ−１，１，…，ｂＤ−１，ρ’-１，ｐ’ｂＤ−１，ρ’，ｂＤ−１，ρ’＋１，…，ｂＤ−１，ｎ｝とし、代表元選択部８３は、ｃＤ，ｋ’＝κ’ｂＤ−１，ρ’（ただし、κ’＝０，１，…，ｐ’-１）とし、ν（Ｄ）＝ｐ’とする。
【００８８】
［第３実施形態］
本形態では、第２実施形態の処理をサブルーチンとして利用してＳＶＰを解く（図１）。
【００８９】
＜構成＞
図１０に例示するように、本形態の計算装置６は、基底生成部６１、設定部６２、選択部６３、および制御部６５を有する。
【００９０】
＜処理＞
本形態の計算装置６は、基底Ｂを入力として、格子Ｌ（Ｂ）の中で最も原点に近い格子点への最短ベクトルｔ（ｃ）を出力する。
【００９１】
まず、基底生成部６１が、すべてのｉ＝１，…，ｎについて、Ｂｉ＝｛ｂ１，…，ｂｉ−１，２ｂｉ，ｂｉ＋１，…，ｂｎ｝に設定する（ステップＳ６１）。
【００９２】
次に、設定部６２が、ｉ＝１，…，ｎについて、Ｂ＝Ｂｉかつｔ＝ｂｉとし、第２実施形態で説明した計算装置８に処理を依頼する。計算装置８は、Ｂ＝Ｂｉかつｔ＝ｂｉとして第２実施形態で説明した処理を行って差分ベクトルｔ（ｄ）を得て出力する。設定部６２は、Ｂ＝Ｂｉおよびｔ＝ｂｉ対して得られた当該差分ベクトルｔ（ｄ）をｔｉ（ｄ）に設定する。これにより、設定部６２はｔ１（ｄ），…，ｔｎ（ｄ）を得る（ステップＳ６２）。
【００９３】
選択部６３は、設定部６２で得られたｔ１（ｄ），…，ｔｎ（ｄ）を入力とし、ｔ１（ｄ），…，ｔｎ（ｄ）の中で最短のもの（長さが最も短いベクトル）を最短ベクトルｔ（ｃ）として出力する（ステップＳ６３）。
【００９４】
［第４実施形態］
本形態の計算装置は、第１実施形態の手法を利用し、ｎ次元ベクトルａｊ，ｇおよびＮの入力に対して
【数９１】
2020149523.tif 000093
を満たす（Ｘ１，…，Ｘｍ）Ｔを得て出力する（図２）。ｎ，ｍ，Ｎは正の整数である。例えば、ｎ，ｍはｍ＜ｎを満たし、Ｎは素数である（なお、本発明のアルゴリズムはＮが素数でなくても適用可能である。すなわちＮが合成数でもよい）。ａｊはｎ個の整数要素ａ１ｊ，…，ａｎｊからなるｎ次元ベクトルａｊ＝（ａ１ｊ，…，ａｎｊ）Ｔである。ｊ＝１，…，ｍである。例えば、ａ１ｊ，…，ａｎｊはＮ未満の非負整数である。（Ｘ１，…，Ｘｍ）Ｔは整数要素Ｘ１，…，Ｘｍからなるｍ次元ベクトルである。例えば、Ｘ１，…，ＸｍはＮ未満の非負整数である。ｇはｎ個の要素ｇ１，…，ｇｎからなるｎ次元ベクトルｇ＝（ｇ１，…，ｇｎ）Ｔである。例えば、ｇ１，…，ｇｎはＮ未満の非負整数である。ｄはｎ個の要素ｄ１，…，ｄｎからなるｎ次元ベクトルｄ＝（ｄ１，…，ｄｎ）Ｔである。例えば、ｄ１，…，ｄｎはＮ未満の非負整数である。
【数９２】
2020149523.tif 000094
【数９３】
2020149523.tif 000095
【数９４】
2020149523.tif 000096
【数９５】
2020149523.tif 000097
と置くと、式（33)は以下のように表現できる。
ｇ＝ＡＸ＋ｄ  ｍｏｄ  Ｎ    (34)
ここでａｊ＝（ａ１ｊ，…，ａｎｊ）Ｔであるため、Ａは以下のように表現できる。
Ａ＝（ａ１，ａ２，…，ａｍ）
【００９５】
本実施形態では、第２実施形態と同様な探索木の探索によって（Ｘ１，…，Ｘｍ）Ｔを計算していく。このとき、Ｘ＝（Ｘ１，…，Ｘｍ）Ｔの変数（要素）Ｘ１，…，Ｘｍそれぞれが探索木の深さＤと一対一に対応する。従って、探索木の深さはＸの変数の数ｍと一致する。すなわち、Ｘ１，…，Ｘｍのそれぞれは、探索木の何れかの深さＤ＝１，…，ｍでの探索（Ｄ＝１，…，ｍの何れかに対応する処理）で得られる。探索木の深さＤ（＝１，２，…，ｍ）において決定される変数Ｘｊ（深さＤに対応する処理で得られるＸｊ）をＸｊ（Ｄ）∈｛Ｘ１，…，Ｘｍ｝と記述する。また、深さＤの探索で得られる（深さＤに対応する処理で得られる）Ｘｊ（Ｄ）の値がαｊ（Ｄ）であり、このＸｊ（Ｄ）に対応するｎ次元ベクトルａｊがａｊ（Ｄ）∈｛ａ１，…，ａｍ｝である。なぜなら、式(34)よりｇ＝Ｘ１ａ１＋…＋Ｘｊ（Ｄ）ａｊ（Ｄ）＋…＋Ｘｍａｍ＋ｄ  ｍｏｄ  Ｎとなるからである。例えば、各Ｄ＝１，…，ｍに対応するＸｊ（Ｄ）およびａｊ（Ｄ）は予め定められている。例えば、Ｘｊ（Ｄ）＝ＸＤであり、ａｊ（Ｄ）＝ａＤである。各変数Ｘｊ（Ｄ）の値は０，１，…，Ｎ−１のどれかなので、探索木の枝の数は深さによらずＮとなる。本形態の場合、Ｌ（ＢＤ−１）／Ｌ（ＢＤ）におけるcosetの代表元はｃＤ，０，ｃＤ，１，…，ｃＤ，Ｎ−１となり、それらはそれぞれ０，Ｘｊ（Ｄ），２Ｘｊ（Ｄ），…，（Ｎ−１）Ｘｊ（Ｄ）と対応する。従って、ｃＤ，ｊ’＝ｊ’・Ｘｊ（Ｄ）である（ただし、ｊ’＝０，１，２…，Ｎ−１）。なお、ＢＤおよびｃＤ，ｊ’は、例えば第２実施形態で例示した「ステップＳ８２，Ｓ８３の標準的な方法」によって計算することができるが、Ｎが素数の場合、ステップＳ８２，Ｓ８３の標準的な方法で素数ｐ’を選択しようとするとｐ’＝Ｎとせざるを得ない。
【００９６】
式（34）において、Ａ，Ｘの要素の順序を入れ替えた式は以下のようになる。
【数９６】
2020149523.tif 000098
深さＤ−１まで探索を終えると、変数Ｘｊ（１），Ｘｊ（２），…，Ｘｊ（Ｄ−１）の値が決まる。深さＤの探索で得られるＸｊ（Ｄ）の値（深さＤに対応する処理で得られるＸｊ（Ｄ）の値）をαｊ（Ｄ）とすると、式（35)から以下の関係が得られる。
【数９７】
2020149523.tif 000099
なお、深さＤで探索を行う変数Ｘｊ（Ｄ）は未探索の変数のいずれであってもよい。ここで、Ｄ＝２，…，ｍについて
ＡＤ−１＝（ａｊ（Ｄ）ａｊ（Ｄ＋１） … ａｊ（ｍ））
Ｘ’Ｄ−１＝（Ｘｊ（Ｄ），Ｘｊ（Ｄ＋１），…，Ｘｊ（ｍ））Ｔ
【数９８】
2020149523.tif 000100
とおく。またＤ＝１については、Ａ０＝Ａであり、Ｘ’０＝Ｘであり、ｇ０’＝ｇである。探索木の深さＤ＝１，２，…，ｍに対して、条件
ｇＤ−１’＝ＡＤ−１Ｘ’Ｄ−１＋ｄ ｍｏｄ Ｎ   (36)
の下、（ＡＤ−１，ｇＤ−１’，Ｎ）からＸｊ（Ｄ）を求めていけば、最終的に（Ｘ１，…，Ｘｍ）Ｔの値を得ることができる。
【００９７】
＜構成＞
図１１に例示するように、本形態の計算装置１０は、初期設定部１００、古典計算部１０１，１０３（第１，２古典計算部）、選択部１０２、量子計算部７２を有する。古典計算部１０１，１０３は複数の演算部を有し、量子計算部７２は複数の量子計算部を有する（図示せず）。
【００９８】
＜処理＞
本形態の処理を説明する。
≪初期設定部１００≫
初期設定部１００は、Ｄ＝１、Ａ０＝Ａ、Ｘ’０＝Ｘ、ｇ０’＝ｇに初期設定する（ステップＳ１００）。その後、深さＤでの探索（深さＤに対応する処理）として以下の各処理が実行される。
【００９９】
≪古典計算部１０１の処理≫
ｊ’＝０，１，２…，Ｎ−１のそれぞれに対し、式（36)は以下のように表現できる。
ｇＤ−１’−ｊ’・ａｊ（Ｄ）＝ＡＤＸ’Ｄ＋ｄ ｍｏｄ Ｎ   (37)
式（37）を転置すると、以下の式(38)が得られる。
ｇＤ−１’Ｔ−ｊ’・ａｊ（Ｄ）Ｔ＝Ｘ’ＤＴＡＤＴ＋ｄＴｍｏｄ Ｎ   (38)
ＡＤの列ベクトルはａｊ（Ｄ＋１），ａｊ（Ｄ＋２），…，ａｊ（ｍ）であるため、ａｊ（Ｄ＋１）Ｔ，ａｊ（Ｄ＋２）Ｔ，… ａｊ（ｍ）ＴはＡＤの行ベクトルである。
【０１００】
古典計算部１０１の演算部は、ＡＤ，Ｎ，ε１，…，εｎを入力とし、ＡＤＴにＮεｉＴ（ただし、ｉ＝１，…，ｎ）を加えた行ベクトルの集合｛ａｊ（Ｄ＋１）Ｔａｊ（Ｄ＋２）Ｔ … ａｊ（ｍ）Ｔ Ｎε１Ｔ…ＮεｎＴ｝で定義される格子のＬＬＬ既約基底ＢＤを計算して出力する。各ｊ’＝０，１，２…，Ｎ−１とｄＴに対して、式（38)の解Ｘ’ＤＴの存在と、
ｇＤ−１’Ｔ−ｊ’・ａｊ（Ｄ）Ｔ＝ｕ（Ｄ）ＢＤ＋ｄＴ   (39)
を満たす解ｕ（Ｄ）∈Ｚｎの存在とは等価である。なお、ｕ（Ｄ）は整数要素からなるｎ次元ベクトルである（ステップＳ１０１１）。
【０１０１】
古典計算部１０１の演算部は、ステップＳ１０１１で得たＬＬＬ既約基底ＢＤのＮに関する双対基底ＢＤ−を得て出力する（ステップＳ１０１２）。
【０１０２】
量子計算部７２は、以下のように、深さＤに対応する各ノード（ＢＤ，ｇＤ−１’Ｔ−ｊ’・ａｊ（Ｄ）Ｔ）について、各ｊ’＝０，１，２…，Ｎ−１に対応するスワップテストの判定結果を求める。
【０１０３】
量子計算部７２は、第２実施形態の量子計算部７２と同じ処理を行い、量子状態｜φ＞Ｄ，０と｜φ＞ｔ（Ｄ，ｊ´）を生成し、これらの量子状態にスワップテストを行って、スワップテストの判定結果を得て出力する（ステップＳ１０７２）。ただし、第２実施形態のｋ'＝０，１，…，ν（Ｄ）−１の代わりに、本実施形態ではｊ’＝０，１，２，…，Ｎ−１を用いる。各量子状態は以下のように表せる。
【数９９】
2020149523.tif 000101
【数１００】
2020149523.tif 000102
量子状態｜φ＞ｔ（Ｄ，ｊ´）を生成するために用いる量子回転ゲートの例を以下に示す。
【数１０１】
2020149523.tif 000103
量子計算部７２は、ｊ’＝０，１，２，…，Ｎ−１について、ステップＳ１０７２ａで得られた量子状態｜φ＞Ｄ，０のレジスタと、ステップＳ１０７２ｂで得られた量子状態｜φ＞ｔ（Ｄ，ｊ’）のレジスタとの各ペアに対してスワップテストを実行し、量子状態｜φ＞Ｄ，０と量子状態｜φ＞ｔ（Ｄ，ｊ’）とのペアに対するスワップテストの結果が受理となるか不受理となるかの結果を得て出力する。
【０１０４】
≪選択部１０２の処理≫
選択部１０２は、ｊ’＝０，１，２，…，Ｎ−１について、量子計算部７２から出力されたスワップテストの判定結果に基づいて、量子状態｜φ＞Ｄ，０と量子状態｜φ＞ｔ（Ｄ，ｊ’）とのペアに対するスワップテストの結果が受理となる確率ｐＤ，０，ｐＤ，１，…，ｐＤ，Ｎ−１を求め、この中から最も高い確率ｐＤ，ｊｍａｘに対応するｊｍａｘ∈｛０，１，２，…，Ｎ−１｝をαｊ（Ｄ）として出力する。すなわち、ｐＤ，ｊｍａｘ≧ｐＤ，０，ｐＤ，１，ｐＤ，ｊｍａｘ−１，ｐＤ，ｊｍａｘ＋１，…，ｐＤ，Ｎ−１であり、αｊ（Ｄ）＝ｊｍａｘである。また選択部１０２は、ｇＤ’＝ｇＤ−１’−αｊ（Ｄ）・ａｊ（Ｄ）を計算して出力する（ステップＳ１０２）。ここで得られる値αｊ（Ｄ）が深さＤでのＸｊ（Ｄ）の値となる。
【０１０５】
≪古典計算部１０３の処理≫
選択部１０２ｇがすべてのＤ＝１，…，ｍについてαｊ（Ｄ）を出力している場合、古典計算部１０３は、αｊ（１），…，αｊ（ｍ）を整列して得られる（Ｘ１，…，Ｘｍ）Ｔの解（α１，…，αｍ）Ｔを出力する。一方、選択部１０２ｇが何れかのＤ＝１，…，ｍについてαｊ（Ｄ）を出力していない場合、古典計算部１０３は、Ｄ＋１を新たなＤとし、古典計算部１０１と量子計算部７２と選択部１０２と古典計算部１０３の各処理（ステップＳ１０１１，Ｓ１０１２，Ｓ１０７２，Ｓ１０２，Ｓ１０３）を再び実行させる制御を行う（ステップＳ１０３）。
【０１０６】
＜具体例＞
次に、本実施形態の具体例を示す。ここではＬＷＥの例として、以下の場合を例示する。ｍ＝３，ｎ＝９（＝ｍ２），Ｎ＝１１（ｎよりも大きな最小の素数），
【数１０２】
2020149523.tif 000104
【数１０３】
2020149523.tif 000105
【数１０４】
2020149523.tif 000106
【数１０５】
2020149523.tif 000107
ここで、Ａ，Ｘはランダムな要素を持つ行列とベクトルであり、ｄは平均０分散１の正規分布に従うランダムな要素を持つベクトルであり、ｇはＡＸ＋ｄ  ｍｏｄ  Ｎを計算して得たベクトルである。ＬＷＥでは、Ｘとｄが未知であり、（Ａ，ｇ，Ｎ）が与えられたとき、Ｘを求める。以下、Ｘの最初の変数Ｘ１をＸｊ（１）とし、深さＤ＝１で探索において、その値αｊ（１）＝１０を計算する手順を例示する。変数Ｘ２，変数Ｘ３についても、深さＤ＝２，３の探索で同様に求めることができるため、変数Ｘ２，変数Ｘ３の計算手順については省略する。
【０１０７】
≪初期設定部１００≫
初期設定部１００は、Ｄ＝１、Ａ０＝Ａ、Ｘ’０＝Ｘ、ｇ０’＝ｇに初期設定する（ステップＳ１００）。
【０１０８】
≪古典計算部１０１の処理≫
Ａから深さＤで求めたい変数番号の列を除いたｎ×（ｍ−１）行列をRest(Ａ)と表現する。この例の場合、Ｘの一番目の変数Ｘ１の値を求めたいので、Rest(Ａ)はＡから一列目を除いた９×２行列である。古典計算部１０１の演算部は、（ｎ＋ｍ−１）×ｎ行列
【数１０６】
2020149523.tif 000108
が表す基底で定義される格子のＬＬＬ既約基底Ｂ１を計算して出力する。ｍ＝３，ｎ＝９の場合、この例のＢ１を構成するｎ次元ベクトルｂ１，…，ｂｎを要素とする９行９列の基底行列β１は以下のようになる（ステップＳ１０１１）。
【数１０７】
2020149523.tif 000109
【０１０９】
古典計算部１０１の演算部は、Ｂ１のＮに関する双対基底Ｂ１−を得て出力する（ステップＳ１０１２）。ｎ＝９の場合、この例のＢ１−を構成するｎ次元ベクトルｂ１−，…，ｂ９−を要素とする９行９列の基底行列β１−は以下のようになる。
【数１０８】
2020149523.tif 000110
【０１１０】
≪量子計算部７２の処理≫
この例では量子計算部７２が、領域Ｒとして前述のＲ（２Ｂ−）を選択する。領域Ｒを前述のＲ（２Ｂ−）とすると以下が成り立つ。
【数１０９】
2020149523.tif 000111
量子計算部７２は、量子状態｜φ＞１，０がｎ×ｃｅｉｌ（ｌｏｇ２（Ｎ＋１)）個の量子ビットの量子重ね合わせ状態からなる第１レジスタを複数個生成して出力する。この第１レジスタは、格子Ｌ（Ｂ−）の格子点を頂点とした単位平行多面体の各頂点の値のエンコード値の量子重ね合せ状態に相当する。例えば、ｎ＝９の場合、量子状態生成部７２ａは、以下の量子状態｜φ＞１，０の第１レジスタを複数個生成する。
【数１１０】
2020149523.tif 000112
【０１１１】
量子計算部７２は、量子状態｜φ＞１，０の複数のレジスタを２つのグループに分け、片方のグループレジスタに量子回転ゲートを適用する。これにより、以下の量子状態からなるレジスタが得られる。
【数１１１】
2020149523.tif 000113
ここで、この例の目標ベクトルｇ０’Ｔ−ｊ’・ａｊ（１）Ｔは以下の１１種類である。
ｇ０’Ｔ−ｊ’・ａｊ（１）Ｔ＝（１，８−ｊ’，６−３ｊ’，７−ｊ’，４−９ｊ’，５，８−７ｊ’，１０−４ｊ’，６）  ｍｏｄ  １１
【０１１２】
そして、量子計算部７２は、ｊ’＝０，１，２…，１０について、量子状態｜φ＞１，０のレジスタと、量子状態｜φ＞ｔ（１，ｊ’）のレジスタとの各ペアに対してスワップテストを実行し、量子状態｜φ＞１，０と量子状態｜φ＞ｔ（１，ｊ’）とのペアに対するスワップテストの結果を得て出力する。
【０１１３】
≪選択部１０２の処理≫
選択部１０２は、量子計算部７２で得たスワップテストの結果から、スワップテストが受理となる確率ｐ１，ｊ’を計算する。例えば、量子計算部７２において各ｊ’＝０，１，２…，１０について複数回（例えば、１００回）のスワップテストを実行し、受理となった割合を各ｊ’における確率ｐ１，ｊ’として計算する。確率ｐ１，ｊ’を理論的に計算すると以下のようになる。
p1,0=0.500002
p1,1=0.500001
p1,2=0.500000
p1,3=0.500000
p1,4=0.500002
p1,5=0.500132
p1,6=0.500093
p1,7=0.500000
p1,8=0.504587
p1,9=0.500001
p1,10=0.665613
次に、選択部１０２は、確率ｐ１，０，ｐ１，１，…，ｐ１，Ｎ−１のうち最も高い確率ｐ１，１０に対応する１０をαｊ（１）として出力する。式（４１）のようにＸ１＝１０であり、正しい答えαｊ（１）＝１０を算出することができた。
【０１１４】
［第５実施形態］
第５実施形態でも、量子計算と古典計算とによって距離比較問題を解く（図１および図２）。第１実施形態では、距離比較問題の対象となる格子Ｌ（Ｂ）と同じ次元の双対格子Ｌ（Ｂ−）を用いた。本形態では、距離比較問題の対象となる格子Ｌ（Ｂ）をより大きな次元ｎ’の空間に埋め込んで得られる格子を用いることで精度を高める。
【０１１５】
＜構成＞
図３に例示するように、本形態の判定装置１１は古典計算部１１１，７３（第１，２古典計算部）、量子計算部１１２、および制御部７４を有する。図４に例示するように、本形態の量子計算部１１２は、量子状態生成部１１２ａ，１１２ｂ（第１から第４量子状態生成部）、およびスワップテスト部７２ｃ（第１，２スワップテスト部）を有する。判定装置１１は、制御部７４の制御のもとで各処理を実行する。古典計算部１１１，７３は複数の演算部を有し、量子状態生成部１１２ａ，１１２ｂおよびスワップテスト部７２ｃは複数の量子計算部を有する（図示せず）。
【０１１６】
＜処理＞
本形態の処理を説明する。本形態の判定装置１１は、基底Ｂ、ｎ個の整数要素ｔ１，ｉからなる目標ベクトルｔ１＝（ｔ１，１，…，ｔ１，ｎ）Ｔ、およびｎ個の整数要素ｔ２，ｉからなる目標ベクトルｔ２＝（ｔ２，１，…，ｔ２，ｎ）Ｔを入力とし、以下に説明する古典計算および量子計算を行い、||ｔ１（ｄ）||と||ｔ２（ｄ）||の何れが大きいかを判定する。
【０１１７】
≪古典計算部１１１の処理≫
判定装置１１の古典計算部１１１（図３）の演算部は、基底Ｂを入力とし、行列αと基底行列βとを行方向に並べた行列β’＝（α  β）の転置行列β’Ｔのエルミート標準形が対角成分１の行列となる行列αを選択し、行列β’を得て出力する。βは基底Ｂのｎ次元ベクトルｂ１，…，ｂｎを要素とするｎ行ｎ列の基底行列であり、例えば、ｎ次元ベクトルｂ１，…，ｂｎを行ベクトルとした行列である。αはｎ行の整数要素からなる行列である。行列αの一例はｎ×ｎ単位行列であるが、本発明はこれに限定されない。一般に、ランダムな０または１の要素からなるｎ×ｎ行列をαとすれば、行列β’＝（α  β）の転置行列β’Ｔのエルミート標準形は対角成分１の行列（対角成分だけを持つ行列）となり、上記条件を満たす。また、行列αはｎ×ｎ行列である必要はなく、ｎよりも列数の小さいｎ行の行列や、ｎよりも列数がずっと大きな（例えば、列数がｎ２よりも大きな）ｎ行の行列であってもよい。行列β’＝（ｂ１’，…，ｂｎ’’）Ｔの行ベクトルｂ１’，…，ｂｎ’からなる基底をＢ’と表現する。行ベクトルｂ１’，…，ｂｎ’は一次独立であり、ｉ＝１，…，ｎについてｂｉ’は整数要素からなるｎ’次元ベクトルである。ただし、ｎ’はｎよりも大きな正整数である（ステップＳ１１１−１）。
【０１１８】
古典計算部１１１の演算部は、行列β’を入力とし、行列β’Ｔをエルミート分解し、β−’β’Ｔ＝Ｈ’を満たすユニモジュラ行列β−’とエルミート標準形の行列Ｈ’を得る。ユニモジュラ行列β−’＝（ｂ１−’，…，ｂｎ’−’）Ｔの行ベクトルｂ１−’，…，ｂｎ’−’からなる基底をＢ−’として出力する。行ベクトルｂ１−’，…，ｂｎ’−’は一次独立であり、ｉ’＝１，…，ｎ’についてｂｉ’−’は整数要素からなるｎ’次元ベクトルである。ｎ’がβ−’の行数である。なお、Ｂ−’の上付き添え字の「−」は本来「Ｂ」の真上に記載すべきであるが、記載表記の制約上、「Ｂ」の右上に表記する場合がある。「ｂｉ’−’」の上付き添え字の「−」は本来「ｂ」の真上に記載すべきであるが、記載表記の制約上、「ｂ」の右上に表記する場合がある（ステップＳ１１１−２）。
【０１１９】
古典計算部１１１の演算部は、基底Ｂ’および目標ベクトルｔ１＝（ｔ１，１，…，ｔ１，ｎ）Ｔ，ｔ２＝（ｔ２，１，…，ｔ２，ｎ）Ｔを入力とし、基底Ｂ’が張る空間ｓｐａｎ（Ｂ’）に属するｎ’個の整数要素ｔ’１，ｉ’からなる目標ベクトルｔ１’＝（ｔ’１，１，…，ｔ’１，ｎ’）Ｔ∈ｓｐａｎ（Ｂ’）およびｎ’個の整数要素ｔ’２，ｉ’からなる目標ベクトルｔ２’＝（ｔ’２，１，…，ｔ’２，ｎ’）Ｔ∈ｓｐａｎ（Ｂ’）を得て出力する。ただし、Ｐｒｏｊ（ｔ１’）＝（０，ｔ１）、Ｐｒｏｊ（ｔ２’）＝（０，ｔ２）であり、Ｐｒｏｊ（μ）はμの最初のｎ’−ｎ個の要素が０であるｎ次元ベクトル空間への射影を表す（ステップＳ１１１−３）。
【０１２０】
≪量子計算部１１２の処理≫
量子計算部１１２（図４）は、基底Ｂ−’および目標ベクトルｔ１’，ｔ２’を入力とし、ｎ’次元空間における適当な領域（整数要素からなるｎ’次空間に属する部分領域）Ｒ⊆Ｚｎ’に対して以下に示す処理を実行し、スワップテストの結果を出力する（ステップＳ１１２）。例えば、Ｒ⊂Ｚｎ’である。
【０１２１】
例えば、以下の領域Ｒ（ΓＢ−’）を領域Ｒとすることができる。
【数１１２】
2020149523.tif 000114
ただし、Ｒ[０，Γ）は０以上Γ未満の実数を表し、ｘ”j"は実数であり、Γは２以上の整数であり、例えばΓ＝２である。また、ｊ”の値に応じて異なる整数Γが用いられてもよい。
あるいは、例えば、以下の領域Ｒ（ΓＢ−’*）を領域Ｒとしてもよい。
【数１１３】
2020149523.tif 000115
ただし、Ｂ−*’は双対基底Ｂ−’のGram-Schmidt非正規化直交ベクトルｂ−*’１，…，ｂ−*’ｎからなる基底Ｂ−*’＝｛ｂ−*’１，…，ｂ−*’ｎ｝を表す。ｂ−*’ｉのそれぞれはｎ’個の整数要素からなるｎ’次元ベクトルである。なお、これらの領域Ｒは本発明を限定するものではない。
【０１２２】
量子計算部１１２は以下の手順でスワップテストの結果を得る。
（ａ−１）量子計算部１１２の量子状態生成部１１２ａは、以下の量子状態からなるレジスタを複数個生成する（ステップＳ１１７２ａ−１）。
【数１１４】
2020149523.tif 000116
【０１２３】
（ｂ−１）量子状態生成部１１２ｂは、（ａ―１）で生成したレジスタのうち一部のレジスタに量子操作を行い、以下の量子状態に変換されたレジスタを得る（ステップＳ１１７２ｂ−１）。
【数１１５】
2020149523.tif 000117
これにより、｜φ＞０の量子状態のレジスタと｜φ＞ｔ１’の量子状態のレジスタがそれぞれ複数個存在することになる。
【０１２４】
（ｃ−１）スワップテスト部７２ｃは、量子状態｜φ＞０のレジスタと、量子状態｜φ＞ｔ１’のレジスタとの各ペアに対してスワップテストを実行し、各ペアに対するスワップテストの結果が受理（０，Ｙｅｓ）となるか拒否（１，Ｎｏ）となるかの判定結果を得て出力する（ステップＳ１１７２ｃ−１）。
【０１２５】
また、量子計算部１１２は以下の手順で別のスワップテストの結果も計算する。
（ａ−２）量子計算部１１２の量子状態生成部１１２ａは、以下の量子状態からなるレジスタを複数個作成する（ステップＳ１１７２ａ−２）。
【数１１６】
2020149523.tif 000118
【０１２６】
（ｂ−２）量子状態生成部１１２ｂは、（ａ−２）で生成したレジスタの一部に量子操作を行い、以下の量子状態からなるレジスタを得る（ステップＳ１１７２ｂ−２）。
【数１１７】
2020149523.tif 000119
【０１２７】
（ｃ−２）スワップテスト部７２ｃは、量子状態｜φ＞０のレジスタと、量子状態｜φ＞ｔ２’のレジスタとの各ペアに対してスワップテストを実行し、各ペアに対するスワップテストの結果が受理（０，Ｙｅｓ）となるか拒否（１，Ｎｏ）となるかの判定結果を得て出力する（ステップＳ１１７２ｃ−２）。
【０１２８】
≪古典計算部７３の処理≫
古典計算部７３は、量子計算部１１２で得られたスワップテストの結果を用い、量子状態｜φ＞０と量子状態｜φ＞ｔ１’とのペアに対するスワップテストの結果が受理となる確率ｐ１と、量子状態｜φ＞０と量子状態｜φ＞ｔ２’とのペアに対するスワップテストの結果が受理となる確率ｐ２とを計算する。そして、古典計算部７３は、ｐ１≧ｐ２の場合に||ｔ１（ｄ）||≦||ｔ２（ｄ）||であることを表す情報を出力し、ｐ１＜ｐ２の場合に||ｔ１（ｄ）||＞||ｔ２（ｄ）||であることを表す情報を出力する。あるいは、古典計算部７３は、ｐ１＞ｐ２の場合に||ｔ１（ｄ）||＜||ｔ２（ｄ）||であることを表す情報を出力し、ｐ１≦ｐ２の場合に||ｔ１（ｄ）||≧|ｔ２（ｄ）||であることを表す情報を出力する（ステップＳ７３）。
【０１２９】
＜具体例＞
第１実施形態の具体例と同じ問題を扱う。ここでは、基底Ｂを１次元高い空間に埋め込む、最も簡単な例を述べる。
≪古典計算部１１１の処理≫
古典計算部１１１の演算部は、基底Ｂを入力とし、以下の行列β’を得て出力する。
【数１１８】
2020149523.tif 000120
行列β’＝（ｂ１’，…，ｂｎ’’）Ｔの行ベクトルｂ１’，…，ｂｎ’’からなる基底をＢ’と表現する（ステップＳ１１１−１）。
【０１３０】
古典計算部１１１の演算部は、行列β’を入力とし、行列β’Ｔをエルミート分解する。エルミート標準形の行列Ｈ’の対角成分はすべて１、ユニモジュラ行列β−’は以下のようになる。
【数１１９】
2020149523.tif 000121
従って、以下が成立する。
【数１２０】
2020149523.tif 000122
古典計算部１１１の演算部は、ユニモジュラ行列β−’＝（ｂ１−’，ｂ２−’，ｂ３−’）Ｔの行ベクトルｂ１−’，ｂ２−’，ｂ３−’からなる基底をＢ−’として出力する（ステップＳ１１１−２）。
【０１３１】
古典計算部１１１の演算部は、基底Ｂ’および目標ベクトルｔ１＝（ｔ１，１，ｔ１，２）Ｔ，ｔ２＝（ｔ２，１，ｔ２，２）Ｔを入力とし、基底Ｂ’が張る空間ｓｐａｎ（Ｂ’）に属する３個の整数要素ｔ’１，ｉ’からなる目標ベクトルｔ１’＝（ｔ’１，１，…，ｔ’１，３）Ｔ∈ｓｐａｎ（Ｂ’）および３個の整数要素ｔ’２，ｉ’からなる目標ベクトルｔ２’＝（ｔ’２，１，ｔ’２，２，ｔ’２，３）Ｔ∈ｓｐａｎ（Ｂ’）を得て出力する。ｔ１’およびｔ２’は以下のようになる（ステップＳ１１１−３）。
【数１２１】
2020149523.tif 000123
【数１２２】
2020149523.tif 000124
【０１３２】
≪量子計算部１１２の処理≫
領域Ｒ（２Ｂ−’）が領域Ｒの場合には以下が成り立つ。
【数１２３】
2020149523.tif 000125
【０１３３】
量子計算部１１２は以下の計算を行う。
（ａ−１）量子計算部１１２の量子状態生成部１１２ａは、以下の量子状態のレジスタを複数個生成する。
【数１２４】
2020149523.tif 000126
【０１３４】
（ｂ−１）量子状態生成部１１２ｂは、上記複数個のレジスタのうち一部のレジスタに量子回転ゲート操作を適用する。これにより、回転ゲートが適用されたレジスタの量子状態は以下のようになる。
【数１２５】
2020149523.tif 000127
【０１３５】
（ｃ−１）スワップテスト部７２ｃは、量子状態｜φ＞０のレジスタと、量子状態｜φ＞ｔ１のレジスタとの各ペアに対してスワップテストを実行し、その結果を出力する。
【０１３６】
量子計算部１１２は以下の計算を行う。
（ａ−２）量子計算部１１２の量子状態生成部１１２ａは、以下の量子状態からなるレジスタを複数個生成する。
【数１２６】
2020149523.tif 000128
【０１３７】
（ｂ−２）量子状態生成部１１２ｂは、上記複数個のレジスタのうち一部のレジスタに量子回転ゲート操作を適用する。これにより、回転ゲートが適用されたレジスタの量子状態は以下のようになる。
【数１２７】
2020149523.tif 000129
【０１３８】
（ｃ−２）スワップテスト部７２ｃは、量子状態｜φ＞０のレジスタと、量子状態｜φ＞ｔ２’のレジスタとの各ペアに対してスワップテストを実行し、その結果を得て出力する。
【０１３９】
≪古典計算部７３の処理≫
古典計算部７３は、以上のスワップテストの結果から、確率ｐ１，ｐ２の値を計算する。この値を理論的に求めると、
【数１２８】
2020149523.tif 000130
となる。これらの値は第１実施形態の具体例のものと同一である。図１２に、この具体例での確率ｐ＝ｐ１，ｐ２の密度分布を例示する。図１２から分かるように、第１実施形態と同様、確率ｐ＝ｐ１，ｐ２の値で目標ベクトルが格子点に近いか否かを判断できることが分かる。
【０１４０】
最後に、この例ではｐ１＞ｐ２であるため、古典計算部７３は、||ｔ１（ｄ）||＜||ｔ２（ｄ）||であることを表す情報を出力する。
【０１４１】
［第６実施形態］
第６実施形態は、第２実施形態の変形例であり、第１実施形態の手法に代えて第５実施形態の手法を用い、与えられたｎ次元の最近ベクトル問題（Ｂ，ｔ）を解く（図１）。すなわち、与えられたｎ次元の最近ベクトル問題（Ｂ，ｔ）に対し、第５実施形態の手法を用い、目標ベクトルｔとの差分ベクトルｔ（Ｂ，ｄ）＝ｔ−ｔ（Ｂ，ｃ）が最短となるような格子Ｌ（Ｂ）上の最近ベクトルｔ（Ｂ，ｃ）∈Ｌ（Ｂ）を求める。
【０１４２】
＜構成＞
図７に例示するように、本形態の計算装置１２は、初期設定部８１、基底選択部８２、代表元選択部８３、子ノード生成部８４、古典計算部１２７、ノード選択部８５、制御部８６、および量子計算部１１２を有する。初期設定部８１、基底選択部８２、代表元選択部８３、子ノード生成部８４、古典計算部７１、ノード選択部８５、および制御部８６は、複数の演算部を有し、量子計算部１１２は、複数の量子計算部を有する（図示せず）。
【０１４３】
＜処理＞
本形態の処理を説明する。
初期設定部８１、基底選択部８２、代表元選択部８３、子ノード生成部８４の処理は第２実施形態と同じである。
【０１４４】
≪古典計算部１２７の処理≫
古典計算部１２７は、基底ＢＤおよび整数Ｎを用い、行列αＤと基底行列βＤとを行方向に並べた行列βＤ’＝（αＤ  βＤ）の転置行列βＤ’Ｔのエルミート標準形が対角成分１の行列となる行列αＤを選択し、βＤ’を出力する。古典計算部１２７は、エルミート標準形の行列Ｈ’に対してβＤ−’βＤ’Ｔ＝Ｈ’を満たすユニモジュラ行列βＤ−’を得て出力する。古典計算部１２７は、行列βＤ’＝（ｂＤ，１’，…，ｂＤ，ｎ’’）Ｔの行ベクトルｂＤ，１’，…，ｂＤ，ｎ’’からなる基底をＢＤ’とし、ユニモジュラ行列βＤ−’＝（ｂＤ，１−’，…，ｂＤ，ｎ’−’）Ｔの行ベクトルｂＤ，１−’，…，ｂＤ，ｎ’−’からなる基底をＢＤ−’とし、基底ＢＤ’が張る空間ｓｐａｎ（ＢＤ’）に属するｎ’個の整数要素からなる目標ベクトルｔ（Ｄ，ｋ’）∈ｓｐａｎ（ＢＤ’）を得て出力する。ただし、ｋ’＝０，１，…，ν（Ｄ）−１であり、Ｐｒｏｊ（ｔ（Ｄ，ｋ’））＝（０，ｔ（Ｄ−１）−ｃＤ，ｋ’）であり、Ｐｒｏｊ（μ）がμの最初のｎ’−ｎ個の要素が０であるｎ次元ベクトル空間への射影を表し、Ｌ（Ｂ−’）が格子Ｌ（Ｂ−’）＝｛Σｉ’＝１，…，ｎ’  ｘｉ’ｂ−’ｉ’｜ｘｉ’∈Ｚ，ｂ−’ｉ’∈Ｂ−’｝であり、ｘｉ’が整数であり、Ｒ⊆Ｚｎ’が整数要素からなるｎ’次空間に属する部分領域である（ステップＳ１２８７）。
【０１４５】
量子計算部１１２の処理は、（ａ−１）（ｂ−１）の｜φ＞０，Ｂ−’，｜φ＞ｔ１’，ｔ１’が｜φ＞Ｄ，０，ＢＤ−’，｜φ＞ｔ（Ｄ，ｋ’），ｔ（Ｄ，ｋ’）にそれぞれ置換され、（ｃ−１）が第２実施形態のスワップテストに置換され、（ａ−２）（ｂ−２）（ｃ−２）が実行されないこと以外、第５実施形態と同じである。
【０１４６】
ノード選択部８５、制御部８６の処理は、第２実施形態と同じである。
【０１４７】
［第７実施形態］
本形態では、第６実施形態の処理をサブルーチンとして利用してＳＶＰを解く（図１）。
【０１４８】
＜構成＞
図１０に例示するように、本形態の計算装置６は、基底生成部６１、設定部６２、選択部６３、および制御部６５を有する。
【０１４９】
＜処理＞
本形態の計算装置６は、基底Ｂを入力として、格子Ｌ（Ｂ）の中で最も原点に近い格子点への最短ベクトルｔ（ｃ）を出力する。
第３実施形態の設定部６２は第２実施形態の計算装置８により、差分ベクトルｔ（ｄ）を得ていたが、本実施形態の設定部６２は、第６実施形態で説明した計算装置１２により差分ベクトルｔ（ｄ）を得る。その他の処理は、第３実施形態と同じであるので説明を省略する。
【０１５０】
［第８実施形態］
本形態は第４実施形態の変形例である。本形態の計算装置は、第１実施形態の手法に代えて第５実施形態の手法を応用し、ｎ次元ベクトルａｊ，ｇおよびＮの入力に対して
【数１２９】
2020149523.tif 000131
を満たす（Ｘ１，…，Ｘｍ）Ｔを得て出力する（図２）。
【０１５１】
＜構成＞
図１１に例示するように、本形態の計算装置１４は、初期設定部１００、古典計算部１４０１，１０３（第１，２古典計算部）、選択部１０２、量子計算部１１２を有する。古典計算部１４０１，１０３は複数の演算部を有し、量子計算部１１２は複数の量子計算部を有する（図示せず）。  
【０１５２】
＜処理＞
本形態の処理を説明する。既に説明した処理部と同じ機能については説明を省略する。
【０１５３】
≪古典計算部１４０１の処理≫
古典計算部１４０１の演算部は、ＡＤ，Ｎ，ε１，…，εｎを入力とし、ＡＤＴにＮεｉＴ（ただし、ｉ＝１，…，ｎ）を加えた行ベクトルの集合｛ａｊ（Ｄ＋１）Ｔａｊ（Ｄ＋２）Ｔ … ａｊ（ｍ）Ｔ Ｎε１Ｔ…ＮεｎＴ｝で定義される格子のＬＬＬ既約基底ＢＤを計算して出力する（ステップＳ１４１１）。
【０１５４】
古典計算部１４０１の演算部は、ａｊ（Ｄ＋１）Ｔ，ａｊ（Ｄ＋２）Ｔ，…，ａｊ（ｍ）Ｔ，Ｎε１Ｔ，…，ＮεｎＴのＬＬＬ既約基底ＢＤの基底行列βＤを得て出力し、ｎ列の整数要素からなる行列αＤと基底行列βＤとを行方向に並べた行列βＤ’＝（αＤ  βＤ）の転置行列βＤ’Ｔのエルミート標準形が対角成分１の行列となる行列αＤを選択し、βＤ’を出力する。古典計算部１４０１の演算部は、エルミート標準形の行列Ｈ’に対してβＤ−’βＤ’Ｔ＝Ｈ’を満たすユニモジュラ行列βＤ−’を得て出力する。古典計算部１４０１の演算部は、行列βＤ’＝（ｂＤ，１’，…，ｂＤ，ｎ’’）Ｔの行ベクトルｂＤ，１’，…，ｂＤ，ｎ’’からなる基底をＢＤ’とし、ユニモジュラ行列βＤ−’＝（ｂＤ，１−’，…，ｂＤ，ｎ’−’）Ｔの行ベクトルｂＤ，１−’，…，ｂＤ，ｎ’−’からなる基底をＢＤ−’として出力する。古典計算部１４０１の演算部は、基底ＢＤ’が張る空間ｓｐａｎ（ＢＤ’）に属するｎ’個の整数要素からなる目標ベクトルｔ（Ｄ，j’）∈ｓｐａｎ（ＢＤ’）を得て出力する。ただし、ｊ’＝０，１，２…，Ｎ−１であり、Ｐｒｏｊ（ｔ（Ｄ，j’））＝（０，ｇＤ−１’Ｔ−ｊ’・ａｊ（Ｄ）Ｔ）であり、Ｐｒｏｊ（μ）がμの最初のｎ’−ｎ個の要素が０であるｎ次元ベクトル空間への射影を表す（ステップＳ１４１２）。
【０１５５】
量子計算部１１２の処理は、（ａ−１）（ｂ−１）の｜φ＞０，Ｂ−’，｜φ＞ｔ１’，ｔ１’が｜φ＞Ｄ，０，ＢＤ−’，｜φ＞ｔ（Ｄ，ｊ’），ｔ（Ｄ，j’）にそれぞれ置換され、（ｃ−１）が第４実施形態のスワップテストに置換され、（ａ−２）（ｂ−２）（ｃ−２）が実行されないこと以外、第５実施形態と同じである。
【０１５６】
＜具体例＞
次に、本実施形態の具体例を示す。ここではＬＷＥの例として、第４実施形態の具体例と同じ問題を扱う。ここでは深さＤ＝１の処理を例示するが、これらの処理はＤの値以外、その他のＤについても同様である。
【０１５７】
≪古典計算部１４０１の処理の例１≫
１．Ａから求めたい変数番号の列を除いたｎ×（ｍ−１）行列をRest(Ａ)と表現する。この例の場合、Ｘの一番目の変数Ｘ１の値を求めたいので、Rest(Ａ)はＡから一列目を除いた９×２行列である。古典計算部１４０１の演算部は、（ｎ＋ｍ−１）×ｎ行列
【数１３０】
2020149523.tif 000132
が表す基底で定義される格子のＬＬＬ既約基底Ｂ１を計算して出力する（ステップＳ１４１１）。ｍ＝３，ｎ＝９の場合、この例のＢ１を構成するｎ次元ベクトルｂ１，…，ｂ９を要素とする９行９列の基底行列β１は以下のようになる（ステップＳ１４１１）。
【数１３１】
2020149523.tif 000133
【０１５８】
その後、ステップＳ１４１２として、以下のステップＳ１４１２ａ〜Ｓ１４１２ｇが実行される。
２．古典計算部１４０１の演算部は、格子Ｌ（Ｂ１）を埋め込む空間の次元ｎ’を決める（ステップＳ１４１２ａ）。ｎ’はｎの倍数である。以下では、ｎ’がｎの３倍、すなわちｎ’＝９×３＝２７の例を説明する。
【０１５９】
３．古典計算部１４０１の演算部は、格子Ｌ（Ｂ１）の互いに異なる既約基底
【数１３２】
2020149523.tif 000134
をランダムに選ぶ（ステップＳ１４１２ｂ）。すなわち、
【数１３３】
2020149523.tif 000135
が成り立つ。古典計算部１４０１の演算部は、ｎ×ｎの行列β１Ｃｉ−1（ｉ＝１，２，…，（ｎ’／ｎ）−１）を横（行方向）に並べて、ｎ×（ｎ’−ｎ）行列
【数１３４】
2020149523.tif 000136
を得る（ステップＳ１４１２ｃ）。さらに古典計算部１４０１の演算部は、以下のようにｎ×ｎ’行列β１’を設定する。
β１’＝（Ｉｎ  Ｒ’）  (41)
ここでＩｎはｎ×ｎの単位行列である（ステップＳ１４１２ｄ）。β１’の行ベクトルｂ１’，…，ｂｎ’を要素とする｛ｂ１’，…，ｂｎ’｝が定義するｎ次元格子基底をＢ１’で表現する。以下にｎ’＝３ｎ＝２７のときのＲ’を例示する。
【数１３５】
2020149523.tif 000137
【０１６０】
４．古典計算部１４０１の演算部は、β１’の転置行列β１’Ｔをエルミート分解し、エルミート標準形の対角成分１のｎ’×ｎ行列と、ユニモジュラ行列
【数１３６】
2020149523.tif 000138
とを得る（ステップＳ１４１２ｅ）。ここで、Ｏｎ，ｎ’−ｎはｎ×（ｎ’−ｎ）ゼロ行列である。古典計算部１４０１の演算部は、このユニモジュラ行列の行ベクトルをｂ１−’，…，ｂｎ’−’とし、｛ｂ１−’，…，ｂｎ’−’｝で定義されるｎ’次元格子基底をＢ１−’とする（ステップＳ１４１２ｆ）。すなわち、
【数１３７】
2020149523.tif 000139
を満たす。式（４３）により、β１’の行ベクトルが張る空間（ｓｐａｎ｛ｂ１’，…，ｂｎ’｝）と（ｎ’−ｎ）×ｎ’行列（−ＲＴ  Ｉｎ’−ｎ）の行ベクトルが張る空間（ｓｐａｎ｛ｂｎ＋１−’，…，ｂｎ’−’｝）とが垂直であることに注意のこと。
【０１６１】
古典計算部１４０１の演算部は、以下の式（43Ａ）のように、基底Ｂ１’が張る空間ｓｐａｎ（Ｂ１’）に属するｎ’個の整数要素からなる目標ベクトルｔ（１，j’）∈ｓｐａｎ（Ｂ１’）を得て出力する。この目標ベクトルｔ（１，j’）は目標ベクトルｇ０’Ｔ−ｊ’・ａｊ（１）Ｔをｎ’次元空間へ埋め込んだものである。
ｔ（１，j’）＝（ｇ０’Ｔ−ｊ’・ａｊ（１）Ｔ）β１−１β１’  （43Ａ）
定義により、ｔ（１，j’）はβ１’の線形和なのでｔ（１，j’）∈ｓｐａｎ（Ｂ１’）である（ステップＳ１４１２ｇ）。ここでｓｐａｎ（Ｂ１’）はＢ１’の実数係数線形和が作る超平面である。ただし、（ｇ０’Ｔ−ｊ’・ａｊ（１）Ｔ）β１−１が整数であるとは限らないため、一般には
【数１３８】
2020149523.tif 000140
となる。例として、この具体例におけるｔ（１，１０）の計算結果を以下に示す。
【数１３９】
2020149523.tif 000141
【０１６２】
その後、例えば、Ｂ−＝Ｂ１−’とし、前述の領域Ｒ（ΓＢ−）またはＲ（ΓＢ−*）を領域Ｒとして、これ以降の量子計算部１１２の処理、選択部１０２の処理、および古典計算部１０３の処理が行われる。
【０１６３】
≪古典計算部１４０１の処理の例２≫
Ｂ１−’に代え、以下のように生成されるＢ１−”が用いられてもよい。これにより、より小さな次元数ｎ’の空間を用いて正しいαｊ（Ｄ）を求めることができる。この場合、古典計算部１４０１の演算部は、上述の≪古典計算部１４０１の処理の例１≫で説明したステップＳ１４１１を実行し、ステップＳ１４１２としてＳ１４１２ａ〜Ｓ１４１２ｆの処理を実行し、さらに以下のステップＳ１４１２ｈ〜Ｓ１４１２ｋ，Ｓ１４１２ｆを実行する。
【０１６４】
５．古典計算部１４０１の演算部は、ｎ’次元空間における単位ベクトルｕｎｉｔ１，…，ｕｎｉｔｎ’のｎ次元格子基底Ｂ１’が張る空間ｓｐａｎ（Ｂ１’）への射影ベクトルＰｒｏｊＢ１’（ｕｎｉｔ１），…，ＰｒｏｊＢ１’（ｕｎｉｔｎ’）を計算する（ステップＳ１４１２ｈ）。ここで単位ベクトルｕｎｉｔ１，…，ｕｎｉｔｎ’を用いるのは、Ｌ（Ｂ１−’）が単位ベクトルｕｎｉｔ１，…，ｕｎｉｔｎ’を基底とする格子と一致するからである。これらの射影ベクトルＰｒｏｊＢ１’（ｕｎｉｔ１），…，ＰｒｏｊＢ１’（ｕｎｉｔｎ’）は、長さ１以下、有理数要素のｎ’次元ベクトルとなる。式（４４）に示すように、これらの射影ベクトルＰｒｏｊＢ１’（ｕｎｉｔ１），…，ＰｒｏｊＢ１’（ｕｎｉｔｎ’）を縦に並べたｎ’×ｎ’行列をＰ１とする。
【数１４０】
2020149523.tif 000142
なお、式（４４）のランク（一次独立な行ベクトルの最大数）はｎなので、行列Ｐ１は逆行列Ｐ１−１を持たない。
【０１６５】
６．古典計算部１４０１の演算部は、｛ＰｒｏｊＢ１’（ｕｎｉｔ１），…，ＰｒｏｊＢ１’（ｕｎｉｔｎ’）｝のＬＬＬ既約基底｛ｑ１，ｑ２，…，ｑｎ｝を計算し、当該ＬＬＬ既約基底｛ｑ１，ｑ２，…，ｑｎ｝を構成する有理数要素のｎ’次元ベクトルｑ１，ｑ２，…，ｑｎを得る（ステップＳ１４１２ｉ）。式（４５）に示すように、ｎ’次元ベクトルｑ１，ｑ２，…，ｑｎを縦に並べたｎ×ｎ’行列（ｎ’次元空間中のｎ次元格子基底）をＱ１とする。
【数１４１】
2020149523.tif 000143
【０１６６】
７．古典計算部１４０１の演算部は、次の式（４６）を満たす整数要素のｎ×ｎ’行列Ｘ１を得る（ステップＳ１４１２ｊ）。
Ｘ１Ｐ１＝Ｑ１    (46)
ただし、前述のように行列Ｐ１は逆行列Ｐ１−１を持たないため、式（４６）の両辺の右側から行列Ｐ１の逆行列Ｐ１−１を掛けて行列Ｘ１を求めることはできない。そこで古典計算部１４０１の演算部は、まず、行列Ｐ１のスミス分解を行い、以下の式（４７）を満たすユニモジュラｎ’×ｎ’行列Ｕ１，Ｖ１と、整数α１，１，α２，２，…，αｎ，ｎとを計算する。
【数１４２】
2020149523.tif 000144
ここで、式（４７）を使って式（４５）からＰ１を削除すると、以下の式（４８）が得られる。
【数１４３】
2020149523.tif 000145
古典計算部１４０１の演算部は、行列Ｑ１，Ｕ１，Ｖ１と整数α１，１，α２，２，…，αｎ，ｎとを用い、式（４８）に従って行列Ｘ１を得る。なお、式（４８）の右辺の要素は分数で表現されているが、これらを計算すれば各要素の分子が分母で割り切れ、行列Ｘ１の各要素は整数となる。
【０１６７】
８．古典計算部１４０１の演算部は、式（４２）の１行目からｎ行目まで（すなわち、（Ｉｎ  Ｏｎ，ｎ’−ｎ）の部分）をｎ×ｎ’行列Ｘ１で置き換え、以下の式（４９）に示す行列β１−”を生成する。
【数１４４】
2020149523.tif 000146
古典計算部１４０１の演算部は、行列β１−”の行ベクトルの集合で定義される基底をＢ１−”に設定する（ステップＳ１４１２ｋ）。
【０１６８】
その後、古典計算部１４０１の演算部は前述のステップＳ１４１２ｇを実行する。そして、例えば、Ｂ−＝Ｂ１−”とし、前述の領域Ｒ（ΓＢ−）またはＲ（ΓＢ−*）を領域Ｒとして、これ以降の量子計算部１１２の処理、選択部１０２の処理、および古典計算部１０３の処理が行われる。
【０１６９】
≪選択部１０２の処理≫
選択部１０２は、量子計算部１１２でスワップテストを行った結果に基づいて、深さＤ＝１に対応する各ノード（Ｂ１，ｇ０’Ｔ−ｊ’・ａｊ（１）Ｔ）について、各ｊ’＝０，１，２…，１０に対応する評価値である確率ｐ１，ｊ’を計算し、これらの評価値に基づいて深さＤ＝１でのＸｊ（１）の値αｊ（１）を求める。この具体例において、領域ＲとしてＲ（２Ｂ１−”*）を用いて量子計算部１１２の処理を実行した場合、確率ｐ１，ｊ’は以下のようになる。
p1,0=0.500007
p1,1=0.500167
p1,2=0.500019
p1,3=0.500106
p1,4=0.500013
p1,5=0.500133
p1,6=0.500007
p1,7=0.500128
p1,8=0.500071
p1,9=0.500012
p1,10=0.500721
上記の例では、スワップテストを１００００回行ったときに、ｊ＝１０に対して約５００７回の０（受理，Ｙｅｓ）が得られるのに対し、ｊ≠１０に対しては高々５００１回程度しか０（受理，Ｙｅｓ）が得られない。従って、選択部１０２は、確率ｐ１，０，ｐ１，１，…，ｐ１，１０のうち最も高い確率ｐ１，１０に対応する１０をαｊ（１）として出力する。また選択部１０２は、ｇ１’＝ｇ０−１０・ａｊ（１）を計算して出力する。
【０１７０】
第４実施形態の具体例と比べて、第８実施形態の具体例の確率ｐ１，１０と他の確率ｐ１，０，…，ｐ１，９との差が著しく小さいのは、格子を埋め込む空間の次元が小さすぎるからである。確率ｐ１，１０と他の確率ｐ１，０，…，ｐ１，９との差を大きくするためには、次元数ｎ’を大きくすればよい。図１３に次元数ｎ’と確率ｐ１，ｊ’（ただし、ｊ’＝０，…，１０）との関係を例示する。図１３より、次元数ｎ’を大きくすることで確率ｐ１，１０と他の確率ｐ１，０，…，ｐ１，９との差を大きくなっていくことが分かる。一般に、正しいｊ’を選ぶためには必要な空間の次元数ｎ’は、元の格子の次元数ｎ、基底Ｂ１’、エラーの大きさ||error||に依存する。格子を埋め込む空間の次元n’を大きくし、基底Ｂ１’をうまく選択すれば、より大きなエラーに対する求解が可能になる。
【０１７１】
［第９実施形態］
第９実施形態は、学習データであるデータセットおよびクラスラベルを入力とし、第４，８実施形態の何れかの手法を用い、順伝播型ニューラルネットワークの教師有り学習を行う（図１４）。なお、本実施形態で扱うニューラルネットワークは順伝播型のみであるため、以下、「順伝播型」という記述を省略し、単に「ニューラルネットワーク」と表記する。
【０１７２】
図１５はニューラルネットワークの構成図を示す。ニューラルネットワークは、ユニットと呼ばれるノードの重みつき有向グラフで表現され、入力層、隠れ層（hidden layer）、出力層から構成される。隠れ層のないニューラルネットワークは、単層ニューラルネットワークと呼ばれる。また、１層以上の隠れ層を持つニューラルネットワークは、深層（多層）ニューラルネットワークと呼ばれる。バイアスユニットと呼ばれる固定値を持つユニットを除いて、ユニットには実数（浮動小数）値の変数がラベル付けされているものとする。以下、第Ｌ”層目（Ｌ”＝１，２，…，Ｄ”−２，Ｄ”−１，Ｄ”）、ι”番目（ι”＝０，１，２，…，ｍ）のユニットの変数をｘι”（Ｌ”）と表記する。ただし、Ｄ”は２以上の整数であり、ｍは正の整数である。ι”＝０に相当するユニットがバイアスユニットで、すべての深さＬ”に対してバイアスユニットの持つ固定値を１とする。
【０１７３】
第Ｌ”層目（Ｌ”＝１，２，…，Ｄ”−２，Ｄ”−１）における変数ｘ１（Ｌ”），…，ｘｍ（Ｌ”）の値から、第Ｌ”＋１層目のκ”番目のユニットの変数ｘκ”（Ｌ”＋１）の値が以下のように計算される。
【数１４５】
2020149523.tif 000147
【数１４６】
2020149523.tif 000148
ここで、Ｗι”，κ” （Ｌ”）は第Ｌ”層目のι”番目のユニットと、第Ｌ”＋１層目のκ”番目のユニットとの間の重みを意味する実数値である。なお、本来「ｘκ”（Ｌ”＋１）」「Ｗι”，κ”（Ｌ”）」等の上付き添え字は下付き添え字の真上に表記すべきであるが、記載表記の制約上、上付き添え字を下付き添え字の右上に表記することがある。また、Ψは活性化関数（activation function）と呼ばれる非線形の関数である。活性化関数Ψの例は、シグモイド（Sigmoid）関数（ロジスティック（Logistic）関数とも呼ばれる）
【数１４７】
2020149523.tif 000149
や、双曲線正接（tanh）
【数１４８】
2020149523.tif 000150
などであるが、以下に示すアルゴリズムはこれらの活性化関数に限定されない。なお、説明の便宜上、本実施形態では活性化関数Ψの逆像が一意に定まるものとする。ｅｎａｐは自然対数の底（ネイピア数）を表す。
【０１７４】
ニューラルネットワークの教師あり学習とは、トレーニングデータであるｎ組のｍ次元データセット｛ａ”ｉ，１，…，ａ”ｉ，ｍ｝（ｉ＝１，２，３，…，ｎ）からなる行列
【数１４９】
2020149523.tif 000151
および各データセット｛ａ”ｉ，１，…，ａ”ｉ，ｍ｝に対するクラスラベルｇ”ｉからなるベクトル
【数１５０】
2020149523.tif 000152
と、ニューラルネットワークの深さＤ”とが与えられたときに、各ｉ＝１，２，３，…，ｎ番目のデータセット｛ａ”ｉ，１，…，ａ”ｉ，ｍ｝について、変数ｘｊ（１）に各要素ａ”ｉ，ｊ（ｊ＝１，…，ｍ）を代入し、式（５０）（５１）により、深さＬ”＝２，３，…，Ｄ”の順序で変数ｘｊ（Ｌ”）（ただし、１≦Ｌ”＜Ｄ”のとき１≦ｊ≦ｍであり、Ｌ”＝Ｄ”のときｊ＝１である）の値ａ”ｉ，ｊ（Ｌ”）を計算して得られる、Ｌ”＝Ｄ”に対する変数ｘｊ（Ｄ”）の値ａ”ｉ，１（Ｄ”）が
【数１５１】
2020149523.tif 000153
を満たすような重みＷι”，κ” （Ｌ”）（ただし、１≦Ｌ”＜Ｄ”−２のとき０≦ι”≦ｍ，１≦κ”≦ｍであり、Ｌ”＝Ｄ”−１のとき０≦ι”≦ｍ，κ”＝１である）を決めることである。ただし、Ｒｅは実数の集合を表し、
【数１５２】
2020149523.tif 000154
はα１とα２との近似することを表す。
【０１７５】
これを数式で表現すると、ニューラルネットワークの教師あり学習とは、与えられたｎ×ｍ行列Ａｔとｎ＋１行列Ｇ”と整数Ｄ”≧２から、以下の式（５２）（５３）（５４）により計算して得られるｎ×１行列Ａｔ（Ｄ”）に対して、式（５５）を満たすＷ（１），Ｗ（２），…，Ｗ（Ｄ”−１）を決めることである。
【数１５３】
2020149523.tif 000155
【数１５４】
2020149523.tif 000156
【数１５５】
2020149523.tif 000157
【数１５６】
2020149523.tif 000158
ここで、
【数１５７】
2020149523.tif 000159
【数１５８】
2020149523.tif 000160
【数１５９】
2020149523.tif 000161
である。式（５３）の
【数１６０】
2020149523.tif 000162
はｍ×１行列Ｕ１とｍ×ｍ行列Ａｔ（Ｌ”）を行方向（横方向）に並べて作ったｍ×（ｍ＋１）行列を意味する。式（５４）の
【数１６１】
2020149523.tif 000163
はＺ（Ｌ”＋１）の各要素に活性化関数Ψを作用させて得られた各要素からなる行列（Ｚ（Ｌ”＋１）と同じサイズの行列）を表す。
【０１７６】
本実施形態では、第４，８実施形態の何れかの手法を用い、ニューラルネットワークの教師あり学習を行う。以下にその概念を説明する。
≪単層ニューラルネットワーク（Ｄ”＝２）の場合≫
簡単のため、まず単層ニューラルネットワークの場合を説明する。式（５２）（５３）（５４）（５５）により、以下が成り立つ。
【数１６２】
2020149523.tif 000164
このニューラルネットワークの教師あり学習では、式（５６）を満たすＷ０，１（１），Ｗ１，１（１），…，Ｗｍ，１（１）を計算する。
【０１７７】
ここで、十分大きな整数ｓ”を選択し、Ｎをｓ”よりも十分に大きな２のべき乗とする。例えば、ｓ”としてコンピュータにおける２進表現の有効桁数以上の整数を選択し、Ｎをｓ”よりも十分に大きな２のべき乗とする。ｓ”よりも十分に大きなＮの例は、Ｎ＞（ｓ”）２ｍを満たすＮである。ｓ”とＮの具体例として、例えば、２進表現の有効桁数が６４桁であり、ｍ＝２１０である場合、Ｎ＝２１４０＞（ｓ”）２ｍ＞ｓ”＝２６４を満たすｓ”およびＮを選ぶ。このとき、ｓ”ａ”ｉ，ｊおよびｓ”Ψ−1（ｇ”ｉ）を整数と考えてよい（ｉ＝１，…，ｎ、ｊ＝１，…，ｍ）。すると、式（５６）は以下の式（５７）のＬＷＥ問題と等価である。
【数１６３】
2020149523.tif 000165
そのため、第４，８実施形態の何れかの手法を用いて式（５７）のＬＷＥ問題の解Ｘ０，Ｘ１，…，Ｘｍを求め、求めた解をＷ０，１（１）＝Ｘ０，Ｗ１，１（１）＝Ｘ１，…，Ｗｍ，１（１）＝Ｘｍに設定することができる。ｄ＝（ｄ１，…，ｄｎ）Ｔは短いベクトルである。第４，８実施形態のＬＷＥ問題ではｊ＝１，…，ｍであり、解が（Ｘ１，…，Ｘｍ）Ｔであったが、第４，８実施形態においてｊ＝１，…，ｍをι”＝０，１，２，…，ｍに置換することで、式（５７）のＬＷＥ問題の解Ｘ０，Ｘ１，…，Ｘｍを求めることができる。
【０１７８】
≪深層ニューラルネットワーク（Ｄ”≧３）の場合≫
次に、深層ニューラルネットワークの場合を説明する。本実施形態における深層ニューラルネットワークの教師有り学習では、重みＷι”，κ” （Ｌ”）をＬ”＝１，２，…，Ｄ”−１の順に（すなわち、前方から後方に向かって正順に）計算していく。Ｌ”＝Ｄ”−１の場合の処理は単層ニューラルネットワークの場合と同じである。以下では、１＜Ｌ”＜Ｄ”−１に対してＷι”，κ”（Ｌ”−１）（０≦ι”≦ｍ，１≦κ”≦ｍ）が既に計算されているとして、Ｗι”，κ”（Ｌ”）（０≦ι”≦ｍ，１≦κ”≦ｍ）の計算方法を示す。
【０１７９】
まず、Ｌ”＝１の場合には
【数１６４】
2020149523.tif 000166
に設定する。１＜Ｌ”＜Ｄ”−１の場合には、式（５２）（５３）（５４）を用いてＷι”，κ”（Ｌ”−１）（０≦ι”≦ｍ，１≦κ”≦ｍ）から、変数ｘκ”（Ｌ”）の値ａ”ι”，κ”（Ｌ”）が計算される。次に、第４，８実施形態の何れかの手法を用い、以下の式（５８）のＬＷＥ問題の解Ｘ＝（Ｘ０，Ｘ１，…，Ｘｍ）Ｔの候補値を求め、求めた解Ｘの候補値をＷι”，κ”（Ｌ”）（０≦ι”≦ｍ，１≦κ”≦ｍ）に設定する。
【数１６５】
2020149523.tif 000167
ｄ＝（ｄ１，…，ｄｎ）Ｔは短いベクトルである。式（５８）のＬＷＥ問題に一意的な解が存在する場合、ＬＷＥ問題の求解計算過程において、解Ｘ＝（Ｘ０，Ｘ１，…，Ｘｍ）Ｔの一つの候補値だけが他と比べて極端に短い差分ベクトルｄに対応する。そのため、差分ベクトルｄの長さ||ｄ||から正しい解を見分けやすい。一方、ニューラルネットワークの学習では、重みの準最適値が多数存在すると考えられ、解Ｘの候補値の多くが似たような長さ||ｄ||の差分ベクトルｄを持つ可能性がある。そこで、式（５８）を解いて、長さ||ｄ||が短い順で１番目からｍ番目までである差分ベクトルｄに対応するｍ組の解Ｘの候補値を選択し、κ”（１≦κ”≦ｍ）番目の解Ｘ＝（Ｘ０，Ｘ１，…，Ｘｍ）Ｔの候補値を（Ｗ０，κ”（Ｌ”），Ｗ１，κ”（Ｌ”），…，Ｗｍ，κ”（Ｌ”））Ｔとする。なお、第４実施形態等の選択部１０２では、スワップテストの結果が受理となる確率ｐＤ，０，ｐＤ，１，…，ｐＤ，Ｎ−１を求め、この中から最も高い確率ｐＤ，ｊｍａｘに対応するｊｍａｘ∈｛０，１，２…，Ｎ−１｝をαｊ（Ｄ）＝Ｘｊ（Ｄ）として出力していたが、Ｘｊ（Ｄ）の候補値は確率ｐＤ，０，ｐＤ，１，…，ｐＤ，Ｎ−１の中から確率の高い順に選択した複数個の確率に対応するｊである。
【０１８０】
このようにして重みＷι”，κ”（Ｌ”）を決めると、第Ｌ”＋１層のユニットの変数ｘｊ（Ｌ”＋１）の値ａ”ｉ，ｊ（Ｌ”＋１）は、第Ｌ”層のユニットの変数ｘｊ（Ｌ”）の値ａ”ｉ，ｊ（Ｌ”）よりも、クラスラベルｇ”ｉに近づくことが期待できる。これは以下の理由による。
式（５２）（５３）（５４）によるａ”ｉ，ｊ（Ｌ”＋１）の定義より、以下が成り立つ。
【数１６６】
2020149523.tif 000168
また、式（５８）において各要素はＮに対して十分小さいため、ｍｏｄ  Ｎを無視すると以下の式（６０）が成り立つ。
【数１６７】
2020149523.tif 000169
ｃ”を｜Ψ（ｚ１”）−Ψ（ｚ２”）｜≦ｃ”｜ｚ１”−ｚ２”｜を満たす適当な数とすると（例えば、ｃ”はΨ（ｚ１”）の微分値の絶対値の上界とすればよい）、式（５９）（６０）より、以下の式（６１）が成り立つ。
【数１６８】
2020149523.tif 000170
Ｌ”が大きくなるに従って式（６１）の右辺（差分ベクトルの長さ）が小さくなるように重みＷ０，κ”（Ｌ”），Ｗ１，κ”（Ｌ”），…，Ｗｍ，κ”（Ｌ”）が選ばれるため、式（６１）の左辺はＬ”が大きくなるにつれて０に近づいていく。
【０１８１】
＜構成＞
図１６に例示するように、本形態の学習システム１５は、学習装置１５０と第４，８実施形態で説明した計算装置１０，１４の何れかとを有する。学習装置１５０は、初期設定部１５１、ＬＷＥ問題処理部１５２、活性化関数演算部１５３、および制御部１５４を有する。学習装置１５０は、例えば、ネットワークを通じて計算装置１０，１４の何れかに接続されている。
【０１８２】
＜処理＞
本形態の処理を説明する。
学習装置１５には、トレーニングデータであるｎ組のｍ次元データセット｛ａ”ｉ，１，…，ａ”ｉ，ｍ｝（ｉ＝１，２，３，…，ｎ）からなる行列
【数１６９】
2020149523.tif 000171
および各データセット｛ａ”ｉ，１，…，ａ”ｉ，ｍ｝（ｉ＝１，２，３，…，ｎ）に対するクラスラベルｇ”ｉ（ｉ＝１，２，３，…，ｎ）からなるベクトル
【数１７０】
2020149523.tif 000172
と、ニューラルネットワークの深さＤ”とが入力される。学習装置１５はこれらを用いて以下の各処理を実行する。
【０１８３】
初期設定部１５１は、Ｌ”＝１とし、行列Ａｔを用いて以下のようにａ”ｉ，ｊ（１）を設定する（ステップＳ１５１）。
【数１７１】
2020149523.tif 000173
【０１８４】
ＬＷＥ問題処理部１５２、活性化関数演算部１５３、および制御部１５４は、Ｌ”＝１，２，…，Ｄ”−２の順序で、以下のステップＳ１５２ａおよびＳ１５３ａを実行する。
【０１８５】
≪ステップＳ１５２ａ≫
ＬＷＥ問題処理部１５２は、以下の式（６２）のＬＷＥ問題を計算装置１０，１４の何れかに送る。このＬＷＥ問題が送られた計算装置１０，１４は前述のように以下の式（６２）を解いて、解Ｘ＝（Ｘ０，Ｘ１，…，Ｘｍ）Ｔの候補値を生成して出力する。
【数１７２】
2020149523.tif 000174
なお、式（６２）は、式（６３）のＬＷＥ問題と等価である。
【数１７３】
2020149523.tif 000175
ｓ”は十分大きな整数である。ｓ”の例は、コンピュータにおける２進表現の有効桁数を超える整数である。また、第４，８実施形態のＬＷＥ問題ではｊ＝１，…，ｍであり、解が（Ｘ１，…，Ｘｍ）Ｔであったが、計算装置１０，１４は、第４，８実施形態においてｊ＝１，…，ｍをι”＝０，１，２，…，ｍに置換することで、式（６２）（６３）のＬＷＥ問題の解Ｘ＝（Ｘ０，Ｘ１，…，Ｘｍ）Ｔの候補値を求めて出力する。なお、式（６３）の
【数１７４】
2020149523.tif 000176
【数１７５】
2020149523.tif 000177
【数１７６】
2020149523.tif 000178
は、それぞれ、式（１０）（３３）（４０）の
【数１７７】
2020149523.tif 000179
【数１７８】
2020149523.tif 000180
【数１７９】
2020149523.tif 000181
に相当する。解Ｘ＝（Ｘ０，Ｘ１，…，Ｘｍ）Ｔの候補値は、ＬＷＥ問題処理部１５２に入力される。ＬＷＥ問題処理部１５２は、解Ｘの候補値のうち、対応するｄ＝（ｄ１，…，ｄｎ）Ｔの長さ||ｄ||が短い順にｍ組の解Ｘの解候補を選択し、選択したｍ組の解Ｘの解候補を（Ｗ０，κ”（Ｌ”），Ｗ１，κ”（Ｌ”），…，Ｗｍ，κ”（Ｌ”））Ｔとする（κ”＝１，２，…，ｍ）。ＬＷＥ問題処理部１５２は、これらの（Ｗ０，κ”（Ｌ”），Ｗ１，κ”（Ｌ”），…，Ｗｍ，κ”（Ｌ”））Ｔを用い、以下のＷ（Ｌ”）を設定して出力する。
【数１８０】
2020149523.tif 000182
【０１８６】
≪ステップＳ１５３ａ≫
次に活性化関数演算部１５３は、ａ”ｊ，κ”（Ｌ”＋１）（１≦ｊ，κ”≦ｍ）を以下のように設定して出力する（ステップＳ１５３ａ）。
【数１８１】
2020149523.tif 000183
【０１８７】
≪ステップＳ１５４≫
制御部１５４は、Ｌ”＝Ｄ”−２であるか否かを判断する。Ｌ”＝Ｄ”−２でなければ、Ｌ”＋１を新たなＬ”としてステップＳ１５２ａの処理に戻る。Ｌ”＝Ｄ”−２であれば、次のステップＳ１５２ｂに進む。
【０１８８】
≪ステップＳ１５２ｂ≫
Ｌ”＝Ｄ”−１について以下の処理が実行される。
ＬＷＥ問題処理部１５２は、以下の式（６３）のＬＷＥ問題を計算装置１０，１４の何れかに送る。このＬＷＥ問題が送られた計算装置１０，１４は前述のように以下の式（６３）を解いて、解Ｘ＝（Ｘ０，Ｘ１，…，Ｘｍ）Ｔを生成して出力する。
【数１８２】
2020149523.tif 000184
なお、式（６４）は、式（６５）のＬＷＥ問題と等価である。
【数１８３】
2020149523.tif 000185
なお、式（６５）の
【数１８４】
2020149523.tif 000186
【数１８５】
2020149523.tif 000187
【数１８６】
2020149523.tif 000188
は、それぞれ、式（１０）（３３）（４０）の
【数１８７】
2020149523.tif 000189
【数１８８】
2020149523.tif 000190
【数１８９】
2020149523.tif 000191
に相当する。解Ｘ＝（Ｘ０，Ｘ１，…，Ｘｍ）Ｔは、ＬＷＥ問題処理部１５２に入力される。ＬＷＥ問題処理部１５２は、解Ｘ＝（Ｘ０，Ｘ１，…，Ｘｍ）Ｔを（Ｗ０，１（Ｄ”−１），Ｗ１，１（Ｄ”−１），…，Ｗｍ，１（Ｄ”−１））Ｔとする。ＬＷＥ問題処理部１５２は、これらの（Ｗ０，１（Ｄ”−１），Ｗ１，１（Ｄ”−１），…，Ｗｍ，１（Ｄ”−１））Ｔを用い、以下のＷ（Ｄ”−１）を設定して出力する。
【数１９０】
2020149523.tif 000192
【０１８９】
≪ステップＳ１５３ｂ≫
次に活性化関数演算部１５３は、ａ”ｊ，１（Ｄ”＋１）（１≦ｊ≦ｍ）を以下のように設定して出力する。
【数１９１】
2020149523.tif 000193
【０１９０】
学習装置１５は、以上によって得たＷ（１），…，Ｗ（Ｄ”−１）を、ニューラルネットワークの重みとして出力する。
【０１９１】
［その他の変形例等］
なお、本発明は上述の実施形態に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０１９２】
古典計算部７１，７３，８７，１０１，１０３，１１１，１２７，１４０１、制御部７４，８６、初期設定部８１、基底選択部８２、代表元選択部８３、子ノード生成部８４、ノード選択部８５、計算装置６、および学習装置１５０は、例えば、ＣＰＵ（central processing unit）等のプロセッサ（ハードウェア・プロセッサ）およびＲＡＭ（random-access memory）・ＲＯＭ（read-only memory）等のメモリ等を備える汎用または専用のコンピュータが所定のプログラムを実行することで構成される。このコンピュータは１個のプロセッサやメモリを備えていてもよいし、複数個のプロセッサやメモリを備えていてもよい。このプログラムはコンピュータにインストールされてもよいし、予めＲＯＭ等に記録されていてもよい。また、ＣＰＵのようにプログラムが読み込まれることで機能構成を実現する電子回路である処理回路（processing circuitry）ではなく、プログラムを用いることなく処理機能を実現する電子回路である処理回路（processing circuitry）を用いて一部またはすべての演算部が構成されてもよい。また、１個の装置を構成する電子回路が複数のＣＰＵを含んでいてもよい。量子計算部７２，１１２は、公知の量子コンピュータ（量子コンピュータによる処理回路（processing circuitry））によって構成される。
【０１９３】
以下に、具体的な量子コンピュータの構成例を示す。
１．量子ゲート（量子回路）に基づく方式型：量子ゲート型の量子コンピュータは、量子ゲートと呼ばれる基本演算を量子ビットに順次適用していくことで計算を実現する量子コンピュータである。量子ゲートの適用順序を量子回路として記述できる。量子ゲート型の量子コンピュータでは、量子ビットに量子ゲートに対応する操作を適用することで、量子ビット（キュービット）の集合でエンコードされた量子状態が、順次変化していき、最後に量子状態を観測することで計算結果が得られる。量子ゲート型の量子コンピュータは、最もオーソドックスな方式であり、研究の歴史も長く、ハードウェア開発が進んでいる（参考文献１２参照）。IBM, Google, Intel, Rigetti, IonQ など多数の企業がこの方式に基づく量子コンピュータを開発しており、2018 年時点で、規模は数十キュービットに達している。
［参考文献１２］Michael A. Nielsen and Isaac L. Chuang, Quantum Computation and Quantum Information, Cam-bridge: Cambridge University Press (2000) ISBN 0-521-63235-8, MR 1796805.
【０１９４】
２．断熱量子計算：断熱量子計算に基づく量子コンピュータでは、単純なハミルトニアンから、基底状態が与えられた問題に対する解を記述する（複雑な）ハミルトニアンに物理系を断熱的に変化させることにより、計算を実行する。断熱量子計算は、量子回路モデルとの多項式時間での等価性が証明されている（参考文献１３参照）。
［参考文献１３］Farhi, E.; Goldstone, J.; Gutmann, S.; Sipser, M. (2000). "Quantum Computation by Adiabatic Evolution".arXiv:quant-ph/0001106v1Freely accessible.
断熱量子計算に類似の方式として量子焼きなまし法(Quantum Annealing)も知られている（参考文献１４参照）。2018年時点で、カナダのD-wave社が量子焼きなまし法に基づく2048キュービットの量子コンピュータを発売している。複数の研究機関が導入している。
［参考文献１４］Kadowaki, T.; Nishimori, H. (1998-11-01). "Quantum annealing in the transverse Ising model". Physical Review E. 58: 5355. arXiv:cond-mat/9804280Freely accessible. Bibcode:1998PhRvE..58.5355K. doi:10.1103/PhysRevE.58.5355.
【０１９５】
３．トポロジカル量子計算：トポロジカル量子計算に基づく量子コンピュータは、マヨラナ粒子（Majorana fermion）と呼ばれる理論的には存在が予想されているが実験的には未確認の素粒子を用いた量子コンピュータであり、量子回路に基づく量子コンピュータと等価である（参考文献１５参照）。量子回路方式と比べ量子エラーに強く、大規模化に有利とされている。
［参考文献１５］Freedman, Michael; Kitaev, Alexei; Larsen, Michael; Wang, Zhenghan (2003-01-01). "Topological quantum computation". Bulletin of the American Mathematical Society. 40 (1): 3138. arXiv:quant-ph/0101025Freely accessible. doi:10.1090/S0273-0979-02-00964-3. ISSN 0273-0979.
【０１９６】
４．観測ベース量子計算（一方向性量子計算）：観測ベース量子計算に基づく量子コンピュータでは、エンタングルした多数のキュービットを準備し、それらのキュービットを端から逐次観測し、観測結果に応じて次の観測基底を変えることにより計算を実行する。観測ベース量子計算は、量子回路モデルとの多項式時間での等価性が証明されている（参考文献１６参照）。
［参考文献１６］R. Raussendorf; D. E. Browne & H. J. Briegel (2003). "Measurement based Quantum Computation on Cluster States". Phys. Rev. A. 68 (2): 022312. arXiv:quant-ph/0301052Freely accessible.
Bibcode:2003PhRvA..68b2312R. doi:10.1103/PhysRevA.68.022312.
【０１９７】
なお、第５−８実施形態で正確な解を得るためにはハードウェアに関する大きなリソースが必要となるが、これらの実施形態を利用すれば高次元の格子問題を解くことができる。一方で、第１−４実施形態は、第５−８実施形態のような大きなリソースを必要としないが、高次元の格子問題を解くことができない。これは、第１−４実施形態の手法では、第５−８実施形態で説明した格子を埋め込む空間の次元のような問題の難易度に応じて調節できるパラメータを持っていないためである。そのため、それぞれの長所と短所を考慮したうえで、適切な手法を利用するのが望ましい。
【０１９８】
上述の構成をコンピュータ（古典コンピュータおよび量子コンピュータ）によって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。
【０１９９】
このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０２００】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。処理の実行時、このコンピュータは、自己の記憶装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。
【０２０１】
コンピュータ上で所定のプログラムを実行させて本装置の処理機能が実現されるのではなく、これらの処理機能の少なくとも一部がハードウェアで実現されてもよい。
【産業上の利用可能性】
【０２０２】
以下に本発明の産業上の利用可能性を例示する。ただし、これらの利用可能性は単なる例示にすぎず、本発明を限定するものではない。本発明を用いることにより、組み合わせ最適化問題の一種である格子問題の部分問題を効率的に解くことができる。これにより、例えば２つの産業分野に影響を及ぼす。人工知能分野と耐量子暗号分野である。
【０２０３】
例えば、本発明を適用することで、人工知能分野での組み合わせ最適化問題の部分問題を効率的に（高速に）解くことができる。例えば、本発明をゲート型量子コンピュータ上および古典コンピュータで実装することにより、人工知能を用いて工業・材料・医療・医薬・エネルギー・物理・化学・経済・実社会等の様々な事象を高速にシミュレーションすることが可能となり、各分野の急激な進歩発展に貢献する。
【０２０４】
以下、より具体的に説明する。最近ベクトル問題、最短ベクトル問題、ＬＷＥは、ともにＮＰ困難と呼ばれる問題であり、他のＮＰ（非決定性多項式時間計算量クラス）の問題をこれらの問題に効率的に帰着できることが知られている。帰着した問題を解けば、もとのＮＰ問題に対する解が得られるため、本発明で提案した量子アルゴリズムは、例えば、すべてのＮＰ問題に応用できる。ＮＰ問題には、人工知能を中心に重要な問題が多数含まれており、産業上の応用範囲はきわめて広い。代表的な応用例を列挙する。
【０２０５】
１．車の自動運転における最適経路選択：
車の自動運転における最適経路選択は、巡回セールスマン問題と呼ばれるＮＰ完全問題で定式化される。この問題は人工知能分野で古くから研究されてきた問題であり、頂点の数が多くなると、古典コンピュータで最適解を求めることが困難になる。このため、近年、この問題に対する量子コンピュータ（特に量子アニーリング）の応用が盛んに研究されている。
２. 大規模集積回路の最適化：
大規模集積回路を最適化する問題を論理式で表現することにより、制約充足問題（Constraint Satisfaction Problem）となる。この問題は人工知能における代表的な問題で、有用性が高いことから、古典アルゴリズムによる研究の歴史も長い。この問題は、量子コンピュータの応用対象として、特に有力視されているものの一つである。
３．ネットワークインフラの最適化：
電気・ガス・水道網、交通・通信網、石油・ガスのパイプライン等、大規模・複雑化する都市機能の最適化は、計算量爆発のためこれまで困難だった。本発明で提案した量子アルゴリズムの応用により、これらの問題に対する解決が期待される。
【０２０６】
例えば、車の自動運転における、最適経路選択の問題は、経路の組み合わせをベクトルで表現することにより格子問題に帰着する。経路の長さが一定以下になると、ベクトルが格子点に一定距離以下に近づくようエンコードすることにより、格子問題を解けば、経路に関する情報が得られるようにする。ＮＰ完全問題の格子問題への帰着方法に関するより詳しい説明は、以下の参考文献１７を参照のこと。
［参考文献１７］Daniele Micciancio and Sha_ Goldwasser, Complexity of Lattice Problems: a cryptographic perspective,
Kluwer Academic Publishers, The Kluwer International Series in Engineering and Computer Science, vol. 671 (2002).
その他のＮＰ完全問題に関しては、以下の文献を参照されたい。
［参考文献１８］Michael R. Garey and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W H Freeman & Co (1979).
専門家の間では、すべてのＮＰ問題の厳密解を、古典コンピュータで効率的に解く方法は存在しないと予想されている（Ｐ・ＮＰ予想）。産業上の応用目的で古典コンピュータによりＮＰ問題を扱う場合、解の精度を犠牲にして近似的な計算結果を用いるか、厳密解を得るために部分問題に制限するかの選択を迫られる場合が多い。一方、本発明の量子アルゴリズムを用いると、計算結果の精度が著しく向上したり、部分問題への制限の条件を緩和することができる。この結果、今まで提供できなかったサービスが提供できるようになる。
【０２０７】
また、耐量子暗号分野においては、本発明によって従来の格子暗号の安全性が損なわれる可能性がある。脆弱性を補うために鍵長を長くする等の対策が必要になるが、鍵長の変更は暗号効率の悪化を招きかねない。本発明を格子暗号の安全性評価と暗号効率との評価に利用すれば、これらの問題を共に解決する暗号方式の開発に貢献することも期待される。
【図１】
2020149523.tif 000222
【図２】
2020149523.tif 000223
【図３】
2020149523.tif 000224
【図４】
2020149523.tif 000225
【図５】
2020149523.tif 000226
【図６】
2020149523.tif 000227
【図７】
2020149523.tif 000228
【図８】
2020149523.tif 000229
【図９】
2020149523.tif 000230
【図１０】
2020149523.tif 000231
【図１１】
2020149523.tif 000232
【図１２】
2020149523.tif 000233
【図１３】
2020149523.tif 000234
【図１４】
2020149523.tif 000235
【図１５】
2020149523.tif 000236
【図１６】
2020149523.tif 000237