はじめに
量子回路におけるQFT加算は各ビットの位相を利用した独特な計算方法ですが、そのモジュラー演算もまた特殊なアプローチが必要であり、量子コンピュータの計算を加速させる並列計算はまたそのすべての状態に同じ演算を一律にかける必要があるという並列計算の制約に縛られています。
$a + b \pmod N$
古典コンピュータなら (a + b) % N の一行で終わるこの処理が、可逆計算である量子回路では安易に導入できません。本記事では、Qiskitを用いてQFTベースのモジュラ加算器を実装する過程とについて解説します。
モジュラ加算の難しさ
量子回路での加算にはいくつか手法がありますが、今回は量子ビット数を節約できるQFT加算を採用します。これは、数値を「フーリエ空間（周波数領域）」に変換し、位相を回転させることで加算を行う手法です。
- QFT: 数値を波の状態に変換
- Phase Rotation: 加算したい値に応じて位相を回転（$R_z$ゲートなど）
- IQFT: 逆変換して数値に戻す
これだけなら簡単ですが、モジュラーとなると話が変わります。単に足すだけだと、$N$を超えてしまうからです。
モジュラ加算のアルゴリズム
$|x\rangle$ に定数 $C$ を足して $\pmod N$ をとるアルゴリズムは、以下の条件分岐が必要になります。
- 加算: まず $x + C$ を計算する
- 減算: とりあえず $N$ を引いてみる（$x + C - N$）
- 判定: 結果が負（アンダーフロー）になったかチェックする
- 負なら: 引く必要がなかったということなので、$N$ を足し戻す
- 正なら: そのままでOK（$N$ を引いたのが正解だった）
この過程を見てわかるように、量子コンピュータにおける条件分岐は、古典アルゴリズムのように値を調べてから操作を決定することはできません。
量子力学の重ね合わせの原理により、$N$を引くべき状態と引くべきでない状態が同時に存在し、その両方に対して演算を行う必要があります。また、途中で測定を行ってしまうと量子状態が収束して計算が壊れてしまうため、判定結果はアンシラビットに一時保存し、測定は全ての計算が終わった最後に行う必要があります。
実装：Qiskitによるモジュラ加算器
それでは、具体的な実装コードです。ここでは、すでにQFT変換された状態のレジスタに対して、定数 $C$ を足す関数 add_constant_mod_N を作成します。
import numpy as np
from qiskit import QuantumCircuit
from qiskit.circuit.library import QFT
def add_constant_mod_N(circuit, reg, ancilla, C, N):
n = len(reg)
# -------------------------------------------------------
# 1. +C (無条件加算)
# -------------------------------------------------------
for i in range(n):
angle = 2 * np.pi * C / (2**(n - i))
if abs(angle) > 1e-9:
circuit.p(angle, reg[i])
# -------------------------------------------------------
# 2. -N (試し引き: 無条件で引いてみる)
# -------------------------------------------------------
for i in range(n):
angle = -2 * np.pi * N / (2**(n - i))
if abs(angle) > 1e-9:
circuit.p(angle, reg[i])
# -------------------------------------------------------
# 3. 符号チェック (アンダーフロー判定)
# -------------------------------------------------------
# 一旦、周波数領域から時間領域に戻してMSB(最上位ビット)を見る
circuit.append(QFT(n, do_swaps=False, inverse=True).to_gate(), reg)
# MSBが1なら「負になった（引きすぎた）」ことを意味する
# その情報をアンシラビットにコピー
circuit.cx(reg[-1], ancilla)
# 再び周波数領域へ戻る（補正加算のため）
circuit.append(QFT(n, do_swaps=False).to_gate(), reg)
# -------------------------------------------------------
# 4. 補正 (負になった場合のみ +N して戻す)
# -------------------------------------------------------
for i in range(n):
angle = 2 * np.pi * N / (2**(n - i))
if abs(angle) > 1e-9:
# アンシラが 1 の時だけ足す (Controlled-Phase)
circuit.cp(angle, ancilla, reg[i])
# -------------------------------------------------------
# 5. アンシラの後始末 (Uncomputation)
# -------------------------------------------------------
# 【重要】使い終わったアンシラは必ずリセットする
circuit.reset(ancilla)
add_constant_modを実行する際は、入力regが事前にフーリエ変換されていることに注意してください。
QFT加算における負の数
QFT加算における「負の数」の扱いは、位相空間での回転として理解でき、例えば $-1$ を足す操作は、位相を逆回転させることに相当します。
$$\exp\left(2\pi i \frac{-1}{2^n}\right)$$
これは、周期性を利用すると以下のように書き換えられます。
$$\exp\left(2\pi i \left(\frac{-1}{2^n} + 1\right)\right) = \exp\left(2\pi i \frac{2^n - 1}{2^n}\right)$$
つまり、$-1$ は $2^n - 1$ （全てのビットが1の状態、$\ket{11\dots1}$）として表現されます。これは古典計算における2の補数表現が、位相空間でも自然に成り立っていることを示しています。そのため、使用するビット数は十分に大きく取る必要があります。
Nを差し引く回数
このアルゴリズムでは $N$ を引く処理を一回しか行っていません。「足し算の結果が $2N$ 以上になる場合、一回引くだけでは不十分ではないか？」と思われるかもしれませんが、回路への入力 $x$ と足す定数 $C$ が、ともに $N$ 未満であるという前提を守れば
$$\text{最大値} = (N-1) + (N-1) = 2N - 2$$
となり、和は必ず $2N$ 未満 になります。また事前に足し算の結果が大きいとわかっていればPython側で回路に入力する値を事前に % N しておけばこの前提を守ることができます。
アンコンピューティング
最後のcircuit.reset(ancilla)は非常に重要です。アンシラビットには途中で負になったかどうかという情報が残っています。これを放置すると、アンシラと計算用レジスタがエンタングルしたままになり、正しい計算結果が得られません。実機では逆演算を行ってきれいに $|0\rangle$ に戻す必要がありますが、今回はシミュレータ上での実験なのでreset命令で代用しています。
まとめ
今回は、QFTを利用した量子モジュラ加算器を実装しました。モジュラー足し算に関する記事がなかなか見当たらなかったのでこの記事が参考になれば幸いです。