(57)【要約】【課題】補助キュービットを使うことなく、従来よりも効率的な量子演算技術を提供する。【解決手段】２つの２進数ａ＝ａn-1…ａ0及びｂ＝ｂn-1…ｂ0と、０または１のｚとに対し、ａ＋ｂ＝ｓn…ｓ0と、ｚ（＋XOR）ｓnとを算出する量子演算であって、ｎ個のキュービットＢiと、ｎ＋１個のキュービットＡjを演算対象とし、キュービットＢiの初期状態を|ｂi〉とし、キュービットＡiの初期状態を|ａi〉とし、キュービットＡｎの初期状態を|ｚ〉として、キャリービットｃiが初期状態|ａi〉を与えられたキュービットＡiに蓄えられる。これは、ＭＡＪゲートを二つの制御ＮＯＴゲートを含む前段部と一つのToffoliゲートを含む後段部に分けて、ＭＡＪゲートの作用を複合的に利用することで達成される。【選択図】図５
2010218513.tif 000002
【特許請求の範囲】
【請求項１】
２つの２進数ａ＝ａn-1…ａ0〔ａi∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝〕及びｂ＝ｂn-1…ｂ0〔ｂi∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝〕と、０または１のｚ〔ｚ∈｛０，１｝〕とに対し、ａ＋ｂ＝ｓn…ｓ0〔ｓj∈｛０，１｝，ｊ∈｛０，…，ｎ｝〕と、ｚ（＋XOR）ｓn〔（＋XOR）は２を法とする加算を表す。〕とを算出する量子演算装置であって、
ｎを１以上の整数とし、ｎ個のキュービットＢi（ｉ∈｛０，…，ｎ−１｝）と、ｎ＋１個のキュービットＡj（ｊ∈｛０，…，ｎ｝）を演算対象とし、キュービットＢiの初期状態を|ｂi〉とし（ｉ∈｛０，…，ｎ−１｝）、キュービットＡiの初期状態を|ａi〉とし（ｉ∈｛０，…，ｎ−１｝）、キュービットＡｎの初期状態を|ｚ〉として、
ｎが２以上の整数である場合には、ｐ＝１，・・・，ｎ−１について、キュービットＡpを制御キュービットとし、キュービットＢpを標的キュービットとして、キュービットＢpとキュービットＡpに対する制御ＮＯＴ演算を行う量子演算部と、
ｎが２以上の整数である場合には、ｐ＝ｎ−１，・・・，１について、順に、キュービットＡpを制御キュービットとし、キュービットＡp+1を標的キュービットとして、キュービットＡpとキュービットＡp+1に対する制御ＮＯＴ演算を行う量子演算部と、
ｐ＝０，・・・，ｎ−１について、順に、キュービットＢpおよびキュービットＡpを制御キュービットとし、キュービットＡp+1を標的キュービットとして、キュービットＢpとキュービットＡpとキュービットＡp+1に対するToffoli演算を行う量子演算部と、
ｎが２以上の整数である場合には、ｐ＝ｎ−１，・・・，１について、順に、キュービットＡpを制御キュービットとし、キュービットＢpを標的キュービットとして、キュービットＢpとキュービットＡpに対する制御ＮＯＴ演算を行い、さらに、キュービットＢp-1およびキュービットＡp-1を制御キュービットとし、キュービットＡpを標的キュービットとして、キュービットＢp-1とキュービットＡp-1とキュービットＡpに対するToffoli演算を行う量子演算部と、
ｎが３以上の整数である場合には、ｐ＝１，・・・，ｎ−２について、順に、キュービットＡpを制御キュービットとし、キュービットＡp+1を標的キュービットとして、キュービットＡpとキュービットＡp+1に対する制御ＮＯＴ演算を行う量子演算部と、
ｐ＝０，・・・，ｎ−１について、キュービットＡpを制御キュービットとし、キュービットＢpを標的キュービットとして、キュービットＢpとキュービットＡpに対する制御ＮＯＴ演算を行う量子演算部と
を含む量子演算装置。
【請求項２】
２つの２進数ａ＝ａn-1…ａ0〔ａi∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝〕及びｂ＝ｂn-1…ｂ0〔ｂi∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝〕と、０または１のｚ〔ｚ∈｛０，１｝〕とに対し、ａ−ｂ＝ｓn-1…ｓ0〔ｓi∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝〕とその符号ｓn〔ｓn∈｛０，１｝〕とを算出する量子演算装置であって、
ｎを１以上の整数とし、ｎ個のキュービットＢi（ｉ∈｛０，…，ｎ−１｝）と、ｎ＋１個のキュービットＡj（ｊ∈｛０，…，ｎ｝）を演算対象とし、キュービットＢiの初期状態を|ｂi〉とし（ｉ∈｛０，…，ｎ−１｝）、キュービットＡiの初期状態を|ａi〉とし（ｉ∈｛０，…，ｎ−１｝）、キュービットＡｎの初期状態を|ｚ〉として、
ｐ＝０，・・・，ｎ−１について、キュービットＡpに対するＮＯＴ演算を行う量子演算部と、
ｎが２以上の整数である場合には、ｐ＝１，・・・，ｎ−１について、キュービットＡpを制御キュービットとし、キュービットＢpを標的キュービットとして、キュービットＢpとキュービットＡpに対する制御ＮＯＴ演算を行う量子演算部と、
ｎが２以上の整数である場合には、ｐ＝ｎ−１，・・・，１について、順に、キュービットＡpを制御キュービットとし、キュービットＡp+1を標的キュービットとして、キュービットＡpとキュービットＡp+1に対する制御ＮＯＴ演算を行う量子演算部と、
ｐ＝０，・・・，ｎ−１について、順に、キュービットＢpおよびキュービットＡpを制御キュービットとし、キュービットＡp+1を標的キュービットとして、キュービットＢpとキュービットＡpとキュービットＡp+1に対するToffoli演算を行う量子演算部と、
ｎが２以上の整数である場合には、ｐ＝ｎ−１，・・・，１について、順に、キュービットＡpを制御キュービットとし、キュービットＢpを標的キュービットとして、キュービットＢpとキュービットＡpに対する制御ＮＯＴ演算を行い、さらに、キュービットＢp-1およびキュービットＡp-1を制御キュービットとし、キュービットＡpを標的キュービットとして、キュービットＢp-1とキュービットＡp-1とキュービットＡpに対するToffoli演算を行う量子演算部と、
ｎが３以上の整数である場合には、ｐ＝１，・・・，ｎ−２について、順に、キュービットＡpを制御キュービットとし、キュービットＡp+1を標的キュービットとして、キュービットＡpとキュービットＡp+1に対する制御ＮＯＴ演算を行う量子演算部と、
ｐ＝０，・・・，ｎ−１について、キュービットＡpを制御キュービットとし、キュービットＢpを標的キュービットとして、キュービットＢpとキュービットＡpに対する制御ＮＯＴ演算を行う量子演算部と、
ｐ＝０，・・・，ｎとｒ＝０，・・・，ｎ−１について、キュービットＢrに対するＮＯＴ演算とキュービットＡpに対するＮＯＴ演算を行う量子演算部と
を含む量子演算装置。
【請求項３】
２つの２進数ａ＝ａn-1…ａ0〔ａi∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝〕及びｂ＝ｂn-1…ｂ0〔ｂi∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝〕と、０または１のｚ〔ｚ∈｛０，１｝〕とに対し、ａ−ｂの符号ｙを算出する量子演算装置であって、
ｎを１以上の整数とし、ｎ個のキュービットＢi（ｉ∈｛０，…，ｎ−１｝）と、ｎ＋１個のキュービットＡj（ｊ∈｛０，…，ｎ｝）を演算対象とし、キュービットＢiの初期状態を|ｂi〉とし（ｉ∈｛０，…，ｎ−１｝）、キュービットＡiの初期状態を|ａi〉とし（ｉ∈｛０，…，ｎ−１｝）、キュービットＡｎの初期状態を|ｚ〉として、
ｐ＝０，・・・，ｎ−１について、キュービットＡpに対するＮＯＴ演算を行う量子演算部と、
ｎが２以上の整数である場合には、ｐ＝１，・・・，ｎ−１について、キュービットＡpを制御キュービットとし、キュービットＢpを標的キュービットとして、キュービットＢpとキュービットＡpに対する制御ＮＯＴ演算を行う量子演算部と、
ｎが２以上の整数である場合には、ｐ＝ｎ−１，・・・，１について、順に、キュービットＡpを制御キュービットとし、キュービットＡp+1を標的キュービットとして、キュービットＡpとキュービットＡp+1に対する制御ＮＯＴ演算を行う量子演算部と、
ｐ＝０，・・・，ｎ−１について、順に、キュービットＢpおよびキュービットＡpを制御キュービットとし、キュービットＡp+1を標的キュービットとして、キュービットＢpとキュービットＡpとキュービットＡp+1に対するToffoli演算を行う量子演算部と、
ｎが２以上の整数である場合には、ｐ＝ｎ−１，・・・，１について、順に、キュービットＢp-1およびキュービットＡp-1を制御キュービットとし、キュービットＡpを標的キュービットとして、キュービットＢp-1とキュービットＡp-1とキュービットＡpに対するToffoli演算を行う量子演算部と、
ｎが３以上の整数である場合には、ｐ＝１，・・・，ｎ−２について、順に、キュービットＡpを制御キュービットとし、キュービットＡp+1を標的キュービットとして、キュービットＡpとキュービットＡp+1に対する制御ＮＯＴ演算を行う量子演算部と、
ｐ＝１，・・・，ｎ−１について、キュービットＡpを制御キュービットとし、キュービットＢpを標的キュービットとして、キュービットＢpとキュービットＡpに対する制御ＮＯＴ演算を行う量子演算部と、
ｐ＝０，・・・，ｎについて、キュービットＡpに対するＮＯＴ演算を行う量子演算部と
を含む量子演算装置。
【請求項４】
２つの２進数ａ＝ａn-1…ａ0〔ａi∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝〕及びｂ＝ｂn-1…ｂ0〔ｂi∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝〕と、０または１のｚ〔ｚ∈｛０，１｝〕とに対し、ａ＋ｂ＝ｓn…ｓ0〔ｓj∈｛０，１｝，ｊ∈｛０，…，ｎ｝〕と、ｚ（＋XOR）ｓn〔（＋XOR）は２を法とする加算を表す。〕とを算出する量子演算方法であって、
ｎが１以上の整数とし、ｎ個のキュービットＢi（ｉ∈｛０，…，ｎ−１｝）と、ｎ＋１個のキュービットＡj（ｊ∈｛０，…，ｎ｝）を演算対象とし、キュービットＢiの初期状態を|ｂi〉とし（ｉ∈｛０，…，ｎ−１｝）、キュービットＡiの初期状態を|ａi〉とし（ｉ∈｛０，…，ｎ−１｝）、キュービットＡｎの初期状態を|ｚ〉として、
ｎが２以上の整数である場合には、ｐ＝１，・・・，ｎ−１について、キュービットＡpを制御キュービットとし、キュービットＢpを標的キュービットとして、キュービットＢpとキュービットＡpに対する制御ＮＯＴ演算を行う第１量子演算ステップと、
ｎが２以上の整数である場合には、第１量子演算ステップに続いて、ｐ＝ｎ−１，・・・，１について、順に、キュービットＡpを制御キュービットとし、キュービットＡp+1を標的キュービットとして、キュービットＡpとキュービットＡp+1に対する制御ＮＯＴ演算を行う第２量子演算ステップと、
第２量子演算ステップに続いて、ｐ＝０，・・・，ｎ−１について、順に、キュービットＢpおよびキュービットＡpを制御キュービットとし、キュービットＡp+1を標的キュービットとして、キュービットＢpとキュービットＡpとキュービットＡp+1に対するToffoli演算を行う第３量子演算ステップと、
ｎが２以上の整数である場合には、第３量子演算ステップに続いて、ｐ＝ｎ−１，・・・，１について、順に、キュービットＡpを制御キュービットとし、キュービットＢpを標的キュービットとして、キュービットＢpとキュービットＡpに対する制御ＮＯＴ演算を行い、さらに、キュービットＢp-1およびキュービットＡp-1を制御キュービットとし、キュービットＡpを標的キュービットとして、キュービットＢp-1とキュービットＡp-1とキュービットＡpに対するToffoli演算を行う第４量子演算ステップと、
ｎが３以上の整数である場合には、第４量子演算ステップに続いて、ｐ＝１，・・・，ｎ−２について、順に、キュービットＡpを制御キュービットとし、キュービットＡp+1を標的キュービットとして、キュービットＡpとキュービットＡp+1に対する制御ＮＯＴ演算を行う第５量子演算ステップと、
第５量子演算ステップに続いて、ｐ＝０，・・・，ｎ−１について、キュービットＡpを制御キュービットとし、キュービットＢpを標的キュービットとして、キュービットＢpとキュービットＡpに対する制御ＮＯＴ演算を行う第６量子演算ステップと
を含む量子演算方法。
【請求項５】
２つの２進数ａ＝ａn-1…ａ0〔ａi∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝〕及びｂ＝ｂn-1…ｂ0〔ｂi∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝〕と、０または１のｚ〔ｚ∈｛０，１｝〕とに対し、ａ−ｂ＝ｓn-1…ｓ0〔ｓi∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝〕とその符号ｓn〔ｓn∈｛０，１｝〕とを算出する量子演算方法であって、
ｎを１以上の整数とし、ｎ個のキュービットＢi（ｉ∈｛０，…，ｎ−１｝）と、ｎ＋１個のキュービットＡj（ｊ∈｛０，…，ｎ｝）を演算対象とし、キュービットＢiの初期状態を|ｂi〉とし（ｉ∈｛０，…，ｎ−１｝）、キュービットＡiの初期状態を|ａi〉とし（ｉ∈｛０，…，ｎ−１｝）、キュービットＡｎの初期状態を|ｚ〉として、
ｐ＝０，・・・，ｎ−１について、キュービットＡpに対するＮＯＴ演算を行う第０量子演算ステップと、
ｎが２以上の整数である場合には、第０量子演算ステップに続いて、ｐ＝１，・・・，ｎ−１について、キュービットＡpを制御キュービットとし、キュービットＢpを標的キュービットとして、キュービットＢpとキュービットＡpに対する制御ＮＯＴ演算を行う第１量子演算ステップと、
ｎが２以上の整数である場合には、第１量子演算ステップに続いて、ｐ＝ｎ−１，・・・，１について、順に、キュービットＡpを制御キュービットとし、キュービットＡp+1を標的キュービットとして、キュービットＡpとキュービットＡp+1に対する制御ＮＯＴ演算を行う第２量子演算ステップと、
第２量子演算ステップに続いて、ｐ＝０，・・・，ｎ−１について、順に、キュービットＢpおよびキュービットＡpを制御キュービットとし、キュービットＡp+1を標的キュービットとして、キュービットＢpとキュービットＡpとキュービットＡp+1に対するToffoli演算を行う第３量子演算ステップと、
ｎが２以上の整数である場合には、第３量子演算ステップに続いて、ｐ＝ｎ−１，・・・，１について、順に、キュービットＡpを制御キュービットとし、キュービットＢpを標的キュービットとして、キュービットＢpとキュービットＡpに対する制御ＮＯＴ演算を行い、さらに、キュービットＢp-1およびキュービットＡp-1を制御キュービットとし、キュービットＡpを標的キュービットとして、キュービットＢp-1とキュービットＡp-1とキュービットＡpに対するToffoli演算を行う第４量子演算ステップと、
ｎが３以上の整数である場合には、第４量子演算ステップに続いて、ｐ＝１，・・・，ｎ−２について、順に、キュービットＡpを制御キュービットとし、キュービットＡp+1を標的キュービットとして、キュービットＡpとキュービットＡp+1に対する制御ＮＯＴ演算を行う第５量子演算ステップと、
第５量子演算ステップに続いて、ｐ＝０，・・・，ｎ−１について、キュービットＡpを制御キュービットとし、キュービットＢpを標的キュービットとして、キュービットＢpとキュービットＡpに対する制御ＮＯＴ演算を行う第６量子演算ステップと、
第６量子演算ステップに続いて、ｐ＝０，・・・，ｎとｒ＝０，・・・，ｎ−１について、キュービットＢrに対するＮＯＴ演算とキュービットＡpに対するＮＯＴ演算を行う第７量子演算ステップと
を含む量子演算方法。
【請求項６】
２つの２進数ａ＝ａn-1…ａ0〔ａi∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝〕及びｂ＝ｂn-1…ｂ0〔ｂi∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝〕と、０または１のｚ〔ｚ∈｛０，１｝〕とに対し、ａ−ｂの符号ｙを算出する量子演算方法であって、
ｎを１以上の整数とし、ｎ個のキュービットＢi（ｉ∈｛０，…，ｎ−１｝）と、ｎ＋１個のキュービットＡj（ｊ∈｛０，…，ｎ｝）を演算対象とし、キュービットＢiの初期状態を|ｂi〉とし（ｉ∈｛０，…，ｎ−１｝）、キュービットＡiの初期状態を|ａi〉とし（ｉ∈｛０，…，ｎ−１｝）、キュービットＡｎの初期状態を|ｚ〉として、
ｐ＝０，・・・，ｎ−１について、キュービットＡpに対するＮＯＴ演算を行う第０量子演算ステップと、
ｎが２以上の整数である場合には、第０量子演算ステップに続いて、ｐ＝１，・・・，ｎ−１について、キュービットＡpを制御キュービットとし、キュービットＢpを標的キュービットとして、キュービットＢpとキュービットＡpに対する制御ＮＯＴ演算を行う第１量子演算ステップと、
ｎが２以上の整数である場合には、第１量子演算ステップに続いて、ｐ＝ｎ−１，・・・，１について、順に、キュービットＡpを制御キュービットとし、キュービットＡp+1を標的キュービットとして、キュービットＡpとキュービットＡp+1に対する制御ＮＯＴ演算を行う第２量子演算ステップと、
第２量子演算ステップに続いて、ｐ＝０，・・・，ｎ−１について、順に、キュービットＢpおよびキュービットＡpを制御キュービットとし、キュービットＡp+1を標的キュービットとして、キュービットＢpとキュービットＡpとキュービットＡp+1に対するToffoli演算を行う第３量子演算ステップと、
ｎが２以上の整数である場合には、第３量子演算ステップに続いて、ｐ＝ｎ−１，・・・，１について、順に、キュービットＢp-1およびキュービットＡp-1を制御キュービットとし、キュービットＡpを標的キュービットとして、キュービットＢp-1とキュービットＡp-1とキュービットＡpに対するToffoli演算を行う第４量子演算ステップと、
ｎが３以上の整数である場合には、第４量子演算ステップに続いて、ｐ＝１，・・・，ｎ−２について、順に、キュービットＡpを制御キュービットとし、キュービットＡp+1を標的キュービットとして、キュービットＡpとキュービットＡp+1に対する制御ＮＯＴ演算を行う第５量子演算ステップと、
第５量子演算ステップに続いて、ｐ＝１，・・・，ｎ−１について、キュービットＡpを制御キュービットとし、キュービットＢpを標的キュービットとして、キュービットＢpとキュービットＡpに対する制御ＮＯＴ演算を行う第６量子演算ステップと、
第６量子演算ステップに続いて、ｐ＝０，・・・，ｎについて、キュービットＡpに対するＮＯＴ演算を行う第７量子演算ステップと
を含む量子演算方法。
【請求項７】
２つの２進数ａ＝ａn-1…ａ0〔ａi∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝〕及びｂ＝ｂn-1…ｂ0〔ｂi∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝〕と、０または１のｚ〔ｚ∈｛０，１｝〕とに対し、ａ＋ｂ＝ｓn…ｓ0〔ｓj∈｛０，１｝，ｊ∈｛０，…，ｎ｝〕と、ｚ（＋XOR）ｓn〔（＋XOR）は２を法とする加算を表す。〕とを算出する量子回路であって、
ｎを１以上の整数とし、ｎ個のキュービットＢi（ｉ∈｛０，…，ｎ−１｝）と、ｎ＋１個のキュービットＡj（ｊ∈｛０，…，ｎ｝）を演算対象とし、キュービットＢiの初期状態を|ｂi〉とし（ｉ∈｛０，…，ｎ−１｝）、キュービットＡiの初期状態を|ａi〉とし（ｉ∈｛０，…，ｎ−１｝）、キュービットＡｎの初期状態を|ｚ〉として、
ｎが２以上の整数である場合には、ｐ＝１，・・・，ｎ−１について、キュービットＡpを制御キュービットとし、キュービットＢpを標的キュービットとして、キュービットＢpとキュービットＡpに対して制御ＮＯＴゲートを適用する量子回路と、
ｎが２以上の整数である場合には、ｐ＝ｎ−１，・・・，１について、順に、キュービットＡpを制御キュービットとし、キュービットＡp+1を標的キュービットとして、キュービットＡpとキュービットＡp+1に対して制御ＮＯＴゲートを適用する量子回路と、
ｐ＝０，・・・，ｎ−１について、順に、キュービットＢpおよびキュービットＡpを制御キュービットとし、キュービットＡp+1を標的キュービットとして、キュービットＢpとキュービットＡpとキュービットＡp+1に対してToffoliゲートを適用する量子回路と、
ｎが２以上の整数である場合には、ｐ＝ｎ−１，・・・，１について、順に、キュービットＡpを制御キュービットとし、キュービットＢpを標的キュービットとして、キュービットＢpとキュービットＡpに対して制御ＮＯＴゲートを適用し、さらに、キュービットＢp-1およびキュービットＡp-1を制御キュービットとし、キュービットＡpを標的キュービットとして、キュービットＢp-1とキュービットＡp-1とキュービットＡpに対してToffoliゲートを適用する量子回路と、
ｎが３以上の整数である場合には、ｐ＝１，・・・，ｎ−２について、順に、キュービットＡpを制御キュービットとし、キュービットＡp+1を標的キュービットとして、キュービットＡpとキュービットＡp+1に対して制御ＮＯＴゲートを適用する量子回路と、
ｐ＝０，・・・，ｎ−１について、キュービットＡpを制御キュービットとし、キュービットＢpを標的キュービットとして、キュービットＢpとキュービットＡpに対して制御ＮＯＴゲートを適用する量子回路と
から構成された量子回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、量子演算方法、量子演算装置、量子回路に関する。より詳しくは、加算、減算、比較に係る量子回路、並びにこの量子回路に則った量子演算方法、量子演算装置に関する。
【背景技術】
【０００２】
近年、量子コンピュータのための種々の量子回路が検討されている。特に、１９９４年に因数分解問題や離散対数問題を効率的に解く量子コンピュータ上のアルゴリズム（Shorのアルゴリズム）が提案されたことを契機に、効率的な量子回路の研究が盛んに行われている。その一つに加算のための量子回路（以下、量子加算回路と云う。）がある。効率的な量子加算回路は、Shorのアルゴリズムを効率的に実行する観点からも有用である。
【０００３】
量子回路は、［１］非巡回的であること、［２］ファンイン（FANIN）の禁止、［３］ファンアウト（FANOUT）の禁止、［４］量子ゲートがユニタリー性を持つことなど、古典回路と異なる制約を受けるため、所定の条件を満足する量子回路を構成することは一般的に容易ではない。このような制約の下で量子加算回路を構成する場合に、ファンアウト（FANOUT）の禁止を受けて、補助キュービット（ancillary qubit）を用いる量子加算回路が提案されている（非特許文献１参照）。また、補助キュービットを用いない量子加算回路も提案されている（非特許文献２参照）。ここで量子加算は、ｎビット（ｎ＝１，２，・・・）の２つの２進数ａ＝ａn-1…ａ0及びｂ＝ｂn-1…ｂ0と、０または１のｚとが入力として与えられたとき、ａ＋ｂ＝ｓn…ｓ0を計算し、ｚ（＋XOR）ｓnとｓn-1…ｓ0とａとを出力する演算であり、式（１）で表される演算である。ただし、（＋XOR）あるいは○と＋との組合せ記号は、２を法とする加算（排他的論理和）を表す。また、式（１）において、○と×との組合せ記号はテンソル積を表す。
【数１】
2010218513.tif 000003
【０００４】
図１−図４を参照して、非特許文献２に開示された量子加算回路を概説する。図１−図４では、ｎ＝５の場合の量子加算回路を例示している。なお、１枚の図面に収まらないため、便宜的に４枚の図面に分けてこの量子加算回路を示している。この量子回路は、図１に示す量子回路から図４に示す量子回路までを順番に接続して得られる。この量子加算回路は、リプルキャリーアプローチ（ripple-carry approach）と呼ばれる手法に基づいた回路構成を持つ。ここで、繰り上がり用のキャリービットｃi（０≦ｉ≦ｎ）を式（２）のように定義する。
【数２】
2010218513.tif 000004
【０００５】
このとき、ｓi（０≦ｉ≦ｎ）はキャリービットｃiを用いて式（３）で与えられる。
【数３】
2010218513.tif 000005
【０００６】
非特許文献２に開示された量子加算回路は、式（１）で表される出力を得るため、式（４）で表されるＭＡＪゲートの作用を利用している。このように、ＭＡＪゲートは状態|ｚ（＋XOR）ｃi〉を状態|ｚ（＋XOR）ｃi+1〉に変更する。なおＭＡＪゲートは、図８に示す量子ゲートである。
【数４】
2010218513.tif 000006
【０００７】
式（４）で表されるＭＡＪゲートの作用を利用するため、まず、図１に示す量子回路では、８個の制御ＮＯＴ（CNOT; controlled NOT）ゲートを使って、１≦ｉ≦ｎ−１について|ｚ（＋XOR）ｂi〉および|ｚ（＋XOR）ａi〉が求められる。制御ＮＯＴゲートは、図９に示す量子ゲートである。
【０００８】
そして、図２に示す量子回路では、|ｂ0〉と|ａ0〉と|ｚ〉に作用する１個の制御制御ＮＯＴゲートと４個のＭＡＪゲートを用いて、１≦ｉ≦ｎ−１について|ｂi（＋XOR）ｃi〉および|ａi（＋XOR）ｃi〉と、|ｚ（＋XOR）ｃ5〉＝|ｚ（＋XOR）ｓ5〉が求められる。制御制御ＮＯＴ（controlled-controlled NOT）ゲートは、図１０に示す量子ゲートである。ｎを１以上の整数とし、Ｕを２×２のユニタリー行列として、２n×２nのユニタリー行列Λn-1Ｕを式（５）のように定め、これをｎ-キュービットの一般Toffoliゲートと呼ぶ。制御制御ＮＯＴゲートは、式（５）で表されるｎ-キュービットの一般Toffoliゲート（general Toffoli gate）の特別な場合である（ｎ＝３；Ｕ＝Ｎ；ＮはＮＯＴ演算を表すユニタリー作用素）。そこで、制御制御ＮＯＴゲートを単にToffoliゲートとも呼ぶ。
【数５】
2010218513.tif 000007
【０００９】
次に、図３に示す量子回路および図４に示す量子回路（但し、図４に示す量子回路の破線枠部を除く。）では、１≦ｉ≦ｎ−１について、状態|ｂi（＋XOR）ｃi〉を変更することなく状態|ａi（＋XOR）ｃi〉が状態|ａi〉に変更される。
【００１０】
そして、図４の破線枠部に示す量子回路では、０≦ｉ≦ｎ−１について、|ａi〉を制御キュービット（control qubit）とし、|ｂi（＋XOR）ｃi〉を標的キュービット（target qubit）として、制御ＮＯＴゲートを適用することによって、式（１）に示す所望の出力が得られる。
【００１１】
なお、量子計算や量子アルゴリズムなどについては、非特許文献３に詳しい。
【先行技術文献】
【非特許文献】
【００１２】
【非特許文献１】S. A. Cuccaro, T. G. Draper, S. A. Kutin and D. P. Moulton, A new quantum ripple-carry addition circuit, The Eighth Workshop on Quantum Information Processing, 2005.
【非特許文献２】Y. Takahashi and N. Kunihiro, A linear-size quantum circuit for addition with no ancillary qubits, Quantum Information and Computation, Vol. 5 No. 6, pp.440-448, 2005.
【非特許文献３】M. A. Nielsen and I. L. Chuang, "Quantum Computation and Quantum Information", Cambridge UniversityPress, 2000.
【発明の概要】
【発明が解決しようとする課題】
【００１３】
量子回路が効率的であるか否かを評価する指標として、入力桁数ｎに対する、その量子回路で使われるキュービット（量子ビットとも云う）の数、基本演算数（サイズ）、計算ステップ数（深さ）が用いられる。キュービットの数は２ｎ＋１よりも小さくすることはできないので、補助キュービットの個数が着目される。基本演算は、１キュービットに対する演算と２キュービットに対する演算であり、基本演算数は量子回路で使われている基本演算の個数である。計算ステップ数は、量子回路で使われている基本演算を並列に行える演算からなるグループに分割したときのグループの個数である。ただし、異なるキュービットに対する演算は並列に行えると仮定する。
【００１４】
一般的には、多数のキュービットを協調的に操作することは物理的に困難であると予想され、補助キュービットの個数はできるだけ少ないことが好ましい。また、基本演算の個数が多いほど演算誤りの発生する可能性が大きくなるため、基本演算数はできるだけ少ないほうがよい。また、少ない計算時間のためには計算ステップ数は少ない方がよい。
【００１５】
非特許文献１に開示される量子加算回路は補助キュービットを一つ用いているが、非特許文献２に開示される量子加算回路は補助キュービットを用いていない。
【００１６】
非特許文献２に開示される量子加算回路は、２個のユニタリーゲートと、６ｎ−６個の制御ＮＯＴゲートと、４ｎ−５個のToffoliゲートを用いて構成されるので、基本演算数は１０ｎ−９である（全ての演算は単一量子ビットに対する１量子ビット演算と制御ＮＯＴ演算に分解できるので（上記非特許文献３参照）、ToffoliゲートによるToffoli演算を基本演算としている。）。また、計算ステップ数は８ｎ−７である。補助キュービットを使わずに、１０ｎ−９個よりも少ない基本演算数を持つ量子加算回路は知られていない。
【００１７】
そこで本発明は、このような実情に鑑みて、補助キュービットを使うことなく、従来よりも効率的な量子演算技術を提供することを目的とする。
【課題を解決するための手段】
【００１８】
本発明では、２つの２進数ａ＝ａn-1…ａ0〔ａi∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝〕及びｂ＝ｂn-1…ｂ0〔ｂi∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝〕と、０または１のｚ〔ｚ∈｛０，１｝〕とに対し、ａ＋ｂ＝ｓn…ｓ0〔ｓj∈｛０，１｝，ｊ∈｛０，…，ｎ｝〕と、ｚ（＋XOR）ｓn〔（＋XOR）は２を法とする加算を表す。〕とを算出する量子演算（量子加算）は、ｎを１以上の整数とし、ｎ個のキュービットＢi（ｉ∈｛０，…，ｎ−１｝）と、ｎ＋１個のキュービットＡj（ｊ∈｛０，…，ｎ｝）を演算対象とし、キュービットＢiの初期状態を|ｂi〉とし（ｉ∈｛０，…，ｎ−１｝）、キュービットＡiの初期状態を|ａi〉とし（ｉ∈｛０，…，ｎ−１｝）、キュービットＡｎの初期状態を|ｚ〉として、次のような演算を行う。即ち、ｎが２以上の整数である場合には、ｐ＝１，・・・，ｎ−１について、キュービットＡpを制御キュービットとし、キュービットＢpを標的キュービットとして、キュービットＢpとキュービットＡpに対する制御ＮＯＴ演算と、ｎが２以上の整数である場合には、ｐ＝ｎ−１，・・・，１について、順に、キュービットＡpを制御キュービットとし、キュービットＡp+1を標的キュービットとして、キュービットＡpとキュービットＡp+1に対する制御ＮＯＴ演算と、ｐ＝０，・・・，ｎ−１について、順に、キュービットＢpおよびキュービットＡpを制御キュービットとし、キュービットＡp+1を標的キュービットとして、キュービットＢpとキュービットＡpとキュービットＡp+1に対するToffoli演算と、ｎが２以上の整数である場合には、ｐ＝ｎ−１，・・・，１について、順に、キュービットＡpを制御キュービットとし、キュービットＢpを標的キュービットとして、キュービットＢpとキュービットＡpに対する制御ＮＯＴ演算を行い、さらに、キュービットＢp-1およびキュービットＡp-1を制御キュービットとし、キュービットＡpを標的キュービットとして、キュービットＢp-1とキュービットＡp-1とキュービットＡpに対するToffoli演算を行う量子演算と、ｎが３以上の整数である場合には、ｐ＝１，・・・，ｎ−２について、順に、キュービットＡpを制御キュービットとし、キュービットＡp+1を標的キュービットとして、キュービットＡpとキュービットＡp+1に対する制御ＮＯＴ演算と、ｐ＝０，・・・，ｎ−１について、キュービットＡpを制御キュービットとし、キュービットＢpを標的キュービットとして、キュービットＢpとキュービットＡpに対する制御ＮＯＴ演算である。
【００１９】
また、本発明では、２つの２進数ａ＝ａn-1…ａ0〔ａi∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝〕及びｂ＝ｂn-1…ｂ0〔ｂi∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝〕と、０または１のｚ〔ｚ∈｛０，１｝〕とに対し、ａ−ｂ＝ｓn-1…ｓ0〔ｓi∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝〕とその符号ｓn〔ｓn∈｛０，１｝〕とを算出する量子演算（量子減算）は、ｎを１以上の整数とし、ｎ個のキュービットＢi（ｉ∈｛０，…，ｎ−１｝）と、ｎ＋１個のキュービットＡj（ｊ∈｛０，…，ｎ｝）を演算対象とし、キュービットＢiの初期状態を|ｂi〉とし（ｉ∈｛０，…，ｎ−１｝）、キュービットＡiの初期状態を|ａi〉とし（ｉ∈｛０，…，ｎ−１｝）、キュービットＡｎの初期状態を|ｚ〉として、次のような演算を行う。即ち、ｐ＝０，・・・，ｎ−１について、キュービットＡpに対するＮＯＴ演算と、ｎが２以上の整数である場合には、ｐ＝１，・・・，ｎ−１について、キュービットＡpを制御キュービットとし、キュービットＢpを標的キュービットとして、キュービットＢpとキュービットＡpに対する制御ＮＯＴ演算と、ｎが２以上の整数である場合には、ｐ＝ｎ−１，・・・，１について、順に、キュービットＡpを制御キュービットとし、キュービットＡp+1を標的キュービットとして、キュービットＡpとキュービットＡp+1に対する制御ＮＯＴ演算と、ｐ＝０，１，・・・，ｎ−１について、順に、キュービットＢpおよびキュービットＡpを制御キュービットとし、キュービットＡp+1を標的キュービットとして、キュービットＢpとキュービットＡpとキュービットＡp+1に対するToffoli演算と、ｎが２以上の整数である場合には、ｐ＝ｎ−１，・・・，１について、順に、キュービットＡpを制御キュービットとし、キュービットＢpを標的キュービットとして、キュービットＢpとキュービットＡpに対する制御ＮＯＴ演算を行い、さらに、キュービットＢp-1およびキュービットＡp-1を制御キュービットとし、キュービットＡpを標的キュービットとして、キュービットＢp-1とキュービットＡp-1とキュービットＡpに対するToffoli演算を行う量子演算と、ｎが３以上の整数である場合には、ｐ＝１，・・・，ｎ−２について、順に、キュービットＡpを制御キュービットとし、キュービットＡp+1を標的キュービットとして、キュービットＡpとキュービットＡp+1に対する制御ＮＯＴ演算と、ｐ＝０，・・・，ｎ−１について、キュービットＡpを制御キュービットとし、キュービットＢpを標的キュービットとして、キュービットＢpとキュービットＡpに対する制御ＮＯＴ演算と、ｐ＝０，・・・，ｎとｒ＝０，・・・，ｎ−１について、キュービットＢrに対するＮＯＴ演算とキュービットＡpに対するＮＯＴ演算を行う量子演算である。
【００２０】
また、本発明では、２つの２進数ａ＝ａn-1…ａ0〔ａi∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝〕及びｂ＝ｂn-1…ｂ0〔ｂi∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝〕と、０または１のｚ〔ｚ∈｛０，１｝〕とに対し、ａ−ｂの符号ｙを算出する量子演算（量子比較演算）は、ｎを１以上の整数とし、ｎ個のキュービットＢi（ｉ∈｛０，…，ｎ−１｝）と、ｎ＋１個のキュービットＡj（ｊ∈｛０，…，ｎ｝）を演算対象とし、キュービットＢiの初期状態を|ｂi〉とし（ｉ∈｛０，…，ｎ−１｝）、キュービットＡiの初期状態を|ａi〉とし（ｉ∈｛０，…，ｎ−１｝）、キュービットＡｎの初期状態を|ｚ〉として、次のような演算を行う。即ち、ｐ＝０，・・・，ｎ−１について、キュービットＡpに対するＮＯＴ演算と、ｎが２以上の整数である場合には、ｐ＝１，・・・，ｎ−１について、キュービットＡpを制御キュービットとし、キュービットＢpを標的キュービットとして、キュービットＢpとキュービットＡpに対する制御ＮＯＴ演算と、ｎが２以上の整数である場合には、ｐ＝ｎ−１，・・・，１について、順に、キュービットＡpを制御キュービットとし、キュービットＡp+1を標的キュービットとして、キュービットＡpとキュービットＡp+1に対する制御ＮＯＴ演算と、ｐ＝０，・・・，ｎ−１について、順に、キュービットＢpおよびキュービットＡpを制御キュービットとし、キュービットＡp+1を標的キュービットとして、キュービットＢpとキュービットＡpとキュービットＡp+1に対するToffoli演算と、ｎが２以上の整数である場合には、ｐ＝ｎ−１，・・・，１について、順に、キュービットＢp-1およびキュービットＡp-1を制御キュービットとし、キュービットＡpを標的キュービットとして、キュービットＢp-1とキュービットＡp-1とキュービットＡpに対するToffoli演算と、ｎが３以上の整数である場合には、ｐ＝１，・・・，ｎ−２について、順に、キュービットＡpを制御キュービットとし、キュービットＡp+1を標的キュービットとして、キュービットＡpとキュービットＡp+1に対する制御ＮＯＴ演算と、ｐ＝１，・・・，ｎ−１について、キュービットＡpを制御キュービットとし、キュービットＢpを標的キュービットとして、キュービットＢpとキュービットＡpに対する制御ＮＯＴ演算と、ｐ＝０，・・・，ｎについて、キュービットＡpに対するＮＯＴ演算である。
【発明の効果】
【００２１】
本発明に拠れば、補助キュービットを使わずに、量子加算が７ｎ−６個の基本演算数と５ｎ−３個の計算ステップ数で実現できる。また、この量子加算を利用して、補助キュービットを使わずに、量子減算が１０ｎ−５個の基本演算数と５ｎ−１個の計算ステップ数で実現できる。また、この量子減算を応用して、補助キュービットを使わずに、量子比較演算が８ｎ−５個の基本演算数と４ｎ個の計算ステップ数で実現できる。これらの演算では、基本演算数が従来よりも少ないから、演算誤りの発生する可能性が低い。
【図面の簡単な説明】
【００２２】
【図１】従来の量子加算回路（ステージ１）。
【図２】従来の量子加算回路（ステージ２）。
【図３】従来の量子加算回路（ステージ３）。
【図４】従来の量子加算回路（ステージ４）。
【図５】本発明の一実施形態である５ビットの量子回路（量子加算）。
【図６】本発明の一実施形態である５ビットの量子回路（量子減算）。
【図７】本発明の一実施形態である５ビットの量子回路（量子比較演算）。
【図８】ＭＡＪゲート。
【図９】制御ＮＯＴゲート。
【図１０】Toffoliゲート。
【図１１】ＳＷＡＰゲートを用いた量子回路の等価変換を示す図。
【図１２】ＳＷＡＰゲート。
【図１３】本発明の一実施形態である５ビットの量子回路（量子加算）における演算処理フロー。
【図１４】本発明の一実施形態である５ビットの量子回路（量子減算）における演算処理フロー。
【図１５】本発明の一実施形態である５ビットの量子回路（量子比較演算）における演算処理フロー。
【発明を実施するための形態】
【００２３】
〔量子加算〕
まず、図５および図１３を参照して、加算のための量子回路１００を説明する。以下、加算のための量子回路１００を量子加算回路１００と呼称する。
【００２４】
既述のとおり、量子加算は、ｎビット（入力桁数ｎ）の２つの２進数ａ＝ａn-1…ａ0〔ａi∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝〕及びｂ＝ｂn-1…ｂ0〔ｂi∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝〕と、０または１のｚ〔ｚ∈｛０，１｝〕とが入力として与えられたとき、ａ＋ｂ＝ｓn…ｓ0〔ｓj∈｛０，１｝，ｊ∈｛０，…，ｎ｝〕を計算し、ｚ（＋XOR）ｓnとｓn-1…ｓ0とａとを出力する演算であり、式（１）で表される演算である。ただし、ｎは１以上の整数である。また、繰り上がり用のキャリービットｃi（０≦ｉ≦ｎ）は式（２）のように定義され、ｓi（０≦ｉ≦ｎ）はキャリービットｃiを用いて式（３）で与えられる。
【００２５】
この演算を行う量子加算回路１００は、ｎ個のキュービットＢi（ｉ∈｛０，…，ｎ−１｝）と、ｎ＋１個のキュービットＡj（ｊ∈｛０，…，ｎ｝）を演算対象とする。キュービットＢiの初期状態は|ｂi〉である（ｉ∈｛０，…，ｎ−１｝）。キュービットＡiの初期状態は|ａi〉である（ｉ∈｛０，…，ｎ−１｝）。キュービットＡｎの初期状態は|ｚ〉である。つまり、量子加算回路１００の入力状態は式（６）で表される。図５では５ビット（ｎ＝５）の量子加算回路１００を例示している。
【数６】
2010218513.tif 000008
【００２６】
量子加算回路１００は、ステージ１からステージ６までの最大６個の量子回路で構成されている。
【００２７】
ｎが２以上の整数である場合、ステージ１の量子回路は、ｐ＝１，・・・，ｎ−１について、キュービットＡpを制御キュービットとし、キュービットＢpを標的キュービットとして、キュービットＢpとキュービットＡpに対して制御ＮＯＴゲートを適用する量子回路である。基本演算は制御ＮＯＴ演算であり、基本演算数はｎ−１である。
第１量子演算部は、これらの制御ＮＯＴ演算を実行する（ステップＳ１）。これらの制御ＮＯＴ演算は並列実行可能であり、計算ステップ数は１である。
ステージ１を経た時点での出力状態は式（７）で表される。
【数７】
2010218513.tif 000009
【００２８】
ｎが１である場合、量子加算回路１００はステージ１の量子回路を持たない。
【００２９】
ｎが２以上の整数である場合、ステージ１に続くステージ２の量子回路は、ｐ＝ｎ−１，・・・，１について、順に、キュービットＡpを制御キュービットとし、キュービットＡp+1を標的キュービットとして、キュービットＡpとキュービットＡp+1に対して制御ＮＯＴゲートを適用する量子回路である。基本演算は制御ＮＯＴ演算であり、基本演算数はｎ−１である。
第２量子演算部は、これらの制御ＮＯＴ演算を実行する（ステップＳ２）。これらの制御ＮＯＴ演算はｐ＝ｎ−１，・・・，１の順番で実行されるため、計算ステップ数はｎ−１である。
ステージ２を経た時点での出力状態は式（８）で表される。
【数８】
2010218513.tif 000010
【００３０】
ｎが１である場合、量子加算回路１００はステージ２の量子回路を持たない。
【００３１】
ステージ２に続くステージ３の量子回路は、ｐ＝０，・・・，ｎ−１について、順に、キュービットＢpおよびキュービットＡpを制御キュービットとし、キュービットＡp+1を標的キュービットとして、キュービットＢpとキュービットＡpとキュービットＡp+1に対してToffoliゲートを適用する量子回路である。基本演算はToffoli演算であり、基本演算数はｎである。
第３量子演算部は、これらのToffoli演算を実行する（ステップＳ３）。これらのToffoli演算はｐ＝０，・・・，ｎ−１の順番で実行されるため、計算ステップ数はｎである。
ステージ３を経た時点での出力状態は式（９）で表される。
【数９】
2010218513.tif 000011
【００３２】
ｎが２以上の整数である場合、ステージ３に続くステージ４の量子回路は、ｐ＝ｎ−１，・・・，１について、順に、キュービットＡpを制御キュービットとし、キュービットＢpを標的キュービットとして、キュービットＢpとキュービットＡpに対して制御ＮＯＴゲートを適用し、さらに、キュービットＢp-1およびキュービットＡp-1を制御キュービットとし、キュービットＡpを標的キュービットとして、キュービットＢp-1とキュービットＡp-1とキュービットＡpに対してToffoliゲートを適用する量子回路である。基本演算は制御ＮＯＴ演算とToffoli演算であり、基本演算数はそれぞれｎ−１であり計２ｎ−２である。
第４量子演算部は、これらの制御ＮＯＴ演算とToffoli演算を実行する（ステップＳ４）。これらの制御ＮＯＴ演算とToffoli演算はｐ＝ｎ−１，・・・，１の順番で実行されるため、計算ステップ数はそれぞれｎ−１であり計２ｎ−２である。
ステージ４を経た時点での出力状態は式（１０）で表される。
【数１０】
2010218513.tif 000012
【００３３】
ｎが１である場合、量子加算回路１００はステージ４の量子回路を持たない。
【００３４】
ｎが３以上の整数である場合には、ステージ４に続くステージ５の量子回路は、ｐ＝１，・・・，ｎ−２について、順に、キュービットＡpを制御キュービットとし、キュービットＡp+1を標的キュービットとして、キュービットＡpとキュービットＡp+1に対して制御ＮＯＴゲートを適用する量子回路である。基本演算は制御ＮＯＴ演算であり、基本演算数はｎ−２である。
第５量子演算部は、これらの制御ＮＯＴ演算を実行する（ステップＳ５）。これらの制御ＮＯＴ演算はｐ＝１，・・・，ｎ−２の順番で実行されるため、計算ステップ数はそれぞれｎ−２である。
ステージ５を経た時点での出力状態は式（１１）で表される。
【数１１】
2010218513.tif 000013
【００３５】
ｎが１または２である場合、量子加算回路１００はステージ５の量子回路を持たない。
【００３６】
ステージ５に続くステージ６の量子回路は、ｐ＝０，・・・，ｎ−１について、キュービットＡpを制御キュービットとし、キュービットＢpを標的キュービットとして、キュービットＢpとキュービットＡpに対して制御ＮＯＴゲートを適用する量子回路である。基本演算は制御ＮＯＴ演算であり、基本演算数はｎである。
第６量子演算部は、これらの制御ＮＯＴ演算を実行する（ステップＳ６）。これらの制御ＮＯＴ演算は並列実行可能であり、計算ステップ数は１である。
ステージ６を経た時点での出力状態は式（１２）で表され、この出力状態が量子加算回路１００の出力状態である。
【数１２】
2010218513.tif 000014
【００３７】
本発明の量子加算回路の特徴の一つは、ステージ３を経た時点での出力状態が式（９）で表されるように、キャリービットｃiが初期状態|ａi〉を与えられたキュービットＡiに蓄えられることにある。これは、ＭＡＪゲートを二つの制御ＮＯＴゲートを含む前段部と一つのToffoliゲートを含む後段部に分けて、ＭＡＪゲートの作用を複合的に利用することで達成される。具体的には、前段部を用いて、ステージ２を経た時点で、式（８）で表される出力状態を得る。そして、この出力状態において、キュービットＢ0およびキュービットＡ0を制御キュービットとし、キュービットＡ1を標的キュービットとして、キュービットＢ0とキュービットＡ0とキュービットＡ1に対してToffoliゲートを適用すると、式（１３）で表される状態を得ることは、式（１４）で表されるToffoliゲートの作用から容易に理解される。ただし、式（１４）では１≦ｉ≦ｎ−１であり、ａnをｚと看做すものとする。
【数１３】
2010218513.tif 000015
【００３８】
従って、後段部を用いてToffoliゲートを順次適用することによって式（９）で表される状態を得ることができる。
【００３９】
ｎ≧２の場合、ステージ１からステージ６までの基本演算数と計算ステップ数をそれぞれ加算することによって、量子加算回路１００の基本演算数は７ｎ−６、計算ステップ数は５ｎ−３である。
【００４０】
〔量子減算〕
次に、図６および図１４を参照して、減算のための量子回路２００を説明する。以下、減算のための量子回路２００を量子減算回路２００と呼称する。
【００４１】
量子減算は、ｎビット（入力桁数ｎ）の２つの２進数ａ＝ａn-1…ａ0〔ａi∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝〕及びｂ＝ｂn-1…ｂ0〔ｂi∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝〕と、０または１のｚ〔ｚ∈｛０，１｝〕とが入力として与えられたとき、ａ−ｂ＝ｓn-1…ｓ0〔ｓi∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝〕を計算し、ｚ（＋XOR）ｓnとｓn-1…ｓ0とａとを出力する演算であり、式（１５）で表される演算である。ｓn〔ｓn∈｛０，１｝〕は、ａ−ｂの２進数表現であるｓn-1…ｓ0の符号を表し、ｂ≦ａならば１、それ以外ならば０である。ここでは、負の数を表すために２の補数を用いることとする。つまり、ｓn＝０の場合、ａ−ｂ＝ｓn-1…ｓ0は、絶対値が［ａ−ｂ−１］である負の数を表す。ここで［Ｘ］はＸの１の補数を表す。このとき、符号ｓnを考慮したビット列ｓn…ｓ0についてｓn…ｓ0＝［［ａ］＋ｂ］が成り立つ。なお、ｎは１以上の整数である。
【数１４】
2010218513.tif 000016
【００４２】
ここで便宜的にキャリービットｄi（０≦ｉ≦ｎ）を式（１６）のように定義する。
【数１５】
2010218513.tif 000017
【００４３】
また、ｔi（０≦ｉ≦ｎ）をキャリービットｄiを用いて式（１７）のように定義する。
【数１６】
2010218513.tif 000018
【００４４】
このとき、ｓi（０≦ｉ≦ｎ）はｔiを用いて式（１８）で与えられる。
【数１７】
2010218513.tif 000019
【００４５】
ｓn…ｓ0＝［［ａ］＋ｂ］が成り立つため、量子減算回路２００は、量子加算回路１００を用いて構成される。量子減算回路２００は、ｎ個のキュービットＢi（ｉ∈｛０，…，ｎ−１｝）と、ｎ＋１個のキュービットＡj（ｊ∈｛０，…，ｎ｝）を演算対象とする。キュービットＢiの初期状態は|ｂi〉である（ｉ∈｛０，…，ｎ−１｝）。キュービットＡiの初期状態は|ａi〉である（ｉ∈｛０，…，ｎ−１｝）。キュービットＡｎの初期状態は|ｚ〉である。つまり、量子減算回路２００の入力状態は式（６）で表される。図６では５ビット（ｎ＝５）の量子減算回路２００を例示している。
【００４６】
量子減算回路２００は、ステージ０、ステージ１、・・・、ステージ７までの最大８個の量子回路で構成されている。
【００４７】
ステージ０の量子回路は、ｐ＝０，・・・，ｎ−１について、キュービットＡpに対してＮＯＴゲートを適用する量子回路である。基本演算はＮＯＴ演算であり、基本演算数はｎである。
第０量子演算部は、これらのＮＯＴ演算を実行する（ステップＳ０）。これらのＮＯＴ演算は並列実行可能であり、計算ステップ数は１である。
ステージ０を経た時点での出力状態は式（１９）で表される。
【数１８】
2010218513.tif 000020
【００４８】
ステージ１からステージ６までは、量子加算回路１００と同じである。但し、各ステージを経た時点での出力状態はｎ≧３の場合に式（２０）のとおりである。
【数１９】
2010218513.tif 000021
【００４９】
ステージ６に続くステージ７の量子回路は、ｐ＝０，・・・，ｎとｒ＝０，・・・，ｎ−１について、キュービットＢrに対してＮＯＴゲートを適用し、キュービットＡpに対してＮＯＴゲートを適用する量子回路である。基本演算はＮＯＴ演算であり、基本演算数は２ｎ＋１である。
第７量子演算部は、これらのＮＯＴ演算を実行する（ステップＳ７）。これらのＮＯＴ演算は並列実行可能であり、計算ステップ数は１である。
ステージ７を経た時点での出力状態は式（２１）で表され、この出力状態が量子減算回路２００の出力状態である。
【数２０】
2010218513.tif 000022
【００５０】
ｎ≧２の場合、ステージ０からステージ７までの基本演算数と計算ステップ数をそれぞれ加算することによって、量子減算回路２００の基本演算数は１０ｎ−５、計算ステップ数は５ｎ−１である。
【００５１】
〔量子比較演算〕
次に、図７および図１５を参照して、比較のための量子回路３００を説明する。以下、比較のための量子回路３００を量子比較回路３００と呼称する。
【００５２】
量子比較演算は、ｎビット（入力桁数ｎ）の２つの２進数ａ＝ａn-1…ａ0〔ａi∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝〕及びｂ＝ｂn-1…ｂ0〔ｂi∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝〕と、０または１のｚ〔ｚ∈｛０，１｝〕とが入力として与えられたとき、ａ−ｂ＝ｓn-1…ｓ0〔ｓi∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝〕の符号ｙを計算し、ｚ（＋XOR）ｙとｂとａとを出力する演算であり、式（２２）で表される演算である。ｙ〔ｙ∈｛０，１｝〕は、ａ−ｂの２進数表現であるｓn-1…ｓ0の符号を表し、ｂ≦ａならば１、それ以外ならば０である。ここでは、負の数を表すために２の補数を用いることとする。つまり、ｙ＝０の場合、ａ−ｂ＝ｓn-1…ｓ0は、絶対値が［ａ−ｂ−１］である負の数を表す。ここで［Ｘ］はＸの１の補数を表す。このとき、符号ｙを考慮したビット列yｓn-1…ｓ0についてyｓn-1…ｓ0＝［［ａ］＋ｂ］が成り立つ。なお、ｎは１以上の整数である。
【数２１】
2010218513.tif 000023
【００５３】
キャリービットｄi（０≦ｉ≦ｎ）は式（１６）のように定義される。このとき、ｙ＝ｄnである。
【００５４】
ｓn…ｓ0＝［［ａ］＋ｂ］が成り立つため、量子比較回路３００は、量子減算回路２００を利用して構成される。但し、ｓi（０≦ｉ≦ｎ−１）を計算する必要がないので、量子減算回路２００を一部変形して利用する。量子比較回路３００は、ｎ個のキュービットＢi（ｉ∈｛０，…，ｎ−１｝）と、ｎ＋１個のキュービットＡj（ｊ∈｛０，…，ｎ｝）を演算対象とする。キュービットＢiの初期状態は|ｂi〉である（ｉ∈｛０，…，ｎ−１｝）。キュービットＡiの初期状態は|ａi〉である（ｉ∈｛０，…，ｎ−１｝）。キュービットＡｎの初期状態は|ｚ〉である。つまり、量子比較回路３００の入力状態は式（６）で表される。図７では５ビット（ｎ＝５）の量子比較回路３００を例示している。
【００５５】
量子比較回路３００は、ステージ０、ステージ１、ステージ２、ステージ３、ステージ４ａ、ステージ５、ステージ６ａ、ステージ７ａまでの最大８個の量子回路で構成されている。
【００５６】
ステージ０からステージ３までは、量子減算回路２００と同じである。
【００５７】
ｎが２以上の整数である場合、ステージ３に続くステージ４ａの量子回路は、ｐ＝ｎ−１，・・・，１について、順に、キュービットＢp-1およびキュービットＡp-1を制御キュービットとし、キュービットＡpを標的キュービットとして、キュービットＢp-1とキュービットＡp-1とキュービットＡpに対してToffoliゲートを適用する量子回路である。基本演算はToffoli演算であり、基本演算数はｎ−１である。
第４ａ量子演算部は、これらのToffoli演算を実行する（ステップＳ４ａ）。これらのToffoli演算はｐ＝ｎ−１，・・・，１の順番で実行されるため、計算ステップ数はｎ−１である。
ステージ４ａを経た時点での出力状態は式（２３）で表される。
【数２２】
2010218513.tif 000024
【００５８】
ｎが１である場合、量子比較回路３００はステージ４ａの量子回路を持たない。
【００５９】
ステージ４ａに続くステージ５の量子回路は、量子加算回路１００に含まれるステージ５の量子回路と同じである。但し、ステージ５を経た時点での出力状態はｎ≧３の場合に式（２４）のとおりである。
【数２３】
2010218513.tif 000025
【００６０】
ステージ５に続くステージ６ａの量子回路は、ｐ＝１，・・・，ｎ−１について、キュービットＡpを制御キュービットとし、キュービットＢpを標的キュービットとして、キュービットＢpとキュービットＡpに対して制御ＮＯＴゲートを適用する量子回路である。基本演算は制御ＮＯＴ演算であり、基本演算数はｎ−１である。
第６ａ量子演算部は、これらの制御ＮＯＴ演算を実行する（ステップＳ６ａ）。これらの制御ＮＯＴ演算は並列実行可能であり、計算ステップ数は１である。
ステージ６ａを経た時点での出力状態は式（２５）で表される。
【数２４】
2010218513.tif 000026
【００６１】
ステージ６ａに続くステージ７ａの量子回路は、ｐ＝０，・・・，ｎについて、キュービットＡpに対してＮＯＴゲートを適用する量子回路である。基本演算はＮＯＴ演算であり、基本演算数はｎ＋１である。
第７ａ量子演算部は、これらのＮＯＴ演算を実行する（ステップＳ７ａ）。これらのＮＯＴ演算は並列実行可能であり、計算ステップ数は１である。
ステージ７ａを経た時点での出力状態は式（２６）で表され、この出力状態が量子比較回路３００の出力状態である。
【数２５】
2010218513.tif 000027
【００６２】
ｎ≧２の場合、ステージ０からステージ７ａまでの基本演算数と計算ステップ数をそれぞれ加算することによって、量子比較回路３００の基本演算数は８ｎ−５、計算ステップ数は４ｎである。
【００６３】
〔近傍２量子ビット演算〕
量子演算において、キュービットの状態が物理的な状態であるところ、隣り合うキュービットよりも離れたキュービットに基づく作用を受けるとすると、一般的に演算誤りのリスクが高まる。そこで、隣り合うキュービット間の量子演算である近傍２量子ビット演算を用いる量子回路が好ましい。
【００６４】
量子加算回路１００、量子減算回路２００、量子比較回路３００では、容易に近傍２量子ビット演算を用いる量子回路に変更することができる。この変換は、図１１に示すように、近傍２量子ビット演算ではない制御ＮＯＴ演算とToffoli演算をＳＷＡＰゲートを用いて近傍２量子ビット演算である制御ＮＯＴ演算とToffoli演算に変更することで達成される。ＳＷＡＰゲートは、図１２に示す量子ゲートである。
【００６５】
〔量子演算装置〕
次に、本発明の量子回路に則って量子演算を行う量子演算装置について説明する。本発明の量子演算装置は、本発明の量子回路から明らかなように、実施形態に応じて、第０量子演算部、第１量子演算部、第２量子演算部、第３量子演算部、第４量子演算部、第５量子演算部、第６量子演算部、第７量子演算部、第４ａ量子演算部、第６ａ量子演算部、第７ａ量子演算部のいずれかを含む。さらに、各量子演算部は、実施形態に応じた基本量子演算部（ＮＯＴ演算部、制御ＮＯＴ演算部、Toffoli演算部）を含む。つまり、本発明の量子回路に示した量子ゲートが、量子演算装置の基本量子演算部に相当する。なお、全ての演算は単一量子ビットに対する１量子ビット演算と制御ＮＯＴ演算に分解できる（上記非特許文献３参照）。
【００６６】
量子演算装置は、量子コンピュータ単体で実現できる。量子コンピュータの実現する物理系としては、例えば、イオントラップを用いる方法（J. I. Cirac and P. Zoller, Quantum computations with cold trapped ions, Physical Review Letter 74;4091, 1995）、量子ビットとして光子の偏光や光路を用いる方法（Y. Nakamura, M. Kitagawa, K. Igeta, In 3-rd Proc. Asia-Pacific Phys. Comf., World Scientific, Singapore, 1988）、液体中の各スピンを用いる方法（Gershenfield, Chuang, Bulk spin resonance quantum computation, Science, 275;350, 1997）、シリコン結晶中の核スピンを用いる方法（B. E. Kane, A silicon-based nuclear spin quantum computer, Nature 393, 133, 1998）、量子ドット中の電子スピンを用いる方法（D. Loss and D. P. DiVincenzo, Quantum computation with quantum dots, Physical Review A 57, 120-126, 1998）、超伝導素子を用いる方法（Y. Nakamura, Yu. A. Pashkin and J. S. Tsai, Coherent control of macroscopic quantum states in a single-cooper pair box, Nature 393, 786-788, 1999）等を例示できる。また、それぞれの物理系に対する量子コンピュータの実現方法については、「http://www.ipa.go.jp/security/fy11/report/contents/crypto/crypto/report/QuantumComputers/contents/doc/qc_survey.pdf」や「M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, Cambridge UniversityPress, Chapter 7 Physical Realization」に詳しい。
【００６７】
＜量子ビット＞
イオントラップ量子コンピュータでは、例えば、イオンの基底状態と励起状態を利用して量子ビットを実現する。また、核スピンを量子ビットとして用いる場合には、例えば、「T. D. Ladd, et al., "All-Silicon quantum computer," Phys. Rev. Lett., vol. 89, no. 1, 017901-1‐017901-4, July 1, 2002.」に記載されているようにＳｉ（１１１）基板等に各量子ビットを生成する。なお、量子ビットの初期量子状態は、例えば、他の演算の量子回路による操作によって得られたものを用いてもよいし、各量子ビットが生成された基板をｍＫ（ミリケルビン）オーダー以下に冷却してスピンの向きを揃えた後、所定の電磁波パルスを印加して生成してもよい。また、量子ビットとして光子の偏光を用いる場合には、例えば、パラメトリックダウンコンバージョン（ＰＤＣ：parametric down conversion）（例えば、「P. G. Kwiat, K. Mattle, H. Weinfurter, A. Zeilinger, A. V. Sergienko, and Y. Shih, “New high-intensity source of polarization-entangled photon pairs,” Phys. Rev. Lett. ,75:4337-4341, 1995.」「P. G. Kwiat, E. Waks, A. G. White, I. Appelbaum, and P. H. Eberhard, “Ultrabright source of polarization-entangled photons,” Phys. Rev. A, 60:R773-R776, 1999.」等参照。）によって生成された複数個の単一光子を用いる。この場合、各量子ビットの初期量子状態は、例えば、他の演算の量子回路による操作によって得られたものを用いる。また、パラメトリックダウンコンバージョン等によって生成された単一光子に、ビームスプリッタや偏光回転素子等によって実現されるウォルシューアダマール変換、ＣＮＯＴ、回転等の操作を行い、上述の初期量子状態を生成することとしてもよい。
その他、上記の文献に記載された方法で量子ビットを用意することとしてもよい。
【００６８】
また、演算前後や演算途中において量子ビットの量子状態を保存する必要がある場合には、例えば、量子ドット内の電子準位、核スピン、あるいは超伝導体内部の電荷（クーパー対）量を量子ビットとして用いてデータを保存する量子メモリ等を用いてもよい（A.Barenco, D.Deutsch, and A.Ekert, Phys. Rev. Lett.74,4083(1995)、松枝秀明  電子情報通信学会誌  A Vol.J81-A No.12(1998)1978、T.H.Oosterkamp et.al., Nature 395,873(1998)、D.Loss and D.P. DiVincenzo, Phys. Rev. A57(1998) 120. T.Oshima, quant-ph/0002004, http://arxiv.org/abs/quant-ph/0002004、B.E.Kane, A silicon-based nuclear spin quantum computer, Nature, 393, 133(1998)、http://www.snf.unsw.edu.au/、Y.Nakamura, Yu. A. Pashkin and J.S.Tsai, Nature 398(1999)768）。
【００６９】
＜ＣＮＯＴ演算＞
イオントラップ量子コンピュータでは、例えば、イオンを直線上に並べ、各イオンに狙いを定めたレーザービーム照射によってＣＮＯＴ演算を実現する。また、量子ビットとして光子の偏光を用いる場合には、例えば、偏光ビームスプリッタ等を用い、「T.B. Pittman, M.J. Fitch, B.C. Jacobs, J.D. Franson: “Experimental Controlled-NOT Logic Gate for Single Photons in the Coincidence Basis,” quant-ph/0303095, http://arxiv.org/abs/quant-ph/0303095」記載のPittman et al. 方式によってＣＮＯＴ演算を実現する。また、核スピンを量子ビットとして用いる場合には、例えば、所定の電磁波パルスを量子ビットに印加することによってＣＮＯＴ演算を実現できる。
その他、上記の文献に記載された方法でＣＮＯＴ演算を実現してもよい。
【００７０】
＜量子ビット単体操作＞
イオントラップ量子コンピュータでは、例えば、イオンを直線上に並べ、各イオンに狙いを定めたレーザービーム照射によって量子ビット単体の操作を実現する。核スピンを量子ビットとして用いる場合には、電磁波パルスやレーザービーム照射によって各処理を実現する。また、量子ビットとして光子の偏光を用いる場合には、例えば、偏光回転素子等によって実現する。
【００７１】
なお、本発明は上述の実施の形態に限定されるものではなく、その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。例えば量子加算回路１００では、制御ＮＯＴ演算とToffoli演算を基本演算としている。しかしながら、本発明の量子回路に使われる全ての演算は単一量子ビットに対する１量子ビット演算と制御ＮＯＴ演算に分解できるので（上記非特許文献３参照）、ここでの基本演算以外の演算を用いて量子加算回路１００と等価な量子回路を構成できる。また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００７２】
ところで、本発明の量子回路に則って量子演算を行う手順自体は、古典コンピュータで決定することができる。本発明の量子回路に則って量子演算を行う手順は、本発明の量子回路を入力側から出力側に向かって順に行う各計算ステップである。
【００７３】
具体的には、例えば図５で示した量子加算回路１００を例とすると、ステージ１からステージ６の各量子回路における量子演算を行う手順をそれぞれ決定し量子回路の入力側から出力側に向かって順に手順を並べることで、量子加算回路１００に則って量子演算を行う手順を決定できる。ただし、１計算ステップで並行演算可能であれば、これらの演算を並行するものを１手順とすればよい。
換言すれば、この古典コンピュータは、図１３に示したステップＳ１−ステップＳ６の手順を決定して出力するものといえる。
【００７４】
このような古典コンピュータ、つまり、本発明の量子回路における量子演算の手順を決定する量子演算手順決定装置は、いわゆる古典的な装置構成で実現される。例えばパーソナルコンピュータに例示されるように、記憶装置（例えばＲＡＭ、ＲＯＭやハードディスク）、演算処理装置（例えばＣＰＵ）、入力・出力装置（例えばキーボード、ディスプレイ）、これらの装置間でデータのやり取りが可能に接続するバスなどを備えた古典コンピュータによって実現することができる。
この場合、例えば図５の例でステージ１からステージ６の各量子回路における量子演算を行う手順をそれぞれ決定するための各プログラム、量子回路の入力側から出力側に向かって順に手順を並べるためのプログラムを記憶装置に記憶しておき、必要に応じて演算処理装置がプログラムを読み込んで解釈実行することで、ステージ１からステージ６の各量子回路における量子演算を行う手順をそれぞれ決定する各機能、量子回路の入力側から出力側に向かって順に手順を並べる機能を実現する。また各プログラムは、コンピュータ読み取り可能な記録媒体（例えばＣＤ−Ｒ、ＤＶＤ−ＲＡＭ、ＭＯ）に記録することもできる。
【図１】
2010218513.tif 000028
【図２】
2010218513.tif 000029
【図３】
2010218513.tif 000030
【図４】
2010218513.tif 000031
【図５】
2010218513.tif 000032
【図６】
2010218513.tif 000033
【図７】
2010218513.tif 000034
【図８】
2010218513.tif 000035
【図９】
2010218513.tif 000036
【図１０】
2010218513.tif 000037
【図１１】
2010218513.tif 000038
【図１２】
2010218513.tif 000039
【図１３】
2010218513.tif 000040
【図１４】
2010218513.tif 000041
【図１５】
2010218513.tif 000042