最先端の物理学

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

量子アルゴリズムは干渉ともつれを利用して特定の問題を高速化しますが、すべての計算を速くするわけではありません。

量子アルゴリズムはユニタリゲート、測定、古典処理の列です。指定された計算量モデルで、既知の最良古典手法より少ない資源で有用な出力分布を得ることを目指します。

GroverとShor

Groverはオラクルと平均反転を交互に適用し、印付き状態の振幅を増幅します。非構造探索には約 $\sqrt N$ 回の問い合わせが必要です。Shorは量子フーリエ変換と周期発見を用いて、誤り訂正を含むゲートモデルで入力ビット数の多項式時間で因数分解します。

量子アルゴリズムはあらゆる答えを読み出せるようにするわけではありません。測定結果は一つの標本なので、干渉によって望む振幅を増幅します。Grover探索ではオラクルが目標を標識し、振幅増幅が各反復で状態を目標側へ約 $\pi/4$ 回転させ、問い合わせ回数は $\sqrt N$ のオーダーです。Shor法は剰余乗算の周期性で多項式時間量子素因数分解を行いますが、実用上の優位性は誤り訂正と装置に依存します。

問い合わせ計算量は総実行時間と同じではありません。応用では状態準備、誤り訂正、読み出しのコストも考慮します。解析ではオラクル模型と入力分布を明示する必要があり、漸近的優位性は小規模データや高価な前処理で失われることがあります。理想回路から耐故障機へ移行したとき、どの問題群で利点が保たれるかが重要な研究課題です。