(57)【要約】【課題】  量子探索処理におけるグローバルな演算を減らし、計算速度を向上し、エラー発生確率を低減させる。【解決手段】  入力部１１において検索対象値xの入力を受け付け、初期量子状態生成部において、計算ビットとアンチラビットの初期量子状態｜ψ0〉(×) ｜a0〉を生成する。また、操作部において、操作対象の量子状態｜ψj-1〉(×) ｜a0〉に対し、計算ビットとアンチラビットとに対するUx|y〉(×) ｜a0〉=G(×)Id|y〉(×) ｜a0〉（G:=exp(i・β｜x〉〈x｜)、−π<β=−βu・21-βd・π<0、βu及びβdは自然数）を満たす演算Ｕｘ｜y〉(×)｜m〉と、計算ビットのみに対するローカルな演算Ｕｓ（×）Ｉｄとを施す処理を繰り返す。【選択図】        図１
2006195558.tif 000002
【特許請求の範囲】
【請求項１】
N個のファイルを有するデータベースから所望のファイルを取り出す量子探索装置であって、
検索対象値xの入力を受け付ける入力部と、
jを自然数とし、｜ψj-1〉を計算ビットの量子状態とし、｜aj-1〉をアンチラビットの量子状態とし、(×)をテンソル積とした場合における、計算ビットとアンチラビットの初期量子状態｜ψ0〉(×) ｜a0〉を生成する初期量子状態生成部と、
量子状態｜ψj-1〉(×) ｜a0〉を保存する量子メモリと、
操作対象の量子状態｜ψj-1〉(×) ｜a0〉（最初の操作対象は初期量子状態｜ψ0〉(×) ｜a0〉）に対し、計算ビットとアンチラビットとに対するUx|y〉(×) ｜a0〉=G(×)Id|y〉(×) ｜a0〉（G:=exp(i・β｜x〉〈x｜)、−π<β=−βu・21-βd・π<0、βu及びβdは自然数）を満たす演算Ｕｘ｜y〉(×)｜m〉と、計算ビットのみに対するローカルな演算Ｕｓ（×）Ｉｄ（Ｉｄは無操作を示す）とを施し、当該演算後の量子状態｜ψj〉(×) ｜a0〉を次の操作対象として上記量子メモリに保存する処理を、所定回数繰り返す操作部と、
を有することを特徴とする量子探索装置。
【請求項２】
請求項１記載の量子探索装置であって、
上記操作部における処理が終了した後、上記量子メモリに保存されている計算ビットの量子状態｜ψjop〉を計算基底｜y〉で観測し、その観測値x0を出力する観測部と、
上記観測値x0が入力され、ｆ（x0）＝１であるか否かを判定し、その判定結果を出力する判定部と、
上記判定結果がｆ（x0）＝１でないことを示すものであった場合、上記初期量子状態生成部に上記初期量子状態｜ψ0〉(×) ｜a0〉を生成させ、その初期量子状態｜ψ0〉(×) ｜a0〉を上記量子メモリに保存させ、上記操作部における処理と上記観測部における処理と上記判定部における処理とを再び実行させる制御部と、
を有することを特徴とする量子探索装置。
【請求項３】
請求項１記載の量子探索装置であって、
上記初期量子状態｜ψ0〉(×) ｜a0〉が、
n=log2Nとし、
【数１】
2006195558.tif 000022
を満たす値とし、
h(y)を、ｙを２進表記したとき値が１となる桁の数とし、θを実数とした場合における、
【数２】
2006195558.tif 000023
であり、
上記演算Ｕｘ｜y〉(×)｜m〉が、
計算ビットとアンチラビットの量子状態に
【数３】
2006195558.tif 000024
の操作を施す演算であり、
上記演算Ｕｓ（×）Idが、
計算ビットの量子状態のみに
【数４】
2006195558.tif 000025
の操作を施す演算であり、
上記所定回数が、
jop:=［{π・2n/2/4sin(β/2)}+1/2］（［δ］はδの整数部分）である、
ことを特徴とする量子探索装置。
【請求項４】
請求項３記載の量子探索装置であって、
上記初期量子状態生成部が、
n個の計算ビットとβd個のアンチラビットの量子状態を｜0〉(×) ｜0〉とする初期化部と、
各計算ビットに対して１キュービット回転演算
【数５】
2006195558.tif 000026
を施す１キュービット回転演算と、
各アンチラビットに対して回転演算
【数６】
2006195558.tif 000027
（ｋ∈｛１,2,...,βd｝は各アンチラビットに一義的に対応する自然数）
を施す回転演算部と、
を有することを特徴とする量子探索装置。
【請求項５】
請求項３記載の量子探索装置であって、
上記βがβ≦−π／２である、
ことを特徴とする量子探索装置。
【請求項６】
N個のファイルを有するデータベースから所望のファイルを取り出す量子探索方法であって、
入力部において、検索対象値xの入力を受け付ける手順と、
初期量子状態生成部において、jを自然数とし、｜ψj-1〉を計算ビットの量子状態とし、｜aj-1〉をアンチラビットの量子状態とし、(×)をテンソル積とした場合における、計算ビットとアンチラビットの初期量子状態｜ψ0〉(×) ｜a0〉を生成し、これを量子メモリに保存する手順と、
操作部において、操作対象の量子状態｜ψj-1〉(×) ｜a0〉（最初の操作対象は初期量子状態｜ψ0〉(×) ｜a0〉）に対し、計算ビットとアンチラビットとに対するUx|y〉(×) ｜a0〉=G(×)Id|y〉(×) ｜a0〉（G:=exp(i・β｜x〉〈x｜)、−π<β=−βu・21-βd・π<0、βu及びβdは自然数）を満たす演算Ｕｘ｜y〉(×)｜m〉と、計算ビットのみに対するローカルな演算Ｕｓ（×）Ｉｄ（Ｉｄは無操作を示す）とを施し、当該演算後の量子状態｜ψj〉(×) ｜a0〉を次の操作対象として上記量子メモリに保存する処理を所定回数繰り返す手順と、
を有することを特徴とする量子探索方法。
【請求項７】
請求項６記載の量子探索方法であって、
上記操作部における手順の終了後、観測部において、上記量子メモリに保存されている計算ビットの量子状態｜ψjop〉を計算基底｜y〉で観測し、その観測値x0を出力する手順と、
判定部において、上記観測部における手順の後、ｆ（x0）＝１であるか否かを判定し、その判定結果を出力する手順を有し、
上記判定結果がｆ（x0）＝１でないことを示すものであった場合、制御部において、上記初期量子状態生成部における手順から判定部における手順までを再び実行させる、
ことを特徴とする量子探索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、量子ビットを用いた情報処理技術に関し、特に、未整理のファイルを格納したデータベースから所望のファイルを探索する量子探索装置及び量子探索方法に関する。
【背景技術】
【０００２】
古典的な計算機の場合、ソートされていないＮ個の値を有するデータベースの中から所望の値を見つけ出すためには平均（Ｎ／２）ステップ、すなわちＯ（Ｎ）ステップの試行を要する。なお、Ｏ（Ｎ）は、十分大きなＮに対してＮの定数倍以下であることを意味する（Ｏ記法）。これに対し、近年、量子的に動作する計算機を用い、Ｏ（√N）ステップの試行によってこの所望の値を見つけ出すことができる量子アルゴリズムが提唱された（例えば、非特許文献１参照）。以下、この非特許文献１の量子アルゴリズムについて説明する。なお、以下ではn=log2Nとし、xを探索する所望の値とする。
【０００３】
＜非特許文献１の量子アルゴリズム＞
［初期量子状態の生成］
まず、初期量子状態
【数７】
2006195558.tif 000003
を生成する。なお、｜δ〉は量子状態を示す縦ベクトルを意味し、｜δ〉(×)｜ε〉は｜δ〉と｜ε〉とのテンソル積を意味する。また、δ:=εはδをεと定義することを意味する。
また、この｜ψ0'〉の量子状態が存在するｎ個の量子ビットを計算ビット、｜a0'〉の量子状態が存在する１個の量子ビットをアンチラビットと呼ぶ。
【０００４】
この初期量子状態の生成は量子コンピュータの種類にもよるが基本的に以下のように行う。まず、一定の外場を与えた状態で量子メモリを十分に冷やすことで｜0〉(×) ｜0〉を得る。次にアダマール（Hadamard）演算
【数８】
2006195558.tif 000004
を全ての計算ビットに施すことで｜ψ0'〉(×) ｜0〉を得る。さらに回転演算
【数９】
2006195558.tif 000005
をアンチラビットに施すことで｜ψ0'〉(×) ｜a0'〉を得る。以上の操作を数式で示すと以下の関係式に還元される。
【数１０】
2006195558.tif 000006
｜ψ0'〉(×) ｜a0'〉=Uh' (×)Ua'｜0〉(×) ｜0〉
【０００５】
［所望の値xに対応する状態の確率増幅］
計算ビットとアンチラビットの両方を操作するオラクル演算
【数１１】
2006195558.tif 000007
と、計算ビットのみを操作する演算
Uψ':=1−2｜ψ0〉〈ψ0｜
とをそれぞれ
jop':=[(2n/2・π/4)+1/2]（[δ]はガウス記号でありδの整数部分を表す）
回だけ交互に繰り返す。これにより、観測された際、計算ビットが所望の値xに対応する状態｜x〉に縮退する確率が増幅される。なお、nが無限大の極限におけるこの確率は１になる。つまり、現実的に必要なほどに大きなnにおいては成功確率は十分に１に近い。なお〈δ｜は量子状態を示す縦ベクトルを意味する。
【０００６】
なお、この処理によってこの確率が増幅されるのは、
【数１２】
2006195558.tif 000008
が成り立つためである（例えば非特許文献１参照）。ここで｜〈x｜(Uψ'・G')jop'｜ψ0〉｜2は、所望xの値に対応する状態が観測される確率を表す。また、Ｇ'は計算ビットに作用する演算であって、
G':=exp(i・π・｜x〉〈x｜)=Id−2｜x〉〈x｜
で定義されるものを示す。なお、Idは無操作を意味する。またG'とUx'との間には
Ux'|y〉(×) ｜a0〉=G' (×)Id|y〉(×) ｜a0〉
の関係が成り立つ。
【０００７】
［観測］
次に計算基底｜y〉で計算ビットを観測する。これにより計算ビットの量子状態は１つの状態に縮退し、その状態が観測される。なおこの観測値をx0とする。
［判定］
観測値x0についてf(x0)=1であるか否かを判断する。ここでf(x0)=1であれば処理を終了し、f(x0)=1でなければ［初期量子状態の生成］に戻って処理をやり直す。
以上の量子アルゴリズムにより、古典的計算機による探索処理に比べ、二乗根のスピードアップが達成される。
【非特許文献１】L. K. Grover. Quantum Mechanics Helps in Searching for a Needle in a Haystack. Phys. Rev. Lett. 79(1997)325
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかし、非特許文献１の量子アルゴリズムでは、複数の量子ビットに跨る演算（グローバルな演算）を多数使用しているため、計算速度の向上が制約され、エラー発生確率も高くなってしまうという問題点がある。
一般にグローバルな演算は、１つの量子ビットの中で閉じている演算（ローカルな演算）に比べ、格段に計算時間が長く、エラーを発生させる確率も高い。つまり、グローバルな演算は量子ビット間の相互作用を用いて間接的に行われるが、その演算速度は量子ビット間の相互作用が大きいほど速くなる。しかし反面、量子ビット間の相互作用を大きくすると、意図していない量子ビットにまでこの相互作用の影響が及ぶ可能性が高くなり、エラー発生確率が高くなる。すなわち、グローバルな演算の場合、演算速度とエラー発生率とはトレードオフの関係にあり、演算速度の向上とエラー発生率の低減とをともに実現することはできない。これに対し、ローカルな演算はその量子ビットに対する外からの直接の操作のみによって実現可能であり、グローバルな演算のようなトレードオフの関係は存在しない。その結果、ローカルな演算の場合、エラー発生率を低く抑えつつ計算速度の向上を図ることができる。
【０００９】
そのため、グローバルな演算の数はなるべく減らしたほうがよい。しかし、非特許文献１の量子アルゴリズムでは、必要最低限のオラクル演算以外にもグローバルな演算（上述のアルゴリズムではUψ）を用いている。図８は、このUψの演算内容を説明するための概念図である。この図に示すように、Uψの演算は、ｎ個の計算ビット５１０−１〜ｎに対し、それぞれローカルにアダマール変換５２０−１〜ｎを施した後、量子ビット５１０−１〜ｎが｜０〉の量子状態を示している場合にのみ全ビットを反転させるグローバル演算５３０を施し、その後さらにローカルなアダマール変換５４０−１〜ｎを施す演算である。このように、Uψはグローバルな演算である。
【００１０】
本発明はこのような点に鑑みてなされたものであり、このようなグローバルな演算を減らし、計算速度を向上し、エラー発生確率を低減させることが可能な技術を提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明では、入力部において、検索対象値xの入力を受け付け、初期量子状態生成部において、jを自然数とし、｜ψj-1〉を計算ビットの量子状態とし、｜aj-1〉をアンチラビットの量子状態とし、(×)をテンソル積とした場合における、計算ビットとアンチラビットの初期量子状態｜ψ0〉(×) ｜a0〉を生成し、これを量子メモリに保存する。また、操作部において、操作対象の量子状態｜ψj-1〉(×) ｜a0〉（最初の操作対象は初期量子状態｜ψ0〉(×) ｜a0〉）に対し、計算ビットとアンチラビットとに対するUx|y〉(×) ｜a0〉=G(×)Id|y〉(×) ｜a0〉（G:=exp(i・β｜x〉〈x｜)、−π<β=−βu・21-βd・π<0、βu及びβdは自然数）を満たす演算Ｕｘ｜y〉(×)｜m〉と、計算ビットのみに対するローカルな演算Ｕｓ（×）Ｉｄ（Ｉｄは無操作を示す）とを施し、当該演算後の量子状態｜ψj〉(×) ｜a0〉を次の操作対象として上記量子メモリに保存する。なお、この操作部はこの処理を所定回数繰り返す。
【００１２】
ここで、操作部において行われる演算Ｕｓ（×）Ｉｄは、各量子ビットの中で閉じ、他の量子ビットに影響を及ぼさないローカルな演算である。このローカルの演算には、グローバルな演算の場合のような演算速度とエラー発生率とはトレードオフの関係はない。
また、Ux|y〉(×) ｜a0〉=G(×)Id|y〉(×) ｜a0〉を満たす演算Ｕｘ｜y〉(×)｜m〉を実行するために必要な時間は、基本的に非特許文献１におけるオラクル演算Ｕｘ'｜y〉(×)｜m〉を実行するために必要な時間とほぼ同じである。
【発明の効果】
【００１３】
以上のように、本発明では、従来グローバルな演算が行われていた計算ビットの操作を、演算速度とエラー発生率とにトレードオフの関係がないローカルの演算に置き換えることとしたため、計算速度の向上とエラー発生確率の低減とを実現することができる。
【発明を実施するための最良の形態】
【００１４】
以下、本発明の実施の形態を図面を参照して説明する。
〔記号・用語の定義〕
まず、使用する記号及び用語を定義する。
量子ビット（qubit）とは、量子情報処理における基本単位であり、古典的ビットの２値に対応する状態の任意の重ね合わせ状態をとるものをいう。なお、計算ビット及びアンチラビットはともに量子ビットである。また、重ね合わせ状態とは、古典的ビットの２値に対応する状態を同時にとることができる性質をいう。なお、この重ね合わせ状態は、古典的ビットの２値に対応する状態の線形結合で表現される。例えば、重ね合わせ状態にある１つの量子ビットの量子状態φ（状態ベクトル）は
φ=c1|0〉+c2|1〉  （c12+c22=1）  …(1)
のように表される。ここでc1,c2は、複素数で表される各量子状態の係数であり、その２乗がそれぞれの状態をとる確率を示す。
【００１５】
また、縮退とは、複数の量子状態の重ね合わせ状態が、それ以下の数の量子状態の重ね合わせ状態となること、或いは、いずれか１つの量子状態となることをいう。また、絡み合いの状態（エンタングルメント状態）とは、２つ以上の量子ビットが互いに相関を持ち、一方の量子ビットの量子状態が決まると、瞬時にもう他の量子ビットの量子状態が決まる性質を意味する。また、量子情報とは量子ビットで表現される情報を意味し、古典情報とは古典的ビット（２値ビット）で表現される情報を意味する。
【００１６】
また｜δ〉は量子状態を示す縦ベクトルを意味し、〈δ｜は量子状態を示す横ベクトルを意味する。例えば、式（１）の量子状態φは、さらに
【数１３】
2006195558.tif 000009
と表現できる。そして、量子状態｜０〉である確率c12及び量子状態｜1〉である確率c22は、それぞれ
c12=|〈0｜φ〉|2
c22=|〈1｜φ〉|2
と表現できる。なお〈δ｜ε〉は横ベクトル〈δ｜と縦ベクトル｜ε〉との内積を示す。
【００１７】
また、Idは操作を行わないこと（無操作）を意味し、iは虚数単位を意味し、δ:=εはδをεと定義することを意味する。また、[δ]はガウス記号でありδの整数部分を意味し、｜δ｜はδの絶対値を意味する。さらに、ｅｉ・ωはcosω＋i sinω（オイラーの関係式）を示し、expは自然対数の底（ネピア数）を示す。また、｜δ〉(×)｜ε〉は｜δ〉と｜ε〉とのテンソル積を意味し、ベクトル間及び行列間のテンソル積は以下のように例示される。
ベクトル間のテンソル積の例示：
【数１４】
2006195558.tif 000010
行列間のテンソル積の例示：
【数１５】
2006195558.tif 000011
【００１８】
〔量子探索装置の構成〕
図１は、本形態の量子探索装置１０の構成を示したブロック図である。なお、図１における実線の矢印は量子情報の流れを示し、破線の矢印は古典情報の流れを示すが、制御部１９に出入りする情報の流れは省略してある。
この図に例示するように、量子探索装置１０は、検索対象値xの入力を受け付ける入力部１１と、古典情報を保存する古典メモリ１２と、古典情報の演算を行う古典演算部１３と、計算ビットとアンチラビットの初期量子状態｜ψ0〉(×) ｜a0〉を生成する初期量子状態生成部１４と、量子状態｜ψj-1〉(×) ｜a0〉（ｊは自然数）を保存する量子メモリ１５と、操作対象の量子状態｜ψj-1〉(×) ｜a0〉に対し、計算ビットとアンチラビットとに対するUx|y〉(×) ｜a0〉=G(×)Id|y〉(×) ｜a0〉（G:=exp(i・β｜x〉〈x｜) =Id−(ei・β−1)｜x〉〈x｜、−π<β=−βu・21-βd・π<0、βu及びβdは自然数）を満たす演算Ｕｘ｜y〉(×)｜m〉と、計算ビットのみに対するローカルな演算Ｕｓ（×）Ｉｄとを施し、当該演算後の量子状態｜ψj〉(×) ｜a0〉を次の操作対象として量子メモリ１５に保存する処理を所定回数繰り返す操作部１６と、操作部１６における処理が終了した後、量子メモリ１５に保存されている計算ビットの量子状態｜ψjop〉を計算基底｜y〉で観測し、その観測値x0を出力する観測部１７と、観測値x0が入力され、ｆ（x0）＝１であるか否かを判定し、その判定結果を出力する判定部１８と、判定結果がｆ（x0）＝１でないことを示すものであった場合、初期量子状態生成部１４に初期量子状態｜ψ0〉(×) ｜a0〉を生成させ、その初期量子状態｜ψ0〉(×) ｜a0〉を量子メモリ１５に保存させ、操作部１６における処理と観測部１７における処理と判定部１８における処理とを再び実行させる制御部１９とを有している。なお、この制御部１９は、量子探索装置１０全体の制御も行う。また、初期量子状態生成部１４は、初期化部１４ａと１キュービット回転演算部１４ｂと回転演算部１４ｃとを有しており、操作部１６は、計算ビット操作部１６ａとオラクル演算部１６ｂとを有している。
【００１９】
なお、量子状態が｜ψj-1〉である量子ビットを計算ビットと呼び、量子状態が｜a0〉である量子ビットをアンチラビットと呼ぶものとする。さらに、λ(×)μ｜δ〉(×) ｜ε〉は、｜δ〉に演算λを施し、｜ε〉に演算μを施すことを意味する。すなわち、
λ(×)μ｜δ〉(×) ｜ε〉=λ｜δ〉(×) μ｜ε〉
が成り立つ。
また、上記の初期量子状態｜ψ0〉(×) ｜a0〉は、例えば、
【数１６】
2006195558.tif 000012
を満たす値であり、θは任意のパラメータ（実数）であり、h(y)はyを２進表記したとき値が１となる桁の数（例えば、h(0)=0, h(1)=1, h(2)=1, h(3)=2, h(4)=1, h(5)=2,h(6)=2,h(7)=3）である。
【００２０】
また、この例の場合、演算Ｕｓ（×）Ｉｄは、計算ビットの量子状態のみに
【数１７】
2006195558.tif 000013
のテンソル積である。
また、演算Ｕｘ｜y〉(×)｜m〉は、例えば、計算ビットとアンチラビットの量子状態に
【数１８】
2006195558.tif 000014
の操作を施す演算である。なお、式（５）は、Ux|y〉(×) ｜a0〉=G(×)Id|y〉(×) ｜a0〉を満たす演算である。
【００２１】
〔ハードウェア構成〕
次に、本形態の量子探索装置１０のハードウェア構成を例示する。
入力部１１は、例えば、各種データが入力される入力ポート、キーボード、マウス等であり、古典メモリ１２は、例えば、ハードディスク、ＭＯ（Magneto-Optical disc）、ＲＡＭ (Random Access Memory)等である。また、古典演算部１３、判定部１８及び測定部１９は、例えば、公知のＣＰＵ（Central Processing Unit）に所定のプログラムを実行させることにより構築されるものである。
【００２２】
初期量子状態生成部１４は、例えば、J. -L. Lim, et al., JAP84, 255(1998)」や「Phys. Rev. Lett. 2002」に記載された方法によって量子ビット（ｎ個の計算ビットとβｄ個のアンチラビット）が生成されたＳｉ（１１１）基板等のキュービット基板と、このキュービット基板を［ｍＫ（ミリケルビン）］オーダー以下に冷却可能な希釈冷却機等の冷却装置と、キュービット基板上の任意の位置にレーザ光を照射可能なレーザ光出射装置と、磁場発生装置とを有している。そして、この例の初期量子状態生成部１４は、冷却と磁場の制御とレーザ光の出射とによってキュービット基板上の量子ビットを操作する。
【００２３】
量子メモリ１５は、例えば、量子ドット内の電子準位、核スピン、あるいは超伝導体内部の電荷（クーパー対）量をキュービットとして用いてデータを保存する装置等を用いて実現できる（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、B.E.Kane, A silicon-based nuclear spin quantum computer, Nature, 393, 133(1998)、
1105419433421_26
、Y.Nakamura, Yu. A. Pashkin and J.S.Tsai, Nature 398(1999)768）。
【００２４】
操作部１６は、例えば、上述のキュービット基板と、レーザ光出射装置と、磁場発生装置とを有し、磁場の制御とレーザ光の出射とによってキュービット基板上の量子ビットを操作する。
観測部１７は、例えば、操作対象の量子ビットと同じ量子状態となる測定用の量子ビット列をキュービット基板上に数列生成し、それに対して核磁気共鳴プローブ法（MRFM）（例えば「Phys. Rev. Lett. 2002」参照。）等を適用して量子状態を測定する装置である。
【００２５】
なお、これらの構成は、シリコン結晶中の核スピンを量子ビットとして用いる場合の例であるが、量子ビットとして、例えば液体中の核スピン（Gershenfield, Chuang, Bulk spin resonance quantum computation, Science, 275;350, 1997）、イオントラップ（J. I. Cirac and P. Zoller, Quantum computations with cold trapped ions, Physical Review Letter 74;4091, 1995）、量子ドット中の電子スピン（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-cooperpair box, Nature 393, 786-788, 1999）、光子（Y. Nakamura, M. Kitagawa, K. Igeta, In 3-rd Proc. Asia-Pacific Phys. Comf., World Scientific, Singapore, 1988）等を量子ビットとしてもよい。この場合、初期量子状態生成部１４、初期量子状態生成部１６及び観測部１７は、例えば、「M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, Chapter 7 Physical Realization」に記載された量子コンピュータを所定のプログラムに従って制御することによって実現できる。
【００２６】
〔処理〕
図２は、本形態における量子探索装置の処理の全体を説明するためのフローチャートである。また、図３（ａ）は、図２のステップＳ１の詳細を、図３（ｂ）は図２のステップＳ３の詳細を、それぞれ説明するためのフローチャートである。さらに、図４は、図２のステップＳ４の詳細を説明するためのフローチャートである。以下、これらの図を用い、本形態における量子探索装置の処理について説明する。なお、以下では、式（２）の初期量子状態｜ψ0〉(×) ｜a0〉、式（４）の演算Ｕｓ（×）Ｉｄ及び式（５）の演算Ｕｘ｜y〉(×)｜m〉を用いた場合を例にとって説明するが、本発明はこれに限定されない。
【００２７】
＜パラメータの設定・保存（ステップＳ１）＞
前処理として、各種パラメータの設定・保存を行う。具体的には、例えば、入力部１１において、n=log2Nを満たすn（Nはデータベースのファイル数）、−π<β=−βu・21-βd・π<0を満たすβと、自然数βu，βdと、任意のパラメータθと、g(n)>0及び
【００２８】
【数１９】
2006195558.tif 000015
を満たす関数g(n)との入力を受け付け、これらを古典メモリ１２に格納する（ステップＳ１１）。なお、βはβ≦−π／２であることが望ましい。また、関数g(n)は値域ができるだけ小さくなるものが望ましく、１以下であることがより望ましい。ステップＳ５で計算ビットの量子状態を観測した際、所望の値が得られる確率が高くなるからである。
次に、古典演算部１３が、古典メモリ１２からβ，θ，g(n)を読み出し、式（３）を満たすαを数値的に求め、これを古典メモリ１２に格納する（ステップＳ１２）。
【００２９】
なお、ステップＳ１の処理は、必ずしも毎回実行する必要はなく、データベースを設定する際やその条件の見直しを行う際にのみ実行することとしてもよい。
＜検索対象値xの入力（ステップＳ２）＞
入力部１１において、検索対象となる値x（検索対象値）の入力を受け付け、入力された検索対象値xを古典メモリ１２に格納する。
＜初期量子状態｜ψ0〉(×) ｜a0〉の生成・保存（ステップＳ３）＞
初期量子状態生成部１４において、式（２）に示した初期量子状態初期量子状態｜ψ0〉(×) ｜a0〉を生成し、これを量子メモリ１５に格納する。この処理は何を量子ビットとするかによって異なるが、例えば、基本的には以下のようになる。
【００３０】
まず、初期化部１４ａにおいてｎ個の計算ビットとβｄ個のアンチラビットの量子状態を｜0〉(×) ｜0〉と初期化し、その量子状態を量子メモリ１５に保存する（ステップＳ３１）。具体的には、例えば、量子ビットが核スピンである場合、初期化部１４ａは、ｎ個の計算ビットとβｄ個のアンチラビットが形成されたキュービット基板に一定の外場を与えた状態でこれを数ｍＫ以下にまで冷却する。これにより、各量子ビットのスピン方向が揃い｜0〉(×) ｜0〉の量子状態が生成される。
次に、１キュービット回転演算部１４ｂが、各計算ビットに対して１キュービット回転演算
【数２０】
2006195558.tif 000016
を施す。
また、回転演算部１４ｃが、各アンチラビットに対して回転演算
【数２１】
2006195558.tif 000017
（ｋ∈｛１,2,...,βd｝は各アンチラビットに一義的に対応する自然数）
を施す。
なお、式（６）（７）の操作は以下の関係式に還元される。
｜ψ0〉(×) ｜a0〉=Uh（×）Ua｜0〉(×) ｜0〉
【数２２】
2006195558.tif 000018
このように生成された初期量子状態は量子メモリ１５に格納される（ステップＳ３２）。
【００３１】
＜量子操作（ステップＳ４）＞
操作部１６において、計算ビットとアンチラビットとを操作し、観測された際、計算ビットが所望の値xに対応する状態｜x〉に縮退する確率を増幅させる。
具体的には、例えば、まず制御部１９においてｊに１を代入する（ステップＳ４１）。次に、オラクル演算部１６ｂにおいて、この計算ビットとアンチラビットの量子状態に対し、式（５）で示される演算Ｕｘ｜y〉(×)｜m〉を施す（ステップＳ４２）。そして、これらの演算後の量子状態｜ψj〉(×) ｜a0〉を次の操作対象として量子メモリ１５に保存する。
また、計算ビット操作部１６ａにおいて、量子メモリ１５に保存されている操作対象の量子状態｜ψj-1〉(×) ｜a0〉（最初の操作対象は初期量子状態｜ψ0〉(×) ｜a0〉）に対し、式（４）で示される計算ビットのみに対するローカルな演算Ｕｓ（×）Ｉｄを施す（ステップＳ４３）。図５は、この操作（Ｕｓ（×）Ｉｄ｜ψj-1〉(×) ｜a0〉）を説明するための概念図である。この図に示すように、この操作はｎ個の計算ビット２１０−１〜ｎそれぞれに対するローカルな操作である。
【００３２】
次に、制御部１９がｊ＝ｊｏｐであるか否かを判定する（ステップＳ４４）。なお、この例では、jop:=［{π・2n/2/4sin(β/2)}+1/2］とする。ここで、ｊ＝ｊｏｐでないと判断された場合、制御部１９は処理をステップＳ４２に戻す。一方、ｊ＝ｊｏｐであると判断された場合、制御部１９はステップＳ５へ処理を進める。これにより、操作部１６は、操作対象の量子状態｜ψj-1〉(×) ｜a0〉に対し、計算ビットのみに対するローカルな演算Ｕｓ（×）Ｉｄと、計算ビットとアンチラビットとに対するUx|y〉(×) ｜a0〉=G(×)Id|y〉(×) ｜a0〉を満たす演算Ｕｘ｜y〉(×)｜m〉とを施し、当該演算後の量子状態｜ψj〉(×) ｜a0〉を次の操作対象として量子メモリ１５に保存する処理を、ｊｏｐ回数繰り返すことになる。
【００３３】
なお、ステップＳ４２の処理とステップＳ４３の処理の順序を入れ替えてもよい。しかし、この場合、最初のステップＳ４３の演算は量子状態を何ら変化させないこととなり、無駄な処理を１つ実行することになるため、図４の順序で実施することが望ましい。また、［{π・2n/2/4sin(β/2)}+1/2］以外の値をjopとおいてもよいが、jop=［{π・2n/2/4sin(β/2)}+1/2］とおいた場合、観測時に計算ビットが所望の値xに対応する状態｜x〉に縮退する確率を十分に増幅することができる。具体的には、ｎが無限大とした場合におけるこの確率の極限値は１になる。すなわち、現実的に必要なほどに大きなｎにおいて、この確率は十分１に近くなる（詳細は後述する）。これは、非常に高い確率で検索対象値xの探索が成功することを示している。よって、jop =［{π・2n/2/4sin(β/2)}+1/2］とすることが望ましい。なお、jop =［{π・2n/2/4sin(β/2)}+1/2］としなかった場合、観測時に計算ビットが所望の値xに対応する状態｜x〉に縮退する確率は、sin((π・jop)/(2・jop))程度になる、
【００３４】
＜ステップＳ５＞
観測部１７において、量子メモリ１５に保存されている計算ビットの量子状態｜ψjop〉を計算基底｜y〉で観測する。これにより、計算ビットの量子状態は何れかの状態に縮退し、その状態が観測値x0として観測される。そして、観測部１７は、この観測値x0を出力する（ステップＳ５）。
【００３５】
＜ステップＳ６＞
観測値x0は判定部１８に入力され、判定部１８はｆ（x0）＝１であるか否かを判定し、その判定結果を制御部１９に出力する。制御部１９は、この判定結果がｆ（x0）＝１でない（観測値x0が検索対象値xと異なる）ことを示すものであった場合、処理をステップＳ３に戻し、初期量子状態生成部１４に初期量子状態｜ψ0〉(×) ｜a0〉を生成させ、その初期量子状態｜ψ0〉(×) ｜a0〉を量子メモリ１５に保存させ、操作部１６における処理と観測部１７における処理と判定部１８における処理と（ステップＳ３〜Ｓ６）を再び実行させる。一方、この判定結果がｆ（x0）＝１である（観測値x0が検索対象値xと等しい）と判定された場合、処理を終了する。
【００３６】
〔ステップＳ４の処理により確率が増幅される数学的背景〕
観測された際、計算ビットが所望の値xに対応する状態｜x〉に縮退する確率が増幅されるのは、
【数２３】
2006195558.tif 000019
が成り立つからである。以下、これについて説明する。
まず、前述したように、オラクル演算部１６ｂが行う演算Ｕｘ｜y〉(×)｜m〉は、
Ux|y〉(×) ｜a0〉=G(×)Id|y〉(×) ｜a0〉  …(9)
G:=exp(i・β｜x〉〈x｜)=Id−(ei・β−1)｜x〉〈x｜  …(10)
を満たす演算である。
【００３７】
また、前述したように（〔記号・用語の定義〕）、｜φ〉で示される量子状態を観測したとき｜x〉が観測される確率は|〈x｜φ〉|2で求められる。そして、ステップＳ５の観測の場合、｜x〉が観測される確率は、アンチラビットの状態いかんに関わらず｜x〉が観測される確率である。つまり、ステップＳ５の観測において｜x〉が観測される確率は、アンチラビットの各状態において｜x〉が観測される確率の和となる。よって、ステップＳ５の観測で｜x〉が観測される確率Pは、
P=｜〈x｜(×)〈0｜(ＵｓUx)jop|ψ0〉(×)|a0〉｜2+｜〈x｜(×)〈1｜(ＵｓUx)jop|ψ0〉(×)|a0〉｜2+…+｜〈x｜(×)〈2βｄ−1｜(ＵｓUx)jop|ψ0〉(×)|a0〉｜2  …(11)
となる。また、式（９）より、式（１１）は、
P=｜〈x｜(×)〈0｜(ＵｓG)jop(×)Ｉｄ|ψ0〉(×)|a0〉｜2+｜〈x｜(×)〈1｜(ＵｓG)jop(×)Ｉｄ|ψ0〉(×)|a0〉｜2+…+｜〈x｜(×)〈2βｄ−1｜(ＵｓG)jop(×)Ｉｄ|ψ0〉(×)|a0〉｜2  …(12)
と変形できる。
【００３８】
＜式（１１）から式（１２）へ変形できる理由＞
まずUx|ψ0〉(×)|a0〉の演算（ステップＳ４２）を考えると、これは以下のように変形できる。
Ux|ψ0〉(×)|a0〉
=G(×)Id |ψ0〉(×)|a0〉（式（９）より）
=G|ψ0〉(×) Id |a0〉（前述した定義より）
=G|ψ0〉(×) |a0〉…(13)
次に、(Us(×)Id)Ux|ψ0〉(×)|a0〉の演算（ステップＳ４３）を考えると、これは以下のように変形できる。
【００３９】
(Us(×)Id)Ux|ψ0〉(×)|a0〉
=(Us(×)Id) G|ψ0〉(×) |a0〉（式（１３）より）
= UsG|ψ0〉(×) Id |a0〉（前述した定義より）
= UsG|ψ0〉(×) |a0〉…(14)
次に、((Us(×)Id)Ux)2|ψ0〉(×)|a0〉の演算（２回目のステップＳ４３）を考えると、これは以下のように変形できる。
((Us(×)Id)Ux)2|ψ0〉(×)|a0〉
=((Us(×)Id)Ux)((Us(×)Id)Ux)|ψ0〉(×)|a0〉
=((Us(×)Id)Ux)UsG|ψ0〉(×) |a0〉（式（１4）より）
=(Us(×)Id)(G(×)Id)UsG|ψ0〉(×) |a0〉（式（９）より）
=(Us(×)Id)GUsG|ψ0〉(×) Id |a0〉（前述した定義より）
=(Us(×)Id)GUsG|ψ0〉(×) |a0〉
=UsGUsG|ψ0〉(×) Id |a0〉（前述した定義より）
=(UsG)2|ψ0〉(×) |a0〉
同様に、((Us(×)Id)Ux)jop|ψ0〉(×)|a0〉の演算（jop回目のステップＳ４３）を考えると、これは以下のように変形できる。
【００４０】
((Us(×)Id)Ux)jop|ψ0〉(×)|a0〉
=(UsG)jop|ψ0〉(×) |a0〉
これから式（１１）の１項目｜〈x｜(×)〈0｜(ＵｓUx)jop|ψ0〉(×)|a0〉｜2は以下のように変形できる。
｜〈x｜(×)〈0｜(ＵｓUx)jop|ψ0〉(×)|a0〉｜2
=｜〈x｜(×)〈0｜((Us(×)Id)Ux)jop|ψ0〉(×)|a0〉｜2
=｜〈x｜(×)〈0｜(UsG)jop |ψ0〉(×)|a0〉｜2 …(15)
式（１１）の他の項も式（１５）と同様に変形できるため、式（１１）は式（１２）に変形できる（＜式（１１）から式（１２）へ変形できる理由＞の説明終わり）。
【００４１】
次に、式（１２）は、前述した定義より以下のように変形できる。
P=｜〈x｜(×)〈0｜(ＵｓG)jop|ψ0〉(×)|a0〉｜2+｜〈x｜(×)〈1｜(ＵｓG)jop|ψ0〉(×)|a0〉｜2+…+｜〈x｜(×)〈2βｄ−1｜(ＵｓG)jop|ψ0〉(×)|a0〉｜2  …(16)
また、テンソル積の性質から
(〈λ|(×)〈μ|)(｜δ〉(×) ｜ε〉)=〈λ|δ〉・〈μ|ε〉…(17)
が成り立つ。よって、式（１６）は、
P=｜〈x|(ＵｓG)jop|ψ0〉・〈0|a0〉｜2+｜〈x|(ＵｓG)jop|ψ0〉・〈1|a0〉｜2+…+｜〈x|(ＵｓG)jop|ψ0〉・〈2βｄ−1|a0〉｜2
と変形でき、さらに、
P=｜〈x|(ＵｓG)jop|ψ0〉｜2・｜〈0|a0〉｜2+｜〈x|(ＵｓG)jop|ψ0〉｜2・｜〈1|a0〉｜2+…+｜〈x|(ＵｓG)jop|ψ0〉｜2・｜〈2βｄ−1|a0〉｜2
=｜〈x|(ＵｓG)jop|ψ0〉｜2・(｜〈0|a0〉｜2+｜〈1|a0〉｜2+…+｜〈2βｄ−1|a0〉｜2
) …(18)
と変形できる。
【００４２】
ここで式（２）より、
【数２４】
2006195558.tif 000020
である。また、前述した定義より、δ=εの場合〈δ|ε〉=1となり、δ≠εの場合〈δ|ε〉=0となるから、
【数２５】
2006195558.tif 000021
となる。ここで、前述の通りｅｉ・ωはcosω＋i sinωを意味するが、βu及びβdは自然数であるから式（１９）の各項のωに対応する値は−2πの倍数となり、これは0と等価である。よって、式（１９）は、
｜2‐βd/2｜2+｜2‐βd/2｜2+…+｜2‐βd/2｜2=1
となる。よって式（１８）は、
P=｜〈x|(ＵｓG)jop|ψ0〉｜2
となり、式（８）がｎを無限大にした際のPの極限値を示していることがわかる。よって式（８）が１に近づくのであれば、ステップＳ５の観測で｜x〉が観測される確率Pも１に近づく。
【００４３】
図６及び図７は、横軸をnとし、縦軸を｜〈x|(ＵｓG)jop|ψ0〉｜2としたグラフである。なお、図６（ａ）はβ＝−４π／５の場合を、図６（ｂ）はβ＝−３π／４の場合を、図７（ａ）はβ＝−２π／３の場合を、図６（ａ）はβ＝−π／２の場合を、それぞれ示している。これらのグラフに示すように、ｎが大きくなるとステップＳ５の観測で｜x〉が観測される確率Pが１に近づいていくことがわかる。つまり、現実的に必要なほどに大きなnにおいては成功確率（ステップＳ６でf(x0)=1となる確率）は十分１に近い。
【００４４】
〔本形態の特徴〕
以上説明した通り、本形態では、計算ビットとアンチラビットとに対するUx|y〉(×) ｜a0〉=G(×)Id|y〉(×) ｜a0〉を満たす演算Ｕｘ｜y〉(×)｜m〉と、計算ビットのみに対するローカルな演算Ｕｓ（×）Ｉｄとを用いることとした。ここで、演算Ｕｓ（×）Ｉｄは１つの量子ビットに対する演算の直積の形で書けるローカルな演算である。そのため、グローバルな演算の場合のような演算速度とエラー発生率とはトレードオフの関係はない。よって、エラー発生確率を低く抑えつつ計算速度を向上させることができる。
【００４５】
また、Ux|y〉(×) ｜a0〉=G(×)Id|y〉(×) ｜a0〉を満たす演算Ｕｘ｜y〉(×)｜m〉を実行するために必要な時間は、基本的に非特許文献１におけるオラクル演算Ｕｘ'｜y〉(×)｜m〉を実行するために必要な時間とほぼ同じである。よって、グローバルな演算の必要回数は大雑把にいって非特許文献１の場合の半分になっている。その結果、本形態では、非特許文献１の場合に比べ、最大２倍の速さで計算が可能である。
なお、本発明は上述の実施の形態に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。また、量子探索装置１０を構成する各構成は同じ筺体内に存在してもよいし、複数の筺体に分散配置されることとしてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００４６】
また、量子探索装置が有すべき機能の処理内容はプログラムによって記述される。なお、このプログラムは、例えば、古典コンピュータに読み込まれ、これと協働することにより上述の古典情報を取り扱う部分を構成するための古典情報処理プログラムと、古典コンピュータに読み込まれ、これと協働することにより上述の量子情報を取り扱う部分の制御を行うための量子操作制御プログラムとを有する。
すなわち、入力部１１、古典メモリ１２、古典演算部１３、判定部１８及び制御部１９等の古典情報を取り扱う部分は、このプログラムが古典コンピュータに読み込まれることにより構成され、このプログラムに従った処理を行うことにより各処理を実行する。
【００４７】
また、初期量子状態生成部１４、量子メモリ１５及び操作部１６等の量子情報を扱うハードウェアは、このプログラムが読み込まれた古典コンピュータによる制御に従って各処理を実行する。例えば、量子ビットに核スピンが用いられる場合、このプログラムが読み込まれた古典コンピュータは、量子操作を行う冷却装置、レーザ光出射装置、磁場発生装置等を制御し、これらに目的の量子状態を生成させる。また、例えば、量子ビットに光子が用いられる場合、このプログラムが読み込まれた古典コンピュータは、量子操作を行うビームスプリッタ、位相シフタ等の駆動を制御し、これらに目的の量子状態を生成させる。
【００４８】
このような処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよいが、具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【００４９】
また、このようなプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このようなプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【産業上の利用可能性】
【００５０】
本発明により、大量のデータから必要なファイルを高速で検索できるデータベースを構成することができる。具体的には、例えば、シリアル番号の重ね合わせ状態とした計算ビットと、上述のアンチラビットと、これら以外の第３の量子ビット（計算ビットとの絡み合いの状態を維持しつつ、各シリアル番号に対応する商品詳細情報の重ね合わせ状態とした量子ビット）とからなるデータベースが例示できる。この場合、所望のシリアル番号を検索対象値xとし、本発明の処理を実行する。そして、計算ビットの観測により、この所望のシリアル番号に対応する量子状態が観測されると、この計算ビットと絡み合いの状態にある第３の量子ビットもこの所望のシリアル番号に対応する商品詳細情報を示す量子状態に縮退する。そのため、ここでこの第３の量子ビットを観測すると所望のシリアル番号に対応する商品詳細情報が観測される。これにより、シリアル番号から商品詳細情報を高速で検索できるデータベースを構築できる。
【図面の簡単な説明】
【００５１】
【図１】本形態の量子探索装置の構成を示したブロック図。
【図２】本形態における量子探索装置の処理の全体を説明するためのフローチャート。
【図３】（ａ）は、図２のステップＳ１の詳細を、（ｂ）は図２のステップＳ３の詳細をそれぞれ説明するためのフローチャート。
【図４】図２のステップＳ４の詳細を説明するためのフローチャート。
【図５】計算ビットのみに対するローカルな演算Ｕｓ（×）Ｉｄを説明するための概念図。
【図６】横軸をnとし、縦軸を｜〈x|(ＵｓG)jop|ψ0〉｜2としたグラフ。
【図７】横軸をnとし、縦軸を｜〈x|(ＵｓG)jop|ψ0〉｜2としたグラフ。
【図８】計算ビットのみに対する従来の演算Uψの内容を説明するための概念図。
【符号の説明】
【００５２】
１０  量子探索装置
【図１】
2006195558.tif 000028
【図２】
2006195558.tif 000029
【図３】
2006195558.tif 000030
【図４】
2006195558.tif 000031
【図５】
2006195558.tif 000032
【図６】
2006195558.tif 000033
【図７】
2006195558.tif 000034
【図８】
2006195558.tif 000035