B5: Quantum Arithmetic I

Problem Statement

You are given integers $n,\ m,\ S_0,\ S_1,\ \cdots,\ S_{n-1}$.

For an integer $x = x_0 + 2^1 x_1 + \cdots 2^{n-1}x_{n-1}$ $\left(x_i \in \{0, 1\}\right)$ where $0 \leq x < 2^n$, define the function $f(x)$ by

Implement the $n$-qubit oracle $O$ acting on computational basis states as

for any integer $x$ such that $0 \leq x < 2^n$.

Constraints

• $1 \leq n, m \leq 10$
• $0 \leq S_k < 2^m$
• The circuit depth must not exceed $10$.
• Integers are encoded by little-endian notation, i.e., $\ket{100} = 1 \neq \ket{001}$.
• Changes in the global phase are ignored.
  
• The submitted code must follow the specified format:

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

Sample Input

• $n=2,\ m = 2,\ S_0 = 1,\ S_1 = 3,\ \ket{x} = \ket{11} = \ket{3}$
  Since $f(3) = 1 \cdot 1 + 3 \cdot 1 = 4$, the implemented quantum circuit $\mathrm{qc}$ should perform the following transformation.