shors-algorithm

ショアのアルゴリズム (shors-algorithm)

ショアのアルゴリズムは、量子計算によって整数の素因数分解を高速化するアルゴリズム。動画では、量子コンピュータが暗号へ影響しうる理由を示す代表例として触れられる。

素因数分解は一部の公開鍵暗号の安全性と関係するため、ショアのアルゴリズムは量子計算の社会的インパクトを語るときに頻繁に参照される。ただし動画の文脈では、量子コンピュータが何でも速くするのではなく、特定の構造を持つ問題で計算量のオーダーを改善する例として位置づけられる。