QCoder

解説

量子フーリエ変換 ( $\mathrm{QFT}$ ) は次のように定義されます：

$0$ 以上 $2^n$ 未満の任意の整数 $j$ に対して、次式を満たす $n$ 量子ビットオラクル

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

よって、 $\mathrm{QFT}$ と問題B2の操作（制御位相シフト）、逆量子フーリエ変換 ( $\mathrm{IQFT}$ ) を組み合わせることでこの問題を解くことができます。

\begin{align} \ket{k}_n\ket{c}_1 &\xrightarrow{\mathrm{QFT}} \sqrt{\frac{1}{2^n}} \sum_{j=0}^{2^n-1} \exp{\left(\frac{2\pi i j k}{2^n}\right)} \ket{j}_n\ket{c}_1 \nonumber\\ &\xrightarrow{\text{問題 B2 の操作}} \sqrt{\frac{1}{2^n}} \sum_{j=0}^{2^n-1} \exp{\left(\frac{2\pi i(k + ca)j}{2^n}\right)} \ket{j}_n\ket{c}_1 \nonumber\\ &\xrightarrow{\mathrm{IQFT}} \ket{(k + ca) \bmod 2^n}_n \ket{c}_1 \end{align}

$\mathrm{QFT}$ と $\mathrm{IQFT}$ は必ずしも制御ゲートとする必要はありません。回路の深さは $O(n)$ です。

解答例

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

import math
 
from qiskit import QuantumCircuit
 
 
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
 
 
# B2
def crot(n: int, a: int) -> QuantumCircuit:
    qc = QuantumCircuit(n + 1)
 
    for i in range(n):
        theta = 2 * math.pi * a * 2**i / 2**n
        qc.cp(theta, n, i)
 
    return qc
 
 
def solve(n: int, a: int) -> QuantumCircuit:
    k, c = QuantumRegister(n), QuantumRegister(1)
    qc = QuantumCircuit(k, c)
 
    qc.compose(qft(n), qubits=k, inplace=True)
    qc.compose(crot(n, a), qubits=[*k, *c], inplace=True)
    qc.compose(qft(n).inverse(), qubits=k, inplace=True)
 
    return qc

B3: Controlled Constant Addition

解説

解答例