ショアのアルゴリズムと量子計算複雑性
【 ショアのアルゴリズムと量子計算複雑性 】 1990年代に入って、「対話型証明 = Interactive Proof」の導入によって、証明の概念が大きく変わったことは前回述べました。 1990年代、計算複雑性の世界では、対話型証明と並んでもう一つの大きな前進がありました。それは、1980年代にファインマンらによって始まった量子コンピュータ研究の流れの中で、計算複雑性の概念が、量子コンピュータの計算複雑性に拡大されたことです。 1993年、ベルンシュタインとヴァジラーニは、量子チューリング・マシンの上に、量子チューリング・マシンが多項式時間で計算可能な複雑性のクラス BQPを定義し、それがチューリング・マシンが多項式時間で計算可能な複雑性のクラスPを完全に包摂することを発見します。 古典的なコンピュータが多項式時間では計算できない問題が、量子コンピュータでは多項式時間で計算できる可能性があることが、複雑性理論の言葉で示されたのです。 1994年、ショアは驚くべき発表を行います。コンピュータでは多項式時間では解くことが難しいと考えられていた「素因数分解問題」を、量子コンピュータでは多項式時間で解くことができることを彼は見出したのです。「ショアのアルゴリズム」の発見です。 ショアのアルゴリズムの発見は、量子コンピュータの世界だけでなく、さまざまな分野の多くの人に強烈な影響を与えました。 量子コンピュータの研究に多くの人が加わるようになりました。素因数分解の困難さを、暗号の安全性の基礎に置いていた暗号技術も深刻な反省を迫られることになりました。その余波は、今も続いています。 理論的には、ショアのアルゴリズムは、ヴァジラーニたちが示した、複雑性クラスPの外側にあり(古典コンピュータでは多項式時間では計算できない)、かつ複雑性クラスBQPの内側にある(量子コンピュータでは多項式時間で計算できる)計算の実例を与えるものでした。 計算複雑性の研究も、ヴァジラーニのBQP、ショアのアルゴリズムの発見に大きな刺激を受けます。こうして、1970年代、クック、レビン、カープらによって始められた計算複雑性理論は、1990年代、対話型証明と量子複雑性を中心に、大きく変貌することになります。 -------------------------------- 「複雑性の新しいクラスBQPの