B8: Grover's Algorithm II

Problem Statement

You are given an integer $n$ and an oracle $O$. There exists an integer $L$ in the range from $0$ (inclusive) to $2^n$ (exclusive), and the oracle $O$ satisfies

for any pair of integers $(x,y)$ satisfying $0\leq x\lt 2^n$ and $0\leq y\lt 2$, where $\oplus$ denotes the XOR operator.

Implement an operation on a quantum circuit $\mathrm{qc}$ with $n+1$ qubits that prepares a quantum state $\ket{\psi}$ from the zero state $\ket{0}$, such that $\ket{L}_n\ket{0}_1$ is observed with a probability of at least $0.9$ upon measurement.

More Precise Problem Statement

Define the state $\ket{\psi}$ prepared by applying $\mathrm{qc}$ to $\ket{0}_{n+1}$ as

where $a_i$ denotes the complex amplitude of the computational basis state $\ket{i}_{n+1}$.

Implement $\mathrm{qc}$ satisfying following condition:

Constraints

• $2 \leq n \leq 10$
• The quantum circuit depth must not exceed $250$.
• Oracle $O$ is given as a quantum circuit of depth $1$.
• 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, QuantumRegister
 
"""
You can apply oracle as follows:
qc.compose(o, inplace=True)
"""
 
 
def solve(n: int, o: QuantumCircuit) -> QuantumCircuit:
    x, y = QuantumRegister(n), QuantumRegister(1)
    qc = QuantumCircuit(x, y)
    # Write your code here:
 
    return qc