(57)【要約】【課題】従来よりも少ない数の補助量子ビットで量子加算演算を行う。【解決手段】加算処理ブロックＡｉに属する初期量子状態の量子ビットＱｘ（ｉ＋１）・ｋ−１，…，Ｑｘｉ・ｋ及び量子ビットＱｙ（ｉ＋１）・ｋ−１，…，Ｑｙｉ・ｋと、初期量子状態の補助量子ビットＱｚｉ，１とに対してHIGHBIT演算を施し、補助量子ビットＱｚｗ，１の量子状態を｜ｄｗ＞〔ｄｗ∈｛０，１｝は、加算処理ブロックＡｗから加算処理ブロックＡｗ＋１への繰上げ値〕とする繰上げ処理を加算処理ブロックＡｉ単位で実行し、加算処理ブロックＡｉ単位で加算処理（SUM演算及び繰上げSUM演算）を行う。【選択図】図２
2008269012.tif 000002
【特許請求の範囲】
【請求項１】
２つの２進数ａ＝ａｎ−１…ａ０〔ａｐ∈｛０，１｝，ｐ∈｛０，…，ｎ−１｝，ｎ≧４〕及びｂ＝ｂｎ−１…ｂ０〔ｂｐ∈｛０，１｝〕に対し、ａ＋ｂ＝ｓｎ…ｓ０〔ｓｑ∈｛０，１｝，ｑ∈｛０，…，ｎ｝〕を算出する量子加算演算方法であって、
初期量子状態がそれぞれ｜ａ０＞，…，｜ａｎ−１＞であるｎ個の量子ビットＱｘ０，…，Ｑｘｎ−１と、初期量子状態がそれぞれ｜ｂ０＞，…，｜ｂｎ−１＞であるｎ個の量子ビットＱｙ０，…，Ｑｙｎ−１と、初期量子状態が｜０＞である１個の補助量子ビットＱｚ０，１と、初期量子状態がそれぞれ｜０＞である２・｛（ｎ／ｋ）−１｝〔ｋはｎを割り切る２以上ｎ未満の整数の定数である〕個の補助量子ビットＱｚ１，１，Ｑｚ１，２，Ｑｚ２，１，Ｑｚ２，２，…，Ｑｚ（ｎ／ｋ）−１，１，Ｑｚ（ｎ／ｋ）−１，２と、初期量子状態がそれぞれ｜０＞である
【数１】
2008269012.tif 000025
個〔Ｌはｎ／２Ｌ−１以下の最大の整数をｎ／ｋとする整数である〕の補助量子ビットＱｚ（ｎ／ｋ），…，Ｑｚ（ｎ／ｋ）＋ｍ−１と、が少なくとも存在し、
量子ビットＱｘ（ｉ＋１）・ｋ−１，…，Ｑｘｉ・ｋと量子ビットＱｙ（ｉ＋１）・ｋ−１，…，Ｑｙｉ・ｋとをｉ番目〔０≦ｉ≦（ｎ／ｋ）−１（ｉは整数）〕の加算処理ブロックＡｉとし、当該加算処理ブロックＡｉに属する初期量子状態の量子ビットＱｘ（ｉ＋１）・ｋ−１，…，Ｑｘｉ・ｋ及び量子ビットＱｙ（ｉ＋１）・ｋ−１，…，Ｑｙｉ・ｋと、初期量子状態の補助量子ビットＱｚｉ，１とに対してHIGHBIT演算を施し、量子ビットＱｘ（ｉ＋１）・ｋ−１，…，Ｑｘｉ・ｋの量子状態をそれぞれ｜ａ（ｉ＋１）・ｋ−１＞，…，｜ａｉ・ｋ＞とし、量子ビットＱｙ（ｉ＋１）・ｋ−１，…，Ｑｙｉ・ｋの量子状態をそれぞれ｜ｂ（ｉ＋１）・ｋ−１＞，…，｜ｂｉ・ｋ＞とし、補助量子ビットＱｚｉ，１の量子状態を｜ｃｉ＞〔ｃｉは、２つの２進数ａ（ｉ＋１）・ｋ−１…ａｉ・ｋとｂ（ｉ＋１）・ｋ−１…ｂｉ・ｋの和を２進表記した場合の最上位ビット値〕とする処理を、各加算処理ブロックＡｉについてそれぞれ実行するHIGHBIT演算過程と、
補助量子ビットＱｚ０，１，Ｑｚ１，１，Ｑｚ１，２，Ｑｚ２，１，Ｑｚ２，２，…，Ｑｚ（ｎ／ｋ）−１，１，Ｑｚ（ｎ／ｋ）−１，２，Ｑｚ（ｎ／ｋ），…，Ｑｚ（ｎ／ｋ）＋ｍ−１を用い、補助量子ビットＱｚｗ，１の量子状態を｜ｄｗ＞〔ｄｗ∈｛０，１｝は、加算処理ブロックＡｗから加算処理ブロックＡｗ＋１への繰上げ値〕とする処理を、０≦ｗ≦（ｎ／ｋ）−２（ｗは整数）についてそれぞれ実行し、さらに補助量子ビットＱｚ（ｎ／ｋ）−１，１の量子状態を｜ｓｎ＞とする処理を実行する繰上げ値演算過程と、
加算処理ブロックＡ０に属する量子ビットＱｘｋ−１，…，Ｑｘ０と量子ビットＱｙｋ−１，…，Ｑｙ０とに対してSUM演算を施し、量子ビットＱｘｋ−１，…，Ｑｘ０の量子状態をそれぞれ｜ａｋ−１＞，…，｜ａ０＞とし、量子ビットＱｙｋ−１，…，Ｑｙ０の量子状態をそれぞれ｜ｓｋ−１＞，…，｜ｓ０＞とする第１のSUM演算過程と、
加算処理ブロックＡｉに属する量子ビットＱｘ（ｉ＋１）・ｋ−１，…，Ｑｘｉ・ｋ及び量子ビットＱｙ（ｉ＋１）・ｋ−１，…，Ｑｙｉ・ｋと、補助量子ビットＱｚｉ−１，１とに対して繰上げSUM演算を施し、量子ビットＱｘ（ｉ＋１）・ｋ−１，…，Ｑｘｉ・ｋの量子状態をそれぞれ｜ａ（ｉ＋１）・ｋ−１＞，…，｜ａｉ・ｋ＞とし、量子ビットＱｙ（ｉ＋１）・ｋ−１，…，Ｑｙｉ・ｋの量子状態をそれぞれ｜ｓ（ｉ＋１）・ｋ−１＞，…，｜ｓｉ・ｋ＞とし、補助量子ビットＱｚｉ−１，１の量子状態を維持する処理を、１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）についてそれぞれ実行する第２のSUM演算過程と、
を実行することを特徴とする量子加算演算方法。
【請求項２】
請求項１に記載の量子加算演算方法であって、
上記繰上げ値演算過程は、
量子ビットＱｘｉ・ｋ+ｊを制御ビットとし、量子ビットＱｙｉ・ｋ+ｊを目標ビットとしたCNOT演算を０≦ｊ≦ｋ−１（ｊは整数）についてそれぞれ実行する処理を、１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）についてそれぞれ実行する第１のCNOT演算過程と、
上記第１のCNOT演算過程による処理がなされたｋ個の量子ビットＱｙｉ・ｋ，…，Ｑｙｉ・ｋ＋ｋ−１を制御ビットとし、補助量子ビットＱｚｉ，２を目標ビットとしたk-Toffoli演算を、１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）についてそれぞれ実行する第１のk-Toffoli演算過程と、
第１のk-Toffoli演算過程によるk-Toffoli演算が施された補助量子ビットＱｚｉ，２を補助量子ビットＱｐＬ−１（ｉ）と表現した場合における、補助量子ビットＱｐｔ−１（２ｉ），Ｑｐｔ−１（２ｉ＋１）を制御ビットとし、補助量子ビットＱｚ（ｎ／ｋ），…，Ｑｚ（ｎ／ｋ）＋ｍ−１うちの１つの補助量子ビットである補助量子ビットＱｐｔ（ｉ）を目標ビットとしたToffoli演算を、目標ビットを重複させることなく、ｉ＝１からｉを１ずつ増加させながら
【数２】
2008269012.tif 000026
まで実行する処理を、ｔ＝Ｌからｔを１ずつ増加させながら
【数３】
2008269012.tif 000027
まで実行する第１のToffoli演算過程と、
HIGHBIT演算過程による処理が施された補助量子ビットＱｚｉ，１を補助量子ビットＱｇＬ−１（ｉ）と表現した場合における、補助量子ビットＱｇｔ−１（２ｉ），Ｑｐｔ−１（２ｉ＋１）を制御ビットとし、補助量子ビットＱｇｔ−１（２ｉ＋１）を目標ビットとしたToffoli演算〔当該Toffoli演算後の補助量子ビットＱｇｔ−１（２ｉ＋１）を補助量子ビットＱｇｔ（ｉ）と表現〕を、ｉ＝０からｉを１ずつ増加させながら
【数４】
2008269012.tif 000028
まで実行する処理を、ｔ＝Ｌからｔを１ずつ増加させながら
【数５】
2008269012.tif 000029
まで実行する第２のToffoli演算過程と、
ｕ＝２ｔ・ｉ／ｋ−１とした場合における補助量子ビットＱｚｕ，１，Ｑｐｔ−１（２ｉ）を制御ビットとし、補助量子ビットＱｇｔ−１（２ｉ）を目標ビットとしたToffoli演算を、ｉ＝１からｉを１ずつ増加させながら
【数６】
2008269012.tif 000030
まで実行する処理を、
【数７】
2008269012.tif 000031
からｔを１ずつ減少させながらｔ＝Ｌまで実行する第３のToffoli演算過程と、
補助量子ビットＱｐｔ−１（２ｉ），Ｑｐｔ−１（２ｉ＋１）を制御ビットとし、補助量子ビットＱｐｔ（ｉ）を目標ビットとしたToffoli演算を、
【数８】
2008269012.tif 000032
からｉを１ずつ減少させながらｉ＝１まで実行する処理を、
【数９】
2008269012.tif 000033
からｔを１ずつ減少させながらｔ＝Ｌまで実行する第４のToffoli演算過程と、
第４のToffoli演算過程による処理の後、ｋ個の量子ビットＱｙｉ・ｋ，…，Ｑｙｉ・ｋ＋ｋ−１を制御ビットとし、補助量子ビットＱｚｉ，２を目標ビットとしたk-Toffoli演算を、１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）についてそれぞれ実行する第２のk-Toffoli演算過程と、
第２のk-Toffoli演算過程による処理の後、量子ビットＱｘｉ・ｋ+ｊを制御ビットとし、量子ビットＱｙｉ・ｋ+ｊを目標ビットとしたCNOT演算を０≦ｊ≦ｋ−１（ｊは整数）についてそれぞれ実行する処理を、１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）についてそれぞれ実行する第２のCNOT演算過程と、を有する、
ことを特徴とする量子加算演算方法。
【請求項３】
請求項１に記載の量子加算演算方法であって、
第１のSUM演算過程及び第２のSUM演算過程による処理の後、量子ビットＱｙ（ｉ＋１）・ｋ−１，…，Ｑｙｉ・ｋに対してNOT演算を施す処理を0≦ｉ≦（ｎ／ｋ）−２（ｉは整数）についてそれぞれ実行する第１のNOT演算過程と、
上記繰上げ値演算過程が具備する、補助量子ビットＱｚｗ，１の量子状態を｜ｄｗ＞とする処理の逆演算を、０≦ｗ≦（ｎ／ｋ）−２（ｗは整数）についてそれぞれ実行し、さらに、量子ビットＱｘ（ｗ＋１）・ｋ−１，…，Ｑｘｗ・ｋと量子ビットＱｙ（ｗ＋１）・ｋ−１，…，Ｑｙｗ・ｋと補助量子ビットＱｚｗ，１とに対する上記HIGHBIT演算の逆演算であるHIGHBIT-REV演算を０≦ｗ≦（ｎ／ｋ）−２（ｗは整数）についてそれぞれ実行する逆演算過程と、
逆演算過程による処理の後、量子ビットＱｙ（ｉ＋１）・ｋ−１，…，Ｑｙｉ・ｋに対してNOT演算を施す処理を０≦ｉ≦（ｎ／ｋ）−２（ｉは整数）についてそれぞれ実行する第２のNOT演算過程と、
をさらに実行することを特徴とする量子加算演算方法。
【請求項４】
請求項２に記載の量子加算演算方法であって、
第１のSUM演算過程及び第２のSUM演算過程による処理の後、量子ビットＱｙ（ｉ＋１）・ｋ−１，…，Ｑｙｉ・ｋに対してNOT演算を施す処理を0≦ｉ≦（ｎ／ｋ）−２（ｉは整数）についてそれぞれ実行する第１のNOT演算過程と、
第１のNOT演算過程による処理の後、ｎをｎ−ｋとおいた場合における、上記のHIGHBIT演算過程、第１のCNOT演算過程、第１のk-Toffoli演算過程、第１のToffoli演算過程、第２のToffoli演算過程、第３のToffoli演算過程、第４のToffoli演算過程、第２のk-Toffoli演算過程及び第２のCNOT演算過程によって順次行われる処理からなる演算の逆演算を実行し、
量子ビットＱｘ０，…，Ｑｘｎ−ｋ−１の量子状態をそれぞれ｜ａ０＞，…，｜ａｎ−ｋ−１＞とし、量子ビットＱｙ０，…，Ｑｙｎ−ｋ−１の量子状態をそれぞれ｜ｓ０＞，…，｜ｓｎ−ｋ−１＞の反転状態とし、補助量子ビットＱｚ０，１の量子状態を｜０＞とし、補助量子ビットＱｚ１，１，Ｑｚ１，２，Ｑｚ２，１，Ｑｚ２，２，…，Ｑｚ（ｎ／ｋ）−２，１，Ｑｚ（ｎ／ｋ）−２，２の量子状態をそれぞれ｜０＞にする逆演算過程と、
逆演算過程による処理の後、量子ビットＱｙ（ｉ＋１）・ｋ−１，…，Ｑｙｉ・ｋに対してNOT演算を施す処理を０≦ｉ≦（ｎ／ｋ）−２（ｉは整数）についてそれぞれ実行する第２のNOT演算過程と、
をさらに実行することを特徴とする量子加算演算方法。
【請求項５】
請求項１又は４に記載の量子加算演算方法であって、
量子ビットＱｘ（ｉ＋１）・ｋ−１，…，Ｑｘｉ・ｋと量子ビットＱｙ（ｉ＋１）・ｋ−１，…，Ｑｙｉ・ｋと補助量子ビットＱｚｉ，１とに対する上記HIGHBIT演算は、
量子ビットＱｘｉ・ｋ，Ｑｙｉ・ｋを制御ビットとし、補助量子ビットＱｚｉ，１を目標ビットとするToffoli演算を行う過程と、
ｋ≧３である場合にのみ行われる、量子ビットＱｘｉ・ｋ＋ｗを第１量子ビットとし、量子ビットＱｙｉ・ｋ＋ｗを第２量子ビットとし、補助量子ビットＱｚｉ，１を第３量子ビットとしたMAJ演算と、量子ビットＱｘｉ・ｋ＋ｗ，Ｑｙｉ・ｋ＋ｗを制御ビットとし、量子ビットＱｘｉ・ｋを目標ビットとしたToffoli演算とを、それぞれ、ｗをｗ＝１から１ずつ増加させてｗ＝ｋ−２まで実行する過程と、
量子ビットＱｘ（ｉ＋１）・ｋ−１を第１量子ビットとし、量子ビットＱｙ（ｉ＋１）・ｋ−１を第２量子ビットとし、補助量子ビットＱｚｉ，１を第３量子ビットとしたMAJ演算を実行する過程と、
ｋ≧３である場合にのみ行われる、量子ビットＱｘｉ・ｋを制御ビットとし、量子ビットＱｙｉ・ｋ＋ｗを目標ビットとしたCNOT演算と、量子ビットＱｘｉ・ｋを制御ビットとし、量子ビットＱｘｉ・ｋ＋ｗを目標ビットとしたCNOT演算と、量子ビットＱｘｉ・ｋ＋ｗ−１，Ｑｙｉ・ｋ＋ｗ−１を制御ビットとし、量子ビットＱｘｉ・ｋを目標ビットとしたToffoli演算とを、それぞれ、ｗをｗ＝ｋ−１から１ずつ減少させてｗ＝２まで実行する過程と、
量子ビットＱｙｉ・ｋにNOT演算を施す過程と、
ｋ≧３である場合にのみ行われる、量子ビットＱｘｉ・ｋ，Ｑｙｉ・ｋを制御ビットとし、量子ビットＱｙｉ・ｋ＋ｗを目標ビットとしたToffoli演算と、量子ビットＱｘｉ・ｋ，Ｑｙｉ・ｋを制御ビットとし、量子ビットＱｘｉ・ｋ＋ｗを目標ビットとしたToffoli演算とを、それぞれ、２≦ｗ≦ｋ−１（ｗは整数）について実行する過程と、
量子ビットＱｙｉ・ｋにNOT演算を施す過程と、
量子ビットＱｘｉ・ｋ，Ｑｙｉ・ｋを制御ビットとし、量子ビットＱｙｉ・ｋ＋１を目標ビットとしたToffoli演算と、量子ビットＱｘｉ・ｋ，Ｑｙｉ・ｋを制御ビットとし、量子ビットＱｘｉ・ｋ＋１を目標ビットとしたToffoli演算とを、それぞれ実行する過程と、を実行する演算であり、
上記MAJ演算は、
第３量子ビットを制御ビットとし、第２量子ビットを目標ビットとしたCNOT演算を行う第１過程と、
第３量子ビットを制御ビットとし、第１量子ビットを目標ビットとしたCNOT演算を行う第２過程と、
上記第１過程及び上記第２過程の後に行われる、第１量子ビット及び第２量子ビットを制御ビットとし、第３量子ビットを目標ビットとしたToffoli演算を行うMAJ第３過程と、を実行する演算である、
ことを特徴とする量子加算演算方法。
【請求項６】
請求項１から４の何れかに記載の量子加算演算方法であって、
量子ビットＱｘｋ−１，…，Ｑｘ０と量子ビットＱｙｋ−１，…，Ｑｙ０とに対する上記SUM演算は、
量子ビットＱｙｋ−１を制御ビットとし、量子ビットＱｘｗを目標ビットとしたCNOT演算と、量子ビットＱｙｋ−１を制御ビットとし、量子ビットＱｙｗを目標ビットとしたCNOT演算とを、それぞれ、０≦ｗ≦ｋ−２（ｗは整数）について実行する過程と、
量子ビットＱｘｗを第１量子ビットとし、量子ビットＱｙｗを第２量子ビットとし、量子ビットＱｙｋ−１を第３量子ビットとしたMAJ演算を、それぞれ、ｗをｗ＝０から１ずつ増加させてｗ＝ｋ−２まで実行する過程と、
量子ビットＱｘｗを制御ビットとし、量子ビットＱｙｗを目標ビットとしたCNOT演算を、それぞれ、０≦ｗ≦ｋ−１（ｗは整数）について実行する過程と、を実行する演算であり、
量子ビットＱｘ（ｉ＋１）・ｋ−１，…，Ｑｘｉ・ｋと量子ビットＱｙ（ｉ＋１）・ｋ−１，…，Ｑｙｉ・ｋと補助量子ビットＱｚｉ−１，１とに対する上記繰上げSUM演算〔１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）〕は、
量子ビットＱｙ（ｉ＋１）・ｋ−１を制御ビットとし、量子ビットＱｘｉ・ｋ＋ｗを目標ビットとしたCNOT演算と、量子ビットＱｙ（ｉ＋１）・ｋ−１を制御ビットとし、量子ビットＱｙｉ・ｋ＋ｗを目標ビットとしたCNOT演算とを、それぞれ、０≦ｗ≦ｋ−２（ｗは整数）について実行する過程と、
補助量子ビットＱｚｉ−１，１を制御ビットとし、量子ビットＱｙ（ｉ＋１）・ｋ−１を目標ビットとしてCNOT演算を実行する過程と、
ｋ≧３である場合にのみ行われる、量子ビットＱｘｉ・ｋ＋ｗを第１量子ビットとし、量子ビットＱｙｉ・ｋ＋ｗを第２量子ビットとし、量子ビットＱｙ（ｉ＋１）・ｋ−１を第３量子ビットとしたMAJ演算と、量子ビットＱｘｉ・ｋ＋ｗ，Ｑｙｉ・ｋ＋ｗを制御ビットとし、補助量子ビットＱｚｉ−１，１を目標ビットとしたToffoli演算とを、それぞれ、ｗをｗ＝０から１ずつ増加させてｗ＝ｋ−３まで実行する過程と、
量子ビットＱｘ（ｉ＋１）・ｋ−２を第１量子ビットとし、量子ビットＱｙ（ｉ＋１）・ｋ−２を第２量子ビットとし、量子ビットＱｙ（ｉ＋１）・ｋ−１を第３量子ビットとしたMAJ演算を実行する過程と、
ｋ≧３である場合にのみ行われる、補助量子ビットＱｚｉ−１，１を制御ビットとし、量子ビットＱｘｉ・ｋ＋ｗを目標ビットとしたCNOT演算と、量子ビットＱｘｉ・ｋ＋ｗ−１，Ｑｙｉ・ｋ＋ｗ−１を制御ビットとし、補助量子ビットＱｚｉ−１，１を目標ビットとしたToffoli演算とを、それぞれ、ｗをｗ＝ｋ−２から１ずつ減少させてｗ＝１まで実行する過程と、
補助量子ビットＱｚｉ−１，１を制御ビットとし、量子ビットＱｘｉ・ｋを目標ビットとしたCNOT演算を実行する過程と、
量子ビットＱｘｉ・ｋ＋ｗを制御ビットとし、量子ビットＱｙｉ・ｋ＋ｗを目標ビットとしたCNOT演算を、それぞれ、０≦ｗ≦ｋ−１（ｗは整数）について実行する過程と、を実行する演算を実行する過程と、を実行する演算であり、
上記MAJ演算は、
第３量子ビットを制御ビットとし、第２量子ビットを目標ビットとしたCNOT演算を行う第１過程と、
第３量子ビットを制御ビットとし、第１量子ビットを目標ビットとしたCNOT演算を行う第２過程と、
上記第１過程及び上記第２過程の後に行われる、第１量子ビット及び第２量子ビットを制御ビットとし、第３量子ビットを目標ビットとしたToffoli演算を行うMAJ第３過程と、を実行する演算である、
ことを特徴とする量子加算演算方法。
【請求項７】
請求項１から６の何れかに記載の量子加算演算方法であって、
定数ｋは、ｌｏｇ２（ｌｏｇ２ｎ）以下の最大の整数である、
ことを特徴とする量子加算演算方法。
【請求項８】
２つの２進数ａ＝ａｎ−１…ａ０〔ａｐ∈｛０，１｝，ｐ∈｛０，…，ｎ−１｝，ｎ≧４〕及びｂ＝ｂｎ−１…ｂ０〔ｂｐ∈｛０，１｝〕に対し、ａ＋ｂ＝ｓｎ…ｓ０〔ｓｑ∈｛０，１｝，ｑ∈｛０，…，ｎ｝〕を算出する量子加算演算装置であって、
初期量子状態がそれぞれ｜ａ０＞，…，｜ａｎ−１＞であるｎ個の量子ビットＱｘ０，…，Ｑｘｎ−１と、
初期量子状態がそれぞれ｜ｂ０＞，…，｜ｂｎ−１＞であるｎ個の量子ビットＱｙ０，…，Ｑｙｎ−１と、
初期量子状態が｜０＞である１個の補助量子ビットＱｚ０，１と、初期量子状態がそれぞれ｜０＞である２・｛（ｎ／ｋ）−１｝〔ｋはｎを割り切る２以上ｎ未満の整数の定数である〕個の補助量子ビットＱｚ１，１，Ｑｚ１，２，Ｑｚ２，１，Ｑｚ２，２，…，Ｑｚ（ｎ／ｋ）−１，１，Ｑｚ（ｎ／ｋ）−１，２と、
初期量子状態がそれぞれ｜０＞である
【数１０】
2008269012.tif 000034
個〔Ｌはｎ／２Ｌ−１以下の最大の整数をｎ／ｋとする整数である〕の補助量子ビットＱｚ（ｎ／ｋ），…，Ｑｚ（ｎ／ｋ）＋ｍ−１と、
量子ビットＱｘ（ｉ＋１）・ｋ−１，…，Ｑｘｉ・ｋと量子ビットＱｙ（ｉ＋１）・ｋ−１，…，Ｑｙｉ・ｋとをｉ番目〔０≦ｉ≦（ｎ／ｋ）−１（ｉは整数）〕の加算処理ブロックＡｉとし、当該加算処理ブロックＡｉに属する初期量子状態の量子ビットＱｘ（ｉ＋１）・ｋ−１，…，Ｑｘｉ・ｋ及び量子ビットＱｙ（ｉ＋１）・ｋ−１，…，Ｑｙｉ・ｋと、初期量子状態の補助量子ビットＱｚｉ，１とに対してHIGHBIT演算を施し、量子ビットＱｘ（ｉ＋１）・ｋ−１，…，Ｑｘｉ・ｋの量子状態をそれぞれ｜ａ（ｉ＋１）・ｋ−１＞，…，｜ａｉ・ｋ＞とし、量子ビットＱｙ（ｉ＋１）・ｋ−１，…，Ｑｙｉ・ｋの量子状態をそれぞれ｜ｂ（ｉ＋１）・ｋ−１＞，…，｜ｂｉ・ｋ＞とし、補助量子ビットＱｚｉ，１の量子状態を｜ｃｉ＞〔ｃｉは、２つの２進数ａ（ｉ＋１）・ｋ−１…ａｉ・ｋとｂ（ｉ＋１）・ｋ−１…ｂｉ・ｋの和を２進表記した場合の最上位ビット値〕とする処理を、各加算処理ブロックＡｉについてそれぞれ実行するHIGHBIT演算部と、
補助量子ビットＱｚ０，１，Ｑｚ１，１，Ｑｚ１，２，Ｑｚ２，１，Ｑｚ２，２，…，Ｑｚ（ｎ／ｋ）−１，１，Ｑｚ（ｎ／ｋ）−１，２，Ｑｚ（ｎ／ｋ），…，Ｑｚ（ｎ／ｋ）＋ｍ−１を用い、補助量子ビットＱｚｗ，１の量子状態を｜ｄｗ＞〔ｄｗ∈｛０，１｝は、加算処理ブロックＡｗから加算処理ブロックＡｗ＋１への繰上げ値〕とする処理を、０≦ｗ≦（ｎ／ｋ）−２（ｗは整数）についてそれぞれ実行し、さらに補助量子ビットＱｚ（ｎ／ｋ）−１，１の量子状態を｜ｓｎ＞とする処理を実行する繰上げ値演算部と、
加算処理ブロックＡ０に属する量子ビットＱｘｋ−１，…，Ｑｘ０と量子ビットＱｙｋ−１，…，Ｑｙ０とに対してSUM演算を施し、量子ビットＱｘｋ−１，…，Ｑｘ０の量子状態をそれぞれ｜ａｋ−１＞，…，｜ａ０＞とし、量子ビットＱｙｋ−１，…，Ｑｙ０の量子状態をそれぞれ｜ｓｋ−１＞，…，｜ｓ０＞とする第１のSUM演算部と、
加算処理ブロックＡｉに属する量子ビットＱｘ（ｉ＋１）・ｋ−１，…，Ｑｘｉ・ｋ及び量子ビットＱｙ（ｉ＋１）・ｋ−１，…，Ｑｙｉ・ｋと、補助量子ビットＱｚｉ−１，１とに対して繰上げSUM演算を施し、量子ビットＱｘ（ｉ＋１）・ｋ−１，…，Ｑｘｉ・ｋの量子状態をそれぞれ｜ａ（ｉ＋１）・ｋ−１＞，…，｜ａｉ・ｋ＞とし、量子ビットＱｙ（ｉ＋１）・ｋ−１，…，Ｑｙｉ・ｋの量子状態をそれぞれ｜ｓ（ｉ＋１）・ｋ−１＞，…，｜ｓｉ・ｋ＞とし、補助量子ビットＱｚｉ−１，１の量子状態を維持する処理を、１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）についてそれぞれ実行する第２のSUM演算部と、
を有することを特徴とする量子加算演算装置。
【請求項９】
請求項８に記載の量子加算演算装置であって、
上記繰上げ値演算部は、
量子ビットＱｘｉ・ｋ+ｊを制御ビットとし、量子ビットＱｙｉ・ｋ+ｊを目標ビットとしたCNOT演算を０≦ｊ≦ｋ−１（ｊは整数）についてそれぞれ実行する処理を、１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）についてそれぞれ実行する第１のCNOT演算部と、
上記第１のCNOT演算部による処理がなされたｋ個の量子ビットＱｙｉ・ｋ，…，Ｑｙｉ・ｋ＋ｋ−１を制御ビットとし、補助量子ビットＱｚｉ，２を目標ビットとしたk-Toffoli演算を、１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）についてそれぞれ実行する第１のk-Toffoli演算部と、
第１のk-Toffoli演算部によるk-Toffoli演算が施された補助量子ビットＱｚｉ，２を補助量子ビットＱｐＬ−１（ｉ）と表現した場合における、補助量子ビットＱｐｔ−１（２ｉ），Ｑｐｔ−１（２ｉ＋１）を制御ビットとし、補助量子ビットＱｚ（ｎ／ｋ），…，Ｑｚ（ｎ／ｋ）＋ｍ−１うちの１つの補助量子ビットである補助量子ビットＱｐｔ（ｉ）を目標ビットとしたToffoli演算を、目標ビットを重複させることなく、ｉ＝１からｉを１ずつ増加させながら
【数１１】
2008269012.tif 000035
まで実行する処理を、ｔ＝Ｌからｔを１ずつ増加させながら
【数１２】
2008269012.tif 000036
まで実行する第１のToffoli演算部と、
HIGHBIT演算部による処理が施された補助量子ビットＱｚｉ，１を補助量子ビットＱｇＬ−１（ｉ）と表現した場合における、補助量子ビットＱｇｔ−１（２ｉ），Ｑｐｔ−１（２ｉ＋１）を制御ビットとし、補助量子ビットＱｇｔ−１（２ｉ＋１）を目標ビットとしたToffoli演算〔当該Toffoli演算後の補助量子ビットＱｇｔ−１（２ｉ＋１）を補助量子ビットＱｇｔ（ｉ）と表現〕を、ｉ＝０からｉを１ずつ増加させながら
【数１３】
2008269012.tif 000037
まで実行する処理を、ｔ＝Ｌからｔを１ずつ増加させながら
【数１４】
2008269012.tif 000038
まで実行する第２のToffoli演算部と、
ｕ＝２ｔ・ｉ／ｋ−１とした場合における補助量子ビットＱｚｕ，１，Ｑｐｔ−１（２ｉ）を制御ビットとし、補助量子ビットＱｇｔ−１（２ｉ）を目標ビットとしたToffoli演算を、ｉ＝１からｉを１ずつ増加させながら
【数１５】
2008269012.tif 000039
まで実行する処理を、
【数１６】
2008269012.tif 000040
からｔを１ずつ減少させながらｔ＝Ｌまで実行する第３のToffoli演算部と、
補助量子ビットＱｐｔ−１（２ｉ），Ｑｐｔ−１（２ｉ＋１）を制御ビットとし、補助量子ビットＱｐｔ（ｉ）を目標ビットとしたToffoli演算を、
【数１７】
2008269012.tif 000041
からｉを１ずつ減少させながらｉ＝１まで実行する処理を、
【数１８】
2008269012.tif 000042
からｔを１ずつ減少させながらｔ＝Ｌまで実行する第４のToffoli演算部と、
第４のToffoli演算部による処理の後、ｋ個の量子ビットＱｙｉ・ｋ，…，Ｑｙｉ・ｋ＋ｋ−１を制御ビットとし、補助量子ビットＱｚｉ，２を目標ビットとしたk-Toffoli演算を、１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）についてそれぞれ実行する第２のk-Toffoli演算部と、
第２のk-Toffoli演算部による処理の後、量子ビットＱｘｉ・ｋ+ｊを制御ビットとし、量子ビットＱｙｉ・ｋ+ｊを目標ビットとしたCNOT演算を０≦ｊ≦ｋ−１（ｊは整数）についてそれぞれ実行する処理を、１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）についてそれぞれ実行する第２のCNOT演算部と、
HIGHBIT演算部による処理の後、加算処理ブロックＡ０に属する量子ビットＱｘｋ−１，…，Ｑｘ０及び量子ビットＱｙｋ−１，…，Ｑｙ０とに対してSUM演算を施し、量子ビットＱｘｋ−１，…，Ｑｘ０の量子状態をそれぞれ｜ａｋ−１＞，…，｜ａ０＞とし、量子ビットＱｙｋ−１，…，Ｑｙ０の量子状態をそれぞれ｜ｓｋ−１＞，…，｜ｓ０＞とする第１のSUM演算部と、
第２のCNOT演算部による処理の後、加算処理ブロックＡｉに属する量子ビットＱｘ（ｉ＋１）・ｋ−１，…，Ｑｘｉ・ｋ及び量子ビットＱｙ（ｉ＋１）・ｋ−１，…，Ｑｙｉ・ｋと、補助量子ビットＱｚｉ−１，１とに対してSUM演算を施し、量子ビットＱｘ（ｉ＋１）・ｋ−１，…，Ｑｘｉ・ｋの量子状態をそれぞれ｜ａ（ｉ＋１）・ｋ−１＞，…，｜ａｉ・ｋ＞とし、量子ビットＱｙ（ｉ＋１）・ｋ−１，…，Ｑｙｉ・ｋの量子状態をそれぞれ｜ｓ（ｉ＋１）・ｋ−１＞，…，｜ｓｉ・ｋ＞とし、補助量子ビットＱｚｉ−１，１の量子状態を維持する処理を、１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）についてそれぞれ実行する第２のSUM演算部と、
を有することを特徴とする量子加算演算装置。
【請求項１０】
請求項８に記載の量子加算演算装置であって、
第１のSUM演算部及び第２のSUM演算部による処理の後、量子ビットＱｙ（ｉ＋１）・ｋ−１，…，Ｑｙｉ・ｋに対してNOT演算を施す処理を0≦ｉ≦（ｎ／ｋ）−２（ｉは整数）についてそれぞれ実行する第１のNOT演算部と、
上記繰上げ値演算部による補助量子ビットＱｚｗ，１の量子状態を｜ｄｗ＞とする処理の逆演算を、０≦ｗ≦（ｎ／ｋ）−２（ｗは整数）についてそれぞれ実行し、さらに、量子ビットＱｘ（ｗ＋１）・ｋ−１，…，Ｑｘｗ・ｋと量子ビットＱｙ（ｗ＋１）・ｋ−１，…，Ｑｙｗ・ｋと補助量子ビットＱｚｗ，１とに対する上記HIGHBIT演算の逆演算であるHIGHBIT-REV演算を０≦ｗ≦（ｎ／ｋ）−２（ｗは整数）についてそれぞれ実行する逆演算部と、
逆演算部による処理の後、量子ビットＱｙ（ｉ＋１）・ｋ−１，…，Ｑｙｉ・ｋに対してNOT演算を施す処理を０≦ｉ≦（ｎ／ｋ）−２（ｉは整数）についてそれぞれ実行する第２のNOT演算部と、
をさらに実行することを特徴とする量子加算演算装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、量子コンピュータにおいて加算演算を行う技術に関し、特に、効率的な加算演算を行うための技術に関する。
【背景技術】
【０００２】
Ｏ（ｎ）個の基本演算とＯ（ｌｏｇ２ｎ）個の計算ステップとＯ（ｎ）個の補助ビットとを用い、加算演算を行う量子回路が知られている（例えば、非特許文献１参照）。なおＯ（α）は十分大きなαに対してαの定数倍以下となる値を意味する（Ｏ記法）。また、「量子回路」とは、量子ビットに対する操作内容の時系列表現を意味する。
【０００３】
非特許文献１の量子回路は、２つの２進数ａ＝ａｎ−１…ａ０〔ａｐ∈｛０，１｝，ｐ∈｛０，…，ｎ−１｝〕及びｂ＝ｂｎ−１…ｂ０〔ｂｐ∈｛０，１｝〕が入力として与えられたとき、ａ＋ｂ＝ｓｎ…ｓ０〔ｓｑ∈｛０，１｝，ｑ∈｛０，…，ｎ｝〕を算出し、ｓｎ…ｓ０とａとを出力する量子回路である。すなわち、初期量子状態がそれぞれ｜ａ０＞，…，｜ａｎ−１＞であるｎ個の量子ビットＱｘ０，…，Ｑｘｎ−１と、初期量子状態がそれぞれ｜ｂ０＞，…，｜ｂｎ−１＞であるｎ個の量子ビットＱｙ０，…，Ｑｙｎ−１と、初期量子状態がそれぞれ｜０＞であるＯ（ｎ）個の補助量子ビットとに対し、NOT演算，CNOT演算及びToffoli演算を基本演算とした量子操作を施し、量子状態がそれぞれ｜ａ０＞，…，｜ａｎ−１＞であるｎ個の量子ビットＱｘ０，…，Ｑｘｎ−１と、量子状態がそれぞれ｜ｓ０＞，…，｜ｓｎ−１＞であるｎ個の量子ビットＱｙ０，…，Ｑｙｎ−１と、量子状態が｜ｓｎ＞である１個の補助量子ビットと、量子状態が｜０＞である複数の補助量子ビットとを出力する。なお、補助量子ビットとは、補助ビットとして利用する量子ビットを意味する。
【０００４】
図１７，１８は、非特許文献１に記載された加算演算用の量子回路の例示である。なお、図１７は演算の前段の量子操作を示す量子回路であり、図１８は図１７の量子操作の後に行われる後段の量子操作を示す量子回路である。また、図１７，１８は、８ビット同士（ｎ＝８）の加算演算を行う場合の例である。さらに、図１７，１８中のｃｉ（１≦ｉ≦ｎ）は、
【数１９】
2008269012.tif 000003
である。また、
【数２０】
2008269012.tif 000004
が成り立つことが知られている。
【０００５】
図１７に示すように、非特許文献１の量子回路の前段では、初期量子状態がそれぞれ｜ａ０＞，…，｜ａｎ−１＞であるｎ個の量子ビットＱｘ０，…，Ｑｘｎ−１と、初期量子状態がそれぞれ｜ｂ０＞，…，｜ｂｎ−１＞であるｎ個の量子ビットＱｙ０，…，Ｑｙｎ−１とに対し、CNOT演算によって１ビット毎の加算処理を行い、補助量子ビットを用いたToffoli演算及びCNOT演算によって１ビット毎の繰上げ処理を行っている。また、図１８に示すように、非特許文献１の量子回路の後段では、前段で行った演算の一部の逆演算とNOT演算とによって、補助量子ビットの量子状態を｜０＞に戻す処理を行っている。なお、図１７，１８の量子回路は、容易にｎビット同士の加算用の量子回路に拡張できる。
【非特許文献１】T. G. Draper, S. A. Kutin, E. M. Rains, and K. M. Svore, A logarithmic-depth quantum carry-lookahead adder, Quantum Infomation and Computation, Vol. 6 No. 4&5, pp. 351-369, 2006
【発明の開示】
【発明が解決しようとする課題】
【０００６】
非特許文献１の量子回路では、Ｏ（ｎ）個の基本演算による操作をＯ（ｌｏｇ２ｎ）個の計算ステップで実行し、その際Ｏ（ｎ）個の補助量子ビットを利用している。しかし、演算に必要となる量子ビットの数が多くなればなるほど、それらを実現し、協調的に操作することが物理的に困難となる。よって、出来るだけ少ない数の補助量子ビットによって量子回路を構成することが望ましい。
本発明はこのような点に鑑みてなされたものであり、従来よりも少ない数の補助量子ビットで量子加算演算が可能な技術を提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明では上記課題を解決するために、複数の量子ビット単位（加算処理ブロック単位）で加算処理及び繰上げ処理を行う。
【０００８】
すなわち、本発明では、２つの２進数ａ＝ａｎ−１…ａ０〔ａｐ∈｛０，１｝，ｐ∈｛０，…，ｎ−１｝，ｎ≧４〕及びｂ＝ｂｎ−１…ｂ０〔ｂｐ∈｛０，１｝〕に対し、ａ＋ｂ＝ｓｎ…ｓ０〔ｓｑ∈｛０，１｝，ｑ∈｛０，…，ｎ｝〕を算出するために、初期量子状態がそれぞれ｜ａ０＞，…，｜ａｎ−１＞であるｎ個の量子ビットＱｘ０，…，Ｑｘｎ−１と、初期量子状態がそれぞれ｜ｂ０＞，…，｜ｂｎ−１＞であるｎ個の量子ビットＱｙ０，…，Ｑｙｎ−１と、初期量子状態が｜０＞である１個の補助量子ビットＱｚ０，１と、初期量子状態がそれぞれ｜０＞である２・｛（ｎ／ｋ）−１｝〔ｋはｎを割り切る２以上ｎ未満の整数の定数である〕個の補助量子ビットＱｚ１，１，Ｑｚ１，２，Ｑｚ２，１，Ｑｚ２，２，…，Ｑｚ（ｎ／ｋ）−１，１，Ｑｚ（ｎ／ｋ）−１，２と、初期量子状態がそれぞれ｜０＞である
【数２１】
2008269012.tif 000005
個の補助量子ビットＱｚ（ｎ／ｋ），…，Ｑｚ（ｎ／ｋ）＋ｍ−１と、が少なくとも存在し、量子ビットＱｘ（ｉ＋１）・ｋ−１，…，Ｑｘｉ・ｋと量子ビットＱｙ（ｉ＋１）・ｋ−１，…，Ｑｙｉ・ｋとをｉ番目〔０≦ｉ≦（ｎ／ｋ）−１（ｉは整数）〕の加算処理ブロックＡｉとし、当該加算処理ブロックＡｉに属する初期量子状態の量子ビットＱｘ（ｉ＋１）・ｋ−１，…，Ｑｘｉ・ｋ及び量子ビットＱｙ（ｉ＋１）・ｋ−１，…，Ｑｙｉ・ｋと、初期量子状態の補助量子ビットＱｚｉ，１とに対してHIGHBIT演算を施し、量子ビットＱｘ（ｉ＋１）・ｋ−１，…，Ｑｘｉ・ｋの量子状態をそれぞれ｜ａ（ｉ＋１）・ｋ−１＞，…，｜ａｉ・ｋ＞とし、量子ビットＱｙ（ｉ＋１）・ｋ−１，…，Ｑｙｉ・ｋの量子状態をそれぞれ｜ｂ（ｉ＋１）・ｋ−１＞，…，｜ｂｉ・ｋ＞とし、補助量子ビットＱｚｉ，１の量子状態を｜ｃｉ＞〔ｃｉは、２つの２進数ａ（ｉ＋１）・ｋ−１…ａｉ・ｋとｂ（ｉ＋１）・ｋ−１…ｂｉ・ｋの和を２進表記した場合の最上位ビット値〕とする処理を、各加算処理ブロックＡｉについてそれぞれ実行するHIGHBIT演算過程と、補助量子ビットＱｚ０，１，Ｑｚ１，１，Ｑｚ１，２，Ｑｚ２，１，Ｑｚ２，２，…，Ｑｚ（ｎ／ｋ）−１，１，Ｑｚ（ｎ／ｋ）−１，２，Ｑｚ（ｎ／ｋ），…，Ｑｚ（ｎ／ｋ）＋ｍ−１を用い、補助量子ビットＱｚｗ，１の量子状態を｜ｄｗ＞〔ｄｗ∈｛０，１｝は、加算処理ブロックＡｗから加算処理ブロックＡｗ＋１への繰上げ値〕とする処理を、０≦ｗ≦（ｎ／ｋ）−２（ｗは整数）についてそれぞれ実行し、さらに補助量子ビットＱｚ（ｎ／ｋ）−１，１の量子状態を｜ｓｎ＞とする処理を実行する繰上げ値演算過程と、加算処理ブロックＡ０に属する量子ビットＱｘｋ−１，…，Ｑｘ０と量子ビットＱｙｋ−１，…，Ｑｙ０とに対してSUM演算を施し、量子ビットＱｘｋ−１，…，Ｑｘ０の量子状態をそれぞれ｜ａｋ−１＞，…，｜ａ０＞とし、量子ビットＱｙｋ−１，…，Ｑｙ０の量子状態をそれぞれ｜ｓｋ−１＞，…，｜ｓ０＞とする第１のSUM演算過程と、加算処理ブロックＡｉに属する量子ビットＱｘ（ｉ＋１）・ｋ−１，…，Ｑｘｉ・ｋ及び量子ビットＱｙ（ｉ＋１）・ｋ−１，…，Ｑｙｉ・ｋと、補助量子ビットＱｚｉ−１，１とに対して繰上げSUM演算を施し、量子ビットＱｘ（ｉ＋１）・ｋ−１，…，Ｑｘｉ・ｋの量子状態をそれぞれ｜ａ（ｉ＋１）・ｋ−１＞，…，｜ａｉ・ｋ＞とし、量子ビットＱｙ（ｉ＋１）・ｋ−１，…，Ｑｙｉ・ｋの量子状態をそれぞれ｜ｓ（ｉ＋１）・ｋ−１＞，…，｜ｓｉ・ｋ＞とし、補助量子ビットＱｚｉ−１，１の量子状態を維持する処理を、１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）についてそれぞれ実行する第２のSUM演算過程と、を実行する。
【０００９】
このように、本発明では、加算処理ブロック単位で繰上げ値を求め（HIGHBIT演算過程）、補助量子ビットを用いて当該加算処理ブロック単位の繰上げ処理及び加算値の最上位ビット値の算出を行い（繰上げ値演算過程）、加算処理ブロック単位で加算処理を行う。これにより、量子ビット単位で加算処理を行い、補助量子ビットを用いて量子ビット単位で繰上げ処理を行う場合に比べ、処理に必要な補助量子ビット数を削減できる。なお、本発明において「量子ビット（又は補助量子ビット）の量子状態を｜α＞とする」とは、量子ビット（又は補助量子ビット）の量子状態を、｜α＞と他の量子状態との重ね合わせ状態とすることをも含む概念である。
【００１０】
また、本発明における上記繰上げ値演算過程は、例えば、量子ビットＱｘｉ・ｋ+ｊを制御ビットとし、量子ビットＱｙｉ・ｋ+ｊを目標ビットとしたCNOT演算を０≦ｊ≦ｋ−１（ｊは整数）についてそれぞれ実行する処理を、１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）についてそれぞれ実行する第１のCNOT演算過程と、上記第１のCNOT演算過程による処理がなされたｋ個の量子ビットＱｙｉ・ｋ，…，Ｑｙｉ・ｋ＋ｋ−１を制御ビットとし、補助量子ビットＱｚｉ，２を目標ビットとしたk-Toffoli演算を、１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）についてそれぞれ実行する第１のk-Toffoli演算過程と、第１のk-Toffoli演算過程によるk-Toffoli演算が施された補助量子ビットＱｚｉ，２を補助量子ビットＱｐＬ−１（ｉ）と表現した場合における、補助量子ビットＱｐｔ−１（２ｉ），Ｑｐｔ−１（２ｉ＋１）を制御ビットとし、補助量子ビットＱｚ（ｎ／ｋ），…，Ｑｚ（ｎ／ｋ）＋ｍ−１うちの１つの補助量子ビットである補助量子ビットＱｐｔ（ｉ）を目標ビットとしたToffoli演算を、目標ビットを重複させることなく、ｉ＝１からｉを１ずつ増加させながら
【数２２】
2008269012.tif 000006
まで実行する処理を、ｔ＝Ｌからｔを１ずつ増加させながら
【数２３】
2008269012.tif 000007
まで実行する第１のToffoli演算過程と、
【００１１】
HIGHBIT演算過程による処理が施された補助量子ビットＱｚｉ，１を補助量子ビットＱｇＬ−１（ｉ）と表現した場合における、補助量子ビットＱｇｔ−１（２ｉ），Ｑｐｔ−１（２ｉ＋１）を制御ビットとし、補助量子ビットＱｇｔ−１（２ｉ＋１）を目標ビットとしたToffoli演算〔当該Toffoli演算後の補助量子ビットＱｇｔ−１（２ｉ＋１）を補助量子ビットＱｇｔ（ｉ）と表現〕を、ｉ＝０からｉを１ずつ増加させながら
【数２４】
2008269012.tif 000008
まで実行する処理を、ｔ＝Ｌからｔを１ずつ増加させながら
【数２５】
2008269012.tif 000009
まで実行する第２のToffoli演算過程と、ｕ＝２ｔ・ｉ／ｋ−１とした場合における補助量子ビットＱｚｕ，１，Ｑｐｔ−１（２ｉ）を制御ビットとし、補助量子ビットＱｇｔ−１（２ｉ）を目標ビットとしたToffoli演算を、ｉ＝１からｉを１ずつ増加させながら
【数２６】
2008269012.tif 000010
まで実行する処理を、
【００１２】
【数２７】
2008269012.tif 000011
からｔを１ずつ減少させながらｔ＝Ｌまで実行する第３のToffoli演算過程と、補助量子ビットＱｐｔ−１（２ｉ），Ｑｐｔ−１（２ｉ＋１）を制御ビットとし、補助量子ビットＱｐｔ（ｉ）を目標ビットとしたToffoli演算を、
【００１３】
【数２８】
2008269012.tif 000012
からｉを１ずつ減少させながらｉ＝１まで実行する処理を、
【００１４】
【数２９】
2008269012.tif 000013
からｔを１ずつ減少させながらｔ＝Ｌまで実行する第４のToffoli演算過程と、第４のToffoli演算過程による処理の後、ｋ個の量子ビットＱｙｉ・ｋ，…，Ｑｙｉ・ｋ＋ｋ−１を制御ビットとし、補助量子ビットＱｚｉ，２を目標ビットとしたk-Toffoli演算を、１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）についてそれぞれ実行する第２のk-Toffoli演算過程と、第２のk-Toffoli演算過程による処理の後、量子ビットＱｘｉ・ｋ+ｊを制御ビットとし、量子ビットＱｙｉ・ｋ+ｊを目標ビットとしたCNOT演算を０≦ｊ≦ｋ−１（ｊは整数）についてそれぞれ実行する処理を、１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）についてそれぞれ実行する第２のCNOT演算過程と、を有する。
【００１５】
また、本発明において好ましくは、第１のSUM演算過程及び第２のSUM演算過程による処理の後、量子ビットＱｙ（ｉ＋１）・ｋ−１，…，Ｑｙｉ・ｋに対してNOT演算を施す処理を0≦ｉ≦（ｎ／ｋ）−２（ｉは整数）についてそれぞれ実行する第１のNOT演算過程と、上記繰上げ値演算過程が具備する、補助量子ビットＱｚｗ，１の量子状態を｜ｄｗ＞とする処理の逆演算を、０≦ｗ≦（ｎ／ｋ）−２（ｗは整数）についてそれぞれ実行し、さらに、量子ビットＱｘ（ｗ＋１）・ｋ−１，…，Ｑｘｗ・ｋと量子ビットＱｙ（ｗ＋１）・ｋ−１，…，Ｑｙｗ・ｋと補助量子ビットＱｚｗ，１とに対する上記HIGHBIT演算の逆演算であるHIGHBIT-REV演算を０≦ｗ≦（ｎ／ｋ）−２（ｗは整数）についてそれぞれ実行する逆演算過程と、逆演算過程による処理の後、量子ビットＱｙ（ｉ＋１）・ｋ−１，…，Ｑｙｉ・ｋに対してNOT演算を施す処理を０≦ｉ≦（ｎ／ｋ）−２（ｉは整数）についてそれぞれ実行する第２のNOT演算過程と、をさらに実行する。なお、αをβに変換する処理の逆演算とは、βをαに変換する処理の意味である。
【００１６】
これにより、補助量子ビットの量子状態を初期化でき、補助量子ビットの再利用が可能となる。
【００１７】
また、量子ビットＱｘ（ｉ＋１）・ｋ−１，…，Ｑｘｉ・ｋと量子ビットＱｙ（ｉ＋１）・ｋ−１，…，Ｑｙｉ・ｋと補助量子ビットＱｚｉ，１とに対する上記HIGHBIT演算は、例えば、量子ビットＱｘｉ・ｋ，Ｑｙｉ・ｋを制御ビットとし、補助量子ビットＱｚｉ，１を目標ビットとするToffoli演算を行う過程と、ｋ≧３である場合にのみ行われる、量子ビットＱｘｉ・ｋ＋ｗを第１量子ビットとし、量子ビットＱｙｉ・ｋ＋ｗを第２量子ビットとし、補助量子ビットＱｚｉ，１を第３量子ビットとしたMAJ演算と、量子ビットＱｘｉ・ｋ＋ｗ，Ｑｙｉ・ｋ＋ｗを制御ビットとし、量子ビットＱｘｉ・ｋを目標ビットとしたToffoli演算とを、それぞれ、ｗをｗ＝１から１ずつ増加させてｗ＝ｋ−２まで実行する過程と、量子ビットＱｘ（ｉ＋１）・ｋ−１を第１量子ビットとし、量子ビットＱｙ（ｉ＋１）・ｋ−１を第２量子ビットとし、補助量子ビットＱｚｉ，１を第３量子ビットとしたMAJ演算を実行する過程と、ｋ≧３である場合にのみ行われる、量子ビットＱｘｉ・ｋを制御ビットとし、量子ビットＱｙｉ・ｋ＋ｗを目標ビットとしたCNOT演算と、量子ビットＱｘｉ・ｋを制御ビットとし、量子ビットＱｘｉ・ｋ＋ｗを目標ビットとしたCNOT演算と、量子ビットＱｘｉ・ｋ＋ｗ−１，Ｑｙｉ・ｋ＋ｗ−１を制御ビットとし、量子ビットＱｘｉ・ｋを目標ビットとしたToffoli演算とを、それぞれ、ｗをｗ＝ｋ−１から１ずつ減少させてｗ＝２まで実行する過程と、量子ビットＱｙｉ・ｋにNOT演算を施す過程と、ｋ≧３である場合にのみ行われる、量子ビットＱｘｉ・ｋ，Ｑｙｉ・ｋを制御ビットとし、量子ビットＱｙｉ・ｋ＋ｗを目標ビットとしたToffoli演算と、量子ビットＱｘｉ・ｋ，Ｑｙｉ・ｋを制御ビットとし、量子ビットＱｘｉ・ｋ＋ｗを目標ビットとしたToffoli演算とを、それぞれ、２≦ｗ≦ｋ−１（ｗは整数）について実行する過程と、量子ビットＱｙｉ・ｋにNOT演算を施す過程と、量子ビットＱｘｉ・ｋ，Ｑｙｉ・ｋを制御ビットとし、量子ビットＱｙｉ・ｋ＋１を目標ビットとしたToffoli演算と、量子ビットＱｘｉ・ｋ，Ｑｙｉ・ｋを制御ビットとし、量子ビットＱｘｉ・ｋ＋１を目標ビットとしたToffoli演算とを、それぞれ実行する過程と、を実行する演算であり、上記MAJ演算は、第３量子ビットを制御ビットとし、第２量子ビットを目標ビットとしたCNOT演算を行う第１過程と、第３量子ビットを制御ビットとし、第１量子ビットを目標ビットとしたCNOT演算を行う第２過程と、上記第１過程及び上記第２過程の後に行われる、第１量子ビット及び第２量子ビットを制御ビットとし、第３量子ビットを目標ビットとしたToffoli演算を行うMAJ第３過程と、を実行する演算である。
【００１８】
また、量子ビットＱｘｋ−１，…，Ｑｘ０と量子ビットＱｙｋ−１，…，Ｑｙ０とに対する上記SUM演算は、例えば、量子ビットＱｙｋ−１を制御ビットとし、量子ビットＱｘｗを目標ビットとしたCNOT演算と、量子ビットＱｙｋ−１を制御ビットとし、量子ビットＱｙｗを目標ビットとしたCNOT演算とを、それぞれ、０≦ｗ≦ｋ−２（ｗは整数）について実行する過程と、量子ビットＱｘｗを第１量子ビットとし、量子ビットＱｙｗを第２量子ビットとし、量子ビットＱｙｋ−１を第３量子ビットとしたMAJ演算を、それぞれ、ｗをｗ＝０から１ずつ増加させてｗ＝ｋ−２まで実行する過程と、量子ビットＱｘｗを制御ビットとし、量子ビットＱｙｗを目標ビットとしたCNOT演算を、それぞれ、０≦ｗ≦ｋ−１（ｗは整数）について実行する過程と、を実行する演算である。また、量子ビットＱｘ（ｉ＋１）・ｋ−１，…，Ｑｘｉ・ｋと量子ビットＱｙ（ｉ＋１）・ｋ−１，…，Ｑｙｉ・ｋと補助量子ビットＱｚｉ−１，１とに対する上記繰上げSUM演算〔１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）〕は、例えば、量子ビットＱｙ（ｉ＋１）・ｋ−１を制御ビットとし、量子ビットＱｘｉ・ｋ＋ｗを目標ビットとしたCNOT演算と、量子ビットＱｙ（ｉ＋１）・ｋ−１を制御ビットとし、量子ビットＱｙｉ・ｋ＋ｗを目標ビットとしたCNOT演算とを、それぞれ、０≦ｗ≦ｋ−２（ｗは整数）について実行する過程と、補助量子ビットＱｚｉ−１，１を制御ビットとし、量子ビットＱｙ（ｉ＋１）・ｋ−１を目標ビットとしてCNOT演算を実行する過程と、ｋ≧３である場合にのみ行われる、量子ビットＱｘｉ・ｋ＋ｗを第１量子ビットとし、量子ビットＱｙｉ・ｋ＋ｗを第２量子ビットとし、量子ビットＱｙ（ｉ＋１）・ｋ−１を第３量子ビットとしたMAJ演算と、量子ビットＱｘｉ・ｋ＋ｗ，Ｑｙｉ・ｋ＋ｗを制御ビットとし、補助量子ビットＱｚｉ−１，１を目標ビットとしたToffoli演算とを、それぞれ、ｗをｗ＝０から１ずつ増加させてｗ＝ｋ−３まで実行する過程と、量子ビットＱｘ（ｉ＋１）・ｋ−２を第１量子ビットとし、量子ビットＱｙ（ｉ＋１）・ｋ−２を第２量子ビットとし、量子ビットＱｙ（ｉ＋１）・ｋ−１を第３量子ビットとしたMAJ演算を実行する過程と、ｋ≧３である場合にのみ行われる、補助量子ビットＱｚｉ−１，１を制御ビットとし、量子ビットＱｘｉ・ｋ＋ｗを目標ビットとしたCNOT演算と、量子ビットＱｘｉ・ｋ＋ｗ−１，Ｑｙｉ・ｋ＋ｗ−１を制御ビットとし、補助量子ビットＱｚｉ−１，１を目標ビットとしたToffoli演算とを、それぞれ、ｗをｗ＝ｋ−２から１ずつ減少させてｗ＝１まで実行する過程と、
補助量子ビットＱｚｉ−１，１を制御ビットとし、量子ビットＱｘｉ・ｋを目標ビットとしたCNOT演算を実行する過程と、量子ビットＱｘｉ・ｋ＋ｗを制御ビットとし、量子ビットＱｙｉ・ｋ＋ｗを目標ビットとしたCNOT演算を、それぞれ、０≦ｗ≦ｋ−１（ｗは整数）について実行する過程と、を実行する演算を実行する過程と、を実行する演算である。
【００１９】
また、本発明において好ましくは、定数ｋは、ｌｏｇ２（ｌｏｇ２ｎ）以下の最大の整数である。
【００２０】
この場合、本発明の演算に必要となる補助量子ビットの数はＯ（ｎ／ｌｏｇ２ｎ）となる。なお、定数ｋ＝Ｏ（ｌｏｇ２ｎ）である限り、本発明の演算に必要となる補助量子ビットの数はＯ（ｎ／ｌｏｇ２ｎ）となることがいえる。
【発明の効果】
【００２１】
以上のように、本発明では、加算処理ブロック単位で繰上げ値を求め、補助量子ビットを用いて当該加算処理ブロック単位の繰上げ処理及び加算値の最上位ビット値の算出を行い、加算処理ブロック単位で加算処理を行うとした。そのため、１ビット毎に加算処理及び繰上げ処理を行う従来方法に比べ、繰上げ処理に必要な補助量子ビット数を削減できる。その結果、従来よりも少ない数の補助量子ビットで量子加算演算が可能となる。
【発明を実施するための最良の形態】
【００２２】
以下、本発明を実施するための最良の形態を図面を参照して説明する。
【００２３】
＜構成＞
図１は、本形態の量子加算演算装置１の構成を例示した図である。
【００２４】
本発明の量子加算演算装置は、２つの２進数ａ＝ａｎ−１…ａ０〔ａｐ∈｛０，１｝，ｐ∈｛０，…，ｎ−１｝，ｎ≧４〕及びｂ＝ｂｎ−１…ｂ０〔ｂｐ∈｛０，１｝〕に対し、ａ＋ｂ＝ｓｎ…ｓ０〔ｓｑ∈｛０，１｝，ｑ∈｛０，…，ｎ｝〕を算出する。図１では、その一例としてｎ＝８の場合の量子加算演算装置１の構成を例示する。
【００２５】
図１に例示するように、量子加算演算装置１は、非演算子及び演算結果の情報を保持させる量子ビット１０と、補助ビットとして使用される量子ビットである複数の補助量子ビット２０と、量子ビット１０及び補助量子ビット２０にHIGHBIT演算を施すHIGHBIT演算部３０と、HIGHBIT演算部３０の逆演算を行うHIGHBIT-REV演算部４０と、量子ビット１０及び補助量子ビット２０にCNOT演算を施すCNOT演算部５０と、量子ビット１０にNOT演算を施すNOT演算部６０と、量子ビット１０及び補助量子ビット２０にk-Toffoli演算を施すk-Toffoli演算部７０と、2-Toffoli演算を施すToffoli演算部8０と、量子ビット１０にSUM演算を施すSUM演算部９０と、量子ビット１０及び補助量子ビット２０に繰上げSUM演算を施す繰上げSUM演算部１００と、制御部１１０とを具備する。
【００２６】
ここで、量子ビット１０は、初期量子状態がそれぞれ｜ａ０＞，…，｜ａｎ−１＞であるｎ個の量子ビットＱｘ０，…，Ｑｘｎ−１と、初期量子状態がそれぞれ｜ｂ０＞，…，｜ｂｎ−１＞であるｎ個の量子ビットＱｙ０，…，Ｑｙｎ−１とによって構成される（図１の例では、ｎ＝８）。また、量子ビット１０は加算処理単位である加算処理単位ブロック１１毎に分類される。本形態の場合、量子ビットＱｘ（ｉ＋１）・ｋ−１，…，Ｑｘｉ・ｋと量子ビットＱｙ（ｉ＋１）・ｋ−１，…，Ｑｙｉ・ｋとをｉ番目〔０≦ｉ≦（ｎ／ｋ）−１（ｉは整数）〕の加算処理ブロックＡｉとする。なお、この例のｋはｎを割り切る２以上ｎ未満の整数の定数であり、ｋ＝Ｏ（ｌｏｇ２ｎ）を満たす。一例として、ｌｏｇ２（ｌｏｇ２ｎ）以下の最大の整数を定数ｋとする。図１の例はｋ＝２とした場合の例である。
【００２７】
また、補助量子ビット２０は、初期量子状態が｜０＞である１個の補助量子ビットＱｚ０，１と、初期量子状態がそれぞれ｜０＞である２・｛（ｎ／ｋ）−１｝個の補助量子ビットＱｚ１，１，Ｑｚ１，２，Ｑｚ２，１，Ｑｚ２，２，…，Ｑｚ（ｎ／ｋ）−１，１，Ｑｚ（ｎ／ｋ）−１，２と、初期量子状態がそれぞれ｜０＞である
【数３０】
2008269012.tif 000014
個の補助量子ビットＱｚ（ｎ／ｋ），…，Ｑｚ（ｎ／ｋ）＋ｍ−１とを有する（図１の例では、ｎ＝８）。また、これら以外にもk-Toffoli演算を行う場合等に補助量子ビットが必要となるが、本形態の量子回路全体として使用する補助量子ビットの数はＯ（ｎ／ｌｏｇ２ｎ）となる（詳細は後述する）。
【００２８】
また、本形態の量子回路はNOT演算とCNOT演算とToffoli演算とを基本演算とし、各演算は、これらの組み合わせによって実現される。なお、これらの基本演算、HIGHBIT演算、k-Toffoli演算、SUM演算及び繰上げSUM演算の詳細については後述する。また、量子加算演算装置１のハードウェア構成例については後述する。
【００２９】
＜処理＞
次に、本形態の量子加算演算装置１の処理について説明する。
【００３０】
図２〜９は、本形態の量子加算演算装置１の処理内容を示す量子回路の例示である。
【００３１】
ここで、図２は本形態の演算の前段の量子操作を示す量子回路であり、図３は図２の量子操作の後に行われる後段の量子操作を示す量子回路である。また、図２，３は、８ビット同士（ｎ＝８）の加算演算を行う場合の例である。
【００３２】
また、図４，５は、本形態のHIGHBIT演算を例示した量子回路である。ここで、図４（ａ）はHIGHBIT演算のステージ１を示し、図４（ｂ）はHIGHBIT演算のステージ２を示し、図５はHIGHBIT演算のステージ３を示す。すなわち、図４（ａ），図４（ｂ），図５という順序で量子操作が行われる。なお、図４，５はｋ＝５，ｉ＝０の場合のHIGHBIT演算を例示している。
【００３３】
また、図６は、本形態のSUM演算を例示した量子回路である。ここで、図６（ａ）はSUM演算のステージ１を示し、図４（ｂ）はSUM演算のステージ２を示す。すなわち、図６（ａ），図６（ｂ）という順序で量子操作が行われる。なお、図６はｋ＝５の場合のSUM演算を例示している。
【００３４】
また、図７，８は、本形態の繰上げSUM演算を例示した量子回路である。ここで、図７（ａ）は繰上げSUM演算のステージ１を示し、図７（ｂ）は繰上げSUM演算のステージ２を示し、図８は繰上げSUM演算のステージ３を示す。すなわち、図７（ａ），図７（ｂ），図８という順序で量子操作が行われる。なお、図７，８はｋ＝５，ｉ＝１の場合の繰上げSUM演算を例示している。
【００３５】
また、図９（ａ）はNOT演算を示す量子回路であり、図９（ｂ）はCNOT演算を示す量子回路であり、図９（ｃ）はToffoli演算（2-Toffoli演算）を示す量子回路であり、図９（ｄ）はMAJ演算を示す量子回路である。
【００３６】
また、図１０〜１６は、本形態の量子加算演算装置１の処理内容を示すフローチャートの例示である。ここで、図１０，１１は、本形態の演算の前段の量子操作を説明するためのフローチャートであり、図１２は、本形態の演算の後段の量子操作（補助量子ビット初期化）を説明するためのフローチャートである。また、図１３，１４は、本形態のHIGHBIT演算の詳細を説明するためのフローチャートであり、図１５は、本形態のSUM演算の詳細を説明するためのフローチャートであり、図１６は、本形態の繰上げSUM演算の詳細を説明するためのフローチャートである。
【００３７】
なお、図２，１０，１１に例示する前段の量子操作のみで加算結果は得られる。よって、図３，１２に例示する後段の量子操作は必須ではない。しかし、図３，１２に例示する後段の量子操作を行うことにより、演算結果と無関係な補助量子ビット２０（Ｑｚ０，１，Ｑｚ１，１，Ｑｚ１，２，Ｑｚ２，１，Ｑｚ２，２，…，Ｑｚ（ｎ／ｋ）−１，２，Ｑｚ（ｎ／ｋ），…，Ｑｚ（ｎ／ｋ）＋ｍ−１）を初期量子状態｜０＞に戻すことができる。その結果、当該演算結果と無関係な補助量子ビット２０を別の演算の補助ビットとして再利用できる。本形態では、当該後段の量子操作をも行う処理を説明する。
【００３８】
［処理の全体（図２，３，１０〜１２）］
まず、本形態の処理の全体を説明する。なお、本形態の各処理は、制御部１１０の制御のもと実行される。
【００３９】
まず、HIGHBIT演算部３０が、加算処理ブロックＡｉに属する初期量子状態の量子ビットＱｘ（ｉ＋１）・ｋ−１，…，Ｑｘｉ・ｋ及び量子ビットＱｙ（ｉ＋１）・ｋ−１，…，Ｑｙｉ・ｋと、初期量子状態の補助量子ビットＱｚｉ，１とに対してHIGHBIT演算を施し、量子ビットＱｘ（ｉ＋１）・ｋ−１，…，Ｑｘｉ・ｋの量子状態をそれぞれ｜ａ（ｉ＋１）・ｋ−１＞，…，｜ａｉ・ｋ＞とし、量子ビットＱｙ（ｉ＋１）・ｋ−１，…，Ｑｙｉ・ｋの量子状態をそれぞれ｜ｂ（ｉ＋１）・ｋ−１＞，…，｜ｂｉ・ｋ＞とし、補助量子ビットＱｚｉ，１の量子状態を｜ｃｉ＞〔ｃｉは、２つの２進数ａ（ｉ＋１）・ｋ−１…ａｉ・ｋとｂ（ｉ＋１）・ｋ−１…ｂｉ・ｋの和を２進表記した場合の最上位ビット値〕とする処理を、各加算処理ブロックＡｉ〔０≦ｉ≦（ｎ／ｋ）−１（ｉは整数）〕についてそれぞれ実行する（ステップＳ１／HIGHBIT演算過程）。なお、ステップＳ１内の処理の順序には限定はない。すなわち、ステップＳ１の処理は、０≦ｉ≦（ｎ／ｋ）−１の各ｉについてｉを１ずつ増加又は減少させながら順次実行されてもよいし、０≦ｉ≦（ｎ／ｋ）−１の各ｉについて同時（並列）に実行されてもよい。
【００４０】
次に、CNOT演算部５０、k-Toffoli演算部７０及びToffoli演算部８０（「繰上げ値演算部」を構成）が、補助量子ビットＱｚ０，１，Ｑｚ１，１，Ｑｚ１，２，Ｑｚ２，１，Ｑｚ２，２，…，Ｑｚ（ｎ／ｋ）−１，１，Ｑｚ（ｎ／ｋ）−１，２，Ｑｚ（ｎ／ｋ），…，Ｑｚ（ｎ／ｋ）＋ｍ−１を用い、補助量子ビットＱｚｗ，１の量子状態を｜ｄｗ＞〔ｄｗ∈｛０，１｝は、加算処理ブロックＡｗから加算処理ブロックＡｗ＋１への繰上げ値〕とする処理を、０≦ｗ≦（ｎ／ｋ）−２（ｗは整数）についてそれぞれ実行し、さらに補助量子ビットＱｚ（ｎ／ｋ）−１，１の量子状態を｜ｓｎ＞とする処理を実行する（ステップＳ２〜９／繰上げ値演算過程）。
【００４１】
繰上げ値演算過程では、まず、CNOT演算部５０が、量子ビットＱｘｉ・ｋ+ｊを制御ビットとし、量子ビットＱｙｉ・ｋ+ｊを目標ビットとしたCNOT演算を０≦ｊ≦ｋ−１（ｊは整数）についてそれぞれ実行する処理を、１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）についてそれぞれ実行する（ステップＳ２／第１のCNOT演算過程）。なお、ステップＳ２内の処理の順序には限定はない。すなわち、ステップＳ２の処理は、０≦ｊ≦ｋ−１（ｊは整数）及び１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）を満たす全てのｉ，ｊの組み合わせについて同時（並列）に実行されもよいし、各ｉ，ｊの組み合わせ毎に順次実行されてもよい。一例として、ｊをｊ＝０から１ずつ増加させながらｊ＝ｋ−１までステップＳ２のCNOT演算を施す処理を、ｉをｉ＝１から１ずつ増加させながらｉ＝（ｎ／ｋ）−１まで実行する方法を例示できる。
【００４２】
次に、k-Toffoli演算部７０が、ｋ個の量子ビットＱｙｉ・ｋ，…，Ｑｙｉ・ｋ＋ｋ−１を制御ビットとし、補助量子ビットＱｚｉ，２を目標ビットとしたk-Toffoli演算を、１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）についてそれぞれ実行する（ステップＳ３／第１のk-Toffoli演算過程）。なお、ステップＳ３内の処理の順序に限定はなく、各ｉについて同時（並列）に実行されてもよいし、各ｉについて順次実行されてもよい。一例として、ステップＳ３のk-Toffoli演算を施す処理を、ｉをｉ＝１から１ずつ増加させながらｉ＝（ｎ／ｋ）−１まで実行する方法を例示できる。
【００４３】
次に、Toffoli演算部８０が、ステップＳ３によるk-Toffoli演算が施された補助量子ビットＱｚｉ，２を補助量子ビットＱｐＬ−１（ｉ）と表現した場合における、補助量子ビットＱｐｔ−１（２ｉ），Ｑｐｔ−１（２ｉ＋１）を制御ビットとし、補助量子ビットＱｚ（ｎ／ｋ），…，Ｑｚ（ｎ／ｋ）＋ｍ−１うちの１つの補助量子ビットである補助量子ビットＱｐｔ（ｉ）を目標ビットとしたToffoli演算を、目標ビットを重複させることなく、ｉ＝１からｉを１ずつ増加させながら
【数３１】
2008269012.tif 000015
まで実行する処理を、ｔ＝Ｌからｔを１ずつ増加させながら
【数３２】
2008269012.tif 000016
まで実行する（ステップＳ４／第１のToffoli演算過程）。
【００４４】
次に、Toffoli演算部８０が、ステップＳ１による処理が施された補助量子ビットＱｚｉ，１を補助量子ビットＱｇＬ−１（ｉ）と表現した場合における、補助量子ビットＱｇｔ−１（２ｉ），Ｑｐｔ−１（２ｉ＋１）を制御ビットとし、補助量子ビットＱｇｔ−１（２ｉ＋１）を目標ビットとしたToffoli演算〔当該Toffoli演算後の補助量子ビットＱｇｔ−１（２ｉ＋１）を補助量子ビットＱｇｔ（ｉ）と表現〕を、ｉ＝０からｉを１ずつ増加させながら
【数３３】
2008269012.tif 000017
まで実行する処理を、ｔ＝Ｌからｔを１ずつ増加させながら
【数３４】
2008269012.tif 000018
まで実行する（ステップＳ５／第２のToffoli演算過程）。
【００４５】
次に、Toffoli演算部８０が、ｕ＝２ｔ・ｉ／ｋ−１とした場合における補助量子ビットＱｚｕ，１，Ｑｐｔ−１（２ｉ）を制御ビットとし、補助量子ビットＱｇｔ−１（２ｉ）を目標ビットとしたToffoli演算を、ｉ＝１からｉを１ずつ増加させながら
【数３５】
2008269012.tif 000019
まで実行する処理を、
【数３６】
2008269012.tif 000020
からｔを１ずつ減少させながらｔ＝Ｌまで実行する（ステップＳ６／第３のToffoli演算過程）。
【００４６】
次に、Toffoli演算部８０がステップＳ４の処理を逆の順序で実行する（ステップＳ４の処理の逆演算を実行する）。すなわち、Toffoli演算部８０が、補助量子ビットＱｐｔ−１（２ｉ），Ｑｐｔ−１（２ｉ＋１）を制御ビットとし、補助量子ビットＱｐｔ（ｉ）を目標ビットとしたToffoli演算を、
【数３７】
2008269012.tif 000021
からｉを１ずつ減少させながらｉ＝１まで実行する処理を、
【数３８】
2008269012.tif 000022
からｔを１ずつ減少させながらｔ＝Ｌまで実行する（ステップＳ７／第４のToffoli演算過程）。
【００４７】
次に、ステップＳ２，３の処理を逆の順序で実行する（ステップＳ２，３によってなされる演算の逆演算を実行する）。すなわち、まず、k-Toffoli演算部７０が、ｋ個の量子ビットＱｙｉ・ｋ，…，Ｑｙｉ・ｋ＋ｋ−１を制御ビットとし、補助量子ビットＱｚｉ，２を目標ビットとしたk-Toffoli演算を、１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）についてそれぞれ実行する（ステップＳ８／第２のk-Toffoli演算過程）。次に、CNOT演算部５０が、量子ビットＱｘｉ・ｋ+ｊを制御ビットとし、量子ビットＱｙｉ・ｋ+ｊを目標ビットとしたCNOT演算を０≦ｊ≦ｋ−１（ｊは整数）についてそれぞれ実行する処理を、１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）についてそれぞれ実行する（ステップＳ９／第２のCNOT演算過程／繰上げ値演算過程終了）。
【００４８】
次に、SUM演算部９０が、加算処理ブロックＡ０に属する量子ビットＱｘｋ−１，…，Ｑｘ０と量子ビットＱｙｋ−１，…，Ｑｙ０とに対してSUM演算を施し、量子ビットＱｘｋ−１，…，Ｑｘ０の量子状態をそれぞれ｜ａｋ−１＞，…，｜ａ０＞とし、量子ビットＱｙｋ−１，…，Ｑｙ０の量子状態をそれぞれ｜ｓｋ−１＞，…，｜ｓ０＞とする（ステップＳ１０／第１のSUM演算過程）。
【００４９】
また、繰上げSUM演算部１００が、加算処理ブロックＡｉに属する量子ビットＱｘ（ｉ＋１）・ｋ−１，…，Ｑｘｉ・ｋ及び量子ビットＱｙ（ｉ＋１）・ｋ−１，…，Ｑｙｉ・ｋと、補助量子ビットＱｚｉ−１，１とに対して繰上げSUM演算を施し、量子ビットＱｘ（ｉ＋１）・ｋ−１，…，Ｑｘｉ・ｋの量子状態をそれぞれ｜ａ（ｉ＋１）・ｋ−１＞，…，｜ａｉ・ｋ＞とし、量子ビットＱｙ（ｉ＋１）・ｋ−１，…，Ｑｙｉ・ｋの量子状態をそれぞれ｜ｓ（ｉ＋１）・ｋ−１＞，…，｜ｓｉ・ｋ＞とし、補助量子ビットＱｚｉ−１，１の量子状態を維持する処理を、１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）についてそれぞれ実行する（ステップＳ１１／第２のSUM演算過程）。
【００５０】
ここまでが前段の処理である。ここまでの処理によって、ｎ個の量子ビットＱｘ０，…，Ｑｘｎ−１の量子状態がそれぞれ｜ａ０＞，…，｜ａｎ−１＞となり、量子ビットＱｙ０，…，Ｑｙｎ−１の量子状態がそれぞれ｜ｓ０＞，…，｜ｓｎ−１＞となり、補助量子ビットＱｚ（ｎ／ｋ）−１，１の量子状態が｜ｓｎ＞となる。すなわち、量子ビットＱｘ０，…，Ｑｘｎ−１と補助量子ビットＱｚ（ｎ／ｋ）−１，１を観測することによって加算演算結果ａ＋ｂ＝ｓｎ…ｓ０を得ることができる。
【００５１】
この後、後段の処理によって、この演算結果と無関係な補助量子ビットＱｚ０，１，Ｑｚ１，１，Ｑｚ１，２，Ｑｚ２，１，Ｑｚ２，２，…，Ｑｚ（ｎ／ｋ）−１，２，Ｑｚ（ｎ／ｋ），…，Ｑｚ（ｎ／ｋ）＋ｍ−１の量子状態を初期量子状態｜０＞に戻す。
【００５２】
まず、NOT演算部６０が、量子ビットＱｙ（ｉ＋１）・ｋ−１，…，Ｑｙｉ・ｋに対してNOT演算を施す処理を0≦ｉ≦（ｎ／ｋ）−２（ｉは整数）についてそれぞれ実行する（ステップＳ２１／第１のNOT演算過程）。なお、ステップＳ２１内の処理の順序に限定はない。すなわち、ステップＳ２１の処理は、0≦ｉ≦（ｎ／ｋ）−２に属するｉについて同時（並列）に実行されてもよく、ｉ毎に順次実行されてもよい（例えばｉを０から１ずつ増加させながらｉ＝（ｎ／ｋ）−２まで順次実行）。
【００５３】
次に、CNOT演算部５０とk-Toffoli演算部７０とToffoli演算部８０と（「逆演算部」を構成）が、上記繰上げ値演算過程が具備する、補助量子ビットＱｚｗ，１の量子状態を｜ｄｗ＞とする処理の逆演算を、０≦ｗ≦（ｎ／ｋ）−２（ｗは整数）についてそれぞれ実行し、さらに、HIGHBIT-REV演算部４０（「逆演算部」を構成）が、量子ビットＱｘ（ｗ＋１）・ｋ−１，…，Ｑｘｗ・ｋと量子ビットＱｙ（ｗ＋１）・ｋ−１，…，Ｑｙｗ・ｋと補助量子ビットＱｚｗ，１とに対する上記HIGHBIT演算の逆演算であるHIGHBIT-REV演算を０≦ｗ≦（ｎ／ｋ）−２（ｗは整数）についてそれぞれ実行する（逆演算過程）。
【００５４】
すなわち、ｎをｎ−ｋとおいた場合における、上記のHIGHBIT演算過程（ステップＳ１）、第１のCNOT演算過程（ステップＳ２）、第１のk-Toffoli演算過程（ステップＳ３）、第１のToffoli演算過程（ステップＳ４）、第２のToffoli演算過程（ステップＳ５）、第３のToffoli演算過程（ステップＳ６）、第４のToffoli演算過程（ステップＳ７）、第２のk-Toffoli演算過程（ステップＳ８）及び第２のCNOT演算過程（ステップＳ９）によって順次行われる処理からなる演算の逆演算を実行し（ステップＳ２２）、量子ビットＱｘ０，…，Ｑｘｎ−ｋ−１の量子状態をそれぞれ｜ａ０＞，…，｜ａｎ−ｋ−１＞とし、量子ビットＱｙ０，…，Ｑｙｎ−ｋ−１の量子状態をそれぞれ｜ｓ０＞，…，｜ｓｎ−ｋ−１＞の反転状態とし、補助量子ビットＱｚ０，１の量子状態を｜０＞とし、補助量子ビットＱｚ１，１，Ｑｚ１，２，Ｑｚ２，１，Ｑｚ２，２，…，Ｑｚ（ｎ／ｋ）−２，１，Ｑｚ（ｎ／ｋ）−２，２の量子状態をそれぞれ｜０＞にする。つまり、ステップＳ２２では、ｎをｎ−ｋとおいた場合における、第２のCNOT演算過程（ステップＳ９）を逆の順序で実行し、第２のk-Toffoli演算過程（ステップＳ８）を逆の順序で実行し、第４のToffoli演算過程（ステップＳ７）を逆の順序で実行し、・・・、HIGHBIT演算過程（ステップＳ１）を逆の順序で実行する処理を行う。なお、量子状態｜α＞の反転状態とは、量子状態｜α(+)1＞を意味する。なお、(+)は排他的論理和演算子
【数３９】
2008269012.tif 000023
を示す。
【００５５】
次に、CNOT演算部５０が、量子ビットＱｙ（ｉ＋１）・ｋ−１，…，Ｑｙｉ・ｋに対してNOT演算を施す処理を０≦ｉ≦（ｎ／ｋ）−２（ｉは整数）についてそれぞれ実行する（ステップＳ２３／第２のNOT演算過程）。なお、ステップＳ２３内の処理の順序に限定はない。
【００５６】
＜演算内容の詳細＞
次に、本形態で用いた各演算内容の詳細について説明する。
【００５７】
［基本演算］
まず、NOT演算、CNOT演算、Toffoli演算及びMAJ演算について説明する。
【００５８】
図９（ａ）に示すように、NOT演算は、量子状態｜ｘ＞の量子ビットＱαを、量子状態｜ｘ(+)1＞の量子ビットＱαにする操作である。
【００５９】
また、図９（ｂ）に示すように、量子状態｜ｘ＞の量子ビットＱαを制御ビットとし、量子状態｜ｙ＞の量子ビットＱβを目標ビットビットとするCNOT演算は、量子状態｜ｘ＞の量子ビットＱα及び量子状態｜ｙ＞の量子ビットＱβを、量子状態｜ｘ＞の量子ビットＱα及び量子状態｜x(+)ｙ＞の量子ビットＱβにする操作である。
【００６０】
また、図９（ｃ）に示すように、量子状態｜ｘ＞の量子ビットＱαと量子状態｜ｙ＞の量子ビットＱβとを制御ビットとし、量子状態｜ｚ＞の量子ビットＱγを目標ビットビットとするToffoli演算は、量子状態｜ｘ＞の量子ビットＱαと量子状態｜ｙ＞の量子ビットＱβと量子状態｜ｚ＞の量子ビットＱγとを、量子状態｜ｘ＞の量子ビットＱαと量子状態｜ｙ＞の量子ビットＱβと量子状態｜ｚ(+)xy＞の量子ビットＱγにする操作である。なお、量子状態｜ｘ１＞の量子ビットＱα（１），...，量子状態｜ｘｋ＞の量子ビットＱα（ｋ）を制御ビットとし、量子状態｜ｚ＞の量子ビットＱγを目標ビットビットとするk-Toffoli演算は、量子状態｜ｘ１＞の量子ビットＱα（１），...，量子状態｜ｘｋ＞の量子ビットＱα（ｋ）と量子状態｜ｚ＞の量子ビットＱγとを、量子状態｜ｘ１＞の量子ビットＱα（１），...，量子状態｜ｘｋ＞の量子ビットＱα（ｋ）と量子状態｜ｚ(+)ｘ１・... ・ｘｋ＞の量子ビットＱγにする操作である。
【００６１】
また、図９（ｄ）に示すように、MAJ演算は、第３量子ビットＱγを制御ビットとし、第２量子ビットＱβを目標ビットとしたCNOT演算を行う第１過程と、第３量子ビットＱγを制御ビットとし、第１量子ビットＱαを目標ビットとしたCNOT演算を行う第２過程と、上記第１過程及び上記第２過程の後に行われる、第１量子ビットＱα及び第２量子ビットＱβを制御ビットとし、第３量子ビットＱγを目標ビットとしたToffoli演算を行うMAJ第３過程と、を実行する演算である。これにより、量子状態｜ｘ＞の第１量子ビットＱαと量子状態｜ｙ＞の第２量子ビットＱβと量子状態｜ｚ＞の第３量子ビットＱγとを、量子状態｜ｘ(+)ｚ＞の第１量子ビットＱαと量子状態｜ｙ(+)ｚ＞の第２量子ビットＱβと量子状態｜xy(+)yz(+)zx＞の第３量子ビットＱγにする。
【００６２】
［HIGHBIT演算（図４（ａ）（ｂ），５，１３，１４）］
次に、量子ビットＱｘ（ｉ＋１）・ｋ−１，…，Ｑｘｉ・ｋと量子ビットＱｙ（ｉ＋１）・ｋ−１，…，Ｑｙｉ・ｋと補助量子ビットＱｚｉ，１とに対するHIGHBIT演算について説明する。
【００６３】
HIGHBIT演算では、まず、量子ビットＱｘｉ・ｋ，Ｑｙｉ・ｋを制御ビットとし、補助量子ビットＱｚｉ，１を目標ビットとするToffoli演算を行う（ステップＳ３１）。
【００６４】
次に、ｋ≧３である場合にのみ（ステップＳ３２）、量子ビットＱｘｉ・ｋ＋ｗを第１量子ビットとし、量子ビットＱｙｉ・ｋ＋ｗを第２量子ビットとし、補助量子ビットＱｚｉ，１を第３量子ビットとしたMAJ演算と、量子ビットＱｘｉ・ｋ＋ｗ，Ｑｙｉ・ｋ＋ｗを制御ビットとし、量子ビットＱｘｉ・ｋを目標ビットとしたToffoli演算とを、それぞれ、ｗをｗ＝１から１ずつ増加させてｗ＝ｋ−２まで実行し（ステップＳ３３）、ステップＳ３４に進む。なお、ｋ＜３の場合には、ステップＳ３３を実行することなくステップＳ３４に進む。
【００６５】
ステップＳ３４では、量子ビットＱｘ（ｉ＋１）・ｋ−１を第１量子ビットとし、量子ビットＱｙ（ｉ＋１）・ｋ−１を第２量子ビットとし、補助量子ビットＱｚｉ，１を第３量子ビットとしたMAJ演算を実行する（ステップＳ３４）。
【００６６】
次に、ｋ≧３である場合にのみ（ステップＳ３５）、量子ビットＱｘｉ・ｋを制御ビットとし、量子ビットＱｙｉ・ｋ＋ｗを目標ビットとしたCNOT演算と、量子ビットＱｘｉ・ｋを制御ビットとし、量子ビットＱｘｉ・ｋ＋ｗを目標ビットとしたCNOT演算と、量子ビットＱｘｉ・ｋ＋ｗ−１，Ｑｙｉ・ｋ＋ｗ−１を制御ビットとし、量子ビットＱｘｉ・ｋを目標ビットとしたToffoli演算とを、それぞれ、ｗをｗ＝ｋ−１から１ずつ減少させてｗ＝２まで実行し（ステップＳ３６）、ステップＳ３７に進む。なお、ｋ＜３の場合には、ステップＳ３６を実行することなくステップＳ３７に進む。
【００６７】
ステップＳ３７では、量子ビットＱｙｉ・ｋにNOT演算を施す（ステップＳ３７）。
【００６８】
次に、ｋ≧３である場合にのみ（ステップＳ３８）、量子ビットＱｘｉ・ｋ，Ｑｙｉ・ｋを制御ビットとし、量子ビットＱｙｉ・ｋ＋ｗを目標ビットとしたToffoli演算と、量子ビットＱｘｉ・ｋ，Ｑｙｉ・ｋを制御ビットとし、量子ビットＱｘｉ・ｋ＋ｗを目標ビットとしたToffoli演算とを、それぞれ、２≦ｗ≦ｋ−１（ｗは整数）について実行する（ステップＳ３９）。なお、ｋ＜３の場合には、ステップＳ３９を実行することなくステップＳ４０に進む。
【００６９】
ステップＳ４０では、量子ビットＱｙｉ・ｋにNOT演算を施す（ステップＳ４０）。
【００７０】
次に、量子ビットＱｘｉ・ｋ，Ｑｙｉ・ｋを制御ビットとし、量子ビットＱｙｉ・ｋ＋１を目標ビットとしたToffoli演算と、量子ビットＱｘｉ・ｋ，Ｑｙｉ・ｋを制御ビットとし、量子ビットＱｘｉ・ｋ＋１を目標ビットとしたToffoli演算とを、それぞれ実行する過程と、を実行する（ステップＳ４１）。
【００７１】
［SUM演算（図６（ａ）（ｂ），１５）］
次に、量子ビットＱｘｋ−１，…，Ｑｘ０と量子ビットＱｙｋ−１，…，Ｑｙ０とに対するSUM演算について説明する。
【００７２】
SUM演算では、まず、量子ビットＱｙｋ−１を制御ビットとし、量子ビットＱｘｗを目標ビットとしたCNOT演算と、量子ビットＱｙｋ−１を制御ビットとし、量子ビットＱｙｗを目標ビットとしたCNOT演算とを、それぞれ、０≦ｗ≦ｋ−２（ｗは整数）について実行する（ステップＳ５１）。次に、量子ビットＱｘｗを第１量子ビットとし、量子ビットＱｙｗを第２量子ビットとし、量子ビットＱｙｋ−１を第３量子ビットとしたMAJ演算を、それぞれ、ｗをｗ＝０から１ずつ増加させてｗ＝ｋ−２まで実行する（ステップＳ５２）。次に、量子ビットＱｘｗを制御ビットとし、量子ビットＱｙｗを目標ビットとしたCNOT演算を、それぞれ、０≦ｗ≦ｋ−１（ｗは整数）について実行する（ステップＳ５３）。
【００７３】
なお、ｋの値によっては、ステップＳ５１〜Ｓ５３の処理の一部が互いに相殺する場合がある。このような場合には相殺し合う処理を実行しなくてもよい。例えば、図２のｋ＝２の例では、MAJ演算が有する２つのCNOT演算とステップＳ５１のCNOT演算とが相殺されている。
【００７４】
［繰上げSUM演算（図７（ａ）（ｂ），８，１６）］
次に、量子ビットＱｘ（ｉ＋１）・ｋ−１，…，Ｑｘｉ・ｋと量子ビットＱｙ（ｉ＋１）・ｋ−１，…，Ｑｙｉ・ｋと補助量子ビットＱｚｉ−１，１とに対する繰上げSUM演算〔１≦ｉ≦（ｎ／ｋ）−１（ｉは整数）〕について説明する。
【００７５】
繰上げSUM演算では、まず、量子ビットＱｙ（ｉ＋１）・ｋ−１を制御ビットとし、量子ビットＱｘｉ・ｋ＋ｗを目標ビットとしたCNOT演算と、量子ビットＱｙ（ｉ＋１）・ｋ−１を制御ビットとし、量子ビットＱｙｉ・ｋ＋ｗを目標ビットとしたCNOT演算とを、それぞれ、０≦ｗ≦ｋ−２（ｗは整数）について実行する（ステップＳ６１）。
【００７６】
次に、補助量子ビットＱｚｉ−１，１を制御ビットとし、量子ビットＱｙ（ｉ＋１）・ｋ−１を目標ビットとしてCNOT演算を実行する（ステップＳ６２）。
【００７７】
次に、ｋ≧３である場合にのみ（ステップＳ６３）、量子ビットＱｘｉ・ｋ＋ｗを第１量子ビットとし、量子ビットＱｙｉ・ｋ＋ｗを第２量子ビットとし、量子ビットＱｙ（ｉ＋１）・ｋ−１を第３量子ビットとしたMAJ演算と、量子ビットＱｘｉ・ｋ＋ｗ，Ｑｙｉ・ｋ＋ｗを制御ビットとし、補助量子ビットＱｚｉ−１，１を目標ビットとしたToffoli演算とを、それぞれ、ｗをｗ＝０から１ずつ増加させてｗ＝ｋ−３まで実行し（ステップＳ６４）、ステップＳ６５に進む。なお、ｋ＜３の場合には、ステップＳ６４を実行することなくステップＳ６５に進む。
【００７８】
ステップＳ６５では、量子ビットＱｘ（ｉ＋１）・ｋ−２を第１量子ビットとし、量子ビットＱｙ（ｉ＋１）・ｋ−２を第２量子ビットとし、量子ビットＱｙ（ｉ＋１）・ｋ−１を第３量子ビットとしたMAJ演算を実行する（ステップＳ６５）。
【００７９】
次に、ｋ≧３である場合にのみ（ステップＳ６６）、補助量子ビットＱｚｉ−１，１を制御ビットとし、量子ビットＱｘｉ・ｋ＋ｗを目標ビットとしたCNOT演算と、量子ビットＱｘｉ・ｋ＋ｗ−１，Ｑｙｉ・ｋ＋ｗ−１を制御ビットとし、補助量子ビットＱｚｉ−１，１を目標ビットとしたToffoli演算とを、それぞれ、ｗをｗ＝ｋ−２から１ずつ減少させてｗ＝１まで実行し（ステップＳ６７）、ステップＳ６８に進む。なお、ｋ＜３の場合には、ステップＳ６７を実行することなくステップＳ６８に進む。
【００８０】
ステップＳ６８では、補助量子ビットＱｚｉ−１，１を制御ビットとし、量子ビットＱｘｉ・ｋを目標ビットとしたCNOT演算を実行する（ステップＳ６８）。次に、量子ビットＱｘｉ・ｋ＋ｗを制御ビットとし、量子ビットＱｙｉ・ｋ＋ｗを目標ビットとしたCNOT演算を、それぞれ、０≦ｗ≦ｋ−１（ｗは整数）について実行する（ステップＳ６９）。
【００８１】
＜ハードウェア構成＞
次に本形態の量子加算演算装置１のハードウェア構成を例示する。
【００８２】
本形態の量子加算演算装置１は、量子コンピュータ或いは量子コンピュータと古典コンユータとの組合せで実現できる。量子コンピュータを実現する物理系としては、例えば、イオントラップを用いる方法（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)、http://www.snf.unsw.edu.au/、Y.Nakamura, Yu. A. Pashkin and J.S.Tsai, Nature 398(1999)768）。
【００８８】
［CNOT演算］
イオントラップ量子コンピュータでは、例えば、イオンを直線上に並べ、各イオンに狙いを定めたレーザービーム照射によってCNOT演算を実現する。また、量子ビットとして光子の偏光を用いる場合には、例えば、偏光ビームスプリッタ等を用い、「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. 方式によってCNOT演算を実現する。また、核スピンを量子ビットとして用いる場合には、例えば、所定の電磁波パルスを量子ビットに印加することによってCNOT演算を実現できる。
【００８９】
その他、上記の文献に記載された方法でCNOT演算を実現してもよい。
【００９０】
［Toffoli演算］
Toffoli演算は、CNOT演算と量子ビット単体へのユニタリ変換との組み合わせによって実現できる。なお、この演算にも補助ビットとなる量子ビットが必要となる。k-Toffoli演算についても同様である。
【００９１】
［量子ビット単体の操作（NOT演算，ユニタリ変換）］
イオントラップ量子コンピュータでは、例えば、イオンを直線上に並べ、各イオンに狙いを定めたレーザービーム照射によって量子ビット単体の操作を実現する。核スピンを量子ビットとして用いる場合には、電磁波パルスやレーザービーム照射によって各処理を実現する。また、量子ビットとして光子の偏光を用いる場合には、例えば、偏光回転素子等によって実現する。
【００９２】
＜本形態の特徴＞
以上のように、本形態では、量子ビット毎に加算処置と繰上げ処理とを行うのではなく、複数の量子ビットからなる加算処理ブロック単位で加算処理と繰上げ処理とを行う。その結果、繰上げ処理に必要となる補助量子ビット数を削減できる。具体的には、Ｏ（ｎ／ｌｏｇ２ｎ）個の補助量子ビットを用い、Ｏ（ｎ）個の基本演算をＯ（ｌｏｇ２ｎ）個の計算ステップで実行することにより、２進ｎ桁の加算演算を行うことができる。以下に、本形態の処理でＯ（ｎ／ｌｏｇ２ｎ）個の補助量子ビットしか使用されないことを示す。
【００９３】
まず、図１１，１２のフローチャートの各ステップで必要な補助量子ビットの数をオーダーで示す（すなわち、補助量子ビットの数を表現する多項式の係数部分までは言及しない）。
【００９４】
［ステップＳ１］
各ｉのHIGHBIT演算において補助量子ビットを１個ずつ使用するため、全体としてＯ（ｎ／ｋ）個の補助量子ビットを用いる。
【００９５】
［ステップＳ２，３］
各k-Toffoli演算がそれぞれ１個の補助量子ビットを使用するため、全体としてＯ（ｎ／ｋ）個の補助量子ビットを用いる（なお、正確には、各k-Toffoli演算は基本演算と１つの補助量子ビットによって実現されるため、全体としてk-Toffoli演算数の２倍の補助量子ビットを用いることになるが、オーダーの評価ではＯ（ｎ／ｋ）個と示して問題ない）。
【００９６】
［ステップＳ４］
各Toffoli演算が１個の補助量子ビットを用いるため、全体として
【数４０】
2008269012.tif 000024
個の補助量子ビットを用いる。
【００９７】
［ステップＳ５以降］
新たに補助量子ビットを必要としない。
ここで、ｋ＝Ｏ（ｌｏｇ２ｎ）であるから、Ｏ（ｎ／ｋ）＝Ｏ（ｎ／ｌｏｇ２ｎ）である。また、Ｌの定め方からＬ＝Ｏ｛ｌｏｇ２（ｌｏｇ２ｎ）｝である。これを用いて式（１）を展開するとＯ（ｎ／ｌｏｇ２ｎ）となる。したがって、上記の各ステップで必要となる補助量子ビットの数の合計はＯ（ｎ／ｌｏｇ２ｎ）個となる。
【００９８】
なお、本発明は上述の実施の形態に限定されるものではない。例えば、各量子ビットの初期量子状態が、複数の量子状態が重ね合わされたものであってもよい。また、SUM演算の説明で例示したように、相殺し合う処理を省略してもよい。また、前述のようにステップＳ２１〜Ｓ２３の処理を実行しない構成であってもよい。さらに、上述の各種の処理は、上述した記載に従って実行されるのみならず、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【産業上の利用可能性】
【００９９】
本発明の産業上の利用分野としては、例えば、量子コンピュータ等を例示できる。
【図面の簡単な説明】
【０１００】
【図１】図１は、本形態の量子加算演算装置の構成を例示した図である。
【図２】図２は本形態の演算の前段の量子操作を示す量子回路である。
【図３】図３は図２の量子操作の後に行われる後段の量子操作を示す量子回路である。
【図４】図４は、本形態のHIGHBIT演算を例示した量子回路である。
【図５】図５は、本形態のHIGHBIT演算を例示した量子回路である。
【図６】図６は、本形態のSUM演算を例示した量子回路である。
【図７】図７は、本形態の繰上げSUM演算を例示した量子回路である。
【図８】図８は、本形態の繰上げSUM演算を例示した量子回路である。
【図９】図９（ａ）はNOT演算を示す量子回路であり、図９（ｂ）はCNOT演算を示す量子回路であり、図９（ｃ）はToffoli演算（2-Toffoli演算）を示す量子回路であり、図９（ｄ）はMAJ演算を示す量子回路である。
【図１０】図１０は、本形態の演算の前段の量子操作を説明するためのフローチャートである。
【図１１】図１１は、本形態の演算の前段の量子操作を説明するためのフローチャートである。
【図１２】図１２は、本形態の演算の後段の量子操作（補助量子ビット初期化）を説明するためのフローチャートである。
【図１３】図１３は、本形態のHIGHBIT演算の詳細を説明するためのフローチャートである。
【図１４】図１４は、本形態のHIGHBIT演算の詳細を説明するためのフローチャートである。
【図１５】図１５は、本形態のSUM演算の詳細を説明するためのフローチャートである。
【図１６】図１６は、本形態の繰上げSUM演算の詳細を説明するためのフローチャートである。
【図１７】図１７は、非特許文献１に記載された加算演算用の量子回路の例示である。
【図１８】図１８は、非特許文献１に記載された加算演算用の量子回路の例示である。
【符号の説明】
【０１０１】
１  量子加算演算装置
１０  量子ビット
２０  補助量子ビット
【図１】
2008269012.tif 000043
【図２】
2008269012.tif 000044
【図３】
2008269012.tif 000045
【図４】
2008269012.tif 000046
【図５】
2008269012.tif 000047
【図６】
2008269012.tif 000048
【図７】
2008269012.tif 000049
【図８】
2008269012.tif 000050
【図９】
2008269012.tif 000051
【図１０】
2008269012.tif 000052
【図１１】
2008269012.tif 000053
【図１２】
2008269012.tif 000054
【図１３】
2008269012.tif 000055
【図１４】
2008269012.tif 000056
【図１５】
2008269012.tif 000057
【図１６】
2008269012.tif 000058
【図１７】
2008269012.tif 000059
【図１８】
2008269012.tif 000060