(57)【要約】【課題】  線形サイズ・線形深さで補助ビットを用いずに量子計算を行う。【解決手段】    Q2n+1,Qk+2(k=1,…,2n-2)に対するCNOT演算操作を行い、Q1,Q2,Q2n+1に対するトフォリ演算操作を行い、その操作の後、Q2p+1,Q2p+2,Q2n+1に対するMAJ演算操作とQ2p+1,Q2p+2,Q1に対するトフォリ演算操作とをp=1からp=n-2までpを１ずつ増加させる順序で繰り返し、その繰り返しの後、Q2n-1,Q2n,Q2n+1に対するMAJ演算操作を行う。また、Q1,Q2q+4に対するCNOT演算操作とQ2q+1,Q2q+2,Q1に対するトフォリ演算操作とをq=n-2からq=1までqを１ずつ減少させる順序で繰り返す。そして、Q2に対するNOT演算操作を行い、Q1,Q2,Q2r+4(r=1,…,n-2)に対するトフォリ演算操作を行い、その操作の後、キュービットQ2に対するNOT演算操作を行い、さらにQ1,Q2,Q4に対するトフォリ演算操作を行い、その操作の後、Q2t,Q2t-1(t=1,…,n)に対するCNOT演算操作を行う。  【選択図】        図１
2006338185.tif 000002
【特許請求の範囲】
【請求項１】
２つの２進数ａ＝ａｎ−１…ａ０〔ａｉ∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝〕及びｂ＝ｂｎ−１…ｂ０〔ｂｉ∈｛０，１｝〕と、０または１のｚ〔ｚ∈｛０，１｝〕とに対し、ａ＋ｂ＝ｓｎ…ｓ０〔ｓｊ∈｛０，１｝，ｊ∈｛０，…，ｎ｝〕と、ｚ（＋）ｓｎ〔α（＋）βはαとβとの排他的論理和を示す〕とを算出する量子演算装置であって、
それぞれの初期量子状態が｜ｂ０＞，｜ａ０＞，…，｜ｂｎ−１＞，｜ａｎ−１＞，｜ｚ＞である２ｎ＋１個のキュービットＱ１，Ｑ２，…，Ｑ２ｎ＋１を対象とし、キュービットＱ２ｎ＋１，Ｑｋ＋２（ｋ＝１，…，２ｎ−２）に対するＣＮＯＴ演算操作を行う値分配部と、
キュービットＱ１，Ｑ２，Ｑ２ｎ＋１に対するトフォリ演算操作を行い、その操作の後、キュービットＱ２ｐ＋１，Ｑ２ｐ＋２，Ｑ２ｎ＋１に対するＭＡＪ演算操作とキュービットＱ２ｐ＋１，Ｑ２ｐ＋２，Ｑ１に対するトフォリ演算操作とをｐ＝１からｐ＝ｎ−２までｐを１ずつ増加させる順序で繰り返し、その繰り返しの後、キュービットＱ２ｎ−１，Ｑ２ｎ，Ｑ２ｎ＋１に対するＭＡＪ演算操作を行うＭＡＪ計算部と、
キュービットＱ１，Ｑ２ｑ＋４に対するＣＮＯＴ演算操作とキュービットＱ２ｑ＋１，Ｑ２ｑ＋２，Ｑ１に対するトフォリ演算操作とをｑ＝ｎ−２からｑ＝１までｑを１ずつ減少させる順序で繰り返す第１逆計算部と、
キュービットＱ２に対するＮＯＴ演算操作を行い、キュービットＱ１，Ｑ２，Ｑ２ｒ＋４（ｒ＝１，…，ｎ−２）に対するトフォリ演算操作を行い、その操作の後、キュービットＱ２に対するＮＯＴ演算操作を行い、さらにキュービットＱ１，Ｑ２，Ｑ４に対するトフォリ演算操作を行い、その操作の後、キュービットＱ２ｔ，Ｑ２ｔ−１（ｔ＝１，…，ｎ）に対するＣＮＯＴ演算操作を行う第２逆計算部と、
を有することを特徴とする量子演算装置。
【請求項２】
２つの２進数ａ＝ａｎ−１…ａ０〔ａｉ∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝〕及びｂ＝ｂｎ−１…ｂ０〔ｂｉ∈｛０，１｝〕に対し、（ａ＋ｂ）ｍｏｄ２ｎ＝ｓｎ−１…ｓ０〔ｓｉ∈｛０，１｝〕を算出する量子演算装置であって、
それぞれの初期量子状態が｜ｂ０＞，｜ａ０＞，…，｜ｂｎ−１＞，｜ａｎ−１＞である２ｎ個のキュービットＱ１，Ｑ２，…，Ｑ２ｎを対象とし、キュービットＱ２ｎ，Ｑｋ＋２（ｋ＝１，…，２ｎ−３）に対するＣＮＯＴ演算操作を行う値分配部と、
キュービットＱ１，Ｑ２，Ｑ２ｎに対するトフォリ演算操作を行い、その操作の後、キュービットＱ２ｐ＋１，Ｑ２ｐ＋２，Ｑ２ｎに対するＭＡＪ演算操作とキュービットＱ２ｐ＋１，Ｑ２ｐ＋２，Ｑ１に対するトフォリ演算操作とをｐ＝１からｐ＝ｎ−２までｐを１ずつ増加させる順序で繰り返し、キュービットＱ２ｎ，Ｑ２ｎ−１に対するＣＮＯＴ演算操作を行うＭＡＪ計算部と、
キュービットＱ１，Ｑ２ｑ＋４に対するＣＮＯＴ演算操作とキュービットＱ２ｑ＋１，Ｑ２ｑ＋２，Ｑ１に対するトフォリ演算操作とをｑ＝ｎ−２からｑ＝１までｑを１ずつ減少させる順序で繰り返す第１逆計算部と、
キュービットＱ２に対するＮＯＴ演算操作を行い、キュービットＱ１，Ｑ２，Ｑ２ｒ＋４（ｒ＝１，…，ｎ−２）に対するトフォリ演算操作を行い、その操作の後、キュービットＱ２に対するＮＯＴ演算操作を行い、さらにキュービットＱ１，Ｑ２，Ｑ４に対するトフォリ演算操作を行い、その操作の後、キュービットＱ２ｔ，Ｑ２ｔ−１（ｔ＝１，…，ｎ）に対するＣＮＯＴ演算操作を行う第２逆計算部と、
を有することを特徴とする量子演算装置。
【請求項３】
２つの２進数ａ＝ａｎ−１…ａ０〔ａｉ∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝〕及びｂ＝ｂｎ−１…ｂ０〔ｂｉ∈｛０，１｝〕と、０または１のｚ〔ｚ∈｛０，１｝〕とに対し、ａ−ｂ＝ｓｎ−１…ｓ０〔ｓｉ∈｛０，１｝〕とその符号ｓｎ〔ｓｎ∈｛０，１｝〕とを算出する量子演算装置であって、
それぞれの初期量子状態が｜ｂ０＞，｜ａ０＞，…，｜ｂｎ−１＞，｜ａｎ−１＞，｜ｚ＞である２ｎ＋１個のキュービットＱ１，Ｑ２，…，Ｑ２ｎ＋１を対象とし、キュービットＱ２ｈ（ｈ＝１，…，ｎ）に対するＮＯＴ演算操作を行う第１否定演算部と、
キュービットＱ２ｎ＋１，Ｑｋ＋２（ｋ＝１，…，２ｎ−２）に対するＣＮＯＴ演算操作を行う値分配部と、
キュービットＱ１，Ｑ２，Ｑ２ｎ＋１に対するトフォリ演算操作を行い、その操作の後、キュービットＱ２ｐ＋１，Ｑ２ｐ＋２，Ｑ２ｎ＋１に対するＭＡＪ演算操作とキュービットＱ２ｐ＋１，Ｑ２ｐ＋２，Ｑ１に対するトフォリ演算操作とをｐ＝１からｐ＝ｎ−２までｐを１ずつ増加させる順序で繰り返し、その繰り返しの後、キュービットＱ２ｎ−１，Ｑ２ｎ，Ｑ２ｎ＋１に対するＭＡＪ演算操作を行うＭＡＪ計算部と、
キュービットＱ１，Ｑ２ｑ＋４に対するＣＮＯＴ演算操作とキュービットＱ２ｑ＋１，Ｑ２ｑ＋２，Ｑ１に対するトフォリ演算操作とをｑ＝ｎ−２からｑ＝１までｑを１ずつ減少させる順序で繰り返す第１逆計算部と、
キュービットＱ２に対するＮＯＴ演算操作を行い、キュービットＱ１，Ｑ２，Ｑ２ｒ＋４（ｒ＝１，…，ｎ−２）に対するトフォリ演算操作を行い、その操作の後、キュービットＱ２に対するＮＯＴ演算操作を行い、さらにキュービットＱ１，Ｑ２，Ｑ４に対するトフォリ演算操作を行い、その操作の後、キュービットＱ２ｔ，Ｑ２ｔ−１（ｔ＝１，…，ｎ）に対するＣＮＯＴ演算操作を行う第２逆計算部と、
キュービットＱｕ（ｕ＝１，…，２ｎ＋１）に対するＮＯＴ演算操作を行う第２否定演算部と、
を有することを特徴とする量子演算装置。
【請求項４】
２つの２進数ａ＝ａｎ−１…ａ０〔ａｉ∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝〕及びｂ＝ｂｎ−１…ｂ０〔ｂｉ∈｛０，１｝〕と、０または１のｚ〔ｚ∈｛０，１｝〕とに対し、ａ−ｂの符号ｙを算出する量子演算装置であって、
それぞれの初期量子状態が｜ｂ０＞，｜ａ０＞，…，｜ｂｎ−１＞，｜ａｎ−１＞，｜ｚ＞である２ｎ＋１個のキュービットＱ１，Ｑ２，…，Ｑ２ｎ＋１を対象とし、キュービットＱ２ｋ（ｋ＝１，…，ｎ）に対するＮＯＴ演算操作を行う第１否定演算部と、
キュービットＱ２ｎ＋１，Ｑｋ＋２（ｋ＝１，…，２ｎ−２）に対するＣＮＯＴ演算操作を行う値分配部と、
キュービットＱ１，Ｑ２，Ｑ２ｎ＋１に対するトフォリ演算操作を行い、その操作の後、キュービットＱ２ｐ＋１，Ｑ２ｐ＋２，Ｑ２ｎ＋１に対するＭＡＪ演算操作とキュービットＱ２ｐ＋１，Ｑ２ｐ＋２，Ｑ１に対するトフォリ演算操作とをｐ＝１からｐ＝ｎ−２までｐを１ずつ増加させる順序で繰り返し、その繰り返しの後、キュービットＱ２ｎ−１，Ｑ２ｎ，Ｑ２ｎ＋１に対するＭＡＪ演算操作を行うＭＡＪ計算部と、
キュービットＱ１，Ｑ２ｑ＋４に対するＣＮＯＴ演算操作とキュービットＱ１，Ｑ２ｑ＋３に対するＣＮＯＴ演算操作とキュービットＱ２ｑ＋１，Ｑ２ｑ＋２，Ｑ１に対するトフォリ演算操作とをｑ＝ｎ−２からｑ＝１までｑを１ずつ減少させる順序で繰り返す第１逆計算部と、
キュービットＱ２に対するＮＯＴ演算操作を行い、その操作の後、キュービットＱ１，Ｑ２，Ｑ２ｒ＋４に対するトフォリ演算操作とキュービットＱ１，Ｑ２，Ｑ２ｒ＋３に対するトフォリ演算操作とをｒ＝ｎ−２からｒ＝１までｒを１ずつ減少させる順序で繰り返し、その繰り返しの後、キュービットＱ２に対するＮＯＴ演算操作を行い、キュービットＱ１，Ｑ２，Ｑ４に対するトフォリ演算操作を行い、キュービットＱ１，Ｑ２，Ｑ３に対するトフォリ演算操作を行う第２逆計算部と、
キュービットＱ２ｕ（ｕ＝１，…，ｎ）に対するＮＯＴ演算操作とキュービットＱ２ｎ＋１に対するＮＯＴ演算操作とを行う第２否定演算部と、
を有することを特徴とする量子演算装置。
【請求項５】
２つの２進数ａ＝ａｎ−１…ａ０〔ａｉ∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝〕及びｂ＝ｂｎ−１…ｂ０〔ｂｉ∈｛０，１｝〕と、０または１のｚ〔ｚ∈｛０，１｝〕とに対し、ａ＋ｂ＝ｓｎ…ｓ０〔ｓｊ∈｛０，１｝，ｊ∈｛０，…，ｎ｝〕と、ｚ（＋）ｓｎ〔α（＋）βはαとβとの排他的論理和を示す〕とを算出する量子回路を用いた量子演算方法であって、
それぞれの初期量子状態が｜ｂ０＞，｜ａ０＞，…，｜ｂｎ−１＞，｜ａｎ−１＞，｜ｚ＞である２ｎ＋１個のキュービットＱ１，Ｑ２，…，Ｑ２ｎ＋１を対象とし、値分配部において、キュービットＱ２ｎ＋１，Ｑｋ＋２（ｋ＝１，…，２ｎ−２）に対するＣＮＯＴ演算操作を行うステップと、
ＭＡＪ計算部において、キュービットＱ１，Ｑ２，Ｑ２ｎ＋１に対するトフォリ演算操作を行い、その操作の後、キュービットＱ２ｐ＋１，Ｑ２ｐ＋２，Ｑ２ｎ＋１に対するＭＡＪ演算操作とキュービットＱ２ｐ＋１，Ｑ２ｐ＋２，Ｑ１に対するトフォリ演算操作とをｐ＝１からｐ＝ｎ−２までｐを１ずつ増加させる順序で繰り返し、その繰り返しの後、キュービットＱ２ｎ−１，Ｑ２ｎ，Ｑ２ｎ＋１に対するＭＡＪ演算操作を行うステップと、
第１逆計算部において、キュービットＱ１，Ｑ２ｑ＋４に対するＣＮＯＴ演算操作とキュービットＱ２ｑ＋１，Ｑ２ｑ＋２，Ｑ１に対するトフォリ演算操作とをｑ＝ｎ−２からｑ＝１までｑを１ずつ減少させる順序で繰り返すステップと、
第２逆計算部において、キュービットＱ２に対するＮＯＴ演算操作を行い、キュービットＱ１，Ｑ２，Ｑ２ｒ＋４（ｒ＝１，…，ｎ−２）に対するトフォリ演算操作を行い、その操作の後、キュービットＱ２に対するＮＯＴ演算操作を行い、さらにキュービットＱ１，Ｑ２，Ｑ４に対するトフォリ演算操作を行い、その操作の後、キュービットＱ２ｔ，Ｑ２ｔ−１（ｔ＝１，…，ｎ）に対するＣＮＯＴ演算操作を行うステップと、
を有することを特徴とする量子回路を用いた量子演算方法。
【請求項６】
２つの２進数ａ＝ａｎ−１…ａ０〔ａｉ∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝〕及びｂ＝ｂｎ−１…ｂ０〔ｂｉ∈｛０，１｝〕に対し、（ａ＋ｂ）ｍｏｄ２ｎ＝ｓｎ−１…ｓ０〔ｓｉ∈｛０，１｝〕を算出する量子回路を用いた量子演算方法であって、
それぞれの初期量子状態が｜ｂ０＞，｜ａ０＞，…，｜ｂｎ−１＞，｜ａｎ−１＞である２ｎ個のキュービットＱ１，Ｑ２，…，Ｑ２ｎを対象とし、値分配部において、キュービットＱ２ｎ，Ｑｋ＋２（ｋ＝１，…，２ｎ−３）に対するＣＮＯＴ演算操作を行うステップと、
ＭＡＪ計算部において、キュービットＱ１，Ｑ２，Ｑ２ｎに対するトフォリ演算操作を行い、その操作の後、キュービットＱ２ｐ＋１，Ｑ２ｐ＋２，Ｑ２ｎに対するＭＡＪ演算操作とキュービットＱ２ｐ＋１，Ｑ２ｐ＋２，Ｑ１に対するトフォリ演算操作とをｐ＝１からｐ＝ｎ−２までｐを１ずつ増加させる順序で繰り返し、キュービットＱ２ｎ，Ｑ２ｎ−１に対するＣＮＯＴ演算操作を行うステップと、
第１逆計算部において、キュービットＱ１，Ｑ２ｑ＋４に対するＣＮＯＴ演算操作とキュービットＱ２ｑ＋１，Ｑ２ｑ＋２，Ｑ１に対するトフォリ演算操作とをｑ＝ｎ−２からｑ＝１までｑを１ずつ減少させる順序で繰り返すステップと、
第２逆計算部において、キュービットＱ２に対するＮＯＴ演算操作を行い、キュービットＱ１，Ｑ２，Ｑ２ｒ＋４（ｒ＝１，…，ｎ−２）に対するトフォリ演算操作を行い、その操作の後、キュービットＱ２に対するＮＯＴ演算操作を行い、さらにキュービットＱ１，Ｑ２，Ｑ４に対するトフォリ演算操作を行い、その操作の後、キュービットＱ２ｔ，Ｑ２ｔ−１（ｔ＝１，…，ｎ）に対するＣＮＯＴ演算操作を行うステップと、
を有することを特徴とする量子回路を用いた量子演算方法。
【請求項７】
２つの２進数ａ＝ａｎ−１…ａ０〔ａｉ∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝〕及びｂ＝ｂｎ−１…ｂ０〔ｂｉ∈｛０，１｝〕と、０または１のｚ〔ｚ∈｛０，１｝〕とに対し、ａ−ｂ＝ｓｎ−１…ｓ０〔ｓｉ∈｛０，１｝〕とその符号ｓｎ〔ｓｎ∈｛０，１｝〕とを算出する量子回路を用いた量子演算方法であって、
それぞれの初期量子状態が｜ｂ０＞，｜ａ０＞，…，｜ｂｎ−１＞，｜ａｎ−１＞，｜ｚ＞である２ｎ＋１個のキュービットＱ１，Ｑ２，…，Ｑ２ｎ＋１を対象とし、第１否定演算部において、キュービットＱ２ｈ（ｈ＝１，…，ｎ）に対するＮＯＴ演算操作を行うステップと、
値分配部において、キュービットＱ２ｎ＋１，Ｑｋ＋２（ｋ＝１，…，２ｎ−２）に対するＣＮＯＴ演算操作を行うステップと、
ＭＡＪ計算部において、キュービットＱ１，Ｑ２，Ｑ２ｎ＋１に対するトフォリ演算操作を行い、その操作の後、キュービットＱ２ｐ＋１，Ｑ２ｐ＋２，Ｑ２ｎ＋１に対するＭＡＪ演算操作とキュービットＱ２ｐ＋１，Ｑ２ｐ＋２，Ｑ１に対するトフォリ演算操作とをｐ＝１からｐ＝ｎ−２までｐを１ずつ増加させる順序で繰り返し、その繰り返しの後、キュービットＱ２ｎ−１，Ｑ２ｎ，Ｑ２ｎ＋１に対するＭＡＪ演算操作を行うステップと、
第１逆計算部において、キュービットＱ１，Ｑ２ｑ＋４に対するＣＮＯＴ演算操作とキュービットＱ２ｑ＋１，Ｑ２ｑ＋２，Ｑ１に対するトフォリ演算操作とをｑ＝ｎ−２からｑ＝１までｑを１ずつ減少させる順序で繰り返すステップと、
第２逆計算部において、キュービットＱ２に対するＮＯＴ演算操作を行い、キュービットＱ１，Ｑ２，Ｑ２ｒ＋４（ｒ＝１，…，ｎ−２）に対するトフォリ演算操作を行い、その操作の後、キュービットＱ２に対するＮＯＴ演算操作を行い、さらにキュービットＱ１，Ｑ２，Ｑ４に対するトフォリ演算操作を行い、その操作の後、キュービットＱ２ｔ，Ｑ２ｔ−１（ｔ＝１，…，ｎ）に対するＣＮＯＴ演算操作を行うステップと、
第２否定演算部において、キュービットＱｕ（ｕ＝１，…，２ｎ＋１）に対するＮＯＴ演算操作を行うステップと、
を有することを特徴とする量子回路を用いた量子演算方法。
【請求項８】
２つの２進数ａ＝ａｎ−１…ａ０〔ａｉ∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝〕及びｂ＝ｂｎ−１…ｂ０〔ｂｉ∈｛０，１｝〕と、０または１のｚ〔ｚ∈｛０，１｝〕とに対し、ａ−ｂの符号ｙを算出する量子回路を用いた量子演算方法であって、
それぞれの初期量子状態が｜ｂ０＞，｜ａ０＞，…，｜ｂｎ−１＞，｜ａｎ−１＞，｜ｚ＞である２ｎ＋１個のキュービットＱ１，Ｑ２，…，Ｑ２ｎ＋１を対象とし、第１否定演算部において、キュービットＱ２ｋ（ｋ＝１，…，ｎ）に対するＮＯＴ演算操作を行うステップと、
値分配部において、キュービットＱ２ｎ＋１，Ｑｋ＋２（ｋ＝１，…，２ｎ−２）に対するＣＮＯＴ演算操作を行うステップと、
ＭＡＪ計算部において、キュービットＱ１，Ｑ２，Ｑ２ｎ＋１に対するトフォリ演算操作を行い、その操作の後、キュービットＱ２ｐ＋１，Ｑ２ｐ＋２，Ｑ２ｎ＋１に対するＭＡＪ演算操作とキュービットＱ２ｐ＋１，Ｑ２ｐ＋２，Ｑ１に対するトフォリ演算操作とをｐ＝１からｐ＝ｎ−２までｐを１ずつ増加させる順序で繰り返し、その繰り返しの後、キュービットＱ２ｎ−１，Ｑ２ｎ，Ｑ２ｎ＋１に対するＭＡＪ演算操作を行うステップと、
第１逆計算部において、キュービットＱ１，Ｑ２ｑ＋４に対するＣＮＯＴ演算操作とキュービットＱ１，Ｑ２ｑ＋３に対するＣＮＯＴ演算操作とキュービットＱ２ｑ＋１，Ｑ２ｑ＋２，Ｑ１に対するトフォリ演算操作とをｑ＝ｎ−２からｑ＝１までｑを１ずつ減少させる順序で繰り返すステップと、
第２逆計算部において、キュービットＱ２に対するＮＯＴ演算操作を行い、その操作の後、キュービットＱ１，Ｑ２，Ｑ２ｒ＋４に対するトフォリ演算操作とキュービットＱ１，Ｑ２，Ｑ２ｒ＋３に対するトフォリ演算操作とをｒ＝ｎ−２からｒ＝１までｒを１ずつ減少させる順序で繰り返し、その繰り返しの後、キュービットＱ２に対するＮＯＴ演算操作を行い、キュービットＱ１，Ｑ２，Ｑ４に対するトフォリ演算操作を行い、キュービットＱ１，Ｑ２，Ｑ３に対するトフォリ演算操作を行うステップと、
第２否定演算部において、キュービットＱ２ｕ（ｕ＝１，…，ｎ）に対するＮＯＴ演算操作とキュービットＱ２ｎ＋１に対するＮＯＴ演算操作とを行うステップと、
を有することを特徴とする量子回路を用いた量子演算方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、量子回路を用いて量子演算を行う技術に関する。
【背景技術】
【０００２】
近年、従来の情報理論では解決が難しかった問題を、微細な世界に適用される物理法則である量子力学の原理を応用して解決する技術が注目を集めている。例えば、量子コンピュータは、量子力学の世界特有の現象である重ね合わせ状態を利用し、複数の演算を並列的に実行することができる（量子並列性）。そして、この量子並列性及び観測による状態の縮退により、量子コンピュータは、因数分解などの問題に対し、現在のコンピュータよりはるかに高速に計算が可能であることが示唆されている。
例えば非特許文献１及び２では、量子コンピュータにおいて、２つの２進数ａ＝ａｎ−１…ａ０及びｂ＝ｂｎ−１…ｂ０と、０または１のｚとが入力として与えられたとき、ａ＋ｂ＝ｓｎ…ｓ０を計算し、ｚ（＋）ｓｎとｓｎ−１…ｓ０とａとを出力とする量子回路が開示されている。ただし、α（＋）βは、αとβとのｍｏｄ２での加算（排他的論理和）を示す。
【０００３】
図２１は、この非特許文献１に開示された量子回路を示した図である。
この図に示すように、図２１の量子回路は、ＭＡＪ（Majorrity）量子回路とＵＭＡ（UnMajorrity and And）量子回路とＣＮＯＴ演算とによって構成される。ここで、量子回路とは、ＣＮＯＴ演算等の量子基本演算（操作）の組合せを意味する。また、ＭＡＪ量子回路は、３個のキュービット（量子ビット）がそれぞれ示すｘ，ｙ，ｚのマジョリティｘｙ（＋）ｙｚ（＋）ｚｘを計算する量子回路であり、図２３（ａ）のように定義される。この図に示すように、ＭＡＪ演算は、それぞれ図２４（ｂ）（ｃ）のように定義されるＣＮＯＴ演算とトフォリ（Ｔｏｆｆｏｌｉ）演算とによって構成される。また、図２４（ｂ）（ｃ）におけるＮＯＴ演算は図２４（ａ）のように定義される。また、ＵＭＡ量子回路は、図２３（ｂ）のように定義される。この図に示すように、ＵＭＡ量子回路も、ＣＮＯＴ演算とトフォリ（Ｔｏｆｆｏｌｉ）演算とによって構成される。なお、図面における
【０００４】
【数１】
2006338185.tif 000003
【０００５】
は、前述した（＋）と同じ排他的論理和を示す。
この非特許文献１の量子回路では、２つの２進数ａ＝ａｎ−１…ａ０及びｂ＝ｂｎ−１…ｂ０を示す２ｎ個のキュービット｜ａ０＞，…，｜ａｎ−１＞，｜ｂ０＞，…，｜ｂｎ−１＞と、０または１のｚを示す１個のキュービット｜ｚ＞と、補助ビットである１個のキュービット｜０＞を入力として用いる。なお、図２１は、ａ，ｂがそれぞれ５キュービット（ｎ＝５）によって表される場合の例であるが、これをｎキュービットビット同士の加算回路に拡張することは容易である。
【０００６】
また、この量子回路の場合、演算処理を実行するために必要な基本演算（この例ではＣＮＯＴ演算とトフォリ演算）数は、ａ，ｂの桁数に比例して増加する。さらに、演算処理を実行するために必要な計算ステップ数も、ａ，ｂの桁数に比例して増加する。ここで、入力桁数に比例した基本演算数のことを「線形サイズ」といい、入力桁数に比例した計算ステップ数のことを「線形深さ」という。すなわち、非特許文献１の量子回路は、線形サイズ・線形深さで演算を行う量子回路である。
図２２（ａ）は、非特許文献２に開示された量子回路を示した図である。
【０００７】
この図に示すように、図２１の量子回路は、図２２（ｂ）に示す量子フーリエ変換回路「ＱＦＴ（Quantum Fourier Transform）」と、図２４（ｅ）に示す制御回転Ｒｋ（ｋ＝１，２，…，６）とによって構成される。なお、図２２（ｂ）は、６キュービットに対する量子フーリエ変換を行う量子回路の例であるが、これをｎキュービットに対する量子フーリエ変換を行う量子回路に拡張することは容易である。また、図２２（ｂ）における「Ｈ」は、図２４（ｄ）に示すアダマール（Hadamard）変換演算を示す。なお、ＱＦＴ−１は、ＱＦＴの逆演算を示す。
【０００８】
また、この非特許文献２の量子回路では、２つの２進数ａ＝ａｎ−１…ａ０及びｂ＝ｂｎ−１…ｂ０を示す２ｎ個のキュービット｜ａ０＞，…，｜ａｎ−１＞，｜ｂ０＞，…，｜ｂｎ−１＞と、０または１のｚを示す１個のキュービット｜ｚ＞とを入力として用いる。なお、図２２（ａ）は、ａ，ｂがそれぞれ５キュービット（ｎ＝５）によって表される場合の例であるが、これをｎキュービットビット同士の加算回路に拡張することは容易である。
ここで、量子フーリエ変換は線形深さの演算で実現できることが知られている。また、図２２（ａ）を構成する制御回転Ｒｋも線形深さの演算で実現できる。よって、非特許文献２の量子回路は、補助ビットを用いることなく、線形深さで演算を行う量子回路である。
【非特許文献１】S. A. Cuccaro, T. G. Draper, S. A. Kutin, A new quantum ripple-carry addition circuit，[online], [平成１７年５月２５日検索]，インターネット＜http://arxiv.org/abs/quant-ph/0410184＞,2004
【非特許文献２】T. G. Draper, Addition on a Quantum Computer，[online], [平成１７年５月２５日検索]，インターネット＜http://arxiv.org/abs/quant-ph/0008033＞,2000
【発明の開示】
【発明が解決しようとする課題】
【０００９】
上述の非特許文献１の量子回路は、線形サイズ・線形深さによって演算を行う量子回路であるが、補助ビットが１つ必要となる。一方、非特許文献２の量子回路は、補助ビットを用いることなく線形深さで演算を行う量子回路であるが、入力桁数に対して２乗に比例した個数の基本演算を必要とする（線形サイズではない）。
通常、多数のキュービットを実現し、これらを協調的に操作することは物理的に困難である。よって、補助ビットはできるだけ少ないほうが良い。また、基本演算の個数が多いほど誤りが発生する可能性が大きくなるため、基本演算の個数はできるだけ少ないほうが良い。しかし、従来は、線形サイズ・線形深さで補助ビットを用いずに演算を行う量子回路は提案されていなかった。
【００１０】
本発明はこのような点に鑑みてなされたものであり、線形サイズ・線形深さで補助ビットを用いずに量子計算を行う技術的思想を提供することを目的とする。
【課題を解決するための手段】
【００１１】
以上の課題を解決するために、以下の発明が提供される。
第１の本発明では、２つの２進数ａ＝ａｎ−１…ａ０〔ａｉ∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝〕及びｂ＝ｂｎ−１…ｂ０〔ｂｉ∈｛０，１｝〕と、０または１のｚ〔ｚ∈｛０，１｝〕とに対し、ａ＋ｂ＝ｓｎ…ｓ０〔ｓｊ∈｛０，１｝，ｊ∈｛０，…，ｎ｝〕と、ｚ（＋）ｓｎを算出する。
第１の本発明では、まず、それぞれの初期量子状態が｜ｂ０＞，｜ａ０＞，…，｜ｂｎ−１＞，｜ａｎ−１＞，｜ｚ＞である２ｎ＋１個のキュービットＱ１，Ｑ２，…，Ｑ２ｎ＋１を対象とし、値分配部において、キュービットＱ２ｎ＋１，Ｑｋ＋２（ｋ＝１，…，２ｎ−２）に対するＣＮＯＴ演算操作を行う。
【００１２】
また、ＭＡＪ計算部において、キュービットＱ１，Ｑ２，Ｑ２ｎ＋１に対するトフォリ演算操作を行い、その操作の後、キュービットＱ２ｐ＋１，Ｑ２ｐ＋２，Ｑ２ｎ＋１に対するＭＡＪ演算操作とキュービットＱ２ｐ＋１，Ｑ２ｐ＋２，Ｑ１に対するトフォリ演算操作とをｐ＝１からｐ＝ｎ−２までｐを１ずつ増加させる順序で繰り返し、その繰り返しの後、キュービットＱ２ｎ−１，Ｑ２ｎ，Ｑ２ｎ＋１に対するＭＡＪ演算操作を行う。
また、第１逆計算部において、キュービットＱ１，Ｑ２ｑ＋４に対するＣＮＯＴ演算操作とキュービットＱ２ｑ＋１，Ｑ２ｑ＋２，Ｑ１に対するトフォリ演算操作とをｑ＝ｎ−２からｑ＝１までｑを１ずつ減少させる順序で繰り返す。
【００１３】
そして、第２逆計算部において、キュービットＱ２に対するＮＯＴ演算操作を行い、キュービットＱ１，Ｑ２，Ｑ２ｒ＋４（ｒ＝１，…，ｎ−２）に対するトフォリ演算操作を行い、その操作の後、キュービットＱ２に対するＮＯＴ演算操作を行い、さらにキュービットＱ１，Ｑ２，Ｑ４に対するトフォリ演算操作を行い、その操作の後、キュービットＱ２ｔ，Ｑ２ｔ−１（ｔ＝１，…，ｎ）に対するＣＮＯＴ演算操作を行う。
これにより、補助ビットを用いることなく、線形サイズ・線形深さで加算演算を行うことができる。
【００１４】
第２の本発明では、２つの２進数ａ＝ａｎ−１…ａ０〔ａｉ∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝〕及びｂ＝ｂｎ−１…ｂ０〔ｂｉ∈｛０，１｝〕に対し、（ａ＋ｂ）ｍｏｄ２ｎ＝ｓｎ−１…ｓ０〔（ｓｉ∈｛０，１｝〕を算出する。
第２の本発明では、まず、それぞれの初期量子状態が｜ｂ０＞，｜ａ０＞，…，｜ｂｎ−１＞，｜ａｎ−１＞である２ｎ個のキュービットＱ１，Ｑ２，…，Ｑ２ｎを対象とし、値分配部において、キュービットＱ２ｎ，Ｑｋ＋２（ｋ＝１，…，２ｎ−３）に対するＣＮＯＴ演算操作を行う。
【００１５】
また、ＭＡＪ計算部において、キュービットＱ１，Ｑ２，Ｑ２ｎに対するトフォリ演算操作を行い、その操作の後、キュービットＱ２ｐ＋１，Ｑ２ｐ＋２，Ｑ２ｎに対するＭＡＪ演算操作とキュービットＱ２ｐ＋１，Ｑ２ｐ＋２，Ｑ１に対するトフォリ演算操作とをｐ＝１からｐ＝ｎ−２までｐを１ずつ増加させる順序で繰り返し、キュービットＱ２ｎ，Ｑ２ｎ−１に対するＣＮＯＴ演算操作を行う。
また、第１逆計算部において、キュービットＱ１，Ｑ２ｑ＋４に対するＣＮＯＴ演算操作とキュービットＱ２ｑ＋１，Ｑ２ｑ＋２，Ｑ１に対するトフォリ演算操作とをｑ＝ｎ−２からｑ＝１までｑを１ずつ減少させる順序で繰り返す。
【００１６】
そして、第２逆計算部において、キュービットＱ２に対するＮＯＴ演算操作を行い、キュービットＱ１，Ｑ２，Ｑ２ｒ＋４（ｒ＝１，…，ｎ−２）に対するトフォリ演算操作を行い、その操作の後、キュービットＱ２に対するＮＯＴ演算操作を行い、さらにキュービットＱ１，Ｑ２，Ｑ４に対するトフォリ演算操作を行い、その操作の後、キュービットＱ２ｔ，Ｑ２ｔ−１（ｔ＝１，…，ｎ）に対するＣＮＯＴ演算操作を行う。
これにより、補助ビットを用いることなく、線形サイズ・線形深さで２ｎを法とした加算演算を行うことができる。
【００１７】
第３の本発明では、２つの２進数ａ＝ａｎ−１…ａ０〔ａｉ∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝〕及びｂ＝ｂｎ−１…ｂ０〔ｂｉ∈｛０，１｝〕と、０または１のｚ〔ｚ∈｛０，１｝〕とに対し、ａ−ｂ＝ｓｎ−１…ｓ０〔ｓｉ∈｛０，１｝〕とその符号ｓｎ〔ｓｎ∈｛０，１｝〕とを算出する。
第３の本発明では、まず、それぞれの初期量子状態が｜ｂ０＞，｜ａ０＞，…，｜ｂｎ−１＞，｜ａｎ−１＞，｜ｚ＞である２ｎ＋１個のキュービットＱ１，Ｑ２，…，Ｑ２ｎ＋１を対象とし、第１否定演算部において、キュービットＱ２ｈ（ｈ＝１，…，ｎ）に対するＮＯＴ演算操作を行う。
【００１８】
また、値分配部において、キュービットＱ２ｎ＋１，Ｑｋ＋２（ｋ＝１，…，２ｎ−２）に対するＣＮＯＴ演算操作を行う。
また、ＭＡＪ計算部において、キュービットＱ１，Ｑ２，Ｑ２ｎ＋１に対するトフォリ演算操作を行い、その操作の後、キュービットＱ２ｐ＋１，Ｑ２ｐ＋２，Ｑ２ｎ＋１に対するＭＡＪ演算操作とキュービットＱ２ｐ＋１，Ｑ２ｐ＋２，Ｑ１に対するトフォリ演算操作とをｐ＝１からｐ＝ｎ−２までｐを１ずつ増加させる順序で繰り返し、その繰り返しの後、キュービットＱ２ｎ−１，Ｑ２ｎ，Ｑ２ｎ＋１に対するＭＡＪ演算操作を行う。
【００１９】
また、第１逆計算部において、キュービットＱ１，Ｑ２ｑ＋４に対するＣＮＯＴ演算操作とキュービットＱ２ｑ＋１，Ｑ２ｑ＋２，Ｑ１に対するトフォリ演算操作とをｑ＝ｎ−２からｑ＝１までｑを１ずつ減少させる順序で繰り返す。
また、第２逆計算部において、キュービットＱ２に対するＮＯＴ演算操作を行い、キュービットＱ１，Ｑ２，Ｑ２ｒ＋４（ｒ＝１，…，ｎ−２）に対するトフォリ演算操作を行い、その操作の後、キュービットＱ２に対するＮＯＴ演算操作を行い、さらにキュービットＱ１，Ｑ２，Ｑ４に対するトフォリ演算操作を行い、その操作の後、キュービットＱ２ｔ，Ｑ２ｔ−１（ｔ＝１，…，ｎ）に対するＣＮＯＴ演算操作を行う。
【００２０】
そして、第２否定演算部において、キュービットＱｕ（ｕ＝１，…，２ｎ＋１）に対するＮＯＴ演算操作を行う。
これにより、補助ビットを用いることなく、線形サイズ・線形深さで減算演算を行うことができる。
第４の本発明では、２つの２進数ａ＝ａｎ−１…ａ０〔ａｉ∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝〕及びｂ＝ｂｎ−１…ｂ０〔ｂｉ∈｛０，１｝〕と、０または１のｚ〔ｚ∈｛０，１｝〕とに対し、ａ−ｂの符号ｙを算出する。
【００２１】
第４の本発明では、まず、それぞれの初期量子状態が｜ｂ０＞，｜ａ０＞，…，｜ｂｎ−１＞，｜ａｎ−１＞，｜ｚ＞である２ｎ＋１個のキュービットＱ１，Ｑ２，…，Ｑ２ｎ＋１を対象とし、第１否定演算部において、キュービットＱ２ｋ（ｋ＝１，…，ｎ）に対するＮＯＴ演算操作を行う。
また、値分配部において、キュービットＱ２ｎ＋１，Ｑｋ＋２（ｋ＝１，…，２ｎ−２）に対するＣＮＯＴ演算操作を行う。
また、ＭＡＪ計算部において、キュービットＱ１，Ｑ２，Ｑ２ｎ＋１に対するトフォリ演算操作を行い、その操作の後、キュービットＱ２ｐ＋１，Ｑ２ｐ＋２，Ｑ２ｎ＋１に対するＭＡＪ演算操作とキュービットＱ２ｐ＋１，Ｑ２ｐ＋２，Ｑ１に対するトフォリ演算操作とをｐ＝１からｐ＝ｎ−２までｐを１ずつ増加させる順序で繰り返し、その繰り返しの後、キュービットＱ２ｎ−１，Ｑ２ｎ，Ｑ２ｎ＋１に対するＭＡＪ演算操作を行う。
【００２２】
また、第１逆計算部において、キュービットＱ１，Ｑ２ｑ＋４に対するＣＮＯＴ演算操作とキュービットＱ１，Ｑ２ｑ＋３に対するＣＮＯＴ演算操作とキュービットＱ２ｑ＋１，Ｑ２ｑ＋２，Ｑ１に対するトフォリ演算操作とをｑ＝ｎ−２からｑ＝１までｑを１ずつ減少させる順序で繰り返す。
また、第２逆計算部において、キュービットＱ２に対するＮＯＴ演算操作を行い、その操作の後、キュービットＱ１，Ｑ２，Ｑ２ｒ＋４に対するトフォリ演算操作とキュービットＱ１，Ｑ２，Ｑ２ｒ＋３に対するトフォリ演算操作とをｒ＝ｎ−２からｒ＝１までｒを１ずつ減少させる順序で繰り返し、その繰り返しの後、キュービットＱ２に対するＮＯＴ演算操作を行い、キュービットＱ１，Ｑ２，Ｑ４に対するトフォリ演算操作を行い、キュービットＱ１，Ｑ２，Ｑ３に対するトフォリ演算操作を行う。
【００２３】
そして、第２否定演算部において、キュービットＱ２ｕ（ｕ＝１，…，ｎ）に対するＮＯＴ演算操作とキュービットＱ２ｎ＋１に対するＮＯＴ演算操作とを行う。
これにより、補助ビットを用いることなく、線形サイズ・線形深さで比較演算を行うことができる。
【発明の効果】
【００２４】
本発明では、補助ビットを用いることなく、線形サイズ・線形深さで量子演算を行うことができる。
【発明を実施するための最良の形態】
【００２５】
以下、本発明の実施の形態を図面を参照して説明する。
〔第１の実施の形態〕
第１の実施の形態は、２つの２進数ａ＝ａｎ−１…ａ０〔ａｉ∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝〕及びｂ＝ｂｎ−１…ｂ０〔ｂｉ∈｛０，１｝〕と、０または１のｚ〔ｚ∈｛０，１｝〕とに対し、ａ＋ｂ＝ｓｎ…ｓ０〔ｓｊ∈｛０，１｝，ｊ∈｛０，…，ｎ｝〕と、ｚ（＋）ｓｎとを算出し、ｓｎ−１…ｓ０とｚ（＋）ｓｎとａとを出力する例である。すなわち、本形態では、補助ビットを用いることなく、線形サイズ・線形深さで加算演算を行う。
【００２６】
＜ブロック構成＞
図１は、第１の実施の形態における量子演算装置１の構成を例示したブロック図である。
この図に例示するように、本形態の量子演算装置１は、CNOT演算操作部１１を具備する値分配部１０と、トフォリ演算操作部２１及びMAJ演算操作部２２を具備するMAJ計算部２０と、CNOT演算操作部３１及びトフォリ演算操作部３２を具備する第１逆計算部３０と、NOT演算操作部４１、トフォリ演算操作部４２及びCNOT演算操作部４３を具備する第２逆計算部４０と、メモリ５１を具備する制御部５０と、２ｎ＋１個のキュービット（Ｑ１，Ｑ２，…，Ｑ２ｎ＋１）６０とを有している。なお、２ｎ＋１個のキュービット６０それぞれの初期量子状態は、上述の入力値ａ，ｂ，ｚに対応する｜ｂ０＞，｜ａ０＞，…，｜ｂｎ−１＞，｜ａｎ−１＞，｜ｚ＞である。
【００２７】
＜ハードウェア構成＞
本形態の量子演算装置１は、量子コンピュータによって実現できる。量子コンピュータの実現する物理系としては、例えば、キュービットとして光子の偏光や光路を用いる方法（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）、イオントラップを用いる方法（J. I. Cirac and P. Zoller, Quantum computations with cold trapped ions, Physical Review Letter 74;4091, 1995）、量子ドット中の電子スピンを用いる方法（D. Loss and D. P. DiVincenzo, Quantum computation with quantum dots, Physical Review A 57, 120-126, 1998）、超伝導素子を用いる方法（Y. Nakamura, Yu. A. Pashkin and J. S. Tsai, Coherent control of macroscopic quantum states in a single-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」に詳しい。
【００２８】
以下に、量子演算装置１を実現するための具体的なハードウェア構成を例示する。
＜キュービット６０＞
キュービットとして光子の偏光を用いる場合には、例えば、パラメトリックダウンコンバージョン（ＰＤＣ：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.」等参照。）により生成された２ｎ＋１個の単一光子を用いる。また、キュービット６０それぞれの初期量子状態は、例えば、他の演算の量子回路による操作によって得られたものを用いる。また、パラメトリックダウンコンバージョン等により生成された単一光子に、ビームスプリッタや偏光回転素子等によって実現されるウォルシューアダマール変換、ＣＮＯＴ、Ｒｚ回転等の操作を行い、上述の初期量子状態を生成することとしてもよい。
【００２９】
また、核スピンをキュービットとして用いる場合には、例えば、「T. D. Ladd, et al., "All-Silicon quantum computer," Phys. Rev. Lett., vol. 89, no. 1, 017901-1‐017901-4, July 1, 2002.」に記載されているようにＳｉ（１１１）基板等に各キュービットを生成する。なお、キュービットの初期量子状態は、例えば、他の演算の量子回路による操作によって得られたものを用いてもよいし、各キュービットが生成された基板をｍＫ（ミリケルビン）オーダー以下に冷却してスピンの向きを揃えた後、所定の電磁波パルスを印加して生成してもよい。
【００３０】
その他、上記の文献に記載された方法でキュービットを用意することとしてもよい。
また、演算前後や演算途中においてキュービットの量子状態を保存する必要がある場合には、例えば、量子ドット内の電子準位、核スピン、あるいは超伝導体内部の電荷（クーパー対）量をキュービットとして用いてデータを保存する量子メモリ等を用いてもよい（A.Barenco, D.Deutsch, and A.Ekert, Phys. Rev. Lett.74,4083(1995)、松枝秀明  電子情報通信学会誌  A Vol.J81-A No.12(1998)1978、T.H.Oosterkamp et.al., Nature 395,873(1998)、D.Loss and D.P. DiVincenzo, Phys. Rev. A57(1998) 120. T.Oshima, quant-ph/0002004, http://arxiv.org/abs/quant-ph/0002004、B.E.Kane, A silicon-based nuclear spin quantum computer, Nature, 393, 133(1998)、
1117524573359_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）ＲＡＭ等の読書き可能な半導体メモリでもよいし、上述の量子メモリでもよい。
＜処理＞
次に、本形態における量子演算装置１の処理について説明する。
【００３４】
図２及び図３は、第１の実施の形態における量子演算装置１の処理を説明するためのフローチャートである。また、図４（ａ）は、ステップＳ１からＳ４による量子操作を示した量子回路であり、図４（ｂ）は、ステップＳ５からＳ１１による量子操作を示した量子回路であり、図５（ａ）は、ステップＳ１２からＳ１６による量子操作を示した量子回路であり、図５（ｂ）は、ステップＳ１７からＳ２７による量子操作を示した量子回路である。なお、図４及び図５はｎ＝５の場合の例である。
量子演算装置１は、制御部５０の制御のもと、初期量子状態が｜ｂ０＞，｜ａ０＞，…，｜ｂｎ−１＞，｜ａｎ−１＞，｜ｚ＞である２ｎ＋１個のキュービット（Ｑ１，Ｑ２，…，Ｑ２ｎ＋１）６０に対し、以下の各処理を実行する。
【００３５】
［図４（ａ）］
まず、制御部５０は、変数ｋに１を代入しメモリ５１に格納する（ステップＳ１）。次に、制御部５０はメモリ５１に格納された変数ｋを読み込み、この変数ｋに応じた命令を値分配部１０に与える。これに対し、値分配部１０は、ＣＮＯＴ演算操作部１１においてキュービットＱ２ｎ＋１，Ｑｋ＋２に対するＣＮＯＴ演算操作（制御ビットＱ２ｎ＋１，目標ビットＱｋ＋２）を行う（ステップＳ２）。次に、制御部５０は、メモリ５１に格納された変数ｋを読み込み、この変数ｋが２ｎ−２であるか否かを判断する（ステップＳ３）。なお、ｎは事前に設定される値である。ここで、ｋ＝２ｎ−２でなければ、制御部５０は、メモリ５１の変数ｋに１を加えた値を新たなｋとしてメモリ５１に格納し、処理をステップＳ２に戻す（ステップＳ４）。
【００３６】
［図４（ｂ）］
一方、ｋ＝２ｎ−２であれば、制御部５０は、ＭＡＪ計算部２０に指示を与え、ＭＡＪ計算部２０は、トフォリ演算操作部２１において、キュービットＱ１，Ｑ２，Ｑ２ｎ＋１に対するトフォリ演算操作（制御ビットＱ１，Ｑ２，目標ビットＱ２ｎ＋１）を行う（ステップＳ５）。次に、制御部５０は、変数ｐに１を代入しメモリ５１に格納する（ステップＳ６）。次に、制御部５０はメモリ５１に格納された変数ｐを読み込み、この変数ｐに応じた命令をＭＡＪ計算部２０に与える。これを受けたＭＡＪ計算部２０は、ＭＡＪ演算操作部２２において、キュービットＱ２ｐ＋１，Ｑ２ｐ＋２，Ｑ２ｎ＋１に対するＭＡＪ演算操作（図２３（ａ）の入力（１）としてＱ２ｐ＋１、入力（２）としてＱ２ｐ＋２、入力（３）としてＱ２ｎ＋１）を行う（ステップＳ７）。次に、ＭＡＪ計算部２０は、トフォリ演算操作部２１において、キュービットＱ２ｐ＋１，Ｑ２ｐ＋２，Ｑ１に対するトフォリ演算操作（制御ビットＱ２ｐ＋１，Ｑ２ｐ＋２、目標ビットＱ１）を行う（ステップＳ８）。
【００３７】
次に、制御部５０は、メモリ５１に格納された変数ｐを読み込み、この変数ｐがｎ−２であるか否かを判断する（ステップＳ９）。ここで、ｐ＝ｎ−２でなければ、制御部５０は、メモリ５１の変数ｐに１を加えた値を新たなｐとしてメモリ５１に格納し、処理をステップＳ７に戻す（ステップＳ１０）。一方、ｐ＝ｎ−２であれば、ＭＡＪ計算部２０に命令を与え、ＭＡＪ計算部２０は、ＭＡＪ演算操作部２２において、キュービットＱ２ｎ−１，Ｑ２ｎ，Ｑ２ｎ＋１に対するＭＡＪ演算操作（図２３（ａ）の入力（１）としてＱ２ｎ−１、入力（２）としてＱ２ｎ、入力（３）としてＱ２ｎ＋１）を行う（ステップＳ１１）。
【００３８】
［図５（ａ）］
次に、制御部５０は、変数ｑにｎ−２を代入しメモリ５１に格納する（ステップＳ１２）。次に、制御部５０はメモリ５１に格納された変数ｑを読み込み、この変数ｑに応じた命令を第１逆計算部３０に与える。これを受けた第１逆計算部３０は、ＣＮＯＴ演算操作部３１において、キュービットＱ１，Ｑ２ｑ＋４に対するＣＮＯＴ演算操作（制御ビットＱ１、目標ビットＱ２ｑ＋４）を行う（ステップＳ１３）。次に、トフォリ演算操作部３２において、キュービットＱ２ｑ＋１，Ｑ２ｑ＋２，Ｑ１に対するトフォリ演算操作（制御ビットＱ２ｑ＋１，Ｑ２ｑ＋２、目標ビットＱ１）を行う（ステップＳ１４）。
【００３９】
次に、制御部５０は、メモリ５１に格納された変数ｑを読み込み、この変数ｑが１であるか否かを判断する（ステップＳ１５）。ここで、ｑ＝１でなければ、制御部５０は、メモリ５１の変数ｑから１を引いた値を新たなｑとしてメモリ５１に格納し、処理をステップＳ１３に戻す（ステップＳ１６）。
［図５（ｂ）］
一方、ｑ＝１でなければ、制御部５０は、第２逆計算部４０に指示を与え、第２逆計算部４０は、ＮＯＴ演算操作部４１において、キュービットＱ２に対するＮＯＴ演算操作を行う（ステップＳ１７）。次に、制御部５０は、変数ｒにｎ−２を代入しメモリ５１に格納する（ステップＳ１８）。次に、制御部５０は、メモリ５１に格納された変数ｒを読み込み、この変数ｒに応じた命令を第２逆計算部４０に与える。これを受けた第２逆計算部４０は、トフォリ演算操作部４２において、キュービットＱ１，Ｑ２，Ｑ２ｒ＋４に対するトフォリ演算操作（制御ビットＱ１，Ｑ２、目標ビットＱ２ｒ＋４）を行う（ステップＳ１９）。
【００４０】
次に、制御部５０は、メモリ５１に格納された変数ｒを読み込み、この変数ｒが１であるか否かを判断する（ステップＳ２０）。ここで、ｒ＝１でなければ、制御部５０は、メモリ５１の変数ｒから１を引いた値を新たなｒとしてメモリ５１に格納し、処理をステップＳ１９に戻す（ステップＳ２１）。一方、ｒ＝１であれば、ＮＯＴ演算操作部４１において、キュービットＱ２に対するＮＯＴ演算操作を行い（ステップＳ２２）、トフォリ演算操作部４２において、キュービットＱ１，Ｑ２，Ｑ４に対するトフォリ演算操作（制御ビットＱ１，Ｑ２、目標ビットＱ４）を行う（ステップＳ２３）。
【００４１】
次に、制御部５０は、変数ｔに１を代入しメモリ５１に格納する（ステップＳ２４）。次に、制御部５０は、メモリ５１に格納された変数ｔを読み込み、この変数ｔに応じた命令を第２逆計算部４０に与える。これを受けた第２逆計算部４０は、Ｑ２ｔ，Ｑ２ｔ−１に対するＣＮＯＴ演算操作（制御ビットＱ２ｔ、目標ビットＱ２ｔ−１）を行う（ステップＳ２５）。
次に、制御部５０は、メモリ５１に格納された変数ｔを読み込み、この変数ｔがｎであるか否かを判断する（ステップＳ２６）。ここで、ｔ＝ｎでなければ、制御部５０は、メモリ５１の変数ｔに１を加算した値を新たなｔとしてメモリ５１に格納し、処理をステップＳ２５に戻す（ステップＳ２７）。一方、ｔ＝ｎであれば、制御部５０は、処理を終了させる。
【００４２】
以上の処理により、キュービットＱ２ｆ＋１（ｆ＝０，…，ｎ−１）の量子状態がそれぞれａとｂとの合計値の各桁を示すｓｆとなり、キュービットＱ２ｆ＋２の量子状態がそれぞれａの各桁を示すａｆとなり、キュービットＱ２ｎ＋１の量子状態がｚ（＋）ｓｎとなる。そして、これらの処理において補助ビットは不要であり、これらは線形サイズ・線形深さの演算である。
〔第２の実施の形態〕
第２の実施の形態では、２つの２進数ａ＝ａｎ−１…ａ０〔ａｉ∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝〕及びｂ＝ｂｎ−１…ｂ０〔ｂｉ∈｛０，１｝〕に対し、（ａ＋ｂ）ｍｏｄ２ｎ＝ｓｎ−１…ｓ０〔ｓｉ∈｛０，１｝〕を算出し、ｓｎ−１…ｓ０とａとを出力する。すなわち、本形態では、補助ビットを用いることなく、線形サイズ・線形深さで２ｎを法とした加算演算を行う。以下では、第１の実施の形態との相違点を中心に説明し、第１の実施の形態と共通する事項については説明を省略する。
【００４３】
＜ブロック構成＞
図６は、第２の実施の形態における量子演算装置１００の構成を例示したブロック図である。なお、この図において第１の実施の形態と共通する事項については、図１と同じ符号を付した。
この図に例示するように、本形態の量子演算装置１００は、CNOT演算操作部１１１を具備する値分配部１１０と、トフォリ演算操作部１２１、MAJ演算操作部１２２及びＣＮＯＴ演算操作部１２３を具備するMAJ計算部１２０と、CNOT演算操作部３１及びトフォリ演算操作部３２を具備する第１逆計算部３０と、NOT演算操作部４１、トフォリ演算操作部４２及びCNOT演算操作部４３を具備する第２逆計算部４０と、メモリ５１を具備する制御部５０と、２ｎ個のキュービット（Ｑ１，Ｑ２，…，Ｑ２ｎ）１６０とを有している。なお、２ｎ個のキュービット１６０それぞれの初期量子状態は、上述の入力値ａ，ｂに対応する｜ｂ０＞，｜ａ０＞，…，｜ｂｎ−１＞，｜ａｎ−１＞である。
【００４４】
＜ハードウェア構成＞
第１の実施の形態と同様であるため、説明を省略する。
＜処理＞
次に、本形態における量子演算装置１００の処理について説明する。
図７及び図８は、第２の実施の形態における量子演算装置１００の処理を説明するためのフローチャートである。また、図９（ａ）は、ステップＳ４１からＳ４４による量子操作を示した量子回路であり、図９（ｂ）は、ステップＳ４５からＳ５１による量子操作を示した量子回路である。なお、図９はｎ＝５の場合の例である。
【００４５】
量子演算装置１００は、制御部５０の制御のもと、初期量子状態が｜ｂ０＞，｜ａ０＞，…，｜ｂｎ−１＞，｜ａｎ−１＞である２ｎ個のキュービット（Ｑ１，Ｑ２，…，Ｑ２ｎ）１６０に対し、以下の各処理を実行する。
［図９（ａ）］
まず、制御部５０は、変数ｋに１を代入しメモリ５１に格納する（ステップＳ４１）。次に、制御部５０はメモリ５１に格納された変数ｋを読み込み、この変数ｋに応じた命令を値分配部１１０に与える。これに対し、値分配部１１０は、ＣＮＯＴ演算操作部１１１においてキュービットＱ２ｎ，Ｑｋ＋２に対するＣＮＯＴ演算操作（制御ビットＱ２ｎ，目標ビットＱｋ＋２）を行う（ステップＳ４２）。
【００４６】
次に、制御部５０は、メモリ５１に格納された変数ｋを読み込み、この変数ｋが２ｎ−３であるか否かを判断する（ステップＳ４３）。ここで、ｋ＝２ｎ−３でなければ、制御部５０は、メモリ５１の変数ｋに１を加えた値を新たなｋとしてメモリ５１に格納し、処理をステップＳ４２に戻す（ステップＳ４４）。
［図９（ｂ）］
一方、ｋ＝２ｎ−３であれば、制御部５０は、ＭＡＪ計算部１２０に指示を与え、ＭＡＪ計算部１２０は、トフォリ演算操作部１２１において、キュービットＱ１，Ｑ２，Ｑ２ｎに対するトフォリ演算操作（制御ビットＱ１，Ｑ２，目標ビットＱ２ｎ）を行う（ステップＳ４５）。
【００４７】
次に、制御部５０は、変数ｐに１を代入しメモリ５１に格納する（ステップＳ４６）。次に、制御部５０はメモリ５１に格納された変数ｐを読み込み、この変数ｐに応じた命令をＭＡＪ計算部１２０に与える。これを受けたＭＡＪ計算部１２０は、ＭＡＪ演算操作部１２２において、キュービットＱ２ｐ＋１，Ｑ２ｐ＋２，Ｑ２ｎに対するＭＡＪ演算操作（図２３（ａ）の入力（１）としてＱ２ｐ＋１、入力（２）としてＱ２ｐ＋２、入力（３）としてＱ２ｎ）を行う（ステップＳ４７）。次に、ＭＡＪ計算部１２０は、トフォリ演算操作部１２１において、キュービットＱ２ｐ＋１，Ｑ２ｐ＋２，Ｑ１に対するトフォリ演算操作（制御ビットＱ２ｐ＋１，Ｑ２ｐ＋２、目標ビットＱ１）を行う（ステップＳ４８）。
【００４８】
次に、制御部５０は、メモリ５１に格納された変数ｐを読み込み、この変数ｐがｎ−２であるか否かを判断する（ステップＳ４９）。ここで、ｐ＝ｎ−２でなければ、制御部５０は、メモリ５１の変数ｐに１を加えた値を新たなｐとしてメモリ５１に格納し、処理をステップＳ４７に戻す（ステップＳ５０）。一方、ｐ＝ｎ−２であれば、ＭＡＪ計算部１２０に命令を与え、ＭＡＪ計算部１２０は、ＣＮＯＴ演算操作部１２３において、キュービットＱ２ｎ，Ｑ２ｎ−１に対するＣＮＯＴ演算操作（制御ビットＱ２ｎ、目標ビットＱ２ｎ−１）を行う（ステップＳ５１）。
【００４９】
その後、第１の実施の形態におけるステップＳ１２からＳ２７と同じ処理をキュービット１６０に対して実行する（ステップＳ６２からＳ７７）。
以上の処理により、キュービットＱ２ｆ＋１（ｆ＝０，…，ｎ−１）の量子状態がそれぞれ（ａ＋ｂ）ｍｏｄ２ｎの各桁を示すｓｆとなり、キュービットＱ２ｆ＋２の量子状態がそれぞれａの各桁を示すａｆとなる。そして、これらの処理において補助ビットは不要であり、これらは線形サイズ・線形深さの演算である。
〔第３の実施の形態〕
第３の実施の形態では、２つの２進数ａ＝ａｎ−１…ａ０〔ａｉ∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝〕及びｂ＝ｂｎ−１…ｂ０〔ｂｉ∈｛０，１｝〕と、０または１のｚ〔ｚ∈｛０，１｝〕とに対し、ａ−ｂ＝ｓｎ−１…ｓ０〔ｓｉ∈｛０，１｝〕とその符号ｓｎ〔ｓｎ∈｛０，１｝〕とを算出し、ｚ（＋）ｓｎとｓｎ−１…ｓ０とａとを出力する。ここで、符号ｓｎは、ｂ≦ａであれば１、ｂ＞ａであれば０である。また、負の数の表現には、２の補数表現を用いる。すなわち、ｒ＝ｒｎ−１…ｒ０を正の数としたとき、−ｒをｒ’ｎ−１…ｒ０’で表す。ここでｒｉ’はｒｉの否定（ビットの反転）を表す。すなわち、本形態では、補助ビットを用いることなく、線形サイズ・線形深さで減算演算を行う。以下では、第１の実施の形態との相違点を中心に説明し、第１の実施の形態と共通する事項については説明を省略する。
【００５０】
＜ブロック構成＞
図１０は、第３の実施の形態における量子演算装置２００の構成を例示したブロック図である。なお、この図において第１の実施の形態と共通する事項については、図１と同じ符号を付した。
この図に例示するように、本形態の量子演算装置２００は、CNOT演算操作部１１を具備する値分配部１０と、トフォリ演算操作部２１、MAJ演算操作部２２を具備するMAJ計算部２０と、CNOT演算操作部３１及びトフォリ演算操作部３２を具備する第１逆計算部３０と、NOT演算操作部４１、トフォリ演算操作部４２及びCNOT演算操作部４３を具備する第２逆計算部４０と、ＮＯＴ演算操作部２７１を具備する第１否定演算部２７０と、ＮＯＴ演算操作部２８１を具備する第２否定演算部２８０と、メモリ５１を具備する制御部５０と、２ｎ＋１個のキュービット（Ｑ１，Ｑ２，…，Ｑ２ｎ＋１）６０とを有している。なお、２ｎ＋１個のキュービット６０それぞれの初期量子状態は、上述の入力値ａ，ｂ，ｚに対応する｜ｂ０＞，｜ａ０＞，…，｜ｂｎ−１＞，｜ａｎ−１＞，｜ｚ＞である。
【００５１】
＜ハードウェア構成＞
第１の実施の形態と同様であるため、説明を省略する。
＜処理＞
次に、本形態における量子演算装置２００の処理について説明する。
図１１から図１３は、第３の実施の形態における量子演算装置２００の処理を説明するためのフローチャートである。また、図１４（ａ）は、ステップＳ８１からＳ８４による量子操作を示した量子回路であり、図１４（ｂ）は、ステップＳ１１２からＳ１１４による量子操作を示した量子回路である。なお、図１４はｎ＝５の場合の例である。
【００５２】
量子演算装置２００は、制御部５０の制御のもと、それぞれの初期量子状態が｜ｂ０＞，｜ａ０＞，…，｜ｂｎ−１＞，｜ａｎ−１＞，｜ｚ＞である２ｎ＋１個のキュービット（Ｑ１，Ｑ２，…，Ｑ２ｎ＋１）６０に対し、以下の各処理を実行する。
［図１４（ａ）］
まず、制御部５０は、変数ｈに１を代入しメモリ５１に格納する（ステップＳ８１）。次に、制御部５０はメモリ５１に格納された変数ｈを読み込み、この変数ｈに応じた命令を第１否定演算部２７０に与える。これに対し、第１否定演算部２７０は、ＮＯＴ演算操作部２７１において、キュービットＱ２ｈに対するＮＯＴ演算操作を行う（ステップＳ８２）。
【００５３】
次に、制御部５０は、メモリ５１に格納された変数ｈを読み込み、この変数ｈがｎであるか否かを判断する（ステップＳ８３）。ここで、ｈ＝ｎでなければ、制御部５０は、メモリ５１の変数ｈに１を加えた値を新たなｈとしてメモリ５１に格納し、処理をステップＳ８２に戻す（ステップＳ８４）。
一方、ｈ＝ｎであれば、制御部５０は、第１の実施の形態におけるステップＳ１からＳ２７と同じ処理を行う（ステップＳ８１からＳ１１１）。
［図１４（ｂ）］
そして、ステップＳ１１０において制御部５０がｔ＝ｎであると判断した場合、制御部５０は、変数ｕに１を代入しメモリ５１に格納する（ステップＳ１１２）。次に、制御部５０はメモリ５１に格納された変数ｕを読み込み、この変数ｕに応じた命令を第２否定演算部２８０に与える。これに対し、第２否定演算部２８０は、ＮＯＴ演算操作部２８１において、キュービットＱｕに対するＮＯＴ演算操作を行う（ステップＳ１１３）。
【００５４】
次に、制御部５０は、メモリ５１に格納された変数ｕを読み込み、この変数ｕが２ｎ＋１であるか否かを判断する（ステップＳ１１４）。ここで、ｕ＝２ｎ＋１でなければ、制御部５０は、メモリ５１の変数ｕに１を加えた値を新たなｕとしてメモリ５１に格納し、処理をステップＳ１１３に戻す（ステップＳ１１５）。一方、ｕ＝２ｎ＋１であれば、制御部５０は、処理を終了させる。
以上の処理により、キュービットＱ２ｆ＋１（ｆ＝０，…，ｎ−１）の量子状態がそれぞれａ−ｂの各桁を示すｓｆとなり、キュービットＱ２ｆ＋２の量子状態がそれぞれａの各桁を示すａｆとなり、キュービットＱ２ｎ＋１の量子状態がｚ（＋）ｓｎとなる。そして、これらの処理において補助ビットは不要であり、これらは線形サイズ・線形深さの演算である。
【００５５】
〔第４の実施の形態〕
第４の実施の形態では、２つの２進数ａ＝ａｎ−１…ａ０〔ａｉ∈｛０，１｝，ｉ∈｛０，…，ｎ−１｝〕及びｂ＝ｂｎ−１…ｂ０〔ｂｉ∈｛０，１｝〕と、０または１のｚ〔ｚ∈｛０，１｝〕とに対し、ａ−ｂの符号ｙを算出し、ｚ（＋）ｙとａとｂとを出力する。すなわち、本形態では、補助ビットを用いることなく、線形サイズ・線形深さでａとｂの比較演算を行う。以下では、第１，３の実施の形態との相違点を中心に説明し、第１，３の実施の形態と共通する事項については説明を省略する。
【００５６】
＜ブロック構成＞
図１５は、第４の実施の形態における量子演算装置３００の構成を例示したブロック図である。なお、この図において第１，３の実施の形態と共通する事項については、図１及び図１０と同じ符号を付した。
この図に例示するように、本形態の量子演算装置３００は、CNOT演算操作部１１を具備する値分配部１０と、トフォリ演算操作部２１、MAJ演算操作部２２を具備するMAJ計算部２０と、CNOT演算操作部３３１及びトフォリ演算操作部３３２を具備する第１逆計算部３３０と、NOT演算操作部３４１及びトフォリ演算操作部３４２を具備する第２逆計算部３４０と、ＮＯＴ演算操作部２７１を具備する第１否定演算部２７０と、ＮＯＴ演算操作部３８１を具備する第２否定演算部３８０と、メモリ５１を具備する制御部５０と、２ｎ＋１個のキュービット（Ｑ１，Ｑ２，…，Ｑ２ｎ＋１）６０とを有している。なお、２ｎ＋１個のキュービット６０それぞれの初期量子状態は、上述の入力値ａ，ｂ，ｚに対応する｜ｂ０＞，｜ａ０＞，…，｜ｂｎ−１＞，｜ａｎ−１＞，｜ｚ＞である。
【００５７】
＜ハードウェア構成＞
第１の実施の形態と同様であるため、説明を省略する。
＜処理＞
次に、本形態における量子演算装置３００の処理について説明する。
図１６から図１８は、第４の実施の形態における量子演算装置３００の処理を説明するためのフローチャートである。また、図１９（ａ）は、ステップＳ１３６からＳ１４１による量子操作を示した量子回路であり、図１９（ｂ）は、ステップＳ１４２からＳ１５０による量子操作を示した量子回路である。図２０は、ステップＳ１５１からＳ１５５による量子操作を示した量子回路である。なお、図１９及び図２０はｎ＝５の場合の例である。
【００５８】
量子演算装置３００は、制御部５０の制御のもと、それぞれの初期量子状態が｜ｂ０＞，｜ａ０＞，…，｜ｂｎ−１＞，｜ａｎ−１＞，｜ｚ＞である２ｎ＋１個のキュービットＱ１，Ｑ２，…，Ｑ２ｎ＋１に対し、以下の各処理を実行する。
まず、第３の実施の形態におけるステップＳ８１からＳ９５と同じ処理を行う（ステップＳ１２１からＳ１３５）。
［図１９（ａ）］
次に、制御部５０は、変数ｑにｎ−２を代入しメモリ５１に格納する（ステップＳ１３６）。そして、制御部５０はメモリ５１に格納された変数ｑを読み込み、この変数ｑに応じた命令を第１逆計算部３３０に与える。これに対し、第１逆計算部３３０は、ＣＮＯＴ演算操作部３３１において、キュービットＱ１，Ｑ２ｑ＋４に対するＣＮＯＴ演算操作を行い（ステップＳ１３７）、キュービットＱ１，Ｑ２ｑ＋３に対するＣＮＯＴ演算操作を行う（ステップＳ１３８）。また、トフォリ演算操作部３４２において、キュービットＱ２ｑ＋１，Ｑ２ｑ＋２，Ｑ１に対するトフォリ演算操作を行う（ステップＳ１３９）。
【００５９】
次に、制御部５０は、メモリ５１に格納された変数ｑを読み込み、この変数ｑが１であるか否かを判断する（ステップＳ１４０）。ここで、ｑ＝１でなければ、制御部５０は、メモリ５１の変数ｑから１を減じた値を新たなｑとしてメモリ５１に格納し、処理をステップＳ１３７に戻す（ステップＳ１４１）。
［図１９（ｂ）］
一方、ｑ＝１であれば、制御部５０は、第２逆計算部３４０に指示を与え、これを受けた第２逆計算部３４０は、ＮＯＴ演算操作部３４１において、キュービットＱ２に対するＮＯＴ演算操作を行う（ステップＳ１４２）。
【００６０】
次に、制御部５０は、変数ｒにｎ−２を代入しメモリ５１に格納する（ステップＳ１４３）。そして、制御部５０はメモリ５１に格納された変数ｒを読み込み、この変数ｒに応じた命令を第２逆計算部３４０に与える。これに対し、第２逆計算部３４０は、トフォリ演算操作部３４２において、キュービットＱ１，Ｑ２，Ｑ２ｒ＋４に対するトフォリ演算操作を行い（ステップＳ１４４）、キュービットＱ１，Ｑ２，Ｑ２ｒ＋３に対するトフォリ演算操作を行う（ステップＳ１４５）。
次に、制御部５０は、メモリ５１に格納された変数ｒを読み込み、この変数ｒが１であるか否かを判断する（ステップＳ１４６）。ここで、ｒ＝１でなければ、制御部５０は、メモリ５１の変数ｒから１を減じた値を新たなｒとしてメモリ５１に格納し、処理をステップＳ１４４に戻す（ステップＳ１４７）。一方、ｒ＝１であれば、制御部５０は、第２逆計算部３４０に指示を与え、これを受けた第２逆計算部３４０は、ＮＯＴ演算操作部３４１において、キュービットＱ２に対するＮＯＴ演算操作を行う（ステップＳ１４８）。次に、トフォリ演算操作部３４２において、キュービットＱ１，Ｑ２，Ｑ４に対するトフォリ演算操作を行い（ステップＳ１４９）、キュービットＱ１，Ｑ２，Ｑ３に対するトフォリ演算操作を行う（ステップＳ１５０）。
【００６１】
［図２０］
次に、制御部５０は、変数ｕに１を代入しメモリ５１に格納する（ステップＳ１５１）。そして、制御部５０は、第２否定演算部３８０に指示を与え、これを受けた第２否定演算部３８０は、ＮＯＴ演算操作部３８１において、キュービットＱ２ｕ対するＮＯＴ演算操作を行う（ステップＳ１５２）。次に、制御部５０は、メモリ５１に格納された変数ｕを読み込み、この変数ｕがｎであるか否かを判断する（ステップＳ１５３）。ここで、ｕ＝ｎでなければ、制御部５０は、メモリ５１の変数ｕに１を加えた値を新たなｕとしてメモリ５１に格納し、処理をステップＳ１５２に戻す（ステップＳ１５４）。一方、ｕ＝ｎであれば、制御部５０は、第２否定演算部３８０に指示を与え、これを受けた第２否定演算部３８０は、ＮＯＴ演算操作部３８１において、キュービットＱ２ｎ＋１対するＮＯＴ演算操作を行う（ステップＳ１５５）。
【００６２】
以上の処理により、キュービットＱ２ｆ＋１（ｆ＝０，…，ｎ−１）の量子状態がそれぞれｂの各桁を示すｂｆとなり、キュービットＱ２ｆ＋２の量子状態がそれぞれａの各桁を示すａｆとなり、キュービットＱ２ｎ＋１の量子状態がｚ（＋）ｙとなる。そして、これらの処理において補助ビットは不要であり、これらは線形サイズ・線形深さの演算である。
なお、本発明は上述の実施の形態に限定されるものではない。例えば、本発明の趣旨を逸脱しない範囲で各処理の順序を入れ換えてもよく、複数の基本演算を同時に実行してもよい。例えば、第１の実施の形態において、ステップＳ１７の操作を、ｐ＝１におけるステップＳ７の操作と同時に実行してもよい。また、第３の実施の形態におけるステップＳ８１からＳ８４の処理の代わりに、ｈ＝１からｎに対応する全てのキュービットＱ２ｈのＮＯＴ演算を同時に行うこととしてもよい。これにより、より演算ステップ数を低減させることができる。
【００６３】
また、上述の実施の形態では特に述べなかったが、各キュービットの量子状態を複数の入力値の重ね合わせ状態とし、複数の演算を並行に処理することとしてもよい。
その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【産業上の利用可能性】
【００６４】
例えば、本発明を量子コンピュータに適用することにより、演算速度や演算精度の向上を実現できる。
【図面の簡単な説明】
【００６５】
【図１】図１は、第１の実施の形態における量子演算装置１の構成を例示したブロック図である。
【図２】図２は、第１の実施の形態における量子演算装置１の処理を説明するためのフローチャートである。
【図３】第１の実施の形態における量子演算装置１の処理を説明するためのフローチャートである。
【図４】図４（ａ）は、ステップＳ１からＳ４による量子操作を示した量子回路であり、図４（ｂ）は、ステップＳ５からＳ１１による量子操作を示した量子回路である。
【図５】図５（ａ）は、ステップＳ１２からＳ１６による量子操作を示した量子回路であり、図５（ｂ）は、ステップＳ１７からＳ２７による量子操作を示した量子回路である。
【図６】図６は、第２の実施の形態における量子演算装置の構成を例示したブロック図である。
【図７】図７は、第２の実施の形態における量子演算装置の処理を説明するためのフローチャートである。
【図８】図８は、第２の実施の形態における量子演算装置の処理を説明するためのフローチャートである。
【図９】図９（ａ）は、ステップＳ４１からＳ４４による量子操作を示した量子回路であり、図９（ｂ）は、ステップＳ４５からＳ５１による量子操作を示した量子回路である。
【図１０】図１０は、第３の実施の形態における量子演算装置の構成を例示したブロック図である。
【図１１】図１１は、第３の実施の形態における量子演算装置の処理を説明するためのフローチャートである。
【図１２】図１２は、第３の実施の形態における量子演算装置の処理を説明するためのフローチャートである。
【図１３】図１３は、第３の実施の形態における量子演算装置の処理を説明するためのフローチャートである。
【図１４】図１４（ａ）は、ステップＳ８１からＳ８４による量子操作を示した量子回路であり、図１４（ｂ）は、ステップＳ１１２からＳ１１４による量子操作を示した量子回路である。
【図１５】図１５は、第４の実施の形態における量子演算装置の構成を例示したブロック図である。
【図１６】図１６は、第４の実施の形態における量子演算装置の処理を説明するためのフローチャートである。
【図１７】図１７は、第４の実施の形態における量子演算装置の処理を説明するためのフローチャートである。
【図１８】図１８は、第４の実施の形態における量子演算装置の処理を説明するためのフローチャートである。
【図１９】図１９（ａ）は、ステップＳ１３６からＳ１４１による量子操作を示した量子回路であり、図１９（ｂ）は、ステップＳ１４２からＳ１５０による量子操作を示した量子回路である。
【図２０】図２０は、ステップＳ１５１からＳ１５５による量子操作を示した量子回路である。
【図２１】図２１は、非特許文献１に開示された量子回路を示した図である。
【図２２】図２２（ａ）は、非特許文献２に開示された量子回路を示した図である。図２２（ｂ）は、量子フーリエ変換回路を示した図である。
【図２３】図２３（ａ）は、ＭＡＪ量子回路を示した図であり、図２３（ｂ）は、ＵＭＡ量子回路を示した図である。
【図２４】図２４（ａ）はＮＯＴ演算の定義を、（ｂ）はＣＮＯＴ演算の定義を、（ｃ）はトフォリ演算の定義を、（ｄ）はアダマール変換演算の定義を、（ｅ）は制御回転演算の定義を、それぞれ示した図である。
【符号の説明】
【００６６】
１，１００，２００，３００  量子演算装置
【図１】
2006338185.tif 000004
【図２】
2006338185.tif 000005
【図３】
2006338185.tif 000006
【図４】
2006338185.tif 000007
【図５】
2006338185.tif 000008
【図６】
2006338185.tif 000009
【図７】
2006338185.tif 000010
【図８】
2006338185.tif 000011
【図９】
2006338185.tif 000012
【図１０】
2006338185.tif 000013
【図１１】
2006338185.tif 000014
【図１２】
2006338185.tif 000015
【図１３】
2006338185.tif 000016
【図１４】
2006338185.tif 000017
【図１５】
2006338185.tif 000018
【図１６】
2006338185.tif 000019
【図１７】
2006338185.tif 000020
【図１８】
2006338185.tif 000021
【図１９】
2006338185.tif 000022
【図２０】
2006338185.tif 000023
【図２１】
2006338185.tif 000024
【図２２】
2006338185.tif 000025
【図２３】
2006338185.tif 000026
【図２４】
2006338185.tif 000027