JP4366348B2 - 量子計算方法及び量子計算装置 - Google Patents

Description

本発明は、量子コンピュータ分野に関し、特に、量子コンピュータを用いて位数発見に有用な数を得る技術に関する。

ｊ桁の２進数ＮとＮより小さい２進数Ａとを入力とし、２ｊ＋３個の量子ビットを使って、ｊの４乗に比例した個数の基本演算をｊの３乗に比例した計算ステップ数で実行することにより、Ａのｍｏｄ Ｎに関する位数（すなわち、Ａ^Ｒ＝１ ｍｏｄ Ｎとなる最小の２進数Ｒ）の発見に有用な２ｊ桁の２進数Ｃを高い確率で出力する量子回路の構成方法が知られている（例えば、非特許文献１参照）。ここで、「位数発見に有用な２ｊ桁の２進数Ｃ」とは、非特許文献２の式（５．１３）のｃを意味する。このＣをｊに関する多項式個の基本演算を使った古典回路に入力することにより、Ａのｍｏｄ Ｎに関する位数Ｒ（非特許文献２ではｒ）を高い確率で求めることができる。

以下、非特許文献１に記載された従来の量子回路を概説する。なお、量子回路は、量子ビットに対する演算とＣＮＯＴ演算とを基本演算とするが、図が複雑になるのを避けるため、以下では、これらの演算以外の演算も使って量子回路を構成する。すなわち、この量子回路に使われる全ての演算は、１量子ビットに対する演算とＣＮＯＴ演算に分解できる（例えば、非特許文献３参照）。なお、各図はｊ＝５の場合であるが、これらの量子回路を一般のｊの場合に拡張することは容易である。また、入力に表れる各変数は、０又は１を表す。さらに、重ね合わせ状態に対する量子回路の出力は、各量子状態の線形結合により表現し、Ｎより大きい全ての数はｍｏｄ Ｎで解釈される。また、｜・〉は・を示す量子状態を意味する。

図３１は、この位数発見に有用な値を発見する量子回路の従来構成を示した図である。なお、図３１の構成では、量子状態がそれぞれ｜０〉と｜１〉である２個の量子ビットと、量子状態｜０〉の２ｊ＋１個の量子ビットとに対して量子操作を行い、観測によって位数発見に有用な２ｊ桁の２進数ｃ_２ｊ−１…ｃ_０が得られる。なお、Ｈ，Ｘ，Ｒは、それぞれ図３２（ａ）（ｂ）及び図３３のように定義された演算子である。
図３４は、図３１におけるＣＵ（Ａ）＝ＣＵ（Ａ・２^０）の演算の詳細を示した量子回路である。図３４に示すようにＣＵ（Ａ）は、ｄ∈｛０，１｝と、Ｕ＝ｕ_０・・・ｕ_４と、ｊ＋２個の０とをそれぞれ示す量子状態の入力に対し、ｄ＝１であれば、ｄとＡ・Ｕ ｍｏｄ Ｎの各桁（ｄとＡ・Ｕ ｍｏｄ Ｎ）_０・・・（ｄとＡ・Ｕ ｍｏｄ Ｎ）_４と、ｊ＋２個の０とをそれぞれ示す量子状態を生成し、ｄ＝０であれば、入力の量子状態をそのまま出力する。ここで、図３４のＣＳＷＡＰは、図３５のように示すような演算子である。また、図３５に用いられる各演算子の構成を図３６（ａ）（ｂ）及び図３７に示す。なお、図３１のＣＵ（Ａ・２^１）・・・ＣＵ（Ａ・２^９）は、図３４のＡをＡ・２^１・・・Ａ・２^９に置換したものになる。

図３８は、図３４におけるＣＭＵＬＴ（Ａ）ＭＯＤ（Ｎ）の演算の詳細を示した量子回路である。図３８に示すように、ＣＭＵＬＴ（Ａ）ＭＯＤ（Ｎ）は、ｄと、Ｕと、Ｂ＝ｂ_ｊ−１…ｂ_０の最上位ビットに０を加えた値と、０とをそれぞれ示す量子状態を入力とし、ｄ＝１であれば、ｄとＵとＡ・Ｕ＋Ｍ ｍｏｄ Ｎの各桁と０と０とをそれぞれ示す量子状態を生成し、ｄ＝０であれば、入力の量子状態をそのまま出力する。なお、ＣＭＵＬＴ（Ａ^−１）ＭＯＤ（Ｎ）は、図３８のＡをＡ^−１に置換したものになる。
図３９は、図３８におけるＱＦＴ（量子フーリエ変換）の演算の詳細を示した量子回路である。なお、図３９のＫ∈｛２，…，６｝は図４０のような演算子である。また、図３８のＱＦＴ^−１は、ＱＦＴの逆演算を示す。

図４１は、図３８におけるφＡＤＤ（Ａ）ＭＯＤ（Ｎ）＝φＡＤＤ（２^０・Ａ）ＭＯＤ（Ｎ）の演算の詳細を示した量子回路である。φＡＤＤ（Ａ）ＭＯＤ（Ｎ）は、ｄ_１，ｄ_２と、最上位ビットに０を加えたＢにＱＦＴを適用した値φ_ｊ（Ｂ），…，φ_０（Ｂ）と、０とをそれぞれ示す量子状態を入力とし、ｄ_１＝ｄ_２＝１であれば、ｄ_１，ｄ_２と、Ａ＋Ｂ ｍｏｄ ＮにＱＦＴを適用した値φ_ｊ（Ａ＋Ｂ ｍｏｄ Ｎ），…，φ_０（Ａ＋Ｂ ｍｏｄ Ｎ）と、０とをそれぞれ示す量子状態を生成し、ｄ_１＝ｄ_２＝１でなければ、入力の量子状態をそのまま出力する。なお、図４１におけるφＡＤＤ（Ａ）は、図４２に示すような演算子であり、最上位ビットに０を加えたＢにＱＦＴを適用した値φ_ｊ（Ｂ），…，φ_０（Ｂ）を示す量子状態を入力とし、Ａ＋ＢにＱＦＴを適用した値値φ_ｊ（Ａ＋Ｂ），…，φ_０（Ａ＋Ｂ）を示す量子状態を生成する。なお、図４２におけるσ_ｋ（ｋ∈｛１，…，５｝）は、図４３に示すような演算子である。また、φＡＤＤ（Ａ）^−１は、φＡＤＤ（Ａ）の逆演算である。また、φＡＤＤ（Ｎ）やφＡＤＤ（Ｎ）^−１は、φＡＤＤ（Ａ）やφＡＤＤ（Ａ）^−１のＡをＮに置換した演算子である。なお、その他のφＡＤＤ（Ａ・２^１）ＭＯＤ（Ｎ）・・・φＡＤＤ（Ａ・２^４）ＭＯＤ（Ｎ）については、図４１のＡをＡ・２^１・・・Ａ・２^４に置換したものになる。
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.

上述のように、非特許文献１の量子回路では、ｊ桁の２進数Ｎと、Ｎより小さいｊ桁の２進数進数Ａとから、Ａのｍｏｄ Ｎに関する位数の発見に有用な２ｊ桁の２進数Ｃを高い確率で出力するためには、ｊの４乗に比例した個数の基本演算と、ｊの３乗に比例した計算ステップ数と、２ｊ＋３個の量子ビットとを必要とする。しかし、多数の量子ビットを実現し、協調的に操作するのは物理的に困難なため、量子ビット数はできるだけ少ないほうが良い。
本発明はこのような点に鑑みてなされたものであり、従来よりも少ない量子ビットを使って、位数発見に有用な２ｊ桁の２進数Ｃを高い確率で求めることを可能にする技術を提供することを目的とする。

本発明では上記課題を解決するために、２進数ｊ桁のＮ＝ｎ_ｊ−１…ｎ_０とＡ＝ａ_ｊ−１…ａ_０とをメモリに格納しておき（ｎ_ｈ−１は２進数表記されたＮのｈ桁目の値、ａ_ｈ−１は２進数表記されたＡのｈ桁目の値）、減算部が、メモリから読み込んだＮとＡとからＮ−Ａを算出する。また、ＣＯＭＰＡＲＩＳＯＮ演算部が、減算部で算出されたＮ−Ａを用い、Ｎよりも小さい２進数ｊ桁のＢ＝ｂ_ｊ−１…ｂ_０の各桁をそれぞれ示す量子状態の量子ビットＱＢ_ｊ−１，…，ＱＢ_０と、任意の量子状態の量子ビットＱＵ_ｊ−１，…，ＱＵ_１，ＱＺと、に対する第１量子操作を行い、Ｎ−Ａ＞Ｂの場合にのみ量子ビットＱＺの量子状態を反転させる。そして、ＣＯＭＰＡＲＩＳＯＮ演算部によって処理された量子ビットＱＺは、そのまま或いは反転されて、他の量子演算の制御ビットとして用いられる。

ここで、このＣＯＭＰＡＲＩＳＯＮ演算部の処理内容は、非特許文献１では、図４１におけるφＡＤＤ（Ａ），φＡＤＤ（Ｎ）^−１及びＱＦＴ^−１の処理に包含されていたものである。しかし、従来の図４１の構成では、φＡＤＤ（Ａ），φＡＤＤ（Ｎ）^−１及びＱＦＴ^−１の処理が施された量子ビットの１つ（図４１の下から２個目の量子ビット）の量子状態を、ＣＮＯＴ演算によって他の量子ビット（図４１の最下部の量子ビット）に移し、この他の量子ビットを他の量子演算〔φＡＤＤ（Ｎ）〕の制御ビットとしなければならなかった。これに対し、本発明では、ＣＯＭＰＡＲＩＳＯＮ演算部によって処理された量子ビットＱＺそのものを他の量子演算の制御ビットとして用いることができる。そのため、従来、量子状態を移すために必要であった量子ビットを一つ削減できる。また、本発明では、ＣＯＭＰＡＲＩＳＯＮ演算部が、従来の図４１におけるφＡＤＤ（Ａ），φＡＤＤ（Ｎ）^−１及びＱＦＴ^−１が全く操作していなかった量子ビットＱＵ_ｊ−１，…，ＱＵ_１（値ｕ_４，…，ｕ_１の量子状態を示す量子ビット）の操作も行い、量子ビットの有効利用を図っている。これも本発明の構成が、従来よりも量子ビット数を削減できる理由である。

また、本発明において好ましくは、ＣＯＭＰＡＲＩＳＯＮ演算部が、任意の量子状態の量子ビットＱＤ_１，ＱＤ_２を制御ビットとして、上述の第１量子操作を行い、ＱＦＴ演算部が、量子ビットＱＢ_ｊ−１，…，ＱＢ_０に対して量子フーリエ変換操作を施す。そして、量子ビットＱＤ_１，ＱＤ_２，ＱＺを制御ビットとし、φＡＤＤ演算部が、１を示す量子状態の量子ビットＱＢ_ｋ（ｋ∈｛ｊ−１，…，０｝）のみに対し、

（ただし、量子ビットＱＢ_ｋの量子状態を｜ＱＢ_ｋ〉とし、ｅをネピア数とし、ｉを虚数単位とする）の演算を施し、第１ＮＯＴ演算部が、量子ビットＱＺにＮＯＴ演算を施す。さらに、量子ビットＱＤ_１，ＱＤ_２，ＱＺを制御ビットとし、φＡＤＤ^−１演算部が、１を示す量子状態の量子ビットＱＢ_ｋのみに対し、

（ただし、Ｎ−Ａ＝（ｎ−ａ）_ｊ−１…（ｎ−ａ）_０とする）の演算を施し、第１ＮＯＴ演算部が、量子ビットＱＺにＮＯＴ演算を施す。そして、ＱＦＴ^−１演算部が、量子ビットＱＢ_ｊ−１，…，ＱＢ_０に対して量子フーリエ変換の逆演算操作を施し、ＣＯＭＰＡＲＩＳＯＮ演算部が、量子ビットＱＤ_１，ＱＤ_２を制御ビットとして、量子ビットＱＢ_ｊ−１，…，ＱＢ_０，ＱＵ_ｊ−１，…，ＱＵ_１，ＱＺに対し、Ａ＞Ｂの場合にのみ量子ビットＱＺの量子状態を反転させる量子操作を行い、第１Ｔｏｆｆｏｌｉ演算部が、量子ビットＱＤ_１，ＱＤ_２を制御ビットとし、量子ビットＱＺを目標ビットとしたＴｏｆｆｏｌｉ演算を施す。

ここで、ＣＯＭＰＡＲＩＳＯＮ演算部の第１量子操作が施された量子ビットＱＺは、φＡＤＤ演算部やφＡＤＤ^−１演算部の量子演算の制御ビットとして用いられている。これにより、従来構成に比べ量子ビット数を１つ削減できる。
また、本発明において好ましくは、ＣＯＭＰＡＲＩＳＯＮ演算部が行う第１量子操作は、ＨＩＧＨＢＩＴ演算部が、量子ビットＱＢ_ｊ−１，…，ＱＢ_０と、量子ビットＱＵ_ｊ−１，…，ＱＵ_１と、量子ビットＱＺと対して第２量子操作を行い、量子ビットＱＺを、ｚ（＋）β〔βはＡ−Ｎ＋Ｂの最上位桁、（＋）は排他的論理和〕を示す量子状態とし、他の量子ビットＱＢ_ｊ−１，…，ＱＢ_０、ＱＵ_ｊ−１，…，ＱＵ_１の量子状態を当該第２量子操作前の量子状態とし、第２ＮＯＴ演算部が、量子ビットＱＺにＮＯＴ演算を施し、古典制御ＮＯＴ演算部が、メモリから読み込まれたＡ−Ｎの桁（ａ−ｎ）_ｈ（ｈ∈｛ｊ−１，…，０｝）が１となるｈに対応する量子ビットＱＢ_ｈのみにＮＯＴ演算を施し、第３ＮＯＴ演算部が、各量子ビットＱＢ_ｊ−１，…，ＱＢ_０にＮＯＴ演算を施し、第２Ｔｏｆｆｏｌｉ演算部が、各量子ビットＱＢ_ｊ−１，…，ＱＢ_０を制御ビットとし、量子ビットＱＺを目標ビットとしたＴｏｆｆｏｌｉ演算を施し、第３ＮＯＴ演算部が、各量子ビットＱＢ_ｊ−１，…，ＱＢ_０にＮＯＴ演算を施し、古典制御ＮＯＴ演算部が、メモリから読み込まれたＡ−Ｎの桁（ａ−ｎ）_ｈが１となるｈに対応する量子ビットＱＢ_ｈのみにＮＯＴ演算を施す操作である。

このように、ＨＩＧＨＢＩＴ演算部が、量子ビットＱＵ_ｊ−１，…，ＱＵ_１に対しても量子操作を行う構成をとることによって量子ビットの有効利用を図り、必要となる量子ビット数の低減を図っている。

以上のように本発明では、従来よりも少ない量子ビットを使って、位数発見に有用な２ｊ桁の２進数Ｃを高い確率で求めることが可能となる。

以下、本発明の実施の形態を図面を参照して説明する。
〔第1の実施の形態〕
＜機能構成＞
図１は、本形態における量子計算装置１の構成を例示したブロック図である。
図１に例示するように、本形態の量子計算装置１は、量子ビット１０、入力部２０、古典メモリ３０、減算部４０、乗算部５０、量子計算制御部６０、量子演算部７０及び観測部８０を有している。また、量子演算部７０は、初期量子状態生成部７１、ＣＶ部７２、Ｈ（アダマール）演算部、Ｒ_ｋ演算部７４及びＸ^ＣＫ演算部７５を有している。

図２（ａ）は、ＣＶ演算部７２の詳細構成を例示した図である。この図に示すように、ＣＶ演算部７２は、Ｍ ＭＯＤ演算部１０１及びＣＳＷＡＰ演算部１０２を有している。図２（ｂ）は、Ｍ ＭＯＤ演算部１０１の詳細構成を例示した図である。この図に示すようにＭ ＭＯＤ演算部１０１は、ＡＤＤ ＭＯＤ演算部１１１及びＳＷＡＰ演算部１１２を有している。図２（ｃ）は、ＡＤＤ ＭＯＤ演算部１１１の詳細構成を例示した図である。この図に示すようにＡＤＤ ＭＯＤ演算部１１１は、ＣＯＮＰＡＲＩＳＯＮ演算部１２１、ＱＦＴ演算部１２２、ＱＦＴ^−１演算部１２３、φＡＤＤ演算部１２４、φＡＤＤ^−１演算部１２５、ＮＯＴ演算部１２６及びＴｏｆｆｏｌｉ演算部１２７を有している。図３（ａ）は、ＣＯＮＰＡＲＩＳＯＮ演算部１２１の詳細構成を例示した図である。この図に示すようにＣＯＮＰＡＲＩＳＯＮ演算部１２１は、ＨＩＧＨＢＩＴ演算部１３１、ＮＯＴ演算部１３２、古典制御ＮＯＴ演算部１３３及びＴｏｆｆｏｌｉ演算部１３４を有している。図３（ｂ）は、ＨＩＧＨＢＩＴ演算部１３１の詳細構成を例示した図である。この図に示すようにＨＩＧＨＢＩＴ演算部１３１は、制御ＮＯＴ演算部１４１、Ｅ演算部１４２、Ｆ演算部１４３、Ｔｏｆｆｏｌｉ演算部１４４、ＮＯＴ演算部１４５及びＦ^−１演算部１４３を有している。なお、特に断りが無い限り、量子計算装置１は、量子計算制御部６０の制御のもと各処理を実行する。また、各要素の機能構成の詳細やハードウェア構成の詳細については後述する。

＜処理＞
［処理の全体］
量子計算装置１は、入力されたｊ桁の２進数Ｎ＝ｎ_ｊ−１…ｎ_０（ｎ_ｊ−１,…,ｎ_０∈｛０，１｝）と、Ｎより小さいｊ桁の２進数Ａ＝ａ_ｊ−１…ａ_０（ａ_ｊ−１,…,ａ_０∈｛０，１｝）に対し、２ｊ＋２個の量子ビットを用いたｊの３乗に比例した計算ステップ数のｊの４乗に比例した個数の基本演算を施し、位数発見に有用な２ｊ桁の２進数Ｃ＝ｃ_２ｊ−１…ｃ_０（ｃ_ｊ−１,…,ｃ_０∈｛０，１｝）を高い確率で出力する。以下、この処理の詳細を説明していく。

図４は、本形態の量子計算装置１の処理の全体を説明するためのフローチャートである。また、図１１は、この処理の全体を例示した量子回路である。なお、量子回路は、１量子ビットに対する演算とＣＮＯＴを基本演算とするが、図が複雑になるのを避けるため、図１１では、これらの演算以外の演算も使って表現している。また、この量子回路に使われる全ての演算は，１量子ビットに対する演算とＣＮＯＴに分解できる（前述の非特許文献３参照）。また、図１１は、ｊ＝５の場合の例である。また、Ｎより大きい全ての数はｍｏｄ Ｎで解釈される。

図１１に例示するように、本形態の量子回路は、０と１と２ｊ個の０とをそれぞれ示す量子ビットを入力とし、位数発見に有用な２ｊ桁の２進数Ｃ＝ｃ_２ｊ−１…ｃ_０を出力するものである。この構成は，従来構成を示した図３１において、上から２ｊ＋３番目の量子状態を保持する量子ビットを削除し、ＣＵ（ａ）をＣＶ（ａ）に置換したものに相当する。以下、この量子回路を構成する処理の全体を説明する。
まず、２進数ｊ桁のＮ＝ｎ_ｊ−１…ｎ_０と、Ｎよりも小さい２進数ｊ桁のＡ＝ａ_ｊ−１…ａ_０とが入力部２０から入力され、古典メモリ３０（図１）に格納される（ステップＳ１）。なお、ｊは例えば予め装置に設定された値とする。次に、量子計算制御部６０の制御のもと初期量子状態生成部７１が、量子ビットＱＤ_１，ＱＤ_２，ＱＵ_１〜ＱＵ_ｊ−１，ＱＢ_０〜ＱＢ_ｊ−１，ＱＺの初期量子状態を生成する（ステップＳ２）。この例では、量子ビットＱＤ_２の量子状態を、１を示すものとし、他の量子ビットの量子状態を、０を示すものとする。次に、Ｈ演算部７３が、量子ビットＱＤ_１に対してＨ（アダマール）演算（図３２（ａ））を適用する（ステップＳ３）。なお、量子演算を適用するとは、演算に相当する量子操作を量子ビットに施すことを意味する。次に、量子計算制御部６０が変数ｇａに０を代入して古典メモリ３０に格納し、さらに乗算部５０が古典メモリ３０から読み出したＡ及びｇａを用いてＡ・２^{２ｊ−ｇａ−１}を算出し、これを量子計算制御部６０に送る（ステップＳ４）。次に、量子計算制御部６０は、送られたＡ・２^{２ｊ−ｇａ−１}を用いてＣＶ演算部７２を制御し、ＣＶ演算部７２は、量子ビットＱＤ_１を制御ビットとして、量子ビットＱＤ_２，ＱＵ_１〜ＱＵ_ｊ−１，ＱＢ_０〜ＱＢ_ｊ−１，ＱＺに対し、ＣＶ（Ａ・２^{２ｊ−ｇａ−１}）演算を適用する（ステップＳ５）。なお、この演算の詳細は後述する。次に、Ｈ演算部７３が、量子ビットＱＤ_１に対してＨ演算（図３２（ａ））を適用する（ステップＳ６）。次に、量子計算制御部６０が、古典メモリ３０から変数ｇａを読み出し、観測部８０に量子ビットＱＤ_１の量子状態を観測させて、その観測結果をｃ_ｇａとして古典メモリ３０に格納する（ステップＳ７）。この観測により量子ビットＱＤ_１の量子状態はｃ_ｇａに縮約する（以下も同様）。

次に、量子計算制御部６０が、古典メモリ３０からｃ_ｇａを読み出し、Ｘ^ｃｋ演算部７５に、ｋ＝ｇａとした図３２（ｂ）の量子操作を量子ビットＱＤ_１に対して適用させ、さらに、Ｈ演算部７３に、量子ビットＱＤ_１に対するＨ演算（図３２（ａ））を適用させる（ステップＳ８）。次に、量子計算制御部６０は、古典メモリ３０に格納された変数ｇａを読み出し、ｇａ＋１を新たなｇａとして更新し、これを古典メモリ３０に格納する（ステップＳ９）。次に、乗算部５０が古典メモリ３０から読み出したＡ及びｇａを用いてＡ・２^{２ｊ−ｇａ−１}を算出し、これを量子計算制御部６０に送る。量子計算制御部６０は、送られたＡ・２^{２ｊ−ｇａ−１}を用いてＣＶ演算部７２を制御し、ＣＶ演算部７２は、量子ビットＱＤ_１を制御ビットとして、量子ビットＱＤ_２，ＱＵ_１〜ＱＵ_ｊ−１，ＱＢ_０〜ＱＢ_ｊ−１，ＱＺに対し、ＣＶ（Ａ・２^{２ｊ−ｇａ−１}）演算を適用する（ステップＳ１０）。なお、この演算の詳細は後述する。次に、Ｒ_ｋ演算部７４が、量子ビットＱＤ_１に対してｋ＝ｇａとしたＲ_ｋ演算（図３３）を適用し（ステップＳ１１）、観測部８０が量子ビットＱＤ_１の量子状態を観測し、その観測結果をｃ_ｇａとして古典メモリ３０に格納する（ステップＳ１２）。

次に、量子計算制御部６０において、古典メモリ３０に格納されたｇａが２ｊ−１であるか否かを判断する。ここで、ｇａ＝２ｊ−１でなければ、量子計算制御部６０は処理をステップＳ８に戻す。一方、ｇａ＝２ｊ−１であれば、量子計算制御部６０は、古典メモリ３０に蓄積されたＣ＝ｃ_２ｊ−１…ｃ_０を出力する。
［ＣＶ（Ａ）演算の詳細］
次に、ステップＳ５，Ｓ１１で触れたＣＶ演算の詳細を説明する。なお、以下では、ＡをパラメータとしたＣＶ（Ａ）演算を例にとって説明するが、このＡをＡ・２^{２ｊ−ｇａ−１}に置換すればＣＶ（Ａ・２^{２ｊ−ｇａ−１}）演算に一般化できる。

図５は、このＣＶ（Ａ）演算の詳細を説明するためのフローチャートである。また、図１２は、ｊ＝５の場合におけるＣＶ（Ａ）演算を例示した量子回路である。
図１２に例示するように、ＣＶ（Ａ）演算を示す量子回路は、ｄとＵ＝ｕ_ｊ−１…ｕ_０（ｕ_ｊ−１，…,ｕ_０∈｛０，１｝）とｊ＋１個の０とをそれぞれ示す量子状態の量子ビットＱＤ_１，ＱＤ_２，ＱＵ_１〜ＱＵ_{ｊ−１〔ＱＵｈ’（ｈ’∈｛０，…，ｊ−１｝）が}ｕ_ｈ’に対応_〕，ＱＢ_０〜ＱＢ_ｊ−１，ＱＺを入力とし、ｄ＝１であれば、量子ビットＱＤ_１，ＱＤ_２，ＱＵ_１〜ＱＵ_ｊ−１，ＱＢ_０〜ＱＢ_ｊ−１，ＱＺを、ｄとＡ・Ｕ ｍｏｄ Ｎの各桁（Ａ・Ｕ ｍｏｄ Ｎ）_０…（Ａ・Ｕ ｍｏｄ Ｎ）_ｊ−１とｊ＋１個の０とをそれぞれ示す量子状態とし、ｄ＝０であれば、入力の量子状態を維持するものである。この構成は、図３４の従来構成において、上から２ｊ＋３番目の量子状態を保持する量子ビットを削除し、ＣＭＵＬＴ（Ａ）ＭＯＤ（Ｎ）をＭ（Ａ）ＭＯＤ（Ｎ）に置換したものに相当する。以下、このＣＶ（Ａ）演算の詳細を説明する。

まず、古典メモリ３０からＡを読み込んだ量子計算制御部６０の制御のもと、Ｍ ＭＯＤ演算部１０１（図２（ａ））が、量子ビットＱＤ_１を制御ビットとして、量子ビットＱＤ_２，ＱＵ_１〜ＱＵ_ｊ−１，ＱＢ_０〜ＱＢ_ｊ−１，ＱＺに対し、Ｍ（Ａ）ＭＯＤ（Ｎ）演算を適用する（ステップＳ２１）。なお、Ｍ（Ａ）ＭＯＤ（Ｎ）演算の詳細については後述する。次に、ＣＳＷＡＰ演算部１０２が、量子ビットＱＤ_１，ＱＤ_２，ＱＵ_１〜ＱＵ_ｊ−１，ＱＢ_０〜Ｑ_Ｂｊ−１に対しＣＳＷＡＰ演算（図３５）を適用する（ステップＳ２２）。次に、乗算部５０（図１）が古典メモリ３０に格納されたＡを用いてＡ^−１を算出し（ステップＳ２３）、量子計算制御部６０に送る。量子計算制御部６０は、このＡ^−１を用いてＭ ＭＯＤ演算部１０１を制御し、Ｍ ＭＯＤ演算部１０１は、量子ビットＱＤ_１を制御ビットとして、量子ビットＱＤ_２，ＱＵ_１〜ＱＵ_ｊ−１，ＱＢ_０〜ＱＢ_ｊ−１，ＱＺに対し、Ｍ（Ａ^−１）ＭＯＤ（Ｎ）演算を適用する（ステップＳ２４）。

［Ｍ（Ａ）ＭＯＤ（Ｎ）演算の詳細］
次に、ステップＳ２１，Ｓ２４で触れたＭ（Ａ）ＭＯＤ（Ｎ）演算, Ｍ（Ａ^−１）ＭＯＤ（Ｎ）演算の詳細を説明する。なお、以下では、ＡをパラメータとしたＭ（Ａ）ＭＯＤ（Ｎ）演算を例にとって説明するが、このＡをＡ^−１に置換すればＭ（Ａ^−１）ＭＯＤ（Ｎ）演算となる。
図６は、このＭ（Ａ）ＭＯＤ（Ｎ）演算の詳細を説明するためのフローチャートである。また、図１３は、ｊ＝５の場合におけるＭ（Ａ）ＭＯＤ（Ｎ）演算を例示した量子回路である。

図１３に例示するように、Ｍ（Ａ）ＭＯＤ（Ｎ）演算を示す量子回路は、ｄとＵとＢ＝ｂ_ｊ−１…ｂ_０（ｂ_ｊ−１,…,ｂ_０∈｛０，１｝）と０とをそれぞれ示す量子状態の量子ビットＱＤ_１，ＱＤ_２，ＱＵ_１〜ＱＵ_ｊ−１，ＱＢ_０〜ＱＢ_{ｊ−１〔ＱＢｈ（ｈ∈｛０，…，ｊ−１｝）がｂｈ}に対応_〕，ＱＺを入力とし、ｄ＝１であれば、ｄとＵとＡ・Ｘ＋Ｂ ｍｏｄ Ｎと０とをそれぞれ示す量子状態の量子ビットＱＤ_１，ＱＤ_２，ＱＵ_１〜ＱＵ_ｊ−１，ＱＢ_０〜ＱＢ_ｊ−１を出力し、ｄ＝０であれば、入力の量子状態を維持するものである。ただし、Ａ・Ｘ＋Ｂ ｍｏｄ Ｎ＝（Ａ・Ｘ＋Ｂ ｍｏｄ Ｎ）_ｊ−１…（Ａ・Ｘ＋Ｂ ｍｏｄ Ｎ）_０であり、_{ＱＢｈ（ｈ∈｛０，…，ｊ−１｝）が}（Ａ・Ｘ＋Ｂ ｍｏｄ Ｎ）_{ｈに対応する。以下、この}Ｍ（Ａ）ＭＯＤ（Ｎ）演算の詳細を説明する。

まず、古典メモリ３０からＡを読み込んだ量子計算制御部６０の制御のもと、ＡＤＤ ＭＯＤ演算部１１１（図２（ｂ））が、量子ビットＱＤ_１，ＱＤ_２を制御ビットとして、量子ビットＱＵ_１〜ＱＵ_ｊ−１，ＱＢ_０〜ＱＢ_ｊ−１，ＱＺに対し、ＡＤＤ（２^０・Ａ）ＭＯＤ（Ｎ）演算を適用する（ステップＳ３１）。なお、ＡＤＤ（２^０・Ａ）ＭＯＤ（Ｎ）演算の詳細については後述する。次に、量子計算制御部６０が変数ｇｂに１代入し、この変数ｇｂを古典メモリ３０に格納する（ステップＳ３２）。次に、古典メモリ３０から変数ｇｂを読み込んだ量子計算制御部６０の制御のもと、ＳＷＡＰ演算部１１２が、量子ビットＱＤ_２と量子ビットＱＵ_ｇｂに対し、ＳＷＡＰ演算を適用する（ステップＳ３３）。なお、ＳＷＡＰ演算とは、図１４のように３つの制御ＮＯＴ演算を組み合わせた演算を意味する。ここでｘ，ｙ∈｛０，１｝である。このＳＷＡＰ演算により、入力された２つの量子ビットの量子状態が入れ替わる。

次に乗算部５０が古典メモリ３０からＡと変数ｇｂとを読み込み、２^ｇｂ・Ａを計算して量子計算制御部６０に送る（ステップＳ３４）。量子計算制御部６０は、２^ｇｂ・Ａを用いてＡＤＤ ＭＯＤ演算部１１１を制御し、ＡＤＤ ＭＯＤ演算部１１１は、量子ビットＱＤ_１，ＱＤ_２を制御ビットとして、量子ビットＱＵ_１〜ＱＵ_ｊ−１，ＱＢ_０〜ＱＢ_ｊ−１，ＱＺに対し、ＡＤＤ（２^ｇｂ・Ａ）ＭＯＤ（Ｎ）演算を適用する（ステップＳ３５）。次に、古典メモリ３０から変数ｇｂを読み込んだ量子計算制御部６０の制御のもと、ＳＷＡＰ演算部１１２が、量子ビットＱＤ_２と量子ビットＱＵ_ｇｂに対し、ＳＷＡＰ演算を適用する（ステップＳ３６）。その後、量子計算制御部６０が、古典メモリ３０に格納された変数ｇｂがｊ−１であるか否かを判断する（ステップＳ３７）。ここで、ｇｂ＝ｊ−１でなければ、量子計算制御部６０が、ｇｂ＋１を新たな変数ｇｂとして古典メモリ３０に格納し、処理をステップＳ３３に戻し、ｇｂ＝ｊ−１であれば、Ｍ（Ａ）ＭＯＤ（Ｎ）演算を終了する。

［ＡＤＤ（Ａ）ＭＯＤ（Ｎ）演算の詳細］
次に、ステップＳ３１，Ｓ３５で触れたＡＤＤ（Ａ）ＭＯＤ（Ｎ）演算, ＡＤＤ（２^ｇｂ・Ａ）ＭＯＤ（Ｎ）演算の詳細を説明する。なお、以下では、ＡをパラメータとしたＡＤＤ（Ａ）ＭＯＤ（Ｎ）演算を例にとって説明するが、このＡを２^ｇｂ・Ａに置換すればＡＤＤ（２^ｇｂ・Ａ）ＭＯＤ（Ｎ）演算となる。
図７は、このＡＤＤ（Ａ）ＭＯＤ（Ｎ）演算の詳細を説明するためのフローチャートである。また、図１５は、ｊ＝５の場合におけるＡＤＤ（Ａ）ＭＯＤ（Ｎ）演算を例示した量子回路である。

図１５に例示するように、ＡＤＤ（Ａ）ＭＯＤ（Ｎ）演算を示す量子回路は、ｄ_１，ｄ_２∈｛０，１｝とｕ_１，…，ｕ_ｊ−１∈｛０，１｝とＢと０とをそれぞれ示す量子状態の量子ビットＱＤ_１，ＱＤ_２，ＱＵ_１〜ＱＵ_ｊ−１，ＱＢ_０〜ＱＢ_ｊ−１，ＱＺを入力とし、ｄ_１＝ｄ_２＝１であれば、ｄ_１，ｄ_２とｕ_１，…，ｕ_ｊ−１とＡ＋Ｂ ｍｏｄ Ｎと０とをそれぞれ示す量子状態の量子ビットＱＤ_１，ＱＤ_２，ＱＵ_１〜ＱＵ_ｊ−１，ＱＢ_０〜ＱＢ_ｊ−１，ＱＺを出力し、ｄ_１＝ｄ_２＝１でなければ、入力の量子状態を維持する。ただし、Ａ＋Ｂ ｍｏｄ Ｎ＝（Ａ＋Ｂ ｍｏｄ Ｎ）_ｊ−１…（Ａ＋Ｂ ｍｏｄ Ｎ）_０であり、_{ＱＢｈ（ｈ∈｛０，…，ｊ−１｝）が}（Ａ＋Ｂ ｍｏｄ Ｎ）_{ｈに対応する。以下、この}ＡＤＤ（Ａ）ＭＯＤ（Ｎ）演算の詳細を説明する。

まず、減算部４０が古典メモリ３０から読み込んだＡとＮとからＮ−Ａを算出し、これを量子計算制御部６０に送る（ステップＳ４１）。このＮ−Ａを用いた量子計算制御部６０の制御のもと、ＣＯＭＰＡＲＩＳＯＮ演算部１２１（図２（ｃ））が、量子ビットＱＤ_１，ＱＤ_２を制御ビットとして、量子ビットＱＤ_１，ＱＤ_２がそれぞれ示す量子状態がともに１である場合にのみ、量子ビットＱＵ_１〜ＱＵ_ｊ−１，ＱＢ_０〜ＱＢ_ｊ−１，ＱＺに対し、ＣＯＭＰＡＲＩＳＯＮ（Ｎ−Ａ）演算を適用する（ステップＳ４２）。なお、詳細は後述するが、このＣＯＭＰＡＲＩＳＯＮ（Ｎ−Ａ）演算は、Ｎ−Ａ＞Ｂの場合にのみ量子ビットＱＺの量子状態を反転（０の場合には１にし、１の場合には０に）させる演算である。次に、ＱＦＴ演算部１２２が、量子ビットＱＢ_０〜ＱＢ_ｊ−１に対し、ＱＦＴ（量子フーリエ変換）演算（図３９）を適用する（ステップＳ４３）。

次に、古典メモリ３０からＡを読み込んだ量子計算制御部６０の制御のもと、φＡＤＤ演算部１２４が、量子ビットＱＤ_１，ＱＤ_２，ＱＺを制御ビットとして、量子ビットＱＤ_１，ＱＤ_２，ＱＺがそれぞれ示す量子状態が全て１である場合にのみ、量子ビットＱＢ_０〜ＱＢ_ｊ−１に対するφＡＤＤ（Ａ）演算を適用する（ステップＳ４４）。なお、φＡＤＤ（Ａ）演算は、図４２及び４３に示した通りである。すなわち、ステップＳ４４では、量子ビットＱＤ_１，ＱＤ_２，ＱＺを制御ビットとし、量子ビットＱＤ_１，ＱＤ_２，ＱＺがそれぞれ示す量子状態が全て１である場合にのみ、φＡＤＤ演算部１２４が、１を示す量子状態の量子ビットＱＢ_ｋ（ｋ∈｛ｊ−１，…，０｝）のみに対し、

（ただし、量子ビットＱＢ_ｋの量子状態を｜ＱＢ_ｋ〉とし、ｅをネピア数とし、ｉを虚数単位とする）の演算を施す。
次に、ＮＯＴ演算部１２６が、量子ビットＱＺに対してＮＯＴ演算を適用し（ステップＳ４５）、φＡＤＤ^−１演算部１２５が、量子ビットＱＤ_１，ＱＤ_２，ＱＺを制御ビットとして、量子ビットＱＤ_１，ＱＤ_２，ＱＺがそれぞれ示す量子状態が全て１である場合にのみ、量子ビットＱＢ_０〜ＱＢ_ｊ−１に対し、φＡＤＤ（Ｎ−Ａ）^−１演算を適用する（ステップＳ４６）。なお、φＡＤＤ（Ｎ−Ａ）^−１演算とはφＡＤＤ（Ｎ−Ａ）演算の逆演算を意味する。すなわち、ステップＳ４６では、量子ビットＱＤ_１，ＱＤ_２，ＱＺを制御ビットとし、量子ビットＱＤ_１，ＱＤ_２，ＱＺがそれぞれ示す量子状態が全て１である場合にのみ、φＡＤＤ^−１演算部１２５が、１を示す量子状態の量子ビットＱＢ_ｋのみに対し、

（ただし、Ｎ−Ａ＝（ｎ−ａ）_ｊ−１…（ｎ−ａ）_０とする）の演算を施す。
次に、ＮＯＴ演算部１２６が、量子ビットＱＺに対してＮＯＴ演算を適用し（ステップＳ４７）、ＱＦＴ^−１演算部１２３が、量子ビットＱＢ_０〜ＱＢ_ｊ−１に対し、ＱＦＴ演算の逆演算であるＱＦＴ^−１演算を適用する（ステップＳ４８）。次に、古典メモリ３０からＡを読み込んだ量子計算制御部６０の制御のもと、ＣＯＭＰＡＲＩＳＯＮ演算部１２１が、量子ビットＱＤ_１，ＱＤ_２を制御ビットとして、量子ビットＱＤ_１，ＱＤ_２がそれぞれ示す量子状態がともに１である場合にのみ、量子ビットＱＵ_１〜ＱＵ_ｊ−１，ＱＢ_０〜ＱＢ_ｊ−１，ＱＺに対し、ＣＯＭＰＡＲＩＳＯＮ（Ａ）演算を適用する（ステップＳ４９）。なお、ＣＯＭＰＡＲＩＳＯＮ（Ａ）の詳細については後述する。そして、Ｔｏｆｆｏｌｉ演算部１２７が、量子ビットＱＤ_１，ＱＤ_２を制御ビットとし、量子ビットＱＺを目標ビットとしたＴｏｆｆｏｌｉ演算を適用する（ステップＳ５０）。

［ＣＯＭＰＡＲＩＳＯＮ（Ａ）演算の詳細］
次に、ステップＳ４２，Ｓ４９で触れたＣＯＭＰＡＲＩＳＯＮ（Ｎ−Ａ）演算, ＣＯＭＰＡＲＩＳＯＮ（Ａ）演算の詳細を説明する。なお、以下では、ＡをパラメータとしたＣＯＭＰＡＲＩＳＯＮ（Ａ）演算を例にとって説明するが、このＡをＮ−Ａに置換すればＣＯＭＰＡＲＩＳＯＮ（Ｎ−Ａ）演算となる。
図８は、このＣＯＭＰＡＲＩＳＯＮ（Ａ）演算の詳細を説明するためのフローチャートである。また、図１６は、ｊ＝５の場合におけるＣＯＭＰＡＲＩＳＯＮ（Ａ）演算を例示した量子回路である。

図１６に例示するように、ＣＯＭＰＡＲＩＳＯＮ（Ａ）演算を示す量子回路は、Ｂ＝ｂ_ｊ−１…ｂ_０とｕ_１，…，ｕ_ｊ−１とｚとをそれぞれ示す量子ビットＱＢ_０〜ＱＢ_ｊ−１，ＱＵ_１〜ＱＵ_ｊ−１，ＱＺに対し、Ｂ＝ｂ_ｊ−１…ｂ_０とｕ_１，…，ｕ_ｊ−１とをそれぞれ示す量子状態の量子ビットＱＢ_０〜ＱＢ_ｊ−１，ＱＵ_１〜ＱＵ_ｊ−１と、ｚ（＋）αを示す量子状態の量子ビットＱＺとを出力する。なお、（＋）は排他的論理和（和のｍｏｄ ２を採った値）を示す。また、αは、Ａ＞Ｂの場合にα＝１となり、Ａ≦Ｂの場合にα＝０となる値である。すなわち、ＣＯＭＰＡＲＩＳＯＮ（Ａ）演算は、Ａ＞Ｂの場合にのみ、量子ビットＱＺの量子状態を反転させる演算である。以下、このＣＯＭＰＡＲＩＳＯＮ（Ａ）演算の詳細を説明する。

まず、古典メモリ３０からＡを読み込んだ量子計算制御部６０の制御のもと、ＨＩＢＩＴ演算部１３１（図３（ａ））が、量子ビットＱＵ_１〜ＱＵ_ｊ−１，ＱＢ_０〜ＱＢ_ｊ−１，ＱＺに対し、ＨＩＧＨＢＩＴ（Ａ）演算を適用する（ステップＳ５１）。なお、ＨＩＧＨＢＩＴ（Ａ）演算の詳細については後述する。次に、ＮＯＴ演算部１３２が、量子ビットＱＺに対し、ＮＯＴ演算を適用する（ステップＳ５２）。次に、古典メモリ３０からＡを読み込んだ量子計算制御部６０の制御のもと、古典制御ＮＯＴ演算部１３３が、Ａの桁ａ_ｈ（ｈ∈｛ｊ−１，…，０｝）が１となるｈに対応する量子ビットＱＢ_ｈのみにＮＯＴ演算を適用する（ステップＳ５３）。なお、各図においてＮＯＴ演算等の演算子を四角で囲み、その上部に符号を付したものは、この符号の値が１である場合にのみ、その四角で囲まれた演算を実行する演算子を意味する。

その後、ＮＯＴ演算部１３２が、量子ビットＱＢ_０〜ＱＢ_ｊ−１に対し、ＮＯＴ演算を適用し（ステップＳ５４）、Ｔｏｆｆｏｌｉ演算部１３４が、量子ビットＱＢ_０〜ＱＢ_ｊ−１を制御ビットとし、量子ビットＱＺを目標ビットとしたＴｏｆｆｏｌｉ演算を適用する（ステップＳ５５）。図１７にｊ＝５の場合のＴｏｆｆｏｌｉ演算を示す。さらにその後、ＮＯＴ演算部１３２が、量子ビットＱＢ_０〜ＱＢ_ｊ−１に対し、ＮＯＴ演算を適用する（ステップＳ５６）。そして、古典制御ＮＯＴ演算部１３３が、Ａの桁ａ_ｈ（ｈ∈｛ｊ−１，…，０｝）が１となるｈに対応する量子ビットＱＢ_ｈのみにＮＯＴ演算を適用する（ステップＳ５７）。

［ＨＩＧＨＢＩＴ（Ａ）演算の詳細］
次に、ステップＳ５１で触れたＨＩＧＨＢＩＴ（Ａ）演算の詳細を説明する。
図９及び１０は、このＨＩＧＨＢＩＴ（Ａ）演算の詳細を説明するためのフローチャートである。また、図１８は、ｊ＝５の場合におけるＨＩＧＨＢＩＴ（Ａ）演算を例示した量子回路である。
図１８に例示するように、ＨＩＧＨＢＩＴ（Ａ）演算を示す量子回路は、Ｂ＝ｂ_ｊ−１…ｂ_０とｕ_１，…，ｕ_ｊ−１とｚとをそれぞれ示す量子ビットＱＢ_０〜ＱＢ_ｊ−１，ＱＵ_１〜ＱＵ_ｊ−１，ＱＺに対し、Ｂ＝ｂ_ｊ−１…ｂ_０とｕ_１，…，ｕ_ｊ−１とをそれぞれ示す量子状態の量子ビットＱＢ_０〜ＱＢ_ｊ−１，ＱＵ_１〜ＱＵ_ｊ−１と、ｚ（＋）βを示す量子状態の量子ビットＱＺとを出力する。なお、βはＡ＋Ｂの最上位ビットの値を意味する。以下、ＨＩＧＨＢＩＴ（Ａ）演算の詳細を説明する。

まず、制御ＮＯＴ演算部１４１（図３（ｂ））が、量子ビットＱＵ_ｊ−１を制御ビットとし、量子ビットＱＺを目標ビットとしたＣＮＯＴ演算を適用する（ステップＳ６１）。次に、量子計算制御部６０が変数ｇｃにｊ−１を代入し、これを古典メモリ３０に格納する（ステップＳ６２）。
次に、古典メモリ３０からＡと変数ｇｃとを読み込んだ量子計算制御部６０の制御のもと、Ｅ演算部１４２が、量子ビットＱＵ_ｇｃ，ＱＵ_ｇｃ−１，ＱＢ_ｇｃに対し、Ｅ（ａ_ｇｃ）演算を適用する（ステップＳ６３）。

図１９は、このＥ（ａ_ｇｃ）演算を示した量子回路である。図１９に示すように、Ｅ（ａ_ｇｃ）演算は、ｐ，ｒ，ｓ∈｛０，１｝をそれぞれ示す量子状態の３つの量子ビットＱＵ_ｇｃ−１，ＱＢ_ｇｃ，ＱＵ_ｇｃを入力とする。そして、Ｅ演算部１４２は、まず、ａ_ｇｃ＝１の場合にのみ量子ビットＱＢ_ｇｃにＮＯＴ演算を適用する。次に、Ｅ演算部１４２は、量子ビットＱＵ_ｇｃ−１，ＱＢ_ｇｃを制御ビットとし、量子ビットＱＵ_ｇｃを目標ビットとしたＴｏｆｆｏｌｉ演算を適用し、さらに、ａ_ｇｃ＝１の場合にのみ量子ビットＱＢ_ｇｃにＮＯＴ演算を適用する。これらの操作により、３つの量子ビットＱＵ_ｇｃ−１，ＱＢ_ｇｃ，ＱＵ_ｇｃの量子状態が、それぞれｐ，ｒ，ｓ（＋）（ａ_ｇｃ（＋）ｒ）・ｐを示すものとされる。以上がＥ（ａ_ｇｃ）演算である。

次に、量子計算制御部６０が、古典メモリ３０に格納された変数ｇｃが２であるか否かを判断する（ステップＳ６４）。ここで、ｇｃ＝２でなければ、量子計算制御部６０は、ｇｃ−１を新たなｇｃとして古典メモリ３０に格納した後（ステップＳ６５）、処理をステップＳ６３に戻す。一方、ｇｃ＝２であれば、量子計算制御部６０は、古典メモリからＡの要素ａ_１を読み込み、ａ_１＝１の場合にのみ、制御ＮＯＴ演算部１４１に、量子ビットＱＢ_１を制御ビットとし、量子ビットＱＵ_１を目標ビットとした制御ＮＯＴ演算を適用させ、ＮＯＴ演算部１４５に、量子ビットＱＢ_１へのＮＯＴ演算を適用させる（ステップＳ６６）。次に、量子計算制御部６０は、古典メモリからＡの要素ａ_０を読み込み、ａ_０＝１の場合にのみ、Ｔｏｆｆｏｌｉ演算部１４４に、量子ビットＱＢ_０，ＱＢ_１を制御ビットとし、量子ビットＱＵ_１を目標ビットとしたＴｏｆｆｏｌｉ演算を適用させる（ステップＳ６７）。

次に、古典メモリ３０から変数ｇｃとＡの要素ａ_ｇｃとを読み込んだ量子計算制御部６０の制御のもと、Ｆ演算部１４３が、量子ビットＱＵ_ｇｃ，ＱＵ_ｇｃ−１，ＱＢ_ｇｃに対し、Ｆ（ａ_ｇｃ）演算を適用する（ステップＳ６８）。
図２０は、このＦ（ａ_ｇｃ）演算を示した量子回路である。図２０に示すように、Ｆ（ａ_ｇｃ）演算は、ｐ，ｒ，ｓ∈｛０，１｝をそれぞれ示す量子状態の３つの量子ビットＱＵ_ｇｃ−１，ＱＢ_ｇｃ，ＱＵ_ｇｃを入力とする。そして、Ｆ演算部１４３は、まず、ａ_ｇｃ＝１の場合にのみ量子ビットＱＢ_ｇｃを制御ビットとし、量子ビットＱＵ_ｇｃを目標ビットとした制御ＮＯＴ演算を適用し、さらに量子ビットＱＵ_ｇｃにＮＯＴ演算を適用する。次に、Ｆ演算部１４３は、量子ビットＱＵ_ｇｃ−１，ＱＢ_ｇｃを制御ビットとし、量子ビットＱＵ_ｇｃを目標ビットとしたＴｏｆｆｏｌｉ演算を適用する。これらの操作により、３つの量子ビットＱＵ_ｇｃ−１，ＱＢ_ｇｃ，ＱＵ_ｇｃの量子状態が、それぞれｐ，ａ_ｇｃ（＋）ｒ，ｓ（＋）ｐ・ａ_ｇｃ（＋）ａ_ｇｃ・ｒ（＋）ｒ・ｐを示すものとなる。以上がＦ（ａ_ｇｃ）演算である。

次に、量子計算制御部６０が、古典メモリ３０に格納された変数ｇｃがｊ−１であるか否かを判断する（ステップＳ６９）。ここで、ｇｃ＝ｊ−１でなければ、量子計算制御部６０は、ｇｃ＋１を新たなｇｃとして古典メモリ３０に格納した後（ステップＳ７０）、処理をステップＳ６８に戻す。一方、ｇｃ＝ｊ−１であれば、制御ＮＯＴ演算部１４１が、量子ビットＱＵ_ｊ−１を制御ビットとし、量子ビットＱＺを目標ビットとしたＣＮＯＴ演算を適用する（ステップＳ７１）。次に、古典メモリ３０から変数ｇｃとＡの要素ａ_ｇｃとを読み込んだ量子計算制御部６０の制御のもと、Ｆ演算部１４３が、量子ビットＱＵ_ｇｃ，ＱＵ_ｇｃ−１，ＱＢ_ｇｃに対し、Ｆ（ａ_ｇｃ）演算の逆演算であるＦ（ａ_ｇｃ）^−１演算を適用する（ステップＳ７２）。

次に、量子計算制御部６０が、古典メモリ３０に格納された変数ｇｃが２であるか否かを判断する（ステップＳ７３）。ここで、ｇｃ＝２でなければ、量子計算制御部６０は、ｇｃ−１を新たなｇｃとして古典メモリ３０に格納した後（ステップＳ７４）、処理をステップＳ７２に戻す。一方、ｇｃ＝２であれば、量子計算制御部６０は、古典メモリからＡの要素ａ_０を読み込み、ａ_０＝１の場合にのみ、Ｔｏｆｆｏｌｉ演算部１４４に、量子ビットＱＢ_０，ＱＢ_１を制御ビットとし、量子ビットＱＵ_１を目標ビットとしたＴｏｆｆｏｌｉ演算を適用させる（ステップＳ７５）。

次に、量子計算制御部６０は、古典メモリからＡの要素ａ_１を読み込み、ａ_１＝１の場合にのみ、ＮＯＴ演算部１４５に、量子ビットＱＢ_１へのＮＯＴ演算を適用させ、制御ＮＯＴ演算部１４１に、量子ビットＱＢ_１を制御ビットとし、量子ビットＱＵ_１を目標ビットとした制御ＮＯＴ演算を適用させる（ステップＳ７６）。
次に、古典メモリ３０からＡと変数ｇｃとを読み込んだ量子計算制御部６０の制御のもと、Ｅ演算部１４２が、量子ビットＱＵ_ｇｃ，ＱＵ_ｇｃ−１，ＱＢ_ｇｃに対し、Ｅ（ａ_ｇｃ）演算を適用する（ステップＳ７７）。次に、量子計算制御部６０が、古典メモリ３０に格納された変数ｇｃがｊ−１であるか否かを判断する（ステップＳ７８）。ここで、ｇｃ＝ｊ−１でなければ、量子計算制御部６０は、ｇｃ＋１を新たなｇｃとして古典メモリ３０に格納した後（ステップＳ７９）、処理をステップＳ７７に戻す。一方、ｇｃ＝ｊ−１であれば、ＨＩＧＨＢＩＴ（Ａ）演算を終了させる。

〔第２の実施の形態〕
本形態は、第１の実施の形態の変形例である。第１の実施の形態では、Ａ＝ａ_ｊ−１…ａ_０を古典情報として取り扱っていたが、第２の実施の形態では、Ａ＝ａ_ｊ−１…ａ_０を量子情報として取り扱う。なお、以下では、第１の実施の形態との相違点を中心に説明し、第１の実施の形態と共通する事項については説明を省略する。
＜構成＞
図２１は、本形態における量子計算装置２００の機能構成を例示したブロック図である。

第１の実施の形態の量子計算装置１と第２の実施の形態の量子計算装置２００との構成上の相違点は、第１の実施の形態で古典情報として取り扱っていたＡ＝ａ_ｊ−１…ａ_０の各桁ａ_０，…，ａ_ｊ−１の値を示す量子状態とする量子ビットＱＡ_０，…ＱＡ_ｊ−１を量子ビット１０に追加した量子ビット２１０を用いる点、量子計算部２７０の初期量子状態生成部２７１やＣＶ演算部２７２が、この量子ビットＱＡ_０，…ＱＡ_ｊ−１の量子情報を用いて各処理を実行する点である。
図２２（ａ）は、本形態のＣＶ演算部２７２が有するＣＯＮＰＡＲＩＳＯＮ演算部３２１の詳細構成を例示した図である。この図に示すようにＣＯＮＰＡＲＩＳＯＮ演算部３２１は、ＨＩＧＨＢＩＴ演算部３３１、ＮＯＴ演算部３３２、制御ＮＯＴ演算部３３３及びＴｏｆｆｏｌｉ演算部３３４を有している。図２２（ｂ）は、ＨＩＧＨＢＩＴ演算部３３１の詳細構成を例示した図である。この図に示すようにＨＩＧＨＢＩＴ演算部３３１は、制御ＮＯＴ演算部３４１、Ｅ演算部３４２、Ｆ演算部３４３、Ｔｏｆｆｏｌｉ演算部３４４、ＮＯＴ演算部３４５及びＦ^−１演算部３４３を有している。なお、その他の詳細構成については第１の実施の形態と同様であるため説明を省略する。

＜処理＞
以下では第１の実施の形態との相違点を中心に説明する。
［初期量子状態生成］
第１の実施の形態では、初期量子状態生成部７１が、量子ビットＱＤ_１，ＱＤ_２，ＱＵ_１〜ＱＵ_ｊ−１，ＱＢ_０〜ＱＢ_ｊ−１，ＱＺの初期量子状態を生成していたが（ステップＳ２）、本形態の初期量子状態生成部２７１（図２１）は、さらにＱＡ_０〜ＱＡ_ｊ−１の初期量子状態も生成する。具体的には、古典メモリ３０からＡ＝ａ_ｊ−１…ａ_０を読み込んだ量子計算制御部６０の制御のもと、初期量子状態生成部２７１が、量子ビットＱＡ_０，…ＱＡ_ｊ−１の量子状態を、それぞれＡ＝ａ_ｊ−１…ａ_０の各桁ａ_０，…，ａ_ｊ−１の値を示す量子状態とする。

［ＣＶ演算］
第１の実施の形態では、Ａ＝ａ_ｊ−１…ａ_０を古典情報としてＣＶ演算を行っていたが、本形態では、量子ビットＱＡ_０，…ＱＡ_ｊ−１を用い、Ａ＝ａ_ｊ−１…ａ_０を量子情報としてＣＶ演算を行う。以下では、ＣＯＮＰＡＲＩＳＯＮ演算とＨＩＧＨＢＩＴ演算のみを説明する。その他の演算については、量子ビットＱＡ_０，…ＱＡ_ｊ−１を用いたＣＯＮＰＡＲＩＳＯＮ演算とＨＩＧＨＢＩＴ演算の結果を用いる以外は、第１の実施の形態と同様である。

［ＣＯＮＰＡＲＩＳＯＮ演算の詳細］
図２３は、本形態のＣＯＮＰＡＲＩＳＯＮ演算の詳細を説明するためのフローチャートである。また、図２６は、ｊ＝５の場合における本形態のＣＯＭＰＡＲＩＳＯＮ演算を例示した量子回路である。
図２６に例示するように、本形態のＣＯＭＰＡＲＩＳＯＮ演算を示す量子回路は、Ａ＝ａ_ｊ−１…ａ_０とＢ＝ｂ_ｊ−１…ｂ_０とｕ_１，…，ｕ_ｊ−１とｚとをそれぞれ示す量子ビットＱＡ_０〜ＱＡ_ｊ−１，ＱＢ_０〜ＱＢ_ｊ−１，ＱＵ_１〜ＱＵ_ｊ−１，ＱＺに対し、Ａ＝ａ_ｊ−１…ａ_０とＢ＝ｂ_ｊ−１…ｂ_０とｕ_１，…，ｕ_ｊ−１とをそれぞれ示す量子状態の量子ビットＱＡ_０〜ＱＡ_ｊ−１，ＱＢ_０〜ＱＢ_ｊ−１，ＱＵ_１〜ＱＵ_ｊ−１と、ｚ（＋）αを示す量子状態の量子ビットＱＺとを出力する。また、αは、Ａ＞Ｂの場合にα＝１となり、Ａ≦Ｂの場合にα＝０となる値である。すなわち、ＣＯＭＰＡＲＩＳＯＮ演算は、Ａ＞Ｂの場合にのみ、量子ビットＱＺの量子状態を反転させる演算である。以下、このＣＯＭＰＡＲＩＳＯＮ演算の詳細を説明する。

まず、ＮＯＴ演算部３３２（図２２（ａ））が、量子ビットＱＡ_０〜ＱＡ_ｊ−１に対してＮＯＴ演算を適用する（ステップＳ１０１）。次に、古典メモリ３０からＡを読み込んだ量子計算制御部６０の制御のもと、ＨＩＢＩＴ演算部３３１が、量子ビットＱＵ_１〜ＱＵ_ｊ−１，ＱＡ_０〜ＱＡ_ｊ−１，ＱＢ_０〜ＱＢ_ｊ−１，ＱＺに対し、ＨＩＧＨＢＩＴ演算を適用する（ステップＳ１０２）。なお、ＨＩＧＨＢＩＴ演算の詳細については後述する。次に、ＮＯＴ演算部３３２が、量子ビットＱＡ_０〜ＱＡ_ｊ−１，ＱＺに対してＮＯＴ演算を適用する（ステップＳ１０３）。次に、量子計算制御部６０の制御のもと、制御ＮＯＴ演算部３３３が、量子ビットＱＡ_０〜ＱＡ_ｊ−１を制御ビットとし、量子ビットＱＢ_０〜ＱＢ_ｊ−１を目標ビットとした制御ＮＯＴ演算を適用する（ステップＳ１０４）。その後、ＮＯＴ演算部３３２が、量子ビットＱＢ_０〜ＱＢ_ｊ−１に対し、ＮＯＴ演算を適用し（ステップＳ１０５）、Ｔｏｆｆｏｌｉ演算部３３４が、量子ビットＱＢ_０〜ＱＢ_ｊ−１を制御ビットとし、量子ビットＱＺを目標ビットとしたＴｏｆｆｏｌｉ演算を適用する（ステップＳ１０６）。さらにその後、ＮＯＴ演算部３３２が、量子ビットＱＢ_０〜ＱＢ_ｊ−１に対し、ＮＯＴ演算を適用する（ステップＳ１０７）。そして、量子計算制御部６０の制御のもと、制御ＮＯＴ演算部３３３が、量子ビットＱＡ_０〜ＱＡ_ｊ−１を制御ビットとし、量子ビットＱＢ_０〜ＱＢ_ｊ−１を目標ビットとした制御ＮＯＴ演算を適用する（ステップＳ１０８）。

［ＨＩＧＨＢＩＴ演算の詳細］
次に、ステップＳ１０２で触れたＨＩＧＨＢＩＴ演算の詳細を説明する。
図２４及び２５は、このＨＩＧＨＢＩＴ演算の詳細を説明するためのフローチャートである。また、図２７は、ｊ＝５の場合における、このＨＩＧＨＢＩＴ演算を例示した量子回路である。
図２７に例示するように、ＨＩＧＨＢＩＴ演算を示す量子回路は、Ａ＝ａ_ｊ−１…ａ_０とＢ＝ｂ_ｊ−１…ｂ_０とｕ_１，…，ｕ_ｊ−１とｚとをそれぞれ示す量子ビットＱＢ_０〜ＱＢ_ｊ−１，ＱＵ_１〜ＱＵ_ｊ−１，ＱＺに対し、Ｂ＝ｂ_ｊ−１…ｂ_０とｕ_１，…，ｕ_ｊ−１とをそれぞれ示す量子状態の量子ビットＱＡ_０〜ＱＡ_ｊ−１，ＱＢ_０〜ＱＢ_ｊ−１，ＱＵ_１〜ＱＵ_ｊ−１と、ｚ（＋）βを示す量子状態の量子ビットＱＺとを出力する。なお、βはＡ＋Ｂの最上位ビットの値を意味する。以下、ＨＩＧＨＢＩＴ演算の詳細を説明する。

まず、制御ＮＯＴ演算部３４１（図２２（ｂ））が、量子ビットＱＵ_ｊ−１を制御ビットとし、量子ビットＱＺを目標ビットとしたＣＮＯＴ演算を適用する（ステップＳ１１１）。次に、量子計算制御部６０が変数ｇｃにｊ−１を代入し、これを古典メモリ３０に格納する（ステップＳ１１２）。
次に、古典メモリ３０から変数ｇｃを読み込んだ量子計算制御部６０の制御のもと、Ｅ演算部１４２が、量子ビットＱＵ_ｇｃ，ＱＵ_ｇｃ−１，ＱＡ_ｇｃ，ＱＢ_ｇｃに対し、Ｅ演算を適用する（ステップＳ１１３）。

図２８は、このＥ演算を示した量子回路である。図２８に示すように、Ｅ（演算は、ｐ，ｑ，ｒ，ｓ∈｛０，１｝をそれぞれ示す量子状態の４つの量子ビットＱＵ_ｇｃ−１，ＱＡ_ｇｃ，ＱＢ_ｇｃ，ＱＵ_ｇｃを入力とする。そして、Ｅ演算部１４２は、まず、量子ビットＱＡ_ｇｃを制御ビットとし、量子ビットＱＢ_ｇｃを目標ビットとした制御ＮＯＴ演算を適用する。次に、Ｅ演算部１４２は、量子ビットＱＵ_ｇｃ−１，ＱＢ_ｇｃを制御ビットとし、量子ビットＱＵ_ｇｃを目標ビットとしたＴｏｆｆｏｌｉ演算を適用し、さらに、量子ビットＱＡ_ｇｃを制御ビットとし、量子ビットＱＢ_ｇｃを目標ビットとした制御ＮＯＴ演算を適用する。これらの操作により、４つの量子ビットＱＵ_ｇｃ−１，ＱＡ_ｇｃ，ＱＢ_ｇｃ，ＱＵ_ｇｃの量子状態が、それぞれｐ，ｑ,ｒ，ｓ（＋）（ｑ（＋）ｒ）・ｐを示すものとなる。以上がＥ演算である。

次に、量子計算制御部６０が、古典メモリ３０に格納された変数ｇｃが２であるか否かを判断する（ステップＳ１１４）。ここで、ｇｃ＝２でなければ、量子計算制御部６０は、ｇｃ−１を新たなｇｃとして古典メモリ３０に格納した後（ステップＳ１１５）、処理をステップＳ１１３に戻す。一方、ｇｃ＝２であれば、量子計算制御部６０の制御のもと、Ｔｏｆｆｏｌｉ演算部３４４は、量子ビットＱＡ_１，ＱＢ_１を制御ビットとし、量子ビットＱＵ_１を目標ビットとしたＴｏｆｆｏｌｉ演算を適用する（ステップＳ１１６）。次に、制御ＮＯＴ演算部３４１は、
量子ビットＱＡ_１を制御ビットとし、量子ビットＱＢ_１を目標ビットとした制御ＮＯＴ演算を適用する（ステップＳ１１７）。さらに、Ｔｏｆｆｏｌｉ演算部３４４は、量子ビットＱＡ_０，ＱＢ_０，ＱＢ_１を制御ビットとし、量子ビットＱＵ_１を目標ビットとしたＴｏｆｆｏｌｉ演算を適用する（ステップＳ１１８）。図３０は、このようなＴｏｆｆｏｌｉ演算を示した量子回路である。なお図３０では、それぞれの量子状態が、ｐ，ｑ，ｒ，ｓである量子ビットＱＡ_０，ＱＢ_０，ＱＢ_１，ＱＵ_１を入力とした例を示している。

次に、Ｆ演算部３４３が、量子ビットＱＵ_ｇｃ，ＱＵ_ｇｃ−１ ，ＱＡ_ｇｃ，ＱＢ_ｇｃに対し、Ｆ演算を適用する（ステップＳ１１９）。
図２９は、このＦ演算を示した量子回路である。図２９に示すように、Ｆ演算は、ｐ，ｑ，ｒ，ｓ∈｛０，１｝をそれぞれ示す量子状態の４つの量子ビットＱＵ_ｇｃ−１，ＱＡ_ｇｃ，ＱＢ_ｇｃ，ＱＵ_ｇｃを入力とする。そして、Ｆ演算部３４３は、まず、量子ビットＱＡ_ｇｃ，ＱＢ_ｇｃを制御ビットとし、量子ビットＱＵ_ｇｃを目標ビットとしたＴｏｆｆｏｌｉ演算を適用し、さらにＱＡ_ｇｃを制御ビットとし、量子ビットＱＢ_ｇｃを目標ビットとした制御ＮＯＴ演算を適用する。次に、Ｅ演算部１４２は、量子ビットＱＵ_ｇｃ−１，ＱＢ_ｇｃを制御ビットとし、量子ビットＱＵ_ｇｃを目標ビットとしたＴｏｆｆｏｌｉ演算を適用する。これらの演算により、４つの量子ビットＱＵ_ｇｃ−１，ＱＡ_ｇｃ，ＱＢ_ｇｃ，ＱＵ_ｇｃの量子状態が、それぞれｐ，ｑ，ｑ（＋）ｒ，ｓ（＋）ｐ・ｑ（＋）ｑ・ｒ（＋）ｒ・ｐを示すものとなる。以上がＦ演算である。

次に、量子計算制御部６０が、古典メモリ３０に格納された変数ｇｃがｊ−１であるか否かを判断する（ステップＳ１２０）。ここで、ｇｃ＝ｊ−１でなければ、量子計算制御部６０は、ｇｃ＋１を新たなｇｃとして古典メモリ３０に格納した後（ステップＳ１２１）、処理をステップＳ１１９に戻す。一方、ｇｃ＝ｊ−１であれば、制御ＮＯＴ演算部１４１が、量子ビットＱＵ_ｊ−１を制御ビットとし、量子ビットＱＺを目標ビットとしたＣＮＯＴ演算を適用する（ステップＳ１２２）。
次に、古典メモリ３０から変数ｇｃとＡの要素ａ_ｇｃとを読み込んだ量子計算制御部６０の制御のもと、Ｆ^−１演算部３４６が、量子ビットＱＵ_ｇｃ，ＱＵ_ｇｃ−１，ＱＡ_ｇｃ，ＱＢ_ｇｃに対し、Ｆ演算の逆演算であるＦ^−１演算を適用する（ステップＳ１２３）。

次に、量子計算制御部６０が、古典メモリ３０に格納された変数ｇｃが２であるか否かを判断する（ステップＳ１２４）。ここで、ｇｃ＝２でなければ、量子計算制御部６０は、ｇｃ−１を新たなｇｃとして古典メモリ３０に格納した後（ステップＳ１２５）、処理をステップＳ１２３に戻す。一方、ｇｃ＝２であれば、Ｔｏｆｆｏｌｉ演算部３４４は、量子ビットＱＡ_０，ＱＢ_０，ＱＢ_１を制御ビットとし、量子ビットＱＵ_１を目標ビットとしたＴｏｆｆｏｌｉ演算を適用する（ステップＳ１２６）。次に、制御ＮＯＴ演算部３４１は、
量子ビットＱＡ_１を制御ビットとし、量子ビットＱＢ_１を目標ビットとした制御ＮＯＴ演算を適用する（ステップＳ１２７）。さらに、
Ｔｏｆｆｏｌｉ演算部３４４は、量子ビットＱＡ_１，ＱＢ_１を制御ビットとし、量子ビットＱＵ_１を目標ビットとしたＴｏｆｆｏｌｉ演算を適用する（ステップＳ１２８）。

次に、古典メモリ３０から変数ｇｃを読み込んだ量子計算制御部６０の制御のもと、Ｅ演算部１４２が、量子ビットＱＵ_ｇｃ，ＱＵ_ｇｃ−１，ＱＡ_ｇｃ，ＱＢ_ｇｃに対し、Ｅ演算を適用する（ステップＳ１２９）。次に、量子計算制御部６０が、古典メモリ３０に格納された変数ｇｃがｊ−１であるか否かを判断する（ステップＳ１３０）。ここで、ｇｃ＝ｊ−１でなければ、量子計算制御部６０は、ｇｃ＋１を新たなｇｃとして古典メモリ３０に格納した後（ステップＳ１３１）、処理をステップＳ１２９に戻す。一方、ｇｃ＝ｊ−１であれば、ＨＩＧＨＢＩＴ演算を終了させる。

〔ハードウェア構成〕
次に各実施の形態の量子計算装置１，２００のハードウェア構成を例示する。
本形態の量子演算装置１は、量子コンピュータと古典コンユータとの組合せ、或いは量子コンピュータ単体で実現できる。量子コンピュータの実現する物理系としては、例えば、イオントラップを用いる方法（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）ＲＡＭ等の読書き可能な半導体メモリである。また、古典メモリ３０の代わりに上述の量子メモリを用いてもよい。
なお、本発明は上述の実施の形態に限定されるものではなく、その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。

本発明の利用分野としては、例えば、ＲＳＡ等の因数分解の困難性に安全性の根拠をおく暗号方式の安全性評価装置等を例示できる。

図１は、第１の実施の形態における量子計算装置の構成を例示したブロック図である。 図２（ａ）は、第１の実施の形態におけるＣＶ演算部の詳細構成を例示した図である。図２（ｂ）は、Ｍ ＭＯＤ演算部の詳細構成を例示した図である。図２（ｃ）は、ＡＤＤ ＭＯＤ演算部の詳細構成を例示した図である。 図３（ａ）は、第１の実施の形態におけるＣＯＮＰＡＲＩＳＯＮ演算部の詳細構成を例示した図である。図３（ｂ）は、ＨＩＧＨＢＩＴ演算部の詳細構成を例示した図である。 図４は、第１の実施の形態の量子計算装置の処理の全体を説明するためのフローチャートである。 図５は、ＣＶ（Ａ）演算の詳細を説明するためのフローチャートである。 図６は、このＭ（Ａ）ＭＯＤ（Ｎ）演算の詳細を説明するためのフローチャートである。 図７は、ＡＤＤ（Ａ）ＭＯＤ（Ｎ）演算の詳細を説明するためのフローチャートである。 図８は、ＣＯＭＰＡＲＩＳＯＮ（Ａ）演算の詳細を説明するためのフローチャートである。 図９は、ＨＩＧＨＢＩＴ（Ａ）演算の詳細を説明するためのフローチャートである。 図１０は、ＨＩＧＨＢＩＴ（Ａ）演算の詳細を説明するためのフローチャートである。 図１１は、第１の実施の形態の量子計算装置の処理の全体を例示した量子回路である。 図１２は、ｊ＝５の場合におけるＣＶ（Ａ）演算を例示した量子回路である。 図１３は、ｊ＝５の場合におけるＭ（Ａ）ＭＯＤ（Ｎ）演算を例示した量子回路である。 図１４は、ＳＷＡＰ演算を示した量子回路である。 図１５は、ｊ＝５の場合におけるＡＤＤ（Ａ）ＭＯＤ（Ｎ）演算を例示した量子回路である。 図１６は、ｊ＝５の場合におけるＣＯＭＰＡＲＩＳＯＮ（Ａ）演算を例示した量子回路である。 図１７は、ｊ＝５の場合のＴｏｆｆｏｌｉ演算を示した量子回路である。 図１８は、ｊ＝５の場合におけるＨＩＧＨＢＩＴ（Ａ）演算を例示した量子回路である。 図１９は、Ｅ（ａ_ｇｃ）演算を示した量子回路である。 図２０は、Ｆ（ａ_ｇｃ）演算を示した量子回路である。 図２１は、第２の実施の形態における量子計算装置の機能構成を例示したブロック図である。 図２２（ａ）は、第２の実施の形態のＣＶ演算部が有するＣＯＮＰＡＲＩＳＯＮ演算部の詳細構成を例示した図である。図２２（ｂ）は、ＨＩＧＨＢＩＴ演算部の詳細構成を例示した図である。 図２３は、第２の実施の形態のＣＯＮＰＡＲＩＳＯＮ演算の詳細を説明するためのフローチャートである。 図２４は、ＨＩＧＨＢＩＴ演算の詳細を説明するためのフローチャートである。 図２５は、ＨＩＧＨＢＩＴ演算の詳細を説明するためのフローチャートである。 図２６は、ｊ＝５の場合における、第２の実施の形態のＣＯＭＰＡＲＩＳＯＮ演算を例示した量子回路である。 図２７は、ｊ＝５の場合における、第２の実施の形態のＨＩＧＨＢＩＴ演算を例示した量子回路である。 図２８は、Ｅ演算を示した量子回路である。 図２９は、Ｆ演算を示した量子回路である。 図３０は、Ｔｏｆｆｏｌｉ演算を示す量子回路である。 図３１は、位数発見に有用な値を発見する量子回路の従来構成を示した図である。 図３２（ａ）は、図３１の演算子Ｈを示す量子回路であり、図３２（ｂ）は、図３１の演算子Ｘを示す量子回路である。 図３３は、図３１の演算子Ｒを示す量子回路である。 図３４は、図３１におけるＣＵ（Ａ）＝ＣＵ（Ａ・２^０）の演算の詳細を示した量子回路である。 図３５は、図３４のＣＳＷＡＰ演算を示す量子回路である。 図３６（ａ）は、ＮＯＴ演算を示す量子回路であり、図３６（ｂ）は、制御ＮＯＴ演算を示す量子回路である。 図３７は、Ｔｏｆｆｏｌｉ演算を示す量子回路である。 図３８は、図３４におけるＣＭＵＬＴ（Ａ）ＭＯＤ（Ｎ）の演算の詳細を示した量子回路である。 図３９は、図３８におけるＱＦＴの演算の詳細を示した量子回路である。 図４０は、図３９の演算子Ｋ∈｛２，…，６｝を示した量子回路である。 図４１は、図３８におけるφＡＤＤ（Ａ）ＭＯＤ（Ｎ）＝φＡＤＤ（２^０・Ａ）ＭＯＤ（Ｎ）の演算の詳細を示した量子回路である。 図４２は、図４１におけるφＡＤＤ（Ａ）演算の詳細を示した量子回路である。 図４３は、図４２における演算子σ_ｋ（ｋ∈｛１，…，５｝）を示した量子回路である。

符号の説明

１，２００ 量子計算装置

Claims (5)

1. ２進数ｊ桁のＮ＝ｎ_ｊ−１…ｎ_０と、２進数ｊ桁のＦ＝ｆ _ｊ−１…ｆ _０と、２進数ｊ桁のＢ＝ｂ _ｊ−１ …ｂ _０ とから、Ｆ＋Ｂ ｍｏｄ Ｎを算出する量子計算方法であって、
   （ａ）メモリに上記ＮとＦとを格納するステップと、
   （ｂ）減算部が、上記メモリから読み込んだＮとＦとからＮ−Ｆを算出するステップと、
   （ｃ）第１ＣＯＭＰＡＲＩＳＯＮ演算部が、上記減算部が算出したＮ−Ｆを用い、前記Ｂ＝ｂ_ｊ−１…ｂ_０の各桁をそれぞれ示す量子状態の量子ビットＱＢ_ｊ−１， … ，ＱＢ_０と、任意の量子状態の量子ビットＱＵ_ｊ−１，… ＱＵ_１，ＱＺと、に対し、前記Ｎ−ＦとＢとを比較する第１量子操作を行い、Ｎ−Ｆ＞Ｂの場合にのみ量子ビットＱＺの量子状態を反転させるステップと、
   （ｄ）ＱＦＴ演算部が、前記第１ＣＯＭＰＡＲＩＳＯＮ演算部が演算した結果の量子ビットＱＢ _ｊ−１ ，…，ＱＢ _０ にＱＦＴ（量子フーリエ変換）演算を適用するステップと、
   （ｅ）φＡＤＤ演算部が、前記第１ＣＯＭＰＡＲＩＳＯＮ演算部が演算した結果の量子ビットＱＺが１を示す量子状態のときのみ、前記ＱＦＴ演算部が演算した結果の前記量子ビットＱＢ _ｊ−１ ，…，ＱＢ _０ のうち１を示す量子状態の量子ビットＱＢ _ｋ （０≦ｋ≦ｊ−１）に対し、
   

   

   （ただし、量子ビットＱＢ _ｋ の量子状態を｜ＱＢ _ｋ 〉とし、ｅをネピア数とし、ｉを虚数単位とする）の演算を施すステップと、
   （ｆ）第１ＮＯＴ演算部が、前記第１ＣＯＭＰＡＲＩＳＯＮ演算部が演算した結果の量子ビットＱＺにＮＯＴ演算を施すステップと、
   （ｇ）φＡＤＤ ^−１ 演算部が、前記第１ＮＯＴ演算部が演算した結果の量子ビットＱＺが１を示す量子状態のときのみ、前記φＡＤＤ演算部が演算した結果の量子ビットＱＢ _ｊ−１ ，…，ＱＢ _０ のうち１を示す量子状態の量子ビットＱＢ _ｋ （０≦ｋ≦ｊ−１）に対し、
   

   

   （ただし、Ｎ−Ｆ＝（ｎ−ｆ） _ｊ−１ …（ｎ−ｆ） _０ とする）の演算を施すステップと、
   （ｈ）第２ＮＯＴ演算部が、前記第１ＮＯＴ演算部が演算した結果の量子ビットＱＺにＮＯＴ演算を施すステップと、
   （ｉ）ＱＦＴ ^−１ 演算部が、前記φＡＤＤ ^−１ 演算部が演算した結果の量子ビットＱＢ _ｊ−１ ，…，ＱＢ _０ にＱＦＴ演算の逆演算を適用するステップと、
   （ｊ）第２ＣＯＭＰＡＲＩＳＯＮ演算部が、前記ＦとＢと用い、前記ＱＦＴ ^−１ 演算部が演算した結果の量子ビットＱＢ _ｊ−１ ，… ，ＱＢ _０ と、前記第１ＣＯＭＰＡＲＩＳＯＮ演算部が演算した結果の量子ビットＱＵ _ｊ−１ ，…，ＱＵ _１ と前記第２ＮＯＴ演算部が演算した結果の量子ビットＱＺと、に対し、前記ＦとＢとを比較する第１量子操作を行い、Ｆ＞Ｂの場合にのみ前記第２ＮＯＴ演算部が演算した結果の量子ビットＱＺの量子状態を反転させる量子操作を行うステップと、を実行し、
   前記第２ＣＯＭＰＡＲＩＳＯＮ演算部が演算した結果の量子ビットＱＢ _０ ・・・ＱＢ _ｊ−１ を前記Ｆ＋Ｂ ｍｏｄ Ｎの各桁に対応する量子状態を表す量子ビットとして出力することを特徴とする量子計算方法。
2. 請求項１に記載のＦ＋Ｂ ｍｏｄ Ｎを算出する量子計算方法を用いて、前記２進数ｊ桁のＮ＝ｎ _ｊ−１ …ｎ _０ と、前記Ｎよりも小さい２進数ｊ桁のＡ＝ａ _ｊ−１ …ａ _０ とから、Ａ ^Ｒ ＝１ ｍｏｄ Ｎを満たす最小のＲの算出に有用な値Ｃ＝ｃ _２ｊ−１ ・・・ｃ _０ を計算する量子計算方法であって、
   初期量子状態生成部が、０と１と２ｊ個の０とをそれぞれ示す量子ビットＱＤ _１ ，ＱＤ _２ ，ＱＵ _１ ，・・・ＱＵ _ｊ−１ ，ＱＢ _０ ，・・・，ＱＢ _ｊ−１ ，ＱＺを生成するステップと、
   （Ａ）Ｈ演算部が、量子ビットＱＤ _１ にアダマール演算を適用するステップと、
   （Ｂ）第１乗算部が、前記Ａと変数ｇａとからＡ・２ ^{２ｊ−ｇａ−１} を算出するステップと、
   （Ｃ）第１Ｍ ＭＯＤ演算部が、量子ビットＱＤ _１ とＱＤ _２ とが１を示す量子状態のときのみ、量子ビットＱＵ _１ ，・・・ＱＵ _ｊ−１ ，ＱＢ _０ ，・・・，ＱＢ _ｊ−１ ，ＱＺとに対し、前記第１乗算部が算出したＡ・２ ^{２ｊ−ｇａ−１} から計算した２ ^０ ・Ａ・２ ^{２ｊ−ｇａ−１} を前記Ｆとして請求項１に記載のステップ（ａ）〜（ｊ）を実行し、その結果の量子ビットＱＤ _１ とＱＤ _２ を制御ビットとしＱＺを標的ビットとするＴｏｆｆｏｌｉ演算を適用し、さらに、変数ｇｂ＝１からｊ−１まで、量子ビットＱＤ _２ とＵ _ｇｂ にＳＷＡＰ演算を適用し、前記変数ｇｂと前記第１乗算部が算出したＡ・２ ^{２ｊ−ｇａ−１} とから計算した２ ^ｇｂ ・Ａ・２ ^{２ｊ−ｇａ−１} を前記Ｆとして請求項１に記載のステップ（ａ）〜（ｊ）を適用し、その結果の量子ビットＱＤ _２ とＱＵ _ｇｂ にＳＷＡＰ演算を適用する演算を繰り返すステップと、
   （Ｄ）ＣＳＷＡＰ演算部が、量子ビットＱＤ _１ ，ＱＤ _２ ，ＱＵ _１ ，・・・ＱＵ _ｊ−１ ，ＱＢ _０ ，・・・，ＱＢ _ｊ−１ に対し、ＱＤ _２ をＱＵ _０ として、ｋ＝０からｊ−１について、ＱＢ _ｋ を制御ビットとしＱＵ _ｋ を目標ビットとした制御ＮＯＴ演算を適用し、ＱＤ _１ とＱＵ _ｋ を制御ビットとしＱＢ _ｋ を目標ビットとしたＴｏｆｆｏｌｉ演算を適用し、ＱＢ _ｋ を制御ビットとしＱＵ _ｋ を目標ビットとした制御ＮＯＴ演算を適用するステップと、
   （Ｅ）第２乗算部が、前記第１乗算部で算出したＡ・２ ^{２ｊ−ｇａ−１} から（Ａ・２ ^{２ｊ−ｇａ−１} ） ^−１ を算出するステップと、
   （Ｆ）第２Ｍ ＭＯＤ演算部が、量子ビットＱＤ _１ とＱＤ _２ とが１を示す量子状態のときのみ、量子ビットＱＵ _１ ，・・・ＱＵ _ｊ−１ ，ＱＢ _０ ，・・・，ＱＢ _ｊ−１ ，ＱＺとに対し、前記第２乗算部が算出した（Ａ・２ ^{２ｊ−ｇａ−１} ） ^−１ から計算した２ ^０ ・（Ａ・２ ^{２ｊ−ｇａ−１} ） ^−１ を前記Ｆとして請求項１に記載の（ａ）〜（ｊ）を適用し、その結果の量子ビットＱＤ _１ とＱＤ _２ を制御ビットとしＱＺを標的ビットとするＴｏｆｆｏｌｉ演算を適用し、さらに、その結果の量子ビットに対して、変数ｇｂ＝０からｊ−１まで、量子ビットＱＤ _２ とＵ _ｇｂ にＳＷＡＰ演算を適用し、前記変数ｇｂと前記第２乗算部が算出した（Ａ・２ ^{２ｊ−ｇａ−１} ） ^−１ とから計算した２ ^ｇｂ ・（Ａ・２ ^{２ｊ−ｇａ−１} ） ^−１ を前記Ｆとして請求項１に記載のステップ（ａ）〜（ｊ）を適用し、その結果の量子ビットＱＤ _２ とＱＵ _ｇｂ にＳＷＡＰ演算を適用する演算を繰り返すステップと、
   （Ｇ）観測部が、量子ビットＱＤ _１ の量子状態を観測し、その結果を前記ｃ _ｇａ として前記メモリに格納するステップと、
   （Ｈ）Ｘ _ｃｋ 演算部が、前記観測部で観測した結果ｃ _ｇａ が１のときのみ、量子ビットＱＤ _１ の量子状態を反転させるステップと、
   （Ｉ）Ｒ _ｋ 演算部が、量子ビットＱＤ _１ が１を示す量子状態のときのみ、ＱＤ _１ に
   

   

   （ただし、量子ビットＱＤ _１ の量子状態を｜ＱＤ _１ ＞とする）の演算を施すステップと、
   量子計算制御部が、変数ｇａに０を代入して上記ステップ（Ａ）〜（Ｆ）を順に実行させ、その結果の量子ビットに対して上記ステップ（Ａ）を実行させ、更に、上記ステップ（Ｇ）を実行させ、その結果の量子ビットに対して、変数ｇａ＝１からｇａ＝２ｊ−１まで順番にｇａを１ずつ増やしながら上記ステップ（Ｈ），（Ａ）〜（Ｆ），（Ｉ），（Ｇ）を順に実行させ、前記観測部が観測したｃ _ｇａ （ｇａ＝０，・・・，２ｊ−１）を前記Ａ ^Ｒ ＝１ ｍｏｄ Ｎを満たす最小のＲの算出に有用な値Ｃの各桁として出力することを特徴とする量子計算方法。
3. 請求項１又は２に記載の量子計算方法であって、
   上記第１ＣＯＭＰＡＲＩＳＯＮ演算部が行う上記第１量子操作は、
   ＨＩＧＨＢＩＴ演算部が、量子ビットＱＢ_ｊ−１，…，ＱＢ_０と、量子ビットＱＵ_ｊ−１，…，ＱＵ_１と、量子ビットＱＺと対して第２量子操作を行い、量子ビットＱＺを、ｚ（＋）β〔βはＮ−Ｆ＋Ｂの最上位桁、（＋）は排他的論理和〕を示す量子状態とし、他の量子ビットＱＢ_ｊ−１，…，ＱＢ_０、ＱＵ_ｊ−１，…，ＱＵ_１の量子状態を当該第２量子操作前の量子状態とするステップと、
   第３ＮＯＴ演算部が、量子ビットＱＺにＮＯＴ演算を施すステップと、
   古典情報によって制御される第４ＮＯＴ演算部が、上記メモリから読み込まれた古典情報であるＮ−Ｆの桁（ｎ−ｆ）_ｈ（ｈ∈｛ｊ−１，…，０｝）の値が１となるｈに対応する量子ビットＱＢ_ｈのみにＮＯＴ演算を施すステップと、
   第５ＮＯＴ演算部が、各量子ビットＱＢ_ｊ−１，…，ＱＢ_０にＮＯＴ演算を施すステップと、
   第２Ｔｏｆｆｏｌｉ演算部が、各量子ビットＱＢ_ｊ−１，…，ＱＢ_０を制御ビットとし、量子ビットＱＺを目標ビットとしたＴｏｆｆｏｌｉ演算を施すステップと、
   第６ＮＯＴ演算部が、各量子ビットＱＢ_ｊ−１，…，ＱＢ_０にＮＯＴ演算を施すステップと、
   古典情報によって制御される第７ＮＯＴ演算部が、上記メモリから読み込まれた古典情報であるＮ−Ｆの桁（ｎ−ｆ）_ｈ の値が１となるｈに対応する量子ビットＱＢ_ｈのみにＮＯＴ演算を施すステップと、
   を有することを特徴とする量子計算方法。
4. ２進数ｊ桁のＮ＝ｎ_ｊ−１…ｎ_０と、２進数ｊ桁のＦ＝ｆ _ｊ−１…ｆ _０と、２進数ｊ桁のＢ＝ｂ _ｊ−１ …ｂ _０ とから、Ｆ＋Ｂ ｍｏｄ Ｎを算出する量子計算装置であって、
   上記ＮとＦとを格納するメモリと、
   上記メモリから読み込んだＮとＦとからＮ−Ｆを算出する減算部と、
   上記減算部が算出したＮ−Ｆを用い、前記Ｂ＝ｂ_ｊ−１…ｂ_０の各桁をそれぞれ示す量子状態の量子ビットＱＢ_ｊ−１， … ，ＱＢ_０と、任意の量子状態の量子ビットＱＵ_ｊ−１，… ＱＵ_１，ＱＺと、に対し、前記Ｎ−ＦとＢとを比較する第１量子操作を行い、Ｎ−Ｆ＞Ｂの場合にのみ量子ビットＱＺの量子状態を反転させる第１ＣＯＭＰＡＲＩＳＯＮ演算部と、
   前記第１ＣＯＭＰＡＲＩＳＯＮ演算部が演算した結果の量子ビットＱＢ _ｊ−１ ，…，ＱＢ _０ にＱＦＴ（量子フーリエ変換）演算を適用するＱＦＴ演算部と、
   前記第１ＣＯＭＰＡＲＩＳＯＮ演算部が演算した結果の量子ビットＱＺが１を示す量子状態のときのみ、前記ＱＦＴ演算部が演算した結果の前記量子ビットＱＢ _ｊ−１ ，…，ＱＢ _０ のうち１を示す量子状態の量子ビットＱＢ _ｋ （０≦ｋ≦ｊ−１）に対し、
   

   

   （ただし、量子ビットＱＢ _ｋ の量子状態を｜ＱＢ _ｋ 〉とし、ｅをネピア数とし、ｉを虚数単位とする）の演算を施すφＡＤＤ演算部と、
   前記第１ＣＯＭＰＡＲＩＳＯＮ演算部が演算した結果の量子ビットＱＺにＮＯＴ演算を施す第１ＮＯＴ演算部と、
   前記第１ＮＯＴ演算部が演算した結果の量子ビットＱＺが１を示す量子状態のときのみ、前記φＡＤＤ演算部が演算した結果の量子ビットＱＢ _ｊ−１ ，…，ＱＢ _０ のうち１を示す量子状態の量子ビットＱＢ _ｋ （０≦ｋ≦ｊ−１）に対し、
   

   

   （ただし、Ｎ−Ｆ＝（ｎ−ｆ） _ｊ−１ …（ｎ−ｆ） _０ とする）の演算を施すφＡＤＤ ^−１ 演算部と、
   前記第１ＮＯＴ演算部が演算した結果の量子ビットＱＺにＮＯＴ演算を施す第２ＮＯＴ演算部と、
   前記φＡＤＤ ^−１ 演算部が演算した結果の量子ビットＱＢ _ｊ−１ ，…，ＱＢ _０ にＱＦＴ演算の逆演算を適用するＱＦＴ ^−１ 演算部と、
   前記ＦとＢと用い、前記ＱＦＴ ^−１ 演算部が演算した結果の量子ビットＱＢ _ｊ−１ ，… ，ＱＢ _０ と、前記第１ＣＯＭＰＡＲＩＳＯＮ演算部が演算した結果の量子ビットＱＵ _ｊ−１ ，…，ＱＵ _１ と前記第２ＮＯＴ演算部が演算した結果の量子ビットＱＺと、に対し、前記ＦとＢとを比較する第１量子操作を行い、Ｆ＞Ｂの場合にのみ前記第２ＮＯＴ演算部が演算した結果の量子ビットＱＺの量子状態を反転させる量子操作を行う第２ＣＯＭＰＡＲＩＳＯＮ演算部と、を有し、
   前記第２ＣＯＭＰＡＲＩＳＯＮ演算部が演算した結果の量子ビットＱＢ _０ ・・・ＱＢ _ｊ−１ を前記Ｆ＋Ｂ ｍｏｄ Ｎの各桁に対応する量子状態を表す量子ビットとして出力することを特徴とする量子計算装置。
5. 請求項１に記載のＦ＋Ｂ ｍｏｄ Ｎを算出する量子計算方法を用いて、前記２進数ｊ桁のＮ＝ｎ _ｊ−１ …ｎ _０ と、前記Ｎよりも小さい２進数ｊ桁のＡ＝ａ _ｊ−１ …ａ _０ とから、Ａ ^Ｒ ＝１ ｍｏｄ Ｎを満たす最小のＲの算出に有用な値Ｃ＝ｃ _２ｊ−１ ・・・ｃ _０ を計算する量子計算装置であって、
   ０と１と２ｊ個の０とをそれぞれ示す量子ビットＱＤ _１ ，ＱＤ _２ ，ＱＵ _１ ，・・・ＱＵ _ｊ−１ ，ＱＢ _０ ，・・・，ＱＢ _ｊ−１ ，ＱＺを生成する初期量子状態生成部と、
   量子ビットＱＤ _１ にアダマール演算を適用するＨ演算部と、
   前記Ａと変数ｇａとからＡ・２ ^{２ｊ−ｇａ−１} を算出する第１乗算部と、
   量子ビットＱＤ _１ とＱＤ _２ とが１を示す量子状態のときのみ、量子ビットＱＵ _１ ，・・・ＱＵ _ｊ−１ ，ＱＢ _０ ，・・・，ＱＢ _ｊ−１ ，ＱＺとに対し、前記第１乗算部が算出したＡ・２ ^{２ｊ−ｇａ−１} から計算した２ ^０ ・Ａ・２ ^{２ｊ−ｇａ−１} を前記Ｆとして請求項１に記載のステップ（ａ）〜（ｊ）を実行し、その結果の量子ビットＱＤ _１ とＱＤ _２ を制御ビットとしＱＺを標的ビットとするＴｏｆｆｏｌｉ演算を適用し、さらに、変数ｇｂ＝１からｊ−１まで、量子ビットＱＤ _２ とＵ _ｇｂ にＳＷＡＰ演算を適用し、前記変数ｇｂと前記第１乗算部が算出したＡ・２ ^{２ｊ−ｇａ−１} とから計算した２ ^ｇｂ ・Ａ・２ ^{２ｊ−ｇａ−１} を前記Ｆとして請求項１に記載のステップ（ａ）〜（ｊ）を適用し、その結果の量子ビットＱＤ _２ とＱＵ _ｇｂ にＳＷＡＰ演算を適用する演算を繰り返す第１Ｍ ＭＯＤ演算部と、
   量子ビットＱＤ _１ ，ＱＤ _２ ，ＱＵ _１ ，・・・ＱＵ _ｊ−１ ，ＱＢ _０ ，・・・，ＱＢ _ｊ−１ に対し、ＱＤ _２ をＱＵ _０ として、ｋ＝０からｊ−１について、ＱＢ _ｋ を制御ビットとしＱＵ _ｋ を目標ビットとした制御ＮＯＴ演算を適用し、ＱＤ _１ とＱＵ _ｋ を制御ビットとしＱＢ _ｋ を目標ビットとしたＴｏｆｆｏｌｉ演算を適用し、ＱＢ _ｋ を制御ビットとしＱＵ _ｋ を目標ビットとした制御ＮＯＴ演算を適用するＣＳＷＡＰ演算部と、
   前記第１乗算部で算出したＡ・２ ^{２ｊ−ｇａ−１} から（Ａ・２ ^{２ｊ−ｇａ−１} ） ^−１ を算出する第２乗算部と、
   量子ビットＱＤ _１ とＱＤ _２ とが１を示す量子状態のときのみ、量子ビットＱＵ _１ ，・・・ＱＵ _ｊ−１ ，ＱＢ _０ ，・・・，ＱＢ _ｊ−１ ，ＱＺとに対し、前記第２乗算部が算出した（Ａ・２ ^{２ｊ−ｇａ−１} ） ^−１ から計算した２ ^０ ・（Ａ・２ ^{２ｊ−ｇａ−１} ） ^−１ を前記Ｆとして請求項１に記載の（ａ）〜（ｊ）を適用し、その結果の量子ビットＱＤ _１ とＱＤ _２ を制御ビットとしＱＺを標的ビットとするＴｏｆｆｏｌｉ演算を適用し、さらに、その結果の量子ビットに対して、変数ｇｂ＝０からｊ−１まで、量子ビットＱＤ _２ とＵ _ｇｂ にＳＷＡＰ演算を適用し、前記変数ｇｂと前記第２乗算部が算出した（Ａ・２ ^{２ｊ−ｇａ−１} ） ^−１ とから計算した２ ^ｇｂ ・（Ａ・２ ^{２ｊ−ｇａ−１} ） ^−１ を前記Ｆとして請求項１に記載のステップ（ａ）〜（ｊ）を適用し、その結果の量子ビットＱＤ _２ とＱＵ _ｇｂ にＳＷＡＰ演算を適用する演算を繰り返す第２Ｍ ＭＯＤ演算部と、
   量子ビットＱＤ _１ の量子状態を観測し、その結果を前記ｃ _ｇａ として前記メモリに格納する観測部と、
   前記観測部で観測した結果ｃ _ｇａ が１のときのみ、量子ビットＱＤ _１ の量子状態を反転させるＸ _ｃｋ 演算部と、
   量子ビットＱＤ _１ が１を示す量子状態のときのみ、ＱＤ _１ に
   

   

   （ただし、量子ビットＱＤ _１ の量子状態を｜ＱＤ _１ ＞とする）の演算を施すＲ _ｋ 演算部と、
   変数ｇａに０を代入し、上記Ｈ演算部の処理（Ａ）、上記第１乗算部の処理（Ｂ）、上記第１Ｍ ＭＯＤ演算部の処理（Ｃ）、上記ＣＳＷＡＰ演算部の処理（Ｄ）、上記第２乗算部の処理（Ｅ）、及び上記第２Ｍ ＭＯＤ演算部の処理（Ｆ）を順に実行させ、その結果の量子ビットに対して上記処理（Ａ）を実行させ、更に、上記観測部の処理（Ｇ）を実行させ、その結果の量子ビットに対して、変数ｇａ＝１からｇａ＝２ｊ−１まで順番にｇａを１ずつ増やしながら上記Ｘ _ｃｋ 演算部の処理（Ｈ）、上記処理（Ａ）〜（Ｆ），上記Ｒ _ｋ 演算部の処理（Ｉ），上記処理（Ｇ）を順に実行させ、前記観測部が観測したｃ _ｇａ （ｇａ＝０，・・・，２ｊ−１）を前記Ａ ^Ｒ ＝１ ｍｏｄ Ｎを満たす最小のＲの算出に有用な値Ｃの各桁として出力させる量子計算制御部と、
   を有することを特徴とする量子計算装置。

Images