FPGA開発日記

FPGAというより、コンピュータアーキテクチャかもね! カテゴリ別記事インデックス https://msyksphinz.github.io/github_pages

自作量子コンピュータ・シミュレータで量子フーリエ変換を実装する

量子コンピュータで効率化できるアルゴリズムとして有名なもののひとつに、量子フーリエ変換というものがある。

これは通常の離散フーリエ変換量子コンピュータに応用するもので、詳細な理論は良く分からないのだが、RSA暗号を解読するためのベースとなる技術らしい。 良く分からないが、RSA暗号のカギとなる技術である素因数分解を高速に実行するために、周期を見つけ出すためにフーリエ変換が有効らしい。

下記のページを主に参考にした。なるほど数式が大量に入っているが、最後に綺麗に量子回路に起こしてあるため、何となくイメージがつけやすい。

量子フーリエ変換 (Quantum Fourier Transform) とは - 物理とか

あとは以下の書籍を参考にした。

量子コンピュータ―超並列計算のからくり (ブルーバックス)

量子コンピュータ―超並列計算のからくり (ブルーバックス)

入力と出力が良く分からないが、例えば3ビットの量子ビットを定義したら、その量子ビットが取りうる値を確率として表現する。 例えば、以下のような確率で量子ビットが表現されるとしたら、

f:id:msyksphinz:20181017232302p:plain

フーリエ変換は以下のようになるらしい。ほんとか?フーリエ変換が波数分布を表現していると書いてあるが。。。なんかイメージと違うなあ。

f:id:msyksphinz:20181017232500p:plain

波形の周期を表現したほうがフーリエ変換としてはスッキリしそうだけど。。。

とりあえず理論はさておき、以下のように量子フーリエ変換は表現されるらしい(https://whyitsso.net/physics/quantum_mechanics/QFT.html より抜粋)。 アダマールゲートと、制御付き位相変換回路を使用する。

f:id:msyksphinz:20181017232648p:plain

制御付き位相変換回路は無いので実装した。検査用のビットが1ならば、対象のビットの位相を変える。

void Qbits::CRot (int c_idx, int v_idx, double rad)
{
  complex2d_t matrix;
  matrix.resize(m_qbit_size);
  for (size_t i = 0; i < m_qbit_size; i++) {
    matrix[i].resize(m_qbit_size);
    for (size_t j = 0; j < m_qbit_size; j++) {
      matrix[i][j] = 0.0;
    }
  }

  uint64_t c_bitmask = 1 << c_idx;
  uint64_t v_bitmask = 1 << v_idx;
  for (size_t idx = 0; idx < m_qbit_size; idx++) {
    if ((idx & c_bitmask) == c_bitmask) {
      if ((idx & v_bitmask) == 0) {
        matrix[idx][idx] = 1.0;
      } else {
        matrix[idx][idx] = cos(rad / 2) + sin(rad / 2) * static_cast<std::complex<double>>(1.0if);
      }
    } else {
      matrix[idx][idx] = 1.0;
    }
  }

  m_comp_amp = MatrixMul(matrix, *m_comp_amp);
}

以下のようにPythonのコードで量子回路を記述した。

import math
import collections

length = 3

qubits = [qbit.make_qbit() for i in range(length)]

# qbit.h(qubits[0])
# qbit.h(qubits[1])
# qbit.h(qubits[2])

for j in range(length-1, -1, -1):
    qbit.h(qubits[j])
    for i in range(j-1, -1, -1):
        qbit.crot(qubits[i], qubits[j], 2 * math.pi / (2 ** (j-i)))

result = []

for i in range(0, 10000):
    val = 0
    for idx in range(length):
        val = val | (qbit.val(qubits[idx]) << idx)
    result.append(val)

c = collections.Counter(result)
print(c.most_common(20))

まずは、周期1の波形を作ってみる。

qbit.h(qubits[0])
qbit.h(qubits[1])
qbit.h(qubits[2])
$ ./qbit_simulator ../test/test_qft.py
Before QFT:
[(5, 1320), (2, 1307), (6, 1257), (3, 1245), (7, 1224), (0, 1219), (1, 1216), (4, 1212)]
After QFT:
[(0, 10000)]

量子ビット=0のところにだけ波形が出た。これはつまり周期が一番小さい or 存在しないということかな?

次に、周期2の波形を作ってみた。

# qbit.h(qubits[0])
qbit.h(qubits[1])
qbit.h(qubits[2])

量子ビット0と1のところに波形が出た。周期が1つ飛びなので1が出てきたのかな?

$ ./qbit_simulator ../test/test_qft.py
Before QFT:
[(2, 2552), (4, 2532), (6, 2481), (0, 2435)]
After QFT:
[(0, 5017), (1, 4983)]

次に周期4の波形を作ってみた。

# qbit.h(qubits[0])
# qbit.h(qubits[1])
qbit.h(qubits[2])

実行してみた。0,1,2,3のところに確率が分布したが、これは合っているのかなあ?

$ ./qbit_simulator ../test/test_qft.py
Before QFT:
[(4, 5013), (0, 4987)]
After QFT:
[(0, 2559), (1, 2535), (3, 2504), (2, 2402)]