Physic Labs

最先端の物理学

量子アルゴリズム（Shor、Grover）

Groverのアルゴリズムを示します。NN 個の要素中の目標状態の振幅を増幅し、状態ベクトルが二次元平面内で回転する様子を観察し、最適反復回数 ≈π4N\approx \frac{\pi}{4}\sqrt{N} を確かめます。

研究

器具

  • 二次元平面内で回転する状態ベクトルのモデル
  • サイズ N と反復回数 k のスライダー
  • 反復ごとの目標振幅・確率の表示

手順

  1. 問題サイズを設定

    「サイズ N」スライダーで模擬データベースの要素数（例：N = 25）を選びます。初期状態軸を見ると、目標の振幅は 1/N1/\sqrt{N} から始まり、N が大きいほど小さいです。平均 N/2N/2 回の試行を要する古典探索と比べます。

  2. 反復回数を増やす

    「反復回数」スライダーを1刻みずつ上げ、状態ベクトルが目標軸へ回転するのを追います。各 Grover 反復は角度 2θ2\theta（sin⁡θ=1/N\sin\theta = 1/\sqrt{N}）だけ回します。k 回後に目標を測定する確率 P(k)=sin⁡2((2k+1)θ)P(k) = \sin^2((2k+1)\theta) を読み取ります。

  3. 最適反復回数を探す

    各 N について確率が最大になる k を探し、k∗≈π4Nk^* \approx \frac{\pi}{4}\sqrt{N} と比較します。最適値を超えて回すと確率は再び下がります —— ベクトルが目標を行き過ぎるためです。N を大きく（例：100）して繰り返すと、k∗k^* は NN ではなく N\sqrt{N} に比例して増えます。

シミュレーション

実験の歴史

1982年リチャード・ファインマンは量子系で量子系をシミュレートする考えを提案し、量子計算の端緒を開きました。デイヴィッド・ドイッチュ（1985年）は万能量子チューリング機械を定義。1994年にピーター・ショアが多項式時間の素因数分解を、1996年にラヴ・グローバーが O(N)O(\sqrt{N}) 回のクエリで動く探索アルゴリズムを発表し、古典手法への二次の高速化を示しました。 ショアの数論的な仕組みと違い、Grover のアルゴリズムは2つの幾何学的変換だけを使います。目標状態に関する反射（オラクル）と平均に関する反射（拡散）です。ベネット、バーンスタイン、ブラッサール、ヴァジラニは量子探索の下界も Ω(N)\Omega(\sqrt{N}) であると証明し、Grover が漸近的に最適であることを示しました。イオントラップや超伝導量子ビットで小規模な実証が行われています。

関連する物理学者

リチャード・ファインマンニールス・ボーア

関連するライブラリのトピック

量子アルゴリズム（Shor、Grover）