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{right}}, k_{\text{right}}, 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 + m_{\text{right}}) + b ((-1)^m k_{\text{right}}k + k_{\text{right}})} \ket{a} \ket{b} \ket{0}_{n-1} \\ &= \sum_{0 \leq a < 2} \sum_{0 \leq b < 2} (-1)^{a (m + m_{\text{right}}) + b (k + k_{\text{right}})} \ket{a} \ket{b} \ket{0}_{n-1} \\ &= \sum_{0 \leq a < 2} \sum_{0 \leq b < 2} (-1)^{am_{\text{right}} + b k_{\text{right}}} (-1)^{am + bk} \ket{a} \ket{b} \ket{0}_{n-1} \end{align}

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

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

同様にして、ヒントの式を用いることによって、 $G(m', k')$ を $m_{\text{right}}, k_{\text{right}}, 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 + m_{\text{right}}} R^{c((-1)^{m_{\text{right}}} k + k_{\text{right}})} \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 + m_{\text{right}}} R^{(-1)^{m_{\text{right}}} ck + ck_{\text{right}}} \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} R^{ck} X^{m_{\text{right}}} R^{ck_{\text{right}}} \otimes I_1 \otimes I_{n-1} \right)(\ket{0} \ket{0} + \ket{1} \ket{1}) \ket{c}_{n-1} \end{align}

さて、前問では $X^{m_{\text{left}}}$ $R^{c k_{\text{left}}}$ が左から作用されていましたが、本問では $X^{m_{\text{right}}}$ $R^{c k_{\text{right}}}$ が右から作用されています。これが、この問題の核心となります。では、この $X^{m_{\text{right}}}$ $R^{c k_{\text{right}}}$ をどう扱えば良いでしょうか。

実は任意の行列 $U, V$ に対して、次の等式が成り立ちます。

\begin{equation} (UV \otimes I_{1}) (\ket{0}\ket{0} + \ket{1}\ket{1}) = (U \otimes V^{\text{T}}) (\ket{0}\ket{0} + \ket{1}\ket{1}) \end{equation}

このことから、 $X = X^{\text{T}}, R = R^{\text{T}}$ という性質を用いることで、次の式変形が成り立ちます。

\begin{align} \text{式 (11)} &= \sum_{1 \leq c < 2^{n-1}} \left( X^{m} R^{ck} \otimes \left( X^{m_{\text{right}}} R^{ck_{\text{right}}} \right)^\text{T} \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( I_1 \otimes \left( X^{m_{\text{right}}} R^{ck_{\text{right}}} \right)^\text{T} \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} \\ &= \sum_{1 \leq c < 2^{n-1}} \left( I_1 \otimes R^{ck_{\text{right}}} X^{m_{\text{right}}} \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$ をビット毎に展開すると、 $R^{ck_{\text{right}}} X^{m_{\text{right}}}$ は以下のようになります。

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

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

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

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

$n = 4, m_{\text{right}} = 1, k_{\text{right}} = 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_right: int, k_right: int) -> QuantumCircuit:
    a, b, c = QuantumRegister(1), QuantumRegister(1), QuantumRegister(n - 1)
    qc = QuantumCircuit(a, b, c)
 
    qc.x(c)
 
    if m_right:
        qc.compose(ZGate().control(len(c)), [*c, a[0]], inplace=True)
    if k_right % 2:
        qc.compose(ZGate().control(len(c)), [*c, b[0]], inplace=True)
 
    qc.x(c)
 
    if m_right:
        qc.compose(A3(n - 1), [b[0], *c], inplace=True)
 
    theta = 2 * math.pi / 2 ** (n - 1)
    for i in range(n - 1):
        angle = theta * k_right * (2 ** i)
        qc.compose(RZGate(angle).control(1),
                   [c[i], b[0]], inplace=True)
 
    return qc

B3: Right Action in Another Fourier Basis

解説

解答例