QFT 足し算

QFT をサブルーチンとして捉えると、様々な回路を QFT を使って書くことができます。 一例として、足し算回路で紹介した次の加算回路を考えてみましょう。

この回路は従来のデジタル回路と同様の論理演算を量子回路上に実装したものです。 これは各ビットのオン/オフを条件として と でビット演算を行うため、 が多くやや複雑な回路となっています。

一方で QFT を使った同じ足し算を行う回路は次のようになります。 大ざっぱな構造としては、最初に前処理として逆 QFT を行い、次に a+=b の計算を位相上で行った後、後処理として QFT を行う流れになっています。

これは一見、最初の回路よりもかなり複雑に見えるかもしれません。 しかし、最初の逆 QFT と最後の QFT を除いた a += b のブロック (左から 3 番目) だけを見ると、最初の回路よりもかなり単純化できていることがわかります。 とくに の数はかなり削減できています。

このように、QFT を使った算術演算回路では、実際に演算を行うコア部分に必要なゲートの数を削減することができます。 足し算 1 回だけの単純な回路では QFT 版のほうがずっと複雑です。 しかし、演算内容が大きくなるほど前後の QFT の大きさを無視することができ、またコア部分が単純になるため全体としてはゲート数を削減できます。

QFT 版足し算回路の内部

QFT 版足し算回路は次のように動作します。

• a = 3 を逆 QFT で位相の回転に変換 (= 位相回転の世界へ移動)
• b の値を位相の回転として a に加算ここでは詳しく解説しませんが、この部分の仕組みは QFT によく似ています。余裕のある人は動作を解読してみましょう。
• a += b の結果を QFT で戻す (= 周波数の世界へ移動)

つまり、いったん位相回転の世界に移動することで、足し算を b の各ビットを条件とした位相回転として実行できます。 位相回転は と だけで書くことができるため、普通のデジタル加算回路よりもゲートを削減できるというわけです。 そして最後に QFT で計算結果を位相回転の世界から周波数の世界に逆変換することで、計算結果を確率に書き込みます。

QFT 足し算を少し改造するだけで QFT 引き算回路も作ることができます。 足し算のコア部分は角度を足すという単純な処理なので、角度の値をマイナスにするだけで引き算回路になります。

まとめ

QFT の応用例として、足し算を QFT で行う回路を紹介しました。 わざわざフーリエ変換を使って足し算を行う理由は、回路に必要なゲート数を削減するためです。 QFT によって位相回転の世界に移動すると、足し算や引き算といった算術演算を単純な回転として実装できます。

このように、QFT はたくさんの量子アルゴリズムの一部として利用されています。 位相回転の世界から周波数の世界へ移動する QFT と、その逆を行う逆 QFT の役割をよく理解しておきましょう。