B5: Quantum Arithmetic I

問題文

整数 $n,\ m,\ S_0,\ S_1,\ \cdots,\ S_{n-1}$ が入力として与えられる。

$0$ 以上 $2^n$ 未満の整数 $x = x_0 + 2^1 x_1 + \cdots 2^{n-1}x_{n-1}$ $\left(x_i \in \{0, 1\}\right)$ に対して、関数 $f(x)$ を次式で定義する。

$0$ 以上 $2^n$ 未満の任意の整数 $x$ に対して

を満たす $n$ 量子ビットオラクル $O$ を実装せよ。

制約

• $1 \leq n, m \leq 10$
• $0 \leq S_k < 2^m$
• 量子回路の 深さ は $10$ を超えてはならない。
• 整数は リトルエンディアン にしたがってエンコードすること (例：$\ket{100} = 1 \neq \ket{001}$)
• グローバル位相 の変化は問わない。
• 提出されるコードは次のフォーマットにしたがうこと

from qiskit import QuantumCircuit
 
 
def solve(n: int, m: int, S: list[int]) -> QuantumCircuit:
    qc = QuantumCircuit(n)
    # Write your code here:
 
    return qc

入力例

• $n=2,\ m = 2,\ S_0 = 1,\ S_1 = 3,\ \ket{x} = \ket{11} = \ket{3}$
  $f(3) = 1 \cdot 1 + 3 \cdot 1 = 4$ より、実装された量子回路 $\mathrm{qc}$ は次式を満たす。