LogoQCoder Programming Contest 003
ログイン
← 前の解説次の解説 →

B8: Grover's Algorithm II

実行時間制限：5 秒

メモリ制限：512 MiB

配点：300点

Writer：Not_Leonian

解説

この問題も 問題B6 と同様に特定の計算基底状態の確率振幅を増幅する問題であり、グローバーのアルゴリズムの使用を想定しています。

ここで、Grover iteration を rr 回行った後に増幅対象の計算基底状態を観測される確率 P(r)P(r) は次式で表されます。

P(r)=sin⁡2((r+12)θ)\begin{equation} P(r) = \sin^2\left(\left(r + \frac{1}{2}\right)\theta\right) \end{equation}

ただし、θ=2arcsin⁡(1/2n)\theta = 2\arcsin(1/\sqrt{2^n})とします。

P(r)=1P(r)=1 を満たす実数 rr のうち正で最小のもの rminr_{\mathrm{min}} は、以下のように表せます。

rmin=π2θ−12\begin{equation} r_{\mathrm{min}}=\frac{\pi}{2\theta}-\frac{1}{2} \end{equation}

実際にはイテレーション回数は整数である必要がありますが、この問題の制約の範囲内では整数に丸めた rminr_{\mathrm{min}} で操作後に ∣aL∣2≥0.9|a_L|^2\geq 0.9 を満たすことが確認できます。

また、 n=10n=10 の場合は rmin∼25r_{\mathrm{min}} \sim 25 であり、Grover iterationの回路は深さ 88 以内で実装できるため、量子回路の深さは 250250 以下に抑えることができます。

(1)式の証明

量子状態 ∣ψ′⟩\ket{\psi'} を以下のように定義します。

∣ψ′⟩=12n−1(∑i=02n−1∣i⟩−∣L⟩)\begin{equation} \ket{\psi'} = \frac{1}{\sqrt{2^n-1}} \left(\sum_{i=0}^{2^n-1}\ket{i} - \ket{L}\right) \end{equation}

∣ψ⟩\ket{\psi} は ∣L⟩\ket{L} と ∣ψ′⟩\ket{\psi'} を用いて、以下のように表せます。

∣ψ⟩=12n∣L⟩+2n−12n∣ψ′⟩\begin{equation} \ket{\psi} = \frac{1}{\sqrt{2^n}} \ket{L} + \frac{\sqrt{2^n-1}}{\sqrt{2^n}} \ket{\psi'} \end{equation}

そして、

sin⁡θ2=12n\begin{equation} \sin \frac{\theta}{2} = \frac{1}{\sqrt{2^n}} \end{equation}

を満たす θ\theta を考えると、∣ψ⟩\ket{\psi} は以下のように書き換えられます。

∣ψ⟩=sin⁡θ2∣L⟩+cos⁡θ2∣ψ′⟩\begin{equation} \ket{\psi}=\sin\frac{\theta}{2}\ket{L}+\cos\frac{\theta}{2}\ket{\psi'} \end{equation}

ここで、 rr を非負整数とし、以下の量子状態にGrover iterationを行った後の量子状態を計算します。

sin⁡((r+12)θ)∣L⟩+cos⁡((r+12)θ)∣ψ′⟩\begin{equation} \sin\left(\left(r+\frac{1}{2}\right)\theta\right)\ket{L}+\cos\left(\left(r+\frac{1}{2}\right)\theta\right)\ket{\psi'} \end{equation}

まず、∣ψ⟩\ket{\psi}, ∣ψ′⟩\ket{\psi'}, ∣L⟩\ket{L}の内積では、

⟨ψ∣L⟩=⟨L∣ψ⟩=1/2n, ⟨ψ′∣ψ⟩=⟨ψ∣ψ′⟩=2n−1/2n, ⟨ψ′∣L⟩=⟨L∣ψ′⟩=0\braket{\psi|L}=\braket{L|\psi}=1/\sqrt{2^n},\ \braket{\psi'|\psi}=\braket{\psi|\psi'}=\sqrt{2^n-1}/\sqrt{2^n},\ \braket{\psi'|L}=\braket{L|\psi'}=0

が成立し、計算基底状態 ∣L⟩\ket{L} のみの符号を反転させるオラクルを OO とおいたとき、 O=I−2∣L⟩⟨L∣O = I - 2\ket{L}\bra{L} と表せることから、オラクル OO を(7)(7)式の量子状態に作用させると、以下のようになります。 ただし、r+1/2r + 1 / 2 を r+12r_{+ \frac{1}{2}} とします。

O(sin⁡(r+12θ)∣L⟩+cos⁡(r+12θ)∣ψ′⟩)=(I−2∣L⟩⟨L∣)(sin⁡(r+12θ)∣L⟩+cos⁡(r+12θ)∣ψ′⟩)=sin⁡(r+12θ)∣L⟩+cos⁡(r+12θ)∣ψ′⟩−2sin⁡(r+12θ)∣L⟩⟨L∣L⟩−2cos⁡(r+12θ)∣L⟩⟨L∣ψ′⟩=sin⁡(r+12θ)∣L⟩+cos⁡(r+12θ)∣ψ′⟩−2sin⁡(r+12θ)∣L⟩=−sin⁡(r+12θ)∣L⟩+cos⁡(r+12θ)∣ψ′⟩\begin{align} &O \left(\sin\left(r_{+ \frac{1}{2}} \theta\right) \ket{L} + \cos\left(r_{+ \frac{1}{2}} \theta\right) \ket{\psi'}\right) \nonumber \\ &= (I - 2\ket{L}\bra{L}) \left(\sin\left(r_{+ \frac{1}{2}} \theta\right) \ket{L} + \cos\left(r_{+ \frac{1}{2}} \theta\right) \ket{\psi'}\right) \\ &= \sin \left(r_{+ \frac{1}{2}} \theta\right) \ket{L} + \cos\left(r_{+ \frac{1}{2}} \theta\right) \ket{\psi'} - 2\sin\left(r_{+ \frac{1}{2}} \theta\right) \ket{L} \braket{L|L} - 2\cos\left(r_{+ \frac{1}{2}} \theta\right) \ket{L} \braket{L|\psi'} \\ &= \sin \left(r_{+ \frac{1}{2}} \theta\right) \ket{L} + \cos\left(r_{+ \frac{1}{2}} \theta\right) \ket{\psi'} - 2\sin\left(r_{+ \frac{1}{2}} \theta\right) \ket{L} \\ &= - \sin\left(r_{+ \frac{1}{2}} \theta\right) \ket{L} + \cos\left(r_{+ \frac{1}{2}} \theta\right)\ket{\psi'} \end{align}

次に、演算子 2∣ψ⟩⟨ψ∣−I2\ket{\psi}\bra{\psi} - I で表される操作を適用すると、以下のようになります。

(2∣ψ⟩⟨ψ∣−I)(−sin⁡(r+12θ)∣L⟩+cos⁡(r+12θ)∣ψ′⟩)=−2sin⁡(r+12θ)∣ψ⟩⟨ψ∣L⟩+2cos⁡(r+12θ)∣ψ⟩⟨ψ∣ψ′⟩+sin⁡(r+12θ)∣L⟩−cos⁡(r+12θ)∣ψ′⟩=−22nsin⁡(r+12θ)∣ψ⟩+22n−12ncos⁡(r+12θ)∣ψ⟩+sin⁡(r+12θ)∣L⟩−cos⁡(r+12θ)∣ψ′⟩=−2sin⁡θ2sin⁡(r+12θ)∣ψ⟩+2cos⁡θ2cos⁡(r+12θ)∣ψ⟩+sin⁡(r+12θ)∣L⟩−cos⁡(r+12θ)∣ψ′⟩=−2sin⁡2θ2sin⁡(r+12θ)∣L⟩−2sin⁡θ2cos⁡θ2sin⁡(r+12θ)∣ψ′⟩+2sin⁡θ2cos⁡θ2cos⁡(r+12θ)∣L⟩+2cos⁡2θ2cos⁡(r+12θ)∣ψ′⟩+sin⁡(r+12θ)∣L⟩−cos⁡(r+12θ)∣ψ′⟩=((1−2sin⁡2θ2)sin⁡(r+12θ)+2sin⁡θ2cos⁡θ2cos⁡(r+12θ))∣L⟩+((2cos⁡2 θ2−1)cos⁡(r+12θ)−2sin⁡θ2cos⁡θ2sin⁡(r+12θ))∣ψ′⟩=(sin⁡(r+12θ)cos⁡θ+cos⁡(r+12θ)sin⁡θ)∣L⟩+(cos⁡(r+12θ)cos⁡θ−sin⁡(r+12θ)sin⁡θ)∣ψ′⟩=sin⁡((r+12+1)θ)∣L⟩+cos⁡((r+12+1)θ)∣ψ′⟩\begin{align} & (2 \ket{\psi}\bra{\psi} - I) \left(- \sin \left(r_{+ \frac{1}{2}} \theta\right) \ket{L} + \cos \left(r_{+ \frac{1}{2}} \theta\right) \ket{\psi'} \right) \nonumber \\ &= -2 \sin \left(r_{+ \frac{1}{2}} \theta\right) \ket{\psi} \braket{\psi|L} + 2\cos \left(r_{+ \frac{1}{2}} \theta\right) \ket{\psi} \braket{\psi|\psi'} + \sin \left(r_{+ \frac{1}{2}} \theta\right) \ket{L} - \cos (r_{+ \frac{1}{2}} \theta )\ket{\psi'} \\ &= - \frac{2}{\sqrt{2^n}} \sin \left(r_{+ \frac{1}{2}} \theta\right) \ket{\psi} + \frac{2\sqrt{2^n-1}} {\sqrt{2^n}} \cos \left(r_{+ \frac{1}{2}} \theta\right) \ket{\psi} + \sin \left(r_{+ \frac{1}{2}} \theta\right) \ket{L} - \cos\left(r_{+ \frac{1}{2}} \theta\right) \ket{\psi'} \\ &= - 2 \sin \frac{\theta}{2} \sin \left(r_{+ \frac{1}{2}} \theta\right) \ket{\psi} + 2 \cos\frac{\theta}{2} \cos\left(r_{+ \frac{1}{2}} \theta\right) \ket{\psi} + \sin\left(r_{+ \frac{1}{2}} \theta\right) \ket{L} - \cos\left(r_{+ \frac{1}{2}} \theta\right)\ket{\psi'} \\ &= - 2 \sin^2 \frac{\theta}{2} \sin \left(r_{+ \frac{1}{2}} \theta\right) \ket{L} - 2\sin \frac{\theta}{2} \cos \frac{\theta}{2} \sin\left(r_{+ \frac{1}{2}} \theta\right) \ket{\psi'} \\ & \qquad \qquad + 2\sin\frac{\theta}{2} \cos \frac{\theta}{2} \cos\left(r_{+ \frac{1}{2}} \theta\right) \ket{L} + 2\cos^2 \frac{\theta}{2} \cos\left(r_{+ \frac{1}{2}} \theta\right) \ket{\psi'} + \sin\left(r_{+ \frac{1}{2}} \theta\right) \ket{L} - \cos\left(r_{+ \frac{1}{2}} \theta\right) \ket{\psi'} \nonumber \\ &= \left(\left(1 - 2 \sin^2 \frac{\theta}{2}\right) \sin\left(r_{+ \frac{1}{2}} \theta\right) + 2 \sin \frac{\theta}{2} \cos \frac{\theta}{2} \cos\left(r_{+ \frac{1}{2}} \theta\right)\right) \ket{L} \\ & \qquad \qquad + \left(\left(2 \cos^2\ \frac{\theta}{2} - 1\right) \cos\left(r_{+ \frac{1}{2}} \theta\right) - 2 \sin \frac{\theta}{2} \cos \frac{\theta}{2} \sin\left(r_{+ \frac{1}{2}} \theta\right)\right) \ket{\psi'} \nonumber \\ &= \left(\sin\left(r_{+ \frac{1}{2}} \theta\right) \cos \theta + \cos\left(r_{+ \frac{1}{2}} \theta\right) \sin \theta\right) \ket{L} + \left(\cos\left(r_{+ \frac{1}{2}} \theta\right) \cos \theta - \sin\left(r_{+ \frac{1}{2}} \theta\right) \sin \theta\right) \ket{\psi'} \\ &= \sin\left(\left(r_{+ \frac{1}{2}} + 1\right) \theta\right) \ket{L} + \cos \left(\left(r_{+ \frac{1}{2}} + 1\right) \theta\right) \ket{\psi'} \end{align}

よって、(6)(6)式の∣ψ⟩\ket{\psi} に対してGrover iterationを rr 回行った後の量子状態は以下のようになることがわかります。

∣ψ⟩=sin⁡((r+12)θ)∣L⟩+cos⁡((r+12)θ)∣ψ′⟩\begin{equation} \ket{\psi} = \sin\left(\left(r + \frac{1}{2}\right) \theta\right) \ket{L} + \cos \left(\left(r + \frac{1}{2}\right) \theta\right) \ket{\psi'} \end{equation}

n=2n = 2 の場合の回路図は、以下の通りです。回路図内のReflect_B4は、B4の回路を示しています。

なお、以上の考察は以下のように幾何学的に考えることができます。 図では、 Uψ=2∣ψ⟩⟨ψ∣−IU_{\psi} = 2 \ket{\psi}\bra{\psi} - I とおいています。 ∣ψ′⟩\ket{\psi'} と ∣L⟩\ket{L} が張る 22 次元空間において、 OO はベクトルを ∣ψ′⟩\ket{\psi'} に対して対称なベクトルへ移す変換であり、 UψU_{\psi} はベクトルを ∣ψ⟩\ket{\psi} に対して対称なベクトルへ移す変換です。

Wstate_log

解答例

解答例は以下の通りです。

import math
 
from qiskit import QuantumCircuit, QuantumRegister
from qiskit.circuit.library import ZGate
 
 
def compose_oracle(qc: QuantumCircuit, y: QuantumRegister, o: QuantumCircuit) -> QuantumCircuit:
    qc.x(y)
    qc.h(y)
    qc.compose(o, inplace=True)
    qc.h(y)
    qc.x(y)
 
    return qc
 
 
def reflect(n: int) -> QuantumCircuit:
    qc = QuantumCircuit(n)
 
    qc.x(range(n))
    qc.append(ZGate().control(n - 1), range(n))
    qc.x(range(n))
 
    return qc
 
 
def solve(n: int, o: QuantumCircuit) -> QuantumCircuit:
    x, y = QuantumRegister(n), QuantumRegister(1)
    qc = QuantumCircuit(x, y)
 
    theta = math.asin(1 / math.sqrt(2**n)) * 2
    rotation_count = int(round(math.pi / 2 / theta - 1 / 2))
 
    qc.h(range(n))
 
    for _ in range(rotation_count):
        compose_oracle(qc, y, o)
        qc.h(range(n))
        qc.compose(reflect(n), inplace=True)
        qc.h(range(n))
 
    return qc