QCoder

解説

整数 $k$ を「 $2^x \geq L$ を満たす最小の整数 $x$ 」と定義し、 $k$ 番目までの量子ビットにアダマールゲートを適用することを考えます。

このとき、計算基底状態 $\ket{0},\ \ket{1},\ ...\ \ket{L-1}$ の複素振幅の絶対値 $|a_i|$ はすべて等しく、次式を満たします。

\begin{equation} |a_0| = |a_1| = \cdots = |a_{L-1}| = \frac{1}{\sqrt{2^k}} \end{equation}

ここで、 $2^{k-1} < L \leq 2^k$ より、観測確率の総和は次の不等式を満たします。

\begin{align} \sum_{i=0}^{L-1} |a_i|^2 &= L \times \left(\frac{1}{\sqrt{2^k}}\right)^2 \nonumber\\ &= \frac{L}{2^k} > \frac{2^{k-1}}{2^k} = 0.5\\ \end{align}

なお、「 $2^x \geq L$ を満たす最小の整数 $x$ 」は $\lceil\log_2(L)\rceil$ と表すことができます。( $\lceil(\cdot)\rceil$ は天井関数を表します。）

結果として、 $\lceil\log_2(L)\rceil$ 番目までの量子ビットにアダマールゲートを適用することでこの問題を解くことができます。

$L = 1$ の場合に生じる実装上のコーナーケースに注意して下さい。

解答例

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

from qiskit import QuantumCircuit
import math
 
 
def solve(n: int, L: int) -> QuantumCircuit:
    qc = QuantumCircuit(n)
 
    if L == 1:
        return qc
 
    k = math.ceil(math.log2(L))
    qc.h(range(k))
 
    return qc

補足

所望の状態の確率振幅を増幅する量子アルゴリズムはグローバーのアルゴリズムや振幅増幅 (Amplitude amplification) として知られています。本問をそのようなアルゴリズムを使って解くこともできます。

C1: Generate Uniform Amplitude Superposition State I

解説

解答例

補足