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

C5: Modular Arithmetic IV

実行時間制限：10 秒

メモリ制限：512 MiB

配点：600点

Writer：PSL

※ 本ページの下（探求）で今回の問題がどのようにショアのアルゴリズムに繋がるかを解説しています。

解説

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

k=k0+2k1+⋯+2n−1kn−1(k0,k1,…,kn−1∈{0,1})\begin{equation} k = k_0 + 2k_1 + \cdots + 2^{n-1}k_{n-1} \quad (k_0, k_1, \ldots, k_{n-1} \in \{0, 1\}) \end{equation}

このとき、所望の状態は以下のように展開できます。

12m∑k=02n−1∣k⟩n∣ak mod L⟩2m+1=12m∑k=02n−1∣k0⟩∣k1⟩⋯∣kn−1⟩∣ak0+2k1+⋯2n−1kn−1 mod L⟩2m+1=12m∑k=02n−1∣k0⟩∣k1⟩⋯∣kn−1⟩∣ak0a2k1⋯a2n−1kn−1 mod L⟩2m+1\begin{align} &\frac{1}{\sqrt{2^m}} \sum_{k=0}^{2^n-1} \ket{k}_{n} \ket{a^k \bmod L}_{2m+1} \nonumber\\ &= \frac{1}{\sqrt{2^m}} \sum_{k=0}^{2^n-1} \ket{k_0} \ket{k_1} \cdots \ket{k_{n-1}} \ket{a^{k_0 + 2k_1 + \cdots 2^{n-1}k_{n-1}} \bmod L}_{2m+1} \nonumber\\ &= \frac{1}{\sqrt{2^m}} \sum_{k=0}^{2^n-1} \ket{k_0} \ket{k_1} \cdots \ket{k_{n-1}} \ket{a^{k_0}a^{2k_1}\cdots a^{2^{n-1}k_{n-1}} \bmod L}_{2m+1} \end{align}

よって、∣ki⟩\ket{k_i} を制御ビットとした問題 C4 の操作の制御回路 CC4\mathrm{CC4} を利用することで、所望の操作が実現できます。

∣0⟩n∣0⟩2m+1→H⊗n12m∑k=02n−1∣k0⟩∣k1⟩⋯∣kn−1⟩∣0⟩2m+1→X12m∑k=02n−1∣k0⟩∣k1⟩⋯∣kn−1⟩∣1⟩2m+1→CC4(a)12m∑k=02n−1∣k0⟩∣k1⟩⋯∣kn−1⟩∣ak0 mod L⟩2m+1→CC4(a2)12m∑k=02n−1∣k0⟩∣k1⟩⋯∣kn−1⟩∣ak0a2k1 mod L⟩2m+1⋯→CC4(a2n−1)12m∑k=02n−1∣k0⟩∣k1⟩⋯∣kn−1⟩∣ak0a2k1⋯a2n−1kn−1 mod L⟩2m+1\begin{align} &\ket{0}_n \ket{0}_{2m+1} \nonumber\\ &\xrightarrow{H^{\otimes n}} \frac{1}{\sqrt{2^m}} \sum_{k=0}^{2^n-1} \ket{k_0} \ket{k_1} \cdots \ket{k_{n-1}} \ket{0}_{2m+1} \nonumber\\ &\xrightarrow{X} \frac{1}{\sqrt{2^m}} \sum_{k=0}^{2^n-1} \ket{k_0} \ket{k_1} \cdots \ket{k_{n-1}} \ket{1}_{2m+1} \nonumber\\ &\xrightarrow{\mathrm{CC4}(a)} \frac{1}{\sqrt{2^m}} \sum_{k=0}^{2^n-1} \ket{k_0} \ket{k_1} \cdots \ket{k_{n-1}} \ket{a^{k_0} \bmod L}_{2m+1} \nonumber\\ &\xrightarrow{\mathrm{CC4}(a^2)} \frac{1}{\sqrt{2^m}} \sum_{k=0}^{2^n-1} \ket{k_0} \ket{k_1} \cdots \ket{k_{n-1}} \ket{a^{k_0}a^{2k_1} \bmod L}_{2m+1} \nonumber\\ &\cdots \nonumber \\ &\xrightarrow{\mathrm{CC4}(a^{2^{n-1}})} \frac{1}{\sqrt{2^m}} \sum_{k=0}^{2^n-1} \ket{k_0} \ket{k_1} \cdots \ket{k_{n-1}} \ket{a^{k_0}a^{2k_1} \cdots a^{2^{n-1}k_{n-1}} \bmod L}_{2m+1} \end{align}

回路の深さは O(n3)O(n^3) です。

解答例

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

import math
 
from qiskit import QuantumCircuit, QuantumRegister
 
 
def inv_mod(a: int, L: int) -> int:
    def extended_euclidean(a: int, b: int) -> tuple[int, int, int]:
        # when b == 0:
        if b == 0:
            return a, 1, 0
 
        # recursive step
        gcd, x1, y1 = extended_euclidean(b, a % b)
 
        # update x and y
        x = y1
        y = x1 - (a // b) * y1
 
        return gcd, x, y
 
    _, x, _ = extended_euclidean(a, L)
    return x % L
 
 
def beki(n: int, a: int, L: int) -> list[int]:
    result = [a]
    for _ in range(n - 1):
        result.append(result[-1] ** 2 % L)
 
    return result
 
 
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 mcadd(n: int, a: int, c: int) -> QuantumCircuit:
    qc = QuantumCircuit(n + c)
 
    qc.compose(qft(n), qubits=range(n), inplace=True)
    for i in range(n):
        theta = 2 * math.pi * a * 2**i / 2**n
        if c == 0:
            qc.p(theta, i)
        elif c == 1:
            qc.cp(theta, n, i)
        else:
            qc.mcp(theta, list(range(n, n + c)), i)
    qc.compose(qft(n).inverse(), qubits=range(n), inplace=True)
 
    return qc
 
 
def mcadd_mod(n: int, a: int, L: int, c: int) -> QuantumCircuit:
    qc = QuantumCircuit(n + 1 + c)
 
    qc.compose(mcadd(n + 1, 2**n - L + a, c), qubits=range(n + 1 + c), inplace=True)
 
    qc.x(n)
    qc.compose(mcadd(n, -(2**n - L + a), c + 1), qubits=range(n + 1 + c), inplace=True)
    qc.x(n)
 
    qc.compose(mcadd(n, 2**n - a, c + 1), qubits=range(n + 1 + c), inplace=True)
 
    qc.compose(mcadd(n + 1, a, c), qubits=range(n + 1 + c), inplace=True)
 
    return qc
 
 
def cswap(n: int) -> QuantumCircuit:
    qc = QuantumCircuit(2 * n + 1)
 
    for i in range(n):
        qc.cswap(2 * n, i, i + n)
 
    return qc
 
 
def solve(n: int, m: int, a: int, L: int) -> QuantumCircuit:
    x, y = QuantumRegister(n), QuantumRegister(2 * m + 1)
    qc = QuantumCircuit(x, y)
 
    qc.h(x)
    qc.x(y[0])
 
    lst = beki(n, a, L)
    a_inv = inv_mod(a, L)
    lst_inv = beki(n, a_inv, L)
    lst_minus_inv = [(-v) % L for v in lst_inv]
    for i in range(n):
        b = lst[i]
        for j in range(m):
            qc.compose(mcadd_mod(m, b, L, 2), qubits=[*y[m:], x[i], y[j]], inplace=True)
            b = 2 * b % L
 
        qc.compose(cswap(m), qubits=[*y[: 2 * m], x[i]], inplace=True)
 
        b = lst_minus_inv[i]
        for j in range(m):
            qc.compose(mcadd_mod(m, b, L, 2), qubits=[*y[m:], x[i], y[j]], inplace=True)
            b = 2 * b % L
 
    return qc

探求

今回のコンテストの問題案の原案には最後に以下のような問題 D1, D2 がありました。 ジャッジシステムの都合で出題には至りませんでしたが、ショアのアルゴリズムについての理解を深めるために問題と解説を残しておきます。

問題 D1

整数 nn, mm, aa, LL が入力として与えられる。 入力は 1≤L≤2n1 \leq L \leq 2^n と 0≤a<L0 \leq a < L を満たし、aa と LL は互いに素であるものとする。

ゼロ状態から重ね合わせ状態 ∣B⟩\ket{B} を作り出す操作を、n+2m+1{n + 2m + 1} 量子ビットをもつ量子回路 qc\mathrm{qc} 上に実装し、左側の nn 量子ビットを観測して、ak mod La^k \bmod L の周期 rr を推定せよ。

重ね合わせ状態 ∣B⟩\ket{B} は次式で定義される：

∣B⟩n+2m+1=(IQFT⊗I)12m∑k=02m−1∣k⟩n∣ak mod L⟩2m+1\ket{B}_{n + 2m +1} = \left( \mathrm{IQFT} \otimes I \right) \frac{1}{\sqrt{2^m}} \sum_{k=0}^{2^m-1} \ket{k}_{n} \ket{a^k \bmod L}_{2m + 1}

D1の解説

開く∣C5⟩=12m∑k=02m−1∣k⟩∣gk mod L⟩\begin{equation} \ket{\mathrm{C5}} = \frac{1}{\sqrt{2^m}} \sum_{k=0}^{2^m-1} \ket{k} \ket{g^k \bmod L} \end{equation}

∣C5⟩\ket{\mathrm{C5}} の変形を考えたいですが、まずは以下の A, B, C, D の式を準備します。

GG を以下のように定義します。

任意の xx に対し

G∣x mod L⟩=∣gx mod L⟩⋯A\begin{equation} G \ket{x \bmod L} = \ket{gx \bmod L} \cdots A \end{equation}

突然ですが、0≤s<r0 \leq s < r に対し、∣us⟩\ket{u_{s}} を次のように定義します。

∣us⟩=1r∑k=0r−1exp⁡(−2πiksr)∣gk mod L⟩⋯B\begin{equation} \ket{u_{s}} = \frac{1}{\sqrt{r}} \sum_{k=0}^{r-1} \exp\left(\frac{-2\pi i ks}{r}\right) \ket{g^k \bmod L} \cdots B \end{equation}

このとき ∣us⟩\ket{u_{s}} について以下の C, D が成り立ちます。

1r∑s=0r−1∣us⟩=∣1⟩⋯C\begin{equation} \frac{1}{\sqrt{r}} \sum_{s=0}^{r-1} \ket{u_{s}} = \ket{1} \cdots C \end{equation}G∣us⟩=exp⁡(2πisr)∣us⟩⋯D\begin{equation} G \ket{u_{s}} = \exp\left(\frac{2\pi i s}{r}\right) \ket{u_{s}} \cdots D \end{equation}

C の証明：

1r∑s=0r−1∣us⟩=1r∑s=0r−11r∑k=0r−1exp⁡(−2πiksr)∣gk mod L⟩=∑k=0r−1(1r∑s=0r−1exp⁡(−2πiksr))∣gk mod L⟩=∣1⟩\begin{align} \frac{1}{\sqrt{r}} \sum_{s=0}^{r-1} \ket{u_{s}} &= \frac{1}{\sqrt{r}} \sum_{s=0}^{r-1} \frac{1}{\sqrt{r}} \sum_{k=0}^{r-1} \exp\left(\frac{-2\pi i ks}{r}\right) \ket{g^k \bmod L} \nonumber\\ &= \sum_{k=0}^{r-1} \left( \frac{1}{r} \sum_{s=0}^{r-1} \exp\left(\frac{-2\pi i ks}{r}\right) \right) \ket{g^k \bmod L} \nonumber\\ &= \ket{1} \end{align}

※最後の等号は以下により成り立つ。

k=0k = 0 のとき

1r∑s=0r−1exp⁡(−2πiksr)=1r∑s=0r−11=1\frac{1}{r} \sum_{s=0}^{r-1} \exp\left(\frac{-2\pi i ks}{r}\right) = \frac{1}{r} \sum_{s=0}^{r-1} 1 = 1

k≠0k \neq 0 のとき

1r∑s=0r−1exp⁡(−2πiksr)=1r1−exp⁡(−2πikrr)1−exp⁡(−2πikr)=1r1−11−exp⁡(−2πikr)=0\frac{1}{r} \sum_{s=0}^{r-1} \exp\left(\frac{-2\pi i ks}{r}\right) = \frac{1}{r} \frac{1 - \exp\left(\frac{-2\pi i kr}{r}\right)}{1 - \exp\left(\frac{-2\pi i k}{r}\right)} = \frac{1}{r} \frac{1 - 1}{1 - \exp\left(\frac{-2\pi i k}{r}\right)} = 0

D の証明

G∣us⟩=1r∑k=0r−1exp⁡(−2πiksr)G∣gk mod L⟩=1r∑k=0r−1exp⁡(−2πiksr)∣gk+1 mod L⟩=exp⁡(2πisr)1r∑k=0r−1exp⁡(−2πi(k+1)sr)∣gk+1 mod L⟩=exp⁡(2πisr)1r∑k′=0r−1exp⁡(−2πik′sr)∣gk′ mod L⟩=exp⁡(2πisr)∣us⟩\begin{align} G \ket{u_{s}} &= \frac{1}{\sqrt{r}} \sum_{k=0}^{r-1} \exp\left(\frac{-2\pi i ks}{r}\right) G \ket{g^k \bmod L} \nonumber\\ &= \frac{1}{\sqrt{r}} \sum_{k=0}^{r-1} \exp\left(\frac{-2\pi i ks}{r}\right) \ket{g^{k+1} \bmod L} \nonumber\\ &= \exp\left(\frac{2\pi i s}{r}\right) \frac{1}{\sqrt{r}} \sum_{k=0}^{r-1} \exp\left(\frac{-2\pi i (k+1)s}{r}\right) \ket{g^{k+1} \bmod L} \nonumber\\ &= \exp\left(\frac{2\pi i s}{r}\right) \frac{1}{\sqrt{r}} \sum_{k'=0}^{r-1} \exp\left(\frac{-2\pi i k's}{r}\right) \ket{g^{k'} \bmod L} \nonumber\\ &= \exp\left(\frac{2\pi i s}{r}\right) \ket{u_{s}} \end{align}

準備ができました。 A, B, C, D を使って ∣C5⟩\ket{\mathrm{C5}} を変形します。

∣C5⟩=12m∑k=02m−1∣k⟩∣gk mod L⟩=12m∑k=02m−1∣k⟩Gk∣1⟩=12m∑k=02m−1∣k⟩Gk1r∑s=0r−1∣us⟩=12m∑k=02m−1∣k⟩exp⁡(2πiskr)1r∑s=0r−1∣us⟩=12m∑k=02m−1exp⁡(2πiskr)∣k⟩1r∑s=0r−1∣us⟩\begin{align} \ket{\mathrm{C5}} &= \frac{1}{\sqrt{2^m}} \sum_{k=0}^{2^m-1} \ket{k} \ket{g^k \bmod L} \nonumber\\ &= \frac{1}{\sqrt{2^m}} \sum_{k=0}^{2^m-1} \ket{k} G^{k} \ket{1} \nonumber\\ &= \frac{1}{\sqrt{2^m}} \sum_{k=0}^{2^m-1} \ket{k} G^{k} \frac{1}{\sqrt{r}} \sum_{s=0}^{r-1} \ket{u_{s}} \nonumber\\ &= \frac{1}{\sqrt{2^m}} \sum_{k=0}^{2^m-1} \ket{k} \exp\left(\frac{2\pi i s k}{r}\right) \frac{1}{\sqrt{r}} \sum_{s=0}^{r-1} \ket{u_{s}} \nonumber\\ &= \frac{1}{\sqrt{2^m}} \sum_{k=0}^{2^m-1} \exp\left(\frac{2\pi i s k}{r}\right) \ket{k} \frac{1}{\sqrt{r}} \sum_{s=0}^{r-1} \ket{u_{s}} \end{align}

少し厳密ではない説明になってしまいますが、1r∑s=0r−1∣us⟩\frac{1}{\sqrt{r}} \sum_{s=0}^{r-1} \ket{u_{s}}の部分を無視すると、

12m∑k=02m−1exp⁡(2πi(2ms/r)k2m)∣k⟩\begin{equation} \frac{1}{\sqrt{2^m}} \sum_{k=0}^{2^m-1} \exp\left(\frac{2\pi i (2^{m}s/r) k}{2^{m}}\right) \ket{k} \end{equation}

となっており、これに対し IQFT\mathrm{IQFT} を作用させて観測した値をλ\lambdaとすると、λ≈2msr\lambda \approx \frac{2^{m}s}{r} よって、λ2m≈sr\frac{\lambda}{2^{m}} \approx \frac{s}{r} ここで、rr だけでなく ss もわからない事に注意してください。 しかし、この情報だけでも rr の候補を絞ることができます。 例えば、 λ2m=34138192\frac{\lambda}{2^{m}} = \frac{3413}{8192} だったとします。 連分数展開により以下のように近似計算できます。

34138192=0+12+12+12+1170+14≈0+12+12+12+0=512\begin{align} \frac{3413}{8192} &= 0 + \cfrac{1}{2 + \cfrac{1}{2 + \cfrac{1}{2 + \cfrac{1}{170 + \frac{1}{4}}}}} \nonumber\\ &\approx 0 + \cfrac{1}{2 + \cfrac{1}{2 + \cfrac{1}{2 + 0}}} \nonumber\\ &= \frac{5}{12} \end{align}

こうして、r=12r = 12 と推定できます。

問題 D2

1515 を素因数分解せよ。

D2の解説

開く
  1. gg を 2≤g<L2 \leq g < L の範囲で適当に選ぶ。
  2. gg が LL の約数なら素因数分解成功なので終了。
  3. D1 の方法で gr=1 mod Lg^r = 1 \bmod L を満たす rr を求める。
  4. もし rr が奇数なら最初からやり直す。
  5. もし rr が偶数なら (gr/2+1)(gr/2−1)=0 mod L(g^{r/2}+1)(g^{r/2}-1) = 0 \bmod L である可能性が高い。
  6. gcd(gr/2+1,L)gcd(g^{r/2}+1, L) か gcd(gr/2−1,L)gcd(g^{r/2}-1, L) のどちらかが LL の約数の可能性が高い。素因数分解成功なら終了。
  7. 素因数分解失敗なら最初からやり直す。