"nが1以上の整数であり、mがlog以上の最小の整数であり、gが2≦g≦mを満たす整数であり、jが1≦j≦mを満たす整数であり、kが1≦k≦nを満たす整数であり、xkが0又は1であり、n個の量子ビットR11R1nからなるレジスタR1の初期量子状態が|x1>|xn>であり、n個の量子ビットRg1RgnからなるレジスタRgの初期量子状態のそれぞれが|0>|0>であり、n個の量子ビットSj1SjnからなるレジスタSjの初期量子状態のそれぞれが|0>|0>であり、α1個の量子ビットTj1TjαからなるレジスタTjの初期量子状態のそれぞれが|0>|0>であり、βm1個の量子ビットU1UβからなるレジスタUの初期量子状態が|0>|0>であり、γ1個の量子ビットV1VγからなるレジスタVの初期量子状態が|0>|0>であり、各kについて、前記量子ビットR1kを制御ビットとし、前記量子ビットR2kRmkを目標ビットとして、前記量子ビットR1kRmkに対するFanout演算を実行するステップと、各jについて、前記量子ビットSj1に対するアダマール演算Hを実行するステップと、前記ステップの後、各jについて、前記量子ビットSj1を制御ビットとし、前記量子ビットSj2Sjnを目標ビットとして、前記量子ビットSj1Sjnに対するFanout演算を実行するステップと、前記ステップの後、各jkについて、前記量子ビットRjkを制御ビットとし、前記量子ビットSjkを目標ビットとして、前記量子ビットRjkSjkに対するCPHASE演算を実行するステップと、前記ステップの後、各jについて、前記量子ビットSj1を制御ビットとし、前記量子ビットSj2Sjnを目標ビットとして、前記量子ビットSj1Sjnに対するFanout演算を実行するステップと、前記ステップの後、各jについて、前記量子ビットSj1に対するアダマール演算Hを実行するステップと、前記ステップの後、各jについて、前記量子ビットSj1を制御ビットとし、前記量子ビットTj1Tjαを目標ビットとして、前記量子ビットSj1Tj1Tjαに対するFanout演算を実行するステップと、前記ステップの後、各jp1について、前記量子ビットTjpに対するアダマール演算Hを実行し、各qm1について、前記量子ビットUqに対するアダマール演算Hを実行するステップと、yjが0又は1であり、Yがyy1ym≧2を満たすm桁の任意のビット列yy1ymを要素とする集合であり、前記ビット列yy1ymを構成するビットy1ymの中で値が1であるビットがであり、a≦m1が、前記集合Yに属する前記ビット列yy1ymのそれぞれに対して、前記ビット列yy1ymが表す2進数表現値の小さい方から順番に付された1からm1までの互いに異なる整数番号であり、ajが、前記集合Yの要素であるビット列y’y1’ym’のうちで、当該ビット列y’y1’ym’が表す2進数表現値が当該ajに対応する前記ビット列yy1ymが表す2進数表現値よりも小さく、なおかつ、ビットyj’の値が1であるビット列の個数に1を加えた数であり、前記ステップの後、前記集合Yに属する各要素について、前記量子ビットを制御ビットとし、前記量子ビットを目標ビットとして、前記量子ビットに対するFanout演算を実行するステップと、前記ステップの後、各jp1について、前記量子ビットTjpに対するアダマール演算Hを実行し、各qm1について、前記量子ビットUqに対するアダマール演算Hを実行するステップと、前記量子ビットV1に対するアダマール演算Hを実行するステップと、前記ステップの後、前記量子ビットV1を制御ビットとし、前記量子ビットV2Vγを目標ビットとして、前記量子ビットV1Vγに対するFanout演算を実行するステップと、前記ステップ及びの後、各jについて、前記量子ビットSj1を制御ビットとし、前記量子ビットVjを目標ビットとして、前記量子ビットSj1Vjに対するCPHASE演算を実行し、各qm1について、前記ステップが実行された前記量子ビットUqを制御ビットとし、前記量子ビットVmqを目標ビットとして、前記量子ビットUqVmqに対するCPHASE演算を実行するステップと、前記ステップの後、前記量子ビットV1を制御ビットとした前記量子ビットV1Vγに対するFanout演算を実行するステップと、前記ステップの後、前記量子ビットV1に対するアダマール演算Hを実行するステップと、を有する量子計算方法。nが1以上の整数であり、mがlog以上の最小の整数であり、gが2≦g≦mを満たす整数であり、jが1≦j≦mを満たす整数であり、kが1≦k≦nを満たす整数であり、xkが0又は1であり、n個の量子ビットR11R1nからなるレジスタR1の初期量子状態が|x1>|xn>であり、n個の量子ビットRg1RgnからなるレジスタRgの初期量子状態のそれぞれが|0>|0>であり、n個の量子ビットSj1SjnからなるレジスタSjの初期量子状態のそれぞれが|0>|0>であり、α1個の量子ビットTj1TjαからなるレジスタTjの初期量子状態のそれぞれが|0>|0>であり、βm1個の量子ビットU1UβからなるレジスタUの初期量子状態が|0>|0>であり、γ1個の量子ビットV1VγからなるレジスタVの初期量子状態が|0>|0>であり、各kについて、前記量子ビットR1kを制御ビットとし、前記量子ビットR2kRmkを目標ビットとして、前記量子ビットR1kRmkに対するFanout演算を実行する第1処理部と、各jについて、前記量子ビットSj1に対するアダマール演算Hを実行する第2処理部と、前記第2処理部による処理の後、各jについて、前記量子ビットSj1を制御ビットとし、前記量子ビットSj2Sjnを目標ビットとして、前記量子ビットSj1Sjnに対するFanout演算を実行する第3処理部と、前記第3処理部による処理の後、各jkについて、前記量子ビットRjkを制御ビットとし、前記量子ビットSjkを目標ビットとして、前記量子ビットRjkSjkに対するCPHASE演算を実行する第4処理部と、前記第4処理部による処理の後、各jについて、前記量子ビットSj1を制御ビットとし、前記量子ビットSj2Sjnを目標ビットとして、前記量子ビットSj1Sjnに対するFanout演算を実行する第5処理部と、前記第5処理部による処理の後、各jについて、前記量子ビットSj1に対するアダマール演算Hを実行する第6処理部と、前記第6処理部による処理の後、各jについて、前記量子ビットSj1を制御ビットとし、前記量子ビットTj1Tjαを目標ビットとして、前記量子ビットSj1Tj1Tjαに対するFanout演算を実行する第7処理部と、前記第7処理部による処理の後、各jp1について、前記量子ビットTjpに対するアダマール演算Hを実行し、各qm1について、前記量子ビットUqに対するアダマール演算Hを実行する第8処理部と、yjが0又は1であり、Yがyy1ym≧2を満たすm桁の任意のビット列yy1ymを要素とする集合であり、前記ビット列yy1ymを構成するビットy1ymの中で値が1であるビットがであり、a≦m1が、前記集合Yに属する前記ビット列yy1ymのそれぞれに対して、前記ビット列yy1ymが表す2進数表現値の小さい方から順番に付された1からm1までの互いに異なる整数番号であり、ajが、前記集合Yの要素であるビット列y’y1’ym’のうちで、当該ビット列y’y1’ym’が表す2進数表現値が当該ajに対応する前記ビット列yy1ymが表す2進数表現値よりも小さく、なおかつ、ビットyj’の値が1であるビット列の個数に1を加えた数であり、前記第8処理部による処理の後、前記集合Yに属する各要素について、前記量子ビットを制御ビットとし、前記量子ビットを目標ビットとして、前記量子ビットに対するFanout演算を実行する第9処理部と、前記第9処理部による処理の後、各jp1について、前記量子ビットTjpに対するアダマール演算Hを実行し、各qm1について、前記量子ビットUqに対するアダマール演算Hを実行する第10処理部と、前記量子ビットV1に対するアダマール演算Hを実行する第11処理部と、前記第11処理部による処理の後、前記量子ビットV1を制御ビットとし、前記量子ビットV2Vγを目標ビットとして、前記量子ビットV1Vγに対するFanout演算を実行する第12処理部と、前記第6,11処理部による処理の後、各jについて、前記量子ビットSj1を制御ビットとし、前記量子ビットVjを目標ビットとして、前記量子ビットSj1Vjに対するCPHASE演算を実行し、各qm1について、前記第10処理部による処理が実行された前記量子ビットUqを制御ビットとし、前記量子ビットVmqを目標ビットとして、前記量子ビットUqVmqに対するCPHASE演算を実行する第13処理部と、前記第13処理部による処理の後、前記量子ビットV1を制御ビットとした前記量子ビットV1Vγに対するFanout演算を実行する第14処理部と、前記第14処理部による処理の後、前記量子ビットV1に対するアダマール演算Hを実行する第15処理部と、を有する量子計算装置。請求項1の量子計算方法のすべてのステップを実行する回路。計算ステップの個数が多いほど計算時間が長くなる。また、基本演算の個数が多いほど誤りの発生する可能性が大きくなる。このため、計算ステップと基本演算の個数はできるだけ少ないほうが良い。上述した従来方法ではO個の計算ステップとO個の基本演算で論理和関数を計算するが、基本演算の個数を増加させることなく、入力桁数nにかかわらず定数個の計算ステップで論理和関数を計算する方法は知られていない。本発明はこのような点に鑑みてなされたものであり、定数個の計算ステップとO個の基本演算で論理和関数を計算することが可能な技術を提供することを目的とする。本発明では、nが1以上の整数であり、mがlog以上の最小の整数であり、gが2≦g≦mを満たす整数であり、jが1≦j≦mを満たす整数であり、kが1≦k≦nを満たす整数であり、xkが0又は1であり、n個の量子ビットR11R1nからなるレジスタR1の初期量子状態が|x1>|xn>であり、n個の量子ビットRg1RgnからなるレジスタRgの初期量子状態のそれぞれが|0>|0>であり、n個の量子ビットSj1SjnからなるレジスタSjの初期量子状態のそれぞれが|0>|0>であり、α1個の量子ビットTj1TjαからなるレジスタTjの初期量子状態のそれぞれが|0>|0>であり、βm1個の量子ビットU1UβからなるレジスタUの初期量子状態が|0>|0>であり、γ1個の量子ビットV1VγからなるレジスタVの初期量子状態が|0>|0>である。まず各kについて、量子ビットR1kを制御ビットとし、量子ビットR2kRmkを目標ビットとして、量子ビットR1kRmkに対するFanout演算を実行し、各jについて、量子ビットSj1に対するアダマール演算Hを実行し、各jについて、量子ビットSj1を制御ビットとし、量子ビットSj2Sjnを目標ビットとして、量子ビットSj1Sjnに対するFanout演算を実行し、各jkについて、量子ビットRjkを制御ビットとし、量子ビットSjkを目標ビットとして、量子ビットRjkSjkに対するCPHASE演算を実行し、ステップの後、各jについて、量子ビットSj1を制御ビットとし、量子ビットSj2Sjnを目標ビットとして、量子ビットSj1Sjnに対するFanout演算を実行し、各jについて、量子ビットSj1に対するアダマール演算Hを実行する。その後、各jについて、量子ビットSj1を制御ビットとし、量子ビットTj1Tjαを目標ビットとして、量子ビットSj1Tj1Tjαに対するFanout演算を実行し、各jp1について、量子ビットTjpに対するアダマール演算Hを実行し、各qm1について、量子ビットUqに対するアダマール演算Hを実行し、集合Yに属する各要素について、量子ビットを制御ビットとし、量子ビットを目標ビットとして、量子ビットに対するFanout演算を実行する。ただし、yjが0又は1であり、Yがyy1ym≧2を満たすm桁の任意のビット列yy1ymを要素とする集合であり、ビット列yy1ymを構成するビットy1ymの中で値が1であるビットがであり、a≦m1が、集合Yに属するビット列yy1ymのそれぞれに対して、ビット列yy1ymが表す2進数表現値の小さい方から順番に付された1からm1までの互いに異なる整数番号であり、ajが、集合Yの要素であるビット列y’y1’ym’のうちで、当該ビット列y’y1’ym’が表す2進数表現値が当該ajに対応するビット列yy1ymが表す2進数表現値よりも小さく、なおかつ、ビットyj’の値が1であるビット列の個数に1を加えた数である。さらに、各jp1について、量子ビットTjpに対するアダマール演算Hを実行し、各qm1について、量子ビットUqに対するアダマール演算Hを実行し、量子ビットV1に対するアダマール演算Hを実行し、量子ビットV1を制御ビットとし、量子ビットV2Vγを目標ビットとして、量子ビットV1Vγに対するFanout演算を実行し、各jについて、量子ビットSj1を制御ビットとし、量子ビットVjを目標ビットとして、量子ビットSj1Vjに対するCPHASE演算を実行し、各qm1について、量子ビットUqを制御ビットとし、量子ビットVmqを目標ビットとして、量子ビットUqVmqに対するCPHASE演算を実行し、量子ビットV1を制御ビットとした量子ビットV1Vγに対するFanout演算を実行し、量子ビットV1に対するアダマール演算Hを実行する。これによって、量子ビットV1の状態が|x1∨∨xn>となる。これらの計算ステップの個数はnの値にかからず定数であり、基本演算数はO個である。本発明では、定数個の計算ステップとO個の基本演算で論理和関数を計算できる。以下、図面を参照して本発明の実施形態を説明する。<定義>実施形態で用いられる記号や用語を定義する。量子ビットqubitとは、量子情報処理における基本単位である。量子ビットの具体例は、光子の偏光や原子の核スピンなどである。量子ビットは、古典的ビットの2値に対応する計算基底の量子状態の重ね合わせ状態をとる。重ね合わせ状態とは、量子力学的に複数の量子状態が同時に存在することを意味する。量子状態はケットベクトル|Φ>を用いて表記される。量子状態の重ね合わせ状態はケットベクトルの線形和として表記される。|Φ1>|Φ2>は|Φ1>と|Φ1>とのテンソル積を表す。いかなる|Φ1>及び|Φ2>を用いても|Φ1>|Φ2>で表現することのできない複数の量子ビットの量子状態をエンタングルメント状態と呼ぶ。図4Aに示すように、入力されたκ1個の量子ビットの量子状態|η>|μ1>|μκ>を量子状態|η>|ημ1>|ημκ>に変換する処理をκFanout演算と呼ぶημτ∈01、1≦τ≦κ、κ≧1。ただし、は排他的論理和演算子を表す。ここで量子状態|η>で入力された1個の量子ビットが制御ビットであり、量子状態|μτ>で入力されたκ個の量子ビットが目標ビットである。κFanout演算によって、制御ビットの量子状態は|η>となり、目標ビットの量子状態はそれぞれ|ημτ>1≦τ≦κとなる。なお1Fanout演算をCNOT演算と呼ぶ。図4Bに示すように、入力された1個の量子ビットの量子状態|η>を以下の量子状態に変換する処理をアダマールHadamard演算と呼び、Hと表記するη∈01。図4Cに示すように、入力された2個の量子ビットの量子状態|η>|μ>を以下の量子状態に変換する処理をCPHASE演算と呼ぶημ∈01、λは整数。ただし、iは虚数単位を表し、πは円周率を表す。ここで量子状態|η>で入力された量子ビットが制御ビットであり、量子状態|μ>で入力された量子ビットが目標ビットである。<構成>図1に例示するように、本形態の量子計算装置1は処理部101~115及び制御部100を有し、処理部101~115は制御部100の制御のもと量子ビットに対する演算処理を行う。量子計算装置1は、例えば、量子コンピュータ或いは量子コンピュータと古典コンユータとの組合せで実現できる。量子コンピュータを実現する物理系としては、例えば、イオントラップを用いる方法参考文献1JICiracandPZollerQuantumcomputationswithcoldtrappedionsPhysicalRevLettvol74No20pp409140941995などを例示できる。イオントラップ量子コンピュータでは、イオンの基底状態と励起状態を利用して量子ビットを実現し、イオンを直線上に並べて計算を行う。アダマール演算Hを含む1量子ビットユニタリ演算は個々のイオンに狙いを定めたレーザービームによって実現され、2量子ビットユニタリ演算CNOTも同様に実現される。CPHASE演算を含む一般の2量子ビットユニタリ演算は1量子ビットユニタリ演算とCNOTを組み合わせて実現される。κFanoutのように、入力の長さκに依存する個数の量子ビット上の演算の実現方法については参考文献1に詳しい。このような物理系を用い、量子計算方法の各ステップを実行する回路が構成される。<前提処理>本形態の量子計算装置1は、入力ビット列xx1xnに対する論理和演算を行い、前述の式の結果を出力する。そのために、n個の量子ビットR11R1nからなるレジスタR1と、n個の量子ビットRg1RgnからなるレジスタRgと、n個の量子ビットSj1SjnからなるレジスタSjと、α1個の量子ビットTj1TjαからなるレジスタTjと、βm1個の量子ビットU1UβからなるレジスタUと、γ1個の量子ビットV1VγからなるレジスタVとが用意される。まず、n個の量子ビットR11R1nからなるレジスタR1の初期量子状態が|x1>|xn>とされ、n個の量子ビットRg1RgnからなるレジスタRgの初期量子状態のそれぞれが|0>|0>とされ、n個の量子ビットSj1SjnからなるレジスタSjの初期量子状態のそれぞれが|0>|0>とされ、α1個の量子ビットTj1TjαからなるレジスタTjの初期量子状態のそれぞれが|0>|0>とされ、βm1個の量子ビットU1UβからなるレジスタUの初期量子状態が|0>|0>とされ、γ1個の量子ビットV1VγからなるレジスタVの初期量子状態が|0>|0>とされる。<第1ステージ>本形態の量子計算方法は、第1ステージと第2ステージとからなる。上記の初期量子状態の各量子ビットに対して第1ステージの処理が実行され、その後、第2ステージの処理が実行される。図2を参照しつつ、第1ステージの処理を説明する。図2はn4m3の例である。処理部101が、各kについて、量子ビットR1kを制御ビットとし、量子ビットR2kRmkを目標ビットとして、量子ビットR1kRmkに対するFanout演算を並列に実行するステップ。処理部102が、各jについて、量子ビットSj1に対するアダマール演算Hを並列に実行するステップ。ステップの後、処理部103が、各jについて、量子ビットSj1を制御ビットとし、量子ビットSj2Sjnを目標ビットとして、量子ビットSj1Sjnに対するFanout演算を並列に実行するステップ。ステップの後、処理部104が、各jkについて、量子ビットRjkを制御ビットとし、量子ビットSjkを目標ビットとして、量子ビットRjkSjkに対するCPHASE演算を並列に実行するステップ。ステップの後、処理部105が、各jについて、量子ビットSj1を制御ビットとし、量子ビットSj2Sjnを目標ビットとして、量子ビットSj1Sjnに対するFanout演算を並列に実行するステップ。ステップの後、処理部106が、各jについて、量子ビットSj1に対するアダマール演算Hを並列に実行するステップ。<第2ステージ>次に、上述した初期量子状態のそれぞれが|0>|0>であるα1個の量子ビットTj1TjαからなるレジスタTjと、初期量子状態のそれぞれが|0>|0>であるβm1個の量子ビットU1UβからなるレジスタUと、初期量子状態のそれぞれが|0>|0>であるγ1個の量子ビットV1VγからなるレジスタVと、第1ステージの処理がなされた量子ビットSj1とを用いて第2ステージが実行される。図3を参照しつつ、第2ステージの処理を説明する。図3はn4m3の例である。ステップの後、処理部107が、各jについて、量子ビットSj1を制御ビットとし、量子ビットTj1Tjαを目標ビットとして、量子ビットSj1Tj1Tjαに対するFanout演算を並列に実行するステップ。ステップの後、処理部108が、各jp1について、量子ビットTjpに対するアダマール演算Hを実行する処理と、各qm1について、量子ビットUqに対するアダマール演算Hを実行する処理とを並列に行うステップ。ステップの後、処理部109が、集合Yに属する各要素について、量子ビットを制御ビットとし、量子ビットを目標ビットとして、量子ビットに対するFanout演算を並列に実行するステップ。ただし、yjが0又は1であり、Yがyy1ym≧2を満たすm桁の任意のビット列yy1ymを要素とする集合である。このような集合Yの要素はm1個m1種類存在する。例えばm3の場合、Y011101110111となる。また、ビット列yy1ymを構成するビットy1ymの中で値が1であるビットを以下のように表現する。例えばm3の場合は以下のようになる。a≦m1は、集合Yに属するビット列yy1ymのそれぞれに対して、ビット列yy1ymが表す2進数表現値の小さい方から順番に付された1からm1までの互いに異なる整数番号である。言い換えると、集合Yに属するビット列yy1ymに対応する2進数表現値を小さい順に並べた場合のビット列yy1ymに対応する順序番号をaとする。またajは、集合Yの要素であるビット列y’y1’ym’のうちで、当該ビット列y’y1’ym’が表す2進数表現値が当該ajに対応するビット列yy1ymが表す2進数表現値よりも小さく、なおかつ、ビットyj’の値が1であるビット列の個数に1を加えた数である。言い換えると、集合Yの要素であるビット列y’y1’ym’のうちで、ビット列yy1ymが表す2進数表現値よりも小さく、なおかつ、左からj番目のビットyj’の値が1であるビット列の個数に1を加えた数をajとする。以下にm3の場合のa及びajを示す。m3の場合、Y011101110111であるため、a及びajは以下のようになる。よってm3の場合のステップは、量子ビットU1を制御ビットとし、量子ビットT21T31を目標ビットとしたT21T31U1に対する2Fanout演算に対応と、量子ビットU2を制御ビットとし、量子ビットT11T32を目標ビットとしたT11T32U2に対する2Fanout演算に対応と、量子ビットU3を制御ビットとし、量子ビットT12T22を目標ビットとしたT12T22U3に対する2Fanout演算に対応と、量子ビットU4を制御ビットとし、量子ビットT13T23T33を目標ビットとしたT13T23T33U4に対する3Fanout演算に対応とを並列に実行する処理である図3参照。ステップの後、処理部110が、各jp1について、量子ビットTjpに対するアダマール演算Hを実行する処理と、各qm1について、量子ビットUqに対するアダマール演算Hを実行する処理とを並列に行うステップ。次に、処理部111が、量子ビットV1に対するアダマール演算Hを実行するステップ。ステップの後、処理部112が、量子ビットV1を制御ビットとし、量子ビットV2Vγを目標ビットとして、量子ビットV1Vγに対するFanout演算を実行するステップ。ステップの後、処理部113が、各jについて、量子ビットSj1を制御ビットとし、量子ビットVjを目標ビットとして、量子ビットSj1Vjに対するCPHASE演算を実行する処理と、各qm1について、量子ビットUqを制御ビットとし、量子ビットVmqを目標ビットとして、量子ビットUqVmqに対するCPHASE演算を実行する処理とを並列に実行するステップ。ステップの後、処理部114が、量子ビットV1を制御ビットとし、量子ビットV2Vγを目標ビットとして、量子ビットV1Vγに対するFanout演算を実行するステップ。ステップの後、量子ビットV1に対するアダマール演算Hを実行するステップ。以上の処理により、量子ビットV1の量子状態が|x1∨∨xn>となる。よって、量子ビットV1を観測することで論理和x1∨∨xnを得ることができる。本形態の第1ステージ及び第2ステージは、共に定数個の計算ステップで実行されるため、回路全体でも定数個の計算ステップで実行される。本形態の第1ステージは、非特許文献1の第1ステージと同じであり、OO個の基本演算が実行される。また、本形態の第2ステージでは、ステップ及びにおいて、m2mm1個のアダマール演算Hが行われるため、O個の基本演算が行われる。従って、回路全体でO個の基本演算が行われる。<量子ビットV1の量子状態が|x1∨∨xn>となる理由>本形態で最終的に量子ビットV1の量子状態が|x1∨∨xn>となる理由について説明する。本形態の第1ステージステップ~の処理は、非特許文献1に記載された第1ステージと同じである。前述のように、第1ステージでは、初期量子状態が|x1>|xn>とされたn個の量子ビットR11R1nからなるレジスタR1等を入力とし、mceil個の量子ビットSj1の量子状態を前述の式の量子状態にする非特許文献1参照。前述のように、n個の値x1xnの論理和x1∨∨xnは、式に示したm個の量子ビットの状態が表す値の論理和の計算に帰着する。したがって、本形態の第2ステージによって得られる量子ビットV1の量子状態が、量子ビットSj1の量子状態によって表される値χ1...χmの論理和を表すのであれば、その量子状態は|x1∨∨xn>である。以下では、本形態の第2ステージによって得られる量子ビットV1の量子状態が、量子ビットSj1の量子状態によって表される値の論理和を表すことを説明する。m個のビットからなるビット列χχ1...χmに対し、以下の等式が満たされる。一般に、この等式の右辺は2m1個の項からなる。ただし、m≧1であり、各jに対してχjが0又は1である。式が成り立つことは数学的帰納法を用いて証明することができるが、例えば、m123の場合には式は以下のようになり、式の右辺が正確に論理和を表現していることが確認できる。本形態の第2ステージでは、上記の式の論理和関数の表現に基づき、初めにの形で表されるのすべての排他的論理和値を得る。ただし、1つの値のみに対応する排他的論理和値はその値そのものχ1...χmであるため、計算する必要があるのは、それらを除く2mm1個の排他的論理和値である。次に、式の排他的論理和値に対応する量子状態を用いて以下の状態を生成する。式の関係から、式の状態は以下と等しいことがわかる。式の状態は、χ1∨...∨χm0の場合に|>となり、χ1∨...∨χm1の場合に|>となる。したがって、式の状態にアダマール演算Hを施して得られる状態は、χ1∨...∨χm0の場合に|0>となり、χ1∨...∨χm1の場合に|1>となる。すなわち、論理和χ1∨...∨χmを表す量子状態が得られ、これは論理和x1∨∨xnを表す。以上のことと第2ステージの各ステップとの対応を示す。本形態の第1ステージで得られた量子ビットSj1の量子状態が|χj>に相当する。本形態の第2ステージでは、式の形で表されるの2mm1個の排他的論理和値を並列に計算する。そのために、各χjを表す量子状態|χj>の量子ビットがα1個必要となる。ステップでは、Fanout演算によって、量子ビットSj1の量子状態|χj>がα1個の量子ビットTj1Tjαの量子状態としてコピーされる。アダマール演算H、Fanout演算、アダマール演算Hを組み合わせると、排他的論理和演算を実行できることが知られている。例えば、量子状態|χ1>|χ2>|0>の3個の量子ビットQ1,Q2,Q3に対してアダマール演算Hを適用し、さらに量子ビットQ3を制御ビットとし、量子ビットQ1,Q2を目標ビットとして、量子ビットQ1,Q2,Q3に対する2Fanout演算を実行し、3個の量子ビットQ1,Q2,Q3に対してアダマール演算Hを適用すると、量子ビットQ1,Q2,Q3の量子状態は|χ1>|χ2>|χ1χ2>となる。ステップ~では、この性質を利用して式の形で表される2mm1個の排他的論理和値を計算し、2mm1個の量子ビットUqm1の量子状態のそれぞれを式の形で表される各排他的論理和値を表す量子状態にしている。ステップでは、アダマール演算Hで量子ビットV1の量子状態を|>にしている。ステップでは、Fanout演算でγ1個の量子ビットV2Vγを以下の量子状態にしている。例えばm3の場合、ステップで8個の量子ビットV1V8の量子状態が、1/√2|0>|1>|0>|0>|0>|0>|0>|0>=1/√2|0>|0>|0>|0>|0>|0>|1>|0>|0>|0>|0>|0>とされ、ステップで1/√2|0>|0>|0>|0>|0>|0>|1>|1>|1>|1>|1>|1>とされる。ステップでは、2m1個の式の排他的論理和値に対応する量子状態を用いて以下の状態を生成する。すなわち、量子状態|χ1>...|χm>のm個の量子ビットSj1と量子状態|0>...|0>の量子ビットVjとに対するCPHASE演算と、その他の式の排他的論理和値に対応するm1個の量子状態の量子ビットUqm1と量子ビットVmqm1に対するCPHASE演算とを行い、γ1個の量子ビットV1Vγの量子状態を式の状態にする。ステップでは、量子ビットV1Vγに対するFanout処理を実行することで、量子ビットV1Vγの量子状態を以下の状態にする。ステップでは、量子ビットV1にアダマール演算Hを施す。これにより、量子ビットV1の量子状態は、χ1∨...∨χm0の場合に|0>となり、χ1∨...∨χm1の場合に|1>となる。以上のように、本形態の第2ステージは、それだけで入力の論理和関数を計算する量子回路となっている。第1ステージと第2ステージとを組み合わせる理由は、第2ステージだけでは入力桁数nに対する指数関数個の基本演算を必要としてしまうからである。第1ステージと第2ステージとを組み合わせることで、定数個の計算ステップとO個の基本演算で論理和関数を計算できる。本発明は上述の実施形態に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。例えば、上記の実施形態では、各ステップの処理がそれぞれ並列に実行されたが、それらの少なくとも一部が時系列的に直列に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。"