量子コンピュータで効率化できるアルゴリズムとして有名なもののひとつに、量子フーリエ変換というものがある。
これは通常の離散フーリエ変換を量子コンピュータに応用するもので、詳細な理論は良く分からないのだが、RSA暗号を解読するためのベースとなる技術らしい。 良く分からないが、RSA暗号のカギとなる技術である素因数分解を高速に実行するために、周期を見つけ出すためにフーリエ変換が有効らしい。
下記のページを主に参考にした。なるほど数式が大量に入っているが、最後に綺麗に量子回路に起こしてあるため、何となくイメージがつけやすい。
量子フーリエ変換 (Quantum Fourier Transform) とは - 物理とか
あとは以下の書籍を参考にした。
- 作者: 竹内繁樹
- 出版社/メーカー: 講談社
- 発売日: 2005/02/18
- メディア: 新書
- 購入: 7人 クリック: 64回
- この商品を含むブログ (20件) を見る
入力と出力が良く分からないが、例えば3ビットの量子ビットを定義したら、その量子ビットが取りうる値を確率として表現する。 例えば、以下のような確率で量子ビットが表現されるとしたら、
フーリエ変換は以下のようになるらしい。ほんとか?フーリエ変換が波数分布を表現していると書いてあるが。。。なんかイメージと違うなあ。
波形の周期を表現したほうがフーリエ変換としてはスッキリしそうだけど。。。
とりあえず理論はさておき、以下のように量子フーリエ変換は表現されるらしい(https://whyitsso.net/physics/quantum_mechanics/QFT.html より抜粋)。 アダマールゲートと、制御付き位相変換回路を使用する。
制御付き位相変換回路は無いので実装した。検査用のビットが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)]