(57)【要約】【課題】  従来よりも少ない量子ビットを使って、位数発見に有用な２ｊ桁の２進数Ｃを高い確率で求める。【解決手段】  ２進数ｊ桁のＮ＝ｎｊ−１…ｎ０とＡ＝ａｊ−１…ａ０とをメモリに格納しておき（ｎｈ−１は２進数表記されたＮのｈ桁目の値、ａｈ−１は２進数表記されたＡのｈ桁目の値）、減算部が、メモリから読み込んだＮとＡとからＮ−Ａを算出する。また、ＣＯＭＰＡＲＩＳＯＮ演算部が、減算部で算出されたＮ−Ａを用い、Ｎよりも小さい２進数ｊ桁のＢ＝ｂｊ−１…ｂ０の各桁をそれぞれ示す量子状態の量子ビットＱＢｊ−１，…，ＱＢ０と、任意の量子状態の量子ビットＱＵｊ−１，…，ＱＵ１，ＱＺと、に対する第１量子操作を行い、Ｎ−Ａ＞Ｂの場合にのみ量子ビットＱＺの量子状態を反転させる。そして、ＣＯＭＰＡＲＩＳＯＮ演算部によって処理された量子ビットＱＺは、そのまま或いは反転されて、他の量子演算の制御ビットとして用いられる。【選択図】        図１５
2007087307.tif 000002
【特許請求の範囲】
【請求項１】
２進数ｊ桁のＮ＝ｎｊ−１…ｎ０と、Ｎよりも小さい２進数ｊ桁のＡ＝ａｊ−１…ａ０とから、ＡＲ＝１ ｍｏｄ Ｎを満たす最小のＲの算出に有用な値を算出する量子計算方法であって、
メモリに上記ＮとＡとを格納するステップと、
減算部が、上記メモリから読み込んだＮとＡとからＮ−Ａを算出するステップと、
ＣＯＭＰＡＲＩＳＯＮ演算部が、上記減算部で算出されたＮ−Ａを用い、Ｎよりも小さい２進数ｊ桁のＢ＝ｂｊ−１…ｂ０の各桁をそれぞれ示す量子状態の量子ビットＱＢｊ−１，…，ＱＢ０と、任意の量子状態の量子ビットＱＵｊ−１，…，ＱＵ１，ＱＺと、に対する第１量子操作を行い、Ｎ−Ａ＞Ｂの場合にのみ量子ビットＱＺの量子状態を反転させるステップと、を有し、
上記ＣＯＭＰＡＲＩＳＯＮ演算部によって処理された量子ビットＱＺは、そのまま或いは反転されて、他の量子演算の制御ビットとして用いられる、
ことを特徴とする量子計算方法。
【請求項２】
請求項１に記載の量子計算方法であって、
ＣＯＭＰＡＲＩＳＯＮ演算部が、任意の量子状態の量子ビットＱＤ１，ＱＤ２を制御ビットとし、上記第１量子操作を行うステップと、
ＱＦＴ演算部が、量子ビットＱＢｊ−１，…，ＱＢ０に対して量子フーリエ変換操作を施すステップと、
量子ビットＱＤ１，ＱＤ２，ＱＺを制御ビットとし、φＡＤＤ演算部が、１を示す量子状態の量子ビットＱＢｋ（ｋ∈｛ｊ−１，…，０｝）のみに対し、
【数１】
2007087307.tif 000007
（ただし、量子ビットＱＢｋの量子状態を｜ＱＢｋ〉とし、ｅをネピア数とし、ｉを虚数単位とする）の演算を施すステップと、
第１ＮＯＴ演算部が、量子ビットＱＺにＮＯＴ演算を施すステップと、
量子ビットＱＤ１，ＱＤ２，ＱＺを制御ビットとし、φＡＤＤ−１演算部が、１を示す量子状態の量子ビットＱＢｋのみに対し、
【数２】
2007087307.tif 000008
（ただし、Ｎ−Ａ＝（ｎ−ａ）ｊ−１…（ｎ−ａ）０とする）の演算を施すステップと、
第１ＮＯＴ演算部が、量子ビットＱＺにＮＯＴ演算を施すステップと、
ＱＦＴ−１演算部が、量子ビットＱＢｊ−１，…，ＱＢ０に対して量子フーリエ変換の逆演算操作を施すステップと、
ＣＯＭＰＡＲＩＳＯＮ演算部が、量子ビットＱＤ１，ＱＤ２を制御ビットとして、量子ビットＱＢｊ−１，…，ＱＢ０，ＱＵｊ−１，…，ＱＵ１，ＱＺに対し、Ａ＞Ｂの場合にのみ量子ビットＱＺの量子状態を反転させる量子操作を行うステップと、を有し、
第１Ｔｏｆｆｏｌｉ演算部が、量子ビットＱＤ１，ＱＤ２を制御ビットとし、量子ビットＱＺを目標ビットとしたＴｏｆｆｏｌｉ演算を施すステップと、
を有することを特徴とする量子計算方法。
【請求項３】
請求項２に記載の量子計算方法であって、
上記ＣＯＭＰＡＲＩＳＯＮ演算部が行う上記第１量子操作は、
ＨＩＧＨＢＩＴ演算部が、量子ビットＱＢｊ−１，…，ＱＢ０と、量子ビットＱＵｊ−１，…，ＱＵ１と、量子ビットＱＺと対して第２量子操作を行い、量子ビットＱＺを、ｚ（＋）β〔βはＡ−Ｎ＋Ｂの最上位桁、（＋）は排他的論理和〕を示す量子状態とし、他の量子ビットＱＢｊ−１，…，ＱＢ０、ＱＵｊ−１，…，ＱＵ１の量子状態を当該第２量子操作前の量子状態とするステップと、
第２ＮＯＴ演算部が、量子ビットＱＺにＮＯＴ演算を施すステップと、
古典制御ＮＯＴ演算部が、上記メモリから読み込まれたＡ−Ｎの桁（ａ−ｎ）ｈ（ｈ∈｛ｊ−１，…，０｝）が１となるｈに対応する量子ビットＱＢｈのみにＮＯＴ演算を施すステップと、
第３ＮＯＴ演算部が、各量子ビットＱＢｊ−１，…，ＱＢ０にＮＯＴ演算を施すステップと、
第２Ｔｏｆｆｏｌｉ演算部が、各量子ビットＱＢｊ−１，…，ＱＢ０を制御ビットとし、量子ビットＱＺを目標ビットとしたＴｏｆｆｏｌｉ演算を施すステップと、
第３ＮＯＴ演算部が、各量子ビットＱＢｊ−１，…，ＱＢ０にＮＯＴ演算を施すステップと、
古典制御ＮＯＴ演算部が、上記メモリから読み込まれたＡ−Ｎの桁（ａ−ｎ）ｈが１となるｈに対応する量子ビットＱＢｈのみにＮＯＴ演算を施すステップと、
を有することを特徴とする量子計算方法。
【請求項４】
２進数ｊ桁のＮ＝ｎｊ−１…ｎ０と、Ｎよりも小さい２進数ｊ桁のＡ＝ａｊ−１…ａ０とから、ＡＲ＝１ ｍｏｄ Ｎを満たす最小のＲの算出に有用な値を算出する量子計算装置であって、
上記ＮとＡとを格納するメモリと、
上記メモリから読み込んだＮとＡとからＮ−Ａを算出する減算部と、
上記減算部で算出されたＮ−Ａを用い、Ｎよりも小さい２進数ｊ桁のＢ＝ｂｊ−１…ｂ０の各桁をそれぞれ示す量子状態の量子ビットＱＢｊ−１，…，ＱＢ０と、任意の量子状態の量子ビットＱＵｊ−１，…，ＱＵ１，ＱＺと、に対する第１量子操作を行い、Ｎ−Ａ＞Ｂの場合にのみ量子ビットＱＺの量子状態を反転させるＣＯＭＰＡＲＩＳＯＮ演算部と、を有し、
上記ＣＯＭＰＡＲＩＳＯＮ演算部によって処理された量子ビットＱＺは、そのまま或いは反転されて、他の量子演算の制御ビットとして用いられる、
ことを特徴とする量子計算装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、量子コンピュータ分野に関し、特に、量子コンピュータを用いて位数発見に有用な数を得る技術に関する。
【背景技術】
【０００２】
ｊ桁の２進数ＮとＮより小さい２進数Ａとを入力とし、２ｊ＋３個の量子ビットを使って、ｊの４乗に比例した個数の基本演算をｊの３乗に比例した計算ステップ数で実行することにより、Ａのｍｏｄ Ｎに関する位数（すなわち、ＡＲ＝１ ｍｏｄ Ｎとなる最小の２進数Ｒ）の発見に有用な２ｊ桁の２進数Ｃを高い確率で出力する量子回路の構成方法が知られている（例えば、非特許文献１参照）。ここで、「位数発見に有用な２ｊ桁の２進数Ｃ」とは、非特許文献２の式（５．１３）のｃを意味する。このＣをｊに関する多項式個の基本演算を使った古典回路に入力することにより、Ａのｍｏｄ Ｎに関する位数Ｒ（非特許文献２ではｒ）を高い確率で求めることができる。
【０００３】
以下、非特許文献１に記載された従来の量子回路を概説する。なお、量子回路は、量子ビットに対する演算とＣＮＯＴ演算とを基本演算とするが、図が複雑になるのを避けるため、以下では、これらの演算以外の演算も使って量子回路を構成する。すなわち、この量子回路に使われる全ての演算は、１量子ビットに対する演算とＣＮＯＴ演算に分解できる（例えば、非特許文献３参照）。なお、各図はｊ＝５の場合であるが、これらの量子回路を一般のｊの場合に拡張することは容易である。また、入力に表れる各変数は、０又は１を表す。さらに、重ね合わせ状態に対する量子回路の出力は、各量子状態の線形結合により表現し、Ｎより大きい全ての数はｍｏｄ  Ｎで解釈される。また、｜・〉は・を示す量子状態を意味する。
【０００４】
図３１は、この位数発見に有用な値を発見する量子回路の従来構成を示した図である。なお、図３１の構成では、量子状態がそれぞれ｜０〉と｜１〉である２個の量子ビットと、量子状態｜０〉の２ｊ＋１個の量子ビットとに対して量子操作を行い、観測によって位数発見に有用な２ｊ桁の２進数ｃ２ｊ−１…ｃ０が得られる。なお、Ｈ，Ｘ，Ｒは、それぞれ図３２（ａ）（ｂ）及び図３３のように定義された演算子である。
図３４は、図３１におけるＣＵ（Ａ）＝ＣＵ（Ａ・２０）の演算の詳細を示した量子回路である。図３４に示すようにＣＵ（Ａ）は、ｄ∈｛０，１｝と、Ｕ＝ｕ０・・・ｕ４と、ｊ＋２個の０とをそれぞれ示す量子状態の入力に対し、ｄ＝１であれば、ｄとＡ・Ｕ  ｍｏｄ  Ｎの各桁（ｄとＡ・Ｕ  ｍｏｄ  Ｎ）０・・・（ｄとＡ・Ｕ  ｍｏｄ  Ｎ）４と、ｊ＋２個の０とをそれぞれ示す量子状態を生成し、ｄ＝０であれば、入力の量子状態をそのまま出力する。ここで、図３４のＣＳＷＡＰは、図３５のように示すような演算子である。また、図３５に用いられる各演算子の構成を図３６（ａ）（ｂ）及び図３７に示す。なお、図３１のＣＵ（Ａ・２１）・・・ＣＵ（Ａ・２９）は、図３４のＡをＡ・２１・・・Ａ・２９に置換したものになる。
【０００５】
図３８は、図３４におけるＣＭＵＬＴ（Ａ）ＭＯＤ（Ｎ）の演算の詳細を示した量子回路である。図３８に示すように、ＣＭＵＬＴ（Ａ）ＭＯＤ（Ｎ）は、ｄと、Ｕと、Ｂ＝ｂｊ−１…ｂ０の最上位ビットに０を加えた値と、０とをそれぞれ示す量子状態を入力とし、ｄ＝１であれば、ｄとＵとＡ・Ｕ＋Ｍ  ｍｏｄ  Ｎの各桁と０と０とをそれぞれ示す量子状態を生成し、ｄ＝０であれば、入力の量子状態をそのまま出力する。なお、ＣＭＵＬＴ（Ａ−１）ＭＯＤ（Ｎ）は、図３８のＡをＡ−１に置換したものになる。
図３９は、図３８におけるＱＦＴ（量子フーリエ変換）の演算の詳細を示した量子回路である。なお、図３９のＫ∈｛２，…，６｝は図４０のような演算子である。また、図３８のＱＦＴ−１は、ＱＦＴの逆演算を示す。
【０００６】
図４１は、図３８におけるφＡＤＤ（Ａ）ＭＯＤ（Ｎ）＝φＡＤＤ（２０・Ａ）ＭＯＤ（Ｎ）の演算の詳細を示した量子回路である。φＡＤＤ（Ａ）ＭＯＤ（Ｎ）は、ｄ１，ｄ２と、最上位ビットに０を加えたＢにＱＦＴを適用した値φｊ（Ｂ），…，φ０（Ｂ）と、０とをそれぞれ示す量子状態を入力とし、ｄ１＝ｄ２＝１であれば、ｄ１，ｄ２と、Ａ＋Ｂ  ｍｏｄ  ＮにＱＦＴを適用した値φｊ（Ａ＋Ｂ  ｍｏｄ  Ｎ），…，φ０（Ａ＋Ｂ  ｍｏｄ  Ｎ）と、０とをそれぞれ示す量子状態を生成し、ｄ１＝ｄ２＝１でなければ、入力の量子状態をそのまま出力する。なお、図４１におけるφＡＤＤ（Ａ）は、図４２に示すような演算子であり、最上位ビットに０を加えたＢにＱＦＴを適用した値φｊ（Ｂ），…，φ０（Ｂ）を示す量子状態を入力とし、Ａ＋ＢにＱＦＴを適用した値値φｊ（Ａ＋Ｂ），…，φ０（Ａ＋Ｂ）を示す量子状態を生成する。なお、図４２におけるσｋ（ｋ∈｛１，…，５｝）は、図４３に示すような演算子である。また、φＡＤＤ（Ａ）−１は、φＡＤＤ（Ａ）の逆演算である。また、φＡＤＤ（Ｎ）やφＡＤＤ（Ｎ）−１は、φＡＤＤ（Ａ）やφＡＤＤ（Ａ）−１のＡをＮに置換した演算子である。なお、その他のφＡＤＤ（Ａ・２１）ＭＯＤ（Ｎ）・・・φＡＤＤ（Ａ・２４）ＭＯＤ（Ｎ）については、図４１のＡをＡ・２１・・・Ａ・２４に置換したものになる。
【非特許文献１】S. BEAUREGARD, CIRCUIT FOR SHOR’S ALGORITHM USING 2N + 3 QUBITS, QUANTUM INFORMATION AND COMPUTATION, Vol. 3 No. 2, pp. 175‐185, 2003.
【非特許文献２】PETER W. SHOR, POLYNOMIAL-TIME ALGORITHMS FOR PRIME FACTORIZATION AND DISCRETE LOGARITHMS ON A QUANTUM COMPUTER, SIAM J. COMPUT, Vol. 26, No. 5, pp. 1484‐1509, October 1997.
【非特許文献３】M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, Cambridge, 2000.
【発明の開示】
【発明が解決しようとする課題】
【０００７】
上述のように、非特許文献１の量子回路では、ｊ桁の２進数Ｎと、Ｎより小さいｊ桁の２進数進数Ａとから、Ａのｍｏｄ Ｎに関する位数の発見に有用な２ｊ桁の２進数Ｃを高い確率で出力するためには、ｊの４乗に比例した個数の基本演算と、ｊの３乗に比例した計算ステップ数と、２ｊ＋３個の量子ビットとを必要とする。しかし、多数の量子ビットを実現し、協調的に操作するのは物理的に困難なため、量子ビット数はできるだけ少ないほうが良い。
本発明はこのような点に鑑みてなされたものであり、従来よりも少ない量子ビットを使って、位数発見に有用な２ｊ桁の２進数Ｃを高い確率で求めることを可能にする技術を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明では上記課題を解決するために、２進数ｊ桁のＮ＝ｎｊ−１…ｎ０とＡ＝ａｊ−１…ａ０とをメモリに格納しておき（ｎｈ−１は２進数表記されたＮのｈ桁目の値、ａｈ−１は２進数表記されたＡのｈ桁目の値）、減算部が、メモリから読み込んだＮとＡとからＮ−Ａを算出する。また、ＣＯＭＰＡＲＩＳＯＮ演算部が、減算部で算出されたＮ−Ａを用い、Ｎよりも小さい２進数ｊ桁のＢ＝ｂｊ−１…ｂ０の各桁をそれぞれ示す量子状態の量子ビットＱＢｊ−１，…，ＱＢ０と、任意の量子状態の量子ビットＱＵｊ−１，…，ＱＵ１，ＱＺと、に対する第１量子操作を行い、Ｎ−Ａ＞Ｂの場合にのみ量子ビットＱＺの量子状態を反転させる。そして、ＣＯＭＰＡＲＩＳＯＮ演算部によって処理された量子ビットＱＺは、そのまま或いは反転されて、他の量子演算の制御ビットとして用いられる。
【０００９】
ここで、このＣＯＭＰＡＲＩＳＯＮ演算部の処理内容は、非特許文献１では、図４１におけるφＡＤＤ（Ａ），φＡＤＤ（Ｎ）−１及びＱＦＴ−１の処理に包含されていたものである。しかし、従来の図４１の構成では、φＡＤＤ（Ａ），φＡＤＤ（Ｎ）−１及びＱＦＴ−１の処理が施された量子ビットの１つ（図４１の下から２個目の量子ビット）の量子状態を、ＣＮＯＴ演算によって他の量子ビット（図４１の最下部の量子ビット）に移し、この他の量子ビットを他の量子演算〔φＡＤＤ（Ｎ）〕の制御ビットとしなければならなかった。これに対し、本発明では、ＣＯＭＰＡＲＩＳＯＮ演算部によって処理された量子ビットＱＺそのものを他の量子演算の制御ビットとして用いることができる。そのため、従来、量子状態を移すために必要であった量子ビットを一つ削減できる。また、本発明では、ＣＯＭＰＡＲＩＳＯＮ演算部が、従来の図４１におけるφＡＤＤ（Ａ），φＡＤＤ（Ｎ）−１及びＱＦＴ−１が全く操作していなかった量子ビットＱＵｊ−１，…，ＱＵ１（値ｕ４，…，ｕ１の量子状態を示す量子ビット）の操作も行い、量子ビットの有効利用を図っている。これも本発明の構成が、従来よりも量子ビット数を削減できる理由である。
【００１０】
また、本発明において好ましくは、ＣＯＭＰＡＲＩＳＯＮ演算部が、任意の量子状態の量子ビットＱＤ１，ＱＤ２を制御ビットとして、上述の第１量子操作を行い、ＱＦＴ演算部が、量子ビットＱＢｊ−１，…，ＱＢ０に対して量子フーリエ変換操作を施す。そして、量子ビットＱＤ１，ＱＤ２，ＱＺを制御ビットとし、φＡＤＤ演算部が、１を示す量子状態の量子ビットＱＢｋ（ｋ∈｛ｊ−１，…，０｝）のみに対し、
【００１１】
【数３】
2007087307.tif 000003
（ただし、量子ビットＱＢｋの量子状態を｜ＱＢｋ〉とし、ｅをネピア数とし、ｉを虚数単位とする）の演算を施し、第１ＮＯＴ演算部が、量子ビットＱＺにＮＯＴ演算を施す。さらに、量子ビットＱＤ１，ＱＤ２，ＱＺを制御ビットとし、φＡＤＤ−１演算部が、１を示す量子状態の量子ビットＱＢｋのみに対し、
【００１２】
【数４】
2007087307.tif 000004
（ただし、Ｎ−Ａ＝（ｎ−ａ）ｊ−１…（ｎ−ａ）０とする）の演算を施し、第１ＮＯＴ演算部が、量子ビットＱＺにＮＯＴ演算を施す。そして、ＱＦＴ−１演算部が、量子ビットＱＢｊ−１，…，ＱＢ０に対して量子フーリエ変換の逆演算操作を施し、ＣＯＭＰＡＲＩＳＯＮ演算部が、量子ビットＱＤ１，ＱＤ２を制御ビットとして、量子ビットＱＢｊ−１，…，ＱＢ０，ＱＵｊ−１，…，ＱＵ１，ＱＺに対し、Ａ＞Ｂの場合にのみ量子ビットＱＺの量子状態を反転させる量子操作を行い、第１Ｔｏｆｆｏｌｉ演算部が、量子ビットＱＤ１，ＱＤ２を制御ビットとし、量子ビットＱＺを目標ビットとしたＴｏｆｆｏｌｉ演算を施す。
【００１３】
ここで、ＣＯＭＰＡＲＩＳＯＮ演算部の第１量子操作が施された量子ビットＱＺは、φＡＤＤ演算部やφＡＤＤ−１演算部の量子演算の制御ビットとして用いられている。これにより、従来構成に比べ量子ビット数を１つ削減できる。
また、本発明において好ましくは、ＣＯＭＰＡＲＩＳＯＮ演算部が行う第１量子操作は、ＨＩＧＨＢＩＴ演算部が、量子ビットＱＢｊ−１，…，ＱＢ０と、量子ビットＱＵｊ−１，…，ＱＵ１と、量子ビットＱＺと対して第２量子操作を行い、量子ビットＱＺを、ｚ（＋）β〔βはＡ−Ｎ＋Ｂの最上位桁、（＋）は排他的論理和〕を示す量子状態とし、他の量子ビットＱＢｊ−１，…，ＱＢ０、ＱＵｊ−１，…，ＱＵ１の量子状態を当該第２量子操作前の量子状態とし、第２ＮＯＴ演算部が、量子ビットＱＺにＮＯＴ演算を施し、古典制御ＮＯＴ演算部が、メモリから読み込まれたＡ−Ｎの桁（ａ−ｎ）ｈ（ｈ∈｛ｊ−１，…，０｝）が１となるｈに対応する量子ビットＱＢｈのみにＮＯＴ演算を施し、第３ＮＯＴ演算部が、各量子ビットＱＢｊ−１，…，ＱＢ０にＮＯＴ演算を施し、第２Ｔｏｆｆｏｌｉ演算部が、各量子ビットＱＢｊ−１，…，ＱＢ０を制御ビットとし、量子ビットＱＺを目標ビットとしたＴｏｆｆｏｌｉ演算を施し、第３ＮＯＴ演算部が、各量子ビットＱＢｊ−１，…，ＱＢ０にＮＯＴ演算を施し、古典制御ＮＯＴ演算部が、メモリから読み込まれたＡ−Ｎの桁（ａ−ｎ）ｈが１となるｈに対応する量子ビットＱＢｈのみにＮＯＴ演算を施す操作である。
【００１４】
このように、ＨＩＧＨＢＩＴ演算部が、量子ビットＱＵｊ−１，…，ＱＵ１に対しても量子操作を行う構成をとることによって量子ビットの有効利用を図り、必要となる量子ビット数の低減を図っている。
【発明の効果】
【００１５】
以上のように本発明では、従来よりも少ない量子ビットを使って、位数発見に有用な２ｊ桁の２進数Ｃを高い確率で求めることが可能となる。
【発明を実施するための最良の形態】
【００１６】
以下、本発明の実施の形態を図面を参照して説明する。
〔第1の実施の形態〕
＜機能構成＞
図１は、本形態における量子計算装置１の構成を例示したブロック図である。
図１に例示するように、本形態の量子計算装置１は、量子ビット１０、入力部２０、古典メモリ３０、減算部４０、乗算部５０、量子計算制御部６０、量子演算部７０及び観測部８０を有している。また、量子演算部７０は、初期量子状態生成部７１、ＣＶ部７２、Ｈ（アダマール）演算部、Ｒｋ演算部７４及びＸＣＫ演算部７５を有している。
【００１７】
図２（ａ）は、ＣＶ演算部７２の詳細構成を例示した図である。この図に示すように、ＣＶ演算部７２は、Ｍ  ＭＯＤ演算部１０１及びＣＳＷＡＰ演算部１０２を有している。図２（ｂ）は、Ｍ  ＭＯＤ演算部１０１の詳細構成を例示した図である。この図に示すようにＭ  ＭＯＤ演算部１０１は、ＡＤＤ  ＭＯＤ演算部１１１及びＳＷＡＰ演算部１１２を有している。図２（ｃ）は、ＡＤＤ  ＭＯＤ演算部１１１の詳細構成を例示した図である。この図に示すようにＡＤＤ  ＭＯＤ演算部１１１は、ＣＯＮＰＡＲＩＳＯＮ演算部１２１、ＱＦＴ演算部１２２、ＱＦＴ−１演算部１２３、φＡＤＤ演算部１２４、φＡＤＤ−１演算部１２５、ＮＯＴ演算部１２６及びＴｏｆｆｏｌｉ演算部１２７を有している。図３（ａ）は、ＣＯＮＰＡＲＩＳＯＮ演算部１２１の詳細構成を例示した図である。この図に示すようにＣＯＮＰＡＲＩＳＯＮ演算部１２１は、ＨＩＧＨＢＩＴ演算部１３１、ＮＯＴ演算部１３２、古典制御ＮＯＴ演算部１３３及びＴｏｆｆｏｌｉ演算部１３４を有している。図３（ｂ）は、ＨＩＧＨＢＩＴ演算部１３１の詳細構成を例示した図である。この図に示すようにＨＩＧＨＢＩＴ演算部１３１は、制御ＮＯＴ演算部１４１、Ｅ演算部１４２、Ｆ演算部１４３、Ｔｏｆｆｏｌｉ演算部１４４、ＮＯＴ演算部１４５及びＦ−１演算部１４３を有している。なお、特に断りが無い限り、量子計算装置１は、量子計算制御部６０の制御のもと各処理を実行する。また、各要素の機能構成の詳細やハードウェア構成の詳細については後述する。
【００１８】
＜処理＞
［処理の全体］
量子計算装置１は、入力されたｊ桁の２進数Ｎ＝ｎｊ−１…ｎ０（ｎｊ−１,…,ｎ０∈｛０，１｝）と、Ｎより小さいｊ桁の２進数Ａ＝ａｊ−１…ａ０（ａｊ−１,…,ａ０∈｛０，１｝）に対し、２ｊ＋２個の量子ビットを用いたｊの３乗に比例した計算ステップ数のｊの４乗に比例した個数の基本演算を施し、位数発見に有用な２ｊ桁の２進数Ｃ＝ｃ２ｊ−１…ｃ０（ｃｊ−１,…,ｃ０∈｛０，１｝）を高い確率で出力する。以下、この処理の詳細を説明していく。
【００１９】
図４は、本形態の量子計算装置１の処理の全体を説明するためのフローチャートである。また、図１１は、この処理の全体を例示した量子回路である。なお、量子回路は、１量子ビットに対する演算とＣＮＯＴを基本演算とするが、図が複雑になるのを避けるため、図１１では、これらの演算以外の演算も使って表現している。また、この量子回路に使われる全ての演算は，１量子ビットに対する演算とＣＮＯＴに分解できる（前述の非特許文献３参照）。また、図１１は、ｊ＝５の場合の例である。また、Ｎより大きい全ての数はｍｏｄ  Ｎで解釈される。
【００２０】
図１１に例示するように、本形態の量子回路は、０と１と２ｊ個の０とをそれぞれ示す量子ビットを入力とし、位数発見に有用な２ｊ桁の２進数Ｃ＝ｃ２ｊ−１…ｃ０を出力するものである。この構成は，従来構成を示した図３１において、上から２ｊ＋３番目の量子状態を保持する量子ビットを削除し、ＣＵ（ａ）をＣＶ（ａ）に置換したものに相当する。以下、この量子回路を構成する処理の全体を説明する。
まず、２進数ｊ桁のＮ＝ｎｊ−１…ｎ０と、Ｎよりも小さい２進数ｊ桁のＡ＝ａｊ−１…ａ０とが入力部２０から入力され、古典メモリ３０（図１）に格納される（ステップＳ１）。なお、ｊは例えば予め装置に設定された値とする。次に、量子計算制御部６０の制御のもと初期量子状態生成部７１が、量子ビットＱＤ１，ＱＤ２，ＱＵ１〜ＱＵｊ−１，ＱＢ０〜ＱＢｊ−１，ＱＺの初期量子状態を生成する（ステップＳ２）。この例では、量子ビットＱＤ２の量子状態を、１を示すものとし、他の量子ビットの量子状態を、０を示すものとする。次に、Ｈ演算部７３が、量子ビットＱＤ１に対してＨ（アダマール）演算（図３２（ａ））を適用する（ステップＳ３）。なお、量子演算を適用するとは、演算に相当する量子操作を量子ビットに施すことを意味する。次に、量子計算制御部６０が変数ｇａに０を代入して古典メモリ３０に格納し、さらに乗算部５０が古典メモリ３０から読み出したＡ及びｇａを用いてＡ・２２ｊ−ｇａ−１を算出し、これを量子計算制御部６０に送る（ステップＳ４）。次に、量子計算制御部６０は、送られたＡ・２２ｊ−ｇａ−１を用いてＣＶ演算部７２を制御し、ＣＶ演算部７２は、量子ビットＱＤ１を制御ビットとして、量子ビットＱＤ２，ＱＵ１〜ＱＵｊ−１，ＱＢ０〜ＱＢｊ−１，ＱＺに対し、ＣＶ（Ａ・２２ｊ−ｇａ−１）演算を適用する（ステップＳ５）。なお、この演算の詳細は後述する。次に、Ｈ演算部７３が、量子ビットＱＤ１に対してＨ演算（図３２（ａ））を適用する（ステップＳ６）。次に、量子計算制御部６０が、古典メモリ３０から変数ｇａを読み出し、観測部８０に量子ビットＱＤ１の量子状態を観測させて、その観測結果をｃｇａとして古典メモリ３０に格納する（ステップＳ７）。この観測により量子ビットＱＤ１の量子状態はｃｇａに縮約する（以下も同様）。
【００２１】
次に、量子計算制御部６０が、古典メモリ３０からｃｇａを読み出し、Ｘｃｋ演算部７５に、ｋ＝ｇａとした図３２（ｂ）の量子操作を量子ビットＱＤ１に対して適用させ、さらに、Ｈ演算部７３に、量子ビットＱＤ１に対するＨ演算（図３２（ａ））を適用させる（ステップＳ８）。次に、量子計算制御部６０は、古典メモリ３０に格納された変数ｇａを読み出し、ｇａ＋１を新たなｇａとして更新し、これを古典メモリ３０に格納する（ステップＳ９）。次に、乗算部５０が古典メモリ３０から読み出したＡ及びｇａを用いてＡ・２２ｊ−ｇａ−１を算出し、これを量子計算制御部６０に送る。量子計算制御部６０は、送られたＡ・２２ｊ−ｇａ−１を用いてＣＶ演算部７２を制御し、ＣＶ演算部７２は、量子ビットＱＤ１を制御ビットとして、量子ビットＱＤ２，ＱＵ１〜ＱＵｊ−１，ＱＢ０〜ＱＢｊ−１，ＱＺに対し、ＣＶ（Ａ・２２ｊ−ｇａ−１）演算を適用する（ステップＳ１０）。なお、この演算の詳細は後述する。次に、Ｒｋ演算部７４が、量子ビットＱＤ１に対してｋ＝ｇａとしたＲｋ演算（図３３）を適用し（ステップＳ１１）、観測部８０が量子ビットＱＤ１の量子状態を観測し、その観測結果をｃｇａとして古典メモリ３０に格納する（ステップＳ１２）。
【００２２】
次に、量子計算制御部６０において、古典メモリ３０に格納されたｇａが２ｊ−１であるか否かを判断する。ここで、ｇａ＝２ｊ−１でなければ、量子計算制御部６０は処理をステップＳ８に戻す。一方、ｇａ＝２ｊ−１であれば、量子計算制御部６０は、古典メモリ３０に蓄積されたＣ＝ｃ２ｊ−１…ｃ０を出力する。
［ＣＶ（Ａ）演算の詳細］
次に、ステップＳ５，Ｓ１１で触れたＣＶ演算の詳細を説明する。なお、以下では、ＡをパラメータとしたＣＶ（Ａ）演算を例にとって説明するが、このＡをＡ・２２ｊ−ｇａ−１に置換すればＣＶ（Ａ・２２ｊ−ｇａ−１）演算に一般化できる。
【００２３】
図５は、このＣＶ（Ａ）演算の詳細を説明するためのフローチャートである。また、図１２は、ｊ＝５の場合におけるＣＶ（Ａ）演算を例示した量子回路である。
図１２に例示するように、ＣＶ（Ａ）演算を示す量子回路は、ｄとＵ＝ｕｊ−１…ｕ０（ｕｊ−１，…,ｕ０∈｛０，１｝）とｊ＋１個の０とをそれぞれ示す量子状態の量子ビットＱＤ１，ＱＤ２，ＱＵ１〜ＱＵｊ−１〔ＱＵｈ’（ｈ’∈｛０，…，ｊ−１｝）がｕｈ’に対応〕，ＱＢ０〜ＱＢｊ−１，ＱＺを入力とし、ｄ＝１であれば、量子ビットＱＤ１，ＱＤ２，ＱＵ１〜ＱＵｊ−１，ＱＢ０〜ＱＢｊ−１，ＱＺを、ｄとＡ・Ｕ  ｍｏｄ  Ｎの各桁（Ａ・Ｕ  ｍｏｄ  Ｎ）０…（Ａ・Ｕ  ｍｏｄ  Ｎ）ｊ−１とｊ＋１個の０とをそれぞれ示す量子状態とし、ｄ＝０であれば、入力の量子状態を維持するものである。この構成は、図３４の従来構成において、上から２ｊ＋３番目の量子状態を保持する量子ビットを削除し、ＣＭＵＬＴ（Ａ）ＭＯＤ（Ｎ）をＭ（Ａ）ＭＯＤ（Ｎ）に置換したものに相当する。以下、このＣＶ（Ａ）演算の詳細を説明する。
【００２４】
まず、古典メモリ３０からＡを読み込んだ量子計算制御部６０の制御のもと、Ｍ  ＭＯＤ演算部１０１（図２（ａ））が、量子ビットＱＤ１を制御ビットとして、量子ビットＱＤ２，ＱＵ１〜ＱＵｊ−１，ＱＢ０〜ＱＢｊ−１，ＱＺに対し、Ｍ（Ａ）ＭＯＤ（Ｎ）演算を適用する（ステップＳ２１）。なお、Ｍ（Ａ）ＭＯＤ（Ｎ）演算の詳細については後述する。次に、ＣＳＷＡＰ演算部１０２が、量子ビットＱＤ１，ＱＤ２，ＱＵ１〜ＱＵｊ−１，ＱＢ０〜ＱＢｊ−１に対しＣＳＷＡＰ演算（図３５）を適用する（ステップＳ２２）。次に、乗算部５０（図１）が古典メモリ３０に格納されたＡを用いてＡ−１を算出し（ステップＳ２３）、量子計算制御部６０に送る。量子計算制御部６０は、このＡ−１を用いてＭ  ＭＯＤ演算部１０１を制御し、Ｍ  ＭＯＤ演算部１０１は、量子ビットＱＤ１を制御ビットとして、量子ビットＱＤ２，ＱＵ１〜ＱＵｊ−１，ＱＢ０〜ＱＢｊ−１，ＱＺに対し、Ｍ（Ａ−１）ＭＯＤ（Ｎ）演算を適用する（ステップＳ２４）。
【００２５】
［Ｍ（Ａ）ＭＯＤ（Ｎ）演算の詳細］
次に、ステップＳ２１，Ｓ２４で触れたＭ（Ａ）ＭＯＤ（Ｎ）演算, Ｍ（Ａ−１）ＭＯＤ（Ｎ）演算の詳細を説明する。なお、以下では、ＡをパラメータとしたＭ（Ａ）ＭＯＤ（Ｎ）演算を例にとって説明するが、このＡをＡ−１に置換すればＭ（Ａ−１）ＭＯＤ（Ｎ）演算となる。
図６は、このＭ（Ａ）ＭＯＤ（Ｎ）演算の詳細を説明するためのフローチャートである。また、図１３は、ｊ＝５の場合におけるＭ（Ａ）ＭＯＤ（Ｎ）演算を例示した量子回路である。
【００２６】
図１３に例示するように、Ｍ（Ａ）ＭＯＤ（Ｎ）演算を示す量子回路は、ｄとＵとＢ＝ｂｊ−１…ｂ０（ｂｊ−１,…,ｂ０∈｛０，１｝）と０とをそれぞれ示す量子状態の量子ビットＱＤ１，ＱＤ２，ＱＵ１〜ＱＵｊ−１，ＱＢ０〜ＱＢｊ−１〔ＱＢｈ（ｈ∈｛０，…，ｊ−１｝）がｂｈに対応〕，ＱＺを入力とし、ｄ＝１であれば、ｄとＵとＡ・Ｘ＋Ｂ  ｍｏｄ  Ｎと０とをそれぞれ示す量子状態の量子ビットＱＤ１，ＱＤ２，ＱＵ１〜ＱＵｊ−１，ＱＢ０〜ＱＢｊ−１を出力し、ｄ＝０であれば、入力の量子状態を維持するものである。ただし、Ａ・Ｘ＋Ｂ  ｍｏｄ  Ｎ＝（Ａ・Ｘ＋Ｂ  ｍｏｄ  Ｎ）ｊ−１…（Ａ・Ｘ＋Ｂ  ｍｏｄ  Ｎ）０であり、ＱＢｈ（ｈ∈｛０，…，ｊ−１｝）が（Ａ・Ｘ＋Ｂ  ｍｏｄ  Ｎ）ｈに対応する。以下、このＭ（Ａ）ＭＯＤ（Ｎ）演算の詳細を説明する。
【００２７】
まず、古典メモリ３０からＡを読み込んだ量子計算制御部６０の制御のもと、ＡＤＤ  ＭＯＤ演算部１１１（図２（ｂ））が、量子ビットＱＤ１，ＱＤ２を制御ビットとして、量子ビットＱＵ１〜ＱＵｊ−１，ＱＢ０〜ＱＢｊ−１，ＱＺに対し、ＡＤＤ（２０・Ａ）ＭＯＤ（Ｎ）演算を適用する（ステップＳ３１）。なお、ＡＤＤ（２０・Ａ）ＭＯＤ（Ｎ）演算の詳細については後述する。次に、量子計算制御部６０が変数ｇｂに１代入し、この変数ｇｂを古典メモリ３０に格納する（ステップＳ３２）。次に、古典メモリ３０から変数ｇｂを読み込んだ量子計算制御部６０の制御のもと、ＳＷＡＰ演算部１１２が、量子ビットＱＤ２と量子ビットＱＵｇｂに対し、ＳＷＡＰ演算を適用する（ステップＳ３３）。なお、ＳＷＡＰ演算とは、図１４のように３つの制御ＮＯＴ演算を組み合わせた演算を意味する。ここでｘ，ｙ∈｛０，１｝である。このＳＷＡＰ演算により、入力された２つの量子ビットの量子状態が入れ替わる。
【００２８】
次に乗算部５０が古典メモリ３０からＡと変数ｇｂとを読み込み、２ｇｂ・Ａを計算して量子計算制御部６０に送る（ステップＳ３４）。量子計算制御部６０は、２ｇｂ・Ａを用いてＡＤＤ  ＭＯＤ演算部１１１を制御し、ＡＤＤ  ＭＯＤ演算部１１１は、量子ビットＱＤ１，ＱＤ２を制御ビットとして、量子ビットＱＵ１〜ＱＵｊ−１，ＱＢ０〜ＱＢｊ−１，ＱＺに対し、ＡＤＤ（２ｇｂ・Ａ）ＭＯＤ（Ｎ）演算を適用する（ステップＳ３５）。次に、古典メモリ３０から変数ｇｂを読み込んだ量子計算制御部６０の制御のもと、ＳＷＡＰ演算部１１２が、量子ビットＱＤ２と量子ビットＱＵｇｂに対し、ＳＷＡＰ演算を適用する（ステップＳ３６）。その後、量子計算制御部６０が、古典メモリ３０に格納された変数ｇｂがｊ−１であるか否かを判断する（ステップＳ３７）。ここで、ｇｂ＝ｊ−１でなければ、量子計算制御部６０が、ｇｂ＋１を新たな変数ｇｂとして古典メモリ３０に格納し、処理をステップＳ３３に戻し、ｇｂ＝ｊ−１であれば、Ｍ（Ａ）ＭＯＤ（Ｎ）演算を終了する。
【００２９】
［ＡＤＤ（Ａ）ＭＯＤ（Ｎ）演算の詳細］
次に、ステップＳ３１，Ｓ３５で触れたＡＤＤ（Ａ）ＭＯＤ（Ｎ）演算, ＡＤＤ（２ｇｂ・Ａ）ＭＯＤ（Ｎ）演算の詳細を説明する。なお、以下では、ＡをパラメータとしたＡＤＤ（Ａ）ＭＯＤ（Ｎ）演算を例にとって説明するが、このＡを２ｇｂ・Ａに置換すればＡＤＤ（２ｇｂ・Ａ）ＭＯＤ（Ｎ）演算となる。
図７は、このＡＤＤ（Ａ）ＭＯＤ（Ｎ）演算の詳細を説明するためのフローチャートである。また、図１５は、ｊ＝５の場合におけるＡＤＤ（Ａ）ＭＯＤ（Ｎ）演算を例示した量子回路である。
【００３０】
図１５に例示するように、ＡＤＤ（Ａ）ＭＯＤ（Ｎ）演算を示す量子回路は、ｄ１，ｄ２∈｛０，１｝とｕ１，…，ｕｊ−１∈｛０，１｝とＢと０とをそれぞれ示す量子状態の量子ビットＱＤ１，ＱＤ２，ＱＵ１〜ＱＵｊ−１，ＱＢ０〜ＱＢｊ−１，ＱＺを入力とし、ｄ１＝ｄ２＝１であれば、ｄ１，ｄ２とｕ１，…，ｕｊ−１とＡ＋Ｂ  ｍｏｄ  Ｎと０とをそれぞれ示す量子状態の量子ビットＱＤ１，ＱＤ２，ＱＵ１〜ＱＵｊ−１，ＱＢ０〜ＱＢｊ−１，ＱＺを出力し、ｄ１＝ｄ２＝１でなければ、入力の量子状態を維持する。ただし、Ａ＋Ｂ  ｍｏｄ  Ｎ＝（Ａ＋Ｂ  ｍｏｄ  Ｎ）ｊ−１…（Ａ＋Ｂ  ｍｏｄ  Ｎ）０であり、ＱＢｈ（ｈ∈｛０，…，ｊ−１｝）が（Ａ＋Ｂ  ｍｏｄ  Ｎ）ｈに対応する。以下、このＡＤＤ（Ａ）ＭＯＤ（Ｎ）演算の詳細を説明する。
【００３１】
まず、減算部４０が古典メモリ３０から読み込んだＡとＮとからＮ−Ａを算出し、これを量子計算制御部６０に送る（ステップＳ４１）。このＮ−Ａを用いた量子計算制御部６０の制御のもと、ＣＯＭＰＡＲＩＳＯＮ演算部１２１（図２（ｃ））が、量子ビットＱＤ１，ＱＤ２を制御ビットとして、量子ビットＱＤ１，ＱＤ２がそれぞれ示す量子状態がともに１である場合にのみ、量子ビットＱＵ１〜ＱＵｊ−１，ＱＢ０〜ＱＢｊ−１，ＱＺに対し、ＣＯＭＰＡＲＩＳＯＮ（Ｎ−Ａ）演算を適用する（ステップＳ４２）。なお、詳細は後述するが、このＣＯＭＰＡＲＩＳＯＮ（Ｎ−Ａ）演算は、Ｎ−Ａ＞Ｂの場合にのみ量子ビットＱＺの量子状態を反転（０の場合には１にし、１の場合には０に）させる演算である。次に、ＱＦＴ演算部１２２が、量子ビットＱＢ０〜ＱＢｊ−１に対し、ＱＦＴ（量子フーリエ変換）演算（図３９）を適用する（ステップＳ４３）。
【００３２】
次に、古典メモリ３０からＡを読み込んだ量子計算制御部６０の制御のもと、φＡＤＤ演算部１２４が、量子ビットＱＤ１，ＱＤ２，ＱＺを制御ビットとして、量子ビットＱＤ１，ＱＤ２，ＱＺがそれぞれ示す量子状態が全て１である場合にのみ、量子ビットＱＢ０〜ＱＢｊ−１に対するφＡＤＤ（Ａ）演算を適用する（ステップＳ４４）。なお、φＡＤＤ（Ａ）演算は、図４２及び４３に示した通りである。すなわち、ステップＳ４４では、量子ビットＱＤ１，ＱＤ２，ＱＺを制御ビットとし、量子ビットＱＤ１，ＱＤ２，ＱＺがそれぞれ示す量子状態が全て１である場合にのみ、φＡＤＤ演算部１２４が、１を示す量子状態の量子ビットＱＢｋ（ｋ∈｛ｊ−１，…，０｝）のみに対し、
【００３３】
【数５】
2007087307.tif 000005
（ただし、量子ビットＱＢｋの量子状態を｜ＱＢｋ〉とし、ｅをネピア数とし、ｉを虚数単位とする）の演算を施す。
次に、ＮＯＴ演算部１２６が、量子ビットＱＺに対してＮＯＴ演算を適用し（ステップＳ４５）、φＡＤＤ−１演算部１２５が、量子ビットＱＤ１，ＱＤ２，ＱＺを制御ビットとして、量子ビットＱＤ１，ＱＤ２，ＱＺがそれぞれ示す量子状態が全て１である場合にのみ、量子ビットＱＢ０〜ＱＢｊ−１に対し、φＡＤＤ（Ｎ−Ａ）−１演算を適用する（ステップＳ４６）。なお、φＡＤＤ（Ｎ−Ａ）−１演算とはφＡＤＤ（Ｎ−Ａ）演算の逆演算を意味する。すなわち、ステップＳ４６では、量子ビットＱＤ１，ＱＤ２，ＱＺを制御ビットとし、量子ビットＱＤ１，ＱＤ２，ＱＺがそれぞれ示す量子状態が全て１である場合にのみ、φＡＤＤ−１演算部１２５が、１を示す量子状態の量子ビットＱＢｋのみに対し、
【００３４】
【数６】
2007087307.tif 000006
（ただし、Ｎ−Ａ＝（ｎ−ａ）ｊ−１…（ｎ−ａ）０とする）の演算を施す。
次に、ＮＯＴ演算部１２６が、量子ビットＱＺに対してＮＯＴ演算を適用し（ステップＳ４７）、ＱＦＴ−１演算部１２３が、量子ビットＱＢ０〜ＱＢｊ−１に対し、ＱＦＴ演算の逆演算であるＱＦＴ−１演算を適用する（ステップＳ４８）。次に、古典メモリ３０からＡを読み込んだ量子計算制御部６０の制御のもと、ＣＯＭＰＡＲＩＳＯＮ演算部１２１が、量子ビットＱＤ１，ＱＤ２を制御ビットとして、量子ビットＱＤ１，ＱＤ２がそれぞれ示す量子状態がともに１である場合にのみ、量子ビットＱＵ１〜ＱＵｊ−１，ＱＢ０〜ＱＢｊ−１，ＱＺに対し、ＣＯＭＰＡＲＩＳＯＮ（Ａ）演算を適用する（ステップＳ４９）。なお、ＣＯＭＰＡＲＩＳＯＮ（Ａ）の詳細については後述する。そして、Ｔｏｆｆｏｌｉ演算部１２７が、量子ビットＱＤ１，ＱＤ２を制御ビットとし、量子ビットＱＺを目標ビットとしたＴｏｆｆｏｌｉ演算を適用する（ステップＳ５０）。
【００３５】
［ＣＯＭＰＡＲＩＳＯＮ（Ａ）演算の詳細］
次に、ステップＳ４２，Ｓ４９で触れたＣＯＭＰＡＲＩＳＯＮ（Ｎ−Ａ）演算, ＣＯＭＰＡＲＩＳＯＮ（Ａ）演算の詳細を説明する。なお、以下では、ＡをパラメータとしたＣＯＭＰＡＲＩＳＯＮ（Ａ）演算を例にとって説明するが、このＡをＮ−Ａに置換すればＣＯＭＰＡＲＩＳＯＮ（Ｎ−Ａ）演算となる。
図８は、このＣＯＭＰＡＲＩＳＯＮ（Ａ）演算の詳細を説明するためのフローチャートである。また、図１６は、ｊ＝５の場合におけるＣＯＭＰＡＲＩＳＯＮ（Ａ）演算を例示した量子回路である。
【００３６】
図１６に例示するように、ＣＯＭＰＡＲＩＳＯＮ（Ａ）演算を示す量子回路は、Ｂ＝ｂｊ−１…ｂ０とｕ１，…，ｕｊ−１とｚとをそれぞれ示す量子ビットＱＢ０〜ＱＢｊ−１，ＱＵ１〜ＱＵｊ−１，ＱＺに対し、Ｂ＝ｂｊ−１…ｂ０とｕ１，…，ｕｊ−１とをそれぞれ示す量子状態の量子ビットＱＢ０〜ＱＢｊ−１，ＱＵ１〜ＱＵｊ−１と、ｚ（＋）αを示す量子状態の量子ビットＱＺとを出力する。なお、（＋）は排他的論理和（和のｍｏｄ  ２を採った値）を示す。また、αは、Ａ＞Ｂの場合にα＝１となり、Ａ≦Ｂの場合にα＝０となる値である。すなわち、ＣＯＭＰＡＲＩＳＯＮ（Ａ）演算は、Ａ＞Ｂの場合にのみ、量子ビットＱＺの量子状態を反転させる演算である。以下、このＣＯＭＰＡＲＩＳＯＮ（Ａ）演算の詳細を説明する。
【００３７】
まず、古典メモリ３０からＡを読み込んだ量子計算制御部６０の制御のもと、ＨＩＢＩＴ演算部１３１（図３（ａ））が、量子ビットＱＵ１〜ＱＵｊ−１，ＱＢ０〜ＱＢｊ−１，ＱＺに対し、ＨＩＧＨＢＩＴ（Ａ）演算を適用する（ステップＳ５１）。なお、ＨＩＧＨＢＩＴ（Ａ）演算の詳細については後述する。次に、ＮＯＴ演算部１３２が、量子ビットＱＺに対し、ＮＯＴ演算を適用する（ステップＳ５２）。次に、古典メモリ３０からＡを読み込んだ量子計算制御部６０の制御のもと、古典制御ＮＯＴ演算部１３３が、Ａの桁ａｈ（ｈ∈｛ｊ−１，…，０｝）が１となるｈに対応する量子ビットＱＢｈのみにＮＯＴ演算を適用する（ステップＳ５３）。なお、各図においてＮＯＴ演算等の演算子を四角で囲み、その上部に符号を付したものは、この符号の値が１である場合にのみ、その四角で囲まれた演算を実行する演算子を意味する。
【００３８】
その後、ＮＯＴ演算部１３２が、量子ビットＱＢ０〜ＱＢｊ−１に対し、ＮＯＴ演算を適用し（ステップＳ５４）、Ｔｏｆｆｏｌｉ演算部１３４が、量子ビットＱＢ０〜ＱＢｊ−１を制御ビットとし、量子ビットＱＺを目標ビットとしたＴｏｆｆｏｌｉ演算を適用する（ステップＳ５５）。図１７にｊ＝５の場合のＴｏｆｆｏｌｉ演算を示す。さらにその後、ＮＯＴ演算部１３２が、量子ビットＱＢ０〜ＱＢｊ−１に対し、ＮＯＴ演算を適用する（ステップＳ５６）。そして、古典制御ＮＯＴ演算部１３３が、Ａの桁ａｈ（ｈ∈｛ｊ−１，…，０｝）が１となるｈに対応する量子ビットＱＢｈのみにＮＯＴ演算を適用する（ステップＳ５７）。
【００３９】
［ＨＩＧＨＢＩＴ（Ａ）演算の詳細］  
次に、ステップＳ５１で触れたＨＩＧＨＢＩＴ（Ａ）演算の詳細を説明する。
図９及び１０は、このＨＩＧＨＢＩＴ（Ａ）演算の詳細を説明するためのフローチャートである。また、図１８は、ｊ＝５の場合におけるＨＩＧＨＢＩＴ（Ａ）演算を例示した量子回路である。
図１８に例示するように、ＨＩＧＨＢＩＴ（Ａ）演算を示す量子回路は、Ｂ＝ｂｊ−１…ｂ０とｕ１，…，ｕｊ−１とｚとをそれぞれ示す量子ビットＱＢ０〜ＱＢｊ−１，ＱＵ１〜ＱＵｊ−１，ＱＺに対し、Ｂ＝ｂｊ−１…ｂ０とｕ１，…，ｕｊ−１とをそれぞれ示す量子状態の量子ビットＱＢ０〜ＱＢｊ−１，ＱＵ１〜ＱＵｊ−１と、ｚ（＋）βを示す量子状態の量子ビットＱＺとを出力する。なお、βはＡ＋Ｂの最上位ビットの値を意味する。以下、ＨＩＧＨＢＩＴ（Ａ）演算の詳細を説明する。
【００４０】
まず、制御ＮＯＴ演算部１４１（図３（ｂ））が、量子ビットＱＵｊ−１を制御ビットとし、量子ビットＱＺを目標ビットとしたＣＮＯＴ演算を適用する（ステップＳ６１）。次に、量子計算制御部６０が変数ｇｃにｊ−１を代入し、これを古典メモリ３０に格納する（ステップＳ６２）。
次に、古典メモリ３０からＡと変数ｇｃとを読み込んだ量子計算制御部６０の制御のもと、Ｅ演算部１４２が、量子ビットＱＵｇｃ，ＱＵｇｃ−１，ＱＢｇｃに対し、Ｅ（ａｇｃ）演算を適用する（ステップＳ６３）。
【００４１】
図１９は、このＥ（ａｇｃ）演算を示した量子回路である。図１９に示すように、Ｅ（ａｇｃ）演算は、ｐ，ｒ，ｓ∈｛０，１｝をそれぞれ示す量子状態の３つの量子ビットＱＵｇｃ−１，ＱＢｇｃ，ＱＵｇｃを入力とする。そして、Ｅ演算部１４２は、まず、ａｇｃ＝１の場合にのみ量子ビットＱＢｇｃにＮＯＴ演算を適用する。次に、Ｅ演算部１４２は、量子ビットＱＵｇｃ−１，ＱＢｇｃを制御ビットとし、量子ビットＱＵｇｃを目標ビットとしたＴｏｆｆｏｌｉ演算を適用し、さらに、ａｇｃ＝１の場合にのみ量子ビットＱＢｇｃにＮＯＴ演算を適用する。これらの操作により、３つの量子ビットＱＵｇｃ−１，ＱＢｇｃ，ＱＵｇｃの量子状態が、それぞれｐ，ｒ，ｓ（＋）（ａｇｃ（＋）ｒ）・ｐを示すものとされる。以上がＥ（ａｇｃ）演算である。
【００４２】
次に、量子計算制御部６０が、古典メモリ３０に格納された変数ｇｃが２であるか否かを判断する（ステップＳ６４）。ここで、ｇｃ＝２でなければ、量子計算制御部６０は、ｇｃ−１を新たなｇｃとして古典メモリ３０に格納した後（ステップＳ６５）、処理をステップＳ６３に戻す。一方、ｇｃ＝２であれば、量子計算制御部６０は、古典メモリからＡの要素ａ１を読み込み、ａ１＝１の場合にのみ、制御ＮＯＴ演算部１４１に、量子ビットＱＢ１を制御ビットとし、量子ビットＱＵ１を目標ビットとした制御ＮＯＴ演算を適用させ、ＮＯＴ演算部１４５に、量子ビットＱＢ１へのＮＯＴ演算を適用させる（ステップＳ６６）。次に、量子計算制御部６０は、古典メモリからＡの要素ａ０を読み込み、ａ０＝１の場合にのみ、Ｔｏｆｆｏｌｉ演算部１４４に、量子ビットＱＢ０，ＱＢ１を制御ビットとし、量子ビットＱＵ１を目標ビットとしたＴｏｆｆｏｌｉ演算を適用させる（ステップＳ６７）。
【００４３】
次に、古典メモリ３０から変数ｇｃとＡの要素ａｇｃとを読み込んだ量子計算制御部６０の制御のもと、Ｆ演算部１４３が、量子ビットＱＵｇｃ，ＱＵｇｃ−１，ＱＢｇｃに対し、Ｆ（ａｇｃ）演算を適用する（ステップＳ６８）。
図２０は、このＦ（ａｇｃ）演算を示した量子回路である。図２０に示すように、Ｆ（ａｇｃ）演算は、ｐ，ｒ，ｓ∈｛０，１｝をそれぞれ示す量子状態の３つの量子ビットＱＵｇｃ−１，ＱＢｇｃ，ＱＵｇｃを入力とする。そして、Ｆ演算部１４３は、まず、ａｇｃ＝１の場合にのみ量子ビットＱＢｇｃを制御ビットとし、量子ビットＱＵｇｃを目標ビットとした制御ＮＯＴ演算を適用し、さらに量子ビットＱＵｇｃにＮＯＴ演算を適用する。次に、Ｆ演算部１４３は、量子ビットＱＵｇｃ−１，ＱＢｇｃを制御ビットとし、量子ビットＱＵｇｃを目標ビットとしたＴｏｆｆｏｌｉ演算を適用する。これらの操作により、３つの量子ビットＱＵｇｃ−１，ＱＢｇｃ，ＱＵｇｃの量子状態が、それぞれｐ，ａｇｃ（＋）ｒ，ｓ（＋）ｐ・ａｇｃ（＋）ａｇｃ・ｒ（＋）ｒ・ｐを示すものとなる。以上がＦ（ａｇｃ）演算である。
【００４４】
次に、量子計算制御部６０が、古典メモリ３０に格納された変数ｇｃがｊ−１であるか否かを判断する（ステップＳ６９）。ここで、ｇｃ＝ｊ−１でなければ、量子計算制御部６０は、ｇｃ＋１を新たなｇｃとして古典メモリ３０に格納した後（ステップＳ７０）、処理をステップＳ６８に戻す。一方、ｇｃ＝ｊ−１であれば、制御ＮＯＴ演算部１４１が、量子ビットＱＵｊ−１を制御ビットとし、量子ビットＱＺを目標ビットとしたＣＮＯＴ演算を適用する（ステップＳ７１）。次に、古典メモリ３０から変数ｇｃとＡの要素ａｇｃとを読み込んだ量子計算制御部６０の制御のもと、Ｆ演算部１４３が、量子ビットＱＵｇｃ，ＱＵｇｃ−１，ＱＢｇｃに対し、Ｆ（ａｇｃ）演算の逆演算であるＦ（ａｇｃ）−１演算を適用する（ステップＳ７２）。
【００４５】
次に、量子計算制御部６０が、古典メモリ３０に格納された変数ｇｃが２であるか否かを判断する（ステップＳ７３）。ここで、ｇｃ＝２でなければ、量子計算制御部６０は、ｇｃ−１を新たなｇｃとして古典メモリ３０に格納した後（ステップＳ７４）、処理をステップＳ７２に戻す。一方、ｇｃ＝２であれば、量子計算制御部６０は、古典メモリからＡの要素ａ０を読み込み、ａ０＝１の場合にのみ、Ｔｏｆｆｏｌｉ演算部１４４に、量子ビットＱＢ０，ＱＢ１を制御ビットとし、量子ビットＱＵ１を目標ビットとしたＴｏｆｆｏｌｉ演算を適用させる（ステップＳ７５）。
【００４６】
次に、量子計算制御部６０は、古典メモリからＡの要素ａ１を読み込み、ａ１＝１の場合にのみ、ＮＯＴ演算部１４５に、量子ビットＱＢ１へのＮＯＴ演算を適用させ、制御ＮＯＴ演算部１４１に、量子ビットＱＢ１を制御ビットとし、量子ビットＱＵ１を目標ビットとした制御ＮＯＴ演算を適用させる（ステップＳ７６）。
次に、古典メモリ３０からＡと変数ｇｃとを読み込んだ量子計算制御部６０の制御のもと、Ｅ演算部１４２が、量子ビットＱＵｇｃ，ＱＵｇｃ−１，ＱＢｇｃに対し、Ｅ（ａｇｃ）演算を適用する（ステップＳ７７）。次に、量子計算制御部６０が、古典メモリ３０に格納された変数ｇｃがｊ−１であるか否かを判断する（ステップＳ７８）。ここで、ｇｃ＝ｊ−１でなければ、量子計算制御部６０は、ｇｃ＋１を新たなｇｃとして古典メモリ３０に格納した後（ステップＳ７９）、処理をステップＳ７７に戻す。一方、ｇｃ＝ｊ−１であれば、ＨＩＧＨＢＩＴ（Ａ）演算を終了させる。
【００４７】
〔第２の実施の形態〕
本形態は、第１の実施の形態の変形例である。第１の実施の形態では、Ａ＝ａｊ−１…ａ０を古典情報として取り扱っていたが、第２の実施の形態では、Ａ＝ａｊ−１…ａ０を量子情報として取り扱う。なお、以下では、第１の実施の形態との相違点を中心に説明し、第１の実施の形態と共通する事項については説明を省略する。
＜構成＞
図２１は、本形態における量子計算装置２００の機能構成を例示したブロック図である。
【００４８】
第１の実施の形態の量子計算装置１と第２の実施の形態の量子計算装置２００との構成上の相違点は、第１の実施の形態で古典情報として取り扱っていたＡ＝ａｊ−１…ａ０の各桁ａ０，…，ａｊ−１の値を示す量子状態とする量子ビットＱＡ０，…ＱＡｊ−１を量子ビット１０に追加した量子ビット２１０を用いる点、量子計算部２７０の初期量子状態生成部２７１やＣＶ演算部２７２が、この量子ビットＱＡ０，…ＱＡｊ−１の量子情報を用いて各処理を実行する点である。
図２２（ａ）は、本形態のＣＶ演算部２７２が有するＣＯＮＰＡＲＩＳＯＮ演算部３２１の詳細構成を例示した図である。この図に示すようにＣＯＮＰＡＲＩＳＯＮ演算部３２１は、ＨＩＧＨＢＩＴ演算部３３１、ＮＯＴ演算部３３２、制御ＮＯＴ演算部３３３及びＴｏｆｆｏｌｉ演算部３３４を有している。図２２（ｂ）は、ＨＩＧＨＢＩＴ演算部３３１の詳細構成を例示した図である。この図に示すようにＨＩＧＨＢＩＴ演算部３３１は、制御ＮＯＴ演算部３４１、Ｅ演算部３４２、Ｆ演算部３４３、Ｔｏｆｆｏｌｉ演算部３４４、ＮＯＴ演算部３４５及びＦ−１演算部３４３を有している。なお、その他の詳細構成については第１の実施の形態と同様であるため説明を省略する。
【００４９】
＜処理＞
以下では第１の実施の形態との相違点を中心に説明する。
［初期量子状態生成］
第１の実施の形態では、初期量子状態生成部７１が、量子ビットＱＤ１，ＱＤ２，ＱＵ１〜ＱＵｊ−１，ＱＢ０〜ＱＢｊ−１，ＱＺの初期量子状態を生成していたが（ステップＳ２）、本形態の初期量子状態生成部２７１（図２１）は、さらにＱＡ０〜ＱＡｊ−１の初期量子状態も生成する。具体的には、古典メモリ３０からＡ＝ａｊ−１…ａ０を読み込んだ量子計算制御部６０の制御のもと、初期量子状態生成部２７１が、量子ビットＱＡ０，…ＱＡｊ−１の量子状態を、それぞれＡ＝ａｊ−１…ａ０の各桁ａ０，…，ａｊ−１の値を示す量子状態とする。
【００５０】
［ＣＶ演算］
第１の実施の形態では、Ａ＝ａｊ−１…ａ０を古典情報としてＣＶ演算を行っていたが、本形態では、量子ビットＱＡ０，…ＱＡｊ−１を用い、Ａ＝ａｊ−１…ａ０を量子情報としてＣＶ演算を行う。以下では、ＣＯＮＰＡＲＩＳＯＮ演算とＨＩＧＨＢＩＴ演算のみを説明する。その他の演算については、量子ビットＱＡ０，…ＱＡｊ−１を用いたＣＯＮＰＡＲＩＳＯＮ演算とＨＩＧＨＢＩＴ演算の結果を用いる以外は、第１の実施の形態と同様である。
【００５１】
［ＣＯＮＰＡＲＩＳＯＮ演算の詳細］
図２３は、本形態のＣＯＮＰＡＲＩＳＯＮ演算の詳細を説明するためのフローチャートである。また、図２６は、ｊ＝５の場合における本形態のＣＯＭＰＡＲＩＳＯＮ演算を例示した量子回路である。
図２６に例示するように、本形態のＣＯＭＰＡＲＩＳＯＮ演算を示す量子回路は、Ａ＝ａｊ−１…ａ０とＢ＝ｂｊ−１…ｂ０とｕ１，…，ｕｊ−１とｚとをそれぞれ示す量子ビットＱＡ０〜ＱＡｊ−１，ＱＢ０〜ＱＢｊ−１，ＱＵ１〜ＱＵｊ−１，ＱＺに対し、Ａ＝ａｊ−１…ａ０とＢ＝ｂｊ−１…ｂ０とｕ１，…，ｕｊ−１とをそれぞれ示す量子状態の量子ビットＱＡ０〜ＱＡｊ−１，ＱＢ０〜ＱＢｊ−１，ＱＵ１〜ＱＵｊ−１と、ｚ（＋）αを示す量子状態の量子ビットＱＺとを出力する。また、αは、Ａ＞Ｂの場合にα＝１となり、Ａ≦Ｂの場合にα＝０となる値である。すなわち、ＣＯＭＰＡＲＩＳＯＮ演算は、Ａ＞Ｂの場合にのみ、量子ビットＱＺの量子状態を反転させる演算である。以下、このＣＯＭＰＡＲＩＳＯＮ演算の詳細を説明する。
【００５２】
まず、ＮＯＴ演算部３３２（図２２（ａ））が、量子ビットＱＡ０〜ＱＡｊ−１に対してＮＯＴ演算を適用する（ステップＳ１０１）。次に、古典メモリ３０からＡを読み込んだ量子計算制御部６０の制御のもと、ＨＩＢＩＴ演算部３３１が、量子ビットＱＵ１〜ＱＵｊ−１，ＱＡ０〜ＱＡｊ−１，ＱＢ０〜ＱＢｊ−１，ＱＺに対し、ＨＩＧＨＢＩＴ演算を適用する（ステップＳ１０２）。なお、ＨＩＧＨＢＩＴ演算の詳細については後述する。次に、ＮＯＴ演算部３３２が、量子ビットＱＡ０〜ＱＡｊ−１，ＱＺに対してＮＯＴ演算を適用する（ステップＳ１０３）。次に、量子計算制御部６０の制御のもと、制御ＮＯＴ演算部３３３が、量子ビットＱＡ０〜ＱＡｊ−１を制御ビットとし、量子ビットＱＢ０〜ＱＢｊ−１を目標ビットとした制御ＮＯＴ演算を適用する（ステップＳ１０４）。その後、ＮＯＴ演算部３３２が、量子ビットＱＢ０〜ＱＢｊ−１に対し、ＮＯＴ演算を適用し（ステップＳ１０５）、Ｔｏｆｆｏｌｉ演算部３３４が、量子ビットＱＢ０〜ＱＢｊ−１を制御ビットとし、量子ビットＱＺを目標ビットとしたＴｏｆｆｏｌｉ演算を適用する（ステップＳ１０６）。さらにその後、ＮＯＴ演算部３３２が、量子ビットＱＢ０〜ＱＢｊ−１に対し、ＮＯＴ演算を適用する（ステップＳ１０７）。そして、量子計算制御部６０の制御のもと、制御ＮＯＴ演算部３３３が、量子ビットＱＡ０〜ＱＡｊ−１を制御ビットとし、量子ビットＱＢ０〜ＱＢｊ−１を目標ビットとした制御ＮＯＴ演算を適用する（ステップＳ１０８）。
【００５３】
［ＨＩＧＨＢＩＴ演算の詳細］
次に、ステップＳ１０２で触れたＨＩＧＨＢＩＴ演算の詳細を説明する。
図２４及び２５は、このＨＩＧＨＢＩＴ演算の詳細を説明するためのフローチャートである。また、図２７は、ｊ＝５の場合における、このＨＩＧＨＢＩＴ演算を例示した量子回路である。
図２７に例示するように、ＨＩＧＨＢＩＴ演算を示す量子回路は、Ａ＝ａｊ−１…ａ０とＢ＝ｂｊ−１…ｂ０とｕ１，…，ｕｊ−１とｚとをそれぞれ示す量子ビットＱＢ０〜ＱＢｊ−１，ＱＵ１〜ＱＵｊ−１，ＱＺに対し、Ｂ＝ｂｊ−１…ｂ０とｕ１，…，ｕｊ−１とをそれぞれ示す量子状態の量子ビットＱＡ０〜ＱＡｊ−１，ＱＢ０〜ＱＢｊ−１，ＱＵ１〜ＱＵｊ−１と、ｚ（＋）βを示す量子状態の量子ビットＱＺとを出力する。なお、βはＡ＋Ｂの最上位ビットの値を意味する。以下、ＨＩＧＨＢＩＴ演算の詳細を説明する。
【００５４】
まず、制御ＮＯＴ演算部３４１（図２２（ｂ））が、量子ビットＱＵｊ−１を制御ビットとし、量子ビットＱＺを目標ビットとしたＣＮＯＴ演算を適用する（ステップＳ１１１）。次に、量子計算制御部６０が変数ｇｃにｊ−１を代入し、これを古典メモリ３０に格納する（ステップＳ１１２）。
次に、古典メモリ３０から変数ｇｃを読み込んだ量子計算制御部６０の制御のもと、Ｅ演算部１４２が、量子ビットＱＵｇｃ，ＱＵｇｃ−１，ＱＡｇｃ，ＱＢｇｃに対し、Ｅ演算を適用する（ステップＳ１１３）。
【００５５】
図２８は、このＥ演算を示した量子回路である。図２８に示すように、Ｅ（演算は、ｐ，ｑ，ｒ，ｓ∈｛０，１｝をそれぞれ示す量子状態の４つの量子ビットＱＵｇｃ−１，ＱＡｇｃ，ＱＢｇｃ，ＱＵｇｃを入力とする。そして、Ｅ演算部１４２は、まず、量子ビットＱＡｇｃを制御ビットとし、量子ビットＱＢｇｃを目標ビットとした制御ＮＯＴ演算を適用する。次に、Ｅ演算部１４２は、量子ビットＱＵｇｃ−１，ＱＢｇｃを制御ビットとし、量子ビットＱＵｇｃを目標ビットとしたＴｏｆｆｏｌｉ演算を適用し、さらに、量子ビットＱＡｇｃを制御ビットとし、量子ビットＱＢｇｃを目標ビットとした制御ＮＯＴ演算を適用する。これらの操作により、４つの量子ビットＱＵｇｃ−１，ＱＡｇｃ，ＱＢｇｃ，ＱＵｇｃの量子状態が、それぞれｐ，ｑ,ｒ，ｓ（＋）（ｑ（＋）ｒ）・ｐを示すものとなる。以上がＥ演算である。
【００５６】
次に、量子計算制御部６０が、古典メモリ３０に格納された変数ｇｃが２であるか否かを判断する（ステップＳ１１４）。ここで、ｇｃ＝２でなければ、量子計算制御部６０は、ｇｃ−１を新たなｇｃとして古典メモリ３０に格納した後（ステップＳ１１５）、処理をステップＳ１１３に戻す。一方、ｇｃ＝２であれば、量子計算制御部６０の制御のもと、Ｔｏｆｆｏｌｉ演算部３４４は、量子ビットＱＡ１，ＱＢ１を制御ビットとし、量子ビットＱＵ１を目標ビットとしたＴｏｆｆｏｌｉ演算を適用する（ステップＳ１１６）。次に、制御ＮＯＴ演算部３４１は、
量子ビットＱＡ１を制御ビットとし、量子ビットＱＢ１を目標ビットとした制御ＮＯＴ演算を適用する（ステップＳ１１７）。さらに、Ｔｏｆｆｏｌｉ演算部３４４は、量子ビットＱＡ０，ＱＢ０，ＱＢ１を制御ビットとし、量子ビットＱＵ１を目標ビットとしたＴｏｆｆｏｌｉ演算を適用する（ステップＳ１１８）。図３０は、このようなＴｏｆｆｏｌｉ演算を示した量子回路である。なお図３０では、それぞれの量子状態が、ｐ，ｑ，ｒ，ｓである量子ビットＱＡ０，ＱＢ０，ＱＢ１，ＱＵ１を入力とした例を示している。
【００５７】
次に、Ｆ演算部３４３が、量子ビットＱＵｇｃ，ＱＵｇｃ−１ ，ＱＡｇｃ，ＱＢｇｃに対し、Ｆ演算を適用する（ステップＳ１１９）。
図２９は、このＦ演算を示した量子回路である。図２９に示すように、Ｆ演算は、ｐ，ｑ，ｒ，ｓ∈｛０，１｝をそれぞれ示す量子状態の４つの量子ビットＱＵｇｃ−１，ＱＡｇｃ，ＱＢｇｃ，ＱＵｇｃを入力とする。そして、Ｆ演算部３４３は、まず、量子ビットＱＡｇｃ，ＱＢｇｃを制御ビットとし、量子ビットＱＵｇｃを目標ビットとしたＴｏｆｆｏｌｉ演算を適用し、さらにＱＡｇｃを制御ビットとし、量子ビットＱＢｇｃを目標ビットとした制御ＮＯＴ演算を適用する。次に、Ｅ演算部１４２は、量子ビットＱＵｇｃ−１，ＱＢｇｃを制御ビットとし、量子ビットＱＵｇｃを目標ビットとしたＴｏｆｆｏｌｉ演算を適用する。これらの演算により、４つの量子ビットＱＵｇｃ−１，ＱＡｇｃ，ＱＢｇｃ，ＱＵｇｃの量子状態が、それぞれｐ，ｑ，ｑ（＋）ｒ，ｓ（＋）ｐ・ｑ（＋）ｑ・ｒ（＋）ｒ・ｐを示すものとなる。以上がＦ演算である。
【００５８】
次に、量子計算制御部６０が、古典メモリ３０に格納された変数ｇｃがｊ−１であるか否かを判断する（ステップＳ１２０）。ここで、ｇｃ＝ｊ−１でなければ、量子計算制御部６０は、ｇｃ＋１を新たなｇｃとして古典メモリ３０に格納した後（ステップＳ１２１）、処理をステップＳ１１９に戻す。一方、ｇｃ＝ｊ−１であれば、制御ＮＯＴ演算部１４１が、量子ビットＱＵｊ−１を制御ビットとし、量子ビットＱＺを目標ビットとしたＣＮＯＴ演算を適用する（ステップＳ１２２）。
次に、古典メモリ３０から変数ｇｃとＡの要素ａｇｃとを読み込んだ量子計算制御部６０の制御のもと、Ｆ−１演算部３４６が、量子ビットＱＵｇｃ，ＱＵｇｃ−１，ＱＡｇｃ，ＱＢｇｃに対し、Ｆ演算の逆演算であるＦ−１演算を適用する（ステップＳ１２３）。
【００５９】
次に、量子計算制御部６０が、古典メモリ３０に格納された変数ｇｃが２であるか否かを判断する（ステップＳ１２４）。ここで、ｇｃ＝２でなければ、量子計算制御部６０は、ｇｃ−１を新たなｇｃとして古典メモリ３０に格納した後（ステップＳ１２５）、処理をステップＳ１２３に戻す。一方、ｇｃ＝２であれば、Ｔｏｆｆｏｌｉ演算部３４４は、量子ビットＱＡ０，ＱＢ０，ＱＢ１を制御ビットとし、量子ビットＱＵ１を目標ビットとしたＴｏｆｆｏｌｉ演算を適用する（ステップＳ１２６）。次に、制御ＮＯＴ演算部３４１は、
量子ビットＱＡ１を制御ビットとし、量子ビットＱＢ１を目標ビットとした制御ＮＯＴ演算を適用する（ステップＳ１２７）。さらに、
Ｔｏｆｆｏｌｉ演算部３４４は、量子ビットＱＡ１，ＱＢ１を制御ビットとし、量子ビットＱＵ１を目標ビットとしたＴｏｆｆｏｌｉ演算を適用する（ステップＳ１２８）。
【００６０】
次に、古典メモリ３０から変数ｇｃを読み込んだ量子計算制御部６０の制御のもと、Ｅ演算部１４２が、量子ビットＱＵｇｃ，ＱＵｇｃ−１，ＱＡｇｃ，ＱＢｇｃに対し、Ｅ演算を適用する（ステップＳ１２９）。次に、量子計算制御部６０が、古典メモリ３０に格納された変数ｇｃがｊ−１であるか否かを判断する（ステップＳ１３０）。ここで、ｇｃ＝ｊ−１でなければ、量子計算制御部６０は、ｇｃ＋１を新たなｇｃとして古典メモリ３０に格納した後（ステップＳ１３１）、処理をステップＳ１２９に戻す。一方、ｇｃ＝ｊ−１であれば、ＨＩＧＨＢＩＴ演算を終了させる。
【００６１】
〔ハードウェア構成〕
次に各実施の形態の量子計算装置１，２００のハードウェア構成を例示する。
本形態の量子演算装置１は、量子コンピュータと古典コンユータとの組合せ、或いは量子コンピュータ単体で実現できる。量子コンピュータの実現する物理系としては、例えば、イオントラップを用いる方法（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)、
1127708374343_6
、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）ＲＡＭ等の読書き可能な半導体メモリである。また、古典メモリ３０の代わりに上述の量子メモリを用いてもよい。
なお、本発明は上述の実施の形態に限定されるものではなく、その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【産業上の利用可能性】
【００６７】
本発明の利用分野としては、例えば、ＲＳＡ等の因数分解の困難性に安全性の根拠をおく暗号方式の安全性評価装置等を例示できる。
【図面の簡単な説明】
【００６８】
【図１】図１は、第１の実施の形態における量子計算装置の構成を例示したブロック図である。
【図２】図２（ａ）は、第１の実施の形態におけるＣＶ演算部の詳細構成を例示した図である。図２（ｂ）は、Ｍ  ＭＯＤ演算部の詳細構成を例示した図である。図２（ｃ）は、ＡＤＤ  ＭＯＤ演算部の詳細構成を例示した図である。
【図３】図３（ａ）は、第１の実施の形態におけるＣＯＮＰＡＲＩＳＯＮ演算部の詳細構成を例示した図である。図３（ｂ）は、ＨＩＧＨＢＩＴ演算部の詳細構成を例示した図である。
【図４】図４は、第１の実施の形態の量子計算装置の処理の全体を説明するためのフローチャートである。
【図５】図５は、ＣＶ（Ａ）演算の詳細を説明するためのフローチャートである。
【図６】図６は、このＭ（Ａ）ＭＯＤ（Ｎ）演算の詳細を説明するためのフローチャートである。
【図７】図７は、ＡＤＤ（Ａ）ＭＯＤ（Ｎ）演算の詳細を説明するためのフローチャートである。
【図８】図８は、ＣＯＭＰＡＲＩＳＯＮ（Ａ）演算の詳細を説明するためのフローチャートである。
【図９】図９は、ＨＩＧＨＢＩＴ（Ａ）演算の詳細を説明するためのフローチャートである。
【図１０】図１０は、ＨＩＧＨＢＩＴ（Ａ）演算の詳細を説明するためのフローチャートである。
【図１１】図１１は、第１の実施の形態の量子計算装置の処理の全体を例示した量子回路である。
【図１２】図１２は、ｊ＝５の場合におけるＣＶ（Ａ）演算を例示した量子回路である。
【図１３】図１３は、ｊ＝５の場合におけるＭ（Ａ）ＭＯＤ（Ｎ）演算を例示した量子回路である。
【図１４】図１４は、ＳＷＡＰ演算を示した量子回路である。
【図１５】図１５は、ｊ＝５の場合におけるＡＤＤ（Ａ）ＭＯＤ（Ｎ）演算を例示した量子回路である。
【図１６】図１６は、ｊ＝５の場合におけるＣＯＭＰＡＲＩＳＯＮ（Ａ）演算を例示した量子回路である。
【図１７】図１７は、ｊ＝５の場合のＴｏｆｆｏｌｉ演算を示した量子回路である。
【図１８】図１８は、ｊ＝５の場合におけるＨＩＧＨＢＩＴ（Ａ）演算を例示した量子回路である。
【図１９】図１９は、Ｅ（ａｇｃ）演算を示した量子回路である。
【図２０】図２０は、Ｆ（ａｇｃ）演算を示した量子回路である。
【図２１】図２１は、第２の実施の形態における量子計算装置の機能構成を例示したブロック図である。
【図２２】図２２（ａ）は、第２の実施の形態のＣＶ演算部が有するＣＯＮＰＡＲＩＳＯＮ演算部の詳細構成を例示した図である。図２２（ｂ）は、ＨＩＧＨＢＩＴ演算部の詳細構成を例示した図である。
【図２３】図２３は、第２の実施の形態のＣＯＮＰＡＲＩＳＯＮ演算の詳細を説明するためのフローチャートである。
【図２４】図２４は、ＨＩＧＨＢＩＴ演算の詳細を説明するためのフローチャートである。
【図２５】図２５は、ＨＩＧＨＢＩＴ演算の詳細を説明するためのフローチャートである。
【図２６】図２６は、ｊ＝５の場合における、第２の実施の形態のＣＯＭＰＡＲＩＳＯＮ演算を例示した量子回路である。
【図２７】図２７は、ｊ＝５の場合における、第２の実施の形態のＨＩＧＨＢＩＴ演算を例示した量子回路である。
【図２８】図２８は、Ｅ演算を示した量子回路である。
【図２９】図２９は、Ｆ演算を示した量子回路である。
【図３０】図３０は、Ｔｏｆｆｏｌｉ演算を示す量子回路である。
【図３１】図３１は、位数発見に有用な値を発見する量子回路の従来構成を示した図である。
【図３２】図３２（ａ）は、図３１の演算子Ｈを示す量子回路であり、図３２（ｂ）は、図３１の演算子Ｘを示す量子回路である。
【図３３】図３３は、図３１の演算子Ｒを示す量子回路である。
【図３４】図３４は、図３１におけるＣＵ（Ａ）＝ＣＵ（Ａ・２０）の演算の詳細を示した量子回路である。
【図３５】図３５は、図３４のＣＳＷＡＰ演算を示す量子回路である。
【図３６】図３６（ａ）は、ＮＯＴ演算を示す量子回路であり、図３６（ｂ）は、制御ＮＯＴ演算を示す量子回路である。
【図３７】図３７は、Ｔｏｆｆｏｌｉ演算を示す量子回路である。
【図３８】図３８は、図３４におけるＣＭＵＬＴ（Ａ）ＭＯＤ（Ｎ）の演算の詳細を示した量子回路である。
【図３９】図３９は、図３８におけるＱＦＴの演算の詳細を示した量子回路である。
【図４０】図４０は、図３９の演算子Ｋ∈｛２，…，６｝を示した量子回路である。
【図４１】図４１は、図３８におけるφＡＤＤ（Ａ）ＭＯＤ（Ｎ）＝φＡＤＤ（２０・Ａ）ＭＯＤ（Ｎ）の演算の詳細を示した量子回路である。
【図４２】図４２は、図４１におけるφＡＤＤ（Ａ）演算の詳細を示した量子回路である。
【図４３】図４３は、図４２における演算子σｋ（ｋ∈｛１，…，５｝）を示した量子回路である。
【符号の説明】
【００６９】
１，２００  量子計算装置
【図１】
2007087307.tif 000009
【図２】
2007087307.tif 000010
【図３】
2007087307.tif 000011
【図４】
2007087307.tif 000012
【図５】
2007087307.tif 000013
【図６】
2007087307.tif 000014
【図７】
2007087307.tif 000015
【図８】
2007087307.tif 000016
【図９】
2007087307.tif 000017
【図１０】
2007087307.tif 000018
【図１１】
2007087307.tif 000019
【図１２】
2007087307.tif 000020
【図１３】
2007087307.tif 000021
【図１４】
2007087307.tif 000022
【図１５】
2007087307.tif 000023
【図１６】
2007087307.tif 000024
【図１７】
2007087307.tif 000025
【図１８】
2007087307.tif 000026
【図１９】
2007087307.tif 000027
【図２０】
2007087307.tif 000028
【図２１】
2007087307.tif 000029
【図２２】
2007087307.tif 000030
【図２３】
2007087307.tif 000031
【図２４】
2007087307.tif 000032
【図２５】
2007087307.tif 000033
【図２６】
2007087307.tif 000034
【図２７】
2007087307.tif 000035
【図２８】
2007087307.tif 000036
【図２９】
2007087307.tif 000037
【図３０】
2007087307.tif 000038
【図３１】
2007087307.tif 000039
【図３２】
2007087307.tif 000040
【図３３】
2007087307.tif 000041
【図３４】
2007087307.tif 000042
【図３５】
2007087307.tif 000043
【図３６】
2007087307.tif 000044
【図３７】
2007087307.tif 000045
【図３８】
2007087307.tif 000046
【図３９】
2007087307.tif 000047
【図４０】
2007087307.tif 000048
【図４１】
2007087307.tif 000049
【図４２】
2007087307.tif 000050
【図４３】
2007087307.tif 000051