QCoder

解説

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

\begin{equation} k = k_0 + 2k_1 + \cdots + 2^{n-1}k_{n} \quad (k_0, k_1, \ldots, k_n \in \{0, 1\}) \end{equation}

このとき、問題の「 $s \leq k < 2^n$ 」は「 $s \leq k$ かつ $k_n = 0$ 」、「 $2^n \leq k < t$ 」は「 $k_n = 1$ かつ $k < t$ 」と言い換える事ができます。

よって、 $\ket{k_n}_1$ を制御ビットとして B3 の操作を2回行うことでこの問題を解くことができます。

\begin{equation} \ket{k}_{n} \xrightarrow{O} \ket{k - s}_{n} \quad (\ket{k_n} = \ket{1}) \end{equation}

\begin{equation} \ket{k}_{n} \xrightarrow{O} \ket{k + 2^{n+1} - t}_{n} \quad (\ket{k_n} = \ket{0}) \end{equation}

$k < s$ もしくは $k \geq t$ を満たす計算基底状態 $\ket{k}$ については問題で規定していないため、どのような遷移をしても構いません。

解答例

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

import math
 
from qiskit import QuantumCircuit
 
 
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
 
 
# B2
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
 
 
# B3
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 solve(n: int, s: int, t: int) -> QuantumCircuit:
    qc = QuantumCircuit(n + 1)
 
    # when k_{n-1} = 1
    qc.compose(cadd(n, 2 ** (n + 1) - t), qubits=range(n + 1), inplace=True)
 
    # when k_{n-1} = 0
    qc.x(n)
    qc.compose(cadd(n, -s), qubits=range(n + 1), inplace=True)
    qc.x(n)
 
    return qc

B4: Left and Right Aligned

解説

解答例