LogoQCoder Programming Contest 004
ログイン
← 前の解説次の解説 →

C3: Modular Arithmetic II

実行時間制限：3 秒

メモリ制限：512 MiB

配点：300点

Writer：PSL

解説

はじめに xx を二進展開します。

x=x0+2x1+⋯+2n−1xn−1(x0,x1,…,xn−1∈{0,1})\begin{equation} x = x_0 + 2x_1 + \cdots + 2^{n-1}x_{n-1} \quad (x_0, x_1, \ldots, x_{n-1} \in \{0, 1\}) \end{equation}

このとき、∣x⟩n∣y+ax mod L⟩n\ket{x}_n \ket{y + ax \ \text{mod} \ L}_n は以下のように展開できます。

∣x⟩n∣y+ax mod L⟩n=∣x0⟩∣x1⟩⋯∣xn−1⟩∣y+a(x0+2x1+⋯+2n−1xn−1) mod L⟩=∣x0⟩∣x1⟩⋯∣xn−1⟩∣y+ax0+(2a)x1+⋯+(2n−1a)xn−1 mod L⟩\begin{align} &\ket{x}_n \ket{y + ax \ \text{mod} \ L}_n \nonumber\\ &= \ket{x_0} \ket{x_1} \cdots \ket{x_{n-1}} \ket{y + a(x_0 + 2x_1 + \cdots + 2^{n-1}x_{n-1}) \ \text{mod} \ L} \nonumber\\ &= \ket{x_0} \ket{x_1} \cdots \ket{x_{n-1}} \ket{y + ax_0 + (2a)x_1 + \cdots + (2^{n-1}a)x_{n-1} \ \text{mod} \ L} \end{align}

よって、∣xi⟩\ket{x_i} を制御ビットとする問題 B5 の操作の制御回路 CB5\mathrm{CB5} を繰り返し作用させることでこの問題を解くことができます。

∣x⟩n∣y mod L⟩n∣0⟩1→CB5(a)∣x0⟩∣x1⟩⋯∣xn−1⟩∣y+ax0 mod L⟩∣0⟩→CB5(2a)∣x0⟩∣x1⟩⋯∣xn−1⟩∣y+ax0+(2a)x1 mod L⟩∣0⟩⋯→CB5(2n−1a)∣x0⟩∣x1⟩⋯∣xn−1⟩∣y+ax0+(2a)x1+⋯+(2n−1a)xn−1 mod L⟩∣0⟩\begin{align} &\ket{x}_n \ket{y \ \text{mod} \ L}_n \ket{0}_1 \nonumber\\ &\xrightarrow{\mathrm{CB5}(a)} \ket{x_0} \ket{x_1} \cdots \ket{x_{n-1}} \ket{y + ax_0 \ \text{mod} \ L} \ket{0} \nonumber\\ &\xrightarrow{\mathrm{CB5}(2a)} \ket{x_0} \ket{x_1} \cdots \ket{x_{n-1}} \ket{y + ax_0 + (2a)x_1 \ \text{mod} \ L} \ket{0} \nonumber\\ &\cdots \nonumber\\ &\xrightarrow{\mathrm{CB5}(2^{n-1}a)} \ket{x_0} \ket{x_1} \cdots \ket{x_{n-1}} \ket{y + ax_0 + (2a)x_1 + \cdots + (2^{n-1}a)x_{n-1} \ \text{mod} \ L} \ket{0} \end{align}

CB5(⋅)\mathrm{CB5}(\cdot) の入力は LL で mod\mathrm{mod} をとる必要があることに注意してください。

回路の深さは O(n2)O(n^2) です。

解答例

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

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 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 cadd(n: int, a: int) -> QuantumCircuit:
    qc = QuantumCircuit(n + 1)
 
    qc.compose(qft(n), qubits=range(n), inplace=True)
    qc.compose(crot(n, a), qubits=range(n + 1), inplace=True)
    qc.compose(qft(n).inverse(), qubits=range(n), inplace=True)
 
    return qc
 
 
def ccrot(n: int, a: int) -> QuantumCircuit:
    qc = QuantumCircuit(n + 2)
 
    for i in range(n):
        theta = 2 * math.pi * a * 2**i / 2**n
        qc.mcp(theta, [n, n + 1], i)
 
    return qc
 
 
def ccadd(n: int, a: int) -> QuantumCircuit:
    qc = QuantumCircuit(n + 2)
 
    qc.compose(qft(n), qubits=range(n), inplace=True)
    qc.compose(ccrot(n, a), qubits=range(n + 2), inplace=True)
    qc.compose(qft(n).inverse(), qubits=range(n), inplace=True)
 
    return qc
 
 
def cpack(n: int, s: int, t: int) -> QuantumCircuit:
    qc = QuantumCircuit(n + 2)
 
    qc.compose(ccadd(n, 2 ** (n + 1) - t), qubits=range(n + 2), inplace=True)
    qc.x(n)
    qc.compose(ccadd(n, -s), qubits=range(n + 2), inplace=True)
    qc.x(n)
 
    return qc
 
 
def solve(n: int, a: int, L: int) -> QuantumCircuit:
    x, y = QuantumRegister(n), QuantumRegister(n + 1)
    qc = QuantumCircuit(x, y)
 
    for i in range(n):
        b = (2**i * a) % L
        targets = [*y, x[i]]
        qc.compose(cadd(n + 1, 2**n - L), qubits=targets, inplace=True)
        qc.compose(cadd(n + 1, b), qubits=targets, inplace=True)
        qc.compose(cpack(n, 2**n - L + b, 2**n + b), qubits=targets, inplace=True)
        qc.compose(cadd(n + 1, b), qubits=targets, inplace=True)
 
    return qc