JP2008052365A - 近似量子フーリエ変換を行う量子回路、近似量子フーリエ変換演算方法および装置 - Google Patents
近似量子フーリエ変換を行う量子回路、近似量子フーリエ変換演算方法および装置 Download PDFInfo
- Publication number
- JP2008052365A JP2008052365A JP2006225709A JP2006225709A JP2008052365A JP 2008052365 A JP2008052365 A JP 2008052365A JP 2006225709 A JP2006225709 A JP 2006225709A JP 2006225709 A JP2006225709 A JP 2006225709A JP 2008052365 A JP2008052365 A JP 2008052365A
- Authority
- JP
- Japan
- Prior art keywords
- quantum
- bits
- performs
- swap
- bit
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Images
Landscapes
- Complex Calculations (AREA)
Abstract
【課題】Ｏ(ｎ)個の計算ステップ数でありながら、従来よりも少ないオーダの基本演算の個数で近似量子フーリエ変換を実現する。
【解決手段】自己相似的に分解構成された、近傍２量子ビット演算を用いた近似でない量子フーリエ変換の量子回路と、近傍２量子ビット演算を用いた近似でない量子フーリエ変換の従来的量子回路に基づいて、２ｎを法とする近似量子フーリエ変換を行う量子回路を構成する。この量子回路は、２ｍ〔ｍは近似の閾値〕以下の数を法とする量子フーリエ変換を行う量子回路から構成されるようになるまで自己相似的に分解して構成される。２ｍ以下の数を法とする量子フーリエ変換を行う量子回路は、近傍２量子ビット演算を用いた近似でない量子フーリエ変換を行う従来的な量子回路として構成される。
【選択図】図２２
【解決手段】自己相似的に分解構成された、近傍２量子ビット演算を用いた近似でない量子フーリエ変換の量子回路と、近傍２量子ビット演算を用いた近似でない量子フーリエ変換の従来的量子回路に基づいて、２ｎを法とする近似量子フーリエ変換を行う量子回路を構成する。この量子回路は、２ｍ〔ｍは近似の閾値〕以下の数を法とする量子フーリエ変換を行う量子回路から構成されるようになるまで自己相似的に分解して構成される。２ｍ以下の数を法とする量子フーリエ変換を行う量子回路は、近傍２量子ビット演算を用いた近似でない量子フーリエ変換を行う従来的な量子回路として構成される。
【選択図】図２２
Description
本発明は、近似量子フーリエ変換を行う量子回路、近似量子フーリエ変換の演算方法と演算装置に関する。より詳しくは、１量子ビット演算および近傍２量子ビット演算だけで構成された近似量子フーリエ変換を行う量子回路、演算方法、演算装置に関する。
まず、量子フーリエ変換（quantum Fourier transform）について説明し、ついで、近傍２量子ビット演算（linear nearest neighbor quantum bit operation）で構成された近似でない量子フーリエ変換の量子回路について説明し、さらに、単一量子ビットに対する１量子ビット演算および隣り合う量子ビット間の量子ビット演算である近傍２量子ビット演算だけで構成された近似量子フーリエ変換（approximate quantum Fourier transform）の量子回路について説明する。
なお、本明細書では、計算量の評価をＯ記法に従って記す。
なお、本明細書では、計算量の評価をＯ記法に従って記す。
＜量子フーリエ変換ＱＦＴ＞
量子フーリエ変換については例えば非特許文献１に詳しい。ここでは、量子フーリエ変換について概説する。
量子ビット〔quantum bit;以下、ｑビット（qubit）とも云う。〕の正規直交系をなす基底状態である正規直交基底|０〉，|１〉，…，|Ｎ−１〉上の量子フーリエ変換は、基底状態に式（１）の作用をする線形オペレータとして定義される。ここでｑビットの状態は、複素ベクトル空間のベクトルであり、計算基底状態（computational basis state）である。式（１）においてｉは虚数単位（imaginary unit）であり、ｅはネピア数（Napier's constant;自然対数の底）である。なお、本明細書では、ネピア数ｅのｐ乗をexp(ｐ)の如く表す場合がある。
量子フーリエ変換については例えば非特許文献１に詳しい。ここでは、量子フーリエ変換について概説する。
量子ビット〔quantum bit;以下、ｑビット（qubit）とも云う。〕の正規直交系をなす基底状態である正規直交基底|０〉，|１〉，…，|Ｎ−１〉上の量子フーリエ変換は、基底状態に式（１）の作用をする線形オペレータとして定義される。ここでｑビットの状態は、複素ベクトル空間のベクトルであり、計算基底状態（computational basis state）である。式（１）においてｉは虚数単位（imaginary unit）であり、ｅはネピア数（Napier's constant;自然対数の底）である。なお、本明細書では、ネピア数ｅのｐ乗をexp(ｐ)の如く表す場合がある。
ここでＮ＝２ｎ、ｎは１以上の整数〔正整数〕とし、基底|０〉，|１〉，…，|２ｎ−１〉はｎ個のｑビットの量子コンピュータに対する計算基底状態とする。状態|ｂ〉を２進数表現でｂ＝ｂｎ−１ｂｎ−２…ｂ１ｂ０と書くとする。１０進数表現では、ｂ＝ｂｎ−１２ｎ−１＋ｂｎ−２２ｎ−２＋…＋ｂ１２１＋ｂ０２０となる。２進少数表現を式（２）で定義する。なお、状態|ｖ〉，|ｗ〉のテンソル積を|ｖ〉|ｗ〉、|ｖ，ｗ〉、|ｖｗ〉などと表記する。
このとき、式（１）と式（３）は等価である。式（３）は、２ｎを法とする量子フーリエ変換の積表現である。以下、断りのない限り、量子フーリエ変換は、近似量子フーリエ変換または近似でない量子フーリエ変換を問わず、２の冪乗の数を法とする量子フーリエ変換であるとする。
式（３）で表される効率的な量子フーリエ変換を行う量子回路を、ｎ＝８の場合を例として図１に示す。一般的に量子回路では単一ｑビットに対する１量子ビット演算とＣＮＯＴ（controlled-NOT）を基本演算とするが、量子回路が複雑になるのを避けるため、本明細書ではこれらの演算以外の演算も用いて量子回路を構成するものとして説明する。量子回路に使われる全ての演算は、単一ｑビットに対する１量子ビット演算とＣＮＯＴに分解できることに注意しなければならない〔非特許文献１参照〕。ＣＮＯＴは、２つの入力ｑビットに対する２量子ビット演算である。
なお、非特許文献１では、図１に示される量子回路の最後の状態に対して交換操作を行ってｑビットの状態を反転させたものを、量子フーリエ変換を行う量子回路として説明しているが、本明細書では、上記交換操作を行わない図１に示される量子回路をもって量子フーリエ変換の量子回路とする。これは、テンソル積で表される式（３）の表現の違いに基づくに過ぎない。
なお、非特許文献１では、図１に示される量子回路の最後の状態に対して交換操作を行ってｑビットの状態を反転させたものを、量子フーリエ変換を行う量子回路として説明しているが、本明細書では、上記交換操作を行わない図１に示される量子回路をもって量子フーリエ変換の量子回路とする。これは、テンソル積で表される式（３）の表現の違いに基づくに過ぎない。
ｎ＝８の場合の量子フーリエ変換ＱＦＴ８は、入力状態|ｂ７ｂ６…ｂ１ｂ０〉に対して、出力状態(|０〉＋exp(２πｉ０．ｂ７ｂ６…ｂ１ｂ０)|１〉)( |０〉＋exp(２πｉ０．ｂ６…ｂ１ｂ０)|１〉)…(|０〉＋exp(２πｉ０．ｂ０)|１〉)／２ｎ／２を得る。図１は、入力状態と出力状態とを単一ｑビットごとの配線（wire）に分解して表したＱＦＴ８の量子回路を示している。図１において出力状態|φｋ(ｂ)〉は、|φｋ(ｂ)〉＝(|０〉＋exp(２πｉΣｍ＝０ ｋ(ｂｋ−ｍ／２ｍ＋１))|１〉)／２１／２で表せる。但し、ｋ＝０，１，２，３，４，５，６，７である。
図１に現われる量子ゲートについて概説する。図１において、記号Ｈで表される量子ゲートはアダマールゲート（Hadamard gate）であり、アダマール変換が行われる。ｑビットの入力状態|ｘ〉をアダマールゲートに通すと、出力状態(|０〉＋（−１）ｘ|１〉)／２１／２が得られる〔図２参照〕。出力状態は、(|０〉＋ｅ２πｉ０．ｘ|１〉)／２１／２とも表せる。
図１において、数字ｔ＝２，３，４，５，６，７，８で表される量子ゲートは制御フェイズシフトゲート（controlled phase shift gate）であり、式（４）で示す行列で表されるユニタリー変換が行われる。２つのｑビットの入力状態|ｘ〉および|ｙ〉を制御フェイズシフトゲートに通すと、出力状態exp(２πｉｘｙ／２ｔ)|ｘ〉|ｙ〉が得られる〔図３参照〕。制御フェイズシフトゲートは、角度２π／２ｔの回転ゲートであり、以下では、数字ｔで表される制御フェイズシフトゲートの作用を、角度２π／２ｔの制御フェイズシフトと云うこともある。図３は、入力状態と出力状態とを単一ｑビットごとの配線に分解して表した量子回路を示している。なお、図３に示される制御フェイズシフトゲートは、図４に示される制御フェイズシフトゲートと等価であることに注意しなければならない。
＜近傍２量子ビット演算で構成された近似でない量子フーリエ変換ＬＮＮ−ＱＦＴの量子回路＞
図１に示したＱＦＴ８の量子回路では、例えば最初の８個の計算ステップをみると、入力状態|ｂ７ｂ６…ｂ１ｂ０〉に対して、まず、最初の計算ステップで状態|ｂ７〉にアダマール変換を作用させ、この作用で得られた中間状態(|０〉＋exp(２πｉ０．ｂ７)|１〉)／２１／２|ｂ６…ｂ１ｂ０〉に次の計算ステップで状態|ｂ６〉に基づく制御フェイズシフトを作用させ、この作用で得られた中間状態(|０〉＋exp(２πｉ０．ｂ７ｂ６)|１〉)／２１／２|ｂ６…ｂ１ｂ０〉に次の計算ステップで状態|ｂ５〉に基づく制御フェイズシフトを作用させ、この作用で得られた中間状態(|０〉＋exp(２πｉ０．ｂ７ｂ６ｂ５)|１〉)／２１／２|ｂ６…ｂ１ｂ０〉に次の計算ステップで状態|ｂ４〉に基づく制御フェイズシフトを作用させ、・・・中略・・・、この作用で得られた中間状態(|０〉＋exp(２πｉ０．ｂ７ｂ６ｂ５ｂ４ｂ３ｂ２ｂ１)|１〉)／２１／２|ｂ６…ｂ１ｂ０〉に次の計算ステップで状態|ｂ０〉に基づく制御フェイズシフトを作用させる、といった処理が行われる。
図１に示したＱＦＴ８の量子回路では、例えば最初の８個の計算ステップをみると、入力状態|ｂ７ｂ６…ｂ１ｂ０〉に対して、まず、最初の計算ステップで状態|ｂ７〉にアダマール変換を作用させ、この作用で得られた中間状態(|０〉＋exp(２πｉ０．ｂ７)|１〉)／２１／２|ｂ６…ｂ１ｂ０〉に次の計算ステップで状態|ｂ６〉に基づく制御フェイズシフトを作用させ、この作用で得られた中間状態(|０〉＋exp(２πｉ０．ｂ７ｂ６)|１〉)／２１／２|ｂ６…ｂ１ｂ０〉に次の計算ステップで状態|ｂ５〉に基づく制御フェイズシフトを作用させ、この作用で得られた中間状態(|０〉＋exp(２πｉ０．ｂ７ｂ６ｂ５)|１〉)／２１／２|ｂ６…ｂ１ｂ０〉に次の計算ステップで状態|ｂ４〉に基づく制御フェイズシフトを作用させ、・・・中略・・・、この作用で得られた中間状態(|０〉＋exp(２πｉ０．ｂ７ｂ６ｂ５ｂ４ｂ３ｂ２ｂ１)|１〉)／２１／２|ｂ６…ｂ１ｂ０〉に次の計算ステップで状態|ｂ０〉に基づく制御フェイズシフトを作用させる、といった処理が行われる。
ここに明らかなように、直前の中間状態に制御フェイズシフトを作用させると、例えば最初の８個の計算ステップでは、その度に、状態|ｂ７〉に基づいた状態|１〉の係数の位相に、制御フェイズシフトの標的ｑビット〔あるいは、制御ｑビットと言っても同様である（図４参照）。〕に相当する追加ビットが加わる。より一般的に、計算理論上は、このような演算に格別の問題は無いが、ｑビットの状態が物理的な状態であるところ、隣り合うｑビットよりも離れたｑビットに基づく作用を受けるとすると、一般的に演算誤りのリスクが高まる。そこで、隣り合う量子ビット間の量子ビット演算である近傍２量子ビット演算で量子フーリエ変換を行う量子回路を構成することが提案されている〔非特許文献２参照〕。
ここでは、近傍２量子ビット演算で構成された近似でない量子フーリエ変換の量子回路について概説する。
近傍２量子ビット演算で構成された近似でない量子フーリエ変換の量子回路は、式（３）で表される効率的な量子フーリエ変換を行う量子回路に適宜にＳＷＡＰ（swap operation; 交換演算）を施すことで得られる。ｎ＝８の場合を例として、図１に示したＱＦＴ８の量子回路を基にした、近傍２量子ビット演算で構成した近似でない量子フーリエ変換ＬＮＮ−ＱＦＴ８の量子回路を図５に示す。図５で使われているＳＷＡＰの量子回路を、図６に示す。ＳＷＡＰの量子回路は、入力された２つのｑビットの状態を交換する。図６に示したＳＷＡＰの量子回路には、３個のＣＮＯＴが使われている。ＣＮＯＴの量子回路を、図７に示す。ＣＮＯＴの量子回路は、最も基本的な２量子ビット演算を行ない、この意味でＣＮＯＴゲートと呼ばれる。ＣＮＯＴゲートは、古典的ＸＯＲゲートに対応しており、制御ｑビットの状態|ｘ〉に応じて、標的ｑビットの状態|ｙ〉に変更をもたらす。２準位系で簡潔に説明すれば、制御ｑビットの状態が|０〉であれば、標的ｑビットの状態|ｙ〉に変更をもたらさず、制御ｑビットの状態が|１〉であれば、標的ｑビットの状態|ｙ〉を反転させる。
近傍２量子ビット演算で構成された近似でない量子フーリエ変換の量子回路は、式（３）で表される効率的な量子フーリエ変換を行う量子回路に適宜にＳＷＡＰ（swap operation; 交換演算）を施すことで得られる。ｎ＝８の場合を例として、図１に示したＱＦＴ８の量子回路を基にした、近傍２量子ビット演算で構成した近似でない量子フーリエ変換ＬＮＮ−ＱＦＴ８の量子回路を図５に示す。図５で使われているＳＷＡＰの量子回路を、図６に示す。ＳＷＡＰの量子回路は、入力された２つのｑビットの状態を交換する。図６に示したＳＷＡＰの量子回路には、３個のＣＮＯＴが使われている。ＣＮＯＴの量子回路を、図７に示す。ＣＮＯＴの量子回路は、最も基本的な２量子ビット演算を行ない、この意味でＣＮＯＴゲートと呼ばれる。ＣＮＯＴゲートは、古典的ＸＯＲゲートに対応しており、制御ｑビットの状態|ｘ〉に応じて、標的ｑビットの状態|ｙ〉に変更をもたらす。２準位系で簡潔に説明すれば、制御ｑビットの状態が|０〉であれば、標的ｑビットの状態|ｙ〉に変更をもたらさず、制御ｑビットの状態が|１〉であれば、標的ｑビットの状態|ｙ〉を反転させる。
図５に示すＬＮＮ−ＱＦＴ８の量子回路では、ＩＮＶ（inverse operation; 交換操作）が各ｑビットの状態に対して施される。ＩＮＶの量子回路を、図８に示す。図８では、ｑビットの入力状態|ｂｓ＝７，６，…，０〉と混同しないように、状態を記号|ａｓ＝７，６，…，０〉で表している。以下、入力状態|ｂｓ〉と区別して状態を一般的に表したい場合には、記号|ａｓ〉を用いる。
ＩＮＶの量子回路は、入力ｑビットの状態の並びを逆順で並び替えて出力するものであり、この意味でＩＮＶゲートと呼ぶことにする。なお、近傍２量子ビット間でのＳＷＡＰだけで構成しないものとすれば、Ｏ(ｎ／２)程度のＳＷＡＰ回数となるようにＩＮＶの量子回路を構成できるが、図８では、近傍２量子ビット間でのＳＷＡＰだけで構成したＩＮＶの量子回路を示している。出力状態の順序を図１に示す量子回路の出力状態と同じにするために、図５に示すＬＮＮ−ＱＦＴ８の量子回路ではＩＮＶゲートを使っている。ＩＮＶゲートを用いたＬＮＮ−ＱＦＴ８の量子回路における計算ステップ数と基本演算の個数は、ＩＮＶゲートを用いないＱＦＴ８の量子回路のそれらと比較して、同じ程度のオーダで済む。一般に、ＩＮＶゲートを用いたことによっても、ＬＮＮ−ＱＦＴの量子回路が、ＱＦＴの量子回路に比して非効率的になっているのではないことに注意しなければならない。
ＩＮＶの量子回路は、入力ｑビットの状態の並びを逆順で並び替えて出力するものであり、この意味でＩＮＶゲートと呼ぶことにする。なお、近傍２量子ビット間でのＳＷＡＰだけで構成しないものとすれば、Ｏ(ｎ／２)程度のＳＷＡＰ回数となるようにＩＮＶの量子回路を構成できるが、図８では、近傍２量子ビット間でのＳＷＡＰだけで構成したＩＮＶの量子回路を示している。出力状態の順序を図１に示す量子回路の出力状態と同じにするために、図５に示すＬＮＮ−ＱＦＴ８の量子回路ではＩＮＶゲートを使っている。ＩＮＶゲートを用いたＬＮＮ−ＱＦＴ８の量子回路における計算ステップ数と基本演算の個数は、ＩＮＶゲートを用いないＱＦＴ８の量子回路のそれらと比較して、同じ程度のオーダで済む。一般に、ＩＮＶゲートを用いたことによっても、ＬＮＮ−ＱＦＴの量子回路が、ＱＦＴの量子回路に比して非効率的になっているのではないことに注意しなければならない。
近傍２量子ビット演算で構成された近似でない量子フーリエ変換ＬＮＮ−ＱＦＴの量子回路（３）の構成方法を示しておく。
量子回路（３）へ入力されるｎ個のｑビットの状態を|ｂｎ−１〉，…，|ｂ０〉とし、それぞれのｑビットを順に第１-ｑビット、…、第ｎ-ｑビットと云うことにする。つまり、最上位の配線に相当するｑビットを第１-ｑビットとし、最下位の配線に相当するｑビットを第ｎ-ｑビットとする。また、記載の便宜から、第(・)-ｑビットなどとも記載する。
量子回路（３）へ入力されるｎ個のｑビットの状態を|ｂｎ−１〉，…，|ｂ０〉とし、それぞれのｑビットを順に第１-ｑビット、…、第ｎ-ｑビットと云うことにする。つまり、最上位の配線に相当するｑビットを第１-ｑビットとし、最下位の配線に相当するｑビットを第ｎ-ｑビットとする。また、記載の便宜から、第(・)-ｑビットなどとも記載する。
《１》 ｇ＝１，…，ｎについて、順に、次の演算を行う量子回路とする。
[ｇ＝１の場合]
第１-ｑビットにアダマール変換を適用する。
[ｇが３以上の奇数の場合]
第１-ｑビットにアダマール変換を適用する。第(ｊ−１)-ｑビットと第ｊ-ｑビットに角度２π／２ｊの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。ただし、ｊは３からｇまでの奇数とし、ｇごとにアダマール変換および全てのｊについての演算を並列に行う。
[ｇが偶数の場合]
第(ｊ−１)-ｑビットと第ｊ-ｑビットに角度２π／２ｊの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。ただし、ｊは２からｇまでの偶数とし、ｇごとに全てのｊについての演算を並列に行う。
《２》 ｇ＝ｎ−１，…，１について、順に、次の演算を行う量子回路とする。
[ｇ＝１の場合]
第１-ｑビットにアダマール変換を適用する。
[ｇが３以上の奇数の場合]
第１-ｑビットにアダマール変換を適用する。第(ｊ−１)-ｑビットと第ｊ-ｑビットに角度２π／２ｊの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。ただし、ｊは３からｇまでの奇数とし、ｇごとにアダマール変換および全てのｊについての演算を並列に行う。
[ｇが偶数の場合]
第(ｊ−１)-ｑビットと第ｊ-ｑビットに角度２π／２ｊの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。ただし、ｊは２からｇまでの偶数とし、ｇごとに全てのｊについての演算を並列に行う。
《３》 ｇ＝１，…，ｎ−１について、順に、次の演算を行う量子回路とする。
[ｇが奇数の場合]
第ｊ-ｑビットと第(ｊ＋１)-ｑビットにＳＷＡＰを適用する。ただし、ｊは１からｇまでの奇数とし、ｇごとに全てのｊについてのＳＷＡＰを並列に行う。
[ｇが偶数の場合]
第ｊ-ｑビットと第(ｊ＋１)-ｑビットにＳＷＡＰを適用する。ただし、ｊは２からｇまでの偶数とし、ｇごとに全てのｊについてのＳＷＡＰを並列に行う。
《４》 ｇ＝ｎ−２，…，１について、順に、次の演算を行う量子回路とする。
[ｇが奇数の場合]
第ｊ-ｑビットと第(ｊ＋１)-ｑビットにＳＷＡＰを適用する。ただし、ｊは１からｇまでの奇数とし、ｇごとに全てのｊについてのＳＷＡＰを並列に行う。
[ｇが偶数の場合]
第ｊ-ｑビットと第(ｊ＋１)-ｑビットにＳＷＡＰを適用する。ただし、ｊは２からｇまでの偶数とし、ｇごとに全てのｊについてのＳＷＡＰを並列に行う。
[ｇ＝１の場合]
第１-ｑビットにアダマール変換を適用する。
[ｇが３以上の奇数の場合]
第１-ｑビットにアダマール変換を適用する。第(ｊ−１)-ｑビットと第ｊ-ｑビットに角度２π／２ｊの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。ただし、ｊは３からｇまでの奇数とし、ｇごとにアダマール変換および全てのｊについての演算を並列に行う。
[ｇが偶数の場合]
第(ｊ−１)-ｑビットと第ｊ-ｑビットに角度２π／２ｊの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。ただし、ｊは２からｇまでの偶数とし、ｇごとに全てのｊについての演算を並列に行う。
《２》 ｇ＝ｎ−１，…，１について、順に、次の演算を行う量子回路とする。
[ｇ＝１の場合]
第１-ｑビットにアダマール変換を適用する。
[ｇが３以上の奇数の場合]
第１-ｑビットにアダマール変換を適用する。第(ｊ−１)-ｑビットと第ｊ-ｑビットに角度２π／２ｊの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。ただし、ｊは３からｇまでの奇数とし、ｇごとにアダマール変換および全てのｊについての演算を並列に行う。
[ｇが偶数の場合]
第(ｊ−１)-ｑビットと第ｊ-ｑビットに角度２π／２ｊの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。ただし、ｊは２からｇまでの偶数とし、ｇごとに全てのｊについての演算を並列に行う。
《３》 ｇ＝１，…，ｎ−１について、順に、次の演算を行う量子回路とする。
[ｇが奇数の場合]
第ｊ-ｑビットと第(ｊ＋１)-ｑビットにＳＷＡＰを適用する。ただし、ｊは１からｇまでの奇数とし、ｇごとに全てのｊについてのＳＷＡＰを並列に行う。
[ｇが偶数の場合]
第ｊ-ｑビットと第(ｊ＋１)-ｑビットにＳＷＡＰを適用する。ただし、ｊは２からｇまでの偶数とし、ｇごとに全てのｊについてのＳＷＡＰを並列に行う。
《４》 ｇ＝ｎ−２，…，１について、順に、次の演算を行う量子回路とする。
[ｇが奇数の場合]
第ｊ-ｑビットと第(ｊ＋１)-ｑビットにＳＷＡＰを適用する。ただし、ｊは１からｇまでの奇数とし、ｇごとに全てのｊについてのＳＷＡＰを並列に行う。
[ｇが偶数の場合]
第ｊ-ｑビットと第(ｊ＋１)-ｑビットにＳＷＡＰを適用する。ただし、ｊは２からｇまでの偶数とし、ｇごとに全てのｊについてのＳＷＡＰを並列に行う。
＜１量子ビット演算および近傍２量子ビット演算だけで構成された近似量子フーリエ変換ＬＮＮ−ＡＱＦＴの量子回路＞
近似の閾値がｍである近似量子フーリエ変換を行う量子回路は、２ｎを法とする近似でない量子フーリエ変換を行う量子回路において、ｔ＞ｍを満たす制御フェイズシフトを恒等変換とみなした量子回路である〔ここでｔは、制御フェイズシフトゲートの数字に対応する。〕。なお、ｍはｎよりも小さい正整数である。
近傍２量子ビット演算で構成された近似でない量子フーリエ変換の量子回路でも同様であり、近似の閾値より大きい数字ｔで表される制御フェイズシフトを恒等変換とみなす。これによって得られた量子回路が、１量子ビット演算および近傍２量子ビット演算だけで構成された近似量子フーリエ変換の量子回路である〔非特許文献３参照〕。ｎ＝８の場合を例として、図５に示したＬＮＮ−ＱＦＴ８の量子回路を基にした、１量子ビット演算および近傍２量子ビット演算だけで構成された近似量子フーリエ変換ＬＮＮ−ＡＱＦＴ８の量子回路を図９に示す。図９に示したＬＮＮ−ＡＱＦＴ８の量子回路は、近似の閾値ｍが５の場合を示している。量子フーリエ変換の近似の閾値は、下限がＯ(logｎ)とされる〔非特許文献３参照〕。なお、図９において出力状態|φｋ(ｂ)〉は、|φｋ(ｂ)〉＝(|０〉＋exp(２πｉΣｍ＝０ ４(ｂｋ−ｍ／２ｍ＋１))|１〉)／２１／２〔但し、ｋ＝５，６，７〕、|φｋ(ｂ)〉＝(|０〉＋exp(２πｉΣｍ＝０ ｋ(ｂｋ−ｍ／２ｍ＋１))|１〉)／２１／２〔但し、ｋ＝０，１，２，３，４〕で表せる。
このような近似量子フーリエ変換を行う量子回路における計算ステップ数と基本演算の個数は、ＬＮＮ−ＱＦＴの量子回路やＱＦＴの量子回路におけるそれらと比較して、同じ程度のオーダとなっている。
近似の閾値がｍである近似量子フーリエ変換を行う量子回路は、２ｎを法とする近似でない量子フーリエ変換を行う量子回路において、ｔ＞ｍを満たす制御フェイズシフトを恒等変換とみなした量子回路である〔ここでｔは、制御フェイズシフトゲートの数字に対応する。〕。なお、ｍはｎよりも小さい正整数である。
近傍２量子ビット演算で構成された近似でない量子フーリエ変換の量子回路でも同様であり、近似の閾値より大きい数字ｔで表される制御フェイズシフトを恒等変換とみなす。これによって得られた量子回路が、１量子ビット演算および近傍２量子ビット演算だけで構成された近似量子フーリエ変換の量子回路である〔非特許文献３参照〕。ｎ＝８の場合を例として、図５に示したＬＮＮ−ＱＦＴ８の量子回路を基にした、１量子ビット演算および近傍２量子ビット演算だけで構成された近似量子フーリエ変換ＬＮＮ−ＡＱＦＴ８の量子回路を図９に示す。図９に示したＬＮＮ−ＡＱＦＴ８の量子回路は、近似の閾値ｍが５の場合を示している。量子フーリエ変換の近似の閾値は、下限がＯ(logｎ)とされる〔非特許文献３参照〕。なお、図９において出力状態|φｋ(ｂ)〉は、|φｋ(ｂ)〉＝(|０〉＋exp(２πｉΣｍ＝０ ４(ｂｋ−ｍ／２ｍ＋１))|１〉)／２１／２〔但し、ｋ＝５，６，７〕、|φｋ(ｂ)〉＝(|０〉＋exp(２πｉΣｍ＝０ ｋ(ｂｋ−ｍ／２ｍ＋１))|１〉)／２１／２〔但し、ｋ＝０，１，２，３，４〕で表せる。
このような近似量子フーリエ変換を行う量子回路における計算ステップ数と基本演算の個数は、ＬＮＮ−ＱＦＴの量子回路やＱＦＴの量子回路におけるそれらと比較して、同じ程度のオーダとなっている。
ここでの説明は、ｎ＝８の場合、つまり８ｑビットの場合で説明したが、一般のｎ-ｑビットの場合に拡張できる〔８ｑビット未満の場合は、８ｑビットの場合に内包されている。〕。
M. A. Nielsen and I. L. Chuang, "Quantum Computation and Quantum Information", Cambridge University Press, 2000. A. G. Fowler, S. J. Devitt, and L. C. L. Hollenberg, "Implementation of Shor’s algorithm on a linear nearest neighbour qubit array", Quantum Information and Computation, Vol.4, No.4, pp.237-251, 2004. D. Coppersmith, "An approximate Fourier transform useful in quantum factoring", Technical Report RC19642, IBM, 1994.
M. A. Nielsen and I. L. Chuang, "Quantum Computation and Quantum Information", Cambridge University Press, 2000. A. G. Fowler, S. J. Devitt, and L. C. L. Hollenberg, "Implementation of Shor’s algorithm on a linear nearest neighbour qubit array", Quantum Information and Computation, Vol.4, No.4, pp.237-251, 2004. D. Coppersmith, "An approximate Fourier transform useful in quantum factoring", Technical Report RC19642, IBM, 1994.
以上に説明した近似量子フーリエ変換の従来の量子回路は、近似の閾値をＯ(logｎ)とし、単一量子ビットに対する１量子ビット演算と近傍２量子ビット演算だけを使うとき、Ｏ(ｎ)個の計算ステップ数（depth）およびＯ(ｎ２)個の基本演算（size）を用いて近似量子フーリエ変換を実現する。
ところで、基本演算の個数が多いほど演算誤りが発生する可能性が大きくなるため、基本演算の個数はできるだけ少ないほうが良い。また、少ない計算時間のためには計算ステップ数は少ない方がよい。
そこで本発明は、Ｏ(ｎ)個の計算ステップ数でありながら、従来よりも少ないオーダの基本演算の個数で実現する、１量子ビット演算および近傍２量子ビット演算だけで構成された近似量子フーリエ変換を行う量子回路、近似量子フーリエ変換演算方法と演算装置を提供することを目的とする。
上記課題を解決するために、本発明の量子回路は、次のような構成とされる。即ち、近似の閾値を正整数ｎよりも小さい正整数ｍとし、２ｎを法とする近似量子フーリエ変換を行う量子回路であって、ｎ個のｑビットである第１-ｑビット、…、第ｎ-ｑビットに対して、ｎが偶数の場合、《１》第１-ｑビットから第(ｎ／２)-ｑビットまでについて、近傍２量子ビット演算で構成した２ｎ／２を法とする量子フーリエ変換を行う量子回路を構成し、《２》ｇ＝２，…，ｎ／２＋１について、順に、第(ｎ／２−ｇ＋２ｊ)-ｑビットと第(ｎ／２−ｇ＋２ｊ＋１)-ｑビットに角度２π／２ｇの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する演算を行う量子回路を構成し〔ただし、ｊ＝１，…，ｇ−１とし、ｇごとに全てのｊについての演算を並列に行う量子回路とする。〕、《３》ｇ＝ｎ／２＋２，…，ｎについて、順に、第(ｇ−ｎ／２＋２ｊ−２)-ｑビットと第(ｇ−ｎ／２＋２ｊ−１)-ｑビットに角度２π／２ｇの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する演算を行う量子回路を構成し〔ただし、ｊ＝１，…，ｎ＋１−ｇとし、ｇごとに全てのｊについての演算を並列に行う量子回路とする。〕、《４》ｇ＝ｎ，…，ｎ／２＋２について、順に、第(ｇ−ｎ／２＋２ｊ−２)-ｑビットと第(ｇ−ｎ／２＋２ｊ−１)-ｑビットにＳＷＡＰを適用する演算を行うＳＷＡＰ量子回路を構成し〔ただし、ｊ＝１，…，ｎ＋１−ｇとし、ｇごとに全てのｊについての演算を並列に行う量子回路とする。〕、《５》ｇ＝ｎ／２＋１，…，２について、順に、第(ｎ／２−ｇ＋２ｊ)-ｑビットと第(ｎ／２−ｇ＋２ｊ＋１)-ｑビットにＳＷＡＰを適用する演算を行うＳＷＡＰ量子回路を構成し〔ただし、ｊ＝１，…，ｇ−１とし、ｇごとに全てのｊについての演算を並列に行う量子回路とする。〕、《６》第(ｎ／２＋１)-ｑビットから第ｎ-ｑビットまでについて、近傍２量子ビット演算で構成した２ｎ／２を法とする量子フーリエ変換を行う量子回路を構成し、ｎが奇数の場合、パターン１またはパターン２のいずれかで、（パターン１）《１》第１-ｑビットから第((ｎ＋１)／２)-ｑビットまでについて、近傍２量子ビット演算で構成した２(ｎ＋１)／２を法とする量子フーリエ変換を行う量子回路を構成し、《２》ｇ＝２，…，(ｎ＋１)／２について、順に、第((ｎ＋１)／２−ｇ＋２ｊ)-ｑビットと第((ｎ＋１)／２−ｇ＋２ｊ＋１)-ｑビットに角度２π／２ｇの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する演算を行う量子回路を構成し〔ただし、ｊ＝１，…，ｇ−１とし、ｇごとに全てのｊについての演算を並列に行う量子回路とする。〕、《３》ｇ＝(ｎ＋１)／２＋１，…，ｎについて、順に、第(ｇ−(ｎ＋１)／２＋２ｊ−２)-ｑビットと第(ｇ−(ｎ＋１)／２＋２ｊ−１)ビットに角度２π／２ｇの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する演算を行う量子回路を構成し〔ただし、ｊ＝１，…，ｎ＋１−ｇとし、ｇごとに全てのｊについての演算を並列に行う量子回路とする。〕、《４》ｇ＝ｎ，…，(ｎ＋１)／２＋１について、順に、第(ｇ−(ｎ＋１)／２＋２ｊ−２)-ｑビットと第(ｇ−(ｎ＋１)／２＋２ｊ−１)-ｑビットにＳＷＡＰを適用する演算を行うＳＷＡＰ量子回路を構成し〔ただし、ｊ＝１，…，ｎ＋１−ｇとし、ｇごとに全てのｊについての演算を並列に行う量子回路とする。〕、
《５》ｇ＝(ｎ＋１)／２，…，２について、順に、第((ｎ＋１)／２−ｇ＋２ｊ)-ｑビットと第((ｎ＋１)／２−ｇ＋２ｊ＋１)-ｑビットにＳＷＡＰを適用する演算を行うＳＷＡＰ量子回路を構成し〔ただし、ｊ＝１，…，ｇ−１とし、ｇごとに全てのｊについての演算を並列に行う量子回路とする。〕、《６》第((ｎ＋１)／２＋１)-ｑビットから第ｎ-ｑビットまでについて、近傍２量子ビット演算で構成した２ (ｎ−１)／２を法とする量子フーリエ変換を行う量子回路を構成し、（パターン２）《１》第１-ｑビットから第((ｎ−１)／２)-ｑビットまでについて、近傍２量子ビット演算で構成した２(ｎ−１)／２を法とする量子フーリエ変換を行う量子回路を構成し、《２》ｇ＝２，…，(ｎ＋１)／２について、順に、第((ｎ＋１)／２−ｇ＋２ｊ−１)-ｑビットと第((ｎ＋１)／２−ｇ＋２ｊ)-ｑビットに角度２π／２ｇの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する演算を行う量子回路を構成し〔ただし、ｊ＝１，…，ｇ−１とし、ｇごとに全てのｊについての演算を並列に行う量子回路とする。〕、《３》ｇ＝(ｎ＋１)／２＋１，…，ｎについて、順に、第(ｇ−(ｎ＋１)／２＋２ｊ−１)-ｑビットと第(ｇ−(ｎ＋１)／２＋２ｊ)ビットに角度２π／２ｇの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する演算を行う量子回路を構成し〔ただし、ｊ＝１，…，ｎ＋１−ｇとし、ｇごとに全てのｊについての演算を並列に行う量子回路とする。〕、《４》ｇ＝ｎ，…，(ｎ＋１)／２＋１について、順に、第(ｇ−(ｎ＋１)／２＋２ｊ−１)-ｑビットと第(ｇ−(ｎ＋１)／２＋２ｊ)-ｑビットにＳＷＡＰを適用する演算を行うＳＷＡＰ量子回路を構成し〔ただし、ｊ＝１，…，ｎ＋１−ｇとし、ｇごとに全てのｊについての演算を並列に行う量子回路とする。〕、《５》ｇ＝(ｎ＋１)／２，…，２について、順に、第((ｎ＋１)／２−ｇ＋２ｊ−１)-ｑビットと第((ｎ＋１)／２−ｇ＋２ｊ)-ｑビットにＳＷＡＰを適用する演算を行うＳＷＡＰ量子回路を構成し〔ただし、ｊ＝１，…，ｇ−１とし、ｇごとに全てのｊについての演算を並列に行う量子回路とする。〕、《６》第((ｎ−１)／２＋１)-ｑビットから第ｎ-ｑビットまでについて、近傍２量子ビット演算で構成した２ (ｎ＋１)／２を法とする量子フーリエ変換を行う量子回路を構成し、ｎ＝１の場合、第１-ｑビットにアダマール変換を適用する量子回路を構成し、上記の手順で構成された量子回路において、２ｎより小さく２ｍより大きい数２Ｂを法とする量子フーリエ変換の量子回路については、このＢを新たなｎと看做して、上記の場合分けに従った手順で量子回路を構成し、２ｍ以下の数を法とする量子フーリエ変換を行う量子回路Ａについては、量子回路Ａへ入力されるＮ個のｑビットである第１-ｑビット、…、第Ｎ-ｑビットに対して、《１》ｇ＝１，…，Ｎについて、順に、ｇ＝１の場合、第１-ｑビットにアダマール変換を適用する演算を行う量子回路を構成し、ｇが３以上の奇数の場合、第１-ｑビットにアダマール変換を適用する演算を行う量子回路を構成し、第(ｊ−１)-ｑビットと第ｊ-ｑビットに角度２π／２ｊの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する演算を行う量子回路を構成し〔ただし、ｊは３からｇまでの奇数とし、ｇごとに第１-ｑビットに対するアダマール変換および全てのｊについての演算を並列に行う量子回路とする。〕、ｇが偶数の場合、第(ｊ−１)-ｑビットと第ｊ-ｑビットに角度２π／２ｊの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する演算を行う量子回路を構成し〔ただし、ｊは２からｇまでの偶数とし、ｇごとに全てのｊについての演算を並列に行う量子回路とする。〕、《２》ｇ＝Ｎ−１，…，１について、順に、ｇ＝１の場合、第１-ｑビットにアダマール変換を適用する演算を行う量子回路を構成し、ｇが３以上の奇数の場合、第１-ｑビットにアダマール変換を適用する演算を行う量子回路を構成し、第(ｊ−１)-ｑビットと第ｊ-ｑビットに角度２π／２ｊの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する演算を行う量子回路を構成し〔ただし、ｊは３からｇまでの奇数とし、ｇごとに第１-ｑビットに対するアダマール変換および全てのｊについての演算を並列に行う量子回路とする。〕、ｇが偶数の場合、第(ｊ−１)-ｑビットと第ｊ-ｑビットに角度２π／２ｊの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する演算を行う量子回路を構成し〔ただし、ｊは２からｇまでの偶数とし、ｇごとに全てのｊについての演算を並列に行う量子回路とする。〕、《３》ｇ＝１，…，Ｎ−１について、順に、ｇが奇数の場合、第ｊ-ｑビットと第(ｊ＋１)-ｑビットにＳＷＡＰを適用する演算を行う量子回路を構成し〔ただし、ｊは１からｇまでの奇数とし、ｇごとに全てのｊについてのＳＷＡＰを並列に行う量子回路とする。〕、ｇが偶数の場合、第ｊ-ｑビットと第(ｊ＋１)-ｑビットにＳＷＡＰを適用する演算を行う量子回路を構成し〔ただし、ｊは２からｇまでの偶数とし、ｇごとに全てのｊについてのＳＷＡＰを並列に行う量子回路とする。〕、《４》ｇ＝Ｎ−２，…，１について、順に、ｇが奇数の場合、第ｊ-ｑビットと第(ｊ＋１)-ｑビットにＳＷＡＰを適用する演算を行う量子回路を構成し〔ただし、ｊは１からｇまでの奇数とし、ｇごとに全てのｊについてのＳＷＡＰを並列に行う量子回路とする。〕、ｇが偶数の場合、第ｊ-ｑビットと第(ｊ＋１)-ｑビットにＳＷＡＰを適用する演算を行う量子回路を構成し〔ただし、ｊは２からｇまでの偶数とし、ｇごとに全てのｊについてのＳＷＡＰを並列に行う量子回路とする。〕、これまでの手順で構成された量子回路において、角度２π／２ｔ（ｔ＞ｍ）の制御フェイズシフトを恒等変換に置換し、角度２π／２ｔ（ｔ＝ｍ）の制御フェイズシフトの直後のＳＷＡＰおよび恒等変換とされた制御フェイズシフトの直後のＳＷＡＰの各演算を行う量子回路Ｃと、上記ＳＷＡＰ量子回路において量子回路Ｃの鏡像対称の量子回路部分とを相殺して構成された近似量子フーリエ変換を行う量子回路とする。
《５》ｇ＝(ｎ＋１)／２，…，２について、順に、第((ｎ＋１)／２−ｇ＋２ｊ)-ｑビットと第((ｎ＋１)／２−ｇ＋２ｊ＋１)-ｑビットにＳＷＡＰを適用する演算を行うＳＷＡＰ量子回路を構成し〔ただし、ｊ＝１，…，ｇ−１とし、ｇごとに全てのｊについての演算を並列に行う量子回路とする。〕、《６》第((ｎ＋１)／２＋１)-ｑビットから第ｎ-ｑビットまでについて、近傍２量子ビット演算で構成した２ (ｎ−１)／２を法とする量子フーリエ変換を行う量子回路を構成し、（パターン２）《１》第１-ｑビットから第((ｎ−１)／２)-ｑビットまでについて、近傍２量子ビット演算で構成した２(ｎ−１)／２を法とする量子フーリエ変換を行う量子回路を構成し、《２》ｇ＝２，…，(ｎ＋１)／２について、順に、第((ｎ＋１)／２−ｇ＋２ｊ−１)-ｑビットと第((ｎ＋１)／２−ｇ＋２ｊ)-ｑビットに角度２π／２ｇの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する演算を行う量子回路を構成し〔ただし、ｊ＝１，…，ｇ−１とし、ｇごとに全てのｊについての演算を並列に行う量子回路とする。〕、《３》ｇ＝(ｎ＋１)／２＋１，…，ｎについて、順に、第(ｇ−(ｎ＋１)／２＋２ｊ−１)-ｑビットと第(ｇ−(ｎ＋１)／２＋２ｊ)ビットに角度２π／２ｇの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する演算を行う量子回路を構成し〔ただし、ｊ＝１，…，ｎ＋１−ｇとし、ｇごとに全てのｊについての演算を並列に行う量子回路とする。〕、《４》ｇ＝ｎ，…，(ｎ＋１)／２＋１について、順に、第(ｇ−(ｎ＋１)／２＋２ｊ−１)-ｑビットと第(ｇ−(ｎ＋１)／２＋２ｊ)-ｑビットにＳＷＡＰを適用する演算を行うＳＷＡＰ量子回路を構成し〔ただし、ｊ＝１，…，ｎ＋１−ｇとし、ｇごとに全てのｊについての演算を並列に行う量子回路とする。〕、《５》ｇ＝(ｎ＋１)／２，…，２について、順に、第((ｎ＋１)／２−ｇ＋２ｊ−１)-ｑビットと第((ｎ＋１)／２−ｇ＋２ｊ)-ｑビットにＳＷＡＰを適用する演算を行うＳＷＡＰ量子回路を構成し〔ただし、ｊ＝１，…，ｇ−１とし、ｇごとに全てのｊについての演算を並列に行う量子回路とする。〕、《６》第((ｎ−１)／２＋１)-ｑビットから第ｎ-ｑビットまでについて、近傍２量子ビット演算で構成した２ (ｎ＋１)／２を法とする量子フーリエ変換を行う量子回路を構成し、ｎ＝１の場合、第１-ｑビットにアダマール変換を適用する量子回路を構成し、上記の手順で構成された量子回路において、２ｎより小さく２ｍより大きい数２Ｂを法とする量子フーリエ変換の量子回路については、このＢを新たなｎと看做して、上記の場合分けに従った手順で量子回路を構成し、２ｍ以下の数を法とする量子フーリエ変換を行う量子回路Ａについては、量子回路Ａへ入力されるＮ個のｑビットである第１-ｑビット、…、第Ｎ-ｑビットに対して、《１》ｇ＝１，…，Ｎについて、順に、ｇ＝１の場合、第１-ｑビットにアダマール変換を適用する演算を行う量子回路を構成し、ｇが３以上の奇数の場合、第１-ｑビットにアダマール変換を適用する演算を行う量子回路を構成し、第(ｊ−１)-ｑビットと第ｊ-ｑビットに角度２π／２ｊの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する演算を行う量子回路を構成し〔ただし、ｊは３からｇまでの奇数とし、ｇごとに第１-ｑビットに対するアダマール変換および全てのｊについての演算を並列に行う量子回路とする。〕、ｇが偶数の場合、第(ｊ−１)-ｑビットと第ｊ-ｑビットに角度２π／２ｊの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する演算を行う量子回路を構成し〔ただし、ｊは２からｇまでの偶数とし、ｇごとに全てのｊについての演算を並列に行う量子回路とする。〕、《２》ｇ＝Ｎ−１，…，１について、順に、ｇ＝１の場合、第１-ｑビットにアダマール変換を適用する演算を行う量子回路を構成し、ｇが３以上の奇数の場合、第１-ｑビットにアダマール変換を適用する演算を行う量子回路を構成し、第(ｊ−１)-ｑビットと第ｊ-ｑビットに角度２π／２ｊの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する演算を行う量子回路を構成し〔ただし、ｊは３からｇまでの奇数とし、ｇごとに第１-ｑビットに対するアダマール変換および全てのｊについての演算を並列に行う量子回路とする。〕、ｇが偶数の場合、第(ｊ−１)-ｑビットと第ｊ-ｑビットに角度２π／２ｊの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する演算を行う量子回路を構成し〔ただし、ｊは２からｇまでの偶数とし、ｇごとに全てのｊについての演算を並列に行う量子回路とする。〕、《３》ｇ＝１，…，Ｎ−１について、順に、ｇが奇数の場合、第ｊ-ｑビットと第(ｊ＋１)-ｑビットにＳＷＡＰを適用する演算を行う量子回路を構成し〔ただし、ｊは１からｇまでの奇数とし、ｇごとに全てのｊについてのＳＷＡＰを並列に行う量子回路とする。〕、ｇが偶数の場合、第ｊ-ｑビットと第(ｊ＋１)-ｑビットにＳＷＡＰを適用する演算を行う量子回路を構成し〔ただし、ｊは２からｇまでの偶数とし、ｇごとに全てのｊについてのＳＷＡＰを並列に行う量子回路とする。〕、《４》ｇ＝Ｎ−２，…，１について、順に、ｇが奇数の場合、第ｊ-ｑビットと第(ｊ＋１)-ｑビットにＳＷＡＰを適用する演算を行う量子回路を構成し〔ただし、ｊは１からｇまでの奇数とし、ｇごとに全てのｊについてのＳＷＡＰを並列に行う量子回路とする。〕、ｇが偶数の場合、第ｊ-ｑビットと第(ｊ＋１)-ｑビットにＳＷＡＰを適用する演算を行う量子回路を構成し〔ただし、ｊは２からｇまでの偶数とし、ｇごとに全てのｊについてのＳＷＡＰを並列に行う量子回路とする。〕、これまでの手順で構成された量子回路において、角度２π／２ｔ（ｔ＞ｍ）の制御フェイズシフトを恒等変換に置換し、角度２π／２ｔ（ｔ＝ｍ）の制御フェイズシフトの直後のＳＷＡＰおよび恒等変換とされた制御フェイズシフトの直後のＳＷＡＰの各演算を行う量子回路Ｃと、上記ＳＷＡＰ量子回路において量子回路Ｃの鏡像対称の量子回路部分とを相殺して構成された近似量子フーリエ変換を行う量子回路とする。
上記課題を解決するために、本発明の近似量子フーリエ変換演算方法は、次のような方法とされる。即ち、上記記載の近似量子フーリエ変換を行う量子回路に則り、入力された第１-ｑビットの状態|ｂｎ−１〉，…，第ｎ-ｑビットの状態|ｂ０〉に対して近似量子フーリエ変換を行う近似量子フーリエ変換演算方法とする。
上記課題を解決するために、本発明の近似量子フーリエ変換演算装置は、次のような構成とされる。即ち、近似の閾値を正整数ｎよりも小さい正整数ｍとし、２ｎを法とする近似量子フーリエ変換を行う近似量子フーリエ変換演算装置が演算対象とするｎ個のｑビットである第１-ｑビット、…、第ｎ-ｑビットに対して、ｎが偶数の場合、《１》第１-ｑビットから第(ｎ／２)-ｑビットまでについて、近傍２量子ビット演算で構成した２ｎ／２を法とする量子フーリエ変換を行う量子演算部を備え、《２》ｇ＝２，…，ｎ／２＋１について、順に、第(ｎ／２−ｇ＋２ｊ)-ｑビットと第(ｎ／２−ｇ＋２ｊ＋１)-ｑビットに角度２π／２ｇの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する演算を行う量子演算部を備え〔ただし、ｊ＝１，…，ｇ−１とし、ｇごとに全てのｊについての演算を並列に行うものとする。〕、《３》ｇ＝ｎ／２＋２，…，ｎについて、順に、第(ｇ−ｎ／２＋２ｊ−２)-ｑビットと第(ｇ−ｎ／２＋２ｊ−１)-ｑビットに角度２π／２ｇの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する演算を行う量子演算部を備え〔ただし、ｊ＝１，…，ｎ＋１−ｇとし、ｇごとに全てのｊについての演算を並列に行うものとする。〕、《４》ｇ＝ｎ，…，ｎ／２＋２について、順に、第(ｇ−ｎ／２＋２ｊ−２)-ｑビットと第(ｇ−ｎ／２＋２ｊ−１)-ｑビットにＳＷＡＰを適用する演算を行うＳＷＡＰ演算部を備え〔ただし、ｊ＝１，…，ｎ＋１−ｇとし、ｇごとに全てのｊについての演算を並列に行うものとする。〕、《５》ｇ＝ｎ／２＋１，…，２について、順に、第(ｎ／２−ｇ＋２ｊ)-ｑビットと第(ｎ／２−ｇ＋２ｊ＋１)-ｑビットにＳＷＡＰを適用する演算を行うＳＷＡＰ演算部を備え〔ただし、ｊ＝１，…，ｇ−１とし、ｇごとに全てのｊについての演算を並列に行うものとする。〕、《６》第(ｎ／２＋１)-ｑビットから第ｎ-ｑビットまでについて、近傍２量子ビット演算で構成した２ｎ／２を法とする量子フーリエ変換を行う量子演算部を備え、ｎが奇数の場合、パターン１またはパターン２のいずれかで、（パターン１）《１》第１-ｑビットから第((ｎ＋１)／２)-ｑビットまでについて、近傍２量子ビット演算で構成した２(ｎ＋１)／２を法とする量子フーリエ変換を行う量子演算部を備え、《２》ｇ＝２，…，(ｎ＋１)／２について、順に、第((ｎ＋１)／２−ｇ＋２ｊ)-ｑビットと第((ｎ＋１)／２−ｇ＋２ｊ＋１)-ｑビットに角度２π／２ｇの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する演算を行う量子演算部を備え〔ただし、ｊ＝１，…，ｇ−１とし、ｇごとに全てのｊについての演算を並列に行うものとする。〕、《３》ｇ＝(ｎ＋１)／２＋１，…，ｎについて、順に、第(ｇ−(ｎ＋１)／２＋２ｊ−２)-ｑビットと第(ｇ−(ｎ＋１)／２＋２ｊ−１)ビットに角度２π／２ｇの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する演算を行う量子演算部を備え〔ただし、ｊ＝１，…，ｎ＋１−ｇとし、ｇごとに全てのｊについての演算を並列に行うものとする。〕、《４》ｇ＝ｎ，…，(ｎ＋１)／２＋１について、順に、第(ｇ−(ｎ＋１)／２＋２ｊ−２)-ｑビットと第(ｇ−(ｎ＋１)／２＋２ｊ−１)-ｑビットにＳＷＡＰを適用する演算を行うＳＷＡＰ演算部を備え〔ただし、ｊ＝１，…，ｎ＋１−ｇとし、ｇごとに全てのｊについての演算を並列に行うものとする。〕、《５》ｇ＝(ｎ＋１)／２，…，２について、順に、第((ｎ＋１)／２−ｇ＋２ｊ)-ｑビットと第((ｎ＋１)／２−ｇ＋２ｊ＋１)-ｑビットにＳＷＡＰを適用する演算を行うＳＷＡＰ演算部を備え〔ただし、ｊ＝１，…，ｇ−１とし、ｇごとに全てのｊについての演算を並列に行うものとする。〕、《６》第((ｎ＋１)／２＋１)-ｑビットから第ｎ-ｑビットまでについて、近傍２量子ビット演算で構成した２ (ｎ−１)／２を法とする量子フーリエ変換を行う量子演算部を備え、（パターン２）《１》第１-ｑビットから第((ｎ−１)／２)-ｑビットまでについて、近傍２量子ビット演算で構成した２(ｎ−１)／２を法とする量子フーリエ変換を行う量子演算部を備え、《２》ｇ＝２，…，(ｎ＋１)／２について、順に、第((ｎ＋１)／２−ｇ＋２ｊ−１)-ｑビットと第((ｎ＋１)／２−ｇ＋２ｊ)-ｑビットに角度２π／２ｇの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する演算を行う量子演算部を備え〔ただし、ｊ＝１，…，ｇ−１とし、ｇごとに全てのｊについての演算を並列に行うものとする。〕、《３》ｇ＝(ｎ＋１)／２＋１，…，ｎについて、順に、第(ｇ−(ｎ＋１)／２＋２ｊ−１)-ｑビットと第(ｇ−(ｎ＋１)／２＋２ｊ)ビットに角度２π／２ｇの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する演算を行う量子演算部を備え〔ただし、ｊ＝１，…，ｎ＋１−ｇとし、ｇごとに全てのｊについての演算を並列に行うものとする。〕、《４》ｇ＝ｎ，…，(ｎ＋１)／２＋１について、順に、第(ｇ−(ｎ＋１)／２＋２ｊ−１)-ｑビットと第(ｇ−(ｎ＋１)／２＋２ｊ)-ｑビットにＳＷＡＰを適用する演算を行うＳＷＡＰ演算部を備え〔ただし、ｊ＝１，…，ｎ＋１−ｇとし、ｇごとに全てのｊについての演算を並列に行うものとする。〕、《５》ｇ＝(ｎ＋１)／２，…，２について、順に、第((ｎ＋１)／２−ｇ＋２ｊ−１)-ｑビットと第((ｎ＋１)／２−ｇ＋２ｊ)-ｑビットにＳＷＡＰを適用する演算を行うＳＷＡＰ演算部を備え〔ただし、ｊ＝１，…，ｇ−１とし、ｇごとに全てのｊについての演算を並列に行うものとする。〕、《６》第((ｎ−１)／２＋１)-ｑビットから第ｎ-ｑビットまでについて、近傍２量子ビット演算で構成した２ (ｎ＋１)／２を法とする量子フーリエ変換を行う量子演算部を備え、ｎ＝１の場合、第１-ｑビットにアダマール変換を適用する量子演算部を備え、上記の手順で構成された量子演算装置において、２ｎより小さく２ｍより大きい数２Ｂを法とする量子フーリエ変換の量子演算部については、このＢを新たなｎと看做して、上記の場合分けに従った手順で量子演算部を構成し、２ｍ以下の数を法とする量子フーリエ変換を行う量子演算部Ｄについては、量子演算部Ｄへ入力されるＮ個のｑビットである第１-ｑビット、…、第Ｎ-ｑビットに対して、《１》ｇ＝１，…，Ｎについて、順に、ｇ＝１の場合、第１-ｑビットにアダマール変換を適用する演算を行う量子演算部を備え、ｇが３以上の奇数の場合、第１-ｑビットにアダマール変換を適用する演算を行う量子演算部を備え、第(ｊ−１)-ｑビットと第ｊ-ｑビットに角度２π／２ｊの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する演算を行う量子演算部を備え〔ただし、ｊは３からｇまでの奇数とし、ｇごとに第１-ｑビットに対するアダマール変換および全てのｊについての演算を並列に行うものとする。〕、ｇが偶数の場合、第(ｊ−１)-ｑビットと第ｊ-ｑビットに角度２π／２ｊの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する演算を行う量子演算部を備え〔ただし、ｊは２からｇまでの偶数とし、ｇごとに全てのｊについての演算を並列に行うものとする。〕、《２》ｇ＝Ｎ−１，…，１について、順に、ｇ＝１の場合、第１-ｑビットにアダマール変換を適用する演算を行う量子演算部を備え、ｇが３以上の奇数の場合、第１-ｑビットにアダマール変換を適用する演算を行う量子演算部を備え、第(ｊ−１)-ｑビットと第ｊ-ｑビットに角度２π／２ｊの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する演算を行う量子演算部を備え〔ただし、ｊは３からｇまでの奇数とし、ｇごとに第１-ｑビットに対するアダマール変換および全てのｊについての演算を並列に行うものとする。〕、ｇが偶数の場合、第(ｊ−１)-ｑビットと第ｊ-ｑビットに角度２π／２ｊの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する演算を行う量子演算部を備え〔ただし、ｊは２からｇまでの偶数とし、ｇごとに全てのｊについての演算を並列に行うものとする。〕、《３》ｇ＝１，…，Ｎ−１について、順に、ｇが奇数の場合、第ｊ-ｑビットと第(ｊ＋１)-ｑビットにＳＷＡＰを適用する演算を行うＳＷＡＰ演算部を備え〔ただし、ｊは１からｇまでの奇数とし、ｇごとに全てのｊについてのＳＷＡＰを並列に行うものとする。〕、ｇが偶数の場合、第ｊ-ｑビットと第(ｊ＋１)-ｑビットにＳＷＡＰを適用する演算を行うＳＷＡＰ演算部を備え〔ただし、ｊは２からｇまでの偶数とし、ｇごとに全てのｊについてのＳＷＡＰを並列に行うものとする。〕、《４》ｇ＝Ｎ−２，…，１について、順に、ｇが奇数の場合、第ｊ-ｑビットと第(ｊ＋１)-ｑビットにＳＷＡＰを適用する演算を行うＳＷＡＰ演算部を備え〔ただし、ｊは１からｇまでの奇数とし、ｇごとに全てのｊについてのＳＷＡＰを並列に行うものとする。〕、ｇが偶数の場合、第ｊ-ｑビットと第(ｊ＋１)-ｑビットにＳＷＡＰを適用する演算を行うＳＷＡＰ演算部を備え〔ただし、ｊは２からｇまでの偶数とし、ｇごとに全てのｊについてのＳＷＡＰを並列に行うものとする。〕、以上に従って構成された近似量子フーリエ変換演算装置において、角度２π／２ｔ（ｔ＞ｍ）の制御フェイズシフトを行う量子演算部を、恒等変換を行う量子演算部に置換し、角度２π／２ｔ（ｔ＝ｍ）の制御フェイズシフトの直後のＳＷＡＰおよび恒等変換とされた制御フェイズシフトの直後のＳＷＡＰの各演算を行う量子演算部Ｅと、上記ＳＷＡＰ演算部において量子演算部Ｅの鏡像対称の量子演算部とを備えずに構成された近似量子フーリエ変換演算装置とする。
本発明に拠れば、近似の閾値をＯ(logｎ)とし、近傍２量子ビット演算を用いて、Ｏ(ｎ)個の計算ステップ数とＯ(ｎlogｎ)個の基本演算で近似量子フーリエ変換を行うことができる。また、基本演算の個数が従来よりも低減するから、演算誤りの発生する可能性を低減できる。
〔量子回路〕
まず、近似量子フーリエ変換を行う本発明の量子回路（１）を説明する。
近似量子フーリエ変換を行う量子回路（１）は、単一量子ビットに対する１量子ビット演算とＣＮＯＴを基本演算とするが、量子回路が複雑になるのを避けるため、これらの演算以外の演算も使って量子回路を構成するものとして説明する。本発明の量子回路に使われる全ての演算は、単一量子ビットに対する１量子ビット演算とＣＮＯＴに分解できることに注意しなければならない〔上記非特許文献１参照〕。
まず、近似量子フーリエ変換を行う本発明の量子回路（１）を説明する。
近似量子フーリエ変換を行う量子回路（１）は、単一量子ビットに対する１量子ビット演算とＣＮＯＴを基本演算とするが、量子回路が複雑になるのを避けるため、これらの演算以外の演算も使って量子回路を構成するものとして説明する。本発明の量子回路に使われる全ての演算は、単一量子ビットに対する１量子ビット演算とＣＮＯＴに分解できることに注意しなければならない〔上記非特許文献１参照〕。
近似量子フーリエ変換を行う量子回路（１）は、近傍２量子ビット演算で構成されていない、近似でない量子フーリエ変換の量子回路（２）〔下記参考文献参照〕と、上述した近傍２量子ビット演算で構成された近似でない量子フーリエ変換の量子回路（３）に基づいて構成される。
（参考文献） R. Cleve and J. Watrous, "Fast parallel circuits for the quantum Fourier transform", Proc. of the 4lst Annual Symposium on Foundations of Computer Science, pp.526-536, 2000.
（参考文献） R. Cleve and J. Watrous, "Fast parallel circuits for the quantum Fourier transform", Proc. of the 4lst Annual Symposium on Foundations of Computer Science, pp.526-536, 2000.
まず、近傍２量子ビット演算で構成されていない、近似でない量子フーリエ変換の量子回路（２）について説明する。量子回路（２）は自己相似的（self-similar）に構成される。即ち、或るＸを法とする近似でない量子フーリエ変換を行う量子回路を、Ｘより小さい数を法とする近似でない量子フーリエ変換を行う量子回路に分解することによって構成する。この構成の仕方は、正確には次のとおりである。
なお、量子回路（２）が行う近似でない量子フーリエ変換は、式（３）で表される量子フーリエ変換であるが、自己相似的に構成されることを考慮して、量子回路（２）が行う近似でない量子フーリエ変換をＱＦＴ−ＳＳと表記する。
なお、量子回路（２）が行う近似でない量子フーリエ変換は、式（３）で表される量子フーリエ変換であるが、自己相似的に構成されることを考慮して、量子回路（２）が行う近似でない量子フーリエ変換をＱＦＴ−ＳＳと表記する。
[ｎが偶数の場合]
ｎ２／４個の制御フェイズシフトと２ｎ／２を法とする量子フーリエ変換を行う量子回路２つから構成する。
より具体的には、２ｎ／２を法とする量子フーリエ変換を行う２つの量子回路は、上位〔線形な量子フーリエ変換を行う量子回路における上半分の配線に対応する。〕のｎ／２個のｑビットに対する２ｎ／２を法とする量子フーリエ変換を行う量子回路と、下位〔線形な量子フーリエ変換を行う量子回路における下半分の配線に対応する。〕のｎ／２個のｑビットに対する２ｎ／２を法とする量子フーリエ変換を行う量子回路とであり、ｎ２／４個の制御フェイズシフトを含む量子回路は、２ｎ／２を法とする量子フーリエ変換を行う２つの量子回路に挟まれた構成である。
ｎ２／４個の制御フェイズシフトと２ｎ／２を法とする量子フーリエ変換を行う量子回路２つから構成する。
より具体的には、２ｎ／２を法とする量子フーリエ変換を行う２つの量子回路は、上位〔線形な量子フーリエ変換を行う量子回路における上半分の配線に対応する。〕のｎ／２個のｑビットに対する２ｎ／２を法とする量子フーリエ変換を行う量子回路と、下位〔線形な量子フーリエ変換を行う量子回路における下半分の配線に対応する。〕のｎ／２個のｑビットに対する２ｎ／２を法とする量子フーリエ変換を行う量子回路とであり、ｎ２／４個の制御フェイズシフトを含む量子回路は、２ｎ／２を法とする量子フーリエ変換を行う２つの量子回路に挟まれた構成である。
[ｎが奇数の場合]
(ｎ−１)(ｎ＋１)／４個の制御フェイズシフトと２(ｎ＋１)／２を法とする量子フーリエ変換を行う量子回路と２(ｎ−１)／２を法とする量子フーリエ変換を行う量子回路とから構成する。
より具体的には、２つの構成が可能である。
１つ目〔パターン１〕は、２(ｎ＋１)／２を法とする量子フーリエ変換を行う量子回路を、上位〔線形な量子フーリエ変換を行う量子回路における上側の配線に対応する。〕の(ｎ＋１)／２個のｑビットに対する２(ｎ＋１)／２を法とする量子フーリエ変換を行う量子回路とし、２(ｎ−１)／２を法とする量子フーリエ変換を行う量子回路を、下位〔線形な量子フーリエ変換を行う量子回路における下側の配線に対応する。〕の(ｎ−１)／２個のｑビットに対する２(ｎ−１)／２を法とする量子フーリエ変換を行う量子回路とし、(ｎ−１)(ｎ＋１)／４個の制御フェイズシフトを含む量子回路は、２(ｎ＋１)／２を法とする量子フーリエ変換を行う量子回路と２(ｎ−１)／２を法とする量子フーリエ変換を行う量子回路とに挟まれた構成である。
２つ目〔パターン２〕は、２(ｎ＋１)／２を法とする量子フーリエ変換を行う量子回路を、下位〔線形な量子フーリエ変換を行う量子回路における下側の配線に対応する。〕の(ｎ＋１)／２個のｑビットに対する２(ｎ＋１)／２を法とする量子フーリエ変換を行う量子回路とし、２(ｎ−１)／２を法とする量子フーリエ変換を行う量子回路を、上位〔線形な量子フーリエ変換を行う量子回路における上側の配線に対応する。〕の(ｎ−１)／２個のｑビットに対する２(ｎ−１)／２を法とする量子フーリエ変換を行う量子回路とし、(ｎ−１)(ｎ＋１)／４個の制御フェイズシフトを含む量子回路は、２(ｎ＋１)／２を法とする量子フーリエ変換を行う量子回路と２(ｎ−１)／２を法とする量子フーリエ変換を行う量子回路とに挟まれた構成である。
(ｎ−１)(ｎ＋１)／４個の制御フェイズシフトと２(ｎ＋１)／２を法とする量子フーリエ変換を行う量子回路と２(ｎ−１)／２を法とする量子フーリエ変換を行う量子回路とから構成する。
より具体的には、２つの構成が可能である。
１つ目〔パターン１〕は、２(ｎ＋１)／２を法とする量子フーリエ変換を行う量子回路を、上位〔線形な量子フーリエ変換を行う量子回路における上側の配線に対応する。〕の(ｎ＋１)／２個のｑビットに対する２(ｎ＋１)／２を法とする量子フーリエ変換を行う量子回路とし、２(ｎ−１)／２を法とする量子フーリエ変換を行う量子回路を、下位〔線形な量子フーリエ変換を行う量子回路における下側の配線に対応する。〕の(ｎ−１)／２個のｑビットに対する２(ｎ−１)／２を法とする量子フーリエ変換を行う量子回路とし、(ｎ−１)(ｎ＋１)／４個の制御フェイズシフトを含む量子回路は、２(ｎ＋１)／２を法とする量子フーリエ変換を行う量子回路と２(ｎ−１)／２を法とする量子フーリエ変換を行う量子回路とに挟まれた構成である。
２つ目〔パターン２〕は、２(ｎ＋１)／２を法とする量子フーリエ変換を行う量子回路を、下位〔線形な量子フーリエ変換を行う量子回路における下側の配線に対応する。〕の(ｎ＋１)／２個のｑビットに対する２(ｎ＋１)／２を法とする量子フーリエ変換を行う量子回路とし、２(ｎ−１)／２を法とする量子フーリエ変換を行う量子回路を、上位〔線形な量子フーリエ変換を行う量子回路における上側の配線に対応する。〕の(ｎ−１)／２個のｑビットに対する２(ｎ−１)／２を法とする量子フーリエ変換を行う量子回路とし、(ｎ−１)(ｎ＋１)／４個の制御フェイズシフトを含む量子回路は、２(ｎ＋１)／２を法とする量子フーリエ変換を行う量子回路と２(ｎ−１)／２を法とする量子フーリエ変換を行う量子回路とに挟まれた構成である。
[ｎ＝１の場合]
アダマールゲートのみで構成する。つまり、１量子ビット演算を行う量子回路として構成される。
アダマールゲートのみで構成する。つまり、１量子ビット演算を行う量子回路として構成される。
より小さい数２Ｂを法とする量子フーリエ変換の量子回路については、このＢを新たなｎと看做して、上記の場合分けに従って、自己相似的に分解して構成する。例えば、ｎが偶数の場合では、２ｎ／２を法とする量子フーリエ変換を行う量子回路について、ｎ／２を新たなｎと看做して上記の場合分けに従って、自己相似的に分解して構成する。
以下、量子回路（２）の３つの具体例を示す。
図１０に、ｎ＝８の場合であるＱＦＴ８−ＳＳの量子回路（２）を示す。ＱＦＴ８−ＳＳの量子回路（２）は、[ｎが偶数の場合]で説明した方法に従って、図１０に示すように、２８／２を法とする量子フーリエ変換ＱＦＴ４−ＳＳを行う量子回路２つと１６個の制御フェイズシフトゲートとから構成される。図１０に示す量子回路（２）は、図１に示すＱＦＴ８の量子回路と実質的に同じであることに注意しなければならない。
２８／２を法とする量子フーリエ変換ＱＦＴ４−ＳＳを行う量子回路は、[ｎが偶数の場合]で説明した方法に従って、図１１に示すように、２４／２を法とする量子フーリエ変換ＱＦＴ２−ＳＳを行う量子回路２つと４個の制御フェイズシフトゲートとから構成される。
２４／２を法とする量子フーリエ変換ＱＦＴ２−ＳＳを行う量子回路は、[ｎが偶数の場合]で説明した方法に従って、図１２に示すように、２２／２を法とする量子フーリエ変換ＱＦＴ１−ＳＳを行う量子回路２つと１個の制御フェイズシフトゲートとから構成される。
２２／２を法とする量子フーリエ変換ＱＦＴ１−ＳＳを行う量子回路は、[ｎ＝１の場合]で説明した方法に従って、図１３に示すように、アダマールゲート１個から構成される。
図１０に、ｎ＝８の場合であるＱＦＴ８−ＳＳの量子回路（２）を示す。ＱＦＴ８−ＳＳの量子回路（２）は、[ｎが偶数の場合]で説明した方法に従って、図１０に示すように、２８／２を法とする量子フーリエ変換ＱＦＴ４−ＳＳを行う量子回路２つと１６個の制御フェイズシフトゲートとから構成される。図１０に示す量子回路（２）は、図１に示すＱＦＴ８の量子回路と実質的に同じであることに注意しなければならない。
２８／２を法とする量子フーリエ変換ＱＦＴ４−ＳＳを行う量子回路は、[ｎが偶数の場合]で説明した方法に従って、図１１に示すように、２４／２を法とする量子フーリエ変換ＱＦＴ２−ＳＳを行う量子回路２つと４個の制御フェイズシフトゲートとから構成される。
２４／２を法とする量子フーリエ変換ＱＦＴ２−ＳＳを行う量子回路は、[ｎが偶数の場合]で説明した方法に従って、図１２に示すように、２２／２を法とする量子フーリエ変換ＱＦＴ１−ＳＳを行う量子回路２つと１個の制御フェイズシフトゲートとから構成される。
２２／２を法とする量子フーリエ変換ＱＦＴ１−ＳＳを行う量子回路は、[ｎ＝１の場合]で説明した方法に従って、図１３に示すように、アダマールゲート１個から構成される。
図１４に、ｎ＝７の場合であるＱＦＴ７−ＳＳの〔パターン１〕の量子回路（２）を示す。ＱＦＴ７−ＳＳの〔パターン１〕の量子回路（２）は、[ｎが奇数の場合]の〔パターン１〕で説明した方法に従って、図１４に示すように、２８／２を法とする量子フーリエ変換ＱＦＴ４−ＳＳを行う量子回路と、２６／２を法とする量子フーリエ変換ＱＦＴ３−ＳＳを行う量子回路と、１２個の制御フェイズシフトゲートとから構成される。
２８／２を法とする量子フーリエ変換ＱＦＴ４−ＳＳを行う量子回路は、[ｎが偶数の場合]で説明した方法に従って、図１１に示すように、２４／２を法とする量子フーリエ変換ＱＦＴ２−ＳＳを行う量子回路２つと４個の制御フェイズシフトゲートとから構成される。
２６／２を法とする量子フーリエ変換ＱＦＴ３−ＳＳを行う量子回路は、[ｎが奇数の場合]の〔パターン１〕で説明した方法に従って、図１５に示すように、２４／２を法とする量子フーリエ変換ＱＦＴ２−ＳＳを行う量子回路と、２２／２を法とする量子フーリエ変換ＱＦＴ１−ＳＳを行う量子回路と、２個の制御フェイズシフトゲートとから構成される。
２４／２を法とする量子フーリエ変換ＱＦＴ２−ＳＳを行う量子回路は、[ｎが偶数の場合]で説明した方法に従って、図１２に示すように、２２／２を法とする量子フーリエ変換ＱＦＴ１−ＳＳを行う量子回路２つと１個の制御フェイズシフトゲートとから構成される。
２２／２を法とする量子フーリエ変換ＱＦＴ１−ＳＳを行う量子回路は、[ｎ＝１の場合]で説明した方法に従って、図１３に示すように、アダマールゲート１個から構成される。
２８／２を法とする量子フーリエ変換ＱＦＴ４−ＳＳを行う量子回路は、[ｎが偶数の場合]で説明した方法に従って、図１１に示すように、２４／２を法とする量子フーリエ変換ＱＦＴ２−ＳＳを行う量子回路２つと４個の制御フェイズシフトゲートとから構成される。
２６／２を法とする量子フーリエ変換ＱＦＴ３−ＳＳを行う量子回路は、[ｎが奇数の場合]の〔パターン１〕で説明した方法に従って、図１５に示すように、２４／２を法とする量子フーリエ変換ＱＦＴ２−ＳＳを行う量子回路と、２２／２を法とする量子フーリエ変換ＱＦＴ１−ＳＳを行う量子回路と、２個の制御フェイズシフトゲートとから構成される。
２４／２を法とする量子フーリエ変換ＱＦＴ２−ＳＳを行う量子回路は、[ｎが偶数の場合]で説明した方法に従って、図１２に示すように、２２／２を法とする量子フーリエ変換ＱＦＴ１−ＳＳを行う量子回路２つと１個の制御フェイズシフトゲートとから構成される。
２２／２を法とする量子フーリエ変換ＱＦＴ１−ＳＳを行う量子回路は、[ｎ＝１の場合]で説明した方法に従って、図１３に示すように、アダマールゲート１個から構成される。
図１６に、ｎ＝７の場合であるＱＦＴ７−ＳＳの〔パターン２〕の量子回路（２）を示す。ＱＦＴ７−ＳＳの〔パターン２〕の量子回路（２）は、[ｎが奇数の場合]の〔パターン２〕で説明した方法に従って、図１６に示すように、２６／２を法とする量子フーリエ変換ＱＦＴ３−ＳＳを行う量子回路と、２８／２を法とする量子フーリエ変換ＱＦＴ４−ＳＳを行う量子回路と、１２個の制御フェイズシフトゲートとから構成される。
２８／２を法とする量子フーリエ変換ＱＦＴ４−ＳＳを行う量子回路は、[ｎが偶数の場合]で説明した方法に従って、図１１に示すように、２４／２を法とする量子フーリエ変換ＱＦＴ２−ＳＳを行う量子回路２つと４個の制御フェイズシフトゲートとから構成される。
２６／２を法とする量子フーリエ変換ＱＦＴ３−ＳＳを行う量子回路は、[ｎが奇数の場合]の〔パターン２〕で説明した方法に従って、図１７に示すように、２２／２を法とする量子フーリエ変換ＱＦＴ１−ＳＳを行う量子回路と、２４／２を法とする量子フーリエ変換ＱＦＴ２−ＳＳを行う量子回路と、２個の制御フェイズシフトゲートとから構成される。
２４／２を法とする量子フーリエ変換ＱＦＴ２−ＳＳを行う量子回路は、[ｎが偶数の場合]で説明した方法に従って、図１２に示すように、２２／２を法とする量子フーリエ変換ＱＦＴ１−ＳＳを行う量子回路２つと１個の制御フェイズシフトゲートとから構成される。
２２／２を法とする量子フーリエ変換ＱＦＴ１−ＳＳを行う量子回路は、[ｎ＝１の場合]で説明した方法に従って、図１３に示すように、アダマールゲート１個から構成される。
２８／２を法とする量子フーリエ変換ＱＦＴ４−ＳＳを行う量子回路は、[ｎが偶数の場合]で説明した方法に従って、図１１に示すように、２４／２を法とする量子フーリエ変換ＱＦＴ２−ＳＳを行う量子回路２つと４個の制御フェイズシフトゲートとから構成される。
２６／２を法とする量子フーリエ変換ＱＦＴ３−ＳＳを行う量子回路は、[ｎが奇数の場合]の〔パターン２〕で説明した方法に従って、図１７に示すように、２２／２を法とする量子フーリエ変換ＱＦＴ１−ＳＳを行う量子回路と、２４／２を法とする量子フーリエ変換ＱＦＴ２−ＳＳを行う量子回路と、２個の制御フェイズシフトゲートとから構成される。
２４／２を法とする量子フーリエ変換ＱＦＴ２−ＳＳを行う量子回路は、[ｎが偶数の場合]で説明した方法に従って、図１２に示すように、２２／２を法とする量子フーリエ変換ＱＦＴ１−ＳＳを行う量子回路２つと１個の制御フェイズシフトゲートとから構成される。
２２／２を法とする量子フーリエ変換ＱＦＴ１−ＳＳを行う量子回路は、[ｎ＝１の場合]で説明した方法に従って、図１３に示すように、アダマールゲート１個から構成される。
上記の例では、〔パターン１〕で構成する場合には、より小さい奇数を法とする量子フーリエ変換を行う量子回路も〔パターン１〕で構成するとし、〔パターン２〕で構成する場合には、より小さい奇数を法とする量子フーリエ変換を行う量子回路も〔パターン２〕で構成するとして説明したが、このような構成に限定する意味ではない。より大きい奇数を法とする量子フーリエ変換を行う量子回路の構成パターンに束縛されることなく、随意のパターンで、より小さい奇数を法とする量子フーリエ変換を行う量子回路を構成できる。
上記各例からも明らかなように、ＱＦＴ−ＳＳの量子回路は、１計算ステップに処理できる演算を分離していることから、ＬＮＮ−ＱＦＴの量子回路〔図５参照〕よりも計算ステップが増大したものとなっている。
さて、量子回路（２）の構成の仕方と同様に、近似でない量子フーリエ変換を行う量子回路（１ｐ）を構成するが、次の点で構成の仕方に違いがある。
１点目は、２ｍ〔ｍは近似の閾値である。〕以下の数を法とする量子フーリエ変換を行う量子回路から構成されるようになるまで自己相似的に分解して構成する。２ｍ以下の数を法とする量子フーリエ変換を行う量子回路については、さらなる自己相似的な分解をしない。２ｍ以下の数を法とする量子フーリエ変換を行う量子回路は、上述した近傍２量子ビット演算で構成された近似でない量子フーリエ変換ＬＮＮ−ＱＦＴの量子回路（３）として構成される。
２点目は、量子回路（２）は近傍２量子ビット演算を使う量子回路ではないため、近傍２量子ビット演算を使う量子回路とする。
なお、量子回路（１ｐ）が行う近似でない量子フーリエ変換は、式（３）で表される量子フーリエ変換であるが、自己相似的に構成されることと近傍２量子ビット演算を使うことを考慮して、量子回路（１ｐ）が行う近似でない量子フーリエ変換をＬＮＮ−ＱＦＴ−ＳＳと表記する。
１点目は、２ｍ〔ｍは近似の閾値である。〕以下の数を法とする量子フーリエ変換を行う量子回路から構成されるようになるまで自己相似的に分解して構成する。２ｍ以下の数を法とする量子フーリエ変換を行う量子回路については、さらなる自己相似的な分解をしない。２ｍ以下の数を法とする量子フーリエ変換を行う量子回路は、上述した近傍２量子ビット演算で構成された近似でない量子フーリエ変換ＬＮＮ−ＱＦＴの量子回路（３）として構成される。
２点目は、量子回路（２）は近傍２量子ビット演算を使う量子回路ではないため、近傍２量子ビット演算を使う量子回路とする。
なお、量子回路（１ｐ）が行う近似でない量子フーリエ変換は、式（３）で表される量子フーリエ変換であるが、自己相似的に構成されることと近傍２量子ビット演算を使うことを考慮して、量子回路（１ｐ）が行う近似でない量子フーリエ変換をＬＮＮ−ＱＦＴ−ＳＳと表記する。
量子回路（１ｐ）の構成を、図１８を参照して説明する。図１８は、説明の便宜から、ｎが２の冪乗数の場合を想定しており、近似でない量子フーリエ変換ＬＮＮ−ＱＦＴ−ＳＳを行う量子回路（１ｐ）を、自己相似的に分解して構成することを説明する模式図である。図１８の中央に示されたLNN controlled phase shift circuit は、ｎ個のｑビットの量子フーリエ変換ＬＮＮ−ＱＦＴｎ−ＳＳを行う量子回路において、量子回路（２）に表れたｎ２／４個の制御フェイズシフトを近傍２量子ビット演算となるように構成した量子回路を表しており、その詳細は後述する。図１８の中央に示されたLNN controlled phase shift circuit の両脇に、近傍２量子ビット演算で構成されたｎ／２個のｑビットの量子フーリエ変換ＬＮＮ−ＱＦＴｎ／２−ＳＳを行う量子回路が構成される。
ＬＮＮ−ＱＦＴｎ／２−ＳＳを行う量子回路は、ＬＮＮ−ＱＦＴｎ−ＳＳを行う量子回路と自己相似的に構成される。ＬＮＮ−ＱＦＴｎ／２−ＳＳを行う量子回路の中央に示されたLNN controlled phase shift circuit は、ｎ／２個のｑビットの量子フーリエ変換ＬＮＮ−ＱＦＴｎ／２−ＳＳを行う量子回路において、量子回路（２）に表れた(ｎ／２)２／４個の制御フェイズシフトを近傍２量子ビット演算となるように構成した量子回路を表している。ＬＮＮ−ＱＦＴｎ／２−ＳＳを行う量子回路の中央に示されたLNN controlled phase shift circuit の両脇に、近傍２量子ビット演算で構成された(ｎ／２)／２個のｑビットの量子フーリエ変換ＬＮＮ−ＱＦＴ(ｎ／２)／２−ＳＳを行う量子回路が構成される。
ＬＮＮ−ＱＦＴ(ｎ／２)／２−ＳＳを行う量子回路は、ＬＮＮ−ＱＦＴｎ／２−ＳＳを行う量子回路と自己相似的に構成される。ＬＮＮ−ＱＦＴ(ｎ／２)／２−ＳＳを行う量子回路の中央に示されたLNN controlled phase shift circuit は、(ｎ／２)／２個のｑビットの量子フーリエ変換ＬＮＮ−ＱＦＴ(ｎ／２)／２−ＳＳを行う量子回路において、量子回路（２）に表れた((ｎ／２)／２)２／４個の制御フェイズシフトを近傍２量子ビット演算となるように構成した量子回路を表している。ＬＮＮ−ＱＦＴ(ｎ／２)／２−ＳＳを行う量子回路の中央に示されたLNN controlled phase shift circuit の両脇に、近傍２量子ビット演算で構成された((ｎ／２)／２)／２個のｑビットの量子フーリエ変換ＬＮＮ−ＱＦＴ((ｎ／２)／２)／２−ＳＳを行う量子回路が構成される。
このような自己相似的な分解による構成を繰り返すことで、近似でない量子フーリエ変換を行う量子回路（１ｐ）を構成するのであるが、量子回路ＬＮＮ−ＱＦＴｎ／２ｄ〔ｄ＝１，２，…〕が、ｍ≧ｎ／２ｄとなる場合、量子回路ＬＮＮ−ＱＦＴｎ／２ｄを自己相似的に分解して構成することを中止する。つまり、量子回路ＬＮＮ−ＱＦＴｎ／２ｄは、量子回路（３）として構成される。
ここでは、説明の便宜から、ｎが２の冪乗数の場合を想定して説明したが、ｎが一般的に偶数の場合でも奇数の場合でも、上記２つの異なる点に注意して、量子回路（２）の構成の仕方と同様にして、量子回路（１ｐ）を構成することができる。
そこで、ｎが偶数の場合と奇数の場合に分け、自己相似的に分解して量子回路（１ｐ）を構成する方法を説明する。
量子回路（１ｐ）へ入力されるｎ個のｑビットの状態を|ｂｎ−１〉，…，|ｂ０〉とし、それぞれのｑビットを順に第１-ｑビット、…、第ｎ-ｑビットと云うことにする。つまり、最上位の配線に相当するｑビットを第１-ｑビットとし、最下位の配線に相当するｑビットを第ｎ-ｑビットとする。また、記載の便宜から、第(・)-ｑビットなどとも記載する。
量子回路（１ｐ）へ入力されるｎ個のｑビットの状態を|ｂｎ−１〉，…，|ｂ０〉とし、それぞれのｑビットを順に第１-ｑビット、…、第ｎ-ｑビットと云うことにする。つまり、最上位の配線に相当するｑビットを第１-ｑビットとし、最下位の配線に相当するｑビットを第ｎ-ｑビットとする。また、記載の便宜から、第(・)-ｑビットなどとも記載する。
[ｎが偶数の場合]
《１》 第１-ｑビットから第(ｎ／２)-ｑビットまでについて、近傍２量子ビット演算で構成した２ｎ／２を法とする量子フーリエ変換を行う量子回路を適用する。
《１》 第１-ｑビットから第(ｎ／２)-ｑビットまでについて、近傍２量子ビット演算で構成した２ｎ／２を法とする量子フーリエ変換を行う量子回路を適用する。
《２》 ｇ＝２，…，ｎ／２＋１について、順に、次の演算を行う量子回路とする。第(ｎ／２−ｇ＋２ｊ)-ｑビットと第(ｎ／２−ｇ＋２ｊ＋１)-ｑビットに角度２π／２ｇの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。ただし、ｊ＝１，…，ｇ−１とし、ｇごとに全てのｊについての演算を並列に行うものとする。並列に演算することで計算ステップ数の増加を抑圧する〔以下同様〕。
《３》 ｇ＝ｎ／２＋２，…，ｎについて、順に、次の演算を行う量子回路とする。第(ｇ−ｎ／２＋２ｊ−２)-ｑビットと第(ｇ−ｎ／２＋２ｊ−１)-ｑビットに角度２π／２ｇの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。ただし、ｊ＝１，…，ｎ＋１−ｇとし、ｇごとに全てのｊについての演算は並列に行う。
なお、ｇ＝ｎの場合の最後のＳＷＡＰは、下記《４》の最初のＳＷＡＰと相殺されることになる。
なお、ｇ＝ｎの場合の最後のＳＷＡＰは、下記《４》の最初のＳＷＡＰと相殺されることになる。
《４》 ｇ＝ｎ，…，ｎ／２＋２について、順に、次の演算を行う量子回路とする。第(ｇ−ｎ／２＋２ｊ−２)-ｑビットと第(ｇ−ｎ／２＋２ｊ−１)-ｑビットにＳＷＡＰを適用する。ただし、ｊ＝１，…，ｎ＋１−ｇとし、ｇごとに全てのｊについての演算は並列に行う。
《５》 ｇ＝ｎ／２＋１，…，２について、順に、次の演算を行う量子回路とする。第(ｎ／２−ｇ＋２ｊ)-ｑビットと第(ｎ／２−ｇ＋２ｊ＋１)-ｑビットにＳＷＡＰを適用する。ただし、ｊ＝１，…，ｇ−１とし、ｇごとに全てのｊについての演算は並列に行う。
《６》 第(ｎ／２＋１)-ｑビットから第ｎ-ｑビットまでについて、近傍２量子ビット演算で構成した２ｎ／２を法とする量子フーリエ変換を行う量子回路を適用する。
[ｎが奇数の場合]
具体的には、２つの構成が可能である。
具体的には、２つの構成が可能である。
（パターン１）
《１》 第１-ｑビットから第((ｎ＋１)／２)-ｑビットまでについて、近傍２量子ビット演算で構成した２(ｎ＋１)／２を法とする量子フーリエ変換を行う量子回路を適用する。
《１》 第１-ｑビットから第((ｎ＋１)／２)-ｑビットまでについて、近傍２量子ビット演算で構成した２(ｎ＋１)／２を法とする量子フーリエ変換を行う量子回路を適用する。
《２》 ｇ＝２，…，(ｎ＋１)／２について、順に、次の演算を行う量子回路とする。第((ｎ＋１)／２−ｇ＋２ｊ)-ｑビットと第((ｎ＋１)／２−ｇ＋２ｊ＋１)-ｑビットに角度２π／２ｇの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。ただし、ｊ＝１，…，ｇ−１とし、ｇごとに全てのｊについての演算は並列に行う。
《３》 ｇ＝(ｎ＋１)／２＋１，…，ｎについて、順に、次の演算を行う量子回路とする。第(ｇ−(ｎ＋１)／２＋２ｊ−２)-ｑビットと第(ｇ−(ｎ＋１)／２＋２ｊ−１)ビットに角度２π／２ｇの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。ただし、ｊ＝１，…，ｎ＋１−ｇとし、ｇごとに全てのｊについての演算は並列に行う。
なお、ｇ＝ｎの場合の最後のＳＷＡＰは、下記《４》の最初のＳＷＡＰと相殺されることに注意する。
なお、ｇ＝ｎの場合の最後のＳＷＡＰは、下記《４》の最初のＳＷＡＰと相殺されることに注意する。
《４》 ｇ＝ｎ，…，(ｎ＋１)／２＋１について、順に、次の演算を行う量子回路とする。第(ｇ−(ｎ＋１)／２＋２ｊ−２)-ｑビットと第(ｇ−(ｎ＋１)／２＋２ｊ−１)-ｑビットにＳＷＡＰを適用する。ただし、ｊ＝１，…，ｎ＋１−ｇとし、ｇごとに全てのｊについての演算は並列に行う。
《５》 ｇ＝(ｎ＋１)／２，…，２について、順に、次の演算を行う量子回路とする。第((ｎ＋１)／２−ｇ＋２ｊ)-ｑビットと第((ｎ＋１)／２−ｇ＋２ｊ＋１)-ｑビットにＳＷＡＰを適用する。ただし、ｊ＝１，…，ｇ−１とし、ｇごとに全てのｊについての演算は並列に行う。
《６》 第((ｎ＋１)／２＋１)-ｑビットから第ｎ-ｑビットまでについて、近傍２量子ビット演算で構成した２ (ｎ−１)／２を法とする量子フーリエ変換を行う量子回路を適用する。
（パターン２）
《１》 第１-ｑビットから第((ｎ−１)／２)-ｑビットまでについて、近傍２量子ビット演算で構成した２(ｎ−１)／２を法とする量子フーリエ変換を行う量子回路を適用する。
《１》 第１-ｑビットから第((ｎ−１)／２)-ｑビットまでについて、近傍２量子ビット演算で構成した２(ｎ−１)／２を法とする量子フーリエ変換を行う量子回路を適用する。
《２》 ｇ＝２，…，(ｎ＋１)／２について、順に、次の演算を行う量子回路とする。第((ｎ＋１)／２−ｇ＋２ｊ−１)-ｑビットと第((ｎ＋１)／２−ｇ＋２ｊ)-ｑビットに角度２π／２ｇの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。ただし、ｊ＝１，…，ｇ−１とし、ｇごとに全てのｊについての演算は並列に行う。
《３》 ｇ＝(ｎ＋１)／２＋１，…，ｎについて、順に、次の演算を行う量子回路とする。第(ｇ−(ｎ＋１)／２＋２ｊ−１)-ｑビットと第(ｇ−(ｎ＋１)／２＋２ｊ)ビットに角度２π／２ｇの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。ただし、ｊ＝１，…，ｎ＋１−ｇとし、ｇごとに全てのｊについての演算は並列に行う。
なお、ｇ＝ｎの場合の最後のＳＷＡＰは、下記《４》の最初のＳＷＡＰと相殺されることに注意する。
なお、ｇ＝ｎの場合の最後のＳＷＡＰは、下記《４》の最初のＳＷＡＰと相殺されることに注意する。
《４》 ｇ＝ｎ，…，(ｎ＋１)／２＋１について、順に、次の演算を行う量子回路とする。第(ｇ−(ｎ＋１)／２＋２ｊ−１)-ｑビットと第(ｇ−(ｎ＋１)／２＋２ｊ)-ｑビットにＳＷＡＰを適用する。ただし、ｊ＝１，…，ｎ＋１−ｇとし、ｇごとに全てのｊについての演算は並列に行う。
《５》 ｇ＝(ｎ＋１)／２，…，２について、順に、次の演算を行う量子回路とする。第((ｎ＋１)／２−ｇ＋２ｊ−１)-ｑビットと第((ｎ＋１)／２−ｇ＋２ｊ)-ｑビットにＳＷＡＰを適用する。ただし、ｊ＝１，…，ｇ−１とし、ｇごとに全てのｊについての演算は並列に行う。
《６》 第((ｎ−１)／２＋１)-ｑビットから第ｎ-ｑビットまでについて、近傍２量子ビット演算で構成した２ (ｎ＋１)／２を法とする量子フーリエ変換を行う量子回路を適用する。
[ｎ＝１の場合]
第１-ｑビットにアダマール変換を適用する。
第１-ｑビットにアダマール変換を適用する。
２ｎより小さく２ｍより大きい数２Ｂを法とする量子フーリエ変換の量子回路については、このＢを新たなｎと看做して、上記の場合分けに従って、自己相似的に分解して構成する。例えば、ｎが偶数の場合では、２ｎ／２を法とする量子フーリエ変換を行う量子回路について、ｎ／２を新たなｎと看做して上記の場合分けに従って、自己相似的に分解して構成する。
なお、２ｍ以下の数を法とする量子フーリエ変換を行う量子回路については、さらなる自己相似的な分解をしない。２ｍ以下の数を法とする量子フーリエ変換を行う量子回路は、上述した近傍２量子ビット演算で構成された近似でない量子フーリエ変換ＬＮＮ−ＱＦＴの量子回路（３）として構成される。
以下、量子回路（１ｐ）の３つの具体例を示す。
図１９に、ｎ＝８の場合であるＬＮＮ−ＱＦＴ８−ＳＳの量子回路（１ｐ）を示す。ＬＮＮ−ＱＦＴ８−ＳＳの量子回路（１ｐ）は、[ｎが偶数の場合]で説明した方法に従って、次のように構成される。
《１》 第１-ｑビットから第(８／２)-ｑビットまでについて、近傍２量子ビット演算で構成した２８／２を法とする量子フーリエ変換ＬＮＮ−ＱＦＴ４−ＳＳを行う量子回路を構成する〔図１９において符号α１で指示する量子回路〕。ＬＮＮ−ＱＦＴ４−ＳＳを行う量子回路は、[ｎが偶数の場合]で説明した方法に従って構成される。
《２》 ｇ＝２，…，８／２＋１について、次の演算を行う量子回路を構成する。第(８／２−ｇ＋２ｊ)-ｑビットと第(８／２−ｇ＋２ｊ＋１)-ｑビットに角度２π／２ｇの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する〔図１９において符号α２で指示する量子回路〕。ただし、ｊ＝１，…，ｇ−１とし、ｇごとに全てのｊについての演算を並列に行う構成である。つまり、図１９において、例えば実線で囲んだ部分は、１計算ステップで並列に演算可能であり、その他も同様である。
《３》 ｇ＝８／２＋２，…，８について、次の演算を行う量子回路を構成する。第(ｇ−８／２＋２ｊ−２)-ｑビットと第(ｇ−８／２＋２ｊ−１)-ｑビットに角度２π／２ｇの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する〔図１９において符号α３で指示する量子回路〕。ただし、ｊ＝１，…，８＋１−ｇとし、ｇごとに全てのｊについての演算は並列に行う構成である。ｇ＝８の場合の最後のＳＷＡＰは、次の《４》の最初のＳＷＡＰと相殺されることになるが図１９では、説明の便宜で敢えて残している。
《４》 ｇ＝８，…，８／２＋２について、次の演算を行う量子回路を構成する。第(ｇ−８／２＋２ｊ−２)-ｑビットと第(ｇ−８／２＋２ｊ−１)-ｑビットにＳＷＡＰを適用する〔図１９において符号α４で指示する量子回路〕。ただし、ｊ＝１，…，８＋１−ｇとし、ｇごとに全てのｊについての演算は並列に行う構成である。
《５》 ｇ＝８／２＋１，…，２について、次の演算を行う量子回路を構成する。第(８／２−ｇ＋２ｊ)-ｑビットと第(８／２−ｇ＋２ｊ＋１)-ｑビットにＳＷＡＰを適用する〔図１９において符号α５で指示する量子回路〕。ただし、ｊ＝１，…，ｇ−１とし、ｇごとに全てのｊについての演算は並列に行う構成である。
《６》 第(８／２＋１)-ｑビットから第８-ｑビットまでについて、近傍２量子ビット演算で構成した２８／２を法とする量子フーリエ変換ＬＮＮ−ＱＦＴ４−ＳＳを行う量子回路を構成する〔図１９において符号α６で指示する量子回路〕。ＬＮＮ−ＱＦＴ４−ＳＳを行う量子回路は、[ｎが偶数の場合]で説明した方法に従って構成される。
図１９に、ｎ＝８の場合であるＬＮＮ−ＱＦＴ８−ＳＳの量子回路（１ｐ）を示す。ＬＮＮ−ＱＦＴ８−ＳＳの量子回路（１ｐ）は、[ｎが偶数の場合]で説明した方法に従って、次のように構成される。
《１》 第１-ｑビットから第(８／２)-ｑビットまでについて、近傍２量子ビット演算で構成した２８／２を法とする量子フーリエ変換ＬＮＮ−ＱＦＴ４−ＳＳを行う量子回路を構成する〔図１９において符号α１で指示する量子回路〕。ＬＮＮ−ＱＦＴ４−ＳＳを行う量子回路は、[ｎが偶数の場合]で説明した方法に従って構成される。
《２》 ｇ＝２，…，８／２＋１について、次の演算を行う量子回路を構成する。第(８／２−ｇ＋２ｊ)-ｑビットと第(８／２−ｇ＋２ｊ＋１)-ｑビットに角度２π／２ｇの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する〔図１９において符号α２で指示する量子回路〕。ただし、ｊ＝１，…，ｇ−１とし、ｇごとに全てのｊについての演算を並列に行う構成である。つまり、図１９において、例えば実線で囲んだ部分は、１計算ステップで並列に演算可能であり、その他も同様である。
《３》 ｇ＝８／２＋２，…，８について、次の演算を行う量子回路を構成する。第(ｇ−８／２＋２ｊ−２)-ｑビットと第(ｇ−８／２＋２ｊ−１)-ｑビットに角度２π／２ｇの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する〔図１９において符号α３で指示する量子回路〕。ただし、ｊ＝１，…，８＋１−ｇとし、ｇごとに全てのｊについての演算は並列に行う構成である。ｇ＝８の場合の最後のＳＷＡＰは、次の《４》の最初のＳＷＡＰと相殺されることになるが図１９では、説明の便宜で敢えて残している。
《４》 ｇ＝８，…，８／２＋２について、次の演算を行う量子回路を構成する。第(ｇ−８／２＋２ｊ−２)-ｑビットと第(ｇ−８／２＋２ｊ−１)-ｑビットにＳＷＡＰを適用する〔図１９において符号α４で指示する量子回路〕。ただし、ｊ＝１，…，８＋１−ｇとし、ｇごとに全てのｊについての演算は並列に行う構成である。
《５》 ｇ＝８／２＋１，…，２について、次の演算を行う量子回路を構成する。第(８／２−ｇ＋２ｊ)-ｑビットと第(８／２−ｇ＋２ｊ＋１)-ｑビットにＳＷＡＰを適用する〔図１９において符号α５で指示する量子回路〕。ただし、ｊ＝１，…，ｇ−１とし、ｇごとに全てのｊについての演算は並列に行う構成である。
《６》 第(８／２＋１)-ｑビットから第８-ｑビットまでについて、近傍２量子ビット演算で構成した２８／２を法とする量子フーリエ変換ＬＮＮ−ＱＦＴ４−ＳＳを行う量子回路を構成する〔図１９において符号α６で指示する量子回路〕。ＬＮＮ−ＱＦＴ４−ＳＳを行う量子回路は、[ｎが偶数の場合]で説明した方法に従って構成される。
図２０に、ｎ＝７の場合であるＬＮＮ−ＱＦＴ７−ＳＳの（パターン１）の量子回路（１ｐ）を示す。ＬＮＮ−ＱＦＴ７−ＳＳの（パターン１）の量子回路（１ｐ）は、[ｎが奇数の場合]の（パターン１）で説明した方法に従って、次のように構成される。
《１》 第１-ｑビットから第((７＋１)／２)-ｑビットまでについて、近傍２量子ビット演算を用いて２(７＋１)／２を法とする量子フーリエ変換ＬＮＮ−ＱＦＴ４−ＳＳを行う量子回路を構成する〔図２０において符号β１で指示する量子回路〕。ＬＮＮ−ＱＦＴ４−ＳＳを行う量子回路は、[ｎが偶数の場合]で説明した方法に従って構成される。
《２》 ｇ＝２，…，(７＋１)／２について、順に、次の演算を行う量子回路とする。第((７＋１)／２−ｇ＋２ｊ)-ｑビットと第((７＋１)／２−ｇ＋２ｊ＋１)-ｑビットに角度２π／２ｇの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する〔図２０において符号β２で指示する量子回路〕。ただし、ｊ＝１，…，ｇ−１とし、ｇごとに全てのｊについての演算を並列に行う構成である。
《３》 ｇ＝(７＋１)／２＋１，…，７について、順に、次の演算を行う量子回路とする。第(ｇ−(７＋１)／２＋２ｊ−２)-ｑビットと第(ｇ−(７＋１)／２＋２ｊ−１)ビットに角度２π／２ｇの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する〔図２０において符号β３で指示する量子回路〕。ただし、ｊ＝１，…，ｎ＋１−ｇとし、ｇごとに全てのｊについての演算を並列に行う構成である。ｇ＝７の場合の最後のＳＷＡＰは、次の《４》の最初のＳＷＡＰと相殺されることになるが図２０では、説明の便宜で敢えて残している。
《４》 ｇ＝７，…，(７＋１)／２＋１について、順に、次の演算を行う量子回路とする。第(ｇ−(７＋１)／２＋２ｊ−２)-ｑビットと第(ｇ−(７＋１)／２＋２ｊ−１)-ｑビットにＳＷＡＰを適用する〔図２０において符号β４で指示する量子回路〕。ただし、ｊ＝１，…，ｎ＋１−ｇとし、ｇごとに全てのｊについての演算を並列に行う構成である。
《５》 ｇ＝(７＋１)／２，…，２について、順に、次の演算を行う量子回路とする。第((７＋１)／２−ｇ＋２ｊ)-ｑビットと第((７＋１)／２−ｇ＋２ｊ＋１)-ｑビットにＳＷＡＰを適用する〔図２０において符号β５で指示する量子回路〕。ただし、ｊ＝１，…，ｇ−１とし、ｇごとに全てのｊについてのて演算を並列に行う構成である。
《６》 第((７＋１)／２＋１)-ｑビットから第７-ｑビットまでについて、近傍２量子ビット演算を用いて２ (７−１)／２を法とする量子フーリエ変換を行う量子回路ＬＮＮ−ＱＦＴ３−ＳＳを構成する〔図２０において符号β６で指示する量子回路〕。ＬＮＮ−ＱＦＴ３−ＳＳを行う量子回路は、[ｎが奇数の場合]で説明した方法に従って構成される。
《１》 第１-ｑビットから第((７＋１)／２)-ｑビットまでについて、近傍２量子ビット演算を用いて２(７＋１)／２を法とする量子フーリエ変換ＬＮＮ−ＱＦＴ４−ＳＳを行う量子回路を構成する〔図２０において符号β１で指示する量子回路〕。ＬＮＮ−ＱＦＴ４−ＳＳを行う量子回路は、[ｎが偶数の場合]で説明した方法に従って構成される。
《２》 ｇ＝２，…，(７＋１)／２について、順に、次の演算を行う量子回路とする。第((７＋１)／２−ｇ＋２ｊ)-ｑビットと第((７＋１)／２−ｇ＋２ｊ＋１)-ｑビットに角度２π／２ｇの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する〔図２０において符号β２で指示する量子回路〕。ただし、ｊ＝１，…，ｇ−１とし、ｇごとに全てのｊについての演算を並列に行う構成である。
《３》 ｇ＝(７＋１)／２＋１，…，７について、順に、次の演算を行う量子回路とする。第(ｇ−(７＋１)／２＋２ｊ−２)-ｑビットと第(ｇ−(７＋１)／２＋２ｊ−１)ビットに角度２π／２ｇの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する〔図２０において符号β３で指示する量子回路〕。ただし、ｊ＝１，…，ｎ＋１−ｇとし、ｇごとに全てのｊについての演算を並列に行う構成である。ｇ＝７の場合の最後のＳＷＡＰは、次の《４》の最初のＳＷＡＰと相殺されることになるが図２０では、説明の便宜で敢えて残している。
《４》 ｇ＝７，…，(７＋１)／２＋１について、順に、次の演算を行う量子回路とする。第(ｇ−(７＋１)／２＋２ｊ−２)-ｑビットと第(ｇ−(７＋１)／２＋２ｊ−１)-ｑビットにＳＷＡＰを適用する〔図２０において符号β４で指示する量子回路〕。ただし、ｊ＝１，…，ｎ＋１−ｇとし、ｇごとに全てのｊについての演算を並列に行う構成である。
《５》 ｇ＝(７＋１)／２，…，２について、順に、次の演算を行う量子回路とする。第((７＋１)／２−ｇ＋２ｊ)-ｑビットと第((７＋１)／２−ｇ＋２ｊ＋１)-ｑビットにＳＷＡＰを適用する〔図２０において符号β５で指示する量子回路〕。ただし、ｊ＝１，…，ｇ−１とし、ｇごとに全てのｊについてのて演算を並列に行う構成である。
《６》 第((７＋１)／２＋１)-ｑビットから第７-ｑビットまでについて、近傍２量子ビット演算を用いて２ (７−１)／２を法とする量子フーリエ変換を行う量子回路ＬＮＮ−ＱＦＴ３−ＳＳを構成する〔図２０において符号β６で指示する量子回路〕。ＬＮＮ−ＱＦＴ３−ＳＳを行う量子回路は、[ｎが奇数の場合]で説明した方法に従って構成される。
図２１に、ｎ＝７の場合であるＬＮＮ−ＱＦＴ７−ＳＳの（パターン２）の量子回路（１ｐ）を示す。ＬＮＮ−ＱＦＴ７−ＳＳの（パターン２）の量子回路（１ｐ）は、[ｎが奇数の場合]の（パターン２）で説明した方法に従って、次のように構成される。
《１》 第１-ｑビットから第((７−１)／２)-ｑビットまでについて、近傍２量子ビット演算を用いて２(７−１)／２を法とする量子フーリエ変換ＬＮＮ−ＱＦＴ３−ＳＳを行う量子回路を構成する〔図２１において符号γ１で指示する量子回路〕。ＬＮＮ−ＱＦＴ３−ＳＳを行う量子回路は、[ｎが奇数の場合]で説明した方法に従って構成される。
《２》 ｇ＝２，…，(７＋１)／２について、順に、次の演算を行う量子回路とする。第((７＋１)／２−ｇ＋２ｊ−１)-ｑビットと第((７＋１)／２−ｇ＋２ｊ)-ｑビットに角度２π／２ｇの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する〔図２１において符号γ２で指示する量子回路〕。ただし、ｊ＝１，…，ｇ−１とし、ｇごとに全てのｊについての演算を並列に行う構成とする。
《３》 ｇ＝(７＋１)／２＋１，…，７について、順に、次の演算を行う量子回路とする。第(ｇ−(７＋１)／２＋２ｊ−１)-ｑビットと第(ｇ−(７＋１)／２＋２ｊ)ビットに角度２π／２ｇの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する〔図２１において符号γ３で指示する量子回路〕。ただし、ｊ＝１，…，ｎ＋１−ｇとし、ｇごとに全てのｊについての演算を並列に行う構成とする。ｇ＝７の場合の最後のＳＷＡＰは、次の《４》の最初のＳＷＡＰと相殺されることになるが図２１では、説明の便宜で敢えて残している。
《４》 ｇ＝７，…，(７＋１)／２＋１について、順に、次の演算を行う量子回路とする。第(ｇ−(７＋１)／２＋２ｊ−１)-ｑビットと第(ｇ−(７＋１)／２＋２ｊ)-ｑビットにＳＷＡＰを適用する〔図２１において符号γ４で指示する量子回路〕。ただし、ｊ＝１，…，ｎ＋１−ｇとし、ｇごとに全てのｊについての演算を並列に行う構成とする。
《５》 ｇ＝(７＋１)／２，…，２について、順に、次の演算を行う量子回路とする。第((７＋１)／２−ｇ＋２ｊ−１)-ｑビットと第((７＋１)／２−ｇ＋２ｊ)-ｑビットにＳＷＡＰを適用する〔図２１において符号γ５で指示する量子回路〕。ただし、ｊ＝１，…，ｇ−１とし、ｇごとに全てのｊについての演算を並列に行う構成とする。
《６》 第((７−１)／２＋１)-ｑビットから第７-ｑビットまでについて、近傍２量子ビット演算を用いて２ (７＋１)／２を法とする量子フーリエ変換を行う量子回路ＬＮＮ−ＱＦＴ４−ＳＳを構成する〔図２１において符号γ６で指示する量子回路〕。ＬＮＮ−ＱＦＴ４−ＳＳを行う量子回路は、[ｎが偶数の場合]で説明した方法に従って構成される。
《１》 第１-ｑビットから第((７−１)／２)-ｑビットまでについて、近傍２量子ビット演算を用いて２(７−１)／２を法とする量子フーリエ変換ＬＮＮ−ＱＦＴ３−ＳＳを行う量子回路を構成する〔図２１において符号γ１で指示する量子回路〕。ＬＮＮ−ＱＦＴ３−ＳＳを行う量子回路は、[ｎが奇数の場合]で説明した方法に従って構成される。
《２》 ｇ＝２，…，(７＋１)／２について、順に、次の演算を行う量子回路とする。第((７＋１)／２−ｇ＋２ｊ−１)-ｑビットと第((７＋１)／２−ｇ＋２ｊ)-ｑビットに角度２π／２ｇの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する〔図２１において符号γ２で指示する量子回路〕。ただし、ｊ＝１，…，ｇ−１とし、ｇごとに全てのｊについての演算を並列に行う構成とする。
《３》 ｇ＝(７＋１)／２＋１，…，７について、順に、次の演算を行う量子回路とする。第(ｇ−(７＋１)／２＋２ｊ−１)-ｑビットと第(ｇ−(７＋１)／２＋２ｊ)ビットに角度２π／２ｇの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する〔図２１において符号γ３で指示する量子回路〕。ただし、ｊ＝１，…，ｎ＋１−ｇとし、ｇごとに全てのｊについての演算を並列に行う構成とする。ｇ＝７の場合の最後のＳＷＡＰは、次の《４》の最初のＳＷＡＰと相殺されることになるが図２１では、説明の便宜で敢えて残している。
《４》 ｇ＝７，…，(７＋１)／２＋１について、順に、次の演算を行う量子回路とする。第(ｇ−(７＋１)／２＋２ｊ−１)-ｑビットと第(ｇ−(７＋１)／２＋２ｊ)-ｑビットにＳＷＡＰを適用する〔図２１において符号γ４で指示する量子回路〕。ただし、ｊ＝１，…，ｎ＋１−ｇとし、ｇごとに全てのｊについての演算を並列に行う構成とする。
《５》 ｇ＝(７＋１)／２，…，２について、順に、次の演算を行う量子回路とする。第((７＋１)／２−ｇ＋２ｊ−１)-ｑビットと第((７＋１)／２−ｇ＋２ｊ)-ｑビットにＳＷＡＰを適用する〔図２１において符号γ５で指示する量子回路〕。ただし、ｊ＝１，…，ｇ−１とし、ｇごとに全てのｊについての演算を並列に行う構成とする。
《６》 第((７−１)／２＋１)-ｑビットから第７-ｑビットまでについて、近傍２量子ビット演算を用いて２ (７＋１)／２を法とする量子フーリエ変換を行う量子回路ＬＮＮ−ＱＦＴ４−ＳＳを構成する〔図２１において符号γ６で指示する量子回路〕。ＬＮＮ−ＱＦＴ４−ＳＳを行う量子回路は、[ｎが偶数の場合]で説明した方法に従って構成される。
上記の例では、（パターン１）で構成する場合には、より小さい奇数を法とする量子フーリエ変換を行う量子回路も（パターン１）で構成するとし、（パターン２）で構成する場合には、より小さい奇数を法とする量子フーリエ変換を行う量子回路も（パターン２）で構成するとして説明したが、このような構成に限定する意味ではない。より大きい奇数を法とする量子フーリエ変換を行う量子回路の構成パターンに束縛されることなく、随意のパターンで、より小さい奇数を法とする量子フーリエ変換を行う量子回路を構成できる。
近似でない量子フーリエ変換ＬＮＮ−ＱＦＴ−ＳＳを行う量子回路（１ｐ）から近似量子フーリエ変換ＬＮＮ−ＡＱＦＴ−ＳＳを行う量子回路（１）を構成する方法を説明する。一般的に、近似の閾値ｍはＯ(logｎ)程度とされる。
ＬＮＮ−ＱＦＴ−ＳＳを行う量子回路（１ｐ）において、角度２π／２ｔ（ｔ＞ｍ）の制御フェイズシフトを恒等変換に置換する。これに伴い、角度２π／２ｔ（ｔ＝ｍ）の制御フェイズシフトゲートの直後のＳＷＡＰおよび恒等変換とされた制御フェイズシフトゲートの直後のＳＷＡＰが、量子回路（１ｐ）の構成方法で説明したいずれの場合の《４》および《５》で構成されたＳＷＡＰだけからなる量子回路部分のＳＷＡＰの一部と相殺され、量子回路全体が簡略化されることになる。つまり、角度２π／２ｔ（ｔ＝ｍ）の制御フェイズシフトの直後のＳＷＡＰおよび恒等変換とされた制御フェイズシフトの直後のＳＷＡＰの各演算を行う量子回路Ｃと、量子回路（１ｐ）の構成方法で説明したいずれの場合の《４》および《５》で構成されたＳＷＡＰだけからなる量子回路において量子回路Ｃの鏡像対称の量子回路部分とが相殺される。
この処理で得られた量子回路が、ＬＮＮ−ＡＱＦＴ−ＳＳを行う量子回路（１）である。
この量子回路（１）は、近似の閾値の下限をＯ(logｎ)とし、近傍２量子ビット演算を使って、Ｏ(ｎ)個の計算ステップ数とＯ(ｎlogｎ)個の基本演算で近似量子フーリエ変換を行うものとなっている。
この処理で得られた量子回路が、ＬＮＮ−ＡＱＦＴ−ＳＳを行う量子回路（１）である。
この量子回路（１）は、近似の閾値の下限をＯ(logｎ)とし、近傍２量子ビット演算を使って、Ｏ(ｎ)個の計算ステップ数とＯ(ｎlogｎ)個の基本演算で近似量子フーリエ変換を行うものとなっている。
以下、ＬＮＮ−ＡＱＦＴ−ＳＳを行う量子回路（１）の３つの具体例を示す。
ここでは、図９との比較を容易にする観点から、近似の閾値ｍを５の場合として例示する。
ここでは、図９との比較を容易にする観点から、近似の閾値ｍを５の場合として例示する。
図２２に、図１９に対応したＬＮＮ−ＡＱＦＴ８−ＳＳを行う量子回路（１）を示す。
ｔ＝６，７，８に対応する制御フェイズシフトを恒等変換とみなすことから、符号α２で示した量子回路の最後（最右側）の４つのＳＷＡＰおよび符号α３で示した量子回路の６つのＳＷＡＰが、符号α４で示した量子回路の１０つのＳＷＡＰと相殺される。図９と比較して明らかなように、ＳＷＡＰが相殺されて低減することで、基本演算数が従来に比して低減した量子回路となる。
図２２では、より小さい数を法とする量子フーリエ変換を行う量子回路として、具体的にはＬＮＮ−ＡＱＦＴ４−ＳＳと表記しているが、近似の閾値ｍを５としているから、正確には、ＬＮＮ−ＱＦＴ４を行う量子回路となる。このＬＮＮ−ＱＦＴ４を行う量子回路は、従来と同様に構成されたものであり、近傍２量子ビット演算で構成された近似でない量子フーリエ変換の量子回路（３）である。
仮に、ｍが３であれば、ＬＮＮ−ＡＱＦＴ４−ＳＳを行う量子回路をさらに自己相似的に構成すればよく、このとき、ＬＮＮ−ＡＱＦＴ２−ＳＳを行う量子回路が現われるが、２＜３であるから、ＬＮＮ−ＱＦＴ２を行う量子回路とすればよい。つまり、ＬＮＮ−ＡＱＦＴ８−ＳＳを行う量子回路（１）は、ＬＮＮ−ＱＦＴ２を行う４つの量子回路と、３つのLNN controlled phase shift circuit とで構成される。
ｔ＝６，７，８に対応する制御フェイズシフトを恒等変換とみなすことから、符号α２で示した量子回路の最後（最右側）の４つのＳＷＡＰおよび符号α３で示した量子回路の６つのＳＷＡＰが、符号α４で示した量子回路の１０つのＳＷＡＰと相殺される。図９と比較して明らかなように、ＳＷＡＰが相殺されて低減することで、基本演算数が従来に比して低減した量子回路となる。
図２２では、より小さい数を法とする量子フーリエ変換を行う量子回路として、具体的にはＬＮＮ−ＡＱＦＴ４−ＳＳと表記しているが、近似の閾値ｍを５としているから、正確には、ＬＮＮ−ＱＦＴ４を行う量子回路となる。このＬＮＮ−ＱＦＴ４を行う量子回路は、従来と同様に構成されたものであり、近傍２量子ビット演算で構成された近似でない量子フーリエ変換の量子回路（３）である。
仮に、ｍが３であれば、ＬＮＮ−ＡＱＦＴ４−ＳＳを行う量子回路をさらに自己相似的に構成すればよく、このとき、ＬＮＮ−ＡＱＦＴ２−ＳＳを行う量子回路が現われるが、２＜３であるから、ＬＮＮ−ＱＦＴ２を行う量子回路とすればよい。つまり、ＬＮＮ−ＡＱＦＴ８−ＳＳを行う量子回路（１）は、ＬＮＮ−ＱＦＴ２を行う４つの量子回路と、３つのLNN controlled phase shift circuit とで構成される。
図２３に、図２０に対応したＬＮＮ−ＡＱＦＴ７−ＳＳを行う量子回路（１）を示す。ｔ＝６，７，８に対応する制御フェイズシフトを恒等変換とみなすことから、符号β３で示した量子回路の６つのＳＷＡＰが、符号β４で示した量子回路の６つのＳＷＡＰと相殺される。
図２３では、より小さい数を法とする量子フーリエ変換を行う量子回路として、具体的にはＬＮＮ−ＡＱＦＴ４−ＳＳおよびＬＮＮ−ＡＱＦＴ３−ＳＳと表記しているが、近似の閾値ｍを５としているから、正確には、それぞれＬＮＮ−ＱＦＴ４を行う量子回路とＬＮＮ−ＱＦＴ３を行う量子回路となる。これらのＬＮＮ−ＱＦＴ４を行う量子回路とＬＮＮ−ＱＦＴ３を行う量子回路は、従来と同様に構成されたものであり、近傍２量子ビット演算で構成された近似でない量子フーリエ変換の量子回路（３）である。
仮に、ｍが３であれば、ＬＮＮ−ＡＱＦＴ４−ＳＳを行う量子回路をさらに自己相似的に構成すればよく、このとき、ＬＮＮ−ＡＱＦＴ２−ＳＳを行う量子回路が現われるが、２＜３であるから、ＬＮＮ−ＱＦＴ２を行う量子回路とすればよい。つまり、ＬＮＮ−ＡＱＦＴ７−ＳＳを行う量子回路（１）は、ＬＮＮ−ＱＦＴ２を行う２つの量子回路と、ＬＮＮ−ＱＦＴ３を行う量子回路と、２つのLNN controlled phase shift circuit とで構成される。
図２３では、より小さい数を法とする量子フーリエ変換を行う量子回路として、具体的にはＬＮＮ−ＡＱＦＴ４−ＳＳおよびＬＮＮ−ＡＱＦＴ３−ＳＳと表記しているが、近似の閾値ｍを５としているから、正確には、それぞれＬＮＮ−ＱＦＴ４を行う量子回路とＬＮＮ−ＱＦＴ３を行う量子回路となる。これらのＬＮＮ−ＱＦＴ４を行う量子回路とＬＮＮ−ＱＦＴ３を行う量子回路は、従来と同様に構成されたものであり、近傍２量子ビット演算で構成された近似でない量子フーリエ変換の量子回路（３）である。
仮に、ｍが３であれば、ＬＮＮ−ＡＱＦＴ４−ＳＳを行う量子回路をさらに自己相似的に構成すればよく、このとき、ＬＮＮ−ＡＱＦＴ２−ＳＳを行う量子回路が現われるが、２＜３であるから、ＬＮＮ−ＱＦＴ２を行う量子回路とすればよい。つまり、ＬＮＮ−ＡＱＦＴ７−ＳＳを行う量子回路（１）は、ＬＮＮ−ＱＦＴ２を行う２つの量子回路と、ＬＮＮ−ＱＦＴ３を行う量子回路と、２つのLNN controlled phase shift circuit とで構成される。
図２４に、図２１に対応したＬＮＮ−ＡＱＦＴ７−ＳＳを行う量子回路（１）を示す。ｔ＝６，７，８に対応する制御フェイズシフトを恒等変換とみなすことから、符号β３で示した量子回路の６つのＳＷＡＰが、符号β４で示した量子回路の６つのＳＷＡＰと相殺される。
図２４では、より小さい数を法とする量子フーリエ変換を行う量子回路として、具体的にはＬＮＮ−ＡＱＦＴ３−ＳＳおよびＬＮＮ−ＡＱＦＴ４−ＳＳと表記しているが、近似の閾値ｍを５としているから、正確には、それぞれＬＮＮ−ＱＦＴ３を行う量子回路とＬＮＮ−ＱＦＴ４を行う量子回路となる。これらのＬＮＮ−ＱＦＴ３を行う量子回路とＬＮＮ−ＱＦＴ４を行う量子回路は、従来と同様に構成されたものであり、近傍２量子ビット演算で構成された近似でない量子フーリエ変換の量子回路（３）である。
仮に、ｍが３であれば、ＬＮＮ−ＡＱＦＴ４−ＳＳを行う量子回路をさらに自己相似的に構成すればよく、このとき、ＬＮＮ−ＡＱＦＴ２−ＳＳを行う量子回路が現われるが、２＜３であるから、ＬＮＮ−ＱＦＴ２を行う量子回路とすればよい。つまり、ＬＮＮ−ＡＱＦＴ７−ＳＳを行う量子回路（１）は、ＬＮＮ−ＱＦＴ２を行う２つの量子回路と、ＬＮＮ−ＱＦＴ３を行う量子回路と、２つのLNN controlled phase shift circuit とで構成される。
図２４では、より小さい数を法とする量子フーリエ変換を行う量子回路として、具体的にはＬＮＮ−ＡＱＦＴ３−ＳＳおよびＬＮＮ−ＡＱＦＴ４−ＳＳと表記しているが、近似の閾値ｍを５としているから、正確には、それぞれＬＮＮ−ＱＦＴ３を行う量子回路とＬＮＮ−ＱＦＴ４を行う量子回路となる。これらのＬＮＮ−ＱＦＴ３を行う量子回路とＬＮＮ−ＱＦＴ４を行う量子回路は、従来と同様に構成されたものであり、近傍２量子ビット演算で構成された近似でない量子フーリエ変換の量子回路（３）である。
仮に、ｍが３であれば、ＬＮＮ−ＡＱＦＴ４−ＳＳを行う量子回路をさらに自己相似的に構成すればよく、このとき、ＬＮＮ−ＡＱＦＴ２−ＳＳを行う量子回路が現われるが、２＜３であるから、ＬＮＮ−ＱＦＴ２を行う量子回路とすればよい。つまり、ＬＮＮ−ＡＱＦＴ７−ＳＳを行う量子回路（１）は、ＬＮＮ−ＱＦＴ２を行う２つの量子回路と、ＬＮＮ−ＱＦＴ３を行う量子回路と、２つのLNN controlled phase shift circuit とで構成される。
ここで、ＬＮＮ−ＱＦＴ４を行う量子回路を図２５に、ＬＮＮ−ＱＦＴ３を行う量子回路を図２６に示す。これらの量子回路（３）の構成は、背景技術で既に述べたとおりである。
〔量子演算方法〕
次に、本発明の量子回路（１）における量子演算方法について説明する。
量子回路（１）の構成方法から明らかなとおり、一般的には、分解の過程で奇数個のｑビットに対する量子フーリエ変換を行う量子回路が生じるから、ｎ個のｑビットに対する本発明の量子回路を一意に決定することができない。
そこで、ここでは一例として、図２２に示したＬＮＮ−ＡＱＦＴ８−ＳＳを行う量子回路（１）における量子演算方法について説明する。入力状態は|ｂ７ｂ６…ｂ１ｂ０〉である。|ｂ７〉は第１-ｑビットの状態であり、|ｂ６〉は第２-ｑビットの状態であり、中略、|ｂ１〉は第７-ｑビットの状態であり、|ｂ０〉は第８-ｑビットの状態である。
一般的に、量子回路に従った演算は、入力側から出力側に向かって時系列に行われ、並列演算可能な演算は１計算ステップで全て演算される。
次に、本発明の量子回路（１）における量子演算方法について説明する。
量子回路（１）の構成方法から明らかなとおり、一般的には、分解の過程で奇数個のｑビットに対する量子フーリエ変換を行う量子回路が生じるから、ｎ個のｑビットに対する本発明の量子回路を一意に決定することができない。
そこで、ここでは一例として、図２２に示したＬＮＮ−ＡＱＦＴ８−ＳＳを行う量子回路（１）における量子演算方法について説明する。入力状態は|ｂ７ｂ６…ｂ１ｂ０〉である。|ｂ７〉は第１-ｑビットの状態であり、|ｂ６〉は第２-ｑビットの状態であり、中略、|ｂ１〉は第７-ｑビットの状態であり、|ｂ０〉は第８-ｑビットの状態である。
一般的に、量子回路に従った演算は、入力側から出力側に向かって時系列に行われ、並列演算可能な演算は１計算ステップで全て演算される。
ステップＳ１
第１-ｑビットにアダマール変換を適用する。
第１-ｑビットにアダマール変換を適用する。
ステップＳ２
第１-ｑビットと第２-ｑビットに角度２π／２２の制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。
第１-ｑビットと第２-ｑビットに角度２π／２２の制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。
ステップＳ３
第１-ｑビットにアダマール変換を適用する。第２-ｑビットと第３-ｑビットに角度２π／２３の制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。ただし、これらの演算を並列に行う。
第１-ｑビットにアダマール変換を適用する。第２-ｑビットと第３-ｑビットに角度２π／２３の制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。ただし、これらの演算を並列に行う。
ステップＳ４
第１-ｑビットと第２-ｑビットに角度２π／２２の制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。第３-ｑビットと第４-ｑビットに角度２π／２４の制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。ただし、これらの演算を並列に行う。
第１-ｑビットと第２-ｑビットに角度２π／２２の制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。第３-ｑビットと第４-ｑビットに角度２π／２４の制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。ただし、これらの演算を並列に行う。
ステップＳ５
第１-ｑビットにアダマール変換を適用する。第２-ｑビットと第３-ｑビットに角度２π／２３の制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。ただし、これらの演算を並列に行う。
第１-ｑビットにアダマール変換を適用する。第２-ｑビットと第３-ｑビットに角度２π／２３の制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。ただし、これらの演算を並列に行う。
ステップＳ６
第１-ｑビットと第２-ｑビットに角度２π／２２の制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。
第１-ｑビットと第２-ｑビットに角度２π／２２の制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。
ステップＳ７
第１-ｑビットにアダマール変換を適用する。
第１-ｑビットにアダマール変換を適用する。
ステップＳ８
第１-ｑビットと第２-ｑビットにＳＷＡＰを適用する。
第１-ｑビットと第２-ｑビットにＳＷＡＰを適用する。
ステップＳ９
第２-ｑビットと第３-ｑビットにＳＷＡＰを適用する。
第２-ｑビットと第３-ｑビットにＳＷＡＰを適用する。
ステップＳ１０
第１-ｑビットと第２-ｑビットにＳＷＡＰを適用する。第３-ｑビットと第４-ｑビットにＳＷＡＰを適用する。ただし、これらの演算を並列に行う。
第１-ｑビットと第２-ｑビットにＳＷＡＰを適用する。第３-ｑビットと第４-ｑビットにＳＷＡＰを適用する。ただし、これらの演算を並列に行う。
ステップＳ１１
第２-ｑビットと第３-ｑビットにＳＷＡＰを適用する。
第２-ｑビットと第３-ｑビットにＳＷＡＰを適用する。
ステップＳ１２
第１-ｑビットと第２-ｑビットにＳＷＡＰを適用する。
第１-ｑビットと第２-ｑビットにＳＷＡＰを適用する。
ステップＳ１３
第４-ｑビットと第５-ｑビットに角度２π／２２の制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。
第４-ｑビットと第５-ｑビットに角度２π／２２の制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。
ステップＳ１４
第３-ｑビットと第４-ｑビットに角度２π／２３の制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。第５-ｑビットと第６-ｑビットに角度２π／２３の制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。ただし、これらの演算を並列に行う。
第３-ｑビットと第４-ｑビットに角度２π／２３の制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。第５-ｑビットと第６-ｑビットに角度２π／２３の制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。ただし、これらの演算を並列に行う。
ステップＳ１５
第２-ｑビットと第３-ｑビットに角度２π／２４の制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。第４-ｑビットと第５-ｑビットに角度２π／２４の制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。第６-ｑビットと第７-ｑビットに角度２π／２４の制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。ただし、これらの演算を並列に行う。
第２-ｑビットと第３-ｑビットに角度２π／２４の制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。第４-ｑビットと第５-ｑビットに角度２π／２４の制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。第６-ｑビットと第７-ｑビットに角度２π／２４の制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。ただし、これらの演算を並列に行う。
ステップＳ１６
第１-ｑビットと第２-ｑビットに角度２π／２５の制御フェイズシフトを適用する。第３-ｑビットと第４-ｑビットに角度２π／２５の制御フェイズシフトを適用する。第５-ｑビットと第６-ｑビットに角度２π／２５の制御フェイズシフトを適用する。第７-ｑビットと第８-ｑビットに角度２π／２５の制御フェイズシフトを適用する。ただし、これらの演算を並列に行う。
第１-ｑビットと第２-ｑビットに角度２π／２５の制御フェイズシフトを適用する。第３-ｑビットと第４-ｑビットに角度２π／２５の制御フェイズシフトを適用する。第５-ｑビットと第６-ｑビットに角度２π／２５の制御フェイズシフトを適用する。第７-ｑビットと第８-ｑビットに角度２π／２５の制御フェイズシフトを適用する。ただし、これらの演算を並列に行う。
ステップＳ１７
第２-ｑビットと第３-ｑビットにＳＷＡＰを適用する。第４-ｑビットと第５-ｑビットにＳＷＡＰを適用する。第６-ｑビットと第７-ｑビットにＳＷＡＰを適用する。ただし、これらの演算を並列に行う。
第２-ｑビットと第３-ｑビットにＳＷＡＰを適用する。第４-ｑビットと第５-ｑビットにＳＷＡＰを適用する。第６-ｑビットと第７-ｑビットにＳＷＡＰを適用する。ただし、これらの演算を並列に行う。
ステップＳ１８
第３-ｑビットと第４-ｑビットにＳＷＡＰを適用する。第５-ｑビットと第６-ｑビットにＳＷＡＰを適用する。ただし、これらの演算を並列に行う。
第３-ｑビットと第４-ｑビットにＳＷＡＰを適用する。第５-ｑビットと第６-ｑビットにＳＷＡＰを適用する。ただし、これらの演算を並列に行う。
ステップＳ１９
第４-ｑビットと第５-ｑビットにＳＷＡＰを適用する。
第４-ｑビットと第５-ｑビットにＳＷＡＰを適用する。
ステップＳ２０
第５-ｑビットにアダマール変換を適用する。
第５-ｑビットにアダマール変換を適用する。
ステップＳ２１
第５-ｑビットと第６-ｑビットに角度２π／２２の制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。
第５-ｑビットと第６-ｑビットに角度２π／２２の制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。
ステップＳ２２
第５-ｑビットにアダマール変換を適用する。第６-ｑビットと第７-ｑビットに角度２π／２３の制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。ただし、これらの演算を並列に行う。
第５-ｑビットにアダマール変換を適用する。第６-ｑビットと第７-ｑビットに角度２π／２３の制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。ただし、これらの演算を並列に行う。
ステップＳ２３
第５-ｑビットと第６-ｑビットに角度２π／２２の制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。第７-ｑビットと第８-ｑビットに角度２π／２４の制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。ただし、これらの演算を並列に行う。
第５-ｑビットと第６-ｑビットに角度２π／２２の制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。第７-ｑビットと第８-ｑビットに角度２π／２４の制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。ただし、これらの演算を並列に行う。
ステップＳ２４
第５-ｑビットにアダマール変換を適用する。第６-ｑビットと第７-ｑビットに角度２π／２３の制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。ただし、これらの演算を並列に行う。
第５-ｑビットにアダマール変換を適用する。第６-ｑビットと第７-ｑビットに角度２π／２３の制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。ただし、これらの演算を並列に行う。
ステップＳ２５
第５-ｑビットと第６-ｑビットに角度２π／２２の制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。
第５-ｑビットと第６-ｑビットに角度２π／２２の制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する。
ステップＳ２６
第５-ｑビットにアダマール変換を適用する。
第５-ｑビットにアダマール変換を適用する。
ステップＳ２７
第５-ｑビットと第６-ｑビットにＳＷＡＰを適用する。
第５-ｑビットと第６-ｑビットにＳＷＡＰを適用する。
ステップＳ２８
第６-ｑビットと第７-ｑビットにＳＷＡＰを適用する。
第６-ｑビットと第７-ｑビットにＳＷＡＰを適用する。
ステップＳ２９
第５-ｑビットと第６-ｑビットにＳＷＡＰを適用する。第７-ｑビットと第８-ｑビットにＳＷＡＰを適用する。ただし、これらの演算を並列に行う。
第５-ｑビットと第６-ｑビットにＳＷＡＰを適用する。第７-ｑビットと第８-ｑビットにＳＷＡＰを適用する。ただし、これらの演算を並列に行う。
ステップＳ３０
第６-ｑビットと第７-ｑビットにＳＷＡＰを適用する。
第６-ｑビットと第７-ｑビットにＳＷＡＰを適用する。
ステップＳ３１
第５-ｑビットと第６-ｑビットにＳＷＡＰを適用する。
第５-ｑビットと第６-ｑビットにＳＷＡＰを適用する。
〔量子演算装置〕
次に、本発明の量子回路に則って近似量子フーリエ変換を行う量子演算装置について説明する。本発明の量子演算装置は、本発明の量子回路から明らかなように、ｎより小さな数を法とする量子フーリエ変換を行う量子演算部、ＳＷＡＰ演算を行う量子演算部、あるいは従来的な量子回路（３）で量子フーリエ変換を行う量子演算部で構成される。さらに、これらの量子演算部は、１量子ビット演算を行う量子演算部および近傍２量子ビット演算を行う量子演算部からなる。つまり、本発明の量子回路に示した量子ゲートが、量子演算装置の量子演算部に相当する。
次に、本発明の量子回路に則って近似量子フーリエ変換を行う量子演算装置について説明する。本発明の量子演算装置は、本発明の量子回路から明らかなように、ｎより小さな数を法とする量子フーリエ変換を行う量子演算部、ＳＷＡＰ演算を行う量子演算部、あるいは従来的な量子回路（３）で量子フーリエ変換を行う量子演算部で構成される。さらに、これらの量子演算部は、１量子ビット演算を行う量子演算部および近傍２量子ビット演算を行う量子演算部からなる。つまり、本発明の量子回路に示した量子ゲートが、量子演算装置の量子演算部に相当する。
量子演算装置は、量子コンピュータ単体で実現できる。量子コンピュータの実現する物理系としては、例えば、イオントラップを用いる方法（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.」等参照。）によって生成された複数個の単一光子を用いる。この場合、各量子ビットの初期量子状態は、例えば、他の演算の量子回路による操作によって得られたものを用いる。また、パラメトリックダウンコンバージョン等によって生成された単一光子に、ビームスプリッタや偏光回転素子等によって実現されるウォルシューアダマール変換、ＣＮＯＴ、回転等の操作を行い、上述の初期量子状態を生成することとしてもよい。
その他、上記の文献に記載された方法で量子ビットを用意することとしてもよい。
イオントラップ量子コンピュータでは、例えば、イオンの基底状態と励起状態を利用して量子ビットを実現する。また、核スピンを量子ビットとして用いる場合には、例えば、「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)、http://www.snf.unsw.edu.au/、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. 方式によってＣＮＯＴ演算を実現する。また、核スピンを量子ビットとして用いる場合には、例えば、所定の電磁波パルスを量子ビットに印加することによってＣＮＯＴ演算を実現できる。
その他、上記の文献に記載された方法でＣＮＯＴ演算を実現してもよい。
イオントラップ量子コンピュータでは、例えば、イオンを直線上に並べ、各イオンに狙いを定めたレーザービーム照射によってＣＮＯＴ演算を実現する。また、量子ビットとして光子の偏光を用いる場合には、例えば、偏光ビームスプリッタ等を用い、「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. 方式によってＣＮＯＴ演算を実現する。また、核スピンを量子ビットとして用いる場合には、例えば、所定の電磁波パルスを量子ビットに印加することによってＣＮＯＴ演算を実現できる。
その他、上記の文献に記載された方法でＣＮＯＴ演算を実現してもよい。
＜量子ビット単体操作＞
イオントラップ量子コンピュータでは、例えば、イオンを直線上に並べ、各イオンに狙いを定めたレーザービーム照射によって量子ビット単体の操作を実現する。核スピンを量子ビットとして用いる場合には、電磁波パルスやレーザービーム照射によって各処理を実現する。また、量子ビットとして光子の偏光を用いる場合には、例えば、偏光回転素子等によって実現する。
イオントラップ量子コンピュータでは、例えば、イオンを直線上に並べ、各イオンに狙いを定めたレーザービーム照射によって量子ビット単体の操作を実現する。核スピンを量子ビットとして用いる場合には、電磁波パルスやレーザービーム照射によって各処理を実現する。また、量子ビットとして光子の偏光を用いる場合には、例えば、偏光回転素子等によって実現する。
なお、本発明は上述の実施の形態に限定されるものではなく、その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
ところで、本発明の量子回路に則って量子演算を行う手順自体は、古典コンピュータで決定することができる。
つまり、本発明の量子回路に則って量子演算を行う手順は、本発明の量子回路を入力側から出力側に向かって順に行う各計算ステップであるから、本発明の量子回路を構成した後、この量子回路の入力側から出力側に向かって順に行う各計算ステップを、量子演算を行う手順として決定できる。
つまり、本発明の量子回路に則って量子演算を行う手順は、本発明の量子回路を入力側から出力側に向かって順に行う各計算ステップであるから、本発明の量子回路を構成した後、この量子回路の入力側から出力側に向かって順に行う各計算ステップを、量子演算を行う手順として決定できる。
具体的には、例えば図１９で示した量子回路を例とすると、符号α１〜α６の各量子回路における量子演算を行う手順をそれぞれ決定し（この手順は、上述した符号α１〜α６の各量子回路の構成方法そのものである。ただし、符号α１およびα６の各量子回路については自己相似的に分解して繰り返しの構成となる。いずれにしても以上において説明したとおりである。）、さらに、角度２π／２ｔ（ｔ＞ｍ）の制御フェイズシフトを恒等変換に置換して、相殺されるＳＷＡＰの演算手順を除外し、各量子回路で決定された量子演算を行う手順を、完成した量子回路（この例では図２２に相当する。）の入力側から出力側に向かって順に手順を並べることで、本発明の量子回路に則って量子演算を行う手順を決定できる。ただし、１計算ステップで並行演算可能であれば、これらの演算を並行するものを１手順とすればよい。
換言すれば、この古典コンピュータは、図２７から図３２に示したステップＳ１〜ステップＳ３１の手順を決定して出力するものといえる。
換言すれば、この古典コンピュータは、図２７から図３２に示したステップＳ１〜ステップＳ３１の手順を決定して出力するものといえる。
このような古典コンピュータ、つまり、本発明の近似量子フーリエ変換を行う量子回路における量子演算の手順を決定する近似量子フーリエ変換演算手順決定装置は、いわゆる古典的な装置構成で実現される。例えばパーソナルコンピュータに例示されるように、記憶装置（例えばＲＡＭ、ＲＯＭやハードディスク）、演算処理装置（例えばＣＰＵ）、入力・出力装置（例えばキーボード、ディスプレイ）、これらの装置間でデータのやり取りが可能に接続するバスなどを備えた古典コンピュータによって実現することができる。
この場合、例えば図１９の例で符号α１〜α６の各量子回路における量子演算を行う手順をそれぞれ決定するための各プログラム、角度２π／２ｔ（ｔ＞ｍ）の制御フェイズシフトを恒等変換に置換して、相殺されるＳＷＡＰの演算手順を除外するためのプログラム、各量子回路で決定された量子演算を行う手順を完成した量子回路（この例では図２２に相当する。）の入力側から出力側に向かって順に手順を並べるためのプログラム記憶装置に記憶しておき、必要に応じて演算処理装置がプログラムを読み込んで解釈実行することで、符号α１〜α６の各量子回路における量子演算を行う手順をそれぞれ決定する各機能、角度２π／２ｔ（ｔ＞ｍ）の制御フェイズシフトを恒等変換に置換して、相殺されるＳＷＡＰの演算手順を除外する機能、各量子回路で決定された量子演算を行う手順を完成した量子回路の入力側から出力側に向かって順に手順を並べる機能を実現する。また各プログラムは、コンピュータ読み取り可能な記録媒体（例えばＣＤ−Ｒ、ＤＶＤ−ＲＡＭ、ＭＯ）に記録することもできる。
この場合、例えば図１９の例で符号α１〜α６の各量子回路における量子演算を行う手順をそれぞれ決定するための各プログラム、角度２π／２ｔ（ｔ＞ｍ）の制御フェイズシフトを恒等変換に置換して、相殺されるＳＷＡＰの演算手順を除外するためのプログラム、各量子回路で決定された量子演算を行う手順を完成した量子回路（この例では図２２に相当する。）の入力側から出力側に向かって順に手順を並べるためのプログラム記憶装置に記憶しておき、必要に応じて演算処理装置がプログラムを読み込んで解釈実行することで、符号α１〜α６の各量子回路における量子演算を行う手順をそれぞれ決定する各機能、角度２π／２ｔ（ｔ＞ｍ）の制御フェイズシフトを恒等変換に置換して、相殺されるＳＷＡＰの演算手順を除外する機能、各量子回路で決定された量子演算を行う手順を完成した量子回路の入力側から出力側に向かって順に手順を並べる機能を実現する。また各プログラムは、コンピュータ読み取り可能な記録媒体（例えばＣＤ−Ｒ、ＤＶＤ−ＲＡＭ、ＭＯ）に記録することもできる。
本発明の利用分野としては、例えば、位相推定や量子暗号などに用いられる。
１ 近似量子フーリエ変換を行う量子回路
Claims (3)
- 近似の閾値を正整数ｎよりも小さい正整数ｍとし、２ｎを法とする近似量子フーリエ変換を行う量子回路であって、
ｎ個のｑビットである第１-ｑビット、…、第ｎ-ｑビットに対して、
ｎが偶数の場合、
《１》第１-ｑビットから第(ｎ／２)-ｑビットまでについて、近傍２量子ビット演算で構成した２ｎ／２を法とする量子フーリエ変換を行う量子回路を構成し、
《２》ｇ＝２，…，ｎ／２＋１について、順に、第(ｎ／２−ｇ＋２ｊ)-ｑビットと第(ｎ／２−ｇ＋２ｊ＋１)-ｑビットに角度２π／２ｇの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する演算を行う量子回路を構成し〔ただし、ｊ＝１，…，ｇ−１とし、ｇごとに全てのｊについての演算を並列に行う量子回路とする。〕、
《３》ｇ＝ｎ／２＋２，…，ｎについて、順に、第(ｇ−ｎ／２＋２ｊ−２)-ｑビットと第(ｇ−ｎ／２＋２ｊ−１)-ｑビットに角度２π／２ｇの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する演算を行う量子回路を構成し〔ただし、ｊ＝１，…，ｎ＋１−ｇとし、ｇごとに全てのｊについての演算を並列に行う量子回路とする。〕、
《４》ｇ＝ｎ，…，ｎ／２＋２について、順に、第(ｇ−ｎ／２＋２ｊ−２)-ｑビットと第(ｇ−ｎ／２＋２ｊ−１)-ｑビットにＳＷＡＰを適用する演算を行うＳＷＡＰ量子回路を構成し〔ただし、ｊ＝１，…，ｎ＋１−ｇとし、ｇごとに全てのｊについての演算を並列に行う量子回路とする。〕、
《５》ｇ＝ｎ／２＋１，…，２について、順に、第(ｎ／２−ｇ＋２ｊ)-ｑビットと第(ｎ／２−ｇ＋２ｊ＋１)-ｑビットにＳＷＡＰを適用する演算を行うＳＷＡＰ量子回路を構成し〔ただし、ｊ＝１，…，ｇ−１とし、ｇごとに全てのｊについての演算を並列に行う量子回路とする。〕、
《６》第(ｎ／２＋１)-ｑビットから第ｎ-ｑビットまでについて、近傍２量子ビット演算で構成した２ｎ／２を法とする量子フーリエ変換を行う量子回路を構成し、
ｎが奇数の場合、
パターン１またはパターン２のいずれかで、
（パターン１）
《１》第１-ｑビットから第((ｎ＋１)／２)-ｑビットまでについて、近傍２量子ビット演算で構成した２(ｎ＋１)／２を法とする量子フーリエ変換を行う量子回路を構成し、
《２》ｇ＝２，…，(ｎ＋１)／２について、順に、第((ｎ＋１)／２−ｇ＋２ｊ)-ｑビットと第((ｎ＋１)／２−ｇ＋２ｊ＋１)-ｑビットに角度２π／２ｇの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する演算を行う量子回路を構成し〔ただし、ｊ＝１，…，ｇ−１とし、ｇごとに全てのｊについての演算を並列に行う量子回路とする。〕、
《３》ｇ＝(ｎ＋１)／２＋１，…，ｎについて、順に、第(ｇ−(ｎ＋１)／２＋２ｊ−２)-ｑビットと第(ｇ−(ｎ＋１)／２＋２ｊ−１)ビットに角度２π／２ｇの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する演算を行う量子回路を構成し〔ただし、ｊ＝１，…，ｎ＋１−ｇとし、ｇごとに全てのｊについての演算を並列に行う量子回路とする。〕、
《４》ｇ＝ｎ，…，(ｎ＋１)／２＋１について、順に、第(ｇ−(ｎ＋１)／２＋２ｊ−２)-ｑビットと第(ｇ−(ｎ＋１)／２＋２ｊ−１)-ｑビットにＳＷＡＰを適用する演算を行うＳＷＡＰ量子回路を構成し〔ただし、ｊ＝１，…，ｎ＋１−ｇとし、ｇごとに全てのｊについての演算を並列に行う量子回路とする。〕、
《５》ｇ＝(ｎ＋１)／２，…，２について、順に、第((ｎ＋１)／２−ｇ＋２ｊ)-ｑビットと第((ｎ＋１)／２−ｇ＋２ｊ＋１)-ｑビットにＳＷＡＰを適用する演算を行うＳＷＡＰ量子回路を構成し〔ただし、ｊ＝１，…，ｇ−１とし、ｇごとに全てのｊについての演算を並列に行う量子回路とする。〕、
《６》第((ｎ＋１)／２＋１)-ｑビットから第ｎ-ｑビットまでについて、近傍２量子ビット演算で構成した２ (ｎ−１)／２を法とする量子フーリエ変換を行う量子回路を構成し、
（パターン２）
《１》第１-ｑビットから第((ｎ−１)／２)-ｑビットまでについて、近傍２量子ビット演算で構成した２(ｎ−１)／２を法とする量子フーリエ変換を行う量子回路を構成し、
《２》ｇ＝２，…，(ｎ＋１)／２について、順に、第((ｎ＋１)／２−ｇ＋２ｊ−１)-ｑビットと第((ｎ＋１)／２−ｇ＋２ｊ)-ｑビットに角度２π／２ｇの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する演算を行う量子回路を構成し〔ただし、ｊ＝１，…，ｇ−１とし、ｇごとに全てのｊについての演算を並列に行う量子回路とする。〕、
《３》ｇ＝(ｎ＋１)／２＋１，…，ｎについて、順に、第(ｇ−(ｎ＋１)／２＋２ｊ−１)-ｑビットと第(ｇ−(ｎ＋１)／２＋２ｊ)ビットに角度２π／２ｇの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する演算を行う量子回路を構成し〔ただし、ｊ＝１，…，ｎ＋１−ｇとし、ｇごとに全てのｊについての演算を並列に行う量子回路とする。〕、
《４》ｇ＝ｎ，…，(ｎ＋１)／２＋１について、順に、第(ｇ−(ｎ＋１)／２＋２ｊ−１)-ｑビットと第(ｇ−(ｎ＋１)／２＋２ｊ)-ｑビットにＳＷＡＰを適用する演算を行うＳＷＡＰ量子回路を構成し〔ただし、ｊ＝１，…，ｎ＋１−ｇとし、ｇごとに全てのｊについての演算を並列に行う量子回路とする。〕、
《５》ｇ＝(ｎ＋１)／２，…，２について、順に、第((ｎ＋１)／２−ｇ＋２ｊ−１)-ｑビットと第((ｎ＋１)／２−ｇ＋２ｊ)-ｑビットにＳＷＡＰを適用する演算を行うＳＷＡＰ量子回路を構成し〔ただし、ｊ＝１，…，ｇ−１とし、ｇごとに全てのｊについての演算を並列に行う量子回路とする。〕、
《６》第((ｎ−１)／２＋１)-ｑビットから第ｎ-ｑビットまでについて、近傍２量子ビット演算で構成した２ (ｎ＋１)／２を法とする量子フーリエ変換を行う量子回路を構成し、
ｎ＝１の場合、
第１-ｑビットにアダマール変換を適用する量子回路を構成し、
上記の手順で構成された量子回路において、２ｎより小さく２ｍより大きい数２Ｂを法とする量子フーリエ変換の量子回路については、このＢを新たなｎと看做して、上記の場合分けに従った手順で量子回路を構成し、
２ｍ以下の数を法とする量子フーリエ変換を行う量子回路Ａについては、
量子回路Ａへ入力されるＮ個のｑビットである第１-ｑビット、…、第Ｎ-ｑビットに対して、
《１》ｇ＝１，…，Ｎについて、順に、
ｇ＝１の場合、
第１-ｑビットにアダマール変換を適用する演算を行う量子回路を構成し、
ｇが３以上の奇数の場合、
第１-ｑビットにアダマール変換を適用する演算を行う量子回路を構成し、
第(ｊ−１)-ｑビットと第ｊ-ｑビットに角度２π／２ｊの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する演算を行う量子回路を構成し〔ただし、ｊは３からｇまでの奇数とし、ｇごとに第１-ｑビットに対するアダマール変換および全てのｊについての演算を並列に行う量子回路とする。〕、
ｇが偶数の場合、
第(ｊ−１)-ｑビットと第ｊ-ｑビットに角度２π／２ｊの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する演算を行う量子回路を構成し〔ただし、ｊは２からｇまでの偶数とし、ｇごとに全てのｊについての演算を並列に行う量子回路とする。〕、
《２》ｇ＝Ｎ−１，…，１について、順に、
ｇ＝１の場合、
第１-ｑビットにアダマール変換を適用する演算を行う量子回路を構成し、
ｇが３以上の奇数の場合、
第１-ｑビットにアダマール変換を適用する演算を行う量子回路を構成し、
第(ｊ−１)-ｑビットと第ｊ-ｑビットに角度２π／２ｊの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する演算を行う量子回路を構成し〔ただし、ｊは３からｇまでの奇数とし、ｇごとに第１-ｑビットに対するアダマール変換および全てのｊについての演算を並列に行う量子回路とする。〕、
ｇが偶数の場合、
第(ｊ−１)-ｑビットと第ｊ-ｑビットに角度２π／２ｊの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する演算を行う量子回路を構成し〔ただし、ｊは２からｇまでの偶数とし、ｇごとに全てのｊについての演算を並列に行う量子回路とする。〕、
《３》ｇ＝１，…，Ｎ−１について、順に、
ｇが奇数の場合、
第ｊ-ｑビットと第(ｊ＋１)-ｑビットにＳＷＡＰを適用する演算を行う量子回路を構成し〔ただし、ｊは１からｇまでの奇数とし、ｇごとに全てのｊについてのＳＷＡＰを並列に行う量子回路とする。〕、
ｇが偶数の場合、
第ｊ-ｑビットと第(ｊ＋１)-ｑビットにＳＷＡＰを適用する演算を行う量子回路を構成し〔ただし、ｊは２からｇまでの偶数とし、ｇごとに全てのｊについてのＳＷＡＰを並列に行う量子回路とする。〕、
《４》ｇ＝Ｎ−２，…，１について、順に、
ｇが奇数の場合、
第ｊ-ｑビットと第(ｊ＋１)-ｑビットにＳＷＡＰを適用する演算を行う量子回路を構成し〔ただし、ｊは１からｇまでの奇数とし、ｇごとに全てのｊについてのＳＷＡＰを並列に行う量子回路とする。〕、
ｇが偶数の場合、
第ｊ-ｑビットと第(ｊ＋１)-ｑビットにＳＷＡＰを適用する演算を行う量子回路を構成し〔ただし、ｊは２からｇまでの偶数とし、ｇごとに全てのｊについてのＳＷＡＰを並列に行う量子回路とする。〕、
これまでの手順で構成された量子回路において、角度２π／２ｔ（ｔ＞ｍ）の制御フェイズシフトを恒等変換に置換し、
角度２π／２ｔ（ｔ＝ｍ）の制御フェイズシフトの直後のＳＷＡＰおよび恒等変換とされた制御フェイズシフトの直後のＳＷＡＰの各演算を行う量子回路Ｃと、上記ＳＷＡＰ量子回路において量子回路Ｃの鏡像対称の量子回路部分とを相殺して構成された
ことを特徴とする近似量子フーリエ変換を行う量子回路。 - 請求項１に記載の近似量子フーリエ変換を行う量子回路に則り、
入力された第１-ｑビットの状態|ｂｎ−１〉，…，第ｎ-ｑビットの状態|ｂ０〉に対して近似量子フーリエ変換を行う
ことを特徴とする近似量子フーリエ変換演算方法。 - 近似の閾値を正整数ｎよりも小さい正整数ｍとし、２ｎを法とする近似量子フーリエ変換を行う近似量子フーリエ変換演算装置が演算対象とするｎ個のｑビットである第１-ｑビット、…、第ｎ-ｑビットに対して、
ｎが偶数の場合、
《１》第１-ｑビットから第(ｎ／２)-ｑビットまでについて、近傍２量子ビット演算で構成した２ｎ／２を法とする量子フーリエ変換を行う量子演算部を備え、
《２》ｇ＝２，…，ｎ／２＋１について、順に、第(ｎ／２−ｇ＋２ｊ)-ｑビットと第(ｎ／２−ｇ＋２ｊ＋１)-ｑビットに角度２π／２ｇの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する演算を行う量子演算部を備え〔ただし、ｊ＝１，…，ｇ−１とし、ｇごとに全てのｊについての演算を並列に行うものとする。〕、
《３》ｇ＝ｎ／２＋２，…，ｎについて、順に、第(ｇ−ｎ／２＋２ｊ−２)-ｑビットと第(ｇ−ｎ／２＋２ｊ−１)-ｑビットに角度２π／２ｇの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する演算を行う量子演算部を備え〔ただし、ｊ＝１，…，ｎ＋１−ｇとし、ｇごとに全てのｊについての演算を並列に行うものとする。〕、
《４》ｇ＝ｎ，…，ｎ／２＋２について、順に、第(ｇ−ｎ／２＋２ｊ−２)-ｑビットと第(ｇ−ｎ／２＋２ｊ−１)-ｑビットにＳＷＡＰを適用する演算を行うＳＷＡＰ演算部を備え〔ただし、ｊ＝１，…，ｎ＋１−ｇとし、ｇごとに全てのｊについての演算を並列に行うものとする。〕、
《５》ｇ＝ｎ／２＋１，…，２について、順に、第(ｎ／２−ｇ＋２ｊ)-ｑビットと第(ｎ／２−ｇ＋２ｊ＋１)-ｑビットにＳＷＡＰを適用する演算を行うＳＷＡＰ演算部を備え〔ただし、ｊ＝１，…，ｇ−１とし、ｇごとに全てのｊについての演算を並列に行うものとする。〕、
《６》第(ｎ／２＋１)-ｑビットから第ｎ-ｑビットまでについて、近傍２量子ビット演算で構成した２ｎ／２を法とする量子フーリエ変換を行う量子演算部を備え、
ｎが奇数の場合、
パターン１またはパターン２のいずれかで、
（パターン１）
《１》第１-ｑビットから第((ｎ＋１)／２)-ｑビットまでについて、近傍２量子ビット演算で構成した２(ｎ＋１)／２を法とする量子フーリエ変換を行う量子演算部を備え、
《２》ｇ＝２，…，(ｎ＋１)／２について、順に、第((ｎ＋１)／２−ｇ＋２ｊ)-ｑビットと第((ｎ＋１)／２−ｇ＋２ｊ＋１)-ｑビットに角度２π／２ｇの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する演算を行う量子演算部を備え〔ただし、ｊ＝１，…，ｇ−１とし、ｇごとに全てのｊについての演算を並列に行うものとする。〕、
《３》ｇ＝(ｎ＋１)／２＋１，…，ｎについて、順に、第(ｇ−(ｎ＋１)／２＋２ｊ−２)-ｑビットと第(ｇ−(ｎ＋１)／２＋２ｊ−１)ビットに角度２π／２ｇの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する演算を行う量子演算部を備え〔ただし、ｊ＝１，…，ｎ＋１−ｇとし、ｇごとに全てのｊについての演算を並列に行うものとする。〕、
《４》ｇ＝ｎ，…，(ｎ＋１)／２＋１について、順に、第(ｇ−(ｎ＋１)／２＋２ｊ−２)-ｑビットと第(ｇ−(ｎ＋１)／２＋２ｊ−１)-ｑビットにＳＷＡＰを適用する演算を行うＳＷＡＰ演算部を備え〔ただし、ｊ＝１，…，ｎ＋１−ｇとし、ｇごとに全てのｊについての演算を並列に行うものとする。〕、
《５》ｇ＝(ｎ＋１)／２，…，２について、順に、第((ｎ＋１)／２−ｇ＋２ｊ)-ｑビットと第((ｎ＋１)／２−ｇ＋２ｊ＋１)-ｑビットにＳＷＡＰを適用する演算を行うＳＷＡＰ演算部を備え〔ただし、ｊ＝１，…，ｇ−１とし、ｇごとに全てのｊについての演算を並列に行うものとする。〕、
《６》第((ｎ＋１)／２＋１)-ｑビットから第ｎ-ｑビットまでについて、近傍２量子ビット演算で構成した２ (ｎ−１)／２を法とする量子フーリエ変換を行う量子演算部を備え、
（パターン２）
《１》第１-ｑビットから第((ｎ−１)／２)-ｑビットまでについて、近傍２量子ビット演算で構成した２(ｎ−１)／２を法とする量子フーリエ変換を行う量子演算部を備え、
《２》ｇ＝２，…，(ｎ＋１)／２について、順に、第((ｎ＋１)／２−ｇ＋２ｊ−１)-ｑビットと第((ｎ＋１)／２−ｇ＋２ｊ)-ｑビットに角度２π／２ｇの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する演算を行う量子演算部を備え〔ただし、ｊ＝１，…，ｇ−１とし、ｇごとに全てのｊについての演算を並列に行うものとする。〕、
《３》ｇ＝(ｎ＋１)／２＋１，…，ｎについて、順に、第(ｇ−(ｎ＋１)／２＋２ｊ−１)-ｑビットと第(ｇ−(ｎ＋１)／２＋２ｊ)ビットに角度２π／２ｇの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する演算を行う量子演算部を備え〔ただし、ｊ＝１，…，ｎ＋１−ｇとし、ｇごとに全てのｊについての演算を並列に行うものとする。〕、
《４》ｇ＝ｎ，…，(ｎ＋１)／２＋１について、順に、第(ｇ−(ｎ＋１)／２＋２ｊ−１)-ｑビットと第(ｇ−(ｎ＋１)／２＋２ｊ)-ｑビットにＳＷＡＰを適用する演算を行うＳＷＡＰ演算部を備え〔ただし、ｊ＝１，…，ｎ＋１−ｇとし、ｇごとに全てのｊについての演算を並列に行うものとする。〕、
《５》ｇ＝(ｎ＋１)／２，…，２について、順に、第((ｎ＋１)／２−ｇ＋２ｊ−１)-ｑビットと第((ｎ＋１)／２−ｇ＋２ｊ)-ｑビットにＳＷＡＰを適用する演算を行うＳＷＡＰ演算部を備え〔ただし、ｊ＝１，…，ｇ−１とし、ｇごとに全てのｊについての演算を並列に行うものとする。〕、
《６》第((ｎ−１)／２＋１)-ｑビットから第ｎ-ｑビットまでについて、近傍２量子ビット演算で構成した２ (ｎ＋１)／２を法とする量子フーリエ変換を行う量子演算部を備え、
ｎ＝１の場合、
第１-ｑビットにアダマール変換を適用する量子演算部を備え、
上記の手順で構成された量子演算装置において、２ｎより小さく２ｍより大きい数２Ｂを法とする量子フーリエ変換の量子演算部については、このＢを新たなｎと看做して、上記の場合分けに従った手順で量子演算部を構成し、
２ｍ以下の数を法とする量子フーリエ変換を行う量子演算部Ｄについては、
量子演算部Ｄへ入力されるＮ個のｑビットである第１-ｑビット、…、第Ｎ-ｑビットに対して、
《１》ｇ＝１，…，Ｎについて、順に、
ｇ＝１の場合、
第１-ｑビットにアダマール変換を適用する演算を行う量子演算部を備え、
ｇが３以上の奇数の場合、
第１-ｑビットにアダマール変換を適用する演算を行う量子演算部を備え、
第(ｊ−１)-ｑビットと第ｊ-ｑビットに角度２π／２ｊの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する演算を行う量子演算部を備え〔ただし、ｊは３からｇまでの奇数とし、ｇごとに第１-ｑビットに対するアダマール変換および全てのｊについての演算を並列に行うものとする。〕、
ｇが偶数の場合、
第(ｊ−１)-ｑビットと第ｊ-ｑビットに角度２π／２ｊの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する演算を行う量子演算部を備え〔ただし、ｊは２からｇまでの偶数とし、ｇごとに全てのｊについての演算を並列に行うものとする。〕、
《２》ｇ＝Ｎ−１，…，１について、順に、
ｇ＝１の場合、
第１-ｑビットにアダマール変換を適用する演算を行う量子演算部を備え、
ｇが３以上の奇数の場合、
第１-ｑビットにアダマール変換を適用する演算を行う量子演算部を備え、
第(ｊ−１)-ｑビットと第ｊ-ｑビットに角度２π／２ｊの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する演算を行う量子演算部を備え〔ただし、ｊは３からｇまでの奇数とし、ｇごとに第１-ｑビットに対するアダマール変換および全てのｊについての演算を並列に行うものとする。〕、
ｇが偶数の場合、
第(ｊ−１)-ｑビットと第ｊ-ｑビットに角度２π／２ｊの制御フェイズシフトを適用し、さらにこれらのｑビットにＳＷＡＰを適用する演算を行う量子演算部を備え〔ただし、ｊは２からｇまでの偶数とし、ｇごとに全てのｊについての演算を並列に行うものとする。〕、
《３》ｇ＝１，…，Ｎ−１について、順に、
ｇが奇数の場合、
第ｊ-ｑビットと第(ｊ＋１)-ｑビットにＳＷＡＰを適用する演算を行うＳＷＡＰ演算部を備え〔ただし、ｊは１からｇまでの奇数とし、ｇごとに全てのｊについてのＳＷＡＰを並列に行うものとする。〕、
ｇが偶数の場合、
第ｊ-ｑビットと第(ｊ＋１)-ｑビットにＳＷＡＰを適用する演算を行うＳＷＡＰ演算部を備え〔ただし、ｊは２からｇまでの偶数とし、ｇごとに全てのｊについてのＳＷＡＰを並列に行うものとする。〕、
《４》ｇ＝Ｎ−２，…，１について、順に、
ｇが奇数の場合、
第ｊ-ｑビットと第(ｊ＋１)-ｑビットにＳＷＡＰを適用する演算を行うＳＷＡＰ演算部を備え〔ただし、ｊは１からｇまでの奇数とし、ｇごとに全てのｊについてのＳＷＡＰを並列に行うものとする。〕、
ｇが偶数の場合、
第ｊ-ｑビットと第(ｊ＋１)-ｑビットにＳＷＡＰを適用する演算を行うＳＷＡＰ演算部を備え〔ただし、ｊは２からｇまでの偶数とし、ｇごとに全てのｊについてのＳＷＡＰを並列に行うものとする。〕、
以上に従って構成された近似量子フーリエ変換演算装置において、角度２π／２ｔ（ｔ＞ｍ）の制御フェイズシフトを行う量子演算部を、恒等変換を行う量子演算部に置換し、
角度２π／２ｔ（ｔ＝ｍ）の制御フェイズシフトの直後のＳＷＡＰおよび恒等変換とされた制御フェイズシフトの直後のＳＷＡＰの各演算を行う量子演算部Ｅと、上記ＳＷＡＰ演算部において量子演算部Ｅの鏡像対称の量子演算部とを備えずに構成された
ことを特徴とする近似量子フーリエ変換演算装置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2006225709A JP4332167B2 (ja) | 2006-08-22 | 2006-08-22 | 近似量子フーリエ変換を行う量子回路、近似量子フーリエ変換演算方法および装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2006225709A JP4332167B2 (ja) | 2006-08-22 | 2006-08-22 | 近似量子フーリエ変換を行う量子回路、近似量子フーリエ変換演算方法および装置 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JP2008052365A true JP2008052365A (ja) | 2008-03-06 |
| JP4332167B2 JP4332167B2 (ja) | 2009-09-16 |
Family
ID=39236393
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2006225709A Expired - Fee Related JP4332167B2 (ja) | 2006-08-22 | 2006-08-22 | 近似量子フーリエ変換を行う量子回路、近似量子フーリエ変換演算方法および装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP4332167B2 (ja) |
Cited By (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2013033385A (ja) * | 2011-08-02 | 2013-02-14 | Nippon Telegr & Teleph Corp <Ntt> | 量子回路生成装置、方法、プログラム及び記録媒体 |
| KR20190007375A (ko) * | 2017-07-12 | 2019-01-22 | 한국전자통신연구원 | 제어 큐비트에 기초하여 타겟 큐비트의 위상을 쉬프트시키는 양자 회로 |
| CN113692593A (zh) * | 2018-07-06 | 2021-11-23 | 华沙大学 | 执行量子傅里叶-克拉夫丘克变换(qkt)的方法及实施该方法的设备 |
| JP2022035109A (ja) * | 2020-08-20 | 2022-03-04 | 国立大学法人 東京大学 | 量子回路生成装置、量子回路生成方法及び量子回路生成プログラム |
| CN114529003A (zh) * | 2022-01-29 | 2022-05-24 | 西安电子科技大学 | 面向多量子比特量子傅里叶变换线路的分割方法 |
| WO2022249963A1 (ja) * | 2021-05-24 | 2022-12-01 | 国立大学法人東京大学 | 量子回路 |
| WO2024121981A1 (ja) | 2022-12-07 | 2024-06-13 | 三菱電機株式会社 | 近似量子フーリエ変換装置、近似量子フーリエ変換方法及び近似量子フーリエ変換プログラム |
-
2006
- 2006-08-22 JP JP2006225709A patent/JP4332167B2/ja not_active Expired - Fee Related
Cited By (13)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2013033385A (ja) * | 2011-08-02 | 2013-02-14 | Nippon Telegr & Teleph Corp <Ntt> | 量子回路生成装置、方法、プログラム及び記録媒体 |
| KR20190007375A (ko) * | 2017-07-12 | 2019-01-22 | 한국전자통신연구원 | 제어 큐비트에 기초하여 타겟 큐비트의 위상을 쉬프트시키는 양자 회로 |
| KR102338755B1 (ko) | 2017-07-12 | 2021-12-16 | 한국전자통신연구원 | 제어 큐비트에 기초하여 타겟 큐비트의 위상을 쉬프트시키는 양자 회로 |
| CN113692593B (zh) * | 2018-07-06 | 2024-04-26 | 华沙大学 | 执行量子傅里叶-克拉夫丘克变换(qkt)的方法及实施该方法的设备 |
| CN113692593A (zh) * | 2018-07-06 | 2021-11-23 | 华沙大学 | 执行量子傅里叶-克拉夫丘克变换(qkt)的方法及实施该方法的设备 |
| JP2022035109A (ja) * | 2020-08-20 | 2022-03-04 | 国立大学法人 東京大学 | 量子回路生成装置、量子回路生成方法及び量子回路生成プログラム |
| JP7511230B2 (ja) | 2020-08-20 | 2024-07-05 | 国立大学法人 東京大学 | 量子回路生成装置、量子回路生成方法及び量子回路生成プログラム |
| WO2022249963A1 (ja) * | 2021-05-24 | 2022-12-01 | 国立大学法人東京大学 | 量子回路 |
| JP2022180189A (ja) * | 2021-05-24 | 2022-12-06 | 国立大学法人 東京大学 | 量子回路 |
| CN114529003A (zh) * | 2022-01-29 | 2022-05-24 | 西安电子科技大学 | 面向多量子比特量子傅里叶变换线路的分割方法 |
| WO2024121981A1 (ja) | 2022-12-07 | 2024-06-13 | 三菱電機株式会社 | 近似量子フーリエ変換装置、近似量子フーリエ変換方法及び近似量子フーリエ変換プログラム |
| JP7570584B1 (ja) * | 2022-12-07 | 2024-10-21 | 三菱電機株式会社 | 近似量子フーリエ変換装置、近似量子フーリエ変換方法及び近似量子フーリエ変換プログラム |
| EP4589487A4 (en) * | 2022-12-07 | 2025-09-10 | Mitsubishi Electric Corp | APPROXIMATE QUANTUM FOURIER TRANSFORM DEVICE, APPROXIMATE QUANTUM FOURIER TRANSFORM METHOD, AND APPROXIMATE QUANTUM FOURIER TRANSFORM PROGRAM |
Also Published As
| Publication number | Publication date |
|---|---|
| JP4332167B2 (ja) | 2009-09-16 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| García-Álvarez et al. | Digital quantum simulation of minimal AdS/CFT | |
| Albanese et al. | Mirror inversion of quantum states in linear registers | |
| JP4847914B2 (ja) | 量子加算演算方法及び量子加算演算装置 | |
| JP5351862B2 (ja) | 量子演算方法、量子演算装置 | |
| Perriello et al. | A complete quantum circuit to solve the information set decoding problem | |
| JP5227942B2 (ja) | 量子誤り推定装置、量子誤り推定方法、そのプログラム、量子誤り訂正装置、量子誤り訂正方法 | |
| Gard et al. | Inefficiency of classically simulating linear optical quantum computing with Fock-state inputs | |
| JP4332167B2 (ja) | 近似量子フーリエ変換を行う量子回路、近似量子フーリエ変換演算方法および装置 | |
| JP5204698B2 (ja) | 量子演算方法、量子演算装置、量子回路 | |
| JP4700413B2 (ja) | 量子演算装置及び量子回路を用いた量子演算方法 | |
| JP5129646B2 (ja) | 量子回路、量子演算装置及び量子演算方法 | |
| Lin | Shor’s algorithm and the quantum Fourier transform | |
| JP6182123B2 (ja) | 量子演算方法 | |
| Yamaguchi et al. | Experiments and resource analysis of Shor’s factorization using a quantum simulator | |
| Smith et al. | Entangled state preparation for non-binary quantum computing | |
| JP5496921B2 (ja) | 量子演算方法、量子演算装置 | |
| van Meter et al. | Approximate exchange-only entangling gates for the three-spin-1/2 decoherence-free subsystem | |
| Tutul et al. | Shallow Depth Factoring Based on Quantum Feasibility Labeling and Variational Quantum Search | |
| JP4366348B2 (ja) | 量子計算方法及び量子計算装置 | |
| JP4829623B2 (ja) | 量子演算方法及び量子演算装置 | |
| JP5118461B2 (ja) | 量子演算装置、逆２次位相変換演算装置、それらの方法、プログラム及び記録媒体 | |
| JP4718190B2 (ja) | 量子探索装置、量子探索方法及びプログラム | |
| EP4375886A1 (en) | Digital quantum simulations of fermion-boson systems in two-dimensional quantum computing systems | |
| Hwang et al. | Quantum circuit design for computer-assisted Shor's algorithm | |
| KR102740845B1 (ko) | 양자 컴퓨터 상의 곱셈 장치 및 곱셈 방법 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A621 | Written request for application examination |
Free format text: JAPANESE INTERMEDIATE CODE: A621 Effective date: 20080804 |
|
| A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20090430 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20090609 |
|
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20090619 |
|
| R150 | Certificate of patent or registration of utility model |
Ref document number: 4332167 Country of ref document: JP Free format text: JAPANESE INTERMEDIATE CODE: R150 Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120626 Year of fee payment: 3 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20130626 Year of fee payment: 4 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20140626 Year of fee payment: 5 |
|
| S531 | Written request for registration of change of domicile |
Free format text: JAPANESE INTERMEDIATE CODE: R313531 |
|
| R350 | Written notification of registration of transfer |
Free format text: JAPANESE INTERMEDIATE CODE: R350 |
|
| LAPS | Cancellation because of no payment of annual fees |