量子アルゴリズムの得意と限界

量子アルゴリズムは、重ね合わせと干渉を使って、特定の問題を解く手順です。速くなるのは一部の問題だけで、ふつうのプログラムがすべて速くなるわけではありません。

このレッスンでは、探索を速くする仕組みと、速くならないもの、そしてシミュレータの限界を学びます。

4つの項目から、1つの正解を探すとします。まず、4つすべてに同じ振幅 0.5 を与えます。確率は、どれも0.25です。

次に、正解の振幅の符号を逆にします。そして、すべての振幅を平均で折り返します。1回の手順で、正解の振幅が1になります。これを振幅増幅と呼びます。

# 4つの項目で、番号3に印を付けて、1ステップ増幅します。
state = [0.5, 0.5, 0.5, 0.5]
marked = 3
state[marked] = -state[marked]
mean = sum(state) / len(state)
for n in range(len(state)):
    state[n] = 2 * mean - state[n]
print(state)
# marked を 1 に変えて、もう一度実行してください。
# 大きくなる項目は、どれに動きますか。

ラボの amplify.py は、4つの項目の3番に印を付け、1ステップの増幅を行います。印を付ける所は、プログラムに教えています。

表示される言葉は英語です。chance of each は、それぞれの確率という意味です。after one amplification step は、1ステップの後です。

docker exec jupyter python3 steps/amplify.py

N個の項目から探すとき、ふつうの方法は最悪でN回調べます。振幅増幅は、Nの平方根に比例する回数で済みます。

速くなりますが、魔法ではありません。100万個でも、約800ステップが必要です。

大きな整数の素因数分解を、今知られているふつうの方法より、桁違いに速くやる量子アルゴリズムがあります。今の暗号の一部は、素因数分解が難しいことに頼っています。

ただし、必要なのは、大きく誤りの少ない機械です。今の機械は、まだそこに届いていません。

ラボのシミュレータは、すべての振幅を記憶して計算します。量子ビットが1つ増えると、振幅の数が2倍になり、作業も2倍になります。

だから、ふつうのパソコンでは、量子コンピュータの速さの利点は見せられません。見せられるのは、規則です。

本物の量子ビットは、とても繊細です。熱や電波のノイズで、振幅が少しずつ乱れ、干渉がうまくいかなくなります。

この乱れを直すのが誤り訂正です。1つの確かな量子ビットを守るために、たくさんの量子ビットを使います。

4つの項目で、増幅を2回続けると、どうなるでしょう。amplify.py の手順を、紙で2回目まで追います。

正解の確率は、1回目より上がるでしょうか。下がるなら、なぜ回数を数える必要があるかを、一文で書きましょう。