B8: Grover's Algorithm II

問題文

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

ただし、 $\oplus$ は排他的論理和を表す。

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

より正確な問題文

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

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

制約

• $2 \leq n \leq 10$
• 量子回路の深さは $250$ を超えてはならない。
• オラクル $O$ は深さ $1$ の量子回路として与えられる。
• 整数はリトルエンディアンにしたがってエンコードすること (例：$\ket{100} = 1 \neq \ket{001}$)
• グローバル位相 は問わない。
• 提出されるコードは次のフォーマットにしたがうこと

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