(57)【特許請求の範囲】
【請求項１】
２つの２進数ａ＝ａｎ−１…ａ０（ａｉ∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝）及びｂ＝ｂｎ−１…ｂ０（ｂｉ∈｛０，１｝）に対し、（ａ＋ｂ）ｍｏｄ  ｐ（ｐ＝ｐｎ−１…ｐ０，ｐｉ∈｛０，１｝，ａ＋ｂはｐの２倍未満）を算出する量子演算方法であって、
ｎ個の量子ビットＱＡ０，…，ＱＡｎ−１の量子状態をそれぞれ｜ａ０＞，…，｜ａｎ−１＞とし、ｎ個の量子ビットＱＢ０，…，ＱＢｎ−１の量子状態をそれぞれ｜ｂ０＞，…，｜ｂｎ−１＞とし、２個の量子ビットＱＣ０，ＱＣ１の量子状態をそれぞれ｜０＞，｜０＞としておき、
上記量子ビットＱＡ０，…，ＱＡｎ−１，ＱＢ０，…，ＱＢｎ−１，ＱＣ０に対する加算量子操作を行い、上記量子ビットＱＡ０，…，ＱＡｎ−１の量子状態をそれぞれ｜ａ０＞，…，｜ａｎ−１＞とし、上記量子ビットＱＢ０，…，ＱＢｎ−１の量子状態をそれぞれ、｜ｓ０＞，…，｜ｓｎ−１＞（ａ＋ｂ＝ｓｎ…ｓ０（ｓｋ∈｛０，１｝，ｋ∈｛０，…，ｎ｝））とし、上記量子ビットＱＣ０の量子状態を｜ｓｎ＞とする加算演算過程と、
上記加算演算過程で上記加算量子操作された上記量子ビットＱＡ０，…，ＱＡｎ−１，ＱＢ０，…，ＱＢｎ−１，ＱＣ０と、上記量子ビットＱＣ１とに対する比較量子操作を行い、上記量子ビットＱＡ０，…，ＱＡｎ−１の量子状態をそれぞれ｜ａ０＞，…，｜ａｎ−１＞とし、上記量子ビットＱＢ０，…，ＱＢｎ−１の量子状態をそれぞれ｜ｓ０＞，…，｜ｓｎ−１＞とし、上記量子ビットＱＣ０の量子状態を｜ｓｎ＞とし、上記量子ビットＱＣ１の量子状態を｜ｙ＞（ｐ≦ａ＋ｂの場合ｙ＝１、ｐ＞ａ＋ｂの場合ｙ＝０）とする第１比較演算過程と、
上記第１比較演算過程で上記比較量子操作された上記量子ビットＱＣ１の量子状態が｜１＞であった場合にのみ、上記第１比較演算過程で上記比較量子操作された上記量子ビットＱＢ０，…，ＱＢｎ−１の量子状態をそれぞれ｜ｔ０＞，…，｜ｔｎ−１＞（ａ＋ｂ−ｐ＝ｔｎ−１…ｔ０（ｔｉ∈｛０，１｝））とし、上記量子ビットＱＣ０の量子状態を｜０＞とする制御減算演算過程と、
を実行し、
上記加算演算過程で行われる上記加算量子操作は、
θ＝１，…，ｎ−１のそれぞれについて昇順で、上記量子ビットＱＣ０を制御ビットとし、上記量子ビットＱＡθを目標ビットとしたＣＮＯＴ演算操作と、上記量子ビットＱＣ０を制御ビットとし、上記量子ビットＱＢθを目標ビットとしたＣＮＯＴ演算操作とを行うＷ１量子操作過程と、
上記量子ビットＱＡ０，ＱＢ０を制御ビットとし，上記量子ビットＱＣ０を目標ビットとしたトフォリ演算操作を行い、θ＝１，…，ｎ−２のそれぞれについて昇順で、上記量子ビットＱＢθ，ＱＡθ，ＱＣ０に対するＭＡＪ演算操作と、上記量子ビットＱＢθ，ＱＡθを制御ビットとし、上記量子ビットＱＢ０を目標ビットとしたトフォリ演算操作とを行い、さらに上記量子ビットＱＢｎ−１，ＱＡｎ−１，ＱＣ０に対するＭＡＪ演算操作を行うＷ２量子操作過程と、
θ＝２，…，ｎ−１のそれぞれについて降順で、上記量子ビットＱＢ０を制御ビットとし、上記量子ビットＱＡθを目標ビットとしたＣＮＯＴ演算操作と、上記量子ビットＱＢθ−１，ＱＡθ−１を制御ビットとし，上記量子ビットＱＢ０を目標ビットとしたトフォリ演算操作とを行うＷ３量子操作過程と、
上記量子ビットＱＡ０に対するＮＯＴ演算操作を行い、θ＝２，…，ｎ−１のそれぞれについて降順で、上記量子ビットＱＢ０，ＱＡ０を制御ビットとし、上記量子ビットＱＡθを目標ビットとしたトフォリ演算操作を行い、さらに、上記量子ビットＱＡ０に対するＮＯＴ演算操作を行い、上記量子ビットＱＢ０，ＱＡ０を制御ビットとし，上記量子ビットＱＡ１を目標ビットとしたトフォリ演算操作を行い、さらに、θ＝０，…，ｎ−１のそれぞれについて昇順で、上記量子ビットＱＡθを制御ビットとし、上記量子ビットＱＢθを目標ビットとしたＣＮＯＴ演算操作を行うＷ４量子操作過程と、を含む操作であり、
上記第１比較演算過程で行われる上記比較量子操作は、
上記加算演算過程で上記加算量子操作された上記量子ビットＱＢ０，…，ＱＢｎ−１，ＱＣ０の量子状態をそれぞれ反転させ、各量子状態を｜ｓ０’＞，…，｜ｓｎ−１’＞，｜ｓｎ’＞とする第１ＮＯＴ演算過程と、
上記第１ＮＯＴ演算過程で得られた各量子状態が｜ｓ０’＞，…，｜ｓｎ−１’＞，｜ｓｎ’＞の上記量子ビットＱＢ０，…，ＱＢｎ−１，ＱＣ０と、上記加算演算過程で上記加算量子操作された上記量子ビットＱＡ０，…，ＱＡｎ−１，ＱＣ１とに対する最上位ビット演算量子操作を行い、当該量子ビットＱＢ０，…，ＱＢｎ−１，ＱＣ０の量子状態をそれぞれ、｜ｓ０’＞，…，｜ｓｎ−１’＞，｜ｓｎ’＞とし、当該量子ビットＱＡ０，…，ＱＡｎ−１の量子状態をそれぞれ｜ａ０＞，…，｜ａｎ−１＞とし、当該量子ビットＱＣ１の量子状態を｜ｘ＞（ｘはｓ’＋ｐ（ｓ’＝ｓｎ’ｓｎ−１’…ｓ０’）を２進ｎ＋２桁表記した際の最上位桁の値）とする最上位ビット演算過程と、
上記最上位ビット演算過程で上記最上位ビット演算量子操作された上記量子ビットＱＢ０，…，ＱＢｎ−１，ＱＣ０，ＱＣ１の量子状態をそれぞれ反転させ、各量子状態を｜ｓ０＞，…，｜ｓｎ−１＞，｜ｓｎ＞，｜ｙ＞とする第２ＮＯＴ演算過程と、を含む操作であり、
上記最上位ビット演算過程で行われる上記最上位ビット演算量子操作は、
上記量子ビットＱＡｎ−１を制御ビットとし、上記量子ビットＱＣ１を目標ビットとした制御ＮＯＴ演算を行う第１制御ＮＯＴ演算過程と、
上記第１制御ＮＯＴ演算過程による処理の後、上記量子ビットＱＡｎ−２，ＱＣ０を制御ビットとし、上記量子ビットＱＡｎ−１を目標ビットとしたトフォリ演算を施す第１トフォリ演算過程と、
上記第１トフォリ演算過程による処理の後、降順で各ｊ∈｛２，…，ｎ−１｝に対して、ｐｊ＝１である場合にのみ上記量子ビットＱＢｊにＮＯＴ演算を施し、ｐｊの値に拘らず上記量子ビットＱＡｊ−２，ＱＢｊとを制御ビットとして上記量子ビットＱＡｊ−１を目標ビットとしたトフォリ演算を施し、ｐｊ＝１である場合にのみ上記量子ビットＱＢｊにＮＯＴ演算を施す量子操作を実行する第１量子操作過程と、
上記第１量子操作過程による処理の後、ｐ１＝１である場合にのみ、上記量子ビットＱＢ１を制御ビットとし、上記量子ビットＱＡ０を目標ビットとした制御ＮＯＴ演算を施し、さらにその後、上記量子ビットＱＢ１にＮＯＴ演算を施す第２量子操作過程と、
上記第２量子操作過程による処理の後、ｐ０＝１である場合にのみ、上記量子ビットＱＢ０，ＱＢ１を制御ビットとし、上記量子ビットＱＡ０を目標ビットとしたトフォリ演算を施す第３量子演算過程と、
上記第３量子操作過程による処理の後、昇順で各ｊに対して、ｐｊ＝１である場合にのみ上記量子ビットＱＢｊを制御ビットとして上記量子ビットＱＡｊ−１を目標ビットとした制御ＮＯＴ演算を施し、ｐｊ＝１である場合にのみ上記量子ビットＱＢｊにＮＯＴ演算を施し、ｐｊの値に拘らず上記量子ビットＱＡｊ−２，ＱＢｊとを制御ビットとし、上記量子ビットＱＡｊ−１を目標ビットとしたトフォリ演算を施す量子操作を実行する第４量子操作過程と、
上記第４量子操作過程による処理の後、上記量子ビットＱＡｎ−２，ＱＣ０を制御ビットとし、上記量子ビットＱＡｎ−１を目標ビットとしたトフォリ演算を施す第２トフォリ演算過程と、
上記第２トフォリ演算過程による処理の後、上記量子ビットＱＡｎ−１を制御ビットとし、上記量子ビットＱＣ１を目標ビットとした制御ＮＯＴ演算を行う第２制御ＮＯＴ演算過程と、
上記第２制御ＮＯＴ演算による処理の後、上記量子ビットＱＡｎ−２，ＱＣ０を制御ビットとし、上記量子ビットＱＡｎ−１を目標ビットとしたトフォリ演算を施す第３トフォリ演算過程と、
上記第３トフォリ演算過程による処理の後、降順で各ｊに対し、上記第４量子操作過程の操作の逆演算操作を、上記量子ビットＱＡｊ−２，ＱＢｊ，ＱＡｊ−１に対して施す第５量子操作過程と、
上記第５量子操作過程による処理の後、ｐ０＝１である場合にのみ、上記量子ビットＱＢ０，ＱＢ１を制御ビットとし、上記量子ビットＱＡ０を目標ビットとしたトフォリ演算を施す第６量子演算過程と、
上記第６量子操作過程による処理の後、ｐ１＝１である場合にのみ、上記量子ビットＱＢ１にＮＯＴ演算を施し、さらにその後、上記量子ビットＱＢ１を制御ビットとし、上記量子ビットＱＡ０を目標ビットとした制御ＮＯＴ演算を施す第７量子操作過程と、
上記第７量子操作過程による処理の後、昇順で各ｊに対して、上記第１量子操作過程の演算操作を上記量子ビットＱＡｊ−２，ＱＢｊ，ＱＡｊ−１に対して施す第８量子操作過程と、
上記第８量子操作過程による処理の後、上記量子ビットＱＡｎ−２，ＱＣ０を制御ビットとし、上記量子ビットＱＡｎ−１を目標ビットとしたトフォリ演算を施す第４トフォリ演算過程と、を含む操作であり、
上記制御減算演算過程は、
量子状態がそれぞれ｜ｓ０＞，…，｜ｓｎ−１＞，｜ｓｎ＞である上記量子ビットＱＢ０，・・・，ＱＢｎ−１，ＱＣ０に対して量子フーリエ変換を行い、上記量子ビットＱＢ０，・・・，ＱＢｎ−１，ＱＣ０の量子状態を｜Φ０（ｓ）＞，…，｜Φｎ−１（ｓ）＞，｜Φｎ（ｓ）＞にするＱＦＴ演算過程と、
上記量子ビットＱＣ１を制御ビットとし、上記量子ビットＱＢ０，・・・，ＱＢｎ−１，ＱＣ０，ＱＣ０を目標ビットとした制御ΦＡＤＤ（ｐ）−１演算操作を行う制御ΦＡＤＤ（ｐ）−１演算過程と、
上記量子ビットＱＢ０，・・・，ＱＢｎ−１，ＱＣ０に対して上記量子フーリエ変換の逆演算を行うＱＦＴ−１演算過程と、を含み、
ｓ＝ｓｎｓｎ−１…ｓ０、ｋ＝０，…，ｎ、eは自然対数であり、
【数２】
0004829623.tif 000003
であり、
前記制御ΦＡＤＤ（ｐ）−１演算操作は、
上記量子ビットＱＣ１の量子状態が｜１＞の場合にのみ、上記量子ビットＱＢ０，・・・，ＱＢｎ−１，ＱＣ０に対するΦＡＤＤ（ｐ）−１演算操作を行う操作であり、
上記ΦＡＤＤ（ｐ）−１演算操作は、ΦＡＤＤ（ｐ）演算の逆演算であり、
上記ΦＡＤＤ（ｐ）演算は、
量子ビットＱＢｋの量子状態｜ｇｋ＞（ｋ＝０，…，ｎ）のそれぞれを
【数３】
0004829623.tif 000004
にする演算である、
ことを特徴とする量子演算方法。
【請求項２】
請求項１に記載の量子演算方法であって、
上記ｐは素数であり、
上記ａ，ｂは上記ｐ未満である、
ことを特徴とする量子演算方法。
【請求項３】
請求項１に記載の量子演算方法であって、
上記制御減算演算過程による処理の後、上記量子ビットＱＣ０と上記量子ビットＱＣ１との量子状態を交換する交換演算過程と、
上記交換演算過程による処理の後、上記量子ビットＱＡ０，…，ＱＡｎ−１，ＱＢ０，…，ＱＢｎ−１，ＱＣ０に対する第２比較量子操作を行い、上記量子ビットＱＡ０，…，ＱＡｎ−１，ＱＢ０，…，ＱＢｎ−１の量子状態を当該量子操作前のものとし、上記量子ビットＱＣ０の量子状態を｜γ（＋）δ＞（γ（＋）δはγとδとの排他的論理和を示し、γは当該量子操作前の上記量子ビットＱＣ０の量子状態が示す値であり、上記量子ビットＱＢｉの各量子状態が示す値をｉ＋１桁目の値とした２進ｎ桁の数βが、上記量子ビットＱＡｉの各量子状態が示す値をｉ＋１桁目の値とした２進ｎ桁の数α以上である場合δ＝１であり、βがα未満である場合δ＝０である）とする第２比較演算過程と、
上記第２比較演算過程による処理の後、上記量子ビットＱＣ０にＮＯＴ演算を施す第３ＮＯＴ演算過程と、
を有し、
上記第２比較演算過程で行われる上記第２比較量子操作は、
上記量子ビットＱＢ０，・・・，ＱＢｎ−１に対するＮＯＴ演算操作を行い、θ＝１，…，ｎ−１のそれぞれについて昇順で、上記量子ビットＱＣ０を制御ビットとし、上記量子ビットＱＡθを目標ビットとしたＣＮＯＴ演算操作と、上記量子ビットＱＣ０を制御ビットとし、上記量子ビットＱＢθを目標ビットとしたＣＮＯＴ演算操作とを行うＴ１量子操作過程と、
上記量子ビットＱＡ０，ＱＢ０を制御ビットとし，上記量子ビットＱＣ０を目標ビットとしたトフォリ演算操作を行い、θ＝１，…，ｎ−２のそれぞれについて昇順で、上記量子ビットＱＢθ，ＱＡθ，ＱＣ０に対するＭＡＪ演算操作と、上記量子ビットＱＢθ，ＱＡθを制御ビットとし、上記量子ビットＱＢ０を目標ビットとしたトフォリ演算操作とを行い、さらに上記量子ビットＱＢｎ−１，ＱＡｎ−１，ＱＣ０に対するＭＡＪ演算操作を行うＴ２量子操作過程と、
θ＝２，…，ｎ−１のそれぞれについて降順で、上記量子ビットＱＢ０を制御ビットとし、上記量子ビットＱＡθを目標ビットとしたＣＮＯＴ演算操作と、上記量子ビットＱＢ０を制御ビットとし、上記量子ビットＱＢθを目標ビットとしたＣＮＯＴ演算操作と、上記量子ビットＱＡθ−１，ＱＢθ−１を制御ビットとし，上記量子ビットＱＢ０を目標ビットとしたトフォリ演算操作とを行うＴ３量子操作過程と、
上記量子ビットＱＡ０に対するＮＯＴ演算操作を行い、θ＝２，…，ｎ−１のそれぞれについて降順で、上記量子ビットＱＢ０，ＱＡ０を制御ビットとし、上記量子ビットＱＡθを目標ビットとしたトフォリ演算操作を行い、上記量子ビットＱＢ０，ＱＡ０を制御ビットとし、上記量子ビットＱＢθを目標ビットとしたトフォリ演算操作を行い、さらに、上記量子ビットＱＡ０に対するＮＯＴ演算操作を行い、上記量子ビットＱＢ０，ＱＡ０を制御ビットとし、上記量子ビットＱＡ1を目標ビットとしたトフォリ演算操作を行い、上記量子ビットＱＢ０，ＱＡ０を制御ビットとし、上記量子ビットＱＢ1を目標ビットとしたトフォリ演算操作を行い、上記量子ビットＱＢ０，…，ＱＢｎ−１，ＱＣ０に対するＮＯＴ演算操作を行うＴ４量子操作過程と、を含む操作である、
ことを特徴とする量子演算方法。
【請求項４】
２つの２進数ａ＝ａｎ−１…ａ０（ａｉ∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝）及びｂ＝ｂｎ−１…ｂ０（ｂｉ∈｛０，１｝）に対し、（ａ＋ｂ）ｍｏｄ  ｐ（ｐ＝ｐｎ−１…ｐ０，ｐｉ∈｛０，１｝，ａ＋ｂはｐの２倍未満）を算出する量子演算装置であって、
初期量子状態がそれぞれ｜ａ０＞，…，｜ａｎ−１＞であるｎ個の量子ビットＱＡ０，…，ＱＡｎ−１と、初期量子状態をそれぞれ｜ｂ０＞，…，｜ｂｎ−１＞であるｎ個の量子ビットＱＢ０，…，ＱＢｎ−１と、初期量子状態がそれぞれ｜０＞，｜０＞である２個の量子ビットＱＣ０，ＱＣ１と、
上記量子ビットＱＡ０，…，ＱＡｎ−１，ＱＢ０，…，ＱＢｎ−１，ＱＣ０に対する加算量子操作を行い、上記量子ビットＱＡ０，…，ＱＡｎ−１の量子状態をそれぞれ｜ａ０＞，…，｜ａｎ−１＞とし、上記量子ビットＱＢ０，…，ＱＢｎ−１の量子状態をそれぞれ、｜ｓ０＞，…，｜ｓｎ−１＞（ａ＋ｂ＝ｓｎ…ｓ０（ｓｋ∈｛０，１｝，ｋ∈｛０，…，ｎ｝））とし、上記量子ビットＱＣ０の量子状態を｜ｓｎ＞とする加算演算部と、
上記加算演算部で上記加算量子操作された上記量子ビットＱＡ０，…，ＱＡｎ−１，ＱＢ０，…，ＱＢｎ−１，ＱＣ０と、上記量子ビットＱＣ１とに対する比較量子操作を行い、上記量子ビットＱＡ０，…，ＱＡｎ−１の量子状態をそれぞれ｜ａ０＞，…，｜ａｎ−１＞とし、上記量子ビットＱＢ０，…，ＱＢｎ−１の量子状態をそれぞれ｜ｓ０＞，…，｜ｓｎ−１＞とし、上記量子ビットＱＣ０の量子状態を｜ｓｎ＞とし、上記量子ビットＱＣ１の量子状態を｜ｙ＞（ｐ≦ａ＋ｂの場合ｙ＝１、ｐ＞ａ＋ｂの場合ｙ＝０）とする比較演算部と、
上記第１比較演算部で上記比較量子操作された上記量子ビットＱＣ１の量子状態が｜１＞であった場合にのみ、上記第１比較演算部で上記比較量子操作された上記量子ビットＱＢ０，…，ＱＢｎ−１の量子状態をそれぞれ｜ｔ０＞，…，｜ｔｎ−１＞（ａ＋ｂ−ｐ＝ｔｎ−１…ｔ０（ｔｉ∈｛０，１｝））とし、上記量子ビットＱＣ０の量子状態を｜０＞とする制御減算演算部と、
を有し、
上記加算演算部で行われる上記加算量子操作は、
θ＝１，…，ｎ−１のそれぞれについて昇順で、上記量子ビットＱＣ０を制御ビットとし、上記量子ビットＱＡθを目標ビットとしたＣＮＯＴ演算操作と、上記量子ビットＱＣ０を制御ビットとし、上記量子ビットＱＢθを目標ビットとしたＣＮＯＴ演算操作とを行うＷ１量子操作過程と、
上記量子ビットＱＡ０，ＱＢ０を制御ビットとし，上記量子ビットＱＣ０を目標ビットとしたトフォリ演算操作を行い、θ＝１，…，ｎ−２のそれぞれについて昇順で、上記量子ビットＱＢθ，ＱＡθ，ＱＣ０に対するＭＡＪ演算操作と、上記量子ビットＱＢθ，ＱＡθを制御ビットとし、上記量子ビットＱＢ０を目標ビットとしたトフォリ演算操作とを行い、さらに上記量子ビットＱＢｎ−１，ＱＡｎ−１，ＱＣ０に対するＭＡＪ演算操作を行うＷ２量子操作過程と、
θ＝２，…，ｎ−１のそれぞれについて降順で、上記量子ビットＱＢ０を制御ビットとし、上記量子ビットＱＡθを目標ビットとしたＣＮＯＴ演算操作と、上記量子ビットＱＢθ−１，ＱＡθ−１を制御ビットとし，上記量子ビットＱＢ０を目標ビットとしたトフォリ演算操作とを行うＷ３量子操作過程と、
上記量子ビットＱＡ０に対するＮＯＴ演算操作を行い、θ＝２，…，ｎ−１のそれぞれについて降順で、上記量子ビットＱＢ０，ＱＡ０を制御ビットとし，上記量子ビットＱＡθを目標ビットとしたトフォリ演算操作を行い、さらに、上記量子ビットＱＡ０に対するＮＯＴ演算操作を行い、上記量子ビットＱＢ０，ＱＡ０を制御ビットとし，上記量子ビットＱＡ１を目標ビットとしたトフォリ演算操作を行い、さらに、θ＝０，…，ｎ−１のそれぞれについて昇順で、上記量子ビットＱＡθを制御ビットとし、上記量子ビットＱＢθを目標ビットとしたＣＮＯＴ演算操作を行うＷ４量子操作過程と、を含む操作であり、
上記第１比較演算部で行われる上記比較量子操作は、
上記加算演算部で上記加算量子操作された上記量子ビットＱＢ０，…，ＱＢｎ−１，ＱＣ０の量子状態をそれぞれ反転させ、各量子状態を｜ｓ０’＞，…，｜ｓｎ−１’＞，｜ｓｎ’＞とする第１ＮＯＴ演算過程と、
上記第１ＮＯＴ演算過程で得られた各量子状態が｜ｓ０’＞，…，｜ｓｎ−１’＞，｜ｓｎ’＞の上記量子ビットＱＢ０，…，ＱＢｎ−１，ＱＣ０と、上記加算演算部で上記加算量子操作された上記量子ビットＱＡ０，…，ＱＡｎ−１，ＱＣ１とに対する最上位ビット演算量子操作を行い、当該量子ビットＱＢ０，…，ＱＢｎ−１，ＱＣ０の量子状態をそれぞれ、｜ｓ０’＞，…，｜ｓｎ−１’＞，｜ｓｎ’＞とし、当該量子ビットＱＡ０，…，ＱＡｎ−１の量子状態をそれぞれ｜ａ０＞，…，｜ａｎ−１＞とし、当該量子ビットＱＣ１の量子状態を｜ｘ＞（ｘはｓ’＋ｐ（ｓ’＝ｓｎ’ｓｎ−１’…ｓ０’）を２進ｎ＋２桁表記した際の最上位桁の値）とする最上位ビット演算過程と、
上記最上位ビット演算過程で上記最上位ビット演算量子操作された上記量子ビットＱＢ０，…，ＱＢｎ−１，ＱＣ０，ＱＣ１の量子状態をそれぞれ反転させ、各量子状態を｜ｓ０＞，…，｜ｓｎ−１＞，｜ｓｎ＞，｜ｙ＞とする第２ＮＯＴ演算過程と、を含む操作であり、
上記最上位ビット演算過程で行われる上記最上位ビット演算量子操作は、
上記量子ビットＱＡｎ−１を制御ビットとし、上記量子ビットＱＣ１を目標ビットとした制御ＮＯＴ演算を行う第１制御ＮＯＴ演算過程と、
上記第１制御ＮＯＴ演算過程による処理の後、上記量子ビットＱＡｎ−２，ＱＣ０を制御ビットとし、上記量子ビットＱＡｎ−１を目標ビットとしたトフォリ演算を施す第１トフォリ演算過程と、
上記第１トフォリ演算過程による処理の後、降順で各ｊ∈｛２，…，ｎ−１｝に対して、ｐｊ＝１である場合にのみ上記量子ビットＱＢｊにＮＯＴ演算を施し、ｐｊの値に拘らず上記量子ビットＱＡｊ−２，ＱＢｊとを制御ビットとして上記量子ビットＱＡｊ−１を目標ビットとしたトフォリ演算を施し、ｐｊ＝１である場合にのみ上記量子ビットＱＢｊにＮＯＴ演算を施す量子操作を実行する第１量子操作過程と、
上記第１量子操作過程による処理の後、ｐ１＝１である場合にのみ、上記量子ビットＱＢ１を制御ビットとし、上記量子ビットＱＡ０を目標ビットとした制御ＮＯＴ演算を施し、さらにその後、上記量子ビットＱＢ１にＮＯＴ演算を施す第２量子操作過程と、
上記第２量子操作過程による処理の後、ｐ０＝１である場合にのみ、上記量子ビットＱＢ０，ＱＢ１を制御ビットとし、上記量子ビットＱＡ０を目標ビットとしたトフォリ演算を施す第３量子演算過程と、
上記第３量子操作過程による処理の後、昇順で各ｊに対して、ｐｊ＝１である場合にのみ上記量子ビットＱＢｊを制御ビットとして上記量子ビットＱＡｊ−１を目標ビットとした制御ＮＯＴ演算を施し、ｐｊ＝１である場合にのみ上記量子ビットＱＢｊにＮＯＴ演算を施し、ｐｊの値に拘らず上記量子ビットＱＡｊ−２，ＱＢｊとを制御ビットとし、上記量子ビットＱＡｊ−１を目標ビットとしたトフォリ演算を施す量子操作を実行する第４量子操作過程と、
上記第４量子操作過程による処理の後、上記量子ビットＱＡｎ−２，ＱＣ０を制御ビットとし、上記量子ビットＱＡｎ−１を目標ビットとしたトフォリ演算を施す第２トフォリ演算過程と、
上記第２トフォリ演算過程による処理の後、上記量子ビットＱＡｎ−１を制御ビットとし、上記量子ビットＱＣ１を目標ビットとした制御ＮＯＴ演算を行う第２制御ＮＯＴ演算過程と、
上記第２制御ＮＯＴ演算による処理の後、上記量子ビットＱＡｎ−２，ＱＣ０を制御ビットとし、上記量子ビットＱＡｎ−１を目標ビットとしたトフォリ演算を施す第３トフォリ演算過程と、
上記第３トフォリ演算過程による処理の後、降順で各ｊに対し、上記第４量子操作過程の操作の逆演算操作を、上記量子ビットＱＡｊ−２，ＱＢｊ，ＱＡｊ−１に対して施す第５量子操作過程と、
上記第５量子操作過程による処理の後、ｐ０＝１である場合にのみ、上記量子ビットＱＢ０，ＱＢ１を制御ビットとし、上記量子ビットＱＡ０を目標ビットとしたトフォリ演算を施す第６量子演算過程と、
上記第６量子操作過程による処理の後、ｐ１＝１である場合にのみ、上記量子ビットＱＢ１にＮＯＴ演算を施し、さらにその後、上記量子ビットＱＢ１を制御ビットとし、上記量子ビットＱＡ０を目標ビットとした制御ＮＯＴ演算を施す第７量子操作過程と、
上記第７量子操作過程による処理の後、昇順で各ｊに対して、上記第１量子操作過程の演算操作を上記量子ビットＱＡｊ−２，ＱＢｊ，ＱＡｊ−１に対して施す第８量子操作過程と、
上記第８量子操作過程による処理の後、上記量子ビットＱＡｎ−２，ＱＣ０を制御ビットとし、上記量子ビットＱＡｎ−１を目標ビットとしたトフォリ演算を施す第４トフォリ演算過程と、を含む操作であり、
上記制御減算演算部は、
量子状態がそれぞれ｜ｓ０＞，…，｜ｓｎ−１＞，｜ｓｎ＞である上記量子ビットＱＢ０，・・・，ＱＢｎ−１，ＱＣ０に対して量子フーリエ変換を行い、上記量子ビットＱＢ０，・・・，ＱＢｎ−１，ＱＣ０の量子状態を｜Φ０（ｓ）＞，…，｜Φｎ−１（ｓ）＞，｜Φｎ（ｓ）＞にするＱＦＴ演算過程と、
上記量子ビットＱＣ１を制御ビットとし、上記量子ビットＱＢ０，・・・，ＱＢｎ−１，ＱＣ０，ＱＣ０を目標ビットとした制御ΦＡＤＤ（ｐ）−１演算操作を行う制御ΦＡＤＤ（ｐ）−１演算過程と、
上記量子ビットＱＢ０，・・・，ＱＢｎ−１，ＱＣ０に対して上記量子フーリエ変換の逆演算を行うＱＦＴ−１演算過程と、を実行し、
ｓ＝ｓｎｓｎ−１…ｓ０、ｋ＝０，…，ｎ、eは自然対数であり、
【数４】
0004829623.tif 000005
であり、
前記制御ΦＡＤＤ（ｐ）−１演算操作は、
上記量子ビットＱＣ１の量子状態が｜１＞の場合にのみ、上記量子ビットＱＢ０，・・・，ＱＢｎ−１，ＱＣ０に対するΦＡＤＤ（ｐ）−１演算操作を行う操作であり、
上記ΦＡＤＤ（ｐ）−１演算操作は、ΦＡＤＤ（ｐ）演算の逆演算であり、
上記ΦＡＤＤ（ｐ）演算は、
量子ビットＱＢｋの量子状態｜ｇｋ＞（ｋ＝０，…，ｎ）のそれぞれを
【数５】
0004829623.tif 000006
にする演算である、
ことを特徴とする量子演算装置。
【請求項５】
請求項４に記載の量子演算装置であって、
上記ｐは素数であり、
上記ａ，ｂは上記ｐ未満である、
ことを特徴とする量子演算装置。
【請求項６】
請求項４に記載の量子演算装置であって、
上記制御減算演算部による処理の後、上記量子ビットＱＣ０と上記量子ビットＱＣ１との量子状態を交換する交換演算部と、
上記交換演算部による処理の後、上記量子ビットＱＡ０，…，ＱＡｎ−１，ＱＢ０，…，ＱＢｎ−１，ＱＣ０に対する第２比較量子操作を行い、上記量子ビットＱＡ０，…，ＱＡｎ−１，ＱＢ０，…，ＱＢｎ−１の量子状態を当該量子操作前のものとし、上記量子ビットＱＣ０の量子状態を｜γ（＋）δ＞（γ（＋）δはγとδとの排他的論理和を示し、γは当該量子操作前の上記量子ビットＱＣ０の量子状態が示す値であり、上記量子ビットＱＢｉの各量子状態が示す値をｉ＋１桁目の値とした２進ｎ桁の数βが、上記量子ビットＱＡｉの各量子状態が示す値をｉ＋１桁目の値とした２進ｎ桁の数α以上である場合δ＝１であり、βがα未満である場合δ＝０である）とする第２比較演算部と、
上記第２比較演算部による処理の後、上記量子ビットＱＣ０にＮＯＴ演算を施す第３ＮＯＴ演算部と、
を有し、
上記第２比較演算部で行われる上記第２比較量子操作は、
上記量子ビットＱＢ０，・・・，ＱＢｎ−１に対するＮＯＴ演算操作を行い、θ＝１，…，ｎ−１のそれぞれについて昇順で、上記量子ビットＱＣ０を制御ビットとし、上記量子ビットＱＡθを目標ビットとしたＣＮＯＴ演算操作と、上記量子ビットＱＣ０を制御ビットとし、上記量子ビットＱＢθを目標ビットとしたＣＮＯＴ演算操作とを行うＴ１量子操作過程と、
上記量子ビットＱＡ０，ＱＢ０を制御ビットとし，上記量子ビットＱＣ０を目標ビットとしたトフォリ演算操作を行い、θ＝１，…，ｎ−２のそれぞれについて昇順で、上記量子ビットＱＢθ，ＱＡθ，ＱＣ０に対するＭＡＪ演算操作と、上記量子ビットＱＢθ，ＱＡθを制御ビットとし、上記量子ビットＱＢ０を目標ビットとしたトフォリ演算操作とを行い、さらに上記量子ビットＱＢｎ−１，ＱＡｎ−１，ＱＣ０に対するＭＡＪ演算操作を行うＴ２量子操作過程と、
θ＝２，…，ｎ−１のそれぞれについて降順で、上記量子ビットＱＢ０を制御ビットとし、上記量子ビットＱＡθを目標ビットとしたＣＮＯＴ演算操作と、上記量子ビットＱＢ０を制御ビットとし、上記量子ビットＱＢθを目標ビットとしたＣＮＯＴ演算操作と、上記量子ビットＱＡθ−１，ＱＢθ−１を制御ビットとし，上記量子ビットＱＢ０を目標ビットとしたトフォリ演算操作とを行うＴ３量子操作過程と、
上記量子ビットＱＡ０に対するＮＯＴ演算操作を行い、θ＝２，…，ｎ−１のそれぞれについて降順で、上記量子ビットＱＢ０，ＱＡ０を制御ビットとし、上記量子ビットＱＡθを目標ビットとしたトフォリ演算操作を行い、上記量子ビットＱＢ０，ＱＡ０を制御ビットとし、上記量子ビットＱＢθを目標ビットとしたトフォリ演算操作を行い、さらに、上記量子ビットＱＡ０に対するＮＯＴ演算操作を行い、上記量子ビットＱＢ０，ＱＡ０を制御ビットとし、上記量子ビットＱＡ1を目標ビットとしたトフォリ演算操作を行い、上記量子ビットＱＢ０，ＱＡ０を制御ビットとし、上記量子ビットＱＢ1を目標ビットとしたトフォリ演算操作を行い、上記量子ビットＱＢ０，…，ＱＢｎ−１，ＱＣ０に対するＮＯＴ演算操作を行うＴ４量子操作過程と、を含む操作である、
ことを特徴とする量子演算装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、量子コンピュータ技術に関し、特に、剰余演算を行う技術に関する。
【背景技術】
【０００２】
ｎ＋２個の補助ビットを用い、Ｏ（ｎ）個の基本演算を、Ｏ（ｎ）個の計算ステップで実行することにより、有限体（ガロア体）ＧＦ（ｐ）上の加算を行う量子回路（「従来技術１」と呼ぶ）が知られている（例えば、非特許文献１参照）。また、２個の補助ビットを用い、量子フーリエ変換及びその逆演算それぞれ３個とＯ（ｎ）個の基本演算とを、Ｏ（ｎ）個の計算ステップで実行することにより、有限体ＧＦ（ｐ）上の加算を行う量子回路（「従来技術２」と呼ぶ）も知られている（例えば、非特許文献１参照）。なお、ｐは素数であり、ｎはｐを２進数表現した場合のビット長である。また、基本演算とは、１量子ビットに対する演算とＣＮＯＴ（制御ＮＯＴ）演算とを意味する。さらに、量子回路とは、基本演算の集合を意味する。
【０００３】
〔従来技術１〕
従来技術１の量子回路は、ｐよりも小さい２つの２進数ａ＝ａｎ−１…ａ０（ａｉ∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝）及びｂ＝ｂｎ−１…ｂ０（ｂｉ∈｛０，１｝）が入力として与えられたとき、ＧＦ（ｐ）上の加算（ａ＋ｂ）ｍｏｄ  ｐ＝ｕｎ−１…ｕ０（ｕｉ∈｛０，１｝）を行い、ｕｎ−１…ｕ０とａとを出力する。
図３５は、ｎ＝５の場合における従来技術１の量子回路図である。なお、図３５では、ｎ＝５の場合の量子回路を示すが、これをｎに一般化することは容易である。また、量子回路の基本単位は上述の基本演算であるが、図が複雑になるのを防ぐため、以下では基本演算以外の演算をも用いて量子回路を表現する。すなわち、図３５に示す全ての演算は、１量子ビットに対する演算とＣＮＯＴ演算とに分解できる。
【０００４】
図３５の量子回路は、ＡＤＤ１演算と、ＡＤＤ１（ｐ）−１演算と、ＣＮＯＴ演算と、ＡＤＤ１（ｐ）演算と、ＡＤＤ１−１演算と、ＮＯＴ演算とによって構成される。なお、ＡＤＤ１（ｐ）−１演算は、ＡＤＤ１（ｐ）演算の逆演算を表し、ＡＤＤ１−１演算は、ＡＤＤ１演算の逆演算を表す。また、ＱＡｉ，ＱＢｉ（ｉ＝｛０，...，ｎ−１｝）及びＱＣｉ’（ｉ’＝｛０，...，ｎ−１，ｎ，ｎ＋１｝）は量子ビットであり、これらのうちＱＣｉ’は補助ビットである。また、ΦＡＤＤ１（ｐ）演算は、量子ビットＱＣｎ＋１を制御ビットとした制御演算である。
【０００５】
図３６は、図３５におけるＡＤＤ１演算の量子回路図である。なお、「（＋）」は排他的論理和演算（２を法とした加算）を表す。また、ＣはＣＡＲＲＹ演算を、ＳはＳＵＭ演算をそれぞれ表し、Ｃ−１はＣの逆演算を表す。図３７（ａ）は、このＣＡＲＲＹ演算を示す量子回路図であり、図３７（ｂ）は、このＳＵＭ演算を示す量子回路図である。図３７（ａ）に示すように、ＣＡＲＲＹ演算は、４つの量子ビットを用いた量子操作であり、２つのＣＮＯＴ演算と１つのトフォリ（Toffoli）演算とにより構成される。また、図３７（ｂ）に示すように、ＳＵＭ演算は、３つの量子ビットを用いた量子操作であり、２つのＣＮＯＴ演算により構成される。また、図３８（ａ）はトフォリ演算を示し、図３８（ｂ）はＣＮＯＴ演算を示し、図３８（ｃ）はＮＯＴ演算を示す。また、図３９は、ＡＤＤ１（ｐ）演算の量子回路を示した図である。このＡＤＤ１（ｐ）演算は、ＡＤＤ１の一部の量子ビットの情報を古典情報に置き換えた構成となる。なお、図３９においてＮＯＴ演算を示す演算子を四角で囲んだ記号は、この四角の上に記載された古典情報ｐ４が１の場合にのみ、ＮＯＴ演算を行う演算子を示す。また、Ｃ（ｐ）はＣＡＲＲＹ（ｐ）演算を、Ｓ（ｐ）はＳＵＭ（ｐ）演算をそれぞれ表し、Ｃ（ｐ）−１はＣ（ｐ）の逆演算を表す。図４０（ａ）は、このＣＡＲＲＹ（ｐ）演算を示す量子回路図であり、図４０（ｂ）は、このＳＵＭ（ｐ）演算を示す量子回路図である。図４０（ａ）に示すように、ＣＡＲＲＹ（ｐ）演算は、３つの量子ビットを用いた量子操作であり、古典情報ｐｉが１である場合にのみ実行される１組のＣＮＯＴ演算及びＮＯＴ演算と、１つのトフォリ演算とにより構成される。また、図４０（ｂ）に示すように、ＳＵＭ（ｐ）演算は、２つの量子ビットを用いた量子操作であり、古典情報ｐｉが１である場合にのみ実行される１つのＮＯＴ演算と１つのＣＮＯＴ演算により構成される。
【０００６】
図３５の量子回路においてＧＦ（ｐ）上の加算（ａ＋ｂ）ｍｏｄ  ｐの演算を行う場合、まず、各量子ビットＱＡｉをａの各桁ａｉを示す量子状態｜ａｉ＞に、各量子ビットＱＢｉをｂの各桁ｂｉを示す量子状態｜ｂｉ＞に、各量子ビットＱＣｉ’を｜０＞に、それぞれ初期化する。そして、各量子ビットに対して図３５の量子回路が示す演算を施すことにより、量子ビットＱＡｉの量子状態が｜ａｉ＞となり、量子ビットＱＢｉの量子状態が｜ｕｉ＞となり、量子ビットＱＣｉ’の各量子状態が｜０＞となる。そして、演算後の量子ビットＱＢｉの量子状態を観測することにより演算結果ｕ＝ｕｎ−１…ｕ０を検出できる。
【０００７】
〔従来技術２〕
図４１は、ｎ＝５の場合における従来技術２の量子回路図である。この量子回路もＧＦ（ｐ）上の加算（ａ＋ｂ）ｍｏｄ  ｐの演算を行うための量子回路である。なお、図４１では、ｎ＝５の場合の量子回路を示すが、これをｎに一般化することは容易である。
図４１の量子回路は、ＱＦＴ（量子フーリエ変換）演算と、ＱＦＴ−１演算と、ΦＡＤＤ演算と、ΦＡＤＤ−１演算と、ΦＡＤＤ（ｐ）演算と、ΦＡＤＤ（ｐ）−１演算と、ＣＮＯＴ演算と、ＮＯＴ演算とによって構成される。なお、ＱＦＴ−１演算は、ＱＦＴ演算の逆演算を表し、ΦＡＤＤ−１演算は、ΦＡＤＤ演算の逆演算を表し、ΦＡＤＤ（ｐ）−１演算は、ΦＡＤＤ（ｐ）演算の逆演算を表す。また、ＱＡｉ，ＱＢｉ（ｉ＝｛０，...，ｎ−１｝）及びＱＣ０，ＱＣ１は量子ビットであり、これらのうちＱＣ０，ＱＣ１は補助ビットである。また、ΦＡＤＤ（ｐ）演算は、量子ビットＱＣ１を制御ビットとした制御演算である。
【０００８】
図４２は、このＱＦＴ演算を示す量子回路である。なお、図４２におけるＨはアダマール（Hadamard）変換演算を表し、ｋ（ｋ＝２，...，６）は制御回転演算を表す。また、図４３（ａ）は、このアダマール変換演算を表し、図４３（ｂ）は、この制御回転演算を表す。また、図４４は、ＱＦＴ演算とＱＦＴ−１演算との間に実行されるΦＡＤＤ変換を表した量子回路図である。また、図４５は、ΦＡＤＤ（ｐ）演算を表した量子回路図であり、図４６は、図４５のσｋ（ｆ）演算を表した量子回路図である。なお、図４５，図４６におけるｆは、ｆ＝ｆｎ−１…ｆ０（ｆｉ∈｛０，１｝）で表される２進数である。
【０００９】
図４１の量子回路においてＧＦ（ｐ）上の加算（ａ＋ｂ）ｍｏｄ  ｐの演算を行う場合、まず、各量子ビットＱＡｉをａの各桁ａｉを示す量子状態｜ａｉ＞に、各量子ビットＱＢｉをｂの各桁ｂｉを示す量子状態｜ｂｉ＞に、各量子ビットＱＣ０，ＱＣ１を｜０＞に、それぞれ初期化する。そして、各量子ビットに対して図４１の量子回路が示す演算を施すことにより、量子ビットＱＡｉの量子状態が｜ａｉ＞となり、量子ビットＱＢｉの量子状態が｜ｕｉ＞となり、量子ビットＱＣ０，ＱＣ１の各量子状態が｜０＞となる。そして、演算後の量子ビットＱＢｉの量子状態を観測することにより演算結果ｕ＝ｕｎ−１…ｕ０を検出できる。
【非特許文献１】S. Beauregard, G. Brassard, and J. M. Fernandez, Quantum Arithmetic on Galois Fields, quant-ph/0301163, 2003.
【非特許文献２】Y. Takahashi, A LINEAR-SIZE QUANTUM CIRCUIT FOR ADDITION WITH NO ANCILLARY QUBITS, Quantum Information and Computation, Vol. 5, No. 6 (2005) 440-448.
【発明の開示】
【発明が解決しようとする課題】
【００１０】
通常、多数の量子ビットを実現し、これらを協調的に操作することは物理的に困難である。そのため、補助ビットはできるだけ少ないほうがよい。また、補助ビットの数は同じでも基本演算の個数が多いほど誤りが発生する可能性は大きくなる。そのため、基本演算の個数はできるだけ少ないほうがよい。すなわち、演算誤り率の低減のためには、補助ビット数の削減と基本演算数の低減とを同時に満たす必要がある。
しかし、従来技術１の量子回路（図３５）は、まず、ＡＤＤ１演算においてａ＋ｂの加算値を求め、次のＡＤＤ１（ｐ）−１演算でａ＋ｂ−ｐの正負を求め（ａ＋ｂとｐとの大小比較）、ａ＋ｂ−ｐが正である場合には、ａ＋ｂ−ｐを（ａ＋ｂ）ｍｏｄ  ｐの演算結果とし、負である場合にはＡＤＤ１（ｐ）演算によって（ａ＋ｂ−ｐ）＋ｐの演算を行い、それを（ａ＋ｂ）ｍｏｄ  ｐの演算結果とする構成である。なお、ＡＤＤ１−１以降の処理は、量子ビットＱＣ０，ＱＣ６の量子状態をそれぞれ｜０＞にするための処理である。この構成の場合、ＡＤＤ１（ｐ）−１演算でａ＋ｂ−ｐの正負を求めるためにＱＣ０…ＱＣ５（ｎ＋１個）の補助ビットが必要となる。そのため、さらに必要な１つの補助ビットと併せて合計ｎ＋２個もの補助ビットが必要となる。
【００１１】
一方、従来技術２の量子回路（図４１）では、ａ＋ｂの加算値を求めてａ＋ｂ−ｐの正負を求める処理と、ａ＋ｂ−ｐの正負に応じてａ＋ｂ−ｐ又は（ａ＋ｂ−ｐ）＋ｐを（ａ＋ｂ）ｍｏｄ  ｐの演算結果とする処理と、補助ビットの量子状態をそれぞれ｜０＞にするための処理とを、それぞれ量子フーリエ変換後（ＱＦＴ演算）に行い、各処理後に逆量子フーリエ変換（ＱＦＴ−１演算）を行うといった過程をとることにより、補助ビット数を削減していた。この場合、補助ビット数は削減できるが、Ｏ（ｎ２）個の基本演算を要する３個のＱＦＴ演算と３個のＱＦＴ−１演算とが必要となる。
【００１２】
すなわち、従来技術１の量子回路は、（ｎ＋２）個の補助ビットを必要とするため補助ビット数が多く、従来技術２の量子回路は、Ｏ（ｎ２）個の基本演算を要する量子フーリエ変換演算を３個とその逆演算３個とを必要とするため基本演算数が多い。何れも演算誤り率の低減のために十分な構成とはいえない。
本発明はこのような点に鑑みてなされたものであり、（ａ＋ｂ）ｍｏｄ  ｐの演算を行う量子演算技術において、補助ビット数の削減と基本演算数の低減とを同時に行い、演算誤り率を低減させることが可能な技術を提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明では上記課題を解決するために、２つの２進数ａ＝ａｎ−１…ａ０（ａｉ∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝）及びｂ＝ｂｎ−１…ｂ０（ｂｉ∈｛０，１｝）に対し、（ａ＋ｂ）ｍｏｄ  ｐ（ｐ＝ｐｎ−１…ｐ０，ｐｉ∈｛０，１｝，ａ＋ｂはｐの２倍未満）を算出する量子演算方法であって、ｎ個の量子ビットＱＡ０，…，ＱＡｎ−１の量子状態をそれぞれ｜ａ０＞，…，｜ａｎ−１＞とし、ｎ個の量子ビットＱＢ０，…，ＱＢｎ−１の量子状態をそれぞれ｜ｂ０＞，…，｜ｂｎ−１＞とし、２個の量子ビットＱＣ０，ＱＣ１の量子状態をそれぞれ｜０＞，｜０＞としておき、量子ビットＱＡ０，…，ＱＡｎ−１，ＱＢ０，…，ＱＢｎ−１，ＱＣ０に対する量子操作を行い、量子ビットＱＡ０，…，ＱＡｎ−１の量子状態をそれぞれ｜ａ０＞，…，｜ａｎ−１＞とし、量子ビットＱＢ０，…，ＱＢｎ−１の量子状態をそれぞれ、｜ｓ０＞，…，｜ｓｎ−１＞（ａ＋ｂ＝ｓｎ…ｓ０（ｓｋ∈｛０，１｝，ｋ∈｛０，…，ｎ｝））とし、量子ビットＱＣ０の量子状態を｜ｓｎ＞とする加算演算過程と、加算演算過程で量子操作された量子ビットＱＡ０，…，ＱＡｎ−１，ＱＢ０，…，ＱＢｎ−１，ＱＣ０と、量子ビットＱＣ１とに対する量子操作を行い、量子ビットＱＡ０，…，ＱＡｎ−１の量子状態をそれぞれ｜ａ０＞，…，｜ａｎ−１＞とし、量子ビットＱＢ０，…，ＱＢｎ−１の量子状態をそれぞれ｜ｓ０＞，…，｜ｓｎ−１＞とし、量子ビットＱＣ０の量子状態を｜ｓｎ＞とし、量子ビットＱＣ１の量子状態を｜ｙ＞（ｐ≦ａ＋ｂの場合ｙ＝１、ｐ＞ａ＋ｂの場合ｙ＝０）とする第１比較演算過程と、第１比較演算過程で量子操作された量子ビットＱＣ１の量子状態が｜１＞であった場合にのみ、第１比較演算過程で量子操作された量子ビットＱＢ０，…，ＱＢｎ−１の量子状態をそれぞれ｜ｔ０＞，…，｜ｔｎ−１＞（ａ＋ｂ−ｐ＝ｔｎ−１…ｔ０（ｔｉ∈｛０，１｝））とし、量子ビットＱＣ０の量子状態を｜０＞とする制御減算演算過程とを実行する量子演算方法が提供される。なお、「量子ビットＱの量子状態を｜τ＞とする」とは、量子ビットＱの量子状態を、｜τ＞と他の量子状態との重ね合わせ状態にすることをも含む概念である。
【００１４】
ここで、本発明の第１比較演算過程では、ａ＋ｂの情報が乗せられた量子ビットＱＢ０，…，ＱＢｎ−１だけではなく、量子ビットＱＡ０，…，ＱＡｎ−１に対しても量子操作を行い、ａ＋ｂとｐとの大小比較を行っている。これに対し、従来技術１の比較演算（ＡＤＤ１（ｐ）−１演算）では、量子ビットＱＡ０，…，ＱＡｎ−１は全く利用されていない。本発明では、このように量子ビットＱＡ０，…，ＱＡｎ−１を有効利用することにより、従来技術１で必要とされていた補助ビットの一部を不要とする。その結果、補助ビット数の削減が可能となる。さらに、本形態の第１比較演算過程は量子フーリエ変換後に行う必要もないため、従来技術２のように多くの量子フーリエ変換演算も必要としない。
【００１５】
また、本発明において好ましくは、ｐは素数であり、ａ，ｂはｐ未満である。この場合、ｐを位数とした有限体上の演算が可能となる。
また、本発明において好ましくは、第１比較演算過程は、加算演算過程で量子操作された量子ビットＱＢ０，…，ＱＢｎ−１，ＱＣ０の量子状態をそれぞれ反転させ、各量子状態を｜ｓ０’＞，…，｜ｓｎ−１’＞，｜ｓｎ’＞とする第１ＮＯＴ演算過程と、第１ＮＯＴ演算過程で量子操作された量子ビットＱＢ０，…，ＱＢｎ−１，ＱＣ０と、加算演算過程で量子操作された量子ビットＱＡ０，…，ＱＡｎ−１，ＱＣ１とに対する量子操作を行い、当該量子ビットＱＢ０，…，ＱＢｎ−１，ＱＣ０の量子状態をそれぞれ、｜ｓ０’＞，…，｜ｓｎ−１’＞，｜ｓｎ’＞とし、当該量子ビットＱＡ０，…，ＱＡｎ−１の量子状態をそれぞれ｜ａ０＞，…，｜ａｎ−１＞とし、当該量子ビットＱＣ１の量子状態を｜ｘ＞（ｘはｓ’＋ｐ（ｓ’＝ｓｎ’ｓｎ−１’…ｓ０’）を２進ｎ＋２桁表記した際の最上位桁の値）とする最上位ビット演算過程と、最上位ビット演算過程で量子操作された量子ビットＱＢ０，…，ＱＢｎ−１，ＱＣ０，ＱＣ１の量子状態をそれぞれ反転させ、各量子状態を｜ｓ０＞，…，｜ｓｎ−１＞，｜ｓｎ＞，｜ｙ＞とする第２ＮＯＴ演算過程とを有する。
【００１６】
ここで、この第１比較演算過程では、ａ＋ｂの情報が乗せられている量子ビットＱＢ０，…，ＱＢｎ−１だけではなく、量子ビットＱＡ０，…，ＱＡｎ−１をも有効利用し、補助ビット数の削減を図っている。また、この第１比較演算過程は量子フーリエ変換後に行う必要もない。
また、本発明において好ましくは、最上位ビット演算過程は、量子ビットＱＡｎ−１を制御ビットとし、量子ビットＱＣ１を目標ビットとした制御ＮＯＴ演算を行う第１制御ＮＯＴ演算過程と、第１制御ＮＯＴ演算過程による処理の後、量子ビットＱＡｎ−２，ＱＣ０を制御ビットとし、量子ビットＱＡｎ−１を目標ビットとしたトフォリ演算を施す第１トフォリ演算過程と、第１トフォリ演算過程による処理の後、降順で各ｊ∈｛２，…，ｎ−１｝に対して、ｐｊ＝１である場合にのみ量子ビットＱＢｊにＮＯＴ演算を施し、ｐｊの値に拘らず量子ビットＱＡｊ−２，ＱＢｊとを制御ビットとして量子ビットＱＡｊ−１を目標ビットとしたトフォリ演算を施し、ｐｊ＝１である場合にのみ量子ビットＱＢｊにＮＯＴ演算を施す量子操作を実行する第１量子操作過程と、第１量子操作過程による処理の後、ｐ１＝１である場合にのみ、量子ビットＱＢ１を制御ビットとし、量子ビットＱＡ０を目標ビットとした制御ＮＯＴ演算を施し、さらにその後、量子ビットＱＢ１にＮＯＴ演算を施す第２量子操作過程と、第２量子操作過程による処理の後、ｐ０＝１である場合にのみ、量子ビットＱＢ０，ＱＢ１を制御ビットとし、量子ビットＱＡ０を目標ビットとしたトフォリ演算を施す第３量子演算過程と、第３量子操作過程による処理の後、昇順で各ｊに対して、ｐｊ＝１である場合にのみ量子ビットＱＢｊを制御ビットとして量子ビットＱＡｊ−１を目標ビットとした制御ＮＯＴ演算を施し、ｐｊ＝１である場合にのみ量子ビットＱＢｊにＮＯＴ演算を施し、ｐｊの値に拘らず量子ビットＱＡｊ−２，ＱＢｊとを制御ビットとし、量子ビットＱＡｊ−１を目標ビットとしたトフォリ演算を施す量子操作を実行する第４量子操作過程と、第４量子操作過程による処理の後、量子ビットＱＡｎ−２，ＱＣ０を制御ビットとし、量子ビットＱＡｎ−１を目標ビットとしたトフォリ演算を施す第２トフォリ演算過程と、第２トフォリ演算過程による処理の後、量子ビットＱＡｎ−１を制御ビットとし、量子ビットＱＣ１を目標ビットとした制御ＮＯＴ演算を行う第２制御ＮＯＴ演算過程と、第２制御ＮＯＴ演算による処理の後、量子ビットＱＡｎ−２，ＱＣ０を制御ビットとし、量子ビットＱＡｎ−１を目標ビットとしたトフォリ演算を施す第３トフォリ演算過程と、第３トフォリ演算過程による処理の後、降順で各ｊに対し、第４量子操作過程の操作の逆演算操作を、量子ビットＱＡｊ−２，ＱＢｊ，ＱＡｊ−１に対して施す第５量子操作過程と、第５量子操作過程による処理の後、ｐ０＝１である場合にのみ、量子ビットＱＢ０，ＱＢ１を制御ビットとし、量子ビットＱＡ０を目標ビットとしたトフォリ演算を施す第６量子演算過程と、第６量子操作過程による処理の後、ｐ１＝１である場合にのみ、量子ビットＱＢ１にＮＯＴ演算を施し、さらにその後、量子ビットＱＢ１を制御ビットとし、量子ビットＱＡ０を目標ビットとした制御ＮＯＴ演算を施す第７量子操作過程と、第７量子操作過程による処理の後、昇順で各ｊに対して、第１量子操作過程の演算操作を量子ビットＱＡｊ−２，ＱＢｊ，ＱＡｊ−１に対して施す第８量子操作過程と、第８量子操作過程による処理の後、量子ビットＱＡｎ−２，ＱＣ０を制御ビットとし、量子ビットＱＡｎ−１を目標ビットとしたトフォリ演算を施す第４トフォリ演算過程とを有する。なお、ｐ０，…，ｐｎ−１は、古典ビット情報でもよいし、量子ビット情報でもよいし、これらの混合でもよい。
【００１７】
ここで、この最上位ビット演算過程では、ａ＋ｂの情報が乗せられている量子ビットＱＢ０，…，ＱＢｎ−１だけではなく、量子ビットＱＡ０，…，ＱＡｎ−１をも有効利用し、補助ビット数の削減を図っている。また、この上位ビット演算過程は量子フーリエ変換後に行う必要もない。その結果、ＮＯＴ演算過程と最上位ビット演算過程とからなる第１比較演算過程で必要となる補助ビット数の削減と、基本演算数の低減とが可能となる。
また、本発明において好ましくは、制御減算演算過程による処理の後、量子ビットＱＣ０と量子ビットＱＣ１との量子状態を交換する交換演算過程と、交換演算過程による処理の後、量子ビットＱＡ０，…，ＱＡｎ−１，ＱＢ０，…，ＱＢｎ−１，ＱＣ０に対する量子操作を行い、量子ビットＱＡ０，…，ＱＡｎ−１，ＱＢ０，…，ＱＢｎ−１の量子状態を当該量子操作前のものとし、量子ビットＱＣ０の量子状態を｜γ（＋）δ＞（γ（＋）δはγとδとの排他的論理和を示し、γは当該量子操作前の量子ビットＱＣ０の量子状態が示す値であり、量子ビットＱＢｉの各量子状態が示す値をｉ＋１桁目の値とした２進ｎ桁の数βが、量子ビットＱＡｉの各量子状態が示す値をｉ＋１桁目の値とした２進ｎ桁の数α以上である場合δ＝１であり、βがα未満である場合δ＝０である）とする第２比較演算過程と、第２比較演算過程による処理の後、量子ビットＱＣ０にＮＯＴ演算を施す第３ＮＯＴ演算過程とを有する。
【００１８】
これにより、補助ビットの量子状態を全て｜０＞とすることが可能となり、上述の量子演算が施された各量子ビットを別の量子演算の入力ビットとして利用することが容易となる。
【発明の効果】
【００１９】
本発明では、（ａ＋ｂ）ｍｏｄ  ｐの演算を行う量子演算において、補助ビット数の削減と基本演算数の低減とを同時に行い、演算誤り率を低減させることができる。
【発明を実施するための最良の形態】
【００２０】
以下、本発明を実施するための最良の形態を図面を参照して説明する。
〔第１の実施の形態〕
まず、本発明における第１の実施の形態について説明する。
＜構成＞
図１は、第１の実施の形態における量子演算装置１の構成を示したブロック図である。
図１に示すように、本形態の量子演算装置１は、量子ビット１０と、メモリ２０と、演算制御部３０と、量子演算部４０とを有している。ここで、量子ビット１０は、ｎ個の量子ビットＱＡ０，…，ＱＡｎ−１と、ｎ個の量子ビットＱＢ０，…，ＱＢｎ−１と、２個の量子ビットＱＣ０，ＱＣ１とによって構成される。また、メモリ２０にはｐｎ−１，…，ｐ０の値が格納されている。また、量子演算部４０は、初期量子状態生成過程を実行する初期量子状態生成部４１と、加算演算過程を実行する加算演算部４２と、第１比較演算過程を実行する比較演算部４３と、制御減算演算過程を実行する制御減算演算部４４と、交換演算過程を実行する交換演算部４５と、第２比較演算過程を実行する比較演算部４６と、ＮＯＴ演算過程を実行するＮＯＴ演算部４７とを有している。これらの加算演算部４２と、比較演算部４３と、制御減算演算部４４と、交換演算部４５と、比較演算部４６と、ＮＯＴ演算部４７との各機能は、基本演算単体或いは基本演算の組合せによって実現される。
【００２１】
図２は、これらの各機能を実現するための基本演算を表した図である。
図２（ａ）は、１量子ビットに対するＮＯＴ演算を表す。図２（ａ）に示すように、ＮＯＴ演算は、１量子ビットの量子状態を｜ｄ＞（ｄ∈｛０，１｝）から｜ｄ（＋）１＞に変換する量子操作である。なお、（＋）は排他的論理和を示す演算子である。
図２（ｂ）は、１量子ビットに対するアダマール変換を表す。図２（ｂ）に示すように、アダマール変換は、１量子ビットの量子状態を｜ｄ＞（ｄ∈｛０，１｝）から、｛１／（√２）｝｜０＞＋｛（−１）ｄ／（√２）｝｜１＞に変換する量子操作である。
【００２２】
図２（ｃ）は、１量子ビットに対するｋ回転演算を表す。図２（ｃ）に示すように、ｋ回転演算は、１量子ビットの量子状態を｜ｄ＞（ｄ∈｛０，１｝）から｛ｅｘｐ（２πｄｉ／２ｋ）｝｜ｄ＞に変換する量子操作である。なお、ｅｘｐは自然対数を示し、ｉは虚数単位を示す。ｋは自然数である。
図２（ｄ）は、２量子ビットに対するＣＮＯＴ（制御ＮＯＴ）演算を表す。図２（ｃ）に示すように、ＣＮＯＴ演算は、量子状態｜ｄ＞（ｄ∈｛０，１｝）の制御ビットと、量子状態｜ｆ＞（ｆ∈｛０，１｝）の目標ビットとに対する量子操作であり、制御ビットの量子状態を｜ｄ＞に、目標ビットの量子状態を｜ｆ（＋）ｄ＞にするものである。
【００２３】
＜処理＞
本形態では、２つの２進数ａ＝ａｎ−１…ａ０（ａｉ∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝，ｎは自然数）及びｂ＝ｂｎ−１…ｂ０（ｂｉ∈｛０，１｝）に対し、（ａ＋ｂ）ｍｏｄ  ｐ（ｐ＝ｐｎ−１…ｐ０，ｐｉ∈｛０，１｝，ａ＋ｂはｐの２倍未満）の演算を行う。また、本形態では、ｐを素数とし、ａ，ｂをｐ未満の値とする。すなわち、本形態では、位数ｐの有限体ＧＦ（ｐ）上でａとｂとの加算を行う。
［処理の全体］
図３は、第１の実施の形態の処理の全体を説明するためのフローチャートである。また、図１２は、第１の実施の形態の量子操作全体を説明するための量子回路図（ｎ＝５の例）である。なお、図１２における横軸は時間の流れを示し、「入力」から「出力」に向けて時間が経過することを表している（以下同様な図についても同じ）。また、以下の各処理は、制御演算部３０の制御のもと実行される。
【００２４】
まず、初期量子状態生成部４１が、ｎ個の量子ビットＱＡ０，…，ＱＡｎ−１の量子状態をそれぞれ｜ａ０＞，…，｜ａｎ−１＞とし、ｎ個の量子ビットＱＢ０，…，ＱＢｎ−１の量子状態をそれぞれ｜ｂ０＞，…，｜ｂｎ−１＞とし、２個の量子ビットＱＣ０，ＱＣ１の量子状態をそれぞれ｜０＞，｜０＞とする（初期量子状態生成過程／ステップＳ１）。
次に、加算演算部４２が、量子ビットＱＡ０，…，ＱＡｎ−１，ＱＢ０，…，ＱＢｎ−１，ＱＣ０に対する量子操作を行い、量子ビットＱＡ０，…，ＱＡｎ−１の量子状態をそれぞれ｜ａ０＞，…，｜ａｎ−１＞とし、量子ビットＱＢ０，…，ＱＢｎ−１の量子状態をそれぞれ、｜ｓ０＞，…，｜ｓｎ−１＞（ａ＋ｂ＝ｓｎ…ｓ０（ｓｋ∈｛０，１｝，ｋ∈｛０，…，ｎ｝））とし、量子ビットＱＣ０の量子状態を｜ｓｎ＞とする（加算演算過程〔ＡＤＤ〕／ステップＳ２）。
【００２５】
次に、比較演算部４３が、加算演算過程で量子操作された量子ビットＱＡ０，…，ＱＡｎ−１，ＱＢ０，…，ＱＢｎ−１，ＱＣ０と、量子ビットＱＣ１とに対する量子操作を行い、量子ビットＱＡ０，…，ＱＡｎ−１の量子状態をそれぞれ｜ａ０＞，…，｜ａｎ−１＞とし、量子ビットＱＢ０，…，ＱＢｎ−１の量子状態をそれぞれ｜ｓ０＞，…，｜ｓｎ−１＞とし、量子ビットＱＣ０の量子状態を｜ｓｎ＞とし、量子ビットＱＣ１の量子状態を｜ｙ＞（ｐ≦ａ＋ｂの場合ｙ＝１、ｐ＞ａ＋ｂの場合ｙ＝０）とする（第１比較演算過程〔ＣＯＭＰＡＲＩＳＯＮ（ｐ）〕／ステップＳ３）。
【００２６】
次に、制御減算演算部４４が、第１比較演算過程で量子操作された量子ビットＱＣ１の量子状態が｜１＞であった場合にのみ、第１比較演算過程で量子操作された量子ビットＱＢ０，…，ＱＢｎ−１の量子状態をそれぞれ｜ｔ０＞，…，｜ｔｎ−１＞（ａ＋ｂ−ｐ＝ｔｎ−１…ｔ０（ｔｉ∈｛０，１｝））とし、量子ビットＱＣ０の量子状態を｜０＞とする（制御減算演算過程〔ＱＦＴ，ΦＡＤＤ（ｐ）−１，ＱＦＴ−１〕／ステップＳ４）。
次に、交換演算部４５が、量子ビットＱＣ０と量子ビットＱＣ１との量子状態を交換する（交換演算過程〔ＳＷＡＰ〕／ステップＳ５）。
【００２７】
次に、比較演算部４６が、量子ビットＱＡ０，…，ＱＡｎ−１，ＱＢ０，…，ＱＢｎ−１，ＱＣ０に対する量子操作を行い、量子ビットＱＡ０，…，ＱＡｎ−１，ＱＢ０，…，ＱＢｎ−１の量子状態を当該量子操作前のものとし、量子ビットＱＣ０の量子状態を｜γ（＋）δ＞とする（第２比較演算過程〔ＣＯＭＰ〕／ステップＳ６）。なお、γは第２比較演算過程直前の量子ビットＱＣ０の量子状態が示す値である。また、δは、β≧αの場合はδ＝１，β＜αの場合はδ＝０と定義される値である。なお、αは、量子ビットＱＡｉの各量子状態が示す値をｉ＋１桁目の値とした２進ｎ桁の数を示す。また、βは、量子ビットＱＢｉの各量子状態が示す値をｉ＋１桁目の値とした２進ｎ桁の数を示す。
【００２８】
そして、最後にＮＯＴ演算部４７が、量子ビットＱＣ０にＮＯＴ演算を施す（ＮＯＴ演算過程／ステップＳ７）。
以上の量子操作により、ｎ個の量子ビットＱＡ０，…，ＱＡｎ−１の量子状態がそれぞれ｜ａ０＞，…，｜ａｎ−１＞となり、ｎ個の量子ビットＱＢ０，…，ＱＢｎ−１の量子状態をそれぞれ｜ｕ０＞，…，｜ｕｎ−１＞となり、２個の量子ビットＱＣ０，ＱＣ１の量子状態をそれぞれ｜０＞，｜０＞となる。
［加算演算過程〔ＡＤＤ〕／ステップＳ２の詳細］
次に、加算演算過程〔ＡＤＤ〕／ステップＳ２の詳細を説明する。
【００２９】
図４及び図５は、加算演算過程〔ＡＤＤ〕／ステップＳ２の詳細を説明するためのフローチャートである。また、図１３は、加算演算過程〔ＡＤＤ〕の量子操作全体を説明するための量子回路図（ｎ＝５の例）である。また、図１４〜図１７は、図１３のＷ１〜Ｗ４の各量子操作を説明するための量子回路図である。また、図１８（ａ）は、図１５に示すＭＡＪ（majority）演算を説明するための量子回路図である。
加算演算過程〔ＡＤＤ〕は、量子状態が｜ａ０＞，…，｜ａｎ−１＞のｎ個の量子ビットＱＡ０，…，ＱＡｎ−１と、量子状態が｜ｂ０＞，…，｜ｂｎ−１＞のｎ個の量子ビットＱＢ０，…，ＱＢｎ−１と、量子状態が｜０＞の量子ビットＱＣ０とに対する量子操作であり、以下のＷ１〜Ｗ４の量子操作が実行される。
【００３０】
［Ｗ１の量子操作］
まず、演算制御部３０は、変数θに１を代入し、これをメモリ２０に格納する（ステップＳ１１）。次に、演算制御部３０はメモリ２０に格納された変数θを読み込み、この変数θに応じた命令を加算演算部４２に与える。これに対し、加算演算部４２は、ＱＡθ，ＱＣ０に対するＣＮＯＴ演算操作と、ＱＢθ，ＱＣ０に対するＣＮＯＴ演算操作とを実行（制御ビットＱＣ０，目標ビットＱＡθ，ＱＢθ）する（ステップＳ１２）。
次に、演算制御部３０は、メモリ２０に格納された変数θを読み込み、この変数θがｎ−１であるか否かを判断する（ステップＳ１３）。なお、ｎは事前に設定された値である。ここで、θ＝ｎ−１でなければ、演算制御部３０は、メモリ２０の変数θに１を加えた値を新たなθとしてメモリ２０に格納し、処理をステップＳ１２に戻す（ステップＳ１４）。一方、θ＝ｎ−１であれば、以下のＷ２の量子操作に移る。
【００３１】
［Ｗ２の量子操作］
まず、加算演算部４２が、量子ビットＱＡ０，ＱＢ０，ＱＣ０に対するトフォリ演算操作（制御ビットＱＡ０，ＱＢ０，目標ビットＱＣ０）を行う（ステップＳ１５）。
次に、演算制御部３０が、変数θに１を代入し、これをメモリ２０に格納する（ステップＳ１６）。そして、演算制御部３０はメモリ２０に格納された変数θを読み込み、この変数θに応じた命令を加算演算部４２に与える。加算演算部４２は、量子ビットＱＢθ，ＱＡθ，ＱＣ０に対するＭＡＪ演算操作を行う（ステップＳ１７）。なお、図１８（ａ）に示すように、ＭＡＪ演算操作は３量子ビットに対する量子操作である。図１８（ａ）の入力（１），（２），（３）に対応する各量子ビットの量子状態を｜ｖ１＞，｜ｖ２＞，｜ｖ３＞とした場合、ＭＡＪ演算操作後の各量子ビットの量子状態は、｜ｖ１（＋）ｖ３＞，｜ｖ２（＋）ｖ３＞，｜ｖ１ｖ２（＋）ｖ２ｖ３（＋）ｖ３ｖ１＞となる。また、ステップＳ１７のＭＡＪ演算操作は、量子ビットＱＢθ，ＱＡθ，ＱＣ０を、それぞれ、図１８（ａ）の入力（１），（２），（３）として行う。次に、加算演算部４２は、量子ビットＱＢ０，ＱＢθ，ＱＡθに対するトフォリ演算操作（制御ビットＱＢθ，ＱＡθ、目標ビットＱＢ０）を行う（ステップＳ１８）。
【００３２】
次に、演算制御部３０は、メモリ２０に格納された変数θを読み込み、この変数θがｎ−２であるか否かを判断する（ステップＳ１９）。ここで、θ＝ｎ−２でなければ、演算制御部３０は、メモリ２０の変数θに１を加えた値を新たなθとしてメモリ２０に格納し、処理をステップＳ１７に戻す（ステップＳ２０）。一方、θ＝ｎ−２であれば、加算演算部４２に命令を与え、加算演算部４２は、量子ビットＱＢｎ−１，ＱＡｎ−１，ＱＣ０に対するＭＡＪ演算操作を行う（ステップＳ２１）。なお、このＭＡＪ演算操作は、量子ビットＱＢｎ−１，ＱＡｎ−１，ＱＣ０を、それぞれ、図１８（ａ）の入力（１），（２），（３）として行う。
【００３３】
［Ｗ３の量子操作］
次に、演算制御部３０は、変数θにｎ−１を代入し、これをメモリ２０に格納する（ステップＳ２２）。次に、演算制御部３０はメモリ２０に格納された変数θを読み込み、この変数θに応じた命令を加算演算部４２に与える。これを受けた加算演算部４２は、量子ビットＱＢ０，ＱＡθに対するＣＮＯＴ演算操作（制御ビットＱＢ０、目標ビットＱＡθ）を行う（ステップＳ２３）。次に、加算演算部４２において、量子ビットＱＢ０，ＱＢθ−１，ＱＡθ−１に対するトフォリ演算操作（制御ビットＱＢθ−１，ＱＡθ−１、目標ビットＱＢ０）を行う（ステップＳ２４）。
【００３４】
次に、演算制御部３０は、メモリ２０に格納された変数θを読み込み、この変数θが２であるか否かを判断する（ステップＳ２５）。ここで、θ＝２でなければ、演算制御部３０は、メモリ２０の変数θから１を引いた値を新たなθとしてメモリ２０に格納し、処理をステップＳ２３に戻す（ステップＳ２６）。一方、θ＝２であれば、以下のＷ４の量子操作に移る。
［Ｗ４の量子操作］
まず、加算演算部４２が、量子ビットＱＡ０に対するＮＯＴ演算操作を行う（ステップＳ２７）。次に、演算制御部３０は、変数θにｎ−１を代入し、これをメモリ２０に格納する（ステップＳ２８）。次に、演算制御部３０は、メモリ２０に格納された変数θを読み込み、この変数θに応じた命令を加算演算部４２に与える。これを受けた加算演算部４２は、量子ビットＱＢ０，ＱＡ０，ＱＡθに対するトフォリ演算操作（制御ビットＱＢ０，ＱＡ０、目標ビットＱＡθ）を行う（ステップＳ２９）。
【００３５】
次に、演算制御部３０は、メモリ２０に格納された変数θを読み込み、この変数θが２であるか否かを判断する（ステップＳ３０）。ここで、θ＝２でなければ、演算制御部３０は、メモリ２０の変数θから１を引いた値を新たなθとしてメモリ２０に格納し、処理をステップＳ２９に戻す（ステップＳ３１）。一方、θ＝２であれば、加算演算部４２において、量子ビットＱＡ０に対するＮＯＴ演算操作を行い（ステップＳ３２）、さらに、量子ビットＱＢ０，ＱＡ０，ＱＡ１に対するトフォリ演算操作（制御ビットＱＢ０，ＱＡ０、目標ビットＱＡ１）を行う（ステップＳ３３）。
【００３６】
次に、演算制御部３０は、変数θに１を代入し、これをメモリ２０に格納する（ステップＳ３４）。次に、演算制御部３０は、メモリ２０に格納された変数θを読み込み、この変数θに応じた命令を加算演算部４２に与える。これを受けた加算演算部４２は、ＱＢθ，ＱＡθに対するＣＮＯＴ演算操作（制御ビットＱＡθ、目標ビットＱＢθ）を行う（ステップＳ３５）。次に、演算制御部３０は、メモリ２０に格納された変数θを読み込み、この変数θがｎ−１であるか否かを判断する（ステップＳ３６）。ここで、θ＝ｎ−１でなければ、演算制御部３０は、メモリ２０の変数θに１を加算した値を新たなθとしてメモリ２０に格納し、処理をステップＳ３５に戻す（ステップＳ３７）。一方、θ＝ｎ−１であれば、演算制御部３０は、加算演算過程〔ＡＤＤ〕を終了させる。なお、ステップＳ３４〜Ｓ３６の処理の代わりに、θ＝０〜ｎ−１についてのＱＢθ，ＱＡθに対するＣＮＯＴ演算操作（制御ビットＱＡθ、目標ビットＱＢθ）を一度に行っても良い。
【００３７】
以上の処理により、量子ビットＱＡ０，…，ＱＡｎ−１の量子状態がそれぞれ｜ａ０＞，…，｜ａｎ−１＞となり、量子ビットＱＢ０，…，ＱＢｎ−１の量子状態がそれぞれ｜ｓ０＞，…，｜ｓｎ−１＞なり、量子ビットＱＣ０の量子状態が｜０＋ｓｎ＞となる。なお、ｓ＝ａ＋ｂ，ｓ＝ｓｎ…ｓ０（ｓｋ∈｛０，１｝，ｋ∈｛０，…，ｎ｝）である（加算演算過程〔ＡＤＤ〕／ステップＳ２の詳細の説明終わり）。
［第１比較演算過程〔ＣＯＭＰＡＲＩＳＯＮ（ｐ）〕／ステップＳ３の詳細］
次に、第１比較演算過程〔ＣＯＭＰＡＲＩＳＯＮ（ｐ）〕／ステップＳ３の詳細について説明する。
【００３８】
図６は、第１比較演算過程〔ＣＯＭＰＡＲＩＳＯＮ（ｐ）〕／ステップＳ３の詳細の詳細を説明するためのフローチャートである。また、図７及び図８は、図６のステップＳ４６のＨＩＧＨＢＩＴ（ｐ）演算操作を説明するためのフローチャートである。また、図１９は、第１比較演算過程〔ＣＯＭＰＡＲＩＳＯＮ（ｐ）〕を説明するための量子回路図（ｎ＝５の例）である。また、図２０及び図２１は、ＨＩＧＨＢＩＴ（ｐ）演算を説明するための量子回路図である。さらに、図２２（ａ）は、図２０及び図２１のＡ（ｐ）演算を説明するための量子回路図であり、図２２（ｂ）は、Ｃ（ｐ）演算を説明するための量子回路図である。
【００３９】
第１比較演算過程〔ＣＯＭＰＡＲＩＳＯＮ（ｐ）〕は、量子状態が｜ａ０＞，…，｜ａｎ−１＞のｎ個の量子ビットＱＡ０，…，ＱＡｎ−１と、量子状態が｜ｓ０＞，…，｜ｓｎ−１＞のｎ個の量子ビットＱＢ０，…，ＱＢｎ−１と、量子状態が｜０（＋）ｓｎ＞の量子ビットＱＣ０と、量子状態が｜０＞の量子ビットＱＣ１とに対する量子操作である。
まず、演算制御部３０は、変数θに１を代入し、これをメモリ２０に格納する（ステップＳ４１）。次に、演算制御部３０はメモリ２０に格納された変数θを読み込み、この変数θに応じた命令を比較演算部４３に与える。これに対し、比較演算部４３は、ＱＢθに対するＮＯＴ演算操作を行う（ステップＳ４２）。次に、演算制御部３０は、メモリ２０に格納された変数θを読み込み、この変数θがｎ−１であるか否かを判断する（ステップＳ４３）。ここで、θ＝ｎ−１でなければ、演算制御部３０は、メモリ２０の変数θに１を加算した値を新たなθとしてメモリ２０に格納し、処理をステップＳ４２に戻す（ステップＳ４４）。一方、θ＝ｎ−１であれば、演算制御部３０は、比較演算部４３に指示を与え、これを受けた比較演算部４３は、ＱＣ０に対するＮＯＴ演算操作を行う（ステップＳ４５）。これにより、量子ビットＱＢ０，…，ＱＢｎ−１，ＱＣ０の量子状態は、それぞれ｜ｓ０’＞，…，｜ｓｎ−１’＞，｜ｓｎ’＞（｜ｓ０＞，…，｜ｓｎ−１＞，｜ｓｎ＞の反転ビット〔ｓｉ’＝ｓｉ（＋）１〕）となる。なお、ステップＳ４１〜Ｓ４５は、「第１ＮＯＴ演算過程」に相当する。
【００４０】
ステップＳ４５の後、比較演算部４３は、量子ビットＱＢ０，…，ＱＢｎ−１，ＱＣ０，ＱＡ０，…，ＱＡｎ−１，ＱＣ１に対する量子操作を行い、量子ビットＱＢ０，…，ＱＢｎ−１，ＱＣ０の量子状態をそれぞれ、｜ｓ０’＞，…，｜ｓｎ−１’＞，｜ｓｎ’＞とし、量子ビットＱＡ０，…，ＱＡｎ−１の量子状態をそれぞれ｜ａ０＞，…，｜ａｎ−１＞とし、量子ビットＱＣ１の量子状態を｜ｘ＞とするＨＩＧＨＢＩＴ（ｐ）演算操作（最上位ビット演算過程／ステップＳ４６）を実行する。なお、ｘはｓ’＋ｐ（ｓ’＝ｓｎ’ｓｎ−１’…ｓ０’）を２進ｎ＋２桁表記した際の最上位桁の値を示す。また、このＨＩＧＨＢＩＴ（ｐ）演算操作の詳細については後述する。
【００４１】
ステップＳ４６の後、演算制御部３０は、変数θに１を代入し、これをメモリ２０に格納する（ステップＳ４７）。次に、演算制御部３０はメモリ２０に格納された変数θを読み込み、この変数θに応じた命令を比較演算部４３に与える。これに対し、比較演算部４３は、ＱＢθに対するＮＯＴ演算操作を行う（ステップＳ４８）。次に、演算制御部３０は、メモリ２０に格納された変数θを読み込み、この変数θがｎ−１であるか否かを判断する（ステップＳ４９）。ここで、θ＝ｎ−１でなければ、演算制御部３０は、メモリ２０の変数θに１を加算した値を新たなθとしてメモリ２０に格納し、処理をステップＳ４８に戻す（ステップＳ５０）。一方、θ＝ｎ−１であれば、演算制御部３０は、比較演算部４３に指示を与え、これを受けた比較演算部４３は、ＱＣ０，ＱＣ１に対するＮＯＴ演算操作を行う（ステップＳ５１）。これにより、量子ビットＱＡ０，…，ＱＡｎ−１の量子状態は、それぞれ｜ａ０＞，…，｜ａｎ−１＞となり、量子ビットＱＢ０，…，ＱＢｎ−１，ＱＣ０，ＱＣ１の量子状態は、それぞれ｜ｓ０＞，…，｜ｓｎ−１＞，｜ｓｎ＞，｜ｙ＞となる。なお、ステップＳ４７〜Ｓ５１は、「第２ＮＯＴ演算過程」に相当する。
【００４２】
［ＨＩＧＨＢＩＴ（ｐ）演算操作の詳細］
次に、ステップＳ４６のＨＩＧＨＢＩＴ（ｐ）演算操作の詳細を説明する。
ＨＩＧＨＢＩＴ（ｐ）演算操作は、量子状態が｜ａ０＞，…，｜ａｎ−１＞のｎ個の量子ビットＱＡ０，…，ＱＡｎ−１と、量子状態が｜ｓ０’＞，…，｜ｓｎ−１’＞のｎ個の量子ビットＱＢ０，…，ＱＢｎ−１と、量子状態が｜ｓｎ’＞の量子ビットＱＣ０と、量子状態が｜０＞の量子ビットＱＣ１とに対する量子操作である。
まず、比較演算部４３が、量子ビットＱＡｎ−１，ＱＣ１に対するＣＮＯＴ演算操作（制御ビットＱＡｎ−１，目的ビットＱＣ１）を行う（第１制御ＮＯＴ演算過程／ステップＳ６１）。次に、比較演算部４３が、量子ビットＱＡｎ−１，ＱＡｎ−２，ＱＣ０に対するトフォリ演算操作（制御ビットＱＡｎ−２，ＱＣ０，目的ビットＱＡｎ−１）を行う（第１トフォリ演算過程／ステップＳ６２）。
【００４３】
次に、演算制御部３０は、変数θにｎ−１を代入し、これをメモリ２０に格納する（ステップＳ６３）。次に、演算制御部３０はメモリ２０に格納された変数θとｐθとを読み込み、これらの変数θとｐθとに応じた命令を比較演算部４３に与える。これを受けた比較演算部４３は、量子ビットＱＡθ−１，ＱＡθ−２，ＱＢθに対するＡ（ｐθ）演算操作を行う（第１量子操作過程／ステップＳ６４）。
図２２（ａ）に示すように、Ａ（ｐθ）演算は、３つの量子ビットＱＡθ−２，ＱＢθ，ＱＡθ−１に対する量子操作である（入力時の各量子状態がｖ１，ｖ２，ｖ３∈｛０，１｝を示すものとする）。Ａ（ｐθ）演算では、まず、ｐθ＝１の場合にのみ量子ビットＱＢθにＮＯＴ演算を適用する。次に、量子ビットＱＡθ−２，ＱＢθを制御ビットとし、量子ビットＱＡθ−１を目標ビットとしたトフォリ演算を適用し、さらに、ｐθ＝１の場合にのみ量子ビットＱＢθにＮＯＴ演算を適用する。これらの操作により、３つの量子ビットＱＡθ−２，ＱＢθ，ＱＡθ−１の量子状態は、それぞれｖ１，ｖ２，ｖ３（＋）（ｐθ（＋）ｖ２）・ｖ１を示すものとなる。以上がＡ（ｐθ）演算である。
【００４４】
次に、演算制御部３０が、メモリ２０に格納された変数θを読み込み、この変数θが２であるか否かを判断する（ステップＳ６５）。ここで、θ＝２でなければ、演算制御部３０は、メモリ２０の変数θから１を引いた値を新たなθとしてメモリ２０に格納し、処理をステップＳ６４に戻す（ステップＳ６６）。一方、θ＝２であれば、演算制御部３０は、メモリ２０からｐ１を読み込み、ｐ１＝１の場合にのみ、比較演算部４３に、量子ビットＱＢ１を制御ビットとし、量子ビットＱＡ０目標ビットとした制御ＮＯＴ演算操作を実行させ、さらにその後、量子ビットＱＢ１のＮＯＴ演算操作を実行させる（第２量子操作過程／ステップＳ６７）。また、演算制御部３０は、メモリ２０からｐ０を読み込み、ｐ０＝１の場合にのみ、比較演算部４３に、量子ビットＱＢ０，ＱＢ１を制御ビットとし、量子ビットＱＡ０を目標ビットとしたトフォリ演算操作を実行させる（第３量子演算過程／ステップＳ６８）。
【００４５】
次に、演算制御部３０はメモリ２０に格納された変数θとｐθとを読み込み、これらの変数θとｐθとに応じた命令を比較演算部４３に与える。これを受けた比較演算部４３は、量子ビットＱＡθ−１，ＱＡθ−２，ＱＢθに対するＣ（ｐθ）演算操作を行う（第４量子操作過程／ステップＳ６９）。
図２２（ｂ）に示すように、Ｃ（ｐθ）演算は、３つの量子ビットＱＡθ−２，ＱＢθ，ＱＡθ−１に対する量子操作である（入力時の各量子状態がｖ１，ｖ２，ｖ３∈｛０，１｝を示すものとする）。Ｃ（ｐθ）演算では、まず、ｐθ＝１の場合にのみ、量子ビットＱＢθを制御ビットとし、量子ビットＱＡθ−１を目標ビットとしたＣＮＯＴ演算を適用し、さらに、量子ビットＱＢθにＮＯＴ演算を適用する。その後、量子ビットＱＡθ−２，ＱＢθを制御ビットとし、量子ビットＱＡθ−１を目標ビットとしたトフォリ演算を適用する。これらの操作により、３つの量子ビットＱＡθ−２，ＱＢθ，ＱＡθ−１の量子状態は、それぞれｖ１，ｐθ（＋）ｖ２，ｖ３（＋）ｖ１ｐθ（＋）ｖ２ｖ１を示すものとなる。以上がＣ（ｐθ）演算である。
【００４６】
次に、演算制御部３０が、メモリ２０に格納された変数θを読み込み、この変数θがｎ−１であるか否かを判断する（ステップＳ７０）。ここで、θ＝ｎ−１でなければ、演算制御部３０は、メモリ２０の変数θに１を加算した値を新たなθとしてメモリ２０に格納し、処理をステップＳ６９に戻す（ステップＳ７１）。一方、θ＝ｎ−１であれば、演算制御部３０は、比較演算部４３に、量子ビットＱＡｎ−１，ＱＡｎ−２，ＱＣ０に対するトフォリ演算操作（制御ビットＱＡｎ−２，ＱＣ０，目的ビットＱＡｎ−１）を実行させる（第２トフォリ演算過程／ステップＳ７２）。
【００４７】
次に、比較演算部４３が、量子ビットＱＡｎ−１，ＱＣ１に対するＣＮＯＴ演算操作（制御ビットＱＡｎ−１，目的ビットＱＣ１）を行う（第２制御ＮＯＴ演算過程／ステップＳ８１）。次に、比較演算部４３が、量子ビットＱＡｎ−１，ＱＡｎ−２，ＱＣ０に対するトフォリ演算操作（制御ビットＱＡｎ−２，ＱＣ０，目的ビットＱＡｎ−１）を行う（第３トフォリ演算過程／ステップＳ８２）。
次に、演算制御部３０は、変数θにｎ−１を代入し、これをメモリ２０に格納する（ステップＳ８３）。次に、演算制御部３０はメモリ２０に格納された変数θとｐθとを読み込み、これらの変数θとｐθとに応じた命令を比較演算部４３に与える。これを受けた比較演算部４３は、量子ビットＱＡθ−１，ＱＡθ−２，ＱＢθに対するＣ（ｐθ）−１演算操作を行う（第５量子操作過程／ステップＳ８４）。なお、Ｃ（ｐθ）−１演算は、Ｃ（ｐθ）演算の逆演算である。
【００４８】
次に、演算制御部３０が、メモリ２０に格納された変数θを読み込み、この変数θが２であるか否かを判断する（ステップＳ８５）。ここで、θ＝２でなければ、演算制御部３０は、メモリ２０の変数θから１を引いた値を新たなθとしてメモリ２０に格納し、処理をステップＳ８４に戻す（ステップＳ８６）。一方、θ＝２であれば、演算制御部３０は、メモリ２０からｐ０を読み込み、ｐ０＝１の場合にのみ、比較演算部４３に、量子ビットＱＢ０，ＱＢ１を制御ビットとし、量子ビットＱＡ０を目標ビットとしたトフォリ演算操作を実行させる（第６量子演算過程／ステップＳ８７）。さらに、演算制御部３０は、メモリ２０からｐ１を読み込み、ｐ１＝１の場合にのみ、比較演算部４３に、量子ビットＱＢ１のＮＯＴ演算操作を実行させ、さらにその後、量子ビットＱＢ１を制御ビットとし、量子ビットＱＡ０目標ビットとした制御ＮＯＴ演算操作を実行させる（第７量子操作過程／ステップＳ８８）。
【００４９】
次に、演算制御部３０はメモリ２０に格納された変数θとｐθとを読み込み、これらの変数θとｐθとに応じた命令を比較演算部４３に与える。これを受けた比較演算部４３は、量子ビットＱＡθ−１，ＱＡθ−２，ＱＢθに対するＡ（ｐθ）演算操作を行う（第８量子操作過程／ステップＳ８９）。
次に、演算制御部３０が、メモリ２０に格納された変数θを読み込み、この変数θがｎ−１であるか否かを判断する（ステップＳ９０）。ここで、θ＝ｎ−１でなければ、演算制御部３０は、メモリ２０の変数θに１を加算した値を新たなθとしてメモリ２０に格納し、処理をステップＳ８９に戻す（ステップＳ９１）。一方、θ＝ｎ−１であれば、演算制御部３０は、比較演算部４３に、量子ビットＱＡｎ−１，ＱＡｎ−２，ＱＣ０に対するトフォリ演算操作（制御ビットＱＡｎ−２，ＱＣ０，目的ビットＱＡｎ−１）を実行させる（第４トフォリ演算過程／ステップＳ９２／第１比較演算過程〔ＣＯＭＰＡＲＩＳＯＮ（ｐ）〕／ステップＳ３の詳細の説明終わり）。
【００５０】
［制御減算演算過程〔ＱＦＴ，ΦＡＤＤ（ｐ）−１，ＱＦＴ−１〕／ステップＳ４の詳細］
次に、制御減算演算過程〔ＱＦＴ，ΦＡＤＤ（ｐ）−１，ＱＦＴ−１〕／ステップＳ４の詳細について説明する。
図９は、制御減算演算過程〔ＱＦＴ，ΦＡＤＤ（ｐ）−１，ＱＦＴ−１〕を説明するためのフローチャートである。
まず、制御減算演算部４４は、量子状態が、それぞれ｜ｓ０＞，…，｜ｓｎ−１＞，｜ｓｎ＞である量子ビットＱＢ０，・・・，ＱＢｎ−１，ＱＣ０に対し、ＱＦＴ演算操作を実行する（ステップＳ１０１）。ＱＦＴ演算操作の内容は、図４２に示した通りである（なお、図４２は、ｎ＝５の例であり、ｄ０，…，ｄ５がｓ０，…，ｓ５に対応する。）。この量子操作により、量子ビットＱＢ０，・・・，ＱＢｎ−１，ＱＣ０の量子状態は、それぞれ、｜Φ０（ｓ）＞，…，｜Φｎ−１（ｓ）＞，｜Φｎ（ｓ）＞となる。ただし、ｓ＝ｓｎｓｎ−１…ｓ０であり、
【００５１】
【数１】
0004829623.tif 000002
である。
次に、制御減算演算部４４は、量子ビットＱＣ１を制御ビットとした量子ビットＱＢ０，・・・，ＱＢｎ−１，ＱＣ０，ＱＣ１に対する制御ΦＡＤＤ（ｐ）−１演算操作を実行する（ステップＳ１０２）。すなわち、量子ビットＱＣ１の量子状態が｜１＞の場合（ｓ≧ｐの場合）にのみ、量子ビットＱＢ０，・・・，ＱＢｎ−１，ＱＣ０に対するΦＡＤＤ（ｐ）−１演算操作が行われる。なお、ΦＡＤＤ（ｐ）−１演算はΦＡＤＤ（ｐ）演算の逆演算であり、ΦＡＤＤ（ｐ）演算の内容は、図４５及び図４６に示した通りである（図４５及び図４６は、ｎ＝５の例であり、ｄ，ｆがそれぞれｓ，ｐに対応する。）。この量子操作により、量子ビットＱＣ１の量子状態が｜１＞の場合、量子ビットＱＢ０，・・・，ＱＢｎ−１，ＱＣ０の量子状態は、それぞれ｜Φ０（ｓ−ｐ）＞，…，｜Φｎ−１（ｓ−ｐ）＞，｜Φｎ（ｓ−ｐ）＞となり、量子ビットＱＣ１の量子状態が｜０＞の場合、量子ビットＱＢ０，・・・，ＱＢｎ−１，ＱＣ０の量子状態は、それぞれ｜Φ０（ｓ）＞，…，｜Φｎ−１（ｓ）＞，｜Φｎ（ｓ）＞となる。
【００５２】
次に、制御減算演算部４４は、量子ビットＱＢ０，・・・，ＱＢｎ−１，ＱＣ０に対し、ＱＦＴ−１演算操作を実行する（ステップＳ１０３）。なお、ＱＦＴ−１演算は、ＱＦＴ演算の逆演算である。この量子操作により、量子ビットＱＢ０，・・・，ＱＢｎ−１，ＱＣ０の量子状態は、それぞれ、｜ｓ０＞，…，｜ｓｎ−１＞，｜ｓｎ＞〔量子ビットＱＣ１の量子状態が｜０＞の場合（ｓ＜ｐの場合）〕、又は、｜（ｓ−ｐ）０＞，…，｜（ｓ−ｐ）ｎ−１＞，｜（ｓ−ｐ）ｎ＞〔量子ビットＱＣ１の量子状態が｜１＞の場合（ｓ≧ｐの場合）〕となる。すなわち、量子ビットＱＢ０，・・・，ＱＢｎ−１，ＱＣ０の各量子状態は、（ａ＋ｂ）ｍｏｄ  ｐを２進表記した際の各桁を示すことになる（制御減算演算過程〔ＱＦＴ，ΦＡＤＤ（ｐ）−１，ＱＦＴ−１〕／ステップＳ４の詳細の説明終わり）。
【００５３】
［交換演算過程〔ＳＷＡＰ〕／ステップＳ５）の詳細］
次に、交換演算過程〔ＳＷＡＰ〕／ステップＳ５）の詳細を説明する。
図９（ｂ）は、交換演算過程〔ＳＷＡＰ〕の詳細を説明するためのフローチャートである。また、図１８（ｂ）は、交換演算過程〔ＳＷＡＰ〕を説明するための量子回路図である。
まず、交換演算部４５が、量子ビットＱＣ１を制御ビットとし、量子ビットＱＣ０を目標ビットとするＣＮＯＴ演算操作を実行する（ステップＳ１１１）。次に、交換演算部４５が、量子ビットＱＣ０を制御ビットとし、量子ビットＱＣ１を目標ビットとするＣＮＯＴ演算操作を実行する（ステップＳ１１２）。さらに、交換演算部４５が、量子ビットＱＣ１を制御ビットとし、量子ビットＱＣ０を目標ビットとするＣＮＯＴ演算操作を実行する（ステップＳ１１３）。
【００５４】
ここで、量子ビットＱＣ１の量子状態が｜０＞であった場合（ｓ＜ｐの場合）、この量子操作により、量子ビットＱＣ０，ＱＣ１の量子状態は、それぞれ｜０＞，｜ｓｎ＞となる。そして、ｓ＜ｐなのだからｓｎ＝ｐｎ＝０である。一方、量子ビットＱＣ１の量子状態が｜１＞であった場合（ｓ≧ｐの場合）、この量子操作により、量子ビットＱＣ０，ＱＣ１の量子状態は、それぞれ｜１＞，｜（ｓ−ｐ）ｎ＞となる。そして、ａ＋ｂ＝ｓ＜２ｐなのだから、ｓ−ｐ＜ｐであり、（ｓ−ｐ）ｎ＝ｐｎ＝０である（交換演算過程〔ＳＷＡＰ〕／ステップＳ５）の詳細の説明終わり）。
【００５５】
［第２比較演算過程〔ＣＯＭＰ〕／ステップＳ６の詳細］
次に、第２比較演算過程〔ＣＯＭＰ〕／ステップＳ６の詳細について説明する。
図１０及び図１１は、第２比較演算過程〔ＣＯＭＰ〕／ステップＳ６の詳細を説明するためのフローチャートである。また、図２３は、第２比較演算過程〔ＣＯＭＰ〕の量子操作全体を説明するための量子回路図（ｎ＝５の例）である。また、図２４〜図２７は、図２３のＴ１〜Ｔ４の各量子操作を説明するための量子回路図である。
第２比較演算過程は、量子状態が｜ａ０＞，…，｜ａｎ−１＞のｎ個の量子ビットＱＡ０，…，ＱＡｎ−１と、量子状態が｜ｕ０＞，…，｜ｕｎ−１＞のｎ個の量子ビットＱＢ０，…，ＱＢｎ−１と、量子状態が｜γ＞（γ∈｛０，１｝）の量子ビットＱＣ０とに対する量子操作であり、以下のＴ１〜Ｔ４の量子操作が実行される。
【００５６】
［Ｔ１の量子操作］
まず、比較演算部４６は、量子ビットＱＢ０，・・・，ＱＢｎ−１に対するＮＯＴ演算操作を行う（ステップＳ１２１）。次に、演算制御部３０は、変数θに１を代入し、これをメモリ２０に格納する（ステップＳ１２２）。次に、演算制御部３０はメモリ２０に格納された変数θを読み込み、この変数θに応じた命令を比較演算部４６に与える。これに対し、比較演算部４６は、ＱＡθ，ＱＣ０に対するＣＮＯＴ演算操作と、ＱＢθ，ＱＣ０に対するＣＮＯＴ演算操作とを実行（制御ビットＱＣ０，目標ビットＱＡθ，ＱＢθ）する（ステップＳ１２３）。
【００５７】
次に、演算制御部３０は、メモリ２０に格納された変数θを読み込み、この変数θがｎ−１であるか否かを判断する（ステップＳ１２４）。ここで、θ＝ｎ−１でなければ、演算制御部３０は、メモリ２０の変数θに１を加えた値を新たなθとしてメモリ２０に格納し、処理をステップＳ１２３に戻す（ステップＳ１２５）。一方、θ＝ｎ−１であれば、以下のＴ２の量子操作に移る。
［Ｔ２の量子操作］
まず、比較演算部４６が、量子ビットＱＡ０，ＱＢ０，ＱＣ０に対するトフォリ演算操作（制御ビットＱＡ０，ＱＢ０，目標ビットＱＣ０）を行う（ステップＳ１２６）。
【００５８】
次に、演算制御部３０が、変数θに１を代入し、これをメモリ２０に格納する（ステップＳ１２７）。そして、演算制御部３０はメモリ２０に格納された変数θを読み込み、この変数θに応じた命令を比較演算部４６に与える。比較演算部４６は、量子ビットＱＢθ，ＱＡθ，ＱＣ０に対するＭＡＪ演算操作を行う（ステップＳ１２８）。なお、ステップＳ１２８のＭＡＪ演算操作は、量子ビットＱＢθ，ＱＡθ，ＱＣ０を、それぞれ、図１８（ａ）の入力（１），（２），（３）として行う。次に、比較演算部４６は、量子ビットＱＢ０，ＱＢθ，ＱＡθに対するトフォリ演算操作（制御ビットＱＢθ，ＱＡθ、目標ビットＱＢ０）を行う（ステップＳ１２９）。
【００５９】
次に、演算制御部３０は、メモリ２０に格納された変数θを読み込み、この変数θがｎ−２であるか否かを判断する（ステップＳ１３０）。ここで、θ＝ｎ−２でなければ、演算制御部３０は、メモリ２０の変数θに１を加えた値を新たなθとしてメモリ２０に格納し、処理をステップＳ１２８に戻す（ステップＳ１３１）。一方、θ＝ｎ−２であれば、比較演算部４６に命令を与え、比較演算部４６は、量子ビットＱＢｎ−１，ＱＡｎ−１，ＱＣ０に対するＭＡＪ演算操作を行う（ステップＳ１３２）。なお、このＭＡＪ演算操作は、量子ビットＱＢｎ−１，ＱＡｎ−１，ＱＣ０を、それぞれ、図１８（ａ）の入力（１），（２），（３）として行う。
【００６０】
［Ｔ３の量子操作］
次に、演算制御部３０は、変数θにｎ−１を代入し、これをメモリ２０に格納する（ステップＳ１４１）。次に、演算制御部３０はメモリ２０に格納された変数θを読み込み、この変数θに応じた命令を比較演算部４６に与える。これを受けた比較演算部４６は、量子ビットＱＡθ，ＱＢ０に対するＣＮＯＴ演算操作（制御ビットＱＢ０、目標ビットＱＡθ）と、量子ビットＱＢθ，ＱＢ０に対するＣＮＯＴ演算操作（制御ビットＱＢ０、目標ビットＱＢθ）とを行う（ステップＳ１４２）。さらに、比較演算部４６は、量子ビットＱＢ０，ＱＡθ−１，ＱＢθ−１に対するトフォリ演算操作（制御ビットＱＡθ−１，ＱＢθ−１、目標ビットＱＢ０）を行う（ステップＳ１４３）。
【００６１】
次に、演算制御部３０は、メモリ２０に格納された変数θを読み込み、この変数θが２であるか否かを判断する（ステップＳ１４４）。ここで、θ＝２でなければ、演算制御部３０は、メモリ２０の変数θから１を引いた値を新たなθとしてメモリ２０に格納し、処理をステップＳ１４２に戻す（ステップＳ１４５）。一方、θ＝２であれば、以下のＴ４の量子操作に移る。
［Ｔ４の量子操作］
まず、比較演算部４６が、ＱＡ０に対するＮＯＴ演算操作を行う（ステップＳ１４６）。次に、演算制御部３０は、変数θにｎ−１を代入し、これをメモリ２０に格納する（ステップＳ１４７）。次に、演算制御部３０は、メモリ２０に格納された変数θを読み込み、この変数θに応じた命令を比較演算部４６に与える。これを受けた比較演算部４６は、量子ビットＱＢ０，ＱＡ０，ＱＡθに対するトフォリ演算操作（制御ビットＱＢ０，ＱＡ０、目標ビットＱＡθ）と、量子ビットＱＢ０，ＱＡ０，ＱＢθに対するトフォリ演算操作（制御ビットＱＢ０，ＱＡ０、目標ビットＱＢθ）とを行う（ステップＳ１４８）。
【００６２】
次に、演算制御部３０は、メモリ２０に格納された変数θを読み込み、この変数θが２であるか否かを判断する（ステップＳ１４９）。ここで、θ＝２でなければ、演算制御部３０は、メモリ２０の変数θから１を引いた値を新たなθとしてメモリ２０に格納し、処理をステップＳ１４８に戻す（ステップＳ１５０）。一方、θ＝２であれば、比較演算部４６において、量子ビットＱＡ０に対するＮＯＴ演算操作を行い（ステップＳ１５１）、さらに、量子ビットＱＢ０，ＱＡ０，ＱＡ１に対するトフォリ演算操作（制御ビットＱＢ０，ＱＡ０、目標ビットＱＡ１）と、量子ビットＱＢ０，ＱＡ０，ＱＢ１に対するトフォリ演算操作（制御ビットＱＢ０，ＱＡ０、目標ビットＱＢ１）とを行う（ステップＳ１５２）。次に、演算制御部３０は、量子ビットＱＢ０，…，ＱＢｎ−１，ＱＣ０に対するＮＯＴ演算操作を行う（ステップＳ１５３）。
【００６３】
以上の処理により、量子ビットＱＡ０，…，ＱＡｎ−１の量子状態がそれぞれ｜ａ０＞，…，｜ａｎ−１＞となり、量子ビットＱＢ０，…，ＱＢｎ−１の量子状態がそれぞれ｜ｕ０＞，…，｜ｕｎ−１＞となり、量子ビットＱＣ０の量子状態が｜γ（＋）δ＞となる。なお、γ＝０なのは、ａ＋ｂ＝ｓ＝ｕ＜ｐの場合である。この場合は、ａ≦ｕとなり、δ＝１となる。よって、γ（＋）δ＝１となる。一方、γ＝１なのは、ａ＋ｂ＝ｓ≧ｐであり、ｕ＝ｓ−ｐ＝ａ＋ｂ−ｐの場合である。そして、ｂ＜ｐなのだから、ｂ−ｐ＜０である。よって、ｕ＞ａとなり、δ＝１となる。すなわち、量子ビットＱＣ０の量子状態は必ず｜１＞となる（第２比較演算過程〔ＣＯＭＰ〕／ステップＳ６の詳細の説明終わり）。そして、最後にＮＯＴ演算部４７が、量子ビットＱＣ０にＮＯＴ演算を施す（ＮＯＴ演算過程／ステップＳ７）のだから、最終的には、量子ビットＱＣ０の量子状態は必ず｜０＞になる。
【００６４】
＜本形態の特徴＞
以上のように、本形態では、２個の補助ビットを用い、量子フーリエ変換とその逆変換それぞれ１個とＯ（ｎ）個（具体的には、ｎ≧５で9n2+221n-187個）の基本演算とを、Ｏ（ｎ）個の計算ステップで実行し、有限体ＧＦ（ｐ）上の加算を行うことができる。このように、本形態では、従来構成に比べ、補助ビット数の削減と基本演算数の低減とを同時に行うことができ、演算誤り率を低減させることができる。
〔第２の実施の形態〕
次に、本発明における第２の実施の形態について説明する。
【００６５】
本形態は、第１の実施の形態の変形例であり、比較演算過程の処理と制御減算演算過程との処理のみが相違する。すなわち、第１の実施の形態では、メモリ２０にｐを古典情報として保持し、この古典情報を用いたＨＩＧＨＢＩＴ（ｐ）演算操作やΦＡＤＤ（ｐ）−１演算操作を行っていた。本形態では、ｐを古典情報ではなく、量子情報として量子ビットに保持し、この量子情報を用いて行われるＨＩＧＨＢＩＴ演算操作やΦＡＤＤ−１演算操作を用い、比較演算過程の処理と制御減算演算過程との処理を実行する。なお、以下では、第１の実施の形態との相違点を中心に説明し、第１の実施の形態と共通する事項については説明を省略する。
【００６６】
＜構成＞
図２８は、第２の実施の形態における量子演算装置１００の構成を示したブロック図である。
図２８に示すように、本形態の量子演算装置１００は、量子ビット１１０と、メモリ２０と、演算制御部１３０と、量子演算部１４０とを有している。ここで、量子ビット１１０は、ｎ個の量子ビットＱＡ０，…，ＱＡｎ−１と、ｎ個の量子ビットＱＢ０，…，ＱＢｎ−１と、２個の量子ビットＱＣ０，ＱＣ１と、ｎ個の量子ビットＱＰ０，…，ＱＰｎ−１とによって構成される。また、量子演算部１４０は、初期量子状態生成過程を実行する初期量子状態生成部１４１と、加算演算過程を実行する加算演算部４２と、第１比較演算過程を実行する比較演算部１４３と、制御減算演算過程を実行する制御減算演算部１４４と、交換演算過程を実行する交換演算部４５と、第２比較演算過程を実行する比較演算部４６と、ＮＯＴ演算過程を実行するＮＯＴ演算部４７とを有している。なお、これらの加算演算部４２と、比較演算部１４３と、制御減算演算部１４４と、交換演算部４５と、比較演算部４６と、ＮＯＴ演算部４７との各機能は、基本演算単体或いは基本演算の組合せによって実現される。
【００６７】
＜処理＞
以下では、初期量子状態生成過程と、ＨＩＧＨＢＩＴ（ｐ）演算操作やΦＡＤＤ（ｐ）−１演算操作の代わりに行われるＨＩＧＨＢＩＴ演算操作やΦＡＤＤ−１演算操作とを説明する。その他処理については、第１の実施の形態と同じであるため説明を省略する。
［初期量子状態生成過程］
本形態の初期量子状態生成過程では、初期量子状態生成部１４１が、ｎ個の量子ビットＱＡ０，…，ＱＡｎ−１の量子状態をそれぞれ｜ａ０＞，…，｜ａｎ−１＞とし、ｎ個の量子ビットＱＢ０，…，ＱＢｎ−１の量子状態をそれぞれ｜ｂ０＞，…，｜ｂｎ−１＞とし、２個の量子ビットＱＣ０，ＱＣ１の量子状態をそれぞれ｜０＞，｜０＞し、ｎ個の量子ビットＱＰ０，…，ＱＰｎ−１の量子状態をそれぞれ｜ｐ０＞，…，｜ｐｎ−１＞とする。
【００６８】
［ＨＩＧＨＢＩＴ演算操作］
次に、本形態のＨＩＧＨＢＩＴ演算操作について説明する。
図２９及び図３０は、第２の実施の形態のＨＩＧＨＢＩＴ演算操作を説明するためのフローチャートである。また、図３１及び図３２は、第２の実施の形態のＨＩＧＨＢＩＴ演算操作を説明するための量子回路図である。さらに、図３３（ａ）は、図３１及び図３２のＡ演算操作を説明するための量子回路図であり、図３３（ｂ）は、Ｃ演算操作を説明するための量子回路図である。また、図３４は、図３１及び図３２の３トフォリ演算操作を説明するための量子回路である。
【００６９】
ＨＩＧＨＢＩＴ演算操作は、量子状態が｜ａ０＞，…，｜ａｎ−１＞のｎ個の量子ビットＱＡ０，…，ＱＡｎ−１と、量子状態が｜ｓ０’＞，…，｜ｓｎ−１’＞のｎ個の量子ビットＱＢ０，…，ＱＢｎ−１と、量子状態が｜ｓｎ’＞の量子ビットＱＣ０と、量子状態が｜０＞の量子ビットＱＣ１と、量子状態が｜ｐ０＞，…，｜ｐｎ−１＞の量子ビットＱＰ０，…，ＱＰｎ−１とに対する量子操作である。
まず、比較演算部１４３が、量子ビットＱＡｎ−１，ＱＣ１に対するＣＮＯＴ演算操作（制御ビットＱＡｎ−１，目的ビットＱＣ１）を行う（第１制御ＮＯＴ演算過程／ステップＳ２０１）。次に、比較演算部１４３が、量子ビットＱＡｎ−１，ＱＡｎ−２，ＱＣ０に対するトフォリ演算操作（制御ビットＱＡｎ−２，ＱＣ０，目的ビットＱＡｎ−１）を行う（第１トフォリ演算過程／ステップＳ２０２）。
【００７０】
次に、演算制御部１３０は、変数θにｎ−１を代入し、これをメモリ２０に格納する（ステップＳ２０３）。次に、演算制御部３０はメモリ２０に格納された変数θとｐθとを読み込み、これらの変数θとｐθとに応じた命令を比較演算部１４３に与える。これを受けた比較演算部１４３は、量子ビットＱＡθ−１，ＱＡθ−２，ＱＢθ，ＱＰθに対するＡ演算操作を行う（第１量子操作過程／ステップＳ２０４）。
図３３（ａ）に示すように、Ａ演算は、４つの量子ビットＱＡθ−２，ＱＰθ，ＱＢθ，ＱＡθ−１に対する量子操作である（入力時の各量子状態がｖ１, ｐθ，ｖ２，ｖ３∈｛０，１｝を示すものとする）。Ａ演算では、まず、量子ビットＱＰθを制御ビットとし、量子ビットＱＢθを目標ビットとしたＣＮＯＴ演算を適用する。次に、量子ビットＱＡθ−２，ＱＢθを制御ビットとし、量子ビットＱＡθ−１を目標ビットとしたトフォリ演算を適用し、さらに、量子ビットＱＰθを制御ビットとし、量子ビットＱＢθを目標ビットとしたＣＮＯＴ演算を適用する。これらの操作により、４つの量子ビットＱＡθ−２，ＱＰθ，ＱＢθ，ＱＡθ−１の量子状態は、それぞれｖ１，ｐθ，ｖ２，ｖ３（＋）（ｐθ（＋）ｖ２）・ｖ１を示すものとなる。以上がＡ演算である。
【００７１】
次に、演算制御部１３０が、メモリ２０に格納された変数θを読み込み、この変数θが２であるか否かを判断する（ステップＳ２０５）。ここで、θ＝２でなければ、演算制御部１３０は、メモリ２０の変数θから１を引いた値を新たなθとしてメモリ２０に格納し、処理をステップＳ２０４に戻す（ステップＳ２０６）。一方、θ＝２であれば、演算制御部１３０は、比較演算部１４３に、量子ビットＱＰ１，ＱＢ１，ＱＡ０に対するトフォリ演算操作（制御ビットＱＰ１，ＱＢ１，目標ビットＱＡ０）と、量子ビットＱＰ１，ＱＢ１のＣＮＯＴ演算操作（制御ビットＱＰ１，目標ビットＱＢ１）とを実行させる（第２量子操作過程／ステップＳ２０７）。さらに、演算制御部１３０は、比較演算部１４３に、量子ビットＱＰ０，ＱＢ０，ＱＢ１，ＱＡ０に対する３トフォリ演算操作（制御ビットＱＰ０，ＱＢ０，ＱＢ１，目標ビットＱＡ０）を実行させる（第３量子演算過程／ステップＳ２０８）。なお、３トフォリ演算操作の内容は図３４に示す通りである。
次に、比較演算部１４３は、量子ビットＱＡθ−１，ＱＡθ−２，ＱＢθ，ＱＰθに対するＣ演算操作
を行う（第４量子操作過程／ステップＳ２０９）。
【００７２】
図３３（ｂ）に示すように、Ｃ演算は、４つの量子ビットＱＡθ−１，ＱＰθ，ＱＢθ，ＱＡθ−２に対する量子操作である（入力時の各量子状態がｖ１，ｐθ，ｖ２，ｖ３∈｛０，１｝を示すものとする）。Ｃ演算では、まず、量子ビットＱＰθ，ＱＢθを制御ビットとし、量子ビットＱＡθ−１を目標ビットとしたトフォリ演算を適用し、さらに、量子ビットＱＰθを制御ビットとし、量子ビットＱＢθを目標ビットとしたＣＮＯＴ演算を適用する。その後、量子ビットＱＡθ−２，ＱＢθを制御ビットとし、量子ビットＱＡθ−１を目標ビットとしたトフォリ演算を適用する。これらの操作により、４つの量子ビットＱＡθ−１，ＱＰθ，ＱＢθ，ＱＡθ−２の量子状態は、それぞれｖ１，ｐθ，ｐθ（＋）ｖ２，ｖ３（＋）ｖ１ｐθ（＋）ｖ２ｖ１を示すものとなる。以上がＣ演算である。
【００７３】
次に、演算制御部１３０が、メモリ２０に格納された変数θを読み込み、この変数θがｎ−１であるか否かを判断する（ステップＳ２１０）。ここで、θ＝ｎ−１でなければ、演算制御部１３０は、メモリ２０の変数θに１を加算した値を新たなθとしてメモリ２０に格納し、処理をステップＳ２０９に戻す（ステップＳ２１１）。一方、θ＝ｎ−１であれば、演算制御部１３０は、比較演算部１４３に、量子ビットＱＡｎ−１，ＱＡｎ−２，ＱＣ０に対するトフォリ演算操作（制御ビットＱＡｎ−２，ＱＣ０，目的ビットＱＡｎ−１）を実行させる（第２トフォリ演算過程／ステップＳ２１２）。
【００７４】
次に、比較演算部１４３が、量子ビットＱＡｎ−１，ＱＣ１に対するＣＮＯＴ演算操作（制御ビットＱＡｎ−１，目的ビットＱＣ１）を行う（第２制御ＮＯＴ演算過程／ステップＳ２２１）。次に、比較演算部１４３が、量子ビットＱＡｎ−１，ＱＡｎ−２，ＱＣ０に対するトフォリ演算操作（制御ビットＱＡｎ−２，ＱＣ０，目的ビットＱＡｎ−１）を行う（第３トフォリ演算過程／ステップＳ２２２）。
次に、演算制御部１３０は、変数θにｎ−１を代入し、これをメモリ２０に格納する（ステップＳ２２３）。次に、演算制御部１３０はメモリ２０に格納された変数θとｐθとを読み込み、これらの変数θとｐθとに応じた命令を比較演算部１４３に与える。これを受けた比較演算部１４３は、量子ビットＱＡθ−１，ＱＡθ−２，ＱＢθ，ＱＰθに対するＣ−１演算操作を行う（第５量子操作過程／ステップＳ２２４）。なお、Ｃ−１演算は、Ｃ演算の逆演算である。
【００７５】
次に、演算制御部１３０が、メモリ２０に格納された変数θを読み込み、この変数θが２であるか否かを判断する（ステップＳ２２５）。ここで、θ＝２でなければ、演算制御部１３０は、メモリ２０の変数θから１を引いた値を新たなθとしてメモリ２０に格納し、処理をステップＳ２２４に戻す（ステップＳ２２６）。一方、θ＝２であれば、演算制御部１３０は、比較演算部１４３に、量子ビットＱＰ０，ＱＢ０，ＱＢ１を制御ビットとし、量子ビットＱＡ０を目標ビットとしたトフォリ演算操作を実行させる（第６量子演算過程／ステップＳ２２７）。さらに、演算制御部１３０は、比較演算部１４３に、量子ビットＱＰ１を目標ビットとし、量子ビットＱＢ１を目標ビットとしたＣＮＯＴ演算操作を実行させ、さらにその後、量子ビットＱＰ１，ＱＢ１を制御ビットとし、量子ビットＱＡ０目標ビットとしたトフォリ演算操作を実行させる（第７量子操作過程／ステップＳ２２８）。
【００７６】
次に、演算制御部１３０は、比較演算部１４３に、量子ビットＱＡθ−１，ＱＡθ−２，ＱＢθ，ＱＰθ−１に対するＡ演算操作を行う（第８量子操作過程／ステップＳ２２９）。
次に、演算制御部２３０が、メモリ２０に格納された変数θを読み込み、この変数θがｎ−１であるか否かを判断する（ステップＳ２３０）。ここで、θ＝ｎ−１でなければ、演算制御部１３０は、メモリ２０の変数θに１を加算した値を新たなθとしてメモリ２０に格納し、処理をステップＳ２２９に戻す（ステップＳ２３１）。一方、θ＝ｎ−１であれば、演算制御部１３０は、比較演算部１４３に、量子ビットＱＡｎ−１，ＱＡｎ−２，ＱＣ０に対するトフォリ演算操作（制御ビットＱＡｎ−２，ＱＣ０，目的ビットＱＡｎ−１）を実行させる（第４トフォリ演算過程／ステップＳ２３２／ＨＩＧＨＢＩＴ演算操作の説明終わり）。
【００７７】
［ΦＡＤＤ−１演算操作］
次に、本形態のΦＡＤＤ−１演算操作について説明する。
本形態のΦＡＤＤ−１演算操作は、量子ビットＱＣ１を制御ビットとした制御演算操作である。また、量子ビットＱＣ１を制御ビットとして制御されるΦＡＤＤ−１演算操作は、量子状態がそれぞれ｜ａ０＞，…，｜ａｎ−１＞，｜ｓ０＞，…，｜ｓｎ−１＞，｜ｓｎ＞である量子ビットＱＡ０，…，ＱＡｎ−１，ＱＢ０，…，ＱＢｎ−１，ＱＣ０に対する量子操作であり、ΦＡＤＤ演算操作の逆演算である。また、ΦＡＤＤ演算操作の内容は、図４４に示した通りである（なお、図４４は、ｎ＝５の例であり、ｄ０，…，ｄ５がａ０，…，ａ４に対応し、ｆ０，…，ｆ４，ｇがｓ０，…，ｓ４，ｓ５に対応する）。
【００７８】
＜本形態の特徴＞
以上のような構成としても、量子ビットＱＡ０，…，ＱＡｎ−１，ＱＢ０，…，ＱＢｎ−１，ＱＣ０，ＱＣ１に対して第１の実施の形態と同じ量子操作を施すことができる。そのため、本形態でも、２個の補助ビットを用い、量子フーリエ変換とその逆変換それぞれ１個とＯ（ｎ）個（具体的には、ｎ≧５で9n2+221n-187個）の基本演算とを、Ｏ（ｎ）個の計算ステップで実行し、有限体ＧＦ（ｐ）上の加算を行うことができる。その結果、本形態でも、従来構成に比べ、補助ビット数の削減と基本演算数の低減とを同時に行うことができ、演算誤り率を低減させることができる。
【００７９】
〔ハードウェア構成〕
次に各実施の形態の量子演算装置１，１００のハードウェア構成を例示する。
本形態の量子演算装置１，１００は、量子コンピュータと古典コンユータとの組合せ、或いは量子コンピュータ単体で実現できる。量子コンピュータの実現する物理系としては、例えば、イオントラップを用いる方法（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 University Press, 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)、
1138326796062_1
、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. 方式によってＣＮＯＴ演算を実現する。また、核スピンを量子ビットとして用いる場合には、例えば、所定の電磁波パルスを量子ビットに印加することによってＣＮＯＴ演算を実現できる。
【００８４】
その他、上記の文献に記載された方法でＣＮＯＴ演算を実現してもよい。
＜量子ビット単体の操作（ＮＯＴ演算，アダマール変換，ｋ回転演算）＞
イオントラップ量子コンピュータでは、例えば、イオンを直線上に並べ、各イオンに狙いを定めたレーザービーム照射によって量子ビット単体の操作を実現する。核スピンを量子ビットとして用いる場合には、電磁波パルスやレーザービーム照射によって各処理を実現する。また、量子ビットとして光子の偏光を用いる場合には、例えば、偏光回転素子等によって実現する。
【００８５】
＜演算制御部３０，１３０，メモリ２０＞
演算制御部３０，１３０は、例えば公知のコンピュータに所定のプログラムを実行させて実現してもよいし、上述の量子コンピュータによって実現してもよい。また、メモリ２０は、ＤＲＡＭ、ＳＲＡＭ、フラッシュメモリ、ＮＶ（Nonvolatile）ＲＡＭ等の読書き可能な半導体メモリであってもよいし、上述の量子メモリであってもよい。
なお、本発明は上述の実施の形態に限定されるものではない。例えば、第１の実施の形態では、ｐが素数であることとしたが、ａ＋ｂ＜２ｐであるならばｐは素数でなくてもよい。また、量子操作後の各量子ビットを他の量子計算に用いる必要がないならば、ステップＳ５からＳ７の処理は行わなくてもよい。また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【産業上の利用可能性】
【００８６】
本発明の産業上の利用分野としては、例えば、楕円曲線暗号等の暗号分野を例示できる。
【図面の簡単な説明】
【００８７】
【図１】図１は、第１の実施の形態における量子演算装置の構成を示したブロック図である。
【図２】図２は、量子演算部の各機能を実現するための基本演算を表した図である。ここで、図２（ａ）は、１量子ビットに対するＮＯＴ演算を表す。図２（ｂ）は、１量子ビットに対するアダマール変換を表す。図２（ｃ）は、１量子ビットに対するｋ回転演算を表す。図２（ｄ）は、２量子ビットに対するＣＮＯＴ（制御ＮＯＴ）演算を表す。
【図３】図３は、第１の実施の形態の処理の全体を説明するためのフローチャートである。
【図４】図４は、加算演算過程〔ＡＤＤ〕／ステップＳ２の詳細を説明するためのフローチャートである。
【図５】図５は、加算演算過程〔ＡＤＤ〕／ステップＳ２の詳細を説明するためのフローチャートである。
【図６】図６は、第１比較演算過程〔ＣＯＭＰＡＲＩＳＯＮ（ｐ）〕／ステップＳ３の詳細の詳細を説明するためのフローチャートである。
【図７】図７は、図６のステップＳ４６のＨＩＧＨＢＩＴ（ｐ）演算操作を説明するためのフローチャートである。
【図８】図８は、図６のステップＳ４６のＨＩＧＨＢＩＴ（ｐ）演算操作を説明するためのフローチャートである。
【図９】図９は、制御減算演算過程〔ＱＦＴ，ΦＡＤＤ（ｐ）−１，ＱＦＴ−１〕を説明するためのフローチャートである。
【図１０】図１０は、第２比較演算過程〔ＣＯＭＰ〕／ステップＳ６の詳細を説明するためのフローチャートである。
【図１１】図１１は、第２比較演算過程〔ＣＯＭＰ〕／ステップＳ６の詳細を説明するためのフローチャートである。
【図１２】図１２は、第１の実施の形態の量子操作全体を説明するための量子回路図（ｎ＝５の例）である。
【図１３】図１３は、加算演算過程〔ＡＤＤ〕の量子操作全体を説明するための量子回路図（ｎ＝５の例）である。
【図１４】図１４は、図１３のＷ１の各量子操作を説明するための量子回路図である。
【図１５】図１５は、図１３のＷ２の各量子操作を説明するための量子回路図である。
【図１６】図１６は、図１３のＷ３の各量子操作を説明するための量子回路図である。
【図１７】図１７は、図１３のＷ４の各量子操作を説明するための量子回路図である。
【図１８】図１８（ａ）は、図１５に示すＭＡＪ（majority）演算を説明するための量子回路図である。図１８（ｂ）は、交換演算過程〔ＳＷＡＰ〕を説明するための量子回路図である。
【図１９】図１９は、第１比較演算過程〔ＣＯＭＰＡＲＩＳＯＮ（ｐ）〕を説明するための量子回路図（ｎ＝５の例）である。
【図２０】図２０は、ＨＩＧＨＢＩＴ（ｐ）演算を説明するための量子回路図である。
【図２１】図２１は、ＨＩＧＨＢＩＴ（ｐ）演算を説明するための量子回路図である。
【図２２】図２２（ａ）は、図２０及び図２１のＡ（ｐ）演算を説明するための量子回路図であり、図２２（ｂ）は、Ｃ（ｐ）演算を説明するための量子回路図である。
【図２３】図２３は、第２比較演算過程〔ＣＯＭＰ〕の量子操作全体を説明するための量子回路図（ｎ＝５の例）である。
【図２４】図２４は、図２３のＴ１の各量子操作を説明するための量子回路図である。
【図２５】図２５は、図２３のＴ２の各量子操作を説明するための量子回路図である。
【図２６】図２６は、図２３のＴ３の各量子操作を説明するための量子回路図である。
【図２７】図２７は、図２３のＴ４の各量子操作を説明するための量子回路図である。
【図２８】図２８は、第２の実施の形態における量子演算装置の構成を示したブロック図である。
【図２９】図２９は、第２の実施の形態のＨＩＧＨＢＩＴ演算操作を説明するためのフローチャートである。
【図３０】図３０は、第２の実施の形態のＨＩＧＨＢＩＴ演算操作を説明するためのフローチャートである。
【図３１】図３１は、第２の実施の形態のＨＩＧＨＢＩＴ演算操作を説明するための量子回路図である。
【図３２】図３２は、第２の実施の形態のＨＩＧＨＢＩＴ演算操作を説明するための量子回路図である。
【図３３】図３３（ａ）は、図３１及び図３２のＡ演算操作を説明するための量子回路図であり、図３３（ｂ）は、Ｃ演算操作を説明するための量子回路図である。
【図３４】図３４は、図３１及び図３２の３トフォリ演算操作を説明するための量子回路である。
【図３５】図３５は、ｎ＝５の場合における従来技術１の量子回路図である。
【図３６】図３６は、図３５におけるＡＤＤ１演算の量子回路図である。
【図３７】図３７（ａ）は、ＣＡＲＲＹ演算を示す量子回路図であり、図３７（ｂ）は、ＳＵＭ演算を示す量子回路図である。
【図３８】図３８（ａ）はトフォリ演算を示す図であり、図３８（ｂ）はＣＮＯＴ演算を示す図であり、図３８（ｃ）はＮＯＴ演算を示す図である。
【図３９】図３９は、ＡＤＤ１（ｐ）演算の量子回路を示す図である。
【図４０】図４０（ａ）は、ＣＡＲＲＹ（ｐ）演算を示す量子回路図であり、図４０（ｂ）は、ＳＵＭ（ｐ）演算を示す量子回路図である。
【図４１】図４１は、ｎ＝５の場合における従来技術２の量子回路図である。
【図４２】図４２は、ＱＦＴ演算を示す量子回路である。
【図４３】図４３（ａ）は、アダマール変換演算を表す図であり、図４３（ｂ）は、制御回転演算を表す図である。
【図４４】図４４は、ＱＦＴ演算とＱＦＴ−１演算との間に実行されるΦＡＤＤ変換を表した量子回路図である。
【図４５】図４５は、ΦＡＤＤ（ｐ）演算を表した量子回路図である。
【図４６】図４６は、図４５のσｋ（ｆ）演算を表した量子回路図である。
【符号の説明】
【００８８】
１，１００  量子演算装置
【図１】
0004829623.tif 000007
【図２】
0004829623.tif 000008
【図３】
0004829623.tif 000009
【図４】
0004829623.tif 000010
【図５】
0004829623.tif 000011
【図６】
0004829623.tif 000012
【図７】
0004829623.tif 000013
【図８】
0004829623.tif 000014
【図９】
0004829623.tif 000015
【図１０】
0004829623.tif 000016
【図１１】
0004829623.tif 000017
【図１２】
0004829623.tif 000018
【図１３】
0004829623.tif 000019
【図１４】
0004829623.tif 000020
【図１５】
0004829623.tif 000021
【図１６】
0004829623.tif 000022
【図１７】
0004829623.tif 000023
【図１８】
0004829623.tif 000024
【図１９】
0004829623.tif 000025
【図２０】
0004829623.tif 000026
【図２１】
0004829623.tif 000027
【図２２】
0004829623.tif 000028
【図２３】
0004829623.tif 000029
【図２４】
0004829623.tif 000030
【図２５】
0004829623.tif 000031
【図２６】
0004829623.tif 000032
【図２７】
0004829623.tif 000033
【図２８】
0004829623.tif 000034
【図２９】
0004829623.tif 000035
【図３０】
0004829623.tif 000036
【図３１】
0004829623.tif 000037
【図３２】
0004829623.tif 000038
【図３３】
0004829623.tif 000039
【図３４】
0004829623.tif 000040
【図３５】
0004829623.tif 000041
【図３６】
0004829623.tif 000042
【図３７】
0004829623.tif 000043
【図３８】
0004829623.tif 000044
【図３９】
0004829623.tif 000045
【図４０】
0004829623.tif 000046
【図４１】
0004829623.tif 000047
【図４２】
0004829623.tif 000048
【図４３】
0004829623.tif 000049
【図４４】
0004829623.tif 000050
【図４５】
0004829623.tif 000051
【図４６】
0004829623.tif 000052