A5: Minus Oracle

Problem Statement

Given an integer $n$, implement an $n$-qubit oracle $O$ on a quantum circuit $\mathrm{qc}$.

For any integer $k$ satisfying $0 \leq k < 2^n$, the required transformation is as follows:

Here, $- k \ \text{mod} \ 2^n$ denotes the unique integer $x$ such that $0 \leq x < 2^n$ and $k + x$ is divisible by $2^n$.

Constraints

• $1 \leq n \leq 10$
• The quantum circuit depth must not exceed $30$.
• Integers must be encoded by little-endian.
• Global phase is ignored in judge.
• The submitted code must follow the specified format:

from qiskit import QuantumCircuit
 
 
def solve(n: int) -> QuantumCircuit:
    qc = QuantumCircuit(n)
    # Write your code here:
 
    return qc

Hints