LogoQCoder Programming Contest 003
ログイン
← 前の問題次の問題 →

B8: Grover's Algorithm II

実行時間制限：5 秒

メモリ制限：512 MiB

配点：300点

問題文

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

∣x⟩n∣y⟩1→O{∣x⟩n∣y⊕1⟩1(x=L)∣x⟩n∣y⟩1(x≠L)\ket{x}_n \ket{y}_1 \xrightarrow{O} \begin{cases} \ket{x}_n \ket{y\oplus 1}_1 & (x=L) \\ \ket{x}_n\ket{y}_1 & (x\neq L) \end{cases}

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

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

より正確な問題文

量子状態 ∣0⟩n+1\ket{0}_{n+1} に qc\mathrm{qc} を作用させた後の状態 ∣ψ⟩\ket{\psi} を、aia_i を計算基底状態 ∣i⟩n+1\ket{i}_{n+1} の複素振幅として次式で定義する。

∣ψ⟩=∑i=02n+1−1ai∣i⟩\ket{\psi} = \sum_{i=0}^{2^{n+1}-1} a_i\ket{i}

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

∣aL∣2≥0.9|a_L|^2 \geq 0.9

制約

  • 2≤n≤102 \leq n \leq 10
  • 量子回路の深さは 250250 を超えてはならない。
  • オラクル OO は深さ 11 の量子回路として与えられる。
  • 整数は リトルエンディアン にしたがってエンコードすること
  • グローバル位相 は問わない。
  • 提出されるコードは次のフォーマットにしたがうこと
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

解答を提出するにはログインしてください。

ログイン