QCoder

解説

解法(1): グローバーのアルゴリズムと $\pi/3$ phase shift 法を組み合わせる

QPC001 C2 問題と同様に、今回のような任意の量子状態の準備には固定点振幅増幅 (fixed-point amplitude amplification) と呼ばれる量子アルゴリズムを利用できます。

固定点振幅増幅の一種であるグローバーの $\pi/3$ phase shift 法は「所望の計算基底状態の確率振幅をイテレーション数に対して単調に増加させる」という理想的な性質をもちますが、同じく振幅増幅を行うグローバーのアルゴリズムと比較して問合せ計算量¹の観点で非効率（古典計算と同等）であることが知られています。 $\pi/3$ phase shift 法の詳細については、QPC001 C2 問題の解説を参照してください。

今回の問題では、グローバーのアルゴリズムと $\pi/3$ phase shift 法をうまく組み合わせることで、効率的に状態 $\ket{\omega}$ を生成できます。

以下、実数 $P$ の値で場合分けして考えます。

$P > 0.06$ の場合（ $\pi/3$ phase shift 法のみを使う）

$\pi/3$ phase shift 法を $m$ 回再帰することを考えます。

このとき、誤り確率の最大値 ( $(1 - 0.06)^{3^m}$ ) と必要な $R(\cdot)$ ゲートの数は次のように整理されます。


$m$	0	1	2	3	4
$R(\pi/3)$ の数	0	1	4	13	40
誤り確率の最大値	0.94	0.83	0.57	0.19	0.0067

よって、 $4$ 回再帰すれば誤差を十分に小さくできます。

$P \leq 0.06$ の場合は必要な $R(\cdot)$ ゲートの数が $121$ 回となり、制約を満たしません。

$0.02 \leq P \leq 0.06$ の場合（グローバーのアルゴリズムと $\pi/3$ phase shift 法を組み合わせる）

グローバーのアルゴリズムを使うことを考えます。以下、 $\ket{S}$ , $R_S(\theta)$ , $R_\omega(\theta)$ を次のように定義します。

\begin{align} \ket{S} &:= U\ket{0}\\ R_S(\theta) &:= U(I - \left(1 - e^{i\theta})\ket{0}\bra{0}\right)U^{\dagger} = I - (1-e^{i\theta}\ket{S}\bra{S})\\ R_\omega(\theta) &:= I - (1 - e^{i\theta})\ket{\omega}\bra{\omega} \end{align}

$\left|\braket{\omega \mid S}\right|^2 = \sin^2(\theta/2)$ とし、 $\ket{S'} = (\ket{S} - \sin^2(\theta/2)\ket{\omega})/\cos(\theta/2)$ とおくと、以下が成り立ちます。

\begin{align} \ket{S} &= \sin(\theta/2)\ket{\omega} + \cos(\theta/2)\ket{S'}\\ \braket{\omega \mid S'} &= 0\\ \braket{S' \mid S'} &= 1 \end{align}

また、グローバーの振幅増幅を $m$ 回行ったベクトルを $\ket{S_m}$ とすると、以下が成り立ちます。

\begin{align} \ket{S_0} &= \ket{S} = \sin(\theta/2)\ket{\omega} + \cos(\theta/2)\ket{S'}\\ \ket{S_m} &= -R_S(\pi)R_\omega(\pi)\ket{S_{m-1}} \end{align}

これを解くと、 $\ket{S_m}$ は次のように表されます。

\begin{equation} \ket{S_m} = \sin\left(\left(m + \frac{1}{2}\right)\theta\right) \ket{\omega} + \cos\left(m + \frac{1}{2}\right)\ket{S'} \end{equation}

よって、 $\left|\braket{\omega \mid S_m}\right|^2 = \sin^2((m + 1/2)\theta) \fallingdotseq \sin^2(m\theta)$ が成り立ちます。

ここで、 $P$ は十分に小さいので、 $P \leq \sin^2(\theta/2) \leq 4P$ より、次の不等式が近似的に成り立ちます。

\begin{equation} 2\sqrt{P} \leq \theta \leq 2\sqrt{4P} \end{equation}

以上をもとに $m = \pi/(4\sqrt{4P})$ としてグローバーのアルゴリズムを適用します。

\begin{align} \sin^2(m\cdot2\sqrt{P}) \leq \sin^2(m\theta) \leq \sin^2(m \cdot 2\sqrt{4P})\\ \sin^2\left(\frac{\pi}{4}\right) = 0.5 \leq \left|\braket{\omega \mid S_m}\right|^2 \leq 1 = \sin^2\left(\frac{\pi}{2}\right) \end{align}

また、 $\pi/(4\sqrt{4P}) \leq 9$ より、 $9$ 回以下の振幅増幅をすることで誤り確率を $0.5$ 以下にできます。

最後に、 $\ket{S_m} = G\ket{0}$ , $U_0 = G$ として再帰的に $\pi/3$ phase shift 法を適用します。

このとき、誤り確率の最大値 ( $(1 - 0.5)^{3^m}$ ) と必要な $R(\cdot)$ ゲートの数は次のように整理されます。


$m$	0	1	2
$R(\pi)$ , $R(\pi/3)$ の数	9	28	85
誤り確率の最大値	0.5	0.125	0.002

よって、 $R(\cdot)$ ゲートの適用回数は $85$ 回以下で正答できます。

解答例

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

import math
 
from qiskit import QuantumCircuit
 
MAX_R_COUNT = 100
 
 
def R_0(n: int, theta: float) -> QuantumCircuit:
    qc = QuantumCircuit(n)
 
    qc.x(range(n))
 
    if n == 1:
        qc.p(theta, 0)
    else:
        qc.mcp(theta, list(range(n - 1)), n - 1)
 
    qc.x(range(n))
 
    return qc
 
 
def Grover(n: int, P: float, U, R) -> QuantumCircuit:
    qc = QuantumCircuit(n)
    cnt = int(math.pi / (4 * (4 * P) ** 0.5))
 
    qc.compose(U(), inplace=True)
 
    for _ in range(cnt):
        qc.compose(R(math.pi), inplace=True)
        qc.compose(U().inverse(), inplace=True)
        qc.compose(R_0(n, math.pi), inplace=True)
        qc.compose(U(), inplace=True)
 
    return qc, cnt
 
 
def PhaseShift(n: int, U_s, R) -> QuantumCircuit:
    qc = QuantumCircuit(n)
 
    qc.compose(U_s, inplace=True)
    qc.compose(R(math.pi / 3), inplace=True)
    qc.compose(U_s.inverse(), inplace=True)
    qc.compose(R_0(n, math.pi / 3), inplace=True)
    qc.compose(U_s, inplace=True)
 
    return qc
 
 
def solve(n: int, P: float, U, R) -> QuantumCircuit:
    U_s, cnt_R = Grover(n, P, U, R)
    while 3 * cnt_R + 1 <= MAX_R_COUNT:
        U_s = PhaseShift(n, U_s, R)
        cnt_R = 3 * cnt_R + 1
 
    return U_s

解法(2): Fixed-point quantum search with an optimal number of queries [1]

解法(1) で述べたように、グローバーの $\pi/3$ phase shift 法はグローバーのアルゴリズムと比較して問合せ計算量の観点で非効率であるため、単に $\pi/3$ phase shift 法を適用するだけではこの問題は解けません。しかし、2014年にグローバーのアルゴリズムと同等の効率性を持ちながら、固定点振幅増幅を実現するアルゴリズムが提案されています [1]。

よって、このアルゴリズムを適用することでこの問題を解くことができます。

必要な $R(\cdot)$ ゲートの適用回数は $11$ 回以下になり、 $\pi/3$ phase shift 法で必要な $121$ 回の平方根に抑えることができます。

詳細は Writer 解説 (pdf) を参照して下さい。

解答例

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

import math
 
from qiskit import QuantumCircuit
from scipy.special import eval_chebyt
 
 
def R_0(n: int, theta: float) -> QuantumCircuit:
    qc = QuantumCircuit(n)
 
    qc.x(range(n))
 
    if n == 1:
        qc.p(theta, 0)
    else:
        qc.mcp(theta, list(range(n - 1)), n - 1)
 
    qc.x(range(n))
 
    return qc
 
 
# Calculate the minimum number of query L
def calculate_L(delta: float, lambda_: float) -> int:
    L = int(math.ceil(math.log(2 / delta) / math.sqrt(lambda_)))
 
    # Check if L is odd
    if L % 2 == 0:
        L += 1
 
    return L
 
 
def calculate_gamma(L: int, delta: float) -> float:
    # Calculate the Chebyshev polynomial T_{1/L}(1/δ)
    chebyshev_value = eval_chebyt(1 / L, 1 / delta)
 
    # γ is the inverse of the Chebyshev value
    return 1 / chebyshev_value
 
 
# Define the fixed-point Grover's algorithm
def fixed_point_grover(n: int, delta: float, lambda_: float, U, R) -> QuantumCircuit:
    L = calculate_L(delta, lambda_)
 
    # Calculate the angles for Grover's iteration
    gamma = calculate_gamma(L, delta)
    angles = [
        -2 * math.atan(1 / (math.tan(2 * math.pi * j / L) * math.sqrt(1 - gamma**2)))
        for j in range(1, L // 2 + 1)
    ]
 
    qc = QuantumCircuit(n)
    qc.compose(U(), inplace=True)
    for alpha, beta in zip(angles, reversed(angles)):
        qc.compose(R(beta), inplace=True)
        qc.compose(U().inverse(), inplace=True)
        qc.compose(R_0(n, alpha), inplace=True)
        qc.compose(U(), inplace=True)
 
    return qc
 
 
def solve(n: int, P: float, U, R) -> QuantumCircuit:
    delta = 0.01
    lambda_ = P
    return fixed_point_grover(n, delta, lambda_, U, R)

References

[1] T. J. Yoder, G. H. Low, and I. L. Chuang, “Fixed-point quantum search with an optimal number of queries,” Physical Review Letters, vol. 113, no. 21, p. 210501, 2014.

今回の問題では問合せ計算量は $R(\cdot)$ の作用回数を指します。 ↩

Ex: Can you prepare ∣ω⟩?\ket{\omega}?∣ω⟩?

解説

解法(1): グローバーのアルゴリズムと π/3\pi/3π/3 phase shift 法を組み合わせる

P>0.06P > 0.06P>0.06 の場合（π/3\pi/3π/3 phase shift 法のみを使う）

0.02≤P≤0.060.02 \leq P \leq 0.060.02≤P≤0.06 の場合（グローバーのアルゴリズムと π/3\pi/3π/3 phase shift 法を組み合わせる）

解答例

解法(2): Fixed-point quantum search with an optimal number of queries [1]

解答例

References

Footnotes

Ex: Can you prepare $\ket{\omega}?$

解法(1): グローバーのアルゴリズムと $\pi/3$ phase shift 法を組み合わせる

$P > 0.06$ の場合（ $\pi/3$ phase shift 法のみを使う）

$0.02 \leq P \leq 0.06$ の場合（グローバーのアルゴリズムと $\pi/3$ phase shift 法を組み合わせる）