B5: Quantum Arithmetic I

Time Limit: 3 sec

Memory Limit: 512 MiB

Score: 200

Problem Statement

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

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

f(x)=S0x0+S1x1++Sn1xn1.\begin{equation} f(x) = S_0 x_0 + S_1 x_1 + \cdots + S_{n-1}x_{n-1} \nonumber \end{equation}.

Implement the nn-qubit oracle OO acting on computational basis states as

xnOexp(2πif(x)2m)xn\begin{equation} \ket{x}_n \xrightarrow{O} \exp{\left(\frac{2\pi i f(x)}{2^m}\right)}\ket{x}_n \nonumber \end{equation}

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

Constraints

  • 1n,m101 \leq n, m \leq 10
  • 0Sk<2m0 \leq S_k < 2^m
  • The circuit depth must not exceed 1010.
  • Integers are encoded by little-endian notation, i.e., 100=1001\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, S0=1, S1=3, x=11=3n=2,\ m = 2,\ S_0 = 1,\ S_1 = 3,\ \ket{x} = \ket{11} = \ket{3}
    Since f(3)=11+31=4f(3) = 1 \cdot 1 + 3 \cdot 1 = 4, the implemented quantum circuit qc\mathrm{qc} should perform the following transformation.
11qcexp(24πi22)11\ket{11} \xrightarrow{\mathrm{qc}} \exp{\left(\frac{2 \cdot 4\pi i}{2^2}\right)}\ket{11}

Please sign in to submit your answer.