(57)【特許請求の範囲】
【請求項１】
互いに素な正整数ａとＮ、整数ｂ（０≦ｂ＜Ｎ)、及び、ａr＝１ ｍｏｄ Ｎを満たす最小の整数ｒ（ただし、ｒは素数とする）が与えられているときに、ａt＝ｂ ｍｏｄ Ｎを満たす最小の整数ｔを求めるための量子演算方法であって、
ｎをlog ｒ以上の所定の整数とし、ｍをlog Ｎ以上の所定の整数とし、ｎ個の計算量子ビットｘk（ｋ∈｛１，２，…，ｎ｝）からなる第１レジスタとｍ個の補助量子ビットｙj（ｊ∈｛１，２，…，ｍ｝）からなる第２レジスタについて、全ての計算量子ビットｘk（ｋ∈｛１，２，…，ｎ｝）の初期状態を|0〉とし、第１補助量子ビットｙ1の初期状態を|1〉とし、第ｊ補助量子ビットｙj（ｊ∈｛２，３，…，ｍ｝）の初期状態を|0〉とし、計算量子ビットの量子状態を|x>=|x１x２…xn>とし、補助量子ビットの量子状態を|y>=|y１y２…ym>とし、
【数３９】
0005351862.tif 000040
として、
上記第１レジスタに対して、量子フーリエ変換
【数４０】
0005351862.tif 000041
を適用する第１量子フーリエ変換ステップと、
上記第１量子フーリエ変換ステップで得られた演算結果に対して、
（１）各上記計算量子ビットｘk（ｋ∈｛１，２，…，ｎ｝）について、第ｋ計算量子ビットｘkを制御ビットとして、制御ビットの状態が|1>のときのみ、上記第２レジスタ|y>に対して演算Ｕ-a,N（ただし、演算Ｕ-a,Nは
【数４１】
0005351862.tif 000042
で定義される）を２2(n-k)回施し、
（２）ｎ−１個の上記計算量子ビットｘk（ｋ∈｛ｎ−１，ｎ−２，…，１｝）それぞれについて、第ｋ計算量子ビットｘkと第ｈ計算量子ビットｘh（ただし、ｈはｋ＜ｈ≦ｎを満たす整数である）を制御ビットとし、各整数ｈについて、制御ビットの状態が共に|1>のときのみ、上記第２レジスタ|y>に対して上記演算Ｕ-a,Nを２2n-k-h+1回施す
第１剰余演算ステップと、
上記第１剰余演算ステップで得られた上記第１レジスタに対して、量子フーリエ変換
【数４２】
0005351862.tif 000043
を適用する第２量子フーリエ変換ステップと、
上記第２量子フーリエ変換ステップで得られた上記第１レジスタおよび上記第１剰余演算ステップで得られた上記第２レジスタに対して、各上記計算量子ビットｘk（ｋ∈｛１，２，…，ｎ｝）について、第ｋ計算量子ビットｘkを制御ビットとし、制御ビットの状態が|1>のときのみ、第２レジスタ|y>に対して演算Ｕb＾2,N（ただし、演算Ｕb＾2,Nは
【数４３】
0005351862.tif 000044
で定義される）を２k回施す第２剰余演算ステップと、
上記第２剰余演算ステップで得られた上記第１レジスタに対して、量子逆フーリエ変換
【数４４】
0005351862.tif 000045
を適用する第１量子逆フーリエ変換ステップと、
上記第１量子逆フーリエ変換ステップで得られた上記第１レジスタおよび上記第２剰余演算ステップで得られた上記第２レジスタに対して、
（１）各上記計算量子ビットｘk（ｋ∈｛１，２，…，ｎ｝）について、第ｋ計算量子ビットｘkを制御ビットとして、制御ビットの状態が|1>のときのみ、上記第２レジスタ|y>に対して演算Ｕ-a,N（ただし、演算Ｕ-a,Nは
【数４５】
0005351862.tif 000046
で定義される）を２2(n-k)回施し、
（２）ｎ−１個の上記計算量子ビットｘk（ｋ∈｛ｎ−１，ｎ−２，…，１｝）それぞれについて、第ｋ計算量子ビットｘkと第ｈ計算量子ビットｘh（ただし、ｈはｋ＜ｈ≦ｎを満たす整数である）を制御ビットとし、各整数ｈについて、制御ビットの状態が共に|1>のときのみ、上記第２レジスタ|y>に対して上記演算Ｕ-a,Nを２2n-k-h+1回施す
第３剰余演算ステップと、
上記第３剰余演算ステップで得られた上記第１レジスタに対して、量子逆フーリエ変換
【数４６】
0005351862.tif 000047
を適用する第２量子逆フーリエ変換ステップと
を有する量子演算方法。
【請求項２】
互いに素な正整数ａとＮ、整数ｂ（０≦ｂ＜Ｎ)、及び、ａr＝１ ｍｏｄ Ｎを満たす最小の整数ｒ（ただし、ｒは素数とする）が与えられているときに、ａt＝ｂ ｍｏｄ Ｎを満たす最小の整数ｔを求めるための量子演算装置であって、
ｎをlog ｒ以上の所定の整数とし、ｍをlog Ｎ以上の所定の整数とし、ｎ個の計算量子ビットｘk（ｋ∈｛１，２，…，ｎ｝）からなる第１レジスタとｍ個の補助量子ビットｙj（ｊ∈｛１，２，…，ｍ｝）からなる第２レジスタについて、全ての計算量子ビットｘk（ｋ∈｛１，２，…，ｎ｝）の初期状態を|0〉とし、第１補助量子ビットｙ1の初期状態を|1〉とし、第ｊ補助量子ビットｙj（ｊ∈｛２，３，…，ｍ｝）の初期状態を|0〉とし、計算量子ビットの量子状態を|x>=|x１x２…xn>とし、補助量子ビットの量子状態を|y>=|y１y２…ym>とし、
【数４７】
0005351862.tif 000048
として、
上記第１レジスタに対して、量子フーリエ変換
【数４８】
0005351862.tif 000049
を適用する第１量子フーリエ変換部と、
上記第１量子フーリエ変換部の演算結果に対して、
（１）各上記計算量子ビットｘk（ｋ∈｛１，２，…，ｎ｝）について、第ｋ計算量子ビットｘkを制御ビットとして、制御ビットの状態が|1>のときのみ、上記第２レジスタ|y>に対して演算Ｕ-a,N（ただし、演算Ｕ-a,Nは
【数４９】
0005351862.tif 000050
で定義される）を２2(n-k)回施し、
（２）ｎ−１個の上記計算量子ビットｘk（ｋ∈｛ｎ−１，ｎ−２，…，１｝）それぞれについて、第ｋ計算量子ビットｘkと第ｈ計算量子ビットｘh（ただし、ｈはｋ＜ｈ≦ｎを満たす整数である）を制御ビットとし、各整数ｈについて、制御ビットの状態が共に|1>のときのみ、上記第２レジスタ|y>に対して上記演算Ｕ-a,Nを２2n-k-h+1回施す
第１剰余演算部と、
上記第１剰余演算部による演算で得られた上記第１レジスタに対して、量子フーリエ変換
【数５０】
0005351862.tif 000051
を適用する第２量子フーリエ変換部と、
上記第２量子フーリエ変換部による演算で得られた上記第１レジスタおよび上記第１剰余演算部による演算で得られた上記第２レジスタに対して、各上記計算量子ビットｘk（ｋ∈｛１，２，…，ｎ｝）について、第ｋ計算量子ビットｘkを制御ビットとし、制御ビットの状態が|1>のときのみ、第２レジスタ|y>に対して演算Ｕb＾2,N（ただし、演算Ｕb＾2,Nは
【数５１】
0005351862.tif 000052
で定義される）を２k回施す第２剰余演算部と、
上記第２剰余演算部による演算で得られた上記第１レジスタに対して、量子逆フーリエ変換
【数５２】
0005351862.tif 000053
を適用する第１量子逆フーリエ変換部と、
上記第１量子逆フーリエ変換部による演算で得られた上記第１レジスタおよび上記第２剰余演算部による演算で得られた上記第２レジスタに対して、
（１）各上記計算量子ビットｘk（ｋ∈｛１，２，…，ｎ｝）について、第ｋ計算量子ビットｘkを制御ビットとして、制御ビットの状態が|1>のときのみ、上記第２レジスタ|y>に対して演算Ｕ-a,N（ただし、演算Ｕ-a,Nは
【数５３】
0005351862.tif 000054
で定義される）を２2(n-k)回施し、
（２）ｎ−１個の上記計算量子ビットｘk（ｋ∈｛ｎ−１，ｎ−２，…，１｝）それぞれについて、第ｋ計算量子ビットｘkと第ｈ計算量子ビットｘh（ただし、ｈはｋ＜ｈ≦ｎを満たす整数である）を制御ビットとし、各整数ｈについて、制御ビットの状態が共に|1>のときのみ、上記第２レジスタ|y>に対して上記演算Ｕ-a,Nを２2n-k-h+1回施す
第３剰余演算部と、
上記第３剰余演算部による演算で得られた上記第１レジスタに対して、量子逆フーリエ変換
【数５４】
0005351862.tif 000055
を適用する第２量子逆フーリエ変換部と
を備える量子演算装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、量子演算方法、量子演算装置に関する。より詳しくは、多項式時間で離散対数問題を解く量子演算方法、量子演算装置に関する。
【背景技術】
【０００２】
1994年、Shorは量子コンピュータ上で動作する高速な素因数分解アルゴリズムと離散対数問題を解くアルゴリズムを提案した（非特許文献１）。
【０００３】
Shorの素因数分解アルゴリズムは、素因数分解が位数を求める問題に古典的に帰着できることを利用している。ここで、位数を求める問題とは「aとNが互いに素な正の整数のとき、at=1 mod Nを満たす最小の整数tを求める」という問題である。
【０００４】
他方、離散対数問題とは「bを整数、aとNが互いに素な正の整数のとき、at=b mod Nを満たす最小の整数tを求める」という問題である。位数を求める量子アルゴリズムと離散対数問題を解く量子アルゴリズムの違いは、前者が二つのレジスタを利用することに対して、後者が三つのレジスタを利用することである。このレジスタ数の違いは離散対数問題が変数bを扱うために生じるもので、離散対数問題を解くために必要な量子ビット（キュービット；quantum bit）の個数は位数を求めるために必要な量子ビットの個数の約1.5倍となる。ここで、量子ビットの個数は、全てのレジスタで使用される量子ビットである。
【０００５】
このような実情に鑑み、Shorの離散対数問題を解くアルゴリズムを改良し、量子フーリエ変換に相当する演算部分を一つの量子ビットを用いて実行する量子アルゴリズムが提案されている（非特許文献２）。しかし、この方式では、離散対数問題の答えを求めるために、量子アルゴリズムの実行を何度も繰り返す必要があり、効率性の観点ではShorの離散対数問題を解くアルゴリズムに劣る。
【０００６】
なお、量子計算や量子アルゴリズムなどについては、非特許文献３に詳しい。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】P. Shor, Algorithms for Quantum Computation: Discrete Logarithms and Factoring, Proc. of the 35th FOCS, pp. 124-134 (1994).
【非特許文献２】J. Proos and C. Zalka,  Shor's discrete logarithm quantum algorithm for elliptic curves, Quant. Inf. Comp. 3(4), pp. 317-344 (2003).
【非特許文献３】M. A. Nielsen and I. L. Chuang, "Quantum Computation and Quantum Information", Cambridge UniversityPress, 2000.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
本発明は、このような実情に鑑みて、二つのレジスタを用いて離散対数問題を解くための量子演算技術を提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明は、互いに素な正整数ａとＮ、整数ｂ（０≦ｂ＜Ｎ)、及び、ａr＝１ ｍｏｄ Ｎを満たす最小の整数ｒ（ただし、ｒは素数とする）が与えられているときに、ａt＝ｂ ｍｏｄ Ｎを満たす最小の整数ｔを求めるための量子演算技術であり、下記のような処理を行う。
【００１０】
まず、ｎをlog ｒ以上の所定の整数とし、ｍをlog Ｎ以上の所定の整数とし、ｎ個の計算量子ビットｘk（ｋ∈｛１，２，…，ｎ｝）からなる第１レジスタとｍ個の補助量子ビットｙj（ｊ∈｛１，２，…，ｍ｝）からなる第２レジスタについて、全ての計算量子ビットｘk（ｋ∈｛１，２，…，ｎ｝）の初期状態を|0〉とし、第１補助量子ビットｙ1の初期状態を|1〉とし、第ｊ補助量子ビットｙj（ｊ∈｛２，３，…，ｍ｝）の初期状態を|0〉とし、計算量子ビットの量子状態を|x>=|x１x２…xn>とし、補助量子ビットの量子状態を|y>=|y１y２…ym>とし、
【数１】
0005351862.tif 000002
とする。
【００１１】
第１レジスタに対して、量子フーリエ変換
【数２】
0005351862.tif 000003
を適用する（第１量子フーリエ変換処理）。
【００１２】
第１量子フーリエ変換処理で得られた演算結果に対して、
（１）各計算量子ビットｘk（ｋ∈｛１，２，…，ｎ｝）について、第ｋ計算量子ビットｘkを制御ビットとして、制御ビットの状態が|1>のときのみ、第２レジスタ|y>に対して演算Ｕ-a,N（ただし、演算Ｕ-a,Nは
【数３】
0005351862.tif 000004
で定義される）を２2(n-k)回施し、
（２）ｎ−１個の計算量子ビットｘk（ｋ∈｛ｎ−１，ｎ−２，…，１｝）それぞれについて、第ｋ計算量子ビットｘkと第ｈ計算量子ビットｘh（ただし、ｈはｋ＜ｈ≦ｎを満たす整数である）を制御ビットとし、各整数ｈについて、制御ビットの状態が共に|1>のときのみ、第２レジスタ|y>に対して演算Ｕ-a,Nを２2n-k-h+1回施す（第１剰余演算処理）。
【００１３】
第１剰余演算処理で得られた第１レジスタに対して、量子フーリエ変換
【数４】
0005351862.tif 000005
を適用する（第２量子フーリエ変換処理）。
【００１４】
第２量子フーリエ変換処理で得られた第１レジスタおよび第１剰余演算処理で得られた第２レジスタに対して、各計算量子ビットｘk（ｋ∈｛１，２，…，ｎ｝）について、第ｋ計算量子ビットｘkを制御ビットとし、制御ビットの状態が|1>のときのみ、第２レジスタ|y>に対して演算Ｕb＾2,N（ただし、演算Ｕb＾2,Nは
【数５】
0005351862.tif 000006
で定義される）を２k回施す（第２剰余演算処理）。
【００１５】
第２剰余演算処理で得られた第１レジスタに対して、量子逆フーリエ変換
【数６】
0005351862.tif 000007
を適用する（第１量子逆フーリエ変換処理）。
【００１６】
第１量子逆フーリエ変換処理で得られた第１レジスタおよび第２剰余演算処理で得られた第２レジスタに対して、
（１）各計算量子ビットｘk（ｋ∈｛１，２，…，ｎ｝）について、第ｋ計算量子ビットｘkを制御ビットとして、制御ビットの状態が|1>のときのみ、第２レジスタ|y>に対して演算Ｕ-a,N（ただし、演算Ｕ-a,Nは
【数７】
0005351862.tif 000008
で定義される）を２2(n-k)回施し、
（２）ｎ−１個の計算量子ビットｘk（ｋ∈｛ｎ−１，ｎ−２，…，１｝）それぞれについて、第ｋ計算量子ビットｘkと第ｈ計算量子ビットｘh（ただし、ｈはｋ＜ｈ≦ｎを満たす整数である）を制御ビットとし、各整数ｈについて、制御ビットの状態が共に|1>のときのみ、第２レジスタ|y>に対して演算Ｕ-a,Nを２2n-k-h+1回施す（第３剰余演算処理）。
【００１７】
第３剰余演算処理で得られた第１レジスタに対して、量子逆フーリエ変換
【数８】
0005351862.tif 000009
を適用する（第２量子逆フーリエ変換処理）。
【発明の効果】
【００１８】
Shorの離散対数問題を解くアルゴリズムは三つのレジスタを用いているが、本発明では、拡張Clifford群の性質を、離散対数問題を解くために或る特別な場合（後に示す式（１８））に限定することで得られる関係（後に示す式（２０））を、量子コンピュータ上で演算可能な２n次元複素ベクトル空間上の演算（後に示す式（２０’））に変形し、さらに多項式時間で量子演算可能な演算系列への置換を導入することによって、レジスタの数が二つになる（詳細は実施形態にて明らかにする）。このため、二つのレジスタを用いて離散対数問題を解くことが可能になる。
【図面の簡単な説明】
【００１９】
【図１】本発明である量子演算装置の実施形態の機能構成例を示す図。
【図２】回転角度τrの位相演算子を２乗する演算Ｖr,SPを表す量子回路。
【図３】図２に示される量子回路に含まれる量子演算の記法について図解した量子回路。
【図４】３個の計算量子ビットの場合の演算（Ｖr,SP）s＾(-1)の量子回路。
【図５】３個の計算量子ビットの場合の演算Ｖr,SPを２n次元複素ベクトル空間上で実行可能な量子回路。
【図６】図２に示す量子回路の最初の手順を２n次元複素ベクトル空間上で実行可能な量子回路。
【図７】図２に示す量子回路の残りの手順のうち任意のｋ番目の手順を２n次元複素ベクトル空間上で実行可能な量子回路。
【図８】ｎ個のユニタリ変換Ｒrjst（j=1，2，…，n）のテンソル積を２n次元複素ベクトル空間上で実行可能な量子回路。
【図９】３個の計算量子ビットの場合の実施形態を表す量子回路。
【発明を実施するための形態】
【００２０】
本発明は、拡張Clifford群の性質を利用することにより、量子コンピュータ上で離散対数問題の解を高い確率で求める。そこでまず、本発明の原理の説明に先立ち、拡張Clifford群の性質について概説する。
【００２１】
＜本発明の原理を理解するために資する従来技術＞
以下、本発明の原理を理解するために資する従来技術として、下記参考文献Ａに開示された成果の一部を概説する。証明等の詳細は参考文献Ａを参照されたい。
（参考文献Ａ）D. Appleby, "SIC-POVM and the Extended Clifford Group", J. Math. Phys. 46, 052107 (2005). arXiv:quant-ph/0412001
【００２２】
まず、Ｕ(d)を全てのｄ次元ユニタリ演算子からなる群とする。ｄは正整数である。また、Ｚを整数環とし、Ｚdを整数環ＺのイデアルｄＺによる剰余環とする。すなわち、Ｚd＝｛０，１，・・・，ｄ−２，ｄ−１｝である。Ｚ2は各要素が整数である２次元ベクトルの集合を表す。→ｐ＝（ｐ1，ｐ2）T∈Ｚ2、→ｑ＝（ｑ1，ｑ2）T∈Ｚ2としたとき（記号Ｔは転置を表す）、ブラケット記号〈・，・〉を式（１）の如く定義する。また、記号"→"は、記号"→"の次の文字の頭上に附されることを意味し、例えば→Ａは文字Ａの頭上に記号"→"が附された組み合わせ文字を表す。
【数９】
0005351862.tif 000010
【００２３】
|0>，|1>，・・・，|d-1>をｄ次元複素ベクトル空間Ｃdにおける正規直交基底とし、演算子Ｔ、Ｓ、Ｄ→pを式（２）−（４）のように定義する。記号ｉは虚数単位（imaginary unit）であり、ネピア数（Napier's constant;自然対数の底）ｅのｐ乗をexp(ｐ)の如く表す。
【数１０】
0005351862.tif 000011
【００２４】
このとき、全ての→ｐ＝（ｐ1，ｐ2）T∈Ｚ2，→ｑ＝（ｑ1，ｑ2）T∈Ｚ2に対して、式（５）−（７）が成り立つ。記号†はエルミート共役を表す。
【数１１】
0005351862.tif 000012
【００２５】
式（４）に定義される演算子Ｄ→pに関して、式（８）の定義を満たすｄ×ｄの行列を要素（元）とする群ＧＰ(d)を一般化Pauli群（Weyl-Heisenberg群）と呼ぶ。Ｒは実数体を表す。
【数１２】
0005351862.tif 000013
【００２６】
また、一般化Pauli群ＧＰ(d)に対する拡張Clifford群Ｃ(d)は、式（９）の定義を満たすｄ×ｄの行列を元とする群である。Ｕ†は、行列Ｕの共役転置行列である。
【数１３】
0005351862.tif 000014
【００２７】
また、ｄに関して、~ｄを式（１０）のように定義する。また、記号"~"は、記号"~"の次の文字の頭上に附されることを意味し、例えば~Ａは文字Ａの頭上に記号"~"が附された組み合わせ文字を表す。
【数１４】
0005351862.tif 000015
【００２８】
このとき、環Ｚ~d上の特殊線形群ＳＬ（２，Ｚ~d）は、行列式が１になる２×２行列全体の集合として与えられる（式（１１）参照）。
【数１５】
0005351862.tif 000016
【００２９】
式（１１）で与えられる特殊線形群ＳＬ（２，Ｚ~d）の元のうち、βが０以外の値であり且つβが~ｄと互いに素である（ゆえに逆元β−１∈Ｚ~dが存在する）行列を、prime matrixという。なお、逆元β−１の算出は一次合同式β−１β≡１（mod ~d）の解法として古典的知識であるから説明を省略する。
【００３０】
〔補題１〕
拡張Clifford群Ｃ(d)に属する任意のユニタリ演算子Ｕ∈Ｃ(d)について、全ての→ｐ∈Ｚ2に対して式（１２）を満たすＦ∈ＳＬ（２，Ｚ~d），→Ω∈（Ｚd）2が存在する。
【数１６】
0005351862.tif 000017
【００３１】
〔補題２〕
Ｆをprime matrix((α，γ)T，(β，δ)T)∈ＳＬ（２，Ｚ~d）とし、演算子ＶFを式（１３）のように定義する。このとき、演算子ＶFは、全ての→ｐ∈Ｚ2に対して式（１４）を満たす拡張Clifford群Ｃ(d)に属するユニタリ演算子である。
【数１７】
0005351862.tif 000018
【００３２】
〔補題３〕
Ｆをprime matrixではない２×２行列((α，γ)T，(β，δ)T)∈ＳＬ（２，Ｚ~d）とする。このとき、δ＋ｘβが０以外の値であり且つδ＋ｘβが~ｄと互いに素である整数ｘが存在し、Ｆ1＝((0，1)T，(-1，x)T)，Ｆ2＝((γ＋ｘα，−α)T，(δ＋ｘβ，−β)T)とすると、Ｆ1とＦ2はそれぞれprime matrix∈ＳＬ（２，Ｚ~d）であり、Ｆ＝Ｆ1Ｆ2を満たす。
【００３３】
〔補題４〕
Ｆ∈ＳＬ（２，Ｚ~d），→Ω∈（Ｚd）2とせよ。Ｕを、拡張Clifford群Ｃ(d)に属する任意のユニタリ演算子Ｕ∈Ｃ(d)とする。もしＦがprime matrixならば式（１５）が成立し、もしＦがprime matrixでないならばＦ＝Ｆ1Ｆ2を満たすprime matrix Ｆ1とprime matrix Ｆ2を選択する（補題３参照）ことにより式（１６）が成立する。しからば、全ての→ｐ∈Ｚ2に対して式（１７）が成立する。ＶF，ＶF1，ＶF2については式（１３）を参照せよ。
【数１８】
0005351862.tif 000019
【００３４】
補題４から、拡張Clifford群の任意の要素（ユニタリ演算子）Ｕは、せいぜい２つのＶFと１つのＤ→Ωを使って表現できることが分かる。
【００３５】
＜本発明の原理＞
本発明では、既述の拡張Clifford群の性質を、離散対数問題の解を求めるために応用する。離散対数問題は、前述の通り、「bを整数、aとNが互いに素な正の整数のとき、at=b mod Nを満たす最小の整数tを求める」問題である。ここで、ar=1 mod Nを満たす最小の整数rが既に与えられているものとする（この数rは、Shorのアルゴリズムにより求まる）。なお、この前提は従来のShorの離散対数問題を求めるアルゴリズムにおける前提条件と同じである（非特許文献３のp.238を参照）。
【００３６】
以下の説明では、ｒは素数と仮定する。なお、ｒが素数でない場合であっても、この離散対数問題はｒが素数の場合に帰着することができる（ｒが合成数である場合、ｒを素因数分解して素因子を求めればよい。素因数分解の量子アルゴリズムとして例えば既述のShorの素因数分解アルゴリズムを用いることができる。もちろん数体ふるい法などの古典的手法により合成数ｒの素因数分解を行ってもよい）。
【００３７】
まず、既述の拡張Clifford群の説明におけるｄについてｄ＝ｒとする。ｒは、既述の通り、離散対数問題において予め与えられている「ar=1 mod Nを満たす最小の整数ｒ」である。
【００３８】
本発明では、補題２におけるprime matrix Ｆと→ｐを式（１８）に示すＦS，→ｐsとすることが主要な特徴の一つである。
【数１９】
0005351862.tif 000020
【００３９】
補題２のＦ＝((α，γ)T，(β，δ)T)において、α＝ｓ−１，β＝１，γ＝１，δ＝０とおいたものが式（１８）のＦｓである。ここで、ｓ−１はｓ・ｓ−１＝１ ｍｏｄ ｒを満たす整数である（逆元ｓ−１は例えばフェルマーの小定理などによって計算可能である）。
【００４０】
補題４において、Ｆを式（１８）のprime matrix Ｆsとし、→Ω＝（０，０）Tを代入すると、すべてのｓ＝１，２，・・・，ｒ−１に対して式（１９）が成立する。
【数２０】
0005351862.tif 000021
【００４１】
ここで、ＶＦｓとＶ→ｐｓは以下の通りである。
【数２１】
0005351862.tif 000022
【００４２】
すると、任意の整数ｓ（１≦ｓ≦ｒ−１）に対して式（２０）が成立する。
【数２２】
0005351862.tif 000023
【００４３】
したがって、式（２０）の演算を量子コンピュータ上で実現することができれば、演算結果の状態|t>を観測することによって、離散対数問題の答えｔが分かる。なお、ここでの|0>は、ｒ次元複素ベクトル空間上の基底の１つであり、式（２０）のＤFs→psおよびＶFsおよびＶ→psは、いずれもｒ次元複素ベクトル空間上のユニタリ演算である。
【００４４】
〔量子コンピュータ上の演算の基本的な性質〕
ここで、量子コンピュータにおける演算の基本的な事項について説明する。通常、量子コンピュータにおける情報の基本単位を「量子ビット」と呼ぶ。現在のコンピュータにおける「ビット」に相当するものである。第ｊ量子ビットの状態|xj>は、|0>，|1>の二値の重ね合わせ状態で表わされる（式（２１）参照）。
【数２３】
0005351862.tif 000024
【００４５】
ｐ0とｐ1は確率振幅と呼ばれ、|ｐ0|2＋|ｐ1|2＝１を満たす複素数であり、この量子状態を観測すると確率|ｐ0|2で|0>、確率|ｐ1|2で|1>の状態が得られる。量子状態は、式（２１）の右辺に示されるように、確率振幅を要素に持つ２次元複素ベクトルで表わされる。或る量子状態ｐ0|0>＋ｐ1|1>から別の量子状態ｐ0'|0>＋ｐ1'|1>に変換する量子コンピュータ上の演算Ｕは、式（２２）で表される。
【数２４】
0005351862.tif 000025
【００４６】
|ｐ0|2＋|ｐ1|2＝１かつ|ｐ0'|2＋|ｐ1'|2＝１なので、この演算Ｕは、２次元複素ベクトル空間Ｃ2上で全てのベクトルの位置関係を保ったまま同じように回転させる演算（ユニタリ演算）となる。
【００４７】
ｎ量子ビットの量子状態|x>は、式（２３）のようなテンソル積で表わされ、２ｎ次元複素ベクトルとなる。よって、ｎ量子ビットに対する演算は２ｎ次元複素ベクトル空間上のユニタリ演算となる。
【数２５】
0005351862.tif 000026
【００４８】
このように、量子コンピュータ上の演算は、２ｎ次元複素ベクトル空間上のユニタリ演算である。したがって、ｒが２のベキ乗でない場合、式（２０）の演算を量子コンピュータで実行するためには、２ｎ次元複素ベクトル空間上のユニタリ演算で式（２０）のＤFs→ps、または、ＶFsおよびＶ→psを近似する必要がある。ここで、ｎ≧┌log r┐である。記号┌・┐は天井関数（ceiling function）であり、ｎはlog r以上の最小の整数以上の整数とされる。
【００４９】
そこで、本発明では、式（２０）の第２項の各演算を、量子コンピュータ上で効率的に実行できる２ｎ次元複素ベクトル空間上のユニタリ演算で近似することを考える。
【００５０】
まず、式（２０）の第２式に含まれるＶFsを量子コンピュータ上で実現する方法について説明する。最初に、以下の演算を定義する。ここで、|x>は式（２３）で表されるｎ量子ビットからなる量子状態を表す。式（２４）は、周知のｎ量子ビットの量子フーリエ変換（Quantum Fourier Transfrom）の逆変換である。また、式（２５）は、角度τｒの位相演算子を２乗する（Square Phase）演算である。
【数２６】
0005351862.tif 000027
【００５１】
これらを用いると、式（１３’）で表されるＶFsを、式（２６）により近似することができる。
【数２７】
0005351862.tif 000028
【００５２】
次に、式（２０）の第２式に含まれるＤ→psは、式（４’）の定義から分かるように、量子ビットの順番を１つずつ繰り上げる（第ｋ量子ビットを第ｋ＋１量子ビットとし、第ｎ量子ビットについては第１量子ビットに繰り上げる）巡回シフト演算を、ｓｔ回繰り返す演算である。しかし、ｓとｔは未知数であるため繰り返し回数が分からない。つまり、単純にシフトオペレーションを実行することができないので、Ｄ→psを式（２７）のように変形する。ここで、ＱＦＴ2＾(n)は、式（２４）の逆変換、つまり、量子フーリエ変換である。なお、２＾(n)は２nを表す。なお、式（２７）に現れるＲrについては後述する式（３１）を参照されたい。
【数２８】
0005351862.tif 000029
【００５３】
式（２６）、式（２７）を式（２０）に代入すると、本発明の課題を解決するためには、式（２０’）の計算を量子コンピュータ上で効率的に（多項式時間で）行うことができればよいことが分かる。
【数２９】
0005351862.tif 000030
【００５４】
既述のように、ＱＦＴ2＾(n)は周知の量子フーリエ変換であり、ＱＦＴ2＾(n)†はその逆変換（量子逆フーリエ変換）なので、それぞれ量子コンピュータ上で効率的に実行できることが知られている〔非特許文献３の５．１節〕。あとは、式（２０’）の（Ｖr,SP）s^(-1)とΛrで表される演算が、量子コンピュータ上で効率的に実行できればよいことがわかる。
【００５５】
そこでまず、Ｖr,SPについて考える。^xの２進数表現を^x 1^x 2…^x nとする。１０進数表現では式（２８）が成り立つ。ここで記号"＾"は、記号"＾"の次の文字の頭上に附されることを意味し、例えば＾Ａは文字Ａの頭上に記号"＾"が附された組み合わせ文字を表す。この記号はべき乗を表す記号"＾"と同じであるが、文脈よりその区別は可能である。
【数３０】
0005351862.tif 000031
【００５６】
すると、式（２９）および式（３０）が成立する。
【数３１】
0005351862.tif 000032
【００５７】
ゆえに、入力状態|^x>=|^x1^x2…^xn>に対して、図２に示される量子回路に従った演算系列を施せば、Ｖr,SPの演算を実現できることが分かる。なお、図２では、入力の量子ビットを単にｘk（ｋ＝１，２，…，ｎ）と表記しているが、このｘkが^xkに対応すると思えばよい。
【００５８】
ここで、図２に表れる単一量子ビットゲートないし制御ゲートに現れる記号Ｒrjは、式（３１）で定義されるユニタリ変換Ｒrをｊ回繰り返すことを表している。
【数３２】
0005351862.tif 000033
【００５９】
また、図２において、第３列目以降の演算は、図３に示すようなcontrolled-Ｒrjの演算系列を省略表記したものである。よって、図２に示す演算は、controlled-Ｒrjの系列で表わされることが分かる。
【００６０】
式（２０’）における演算（Ｖr,SP）s＾(-1)は、Ｖr,SPをｓ-1回繰り返すことを意味する。ここで、Ｖr,SPを実現する各演算（図２のＲrjおよびcontrolled-Ｒrj）が可換であることを考慮すると（このことは、Ｒrjおよびcontrolled-Ｒrjが対角行列で表せる演算であることから容易に分かる）、Ｖr,SPをｓ-1回繰り返すことは、図２に示される各演算をｓ-1回繰り返すこと、つまり、図２のＲrjおよびcontrolled-ＲrjをＲrj・s＾(-1)およびcontrolled-Ｒrj・s＾(-1)に置き換えることと等価である。
【００６１】
しかし、変数ｓの値は未知数なので、この状態では回転角度Ｒrj・s＾(-1)が決まらないため、まだ量子コンピュータ上で実行することができない。
【００６２】
なお、（Ｖr,SP†）s＾(-1)は（Ｖr,SP）s＾(-1)の逆変換なので、Ｖr,SPの演算系列を逆順に実行すればよい。ただし、既述の通り、Ｖr,SPを構成する各演算は可換なので、Ｖr,SP†とＶr,SPは等価であり、同じ演算系列で実行できる。
【００６３】
同様に、式（２０’）のΛrは、第ｊ量子ビットに対して、Ｒrを２j・ｓ・ｔ回繰り返す演算の系列である。ｓとｔは未知数なので、Λrもこの状態では実行することができないことが分かる。
【００６４】
そこで、Shorのアルゴリズムで知られている考え方〔非特許文献３のp.227〕を応用して補助量子ビット（第２レジスタ）を導入し、ｓの情報を補助量子ビットに持たせることにより、（Ｖr,SP）s＾(-1)とΛrを、ｓに依存せずに実行できる演算に変換する方法を考案した。
【００６５】
まず、式（３２）と式（３３）のように、演算Ｕ-a,NとＵb＾2,Nを定義する。
【数３３】
0005351862.tif 000034
【００６６】
ここで、ａとＮは離散対数問題で与えられている互いに素な整数であり、-a=a(N-1) mod Nである。
【００６７】
全てのｓ＝０，１，・・・，２ｒ−１に対して、式（３４）の状態を定義する。
【数３４】
0005351862.tif 000035
【００６８】
すると、（τrs,|us>）が、演算Ｕ-a,Nの固有値と固有ベクトルの組になることが分かる。同様に、（τr2st,|us>）は、演算Ｕb＾2,Nの固有値と固有ベクトルの組である。すると、Shorのアルゴリズムの場合と同様に、Ｒrj・s＾(-1)を入力|us>に対するcontrolled-Ｕ-a,Nで置き換え、Ｒr2・s・tを入力|us>に対するcontrolled-Ｕb＾2,Nに置き換えることができる。
【００６９】
まず、Ｒrj・s＾(-1)をcontrolled-Ｕ-a,Nで置き換える方法について説明する。置き換えの関係を図６に示す。
【００７０】
置き換え前の第ｋ量子ビットに対する演算Ｒrf1(k)・s＾(-1)（f1(k)＝２2(n-ｋ)）は、第１レジスタの第（ｎ−ｋ＋１）量子ビットを制御ビットとし、第２レジスタ全体にＵ-a,Nf1(k)を適用する演算に置き換える。つまり、図６の左側の回路で示されるＲrf1(k)・s＾(-1)（ｋ＝１，２，・・・，ｎ）の系列は、以下の〔規則１〕の演算系列に置き換えられる。なお、以下では表記を簡潔にするため、ｎ−ｋ＋１→ｋと置き換えて説明している。
【００７１】
〔規則１〕
第１レジスタの第ｋ量子ビットを制御ビットとし、制御ビットの状態が|1>のときのみ、第２レジスタ|y>全体に式（３２）の演算を２2(k-1)回施す。これを、全ての計算量子ビット（ｋ＝１，２，・・・，ｎ）に対して行う。なお、この演算は可換なので、演算順序は任意の順序でよい。
【００７２】
controlled-Ｒrj・s＾(-1)の系列は、controlled-controlled-Ｕ-a,Nの系列に置き換える。この置き換えの関係を図７に示す。
第ｋ量子ビットを制御ビット、第ｈ量子ビットを標的ビットとするcontrolled-Ｒrf2(k,h)・s＾(-1)は、第１レジスタの第（ｎ−ｋ＋１）量子ビットと第（ｎ−ｈ＋１）量子ビットを制御ビットとし、第２レジスタ全体にＵ-a,Njを適用する演算に置き換える。このとき、f2(k,h)=2(n-k+1)+(n-h+1)-1である。
図２に示されるように、controlled-Ｒrf2(k,h)・s＾(-1)の系列は、制御ビットｋ＝２，３,・・・，ｎに対して、標的ビットｋ＜ｈ≦ｎを満たす全ての（ｋ，ｈ）の組からなる。よって、図７の左側の回路で示されるcontrolled-Ｒrf2(k,h)・s＾(-1)の系列は、以下の〔規則２〕の演算系列に置き換えられる。〔規則１〕と同様に表記を簡潔にするため、ｎ−ｋ＋１→ｋ，ｎ−ｈ＋１→ｈに置き換えている。
【００７３】
〔規則２〕
第１レジスタの第ｋ量子ビットと第ｈ量子ビット（ただし、ｋ＜ｈ≦ｎ）を制御ビットとし、制御ビットの状態が共に|1>のときのみ、第２レジスタ|y>全体に式（３２）の演算を２k+h-1回施す。これを、全てのｋ＝ｎ−１，ｎ−２，・・・，１に対して行う。なお、この演算は可換なので、演算順序は任意の順序でよい。
【００７４】
３量子ビットの場合の（Ｖr,SP）s＾(-1)の量子回路を図４に示す。これを上記のように置き換えると、図５のようになる。図４の丸囲み数字１〜６のゲートは、ぞれぞれ図５の丸囲み数字１〜６に対応する。
【００７５】
次に、Λrを実現する第ｋ量子ビットに対する演算Ｒrf3(k)・stを、controlled-Ｕb＾2,Nに置き換える方法を説明する。ここで、f3(k)=2kである。置き換えの関係を図８に示す。置き換え前の第ｋ量子ビットに対する演算Ｒrf3(k)・stは、第１レジスタの第ｋ量子ビットを制御ビットとし、第２レジスタ全体にＵb^2,Nf1(k)を適用する演算に置き換える。つまり、図８の左側の回路で示されるＲrf3(k)・stの系列は、以下の〔規則３〕の演算系列に置き換えられる。
【００７６】
〔規則３〕
第１レジスタの第ｋ量子ビットを制御ビットとし、制御ビットの状態が|1>のときのみ、第２レジスタ|y>全体に式（３３）の演算を２k回施す。これを、全ての計算量子ビット（ｋ＝１，２，・・・，ｎ）に対して行う。なお、この演算は可換なので、演算順序は任意の順序でよい。
【００７７】
上述の置き換えは、固有ベクトル|us>に対して式（３４）が成り立つことを利用して得られるものなので、本来は、置き換えた後の図９のような量子回路（ただし、図９は第１レジスタが３量子ビットの場合の例である）で正しい解を得るためには、第２レジスタの入力状態が|us>でなければならない。しかし、Shorのアルゴリズムの場合（非特許文献３のp.227式(5.44))と同様に、式（３５）が成り立つので、入力状態|us>の代わりに入力状態|1>に対して計算を行えば十分であることが分かる。
【数３５】
0005351862.tif 000036
【００７８】
したがって、第２レジスタの入力状態はｓの情報を知っておく必要はなく、図６〜８のように置き換えた後の全ての演算は、変数ｓの値に依存することなく量子コンピュータ上で実現することができるようになる。
【００７９】
また、Shorのアルゴリズムの場合と同様に、式（３４）においてｕsがＮ以上の場合は、０≦ｕs≦Ｎ−１における作用の繰り返しとなるので、第２レジスタの量子ビットの数ｍは、少なくとも０≦ｕs≦Ｎ−１を表現できる数が必要となる。よって、ｍはｍ≧┌log Ｎ┐を満たす所定の整数である。
【００８０】
なお、図６〜１０で用いられているcontrolled-Ｕ-a,Nとcontrolled-controlled-Ｕ-a,Nとcontrolled-Ｕb＾2,Nの演算は、剰余演算として周知の演算であり、Beauregardらによって量子コンピュータ上で効率的に実行できる演算系列に分解できることが知られている（参考文献Ｂ、参考文献Ｃ）。
（参考文献Ｂ）S. Beauregard, "Circuit for Shor's algorithm using 2n+3 qubits", Quant. Inf. Comp. 3, 2, 175-185 (2003); quant-ph/0205095.
（参考文献Ｃ）高橋康博, "Shor のアルゴリズムのための効率的な量子回路", 情報処理学会会誌「情報処理」, Vol. 47 No. 12, pp. 1323-1328, 2006.
【００８１】
以上より、図９の量子回路に示される演算系列を実行することにより式（２０’）を量子コンピュータ上で実現できる。ただし、図９は第１レジスタが３量子ビットの場合の例である。なお、行列演算の性質上、入力状態|0>に近い演算から順に実行されるため、図９の量子回路に示される演算の順序は式（２０’）とは逆順になっていることに注意する。
【００８２】
また、図９の（Ｖr,SP†）s＾(-1)に相当する量子回路の部分をみると、図５と制御ビットの位置が異なっていることが分かる。これは、量子フーリエ変換を実行すると、量子ビットの順序が逆順になる（非特許文献３の５節）ことによるものである。つまり、図９では、最初のＱＦＴ8を実行することで、出力される第１レジスタの量子ビットの順序は、上から（ｘ3，ｘ2，ｘ1）の順序になる。このことを考慮すると、図９の（Ｖr,SP†）s＾(-1)に相当する量子回路は、図５の逆変換（ゲートの順序を逆順にしたもの）において、第１レジスタの量子ビットの順序を逆（上からｘ3，ｘ2，ｘ1の順）にしたものと同じであることが分かる。
【００８３】
続いて、（Ｖr,SP†）s＾(-1)の実行後にＱＦＴ8を実行するので、第１レジスタの量子ビットの順序が元に戻る。そして、Λrを実行した後、ＱＦＴ8†を実行することにより、再び量子ビットの順序が逆順になる（ｘ3，ｘ2，ｘ1）。よって、図９の（Ｖr,SP）s＾(-1)に相当する量子回路は、図５の第１レジスタの量子ビットの順序を逆（上からｘ3，ｘ2，ｘ1の順）にすれば同じになっていることが分かる。最後にＱＦＴ8†が実行されるので、出力される量子ビットの順序は入力時と同じ（ｘ1，ｘ2，ｘ3）の順である。
【００８４】
ＱＦＴの実行の度に、量子ビットの順序を元に戻すシフト演算を行うこともできる。しかし、式（２０’）では偶数個のＱＦＴが使用されるので、入力時と出力時の量子ビットの順序は同じとなるため、シフト演算を省略した方が、無駄な演算の数を減らすことができる。
【００８５】
このように、（Ｖr,SP†）s＾(-1)と（Ｖr,SP）s＾(-1)の実行時には、量子ビットの順序が入れ替わっていることを考慮すると、〔規則１〕と〔規則２〕は以下のように書き換えられる。
【００８６】
〔規則１’〕
第１レジスタの第ｋ量子ビットを制御ビットとし、制御ビットの状態が|1>のときのみ、第２レジスタ|y>全体に式（３２）の演算を２2(n-k)回施す。これを、全ての計算量子ビット（ｋ＝１，２，・・・，ｎ）に対して行う。なお、この演算は可換なので、演算順序は任意の順序でよい。
【００８７】
〔規則２’〕
第１レジスタの第ｋ量子ビットと第ｈ量子ビット（ただし、ｋ＜ｈ≦ｎ）を制御ビットとし、制御ビットの状態が共に|1>のときのみ、第２レジスタ|y>全体に式（３２）の演算を２(n-k+1)+(n-h+1)-1回施す。これを、全てのｋ＝ｎ−１，ｎ−２，・・・，１に対して行う。なお、この演算は可換なので、演算順序は任意の順序でよい。
【００８８】
〔本発明と従来技術との比較〕
従来の離散対数問題を解く手法は、上記説明と対比させて述べれば、補題２におけるprime matrix Ｆと→ｐを式（３６）に示すＦS，→ｐsのように定めた場合に相当する。
【数３６】
0005351862.tif 000037
【００８９】
よって、式（３７）が導かれる。
【数３７】
0005351862.tif 000038
【００９０】
既述の通り、ｓとｔは未知の変数である。したがって、状態|st>の観測結果からｔを決定することはできないので、Shorの離散対数問題を解くアルゴリズムでは、もう一つレジスタを用意してｓの値を得られるようにし、その後、状態｜ｓｔ〉の観測結果からｔの値を計算する手法を採っている。つまり、本発明と比較すると、sの値を観測できるようにするためのレジスタ（第３レジスタ）が余分に必要となる。本発明では、ｓに依存しない量子計算を行うので、レジスタの数を一つ減らすことができる。
【００９１】
また、本発明に拠ると、非特許文献１に開示されるアルゴリズムよりも少ない量子ビットで離散対数問題を多項式時間で解くことが可能であり、また、非特許文献２に開示されるアルゴリズムよりも少ない演算数で離散対数問題を多項式時間で解くことが可能である。
【００９２】
〔装置構成〕
本発明の実施形態に係る量子演算装置１の機能構成図を図１に示す。
この装置は、式（２０’）の左辺の演算を実行する装置である。ただし、Ｖr,SPとＶr,SP†とΛrは、既述の通りｎ個の計算量子ビット（第１レジスタ）に加えて、ｍ個の補助量子ビット（第２レジスタ）を用いることでｓに依存せずに実行できる演算（図６〜８）に変換したものを用いる。つまり、図９に例示されるような量子回路における演算系列を、左から順に実行する装置である。
【００９３】
入力部１００には、互いに素な正の整数ａとＮ、整数ｂ（０≦ｂ＜Ｎ)、及び、ar=1 mod Nを満たす最小の整数ｒが入力される。
【００９４】
量子演算装置１は二つのレジスタ（第１レジスタ８０１と第２レジスタ８０２）を有しており、第１レジスタ８０１はｎ個の計算量子ビットで構成され、第２レジスタ８０２はｍ個の補助量子ビットで構成されている。ただし、ｎはlog r以上の定められた整数であり、ｍはlog N以上の定められた整数とする。第ｋ番目の計算量子ビットをｘkとし、その量子状態を|xk>と表すこととする。同様に、第ｊ番目の補助量子ビットをｙjとし、その量子状態を|yj>と表す。テンソル積で表現すれば|x>=|x１x２…xn>，|y>=|y１y２…ym>である。
【００９５】
初期化部１００は、全ての計算量子ビットを|0>に初期化し（|xj>=|0>;j=0,1,…,n-1）、0番目の補助量子ビットの状態を|1>にし（|y0>=|1>）、それ以外の全ての補助量子ビットの状態を|0>に初期化する（k≠0のとき|yk>=|0>）。
【００９６】
第１量子フーリエ変換部２０１は、第１レジスタに量子フーリエ変換を適用する。この処理は式（２０’）におけるＱＦＴ2＾(n)の演算を実行する部分である。これは、周知の量子回路（非特許文献３の５．１節）により、量子コンピュータ上で実行することができる。
【００９７】
第１剰余演算部２０２は、式（２０’）における（Ｖr,SP†）s＾(-1)の演算を実行する部分である。具体的には、図２の各ゲートを〔規則１’〕及び〔規則２’〕で置き換えた演算を適用した演算（Ｖr,SP）s＾(-1)の逆演算を適用する。通常は、（Ｖr,SP）s＾(-1)を実現する量子回路の逆順に適用したものが逆変換（Ｖr,SP†）s＾(-1)の量子回路となる。ただし、〔規則１’〕及び〔規則２’〕の各演算は可換なので、この場合は（Ｖr,SP）s＾(-1)は（Ｖr,SP†）s＾(-1)と同じであると考えてよい。
【００９８】
よって、第１剰余演算部２０２は、以下の処理を行うことになる。
（１）第１レジスタの第ｋ計算量子ビットを制御ビットとし、制御ビットの状態が|1>のときのみ、第２レジスタ|y>全体に式（３２）の演算を２2(n-k)回施す演算を、全ての計算量子ビット（ｋ＝１，２，・・・，ｎ）に対して行う。
（２）第１レジスタの第ｋ計算量子ビットと第ｈ計算量子ビット（ただし、ｋ＜ｈ≦ｎ）を制御ビットとし、制御ビットの状態が共に|1>のときのみ、第２レジスタ|y>全体に式（３２）の演算を２(n-k+1)+(n-h+1)-1回施す演算を、全てのｋ＝ｎ−１，ｎ−２，・・・，１に対して行う。
【００９９】
なお、-a=a(N-1) mod Nである。ここで、各演算は可換であり、どの順序で適用しても結果に影響しないので、各演算の適用順序は任意に入れ替えることができる。
【０１００】
次に、第２量子フーリエ変換部３０１と第２剰余演算部３０２と第１量子逆フーリエ変換部３０３による処理を行うが、これは式（２７）のＤ→psの演算、つまり式（２０’）におけるＱＦＴ2＾(n)†・Λr・ＱＦＴ2＾(n)を実行する部分である。
【０１０１】
第２量子フーリエ変換部３０１は、第１レジスタ８０１に量子フーリエ変換を適用する。この量子フーリエ変換については第１量子フーリエ変換部２０１で実行する量子逆フーリエ変換と同じであるから重複説明を省略する。
【０１０２】
第２剰余演算部３０２は、〔規則３〕（図８）により置き換えられたΛrの演算を実行する部分である。具体的には、第１レジスタの第ｋ計算量子ビットを制御ビットとし、制御ビットの状態が|1>のときのみ、第２レジスタ|y>全体に式（３３）の演算を２k回施す演算を、全ての計算量子ビット（ｋ＝１，２，・・・，ｎ）に対して行う。
【０１０３】
第１量子逆フーリエ変換部３０３は、第１レジスタ８０１に量子逆フーリエ変換を適用する。これは、既述の量子フーリエ変換の演算を逆順に実行すればよいので、説明を省略する。
【０１０４】
第３剰余演算部４０１は、式（２０’）における（Ｖr,SP）s＾(-1)の演算を実行する部分である。既述の通り（Ｖr,SP）s＾(-1)と（Ｖr,SP†）s＾(-1)は同じ演算系列で実現できるので、第３剰余演算部は第１剰余演算部２０１と同様の処理を行えばよい。
【０１０５】
第２量子逆フーリエ変換部４０２は、第１量子逆フーリエ変換部３０３と同様の処理を行い、第１レジスタ８０１に量子フーリエ変換を施す。
【０１０６】
観測部５００は、第１レジスタ８０１の量子状態を観測する。
【０１０７】
位数計算部６００は、観測部５００が取得した値を用いてat=b mod Nを満たす最小の整数ｔ（位数ｔ）を計算する。第１レジスタ８０１の観測結果は式（３８）の値が高い確率で得られるので、従来のShorのアルゴリズムと同様に例えば連分数展開の手法を用いて位数ｔを求めることができる。
【数３８】
0005351862.tif 000039
【０１０８】
〔量子演算装置についての概説〕
次に、上述の量子回路に則って量子演算を行う量子演算装置について説明する。本発明の量子演算装置は、上述の量子回路から明らかなように、第１量子フーリエ変換部、第２量子フーリエ変換部、第１剰余演算部、第２剰余演算部、第３剰余演算部、第１量子逆フーリエ変換部、第２量子逆フーリエ変換部を少なくとも含む。各演算部および各変換部は、基本量子演算部（ＮＯＴ演算部、制御ＮＯＴ演算部、Toffoli演算部）により構成できる（上記非特許文献３参照）。なお、全ての演算は単一量子ビットに対する１量子ビット演算と制御ＮＯＴ演算に分解できる（上記非特許文献３参照）。
【０１０９】
量子演算装置は、量子コンピュータ単体で実現できる。量子コンピュータの実現する物理系としては、例えば、イオントラップを用いる方法（J. I. Cirac and P. Zoller, Quantum computations with cold trapped ions, Physical Review Letter 74;4091, 1995）、量子ビットとして光子の偏光や光路を用いる方法（Y. Nakamura, M. Kitagawa, K. Igeta, In 3-rd Proc. Asia-Pacific Phys. Comf., World Scientific, Singapore, 1988）、液体中の各スピンを用いる方法（Gershenfield, Chuang, Bulk spin resonance quantum computation, Science, 275;350, 1997）、シリコン結晶中の核スピンを用いる方法（B. E. Kane, A silicon-based nuclear spin quantum computer, Nature 393, 133, 1998）、量子ドット中の電子スピンを用いる方法（D. Loss and D. P. DiVincenzo, Quantum computation with quantum dots, Physical Review A 57, 120-126, 1998）、超伝導素子を用いる方法（Y. Nakamura, Yu. A. Pashkin and J. S. Tsai, Coherent control of macroscopic quantum states in a single-cooper pair box, Nature 393, 786-788, 1999）等を例示できる。また、それぞれの物理系に対する量子コンピュータの実現方法については、「http://www.ipa.go.jp/security/fy11/report/contents/crypto/crypto/report/QuantumComputers/contents/doc/qc_survey.pdf」や「M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, Cambridge UniversityPress, Chapter 7 Physical Realization」に詳しい。
【０１１０】
＜量子ビット＞
イオントラップ量子コンピュータでは、例えば、イオンの基底状態と励起状態を利用して量子ビットを実現する。また、核スピンを量子ビットとして用いる場合には、例えば、「T. D. Ladd, et al., "All-Silicon quantum computer," Phys. Rev. Lett., vol. 89, no. 1, 017901-1‐017901-4, July 1, 2002.」に記載されているようにＳｉ（１１１）基板等に各量子ビットを生成する。なお、量子ビットの初期量子状態は、例えば、他の演算の量子回路による操作によって得られたものを用いてもよいし、各量子ビットが生成された基板をｍＫ（ミリケルビン）オーダー以下に冷却してスピンの向きを揃えた後、所定の電磁波パルスを印加して生成してもよい。また、量子ビットとして光子の偏光を用いる場合には、例えば、パラメトリックダウンコンバージョン（ＰＤＣ：parametric down conversion）（例えば、「P. G. Kwiat, K. Mattle, H. Weinfurter, A. Zeilinger, A. V. Sergienko, and Y. Shih, “New high-intensity source of polarization-entangled photon pairs,” Phys. Rev. Lett. ,75:4337-4341, 1995.」「P. G. Kwiat, E. Waks, A. G. White, I. Appelbaum, and P. H. Eberhard, “Ultrabright source of polarization-entangled photons,” Phys. Rev. A, 60:R773-R776, 1999.」等参照。）によって生成された複数個の単一光子を用いる。この場合、各量子ビットの初期量子状態は、例えば、他の演算の量子回路による操作によって得られたものを用いる。また、パラメトリックダウンコンバージョン等によって生成された単一光子に、ビームスプリッタや偏光回転素子等によって実現されるウォルシューアダマール変換、ＣＮＯＴ、回転等の操作を行い、既述の初期量子状態を生成することとしてもよい。
その他、上記の文献に記載された方法で量子ビットを用意することとしてもよい。
【０１１１】
また、演算前後や演算途中において量子ビットの量子状態を保存する必要がある場合には、例えば、量子ドット内の電子準位、核スピン、あるいは超伝導体内部の電荷（クーパー対）量を量子ビットとして用いてデータを保存する量子メモリ等を用いてもよい（A.Barenco, D.Deutsch, and A.Ekert, Phys. Rev. Lett.74,4083(1995)、松枝秀明  電子情報通信学会誌  A Vol.J81-A No.12(1998)1978、T.H.Oosterkamp et.al., Nature 395,873(1998)、D.Loss and D.P. DiVincenzo, Phys. Rev. A57(1998) 120. T.Oshima, quant-ph/0002004, http://arxiv.org/abs/quant-ph/0002004、B.E.Kane, A silicon-based nuclear spin quantum computer, Nature, 393, 133(1998)、http://www.snf.unsw.edu.au/、Y.Nakamura, Yu. A. Pashkin and J.S.Tsai, Nature 398(1999)768）。
【０１１２】
＜ＣＮＯＴ演算＞
イオントラップ量子コンピュータでは、例えば、イオンを直線上に並べ、各イオンに狙いを定めたレーザービーム照射によってＣＮＯＴ演算を実現する。また、量子ビットとして光子の偏光を用いる場合には、例えば、偏光ビームスプリッタ等を用い、「T.B. Pittman, M.J. Fitch, B.C. Jacobs, J.D. Franson: “Experimental Controlled-NOT Logic Gate for Single Photons in the Coincidence Basis,” quant-ph/0303095, http://arxiv.org/abs/quant-ph/0303095」記載のPittman et al. 方式によってＣＮＯＴ演算を実現する。また、核スピンを量子ビットとして用いる場合には、例えば、所定の電磁波パルスを量子ビットに印加することによってＣＮＯＴ演算を実現できる。
その他、上記の文献に記載された方法でＣＮＯＴ演算を実現してもよい。
【０１１３】
＜量子ビット単体操作＞
イオントラップ量子コンピュータでは、例えば、イオンを直線上に並べ、各イオンに狙いを定めたレーザービーム照射によって量子ビット単体の操作を実現する。核スピンを量子ビットとして用いる場合には、電磁波パルスやレーザービーム照射によって各処理を実現する。また、量子ビットとして光子の偏光を用いる場合には、例えば、偏光回転素子等によって実現する。
【０１１４】
なお、本発明は既述の実施の形態に限定されるものではなく、その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。例えば、既述の可換な演算については演算の順序に限定がない。また、量子回路に使われる全ての演算は単一量子ビットに対する１量子ビット演算と制御ＮＯＴ演算に分解できるので（上記非特許文献３参照）、各変換部と各演算部の具体的構成についても種々等価な量子回路を構成できる。また、既述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【０１１５】
ところで、上述の量子回路に則って量子演算を行う手順自体は、古典コンピュータで決定することができる。上述の量子回路に則って量子演算を行う手順は、上述の量子回路を入力側から出力側に向かって順に行う各計算ステップである。
【０１１６】
具体的には、例えば図９に示した量子回路の例から明らかなように、式（２０’）の左辺の量子状態|0>に対する左からの各作用に対応する量子回路を作用の順番に従って量子回路の入力側から出力側に向かって並べることで、量子回路に則って量子演算を行う手順を決定できる。ただし、１計算ステップで並行演算可能であれば、これらの演算を並行するものを１手順とすればよい。換言すれば、この古典コンピュータは、図９に示した演算手順を決定して出力するものといえる。
【０１１７】
このような古典コンピュータ、つまり、上述の量子回路における量子演算の手順を決定する量子演算手順決定装置は、いわゆる古典的な装置構成で実現される。例えばパーソナルコンピュータに例示されるように、記憶装置（例えばＲＡＭ、ＲＯＭやハードディスク）、演算処理装置（例えばＣＰＵ）、入力・出力装置（例えばキーボード、ディスプレイ）、これらの装置間でデータのやり取りが可能に接続するバスなどを備えた古典コンピュータによって実現することができる。
【０１１８】
この場合、例えば図９の例のように、式（２０’）の左辺の量子状態|0>に対する左からの各作用に対応する量子回路における量子演算の手順をそれぞれ決定するための各プログラム、決定された手順を上記作用の順番に従って量子回路の入力側から出力側へ並べるためのプログラムを記憶装置に記憶しておき、必要に応じて演算処理装置がプログラムを読み込んで解釈実行することで、式（２０’）の左辺の量子状態|0>に対する左からの各作用に対応する量子回路における量子演算の手順をそれぞれ決定する各機能、決定された手順を上記作用の順番に従って量子回路の入力側から出力側へ並べる機能を実現する。また各プログラムは、コンピュータ読み取り可能な記録媒体（例えばＣＤ−Ｒ、ＤＶＤ−ＲＡＭ、ＭＯ）に記録することもできる。
【図１】
0005351862.tif 000056
【図２】
0005351862.tif 000057
【図３】
0005351862.tif 000058
【図４】
0005351862.tif 000059
【図５】
0005351862.tif 000060
【図６】
0005351862.tif 000061
【図７】
0005351862.tif 000062
【図８】
0005351862.tif 000063
【図９】
0005351862.tif 000064