B6: Grover's Algorithm I

Problem Statement

You are given an integer $n$ and an oracle $O$. There exists an integer $L$ such that $0 \leq L \lt 2^n$, and the oracle $O$ satisfies

for any integer $x$ satisfying $0 \leq x \lt 2^n$.

Implement an operation on a quantum circuit $\mathrm{qc}$ with $n$ qubits that prepares a quantum state $\ket{\psi}$ from the zero state, such that $\ket{L}$ is observed with a probability of at least $4/2^n$ upon measurement.

More Precise Problem Statement

Define the state $\ket{\psi}$ prepared by $\mathrm{qc}$ as

where $a_i$ denotes the probability amplitude of the computational basis state $\ket{i}$.

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

Constraints

• $3 \leq n \leq 10$
• Integers must be encoded by little-endian notation, i.e., $\ket{100} = 1 \neq \ket{001}$.
• Global phase is ignored in judge.
• The submitted code must follow the specified format:

from qiskit import QuantumCircuit
 
"""
You can apply oracle as follows:
qc.compose(o, inplace=True)
"""
 
 
def solve(n: int, o: QuantumCircuit) -> QuantumCircuit:
    qc = QuantumCircuit(n)
    # Write your code here:
 
    return qc