Basic Goal: Factoring／基本目標：素因数分解
計算機科学において最も重要な問題のクラスはPとNPの２つです。Pは多項式(Polynomial)を意味します。つまり、問題のサイズを(N)とし、(k)をある特定の定数とした場合、 Pクラスの問題は((O(N^k)))の多項式時間で解を計算できるあらゆる問題を指します。 NPは非決定性多項式(Non-deterministic Polynomial)です。
NPの問題の解法は指数関数的であり、Pに属さないと考えられていることはよく知られています。 言うまでもなく、どの指数関数も非常に速く値が増大していくため、指数関数的な時間を要する問題の解を計算することは一般的には困難であると考えられています。では、因数分解はどのクラスに属するのでしょうか？
素因数分解は、多項式以上、指数関数以下の計算量を必要とした問題であると現在考えられています。 量子コンピュータ上でShorのアルゴリズムを使えば、多項式時間で因数分解を解くことが出来ます。 これは、主に以下の3つの理由から、魅力的なことであると言えます。
- 問題そのものが重要
- 性能の向上が魅力的
- 新しい技術の確立
Reach your personal and professional goals
Unlock access to hundreds of expert online courses and degrees from top universities and educators to gain accredited qualifications and professional CV-building certificates.
Join over 18 million learners to launch, switch or build upon your career, all at your own pace, across a wide range of topic areas.
