Ex2: Find Hidden Number

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 we know that $L$ is one of the powers of $2$ $(2^0, 2^1, ... 2^{n-1})$. 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$ qubits that prepares a quantum state $\ket{\psi}$ from the zero state, such that $\ket{L}$ is observed with a probability of at least $0.9$ 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

• $2 \leq n \leq 10$
• The circuit depth must not exceed $75$.
• Oracle $O$ is given as a quantum circuit of depth $1$.
• 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