入力される量 子ビットを 2 進数とみなしたときに、離散フーリエ変換をおこなうアルゴリズムです。シミュレータには、離散フーリエ変換 (DFT) を効率的にシミュレーションするために専用のゲートがありますが、これと同じ変換をおこなうアルゴリズムを基本ゲートにかなり近い立場から構築したものと考えて下さい。
入力される状態を としたとき、離散フ−リエ変換DFTqにより出力されるベクトルは、次の関係式により定義されます。



ここで q は、入力される量子ビット数を n としたときに



アルゴリズムは 2 次のユニタリゲート A と 2 次のユニタリ行列 に制御信号が付加されたゲートを随時、各量子ビットに作用されることにより実現されます。


ここで A と は、それぞれ





により定義されます。ただし、はと制御信号が作用する 2 つの量子ビットの位置をkとj (j<k) としたとき



により定義される定数です。

入力される状態ベクトルが純粋状態であれば、位相の異なる等確率な状態ベクトルの重ね合わせを出力することに注目して下さい。

詳しくは

D. Coppersmith, "An Approximate Fourier Transform Useful in Quantum Factoring"
Technical Report RC-19642. IBM Research Division, July 1994

などを参照下さい。

算術アルゴリズムの 1 つで、2 進数でエンコーディングされた 2 つの数 と との加算をおこないます。

量子コンピュータでおこなうアルゴリズムでは、可逆性が要求されます。このため、量 子コンピュータでの加算アルゴリズムでは、入力される値 と について



なる変換をおこなうように設計されていることに注意して下さい。

加算アルゴリズムは、2 量子ビット間でのキャリー計算と和の計算をおこなうゲートを組み合わせることによって構成されています。

キャリーを計算するゲート、2 つのビットの和を計算するゲートは、いくつかの基本ゲートの組み合わせにより構成されます。


これらのキャリーゲートと和ゲートは、2 進数表記されたそれぞれの桁に作用するゲートです。これらを組み合わせることにより加算ゲートが構成されます。



ここで、 と は、加算をおこなう入力ビットで、2 進数でエンコードされているそれぞれの桁の値です。 にはaとbを加えあわせた結果が 2 進数でエンコードされて得られます。 は、それぞれの桁におけるキャリーを保持するために必要な量 子ビットです。 には入力として 0 を与えますが、 の出力も、また 0 であることに注意して下さい。このように、一時的に必要な量 子ビットの入力と出力の値を同じにすることにより、 は、また、別のアルゴリズムで計算途中の値の保持目的などのために、有効に再利用されることになります。

一般に算術アルゴリズムでは、途中の計算結果を保持するために、非常に多くのスクラッチレジスタ (一時的な目的のために利用される量子ビットの列) が必要となります。そのために、計算途中の結果 を保持するために必要な量子ビットを、いかに効率良く利用するようにするかが、アルゴリズムを設計する上で、重要なポイントとなります。
　付属するサンプルでは、キャリーゲートを また和ゲートを S を用いて表記しています。アルゴリズム中で で表記されているゲートは ゲートの逆変換をおこなうゲートです。



入力する と を変化させた場合における出力を確認して下さい。

入力と出力を逆にすると、足し算ではなく引き算ができることに注目して下さい。

詳しくは

Feynman Lectures on Computation, Richard P. Feynman, Addison Wesley (ISBN 0-201-48991-0)

などをご覧下さい。

加算アルゴリズムにおける と の入力値を、等確率に分布させた場合のサンプルです。

等確率で入力を分布させるために、入力として取り得るすべての量 子ビットに ゲートを作用させています。

古典的なコンピュータでは、入力される値のバリエーションの回数だけ繰り返す必要のある計算が、量 子計算においては、たった 1 度の計算で終了する点に注目下さい

古典的なアルゴリズムと比較して、一般に、量子コンピュータでのアルゴリズムが優れている場合には、このような、すべての入力値を与え、一度の計算するという手法を随所でもちいていることに注目する必要があります。

カスタムゲートを利用した場合のサンプルです。

ここで用いているゲートの表現行列は

となります。

入力される状態ベクトル と については、入力されたベクトルと等しい出力を与えますが、それ以外の入力については、入力された量 子ビットが反転された出力を与えます。



こうしたゲートは、シミュレータ内部で数値を入力することにより作成することもできますが、一般 に作業が煩雑になりがちです。このため、普通は、Mathematica とのリンクをおこない、必要な修正を加えることになります。

Mathematica とのリンクをおこない、カスタムゲートの成分が正しく出力されていることを確認して下さい。また、Mathematica で変更を加えた行列をシミュレータに取り込んでみて下さい。

シミュレータでは取り込まれた行列が、ユニタリ行列であるかどうかを確認しています。このため、入出力をおこなう簡単な試験などでは、例えば、単位 行列を

測定ゲートのサンプルです。

アルゴリズムは ゲートの部分と測定ゲートの 2 つの部分に別れます。

最初の ゲートの部分では、すべての量子ビットに ゲートを作用させることにより、等確率の状態ベクトルの生成をおこないます。このときの状態ベクトル は



で与えられます。すなわち、すべての状態が、まったく等しい確率で観測される状態です。

こうした状態を測定ゲートで観測するというアルゴリズムになっています。

アルゴリズムを実行する度に、状態ベクトルがランダムに選ばれた純粋状態に収縮する様子をご確認下さい。

基本ゲートへの分解をおこなったサンプルです。

量子アルゴリズムでは、アルゴリズムの計算量を評価する目的で、アルゴリズムをゲートとゲートに分解します。分解されたこれらのゲートとゲートを基本ゲートと呼びます。これらの個数が、入力についてどのような関係になるかを考慮することにより、アルゴリズムの優劣が評価されることになります。

サンプルではを分解した例を取り扱っています。

ゲートは、2 つのゲート、2 つのゲート、1 つのゲートから構成されたアルゴリズムと等価であることが知られています。

ここで は2 次のユニタリ作用素で



です。また は の共役転地行列で



です。



サンプルで考えているゲートとゲートは基本ゲートではありませんが、ここではこれらを基本ゲートと見なすことにします。

分解例で示される量子アルゴリズムの入出力がと等しいことを確認して下さい。

詳しくは

Barenco, Adriano, et. al, "Elementary gates for quantum computation",
Physical Review A, Vol. 52, No. 5, 1995

などを参照して下さい。