B6: Grover's Algorithm I

問題文

整数 $n$ と オラクル $O$ が入力として与えられる。 $0$ 以上 $2^n$ 未満のある整数 $L$ が存在し、オラクル $O$ は $0 \leq x \lt 2^n$ を満たす任意の整数 $x$ に対して、次式を満たす。

量子状態 $\ket{0}$ から、測定時に $4/2^n$ 以上の確率で $\ket{L}$ が観測されるような状態 $\ket{\psi}$ を作り出す操作を、 $n$ 量子ビットをもつ量子回路 $\mathrm{qc}$ 上に実装せよ。

より正確な問題文

量子状態 $\ket{0}$ に $\mathrm{qc}$ を作用させた後の状態 $\ket{\psi}$ を、 $a_i$ を状態 $\ket{i}$ の複素振幅として次式で定義する。

このとき、次式の条件を満たすような $\mathrm{qc}$ を構築せよ。

制約

• $3 \leq n \leq 10$
• 整数はリトルエンディアンにしたがってエンコードすること (例：$\ket{100} = 1 \neq \ket{001}$)
• グローバル位相 は問わない。
• 提出されるコードは次のフォーマットにしたがうこと

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