QCoder

解説

$E(m, k)$ を末尾の $n - 1$ 量子ビットが $\ket{0}_{n - 1}$ となる状態と、そうでない状態に分けて考えると見通しが良くなります。

まず、以下のように分解します。

\begin{equation} E(m, k) = \frac{1}{\sqrt{2^{n + 1}}} F(m, k) + \frac{1}{\sqrt{2^n}} G(m, k) \end{equation}

ここで、

\begin{equation} F(m, k) = \sum_{0 \leq a < 2} \sum_{0 \leq b < 2} (-1)^{am + bk} \ket{a} \ket{b} \ket{0}_{n-1} \end{equation}

\begin{equation} G(m, k) = \sum_{1 \leq c < 2^{n-1}} \left( X^m R^{ck} \otimes I_1 \otimes I_{n-1} \right)(\ket{0} \ket{0} + \ket{1} \ket{1}) \ket{c}_{n-1} \end{equation}

とします。

次に、ヒントの式を用いることによって、 $F(m', k')$ を $m_{\text{left}}, k_{\text{left}}, m, k$ で表します。

\begin{align} F(m', k') &= \sum_{0 \leq a < 2} \sum_{0 \leq b < 2} (-1)^{am' + bk'} \ket{a} \ket{b} \ket{0}_{n-1} \\ &= \sum_{0 \leq a < 2} \sum_{0 \leq b < 2} (-1)^{a (m_{\text{left}} + m) + b ((-1)^m k_{\text{left}} + k)} \ket{a} \ket{b} \ket{0}_{n-1} \\ &= \sum_{0 \leq a < 2} \sum_{0 \leq b < 2} (-1)^{a (m_{\text{left}} + m) + b (k_{\text{left}} + k)} \ket{a} \ket{b} \ket{0}_{n-1} \\ &= \sum_{0 \leq a < 2} \sum_{0 \leq b < 2} (-1)^{am_{\text{left}} + b k_{\text{left}}} (-1)^{am + bk} \ket{a} \ket{b} \ket{0}_{n-1} \end{align}

よって、末尾の $n - 1$ 量子ビットが $0$ のときに必要となる操作は以下の二つになります。

$m_{\text{left}} \equiv 1 \ (\text{mod} \ 2)$ なら、 $\ket{a}$ に $Z$ ゲートを作用させる。
$k_{\text{left}} \equiv 1 \ (\text{mod} \ 2)$ なら、 $\ket{b}$ に $Z$ ゲートを作用させる。

同様にして、ヒントの式を用いることによって、 $G(m', k')$ を $m_{\text{left}}, k_{\text{left}}, m, k$ で表します。

\begin{align} G(m', k') &= \sum_{1 \leq c < 2^{n-1}} \left( X^{m'} R^{ck'} \otimes I_1 \otimes I_{n-1} \right)(\ket{0} \ket{0} + \ket{1} \ket{1}) \ket{c}_{n-1} \\ &= \sum_{1 \leq c < 2^{n-1}} \left( X^{m_{\text{left}} + m} R^{c((-1)^m k_{\text{left}} + k)} \otimes I_1 \otimes I_{n-1} \right)(\ket{0} \ket{0} + \ket{1} \ket{1}) \ket{c}_{n-1} \\ &= \sum_{1 \leq c < 2^{n-1}} \left( X^{m_{\text{left}} + m} R^{(-1)^m ck_{\text{left}} + ck} \otimes I_1 \otimes I_{n-1} \right)(\ket{0} \ket{0} + \ket{1} \ket{1}) \ket{c}_{n-1} \\ &= \sum_{1 \leq c < 2^{n-1}} \left( X^{m_{\text{left}}} R^{ck_{\text{left}}} X^{m} R^{ck} \otimes I_1 \otimes I_{n-1} \right)(\ket{0} \ket{0} + \ket{1} \ket{1}) \ket{c}_{n-1} \\ &= \sum_{1 \leq c < 2^{n-1}} \left( X^{m_{\text{left}}} R^{ck_{\text{left}}} \otimes I_1 \otimes I_{n-1} \right) \left( X^{m} R^{ck} \otimes I_1 \otimes I_{n-1} \right) (\ket{0} \ket{0} + \ket{1} \ket{1}) \ket{c}_{n-1} \\ \end{align}

そして、 $c$ をビット毎に展開すると、 $X^{m_{\text{left}}} R^{ck_{\text{left}}}$ は以下のようになります。

\begin{equation} X^{m_{\text{left}}} R^{ck_{\text{left}}} = X^{m_{\text{left}}} R^{c_0 k_{\text{left}}} R^{c_1 (2 k_{\text{left}})} ... \ R^{c_{n-2} (2^{n-2} k_{\text{left}})} \end{equation}

よって、末尾の $n - 1$ 量子ビットに $1$ が含まれるときに必要となる操作は以下の二つになります。

任意の $j \in \lbrace0, 1, \dots, n-2\rbrace$ に対して $c_{j} = 1$ なら、 $\ket{a}$ に $R^{2^j k_{\text{left}}}$ を作用させる。（これは、回転ゲート $Rz$ を利用して実装できます。）
$m_{\text{left}} \equiv 1 \ (\text{mod} \ 2)$ なら、 $\ket{a}$ に $X$ を作用させる。（これは、問題 A3の回路を利用して実装できます。）

以上の操作を順に行うことで、目的の量子状態を得ることができます。

$n = 4, m_{\text{left}} = 1, k_{\text{left}} = 2$ の場合の量子回路は次のように表されます。

回路の深さは $O(n)$ です。

解答例

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

import math
 
from qiskit import QuantumCircuit, QuantumRegister
from qiskit.circuit.library import XGate, ZGate, RZGate
 
 
def A3(n: int) -> QuantumCircuit:
    m, k = QuantumRegister(1), QuantumRegister(n)
    qc = QuantumCircuit(m, k)
 
    qc.x(m[0])
 
    qc.x(k)
 
    qc.compose(XGate().control(len(k)), [*k, m[0]], inplace=True)
 
    qc.x(k)
 
    return qc
 
 
def solve(n: int, m_left: int, k_left: int) -> QuantumCircuit:
    a, b, c = QuantumRegister(1), QuantumRegister(1), QuantumRegister(n - 1)
    qc = QuantumCircuit(a, b, c)
 
    qc.x(c)
 
    if m_left:
        qc.compose(ZGate().control(len(c)), [*c, a[0]], inplace=True)
    if k_left % 2:
        qc.compose(ZGate().control(len(c)), [*c, b[0]], inplace=True)
 
    qc.x(c)
 
    theta = 2 * math.pi / 2 ** (n - 1)
    for i in range(n - 1):
        angle = theta * k_left * (2 ** i)
        qc.compose(RZGate(angle).control(1),
                   [c[i], a[0]], inplace=True)
 
    if m_left:
        qc.compose(A3(n - 1), [a[0], *c], inplace=True)
 
    return qc

B2: Left Action in Another Fourier Basis

解説

解答例