QCoder

解説

この問題は、問題 B6 の解法である量子位相推定において、はじめに適用するアダマールゲートを量子フーリエ変換に置き換えることで解くことができます。

$n = 2,\ m = 2$ の場合の回路図は次のように表されます。

以下、計算基底状態 $\ket{x}_n \ket{y}_m$ の状態遷移をみていきます。

はじめにレジスタ $\ket{y}_m$ に量子フーリエ変換を作用させます。

\begin{equation} \ket{y}_m \xrightarrow{\mathrm{QFT}} \sqrt{\frac{1}{2^m}} \sum_{k=0}^{2^m-1} \exp{\left(\frac{2\pi i y k}{2^m}\right)} \ket{k}_m \end{equation}

次に、問題 B6 の解説で定義したオラクル $P_{S}^{2^0}, P_{S}^{2^1}, \cdots, P_{S}^{2^{m-1}}$ を $\ket{y}_m$ の $j$ 番目を制御ビットとしてそれぞれ作用させます。

\begin{equation} \sqrt{\frac{1}{2^m}} \sum_{k=0}^{2^m-1} \exp{\left(\frac{2\pi i y k}{2^m}\right)} \ket{k}_m \xrightarrow{P_S^{2^0}, P_S^{2^1}, \cdots, P_S^{2^{m-1}}} \frac{1}{\sqrt{2^m}} \sum_{k=0}^{2^m-1} e^{\frac{2\pi i (y + f(x))k}{2^m}} \ket{k}_m \end{equation}

最後に、逆量子フーリエ変換を作用させることでレジスタ $\ket{y}_m$ を目的の状態に遷移させることができます。

\begin{align} \frac{1}{\sqrt{2^m}} \sum_{k=0}^{2^m-1} e^{\frac{2\pi i (y + f(x))k}{2^m}} \ket{k}_m \xrightarrow{\mathrm{IQFT}} \ket{(y + f(x))\ \mathrm{mod}\ 2^m}_m \end{align}

以上の操作により、次の状態遷移を実現する量子回路を実装できます。

\begin{equation} \ket{x}_{n}\ket{0}_{m} \xrightarrow{\mathrm{qc}} \ket{x}_{n}\ket{(y + f(x))\ \mathrm{mod}\ 2^m}_m \end{equation}

回路の深さは $4m + \mathrm{max}(n, m)$ です。

Writer 解説

Writer 解説 (pdf)

解答例

解答例は以下の通りです。

import math
 
from qiskit import QuantumCircuit, QuantumRegister
 
 
def qft(n: int) -> QuantumCircuit:
    qc = QuantumCircuit(n)
 
    for i in reversed(range(n)):
        qc.h(i)
        for j in reversed(range(i)):
            qc.cp(math.pi / 2 ** (i - j), j, i)
 
    for i in range(n // 2):
        qc.swap(i, n - i - 1)
 
    return qc
 
 
def solve(n: int, m: int, S: list[int]) -> QuantumCircuit:
    x, y = QuantumRegister(n), QuantumRegister(m)
    qc = QuantumCircuit(x, y)
    qft_m = qft(m)
 
    qc.compose(qft_m, y, inplace=True)
 
    for j in range(m):
        for i in range(n):
            theta = (2 * math.pi * S[i] / 2**m) * 2**j
            qc.cp(theta, x[i], y[j])
 
    qc.compose(qft_m.inverse(), y, inplace=True)
 
    return qc

B7: Quantum Arithmetic III

解説

Writer 解説

解答例