QCoder

解説

特定の計算基底状態の確率振幅を増幅する量子アルゴリズムとしてグローバーのアルゴリズムや振幅増幅 (Amplitude amplification) が知られています。これらのアルゴリズムの所望の計算基底状態の観測確率はイテレーション数に対する周期関数として表され、観測確率を $1.0$ に近い値まで増幅することはできますが、ちょうど $1.0$ にすることは一般にできません。

これに対し、fixed-point amplitude amplification と呼ばれるアルゴリズムは所望の計算基底状態の確率振幅をイテレーション数に対して単調に増加させることができます。すなわち、十分なイテレーション数に対して観測確率が $1.0$ に収束します。

よって、本問は fixed-point amplitude amplification によって解くことができます。

次に fixed-point amplitude amplification の概要を説明します。様々な手法が提案されていますが、ここでは、Grover の $\pi/3$ phase-shift 法を考えます。

はじめに、増幅前の初期状態を $\ket{s}$ ¹、増幅後の所望の状態を $\ket{t}$ と定義します。 $\pi/3$ phase-shift 法では何らかのユニタリ操作 $U$ ² に対し、次式で再帰的に定義される演算子 $U_m$ を初期状態 $\ket{s}$ に作用させることで振幅増幅を行います。

\begin{equation} U_{m+1} = U_m R_s U_m^{\dagger} R_t U_m, \ \ \ \ \ U_0 = U \end{equation}

ただし、 $(\cdot)^{\dagger}$ はエルミート転置を表し、選択的位相シフト演算子 $R_s,\ R_t$ は次式で定義されます。

\begin{align} R_s &= I - \left[1 - \exp\left(i\frac{\pi}{3}\right)\right]\ket{s}\bra{s}\\ R_t &= I - \left[1 - \exp\left(i\frac{\pi}{3}\right)\right]\ket{t}\bra{t} \end{align}

なお、オラクル $R_t$ には問題 B4 で実装したものを利用できます ³。

アルゴリズムの詳細や背景については解答例や文献 [1], [2], [3] を参照してください。

次に誤差解析を行います。

状態 $U\ket{s}$ から所望の計算基底状態のいづれかを観測する確率を $1 - \epsilon_0$ とすることで、初期誤差 $\epsilon_0$ を定義します。本問においては、 $U$ を「アダマールゲートをすべての量子ビットに作用させる操作 ( $H^{\otimes n}$ )」とすると、問題 C1 と同様に $\lceil\log_2(L)\rceil$ 番目までの量子ビットに $U_m$ を作用させることで、 $1 - \epsilon_0 > 0.5 \Rightarrow \epsilon_0 < 0.5$ が保証されます ⁴ 。

このとき、 $U_m\ket{s}$ と $\ket{t}$ の誤差は $\epsilon_0^{3^m}$ で表されます ⁵ 。

よって、誤差を $5.0 \times 10^{-3}$ 未満にするために必要な再帰深さ $m$ は次式を解くことで求めることができます。

\begin{equation} (0.5)^{3^m} < 5.0 \times 10^{-3} \end{equation}

$(4)$ 式の解は $m > 1.85$ と表されます。したがって、 $m = 2$ とすることで問題の制約内で十分に誤差を小さくできます。

解答例

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

from qiskit import QuantumCircuit
from qiskit.circuit.library import PhaseGate
import math
 
 
def Rt(n: int, L: int) -> QuantumCircuit:
    qc = QuantumCircuit(n)
 
    for i in range(n):
        if not (L >> i) & 1:
            continue
        for j in range(i + 1, n):
            if not (L >> j) & 1:
                qc.x(j)
        qc.x(i)
        if i == n - 1:
            qc.p(math.pi / 3, i)
        else:
            qc.append(PhaseGate(math.pi / 3).control(n - i - 1), range(i, n))
        qc.x(i)
        for j in range(i + 1, n):
            if not (L >> j) & 1:
                qc.x(j)
 
    return qc
 
 
def Rs(n: int) -> QuantumCircuit:
    qc = QuantumCircuit(n)
 
    qc.x(range(n))
 
    if n == 1:
        qc.p(math.pi / 3, 0)
    else:
        qc.append(PhaseGate(math.pi / 3).control(n - 1), range(n))
 
    qc.x(range(n))
 
    return qc
 
 
def U(m: int, n: int, L: int) -> QuantumCircuit:
    qc = QuantumCircuit(n)
 
    if m == 0:
        qc.h(range(n))
        return qc
 
    u = U(m - 1, n, L)
 
    qc.compose(u, inplace=True)
    qc.compose(Rt(n, L), inplace=True)
    qc.compose(u.inverse(), inplace=True)
    qc.compose(Rs(n), inplace=True)
    qc.compose(u, inplace=True)
 
    return qc
 
 
def solve(n: int, L: int) -> QuantumCircuit:
    qc = QuantumCircuit(n)
 
    k = math.ceil(math.log2(L))
    if k == 0:
        return qc
 
    m = 2
    qc.compose(U(m, k, L), inplace=True)
 
    return qc

References

本問においては、増幅前の初期状態 $\ket{s}$ はゼロ状態と考えられます。 ↩
状態 $U\ket{s}$ から所望の計算基底状態のいづれかを観測できる任意のユニタリ操作を $U$ として利用できます。詳しくは後述の誤差解析を参照してください。ここでは、 $U$ を「アダマールゲートをすべての量子ビットに作用させる操作 ( $H^{\otimes n}$ )」と解釈して問題ありません。 ↩
正確には B4 問題のオラクルは $(3)$ 式を満たさず、以下の条件を満たす演算子 $R_t$ として定義できます。
$(1) \ R_t U_0 \ket{s} = \left(I - \left[1 - \exp\left(i\frac{\pi}{3}\right)\right]\ket{t}\bra{t}\right) U_0 \ket{s}\\ (2) \ R_t \ket{t} = \left(I - \left[1 - \exp\left(i\frac{\pi}{3}\right)\right]\ket{t}\bra{t}\right) \ket{t}$
証明は省きますが、以上の定義の場合にも fixed-point amplitude amplification は動作することが示せます。
※ こちらの部分は PSL さんにご指摘いただきました。ありがとうございます。 ↩
$U$ をすべての量子ビットに作用させると、初期誤差 $\epsilon_0$ が増大し、より大きい再帰深さ $m$ が必要になります。テストケースによっては制約の回路の深さをクリアすることができません。 ↩
当初 $\epsilon_0^{3m}$ となっていましたが、 $\epsilon_0^{3^m}$ に修正しました。
※ こちらの部分は PSL さんにご指摘いただきました。ありがとうございます。 ↩

C2: Generate Uniform Amplitude Superposition State II

解説

解答例

References

Footnotes