ショアの素因数分解プロトコル

時事用語事典

2008/03

井元信之

1994年、ベル研究所のP.ショアが提案した素因数分解の量子計算プロトコル。一斉アダマール変換（→「量子情報」）と、べき乗剰余計算と、量子フーリエ変換から構成され、そのどれもが量子演算のステップ数として多項式の範囲に収まることが理論的に証明されている。