量子アルゴリズム とは？

量子ビットの状態を操作し、重ね合わせや干渉などを利用するんだ。たとえば干渉を使って、欲しい答えが測定で得られる確率を高めるように計算を組み立てるよ。

全部の答えを読み出せるわけではないよ。測定すると一つの結果が得られる。だから、役立つ情報を取り出せるように操作の順序や繰り返しを設計する必要があるんだ。

ショアのアルゴリズムは、整数の桁数に対して多項式時間で因数分解できる量子アルゴリズムだよ。十分な規模と精度で実行できればRSAなどに影響する。現在知られている古典的な手法との違いであって、古典計算では速い方法が絶対に存在しないと証明したわけではないんだ。

グローバーのアルゴリズムは二次の改善だよ。N個の候補に正解が一つあり、候補が正解かを判定する仕組みを呼び出せるモデルでは、必要な呼び出し回数をO(N)からO(√N)へ減らせる。指数的な改善とは違うし、普通のデータベース検索がそのまま速くなるという意味でもないよ。

そうだね。入力の準備、判定を行う回路、量子操作の精度、測定や繰り返しの費用も考える必要がある。計算量が小さくなる理論と、現実の装置で有利な時間や費用になることは分けて確認しよう。