"m,nをそれぞれ予め定められた1以上の整数として、2n×2n×...×2nのm次元空間における環Z2上のm変数多項式関数である予め与えられた2次関数fa1x12a2x22...amxm2mod2n1と、シフト量s1s2...smによってgfと表される2次関数gに関するオラクルが予め与えられているとき、上記シフト量s1s2...smを求めるための量子演算方法であって、n個の量子ビットからなる変数用レジスタがm個、n個の量子ビットからなる補助レジスタが1個であり、各上記変数用レジスタ並びに上記補助レジスタに含まれるn個の量子ビットの初期状態を0とし、として、各上記変数用レジスタに含まれるmn個の量子ビットのそれぞれにアダマール変換を適用するアダマール演算ステップと、上記補助レジスタに対して、2次関数gに関する上記オラクルを実行するオラクル演算ステップと、上記補助レジスタに対して、で表される量子回転操作を実行する回転演算ステップと、上記補助レジスタに対して、上記オラクルの量子逆操作を実行するオラクル逆演算ステップと、m個の上記変数用レジスタに対して、を実行する演算ステップとを有する量子演算方法。m,nをそれぞれ予め定められた1以上の整数として、2n×2n×...×2nのm次元空間における環Z2上のm変数多項式関数である予め与えられた2次関数fa1x12a2x22...amxm2mod2n1と、シフト量s1s2...smによってgfと表される2次関数gに関するオラクルが予め与えられているとき、上記シフト量s1s2...smを求めるための量子演算装置であって、n個の量子ビットからなる変数用レジスタがm個、n個の量子ビットからなる補助レジスタが1個であり、各上記変数用レジスタ並びに上記補助レジスタに含まれるn個の量子ビットの初期状態を0とし、として、各上記変数用レジスタに含まれるmn個の量子ビットのそれぞれにアダマール変換を適用するアダマール演算部と、上記補助レジスタに対して、2次関数gに関する上記オラクルを実行するオラクル演算部と、上記補助レジスタに対して、で表される量子回転操作を実行する回転演算部と、上記補助レジスタに対して、上記オラクルの量子逆操作を実行するオラクル逆演算部と、m個の上記変数用レジスタに対して、を実行する演算部とを含む量子演算装置。非特許文献3では、量子アルゴリズムの適用対象が2次ブール関数に限定されているため、この量子アルゴリズムの応用範囲は狭い。例えば、2次関数f22mod2n1はの位置に中心を持ち、fの値が中心からの距離の2乗の2n1を法とする剰余で表される同心円関数であるが、fの値がブール値ではないため、非特許文献3で提案された量子アルゴリズムを用いても2次関数fの中心を特定することができない。本発明は、このような実情に鑑みて、所与の2次関数の隠れシフト問題を解く量子演算技術を提供することを目的とする。本発明は、m,nをそれぞれ予め定められた1以上の整数として、2n×2n×...×2nのm次元空間における環Z2上のm変数多項式関数である予め与えられた2次関数fa1x12a2x22...amxm2mod2n1と、シフト量s1s2...smによってgfと表される2次関数gに関するオラクルが予め与えられているとき、シフト量s1s2...smを求めるための量子演算技術であり、下記のような処理を行う。n個の量子ビットからなる変数用レジスタがm個、n個の量子ビットからなる補助レジスタが1個であり、各変数用レジスタ並びに補助レジスタに含まれるn個の量子ビットの初期状態を0とし、とする。各変数用レジスタに含まれるmn個の量子ビットのそれぞれにアダマール変換を適用するアダマール演算処理。補助レジスタに対して、2次関数gに関するオラクルを実行するオラクル演算処理。補助レジスタに対して、で表される量子回転操作を実行する回転演算処理。補助レジスタに対して、オラクルの量子逆操作を実行するオラクル逆演算処理。m個の変数用レジスタに対して、を実行する。本発明によると、2次関数の隠れシフト問題を解くために拡張Clifford群の性質を或る特別な場合に限定することで得られる関係を、量子コンピュータ上で演算可能な2n次元複素ベクトル空間上の演算に置換することによって、所与の2次関数の隠れシフト問題を量子コンピュータ上で解くことができる。本発明は、拡張Clifford群の性質を利用することによって、量子コンピュータ上で所与の2次関数の隠れシフト問題を解く。そこでまず、本発明の原理の説明に先立ち、拡張Clifford群の性質について概説する。<本発明の原理を理解するために資する従来技術>以下、本発明の原理を理解するために資する従来技術として、下記参考文献Aに開示された成果の一部を概説する。証明等の詳細は参考文献Aを参照されたい。参考文献ADApplebySICPOVMandtheExtendedCliffordGroupJMathPhys46052107arXivquantph0412001まず、Uを全てのd次元ユニタリ演算子からなる群とする。dは正整数である。また、Zを整数環とし、Zdを整数環ZのイデアルdZによる剰余環とする。すなわち、Zd={0,1,,d-2,d-1}である。Z2は各要素が整数である2次元ベクトルの集合を表す。→p=p1,p2T∈Z2、→q=q1,q2T∈Z2としたとき記号Tは転置を表す、ブラケット記号,を式1の如く定義する。また、記号→は、記号→の次の文字の頭上に附されることを意味し、例えば→Aは文字Aの頭上に記号→が附された組み合わせ文字を表す。0,1,,d1をd次元複素ベクトル空間Cdにおける正規直交基底とし、演算子T、S、D→pを式2-4のように定義する。記号iは虚数単位imaginaryunitであり、ネピア数Napiersconstant自然対数の底eのp乗をexpの如く表す。このとき、全ての→p=p1,p2T∈Z2,→q=q1,q2T∈Z2に対して、式5-7が成り立つ。記号†はエルミート共役を表す。式4に定義される演算子D→pに関して、式8の定義を満たすd×dの行列を要素元とする群GPを一般化Pauli群WeylHeisenberg群と呼ぶ。Rは実数体を表す。また、一般化Pauli群GPに対する拡張Clifford群Cは、式9の定義を満たすd×dの行列を元とする群である。U†は、行列Uの共役転置行列である。また、dに関して、dを式10のように定義する。また、記号は、記号の次の文字の頭上に附されることを意味し、例えばAは文字Aの頭上に記号が附された組み合わせ文字を表す。このとき、環Zd上の特殊線形群SL2,Zdは、行列式が1になる2×2行列全体の集合として与えられる式11参照。式11で与えられる特殊線形群SL2,Zdの元のうち、βが0以外の値であり且つβがdと互いに素であるゆえに逆元β1∈Zdが存在する行列を、primematrixという。なお、βが与えられているときに逆元β1の算出は一次合同式β1β≡1moddの解法として古典的知識であるから説明を省略する。補題1拡張Clifford群Cに属する任意のユニタリ演算子U∈Cについて、全ての→p∈Z2に対して式12を満たすF∈SL2,Zd,→Ω∈Zd2が存在する。補題2FをprimematrixT,T∈SL2,Zdとし、演算子VFを式13のように定義する。このとき、演算子VFは、全ての→p∈Z2に対して式14を満たす拡張Clifford群Cに属するユニタリ演算子である。補題3Fをprimematrixではない2×2行列T,T∈SL2,Zdとする。このとき、δxβが0以外の値であり且つδxβがdと互いに素である整数xが存在し、F1=T,T,F2=T,Tとすると、F1とF2はそれぞれprimematrix∈SL2,Zdであり、F=F1F2を満たす。補題4F∈SL2,Zd,→Ω∈Zd2とせよ。Uを、拡張Clifford群Cに属する任意のユニタリ演算子U∈Cとする。もしFがprimematrixならば式15が成立し、もしFがprimematrixでないならばF=F1F2を満たすprimematrixF1とprimematrixF2を選択する補題3参照ことにより式16が成立する。しからば、全ての→p∈Z2に対して式17が成立する。VF,VF1,VF2については式13を参照せよ。補題4から、拡張Clifford群の任意の要素ユニタリ演算子Uは、せいぜい2つのVFと1つのD→Ωを使って表現できることが分かる。<本発明の原理>本発明では、既述の拡張Clifford群の性質を、隠れシフト問題の解を求めるために応用する。隠れシフト問題は、前述の通り、与えられた関数の空間上でのシフト量を計算する問題であり、ここでは具体的に、mnを予め定められた1以上の整数として、2n×2n×...×2nのm次元空間における環Zd上のm変数多項式関数である2次関数fと、適当なs1s2...smに対してgfと表される2次関数gに関するオラクルが与えられているとき、シフト量s1s2...smを求める問題とする。2n×2n×...×2nのm次元空間における環Zd上のm変数多項式関数である2次関数fの多重指数は2であり、このようなfとして、ここではfa1x12a2x22...amxm2mod2n1を考えることにする。2次関数gに関するオラクルとは式18で表される量子操作である。ただし、式18において、○ととの組合せ記号は、2を法とする加算排他的論理和を表す。本発明では、補題2におけるprimematrixFを式19に示すFとし、d2nとすることが主要な特徴の一つである。つまり、補題2のF=T,Tにおいて、α=1,γ=0,δ=1とおいたものが式19のFであり、式2においてd2nとおいたものが式20のτdである。このとき、式13で表されるVFは式21のように表すことができる。なお、式21のVFは2n次元複素ベクトル空間上のユニタリ演算である。量子コンピュータ上の演算の基本的な性質ここで、量子コンピュータにおける演算の基本的な事項について説明する。通常、量子コンピュータにおける情報の基本単位を量子ビットと呼ぶ。現在のコンピュータにおけるビットに相当するものである。第j量子ビットの状態xjは、0,1の二値の重ね合わせ状態で表わされる式22参照。p0とp1は確率振幅と呼ばれ、p02p12=1を満たす複素数であり、この量子状態を観測すると確率p02で0、確率p12で1の状態が得られる。量子状態は、式22の右辺に示されるように、確率振幅を要素に持つ2次元複素ベクトルで表わされる。或る量子状態p00p11から別の量子状態p00p11に変換する量子コンピュータ上の演算Uは、式23で表される。p02p12=1かつp02p12=1なので、この演算Uは、2次元複素ベクトル空間C2上で全てのベクトルの位置関係を保ったまま同じように回転させる演算ユニタリ演算となる。n量子ビットの量子状態xは、式24のようなテンソル積で表わされ、2n次元複素ベクトルとなる。よって、n量子ビットに対する演算は2n次元複素ベクトル空間上のユニタリ演算となる。このように、量子コンピュータ上の演算は、2n次元複素ベクトル空間上のユニタリ演算である。したがって、d2nであるから、2n次元複素ベクトル空間上のユニタリ演算である式21のVFを量子コンピュータで実行することができる。そこで、式21のVFを量子コンピュータ上で実現する方法について説明する。最初に、以下の演算を定義する。ここで、xは式24で表されるn量子ビットからなる量子状態を表す。式25は、周知のn量子ビットの量子フーリエ変換QuantumFourierTransfromである。また、式26は、角度τdの位相演算子を2乗するSquarePhase演算である。<βが奇数の場合>式2526を用いると、式19においてβが奇数の場合、式21で表されるVFは式27のように変形される。詳しくは後述するが、βには所与の2次関数fa1x12a2x22...amxm2mod2n1の係数aii12...mの逆元が入る。係数aiが与えられているときに逆元ai1の算出は一次合同式ai1ai≡1moddの解法として古典的知識であるから説明を省略する。既述のように、QFT2は周知の量子フーリエ変換であり、量子コンピュータ上で効率的に実行できることが知られている非特許文献3の5.1節。なお、2は2nを表す。βは量子コンピュータ上で演算QFT2をβ1回繰り返すことを意味する。次にV2SPについて考える。xの2進数表現をx1x2...xnとする。10進数表現では式28が成り立つ。ここで記号^は、記号^の次の文字の頭上に附されることを意味し、例えば^Aは文字Aの頭上に記号^が附された組み合わせ文字を表す。この記号はべき乗を表す記号^と同じであるが、文脈よりその区別は可能である。すると、式29および式30が成立する。ゆえに、入力状態xx1x2...xnに対して、図1に示される量子回路に従った演算系列を施せば、V2SPの演算を実現できることが分かる。なお、図1では、一つの変数用レジスタに含まれるn個の量子ビットを単にxkk=1,2,...,nと表記しているが、このxkがxkに対応すると思えばよい。ここで、図1に表れる単一量子ビットゲートないし制御ゲートに現れる記号R2jは、式31で定義されるユニタリ変換R2をj回繰り返すことを表している。また、図1において、第3列目以降の演算は、図2に示すようなcontrolledR2jの演算系列を省略表記したものである。よって、図1に示す演算は、controlledR2jの系列で表わされることが分かる。式27における演算2SPβ^は、演算V2SPをβ1回繰り返すことを意味する。ここで、演算V2SPを実現する各演算図1のR2jおよびcontrolledR2jが可換であることを考慮するとこのことは、R2jおよびcontrolledR2jが対角行列で表せる演算であることから容易に分かる、V2SPをβ1回繰り返すことは、図1に示される各演算をβ1回繰り返すこと、つまり、図1のR2jおよびcontrolledR2jをR2jβおよびcontrolledR2jβに置き換えることと等価である。演算2SPβ^についても同様である。<βが偶数の場合>式19においてβが偶数の場合、補題3に従い、2つのprimematrixF1F2∈SL2,Zdを用いて式19のFをF=F1F2と表すことができるので、βが奇数の場合に帰着される。つまり、βが偶数の場合は、βが奇数の場合のVFを実行する量子回路を二つ直列に並べた量子回路によって実行できる。以下、このことを具体的に説明する。補題3によると、式19のFは式31aの2つのprimematrixF1F2∈SL2,Zdを用いてF=F1F2と表すことができる。式31aにおいてtは、1tβ≠0且つ1tβがdただしd2nと互いに素であるを満たす整数tである。詳しくは後述するが、βには所与の2次関数fa1x12a2x22...amxm2mod2n1の係数aii12...mの逆元が入る。係数aiが与えられているときに逆元ai1の算出は一次合同式ai1ai≡1moddの解法として古典的知識であるから説明を省略する。2次関数fが既知であるため、本発明の実施の前にtを求めておくことができる。このtの計算方法は古典的知識であるから説明を省略する。このとき、F1について式31bが成立し、F2について式31cが成立する。式31bは、式2526を用いると、式31dのように変形され、式31cは、式2526を用いると、式31eのように変形される。式31dにて、は、量子コンピュータ上で演算QFT2を1回繰り返すことを意味する。元1が与えられているときに逆元-1の算出は一次合同式-1≡1moddの解法として古典的知識であるから説明を省略する。式31dにて、2SP^は、演算V2SPを1回繰り返すことを意味する。ここで、演算V2SPを実現する各演算図1のR2jおよびcontrolledR2jが可換であることを考慮するとこのことは、R2jおよびcontrolledR2jが対角行列で表せる演算であることから容易に分かる、V2SPを1回繰り返すことは、図1に示される各演算を1回繰り返すこと、つまり、図1のR2jおよびcontrolledR2jをR2jおよびcontrolledR2jに置き換えることと等価である。式31eにて、は、量子コンピュータ上で演算QFT2を1回繰り返すことを意味する。元1tβが与えられているときに逆元-1の算出は一次合同式-1≡1moddの解法として古典的知識であるから説明を省略する。式31eにて、2SP^は、演算V2SPを1回繰り返すことを意味する。ここで、演算V2SPを実現する各演算図1のR2jおよびcontrolledR2jが可換であることを考慮すると、V2SPを1回繰り返すことは、図1に示される各演算を1回繰り返すこと、つまり、図1のR2jおよびcontrolledR2jをR2j^およびcontrolledR2j^に置き換えることと等価である。式31eにて、2SP^tは、演算V2SPを1t回繰り返すことを意味する。ここで、演算V2SPを実現する各演算図1のR2jおよびcontrolledR2jが可換であることを考慮すると、V2SPを1t回繰り返すことは、図1に示される各演算を1t回繰り返すこと、つまり、図1のR2jおよびcontrolledR2jをR2j^tおよびcontrolledR2j^tに置き換えることと等価である。装置構成本発明の実施形態に係る量子演算装置1の機能構成図を図3に示す。この装置は、m個の変数2次関数fの変数用レジスタと1個の補助レジスタを用いる。各変数用レジスタと補助レジスタはそれぞれn個の量子ビットで構成される。従って、使用される量子ビットの数はn個である。まず、初期化部100が、全ての量子ビットを0に初期化する。次に、アダマール演算部200が、各変数用レジスタにおいて、各量子ビットにアダマール変換を適用する。アダマール変換は式32で表される単一量子ビットに対する量子操作である。m個の変数用レジスタに含まれるmn個の量子ビットのそれぞれに対するアダマール変換によって、全レジスタに含まれるn個の量子ビットの重ね合わせ状態は式33で表される量子状態となる。xiは第iレジスタの量子状態を表す。次に、オラクル演算部300が、補助レジスタに対して、2次関数gに関するオラクルを実行し式18参照、補助レジスタの状態0をgに変える。既述のとおり、2次関数gに関するオラクルは事前に与えられているものである。2次関数gに関するオラクルを実行したのち、全レジスタに含まれるn個の量子ビットの重ね合わせ状態は式34で表される量子状態となる。次に、回転演算部400が、補助レジスタに対して、式35で表される量子回転操作を実行する。式35で-τ2はτ2の複素共役を表す。Zは式36で定義される。ここで記号-は、記号-の次の文字の頭上に附されることを意味し、例えば-Aは文字Aの頭上に記号-が附された組み合わせ文字を表す。式35において、○と×との組合せ記号はテンソル積を表す。量子回転操作を実行したのち、全レジスタに含まれるn個の量子ビットの重ね合わせ状態は式37で表わされる量子状態となる。次に、オラクル逆演算部500が、補助レジスタに対して、オラクル演算部300が実行したオラクルの逆操作を行い予め与えられたオラクルを実現する演算を量子回路上で逆順に実行すればよい、補助レジスタの状態を0にする。このため、各変数用レジスタと補助レジスタとのエンタングルメントがなくなるため、補助レジスタを無視してよいことになる。さらに、VF演算部600が、各変数用レジスタに対して、式21の演算VFを実行する。ただし、β1には各変数用レジスタに対応する2次関数fの係数a1a2...amが入るので、具体的には、VF演算部600は、m個の変数用レジスタに対して式38で表される演算を実行する。所与の2次関数fa1x12a2x22...amxm2mod2n1の係数aii12...mの逆元ai1が奇数であるか偶数であるかは、事前に決定できているので、第i変数用レジスタについて係数aii12...mの逆元ai1が奇数である場合には、VF演算部600は、第i変数用レジスタに対して式27に従ったユニタリ演算を実行するただし、βai1である。このユニタリ演算の量子回路は既に説明したとおりである。第i変数用レジスタについて係数aii12...mの逆元ai1が偶数である場合には、VF演算部600は、第i変数用レジスタに対して、まず式31eに従ったユニタリ演算を実行し、次いで式31dに従ったユニタリ演算を実行するただし、βai1である。式31eに従ったユニタリ演算の量子回路と式31dに従ったユニタリ演算の量子回路は既に説明したとおりである。つまり、m個の変数用レジスタに対して適用される式38の演算として、VF演算部600は、iを1からmまでの各整数を表すとして、i番目の変数用レジスタについて、2次関数fa1x12a2x22...amxm2mod2n1の係数aiの逆元ai1が奇数である場合、i番目の変数用レジスタに対して、式38aで表される演算を実行し、逆元ai1が偶数である場合、i番目の変数用レジスタに対して、tを1tβ≠0且つ1tβが2n1と互いに素であるを満たす整数として、式38bで表される演算を実行する。続いて、観測部700が全ての変数用レジスタを観測することによって、シフト量が得られる。具体例具体例として、fx123x22mod221gfとする。このときgは、双曲線fをだけ平行移動シフトした形状をしている。もし、空間上のシフト量を古典計算機によって求める場合には、複数のに対するgの値を求め、その結果からシフト量を推定する必要がある。しかし、本発明によると、シフト量を以下のようにして求めることができる。量子演算装置1は、2個の変数用レジスタと1個の補助レジスタを用いる。221を法とする剰余を求めるから、各変数用レジスタと補助レジスタはそれぞれ2個の量子ビットで構成される。従って、使用される量子ビットの数は6個である。この具体例の量子回路を図4に示す。図4に示す量子回路にてHはアダマールゲートを表し、gはオラクル演算を表し、g1はオラクル逆演算を表し、VF[1]は第1変数用レジスタに対するVF演算を表し、VF[2]は第2変数用レジスタに対するVF演算を表す。VF演算の詳細な量子回路は式27に従うので、VF[1]は例えば図5に示す量子回路で実行され221を法とする1の逆元は1である、VF[2]は例えば図6に示す量子回路で実行される221を法とする3の逆元は5である。まず、初期化部100が、全ての量子ビットを0に初期化する。そして、アダマール演算部200が、各変数用レジスタの各量子ビットに対してアダマール変換を適用する。この結果、式39で表される量子状態が得られる。次に、オラクル演算部300が、2次関数gのオラクルを実行する。この結果、式40で表される量子状態が得られる。次に、回転演算部400が、補助レジスタに対して、式41で表される量子回転操作を実行する。この結果、式42で表される量子状態が得られる。次に、オラクル逆演算部500が、2次関数gのオラクルを逆順に実行して、補助レジスタの量子状態を0にする。この結果、式43で表される量子状態が得られる。第1変数用レジスタ並びに第2変数用レジスタと補助レジスタとの間のエンタングルメントはないので、補助レジスタを無視してよい。g232mod221なので、全変数用レジスタの量子状態を正確に書くと式44である。次に、VF演算部600が、第1変数用レジスタと第2変数用レジスタのそれぞれに対して、式45、式46に対応する拡張Clifford群の変換、つまり、第1変数用レジスタに対して式45に対応する式27のユニタリ演算つまり式45aを実行し、第2変数用レジスタに対して式46に対応する式27のユニタリ演算つまり式46aを実行する。式27のユニタリ演算を実行する理由は、2次関数fx123x22mod221の係数1,3の逆元がそれぞれ奇数であるからである。既述のとおり、221を法とする3の逆元は5であるから、式46aは式46bのように展開できる。なお、QFT45QFT4であることは、式25から容易に確認できる。よって、VF1は図5の量子回路に示す演算系列によって、VF2は図6の量子回路に示す演算系列によって実行できることが分かる。なお、QFTを実行すると出力の量子ビットxは、xの順序を逆にしたものとなるため、V22SPおよびV22SP5に対応する量子回路は、図1に示す量子回路の構成と異なる演算関係を反転したような形となることに注意する。続いて、観測部700がVF演算部600による処理で得られた結果における第1変数用レジスタと第2変数用レジスタを観測する。この観測結果は21になる。なぜなら、式45、式46の複素共役転置は式47、式48で表され、式47に状態2を、式48に状態1を代入すると、第1変数用レジスタは式49で表される量子状態となり、第2変数用レジスタは式50で表される量子状態となり、オラクル逆演算部500による処理で得られた量子状態式44参照と一致するからである。量子演算装置についての概説次に、上述の量子回路に則って量子演算を行う量子演算装置について説明する。本発明の量子演算装置は、上述の量子回路から明らかなように、アダマール演算部、オラクル演算部、回転演算部、オラクル逆演算部、VF演算部を少なくとも含む。各演算部は、基本量子演算部NOT演算部、制御NOT演算部、Toffoli演算部により構成できる上記非特許文献4参照。なお、全ての演算は単一量子ビットに対する1量子ビット演算と制御NOT演算に分解できる上記非特許文献4参照。量子演算装置は、量子コンピュータ単体で実現できる。量子コンピュータの実現する物理系としては、例えば、イオントラップを用いる方法JICiracandPZollerQuantumcomputationswithcoldtrappedionsPhysicalReviewLetter7440911995、量子ビットとして光子の偏光や光路を用いる方法YNakamuraMKitagawaKIgetaIn3rdProcAsiaPacificPhysComfWorldScientificSingapore1988、液体中の各スピンを用いる方法GershenfieldChuangBulkspinresonancequantumcomputationScience2753501997、シリコン結晶中の核スピンを用いる方法BEKaneAsiliconbasednuclearspinquantumcomputerNature3931331998、量子ドット中の電子スピンを用いる方法DLossandDPDiVincenzoQuantumcomputationwithquantumdotsPhysicalReviewA571201261998、超伝導素子を用いる方法YNakamuraYuAPashkinandJSTsaiCoherentcontrolofmacroscopicquantumstatesinasinglecooperpairboxNature3937867881999等を例示できる。また、それぞれの物理系に対する量子コンピュータの実現方法については、httpwwwipagojpsecurityfy11reportcontentscryptocryptoreportQuantumComputerscontentsdocqcsurveypdfやMANielsenandILChuangQuantumComputationandQuantumInformationCambridgeUniversityPressChapter7PhysicalRealizationに詳しい。<量子ビット>イオントラップ量子コンピュータでは、例えば、イオンの基底状態と励起状態を利用して量子ビットを実現する。また、核スピンを量子ビットとして用いる場合には、例えば、TDLaddetalAllSiliconquantumcomputerPhysRevLettvol89no10179011‐0179014July12002に記載されているようにSi111基板等に各量子ビットを生成する。なお、量子ビットの初期量子状態は、例えば、他の演算の量子回路による操作によって得られたものを用いてもよいし、各量子ビットが生成された基板をmKミリケルビンオーダー以下に冷却してスピンの向きを揃えた後、所定の電磁波パルスを印加して生成してもよい。また、量子ビットとして光子の偏光を用いる場合には、例えば、パラメトリックダウンコンバージョンPDC:parametricdownconversion例えば、PGKwiatKMattleHWeinfurterAZeilingerAVSergienkoandYShihNewhighintensitysourceofpolarizationentangledphotonpairsPhysRevLett75433743411995PGKwiatEWaksAGWhiteIAppelbaumandPHEberhardUltrabrightsourceofpolarizationentangledphotonsPhysRevA60R773R7761999等参照。によって生成された複数個の単一光子を用いる。この場合、各量子ビットの初期量子状態は、例えば、他の演算の量子回路による操作によって得られたものを用いる。また、パラメトリックダウンコンバージョン等によって生成された単一光子に、ビームスプリッタや偏光回転素子等によって実現されるウォルシューアダマール変換、CNOT、回転等の操作を行い、既述の初期量子状態を生成することとしてもよい。その他、上記の文献に記載された方法で量子ビットを用意することとしてもよい。また、演算前後や演算途中において量子ビットの量子状態を保存する必要がある場合には、例えば、量子ドット内の電子準位、核スピン、あるいは超伝導体内部の電荷クーパー対量を量子ビットとして用いてデータを保存する量子メモリ等を用いてもよいABarencoDDeutschandAEkertPhysRevLett744083、松枝秀明電子情報通信学会誌AVolJ81ANo121978、THOosterkampetalNature395873、DLossandDPDiVincenzoPhysRevA57120TOshimaquantph0002004httparxivorgabsquantph0002004、BEKaneAsiliconbasednuclearspinquantumcomputerNature393133、httpwwwsnfunsweduau、YNakamuraYuAPashkinandJSTsaiNature398768。<CNOT演算>イオントラップ量子コンピュータでは、例えば、イオンを直線上に並べ、各イオンに狙いを定めたレーザービーム照射によってCNOT演算を実現する。また、量子ビットとして光子の偏光を用いる場合には、例えば、偏光ビームスプリッタ等を用い、TBPittmanMJFitchBCJacobsJDFransonExperimentalControlledNOTLogicGateforSinglePhotonsintheCoincidenceBasisquantph0303095httparxivorgabsquantph0303095記載のPittmanetal方式によってCNOT演算を実現する。また、核スピンを量子ビットとして用いる場合には、例えば、所定の電磁波パルスを量子ビットに印加することによってCNOT演算を実現できる。その他、上記の文献に記載された方法でCNOT演算を実現してもよい。<量子ビット単体操作>イオントラップ量子コンピュータでは、例えば、イオンを直線上に並べ、各イオンに狙いを定めたレーザービーム照射によって量子ビット単体の操作を実現する。核スピンを量子ビットとして用いる場合には、電磁波パルスやレーザービーム照射によって各処理を実現する。また、量子ビットとして光子の偏光を用いる場合には、例えば、偏光回転素子等によって実現する。なお、本発明は既述の実施の形態に限定されるものではなく、その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。例えば、既述の可換な演算については演算の順序に限定がない。また、量子回路に使われる全ての演算は単一量子ビットに対する1量子ビット演算と制御NOT演算に分解できるので上記非特許文献4参照、各変換部と各演算部の具体的構成についても種々等価な量子回路を構成できる。また、既述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。ところで、上述の量子回路に則って量子演算を行う手順自体は、古典コンピュータで決定することができる。上述の量子回路に則って量子演算を行う手順は、上述の量子回路を入力側から出力側に向かって順に行う各計算ステップである。具体的には、例えば図4に示した量子回路の例から明らかなように、初期状態0に対する左からの各作用に対応する量子回路を作用の順番に従って量子回路の入力側から出力側に向かって並べることで、量子回路に則って量子演算を行う手順を決定できる。ただし、1計算ステップで並行演算可能であれば、これらの演算を並行するものを1手順とすればよい。換言すれば、この古典コンピュータは、図4に示した演算手順を決定して出力するものといえる。このような古典コンピュータ、つまり、上述の量子回路における量子演算の手順を決定する量子演算手順決定装置は、いわゆる古典的な装置構成で実現される。例えばパーソナルコンピュータに例示されるように、記憶装置例えばRAM、ROMやハードディスク、演算処理装置例えばCPU、入力出力装置例えばキーボード、ディスプレイ、これらの装置間でデータのやり取りが可能に接続するバスなどを備えた古典コンピュータによって実現することができる。この場合、例えば図4の例のように、初期状態0に対する左からの各作用に対応する量子回路における量子演算の手順をそれぞれ決定するための各プログラム、決定された手順を上記作用の順番に従って量子回路の入力側から出力側へ並べるためのプログラムを記憶装置に記憶しておき、必要に応じて演算処理装置がプログラムを読み込んで解釈実行することで、初期状態0に対する左からの各作用に対応する量子回路における量子演算の手順をそれぞれ決定する各機能、決定された手順を上記作用の順番に従って量子回路の入力側から出力側へ並べる機能を実現する。また各プログラムは、コンピュータ読み取り可能な記録媒体例えばCD-R、DVD-RAM、MOに記録することもできる。"