前回は半加算器が完成した。という訳で、これを拡張させて全加算器を作成し、さらにこれを数珠つなぎにして3ビットの加算回路を作ろう。

量子回路で全加算器を作ろう

量子回路を使って全加算器を作るにはどうしたらよいのか、少し検索するとすぐ回路を見つけた。以下のように構成すれば全加算器を作ることができるらしい。

図. $a+b+c_\text{in} = s, c_\text{out}$ の全加算器

これは私が開発している量子コンピュータシミュレータを使えば、以下のように表現できる。

void FullAdder(Qbits *qbits, int a_idx, int b_idx, int c0_idx, int c1_idx)
{
  qbits->CCNot(a_idx, b_idx, c1_idx);
  qbits->CNot (a_idx, b_idx);
  qbits->CCNot(b_idx, c0_idx, c1_idx);
  qbits->CNot (b_idx, c0_idx);
}

これだとbの値は最終的に崩れてしまうのだけれども、使わないので良しとする。

3ビットの加算器を作ろう

3ビットの加算器を作るためには、この全加算器を3つ並べれば良いわけだ。もっとも単純に作るためには以下のようにする。ちなみに、各計算毎にキャリーを保持するために量子ビットを用意している。なので、3ビットの加算器を作るために用意したビットは、 - 3ビットで表現される入力a - 3ビットで表現される入力b - 4ビットの、答え兼carry-bitを保持するための答えc

という訳で、3+3+4ビットで10ビット必要である。この時点で内部的には $1024\times 1024$ の行列計算が行われるわけで、こりゃ確かに大変だ。。。

図. 3ビット量子加算回路

一度全加算器を作ったので、これを並べるだけである。量子ビットは10ビット用意して、{s[3:0], b[2:0], a[2:0]}とした。なので、最後に6ビットシフトしてs[3:0]のみ出力している。

      Qbits qbits (b << 3 | a, 10);
      FullAdder (&qbits, 0, 3, 6, 7);
      FullAdder (&qbits, 1, 4, 7, 8);
      FullAdder (&qbits, 2, 5, 8, 9);
      int res = qbits.Measure();
      res = res >> 6;
      printf ("%x\n", res);

加算回路の実行

とりあえず全部回してみる。目視だが間違いがあればすぐに分かるはずだ。

  for (int a = 0; a < 8; a++) {
    for (int b = 0; b < 8; b++) {
      printf ("%x + %x = ", a, b);

      Qbits qbits (b << 3 | a, 10);
      FullAdder (&qbits, 0, 3, 6, 7);
      FullAdder (&qbits, 1, 4, 7, 8);
      FullAdder (&qbits, 2, 5, 8, 9);
      int res = qbits.Measure();
      res = res >> 6;
      printf ("%x\n", res);
    }
  }

実行すると以下のようになった。ちゃんと動いているな。

$ ./qbit_simulator
0 + 0 = 0
0 + 1 = 1
0 + 2 = 2
0 + 3 = 3
0 + 4 = 4
0 + 5 = 5
0 + 6 = 6
0 + 7 = 7
1 + 0 = 1
...
7 + 4 = b
7 + 5 = c
7 + 6 = d
7 + 7 = e