量子計算における整数格子問題へのアプローチ

摘要

今まで計算困難と思われていた素因数分解?離散対数問題が量子計算機を使うと効率良く解けるというのは今となってはよく知られた事実である．一方，多くの研究者はNP困難問題はさすがに量子計算でも効率良く解くことはできない，と予想しているようである．それでは，素因数分解?離散対数問題以外（特に数論的な問題以外）で，NP困難ではなさそうでP（あるいはBPP）に入ることも知られていない問題に対して量子計算は有効であるのか，というのは自然な疑問であろう．本論文ではその代表として整数格子にまつわるいくつかの問題に関して量子計算の分野でどのような進展があるのか，アルゴリズム，暗号，計算量理論の観点から解説したい．