算術演算
かけ算回路
補助ビットの使い方
かけ算回路は、(著者が知る限り) \(a \mathrel{*}= b\) のように実装することができません。 このため、\(a * b\) の結果を入れるためのビット列が必要になります。 またこのため、左右をひっくり返すだけで割り算回路を作ることもできません。 しかしかけ算は様々な算術演算の重要な部品なので、基本的な実装方法を見ておきましょう。
かけ算を実装するには、二進数のかけ算をおさらいしておく必要があります。 たとえば二進数で \(2 \times 3\) (\(10 \times 11\)) を計算するには、十進数と同様に筆算を行います。
\begin{array}{r} 10 \\[-3pt] \underline{\times\phantom{0}11}\\[-3pt] 10 \\[-3pt] \underline{\phantom{0}10\phantom{0}} \\[-3pt] 110 \end{array}
二進数筆算のやり方は、十進数の場合とまったく同じです。
- 10 に 11 の一桁目 (1) をかけた結果 10 を書く
- 10 に 11 の二桁目 (1) をかけた結果 10 を 1 ビットずらして書く
- 1 と 2 の結果を足す
これをそのまま回路に変換することで、かけ算回路を実装できます。 a と b がそれぞれ 2 ビットの場合、かけ算回路には全部で 10 ビット必要です。
- a (2 ビット): a の入力
- b (2 ビット): b の入力
- m (4 ビット): 計算結果 a * b の出力
- tmp (2 ビット): 計算中の一時ビット
これを頭に入れて、次のかけ算回路を見ていきましょう。
最初の \(a=2\) と \(b=3\) のブロックでは、入力 \(a\) と \(b\) をセットします。それぞれ 2 ビットの値を取ることができます。
次の c=a*b のブロックがかけ算回路の本体であり、筆算手順を回路にしたものです。
最初の 2 つの CCNOT では、a に b の一桁目をかけた値を、m の下位 2 ビットにセットします。
二進数のかけ算では \(1 \times 1\) の場合だけ \(1\)、それ以外の \(1 \times 0\) などは 0
になります。 よって、a の数と b の一桁目がそれぞれ 1 だった場合のみ、CCNOT の
次の 2 つの CCNOT では同様に、a に b の二桁目をかけた値を、一時ビット tmp にセットします。 この値は次に m に足し合わされます。
最後に m の値と tmp を足し合わせます。 この足し算では m の値を 1 ビットずらす必要があるので、tmp の 1 ビット目を m の 2 ビット目、tmp の 2 ビット目を m の 3 ビット目に足し算回路で足します。 こうして、m に a * b の結果が残ります。
一時ビット tmp のクリア
tmp は a と b の二桁目のかけ算結果のための一時ビットで、計算が終わった後は不要です。 量子ビットは 1 ビットでも貴重なので、残った値をクリアして再利用できるようにしたほうがよいでしょう。
ここで安直に tmp の 2 ビットそれぞれに
そこで、もつれをほどくで見たように、tmp に値をセットした CCNOT 2 つの逆回路をかけてやることで、tmp だけを初期状態に戻すことができます。 こうすれば、a や b のビットを壊すことなく tmp のビットだけ 0 に戻すことができます。
この操作は一般的に「アンコンピュテーション (uncomputation、逆計算)」と呼ばれ、量子コンピュータプログラミングで必ず使われるテクニックです。 アンコンピュテーションは不要となった一時ビットに逆演算を行うことで、原状復帰して再利用できるようにします。 いわば量子コンピュータ版の malloc() に対する free() のようなものと言えるでしょうか。 量子コンピュータは低レベルなので GC (ガベージ・コレクション) のような便利な機能はありませんから、ちょっと大変ですが明示的にアンコンピュートして一時ビットを開放する必要があります。