QCoder

解説

まずは問題文を扱いやすい形に書き換えましょう。

\begin{equation} X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \quad R = \begin{pmatrix} \exp\left(- \frac{2\pi i}{2 ^n}\right) & 0 \\ 0 & \exp\left(\frac{2\pi i}{2 ^n}\right) \end{pmatrix} \end{equation}

とします。

実は、操作 $g(m, k)$ を行列

\begin{equation} X^{m} R^{k} \end{equation}

と対応させることができます。

すなわち、問題文を以下のように書き換えることができます。

次の条件を満たすオラクル $O$ を、 $n + 1$ 量子ビットをもつ量子回路 $\mathrm{qc}$ 上に実装せよ。

$0 \leq m < 2$ , $0 \leq k < 2^{n}$ を満たす任意の整数の組 $(m,k)$ に対して
$\ket{m}\ket{k}_n \xrightarrow{O} \ket{m'}\ket{k'}_n$
ただし、 $0 \leq m' < 2$ , $0 \leq k' < 2^{n}$ は以下を満たす必要がある。
$X^{m'}R^{k'} = X^{m_{\text{after}}}R^{k_{\text{after}}} X^{m}R^{k} X^{m_{\text{before}}}R^{k_{\text{before}}}$

では、この問題を解く方法について考えていきましょう。

オラクル $E$ を B2, B3 で定義されている状態への変換

\begin{equation} \ket{m}\ket{k} \xrightarrow{E} E(m,k) \end{equation}

とします。これさえ作ることができれば、以下のようにすることでこの問題の解答が得られます。

\begin{equation} \ket{m}\ket{k} \xrightarrow{E} E(m,k) \xrightarrow{\mathrm{B2}} \xrightarrow{\mathrm{B3}} E(m',k') \xrightarrow{E^{\dagger}} \ket{m'}\ket{k'} \end{equation}

$\text{QFT}$ と A4, A5 の量子回路を使うと、 $E(m,k)$ にかなり似た式の状態を作れます。最後は A2, A3 のような量子回路を作用させて微修正しましょう。

全体としての状態遷移は以下の通りです。

\begin{align} \ket{m}\ket{k}_{n} &\xrightarrow{\text{QFT}} \sqrt{\frac{1}{2^{n}}} \sum_{0 \leq c < 2^{n-1}} \sum_{0 \leq b < 2} \exp\left(\frac{2\pi i}{2 ^n}(c+2^{n-1}b)k\right) \ket{m} \ket{c}_{n-1} \ket{b} \\ &= \sqrt{\frac{1}{2^{n}}} \sum_{0 \leq c < 2^{n-1}} \sum_{0 \leq b < 2} (-1)^{bk} \exp\left({\frac{2\pi i}{2 ^n}ck}\right) \ket{m} \ket{c}_{n-1} \ket{b} \\ &\xrightarrow{\mathrm{A4}} \sqrt{\frac{1}{2^{n}}} \sum_{0 \leq b < 2} \sum_{0 \leq c < 2^{n-1}} (-1)^{bk} \exp\left(\frac{2\pi i}{2 ^n}ck\right) \ket{m} \ket{b} \ket{c}_{n-1} \\ &= \sqrt{\frac{1}{2^{n}}} \sum_{0 \leq b < 2} (-1)^{bk} \ket{m} \ket{b} \ket{0}_{n-1} + \sqrt{\frac{1}{2^{n}}} \sum_{1 \leq c < 2^{n-1}} \exp\left(\frac{2\pi i}{2 ^n}ck\right) \ket{m} \ket{0} \ket{c}_{n-1} \nonumber \\ &\hspace{6em} + \sqrt{\frac{1}{2^{n}}} \sum_{1 \leq c < 2^{n-1}} (-1)^{k} \exp\left(\frac{2\pi i}{2 ^n}ck\right) \ket{m} \ket{1} \ket{c}_{n-1} \\ &\xrightarrow{\text{制御}\mathrm{A5}} \sqrt{\frac{1}{2^{n}}} \sum_{0 \leq b < 2} (-1)^{bk} \ket{m} \ket{b} \ket{0}_{n-1} + \sqrt{\frac{1}{2^{n}}} \sum_{1 \leq c < 2^{n-1}} \exp\left(\frac{2\pi i}{2 ^n}ck\right) \ket{m} \ket{0} \ket{c}_{n-1} \nonumber \\ &\hspace{6em} + \sqrt{\frac{1}{2^{n}}} \sum_{1 \leq c < 2^{n-1}} (-1)^{k} \exp\left(\frac{2\pi i}{2 ^n}ck\right) \ket{m} \ket{1} \ket{2^{n-1}-c}_{n-1} \\ &= \sqrt{\frac{1}{2^{n}}} \sum_{0 \leq b < 2} (-1)^{bk} \ket{m} \ket{b} \ket{0}_{n-1} + \sqrt{\frac{1}{2^{n}}} \sum_{1 \leq c < 2^{n-1}} \exp\left(\frac{2\pi i}{2 ^n}ck\right) \ket{m} \ket{0} \ket{c}_{n-1} \nonumber \\ &\hspace{6em} + \sqrt{\frac{1}{2^{n}}} \sum_{1 \leq c < 2^{n-1}} (-1)^{k} \exp\left(\frac{2\pi i}{2 ^n}(2^{n-1}-c)k\right) \ket{m} \ket{1} \ket{c}_{n-1}\\ &= \sqrt{\frac{1}{2^{n}}} \sum_{0 \leq b < 2} (-1)^{bk} \ket{m} \ket{b} \ket{0}_{n-1} + \sqrt{\frac{1}{2^{n}}} \sum_{1 \leq c < 2^{n-1}} \exp\left(\frac{2\pi i}{2 ^n}ck\right) \ket{m} \ket{0} \ket{c}_{n-1} \nonumber \\ &\hspace{6em} + \sqrt{\frac{1}{2^{n}}} \sum_{1 \leq c < 2^{n-1}} \exp\left(-\frac{2\pi i}{2 ^n}ck\right) \ket{m} \ket{1} \ket{c}_{n-1}\\ &= \sqrt{\frac{1}{2^{n}}} \sum_{0 \leq b < 2} (-1)^{bk} \ket{m} \ket{b} \ket{0}_{n-1} \nonumber \\ &\hspace{6em} + \sqrt{\frac{1}{2^{n}}} \sum_{1 \leq c < 2^{n-1}} \left\lbrace\exp\left(\frac{2\pi i}{2 ^n}ck\right) \ket{m} \ket{0} + \exp\left(-\frac{2\pi i}{2 ^n}ck\right) \ket{m} \ket{1}\right\rbrace\ket{c}_{n-1} \\ &\xrightarrow{\mathrm{A2}} \sqrt{\frac{1}{2^{n+1}}} \sum_{0 \leq a < 2} \sum_{0 \leq b < 2} (-1)^{am+bk} \ket{a} \ket{b} \ket{0}_{n-1} \nonumber \\ &\hspace{6em} + \sqrt{\frac{1}{2^{n}}} \sum_{1 \leq c < 2^{n-1}} \left\lbrace\exp\left(\frac{2\pi i}{2 ^n}ck\right) \ket{m} \ket{0} + \exp\left(-\frac{2\pi i}{2 ^n}ck\right) \ket{m} \ket{1}\right\rbrace\ket{c}_{n-1} \\ &\xrightarrow{\mathrm{A3}} \sqrt{\frac{1}{2^{n+1}}} \sum_{0 \leq a < 2} \sum_{0 \leq b < 2} (-1)^{am+bk} \ket{a} \ket{b} \ket{0}_{n-1} \nonumber \\ &\hspace{6em} + \sqrt{\frac{1}{2^{n}}} \sum_{1 \leq c < 2^{n-1}} \left\lbrace\exp\left(\frac{2\pi i}{2 ^n}ck\right) \ket{m} \ket{1} + \exp\left(-\frac{2\pi i}{2 ^n}ck\right) \ket{m} \ket{0}\right\rbrace\ket{c}_{n-1} \\ &\xrightarrow{\text{微修正}} \sqrt{\frac{1}{2^{n+1}}} \sum_{0 \leq a < 2} \sum_{0 \leq b < 2} (-1)^{am+bk} \ket{a} \ket{b} \ket{0}_{n-1} \nonumber \\ &\hspace{6em} + \sqrt{\frac{1}{2^{n}}} \sum_{1 \leq c < 2^{n-1}} \left\lbrace\exp\left(\frac{2\pi i}{2 ^n}ck\right) \ket{m \oplus 1} \ket{1} + \exp\left(-\frac{2\pi i}{2 ^n}ck\right) \ket{m} \ket{0}\right\rbrace\ket{c}_{n-1} \\ &= \sqrt{\frac{1}{2^{n+1}}} \sum_{0 \leq a < 2} \sum_{0 \leq b < 2} (-1)^{am+bk} \ket{a} \ket{b} \ket{0}_{n-1} \nonumber \\ &\hspace{6em} + \sqrt{\frac{1}{2^{n}}} \sum_{1 \leq c < 2^{n-1}} (X^{m}R^{ck} \otimes I_1 \otimes I_{n-1}) ( \ket{0} \ket{0} + \ket{1} \ket{1})\ket{c}_{n-1} \\ \end{align}

よって、この問題を解くことができます。

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

解答例

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

import math
 
from qiskit import QuantumCircuit, QuantumRegister
from qiskit.circuit.library import ZGate, RZGate, HGate, XGate
 
 
def A2(n: int) -> QuantumCircuit:
    m, k = QuantumRegister(1), QuantumRegister(n)
    qc = QuantumCircuit(m, k)
 
    qc.x(k)
 
    qc.compose(HGate().control(len(k)), [*k, m[0]], inplace=True)
 
    qc.x(k)
 
    return qc
 
 
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 A3_alt(n: int) -> QuantumCircuit:
    a, b, c = QuantumRegister(1), QuantumRegister(1), QuantumRegister(n - 1)
    qc = QuantumCircuit(a, b, c)
 
    qc.cx(b[0], a[0])
 
    qc.x(c)
 
    qc.compose(XGate().control(len(c) + 1), [*c, *b, *a], inplace=True)
 
    qc.x(c)
 
    return qc
 
 
def A4(n: int) -> QuantumCircuit:
    L = n + 1
    qc = QuantumCircuit(L)
 
    for i in range(L.bit_length()):
        for j in range(0, L - (2 ** i), 2 ** (i + 1)):
            qc.swap(j, j + (2 ** i))
 
    return qc
 
 
def A5_alt(n: int) -> QuantumCircuit:
    b, c = QuantumRegister(1), QuantumRegister(n - 1)
    qc = QuantumCircuit(b, c)
 
    for i in range(n-1):
        qc.compose(XGate().control(1), [b[0], c[i]], inplace=True)
 
    for i in reversed(range(1, n-1)):
        qc.compose(XGate().control(i+1), [b[0]] + [c[j]
                   for j in range(i)] + [c[i]], inplace=True)
 
    qc.compose(XGate().control(1), [b[0], c[0]], inplace=True)
 
    return qc
 
 
def B2(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
 
 
def B3(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
 
 
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 dqft(n: int) -> QuantumCircuit:
    a, b, c = QuantumRegister(1), QuantumRegister(1), QuantumRegister(n-1)
    qc = QuantumCircuit(a, b, c)
 
    qc.compose(qft(n), qubits=[*b, *c], inplace=True)
    qc.compose(A4(n - 1), qubits=[*b, *c], inplace=True)
    qc.compose(A5_alt(n), qubits=[*b, *c], inplace=True)
    qc.compose(A2(n - 1), qubits=[*a, *c], inplace=True)
    qc.compose(A3(n - 1), qubits=[*b, *c], inplace=True)
    qc.compose(A3_alt(n), qubits=[*a, *b, *c], inplace=True)
 
    return qc
 
 
def solve(n: int, m_before: int, k_before: int, m_after: int, k_after: int) -> QuantumCircuit:
    qc = QuantumCircuit(n + 1)
 
    qc.compose(dqft(n), inplace=True)
    qc.compose(B3(n, m_before, k_before), inplace=True)
    qc.compose(B2(n, m_after, k_after), inplace=True)
    qc.compose(dqft(n).inverse(), inplace=True)
 
    return qc

探求

問題 B, Exの背景について

問題 B1 は、次のような基本的なアイデアに基づいています：

状態 $\ket{k}$ を状態 $\ket{k+a}$ に遷移させたければ、まず $\ket{k}$ にフーリエ変換を施し、位相ゲートをかけてから逆フーリエ変換で元に戻す

という手順を踏めば良いということです。ここでの加算「 $+$ 」は、巡回群 $\mathbb{Z} / 2^n \mathbb{Z}$ 上の群演算を意味しています。

さて、今回のコンテストのテーマは、より構造の複雑な群である二面体群 $D_{2^n}$ に対して同様のことが可能か？という問いかけです。
二面体群は巡回群とは異なり、基本的に演算が非可換であるという点が大きな違いです。

実は、二面体群の世界にも「フーリエ変換」に相当する操作があります。それがオラクル $E$ です。
この $E(m,k)$ の式をよく見ると、 $m, k$ が全て指数部に現れており、通常のフーリエ変換と非常に似た構造になっていることに気付くはずです。

今回のコンテストでぜひ注目してほしいのは以下の点です：

問題 B2: 群の左からの作用を計算したければ、フーリエ基底上でも左のビットに演算を施せば良い。
問題 B3: 群の右からの作用を計算したければ、フーリエ基底上でも右のビットに演算を施せば良い。

$E(m,k)$ の式がどこから来たのか知りたい方は、群の表現論について調べてみてください。
「オラクル $E$ の回路は思い付かないでしょう」と思った方は以下を参考にしてください。

Püschel, M., Rötteler, M., and Beth, T. (1998). Fast Quantum Fourier Transforms for a Class of Non-Abelian Groups. arXiv:quant-ph/9807064.

Ex: Reverse and Shift

解説

解答例

探求