QCoder

解説

この問題は問題 B5 のオラクルを利用して、量子位相推定 ¹ と呼ばれる量子アルゴリズムを適用することで解くことができます。

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

以下、下位 $m$ ビットをレジスタ $\ket{y}_m$ と表記して、上位 $n$ ビットの計算基底状態 $\ket{x}_n$ に対するレジスタ $\ket{y}_m$ の状態遷移をみていきます。

はじめにレジスタ $\ket{y}_m = \ket{0}$ の各量子ビットにアダマールゲートを作用させ、一様重ね合わせ状態を生成します。

\begin{align} \ket{0}_m &\xrightarrow{H^{\otimes n}} \frac{1}{\sqrt{2^m}} \sum_{k=0}^{2^m-1} \ket{k}_m \nonumber\\ &= \frac{1}{\sqrt{2^m}} (\ket{0} + \ket{1}) \otimes (\ket{0} + \ket{1}) \otimes \cdots \otimes (\ket{0} + \ket{1}) \end{align}

ここで、問題 B5 では次の遷移を実現するオラクルを実装しました。

\begin{equation} \ket{x} \xrightarrow{O} \exp{\left(\frac{2\pi i f(x)}{2^m}\right)}\ket{x} \end{equation}

ここで、このオラクルの位相に $2^j$ をかけたようなオラクルを $P_{S}^{2^j}$ として定義します。

\begin{equation} \ket{x} \xrightarrow{P_{S}^{2^j}} \exp{\left(\frac{2\pi i f(x)}{2^m} \cdot 2^j\right)}\ket{x} \end{equation}

次に、生成した一様重ね合わせ状態に対して、レジスタ $\ket{y}_m$ の $j$ 番目を制御ビットとしたオラクル $P_{S}^{2^j}$ をそれぞれ $\ket{x}$ に対して作用させます。

\begin{align} &\frac{1}{\sqrt{2^m}} (\ket{0} + \ket{1}) \otimes (\ket{0} + \ket{1}) \otimes \cdots \otimes (\ket{0} + \ket{1}) \nonumber \\ \xrightarrow{P_S^{2^0}, P_S^{2^1}, \cdots, P_S^{2^{m-1}}} &\frac{1}{\sqrt{2^m}} (\ket{0} + e^{\frac{2\pi i f(x)\cdot 2^0}{2^m}}\ket{1}) \otimes (\ket{0} + e^{\frac{2\pi i f(x)\cdot 2^1}{2^m}}\ket{1}) \otimes \cdots \otimes (\ket{0} + e^{\frac{2\pi i f(x)\cdot 2^{m-1}}{2^m}}\ket{1}) \nonumber\\ = &\frac{1}{\sqrt{2^m}} \sum_{k=0}^{2^m-1} e^{\frac{2\pi i f(x)k}{2^m}} \ket{k}_m \end{align}

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

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

(5) 式の遷移は、次式で表される量子フーリエ変換の定義から明らかです。

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

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

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

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

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)
 
    qc.h(y)
 
    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

量子位相推定については加藤拓己さんの「世界一分かりやすい量子位相推定」を参照してください。 ↩

B6: Quantum Arithmetic II

解説

Writer 解説

解答例

Footnotes