本題

Qiskit のグローバーのアルゴリズムの振幅増幅の説明に、以下のような記述があります。

解がひとつのとき、反復回数は $\sqrt{N}$ 回でいいとあります。この反復回数を増やせば増やすほど解 | $w$ > の確率振幅は大きくなりそうな説明ですが、実際はそうはなりません。

計算で確認する

量子ビット数N=4で、解が | $w$ > の場合を考えます。

以下では複数回の振幅増幅をしてみて、

平均値 mu
| $w$ >の振幅 w_amp
その他の1つの状態の振幅 other_amp
| $w$ >の測定確率 P(w)
その他の1つの状態の測定確率 P(other)

をそれぞれ計算するコードとその結果を示します。

# coding: utf-8

"""1回反復したときの「|w> の振幅」と「それ以外の振幅」を計算して返す"""
def calc_amplitude(n, w_amp, other_amp):
    # |w>の符号を反転させる
    w_amp = -w_amp

    # 振幅の平均を求める
    mu = (other_amp*(2**n-1) + w_amp) / (2**n)
    print("mu: {}".format(mu))

    # 平均周りで振幅を反転させる
    w_amp = mu + (mu - w_amp)
    other_amp = mu + (mu - other_amp)

    return w_amp, other_amp

# 量子ビットの数 n=4 のとき、すべての振幅の初期値は 1/4
n = 4
w_amp = other_amp = 1/4

# 複数回反復する
for t in range(10):
    print("{}回目の振幅増幅".format(t+1))
    w_amp, other_amp = calc_amplitude(n, w_amp, other_amp)
    # 振幅を出力
    print("w_amp: {}".format(w_amp))
    print("other_amp: {}".format(other_amp))
    # 確率を出力
    print("P(w): {}".format(w_amp**2))
    print("P(other): {}".format(other_amp**2))
    print()

1回目の振幅増幅
mu: 0.21875
w_amp: 0.6875
other_amp: 0.1875
P(w): 0.47265625
P(other): 0.03515625

2回目の振幅増幅
mu: 0.1328125
w_amp: 0.953125
other_amp: 0.078125
P(w): 0.908447265625
P(other): 0.006103515625

3回目の振幅増幅
mu: 0.013671875
w_amp: 0.98046875
other_amp: -0.05078125
P(w): 0.9613189697265625
P(other): 0.0025787353515625

4回目の振幅増幅
mu: -0.10888671875
w_amp: 0.7626953125
other_amp: -0.1669921875
P(w): 0.5817041397094727
P(other): 0.027886390686035156

5回目の振幅増幅
mu: -0.2042236328125
w_amp: 0.354248046875
other_amp: -0.241455078125
P(w): 0.1254916787147522
P(other): 0.058300554752349854

6回目の振幅増幅
mu: -0.248504638671875
w_amp: -0.14276123046875
other_amp: -0.25555419921875
P(w): 0.020380768924951553
P(other): 0.06530794873833656

7回目の振幅増幅
mu: -0.23065948486328125
w_amp: -0.6040802001953125
other_amp: -0.2057647705078125
P(w): 0.36491288826800883
P(other): 0.042339140782132745

8回目の振幅増幅
mu: -0.1551494598388672
w_amp: -0.9143791198730469
other_amp: -0.10453414916992188
P(w): 0.8360891748598078
P(other): 0.010927388342679478

9回目の振幅増幅
mu: -0.04085206985473633
w_amp: -0.9960832595825195
other_amp: 0.02283000946044922
P(w): 0.992181860020537
P(other): 0.0005212093319642008

10回目の振幅増幅
mu: 0.08365833759307861
w_amp: -0.8287665843963623
other_amp: 0.144486665725708
P(w): 0.6868540514120127
P(other): 0.020876396572532485

3回目までは | $w$ > の振幅 w_amp の値は増幅しましたが、4回目以降では小さくなったり大きくなったりします。

4回目で振幅が小さくなる原因は、元の w_amp の値は正なのに対して平均値 mu が負なので、平均周りに振幅を反転すると小さくなってしまうからですね。

4回目の振幅増幅を図示すると以下のような感じになります。