Solving Hard Problems Faster: The Benefit Incentive/難問をより早く解く：量子コンピュータもたらす有益性

まずは、なぜ量子コンピュータを作りたいのか、からお話ししましょう。

なぜ量子コンピュータを作りたいのでしょうか？ 最も話題になっている理由は、量子コンピュータが「高速」で計算できるということです。 では、速い、というのはどういう意味でしょうか？どんな問題を解決できるのでしょうか？

計算能力の変化は社会に多大な影響を与える可能性があります。私たちは、過去半世紀にわたって、コンピュータがいかに気候や天気、地震をモデル化し、プランク時代の宇宙を研究し、新しい薬をつくり、より良い飛行機を設計できるか見てきました。また、あなたがこのコースを受講するのに使っているインターネットも、もちろんその成果の一つです。 興味深いことに、量子コンピュータは我々の能力を著しく向上させることがありますが、そうでないこともあります。その区別を理解することがこのコースの目標の1つです。

100万まで数える

私が100という数字を書きとめてほしいと言ったとしましょう。それは簡単です。 たった3桁です。1、0、0。 ペンと紙を手に慎重に書いていくと、おそらく3秒ほどで終わるでしょう。

次に、1から100までのすべての数字を書きとめてほしいと言ったならば、ちょっと不平を言うかもしれませんが、あなたは数分でそれを終わらせることができます。

100万という数字を書きとめてほしいと言ってみても、書きとめるには数秒しかかからず、まばたきせずに終わらせることができます。 しかし、私が1から100万までの数字を全て書きとめて欲しいと頼んだら、間違いなくあなたは不平を言うでしょう！1桁書くのに1秒かかるとすると、1日24時間働いても約10週間かかります。

なぜでしょうか。ある数字を書き留めることと、全て数え上げることという二つの作業の違いは何でしょうか。

数字を書きとめるのにかかる時間は、桁数の線形になると言えます。 100を書きとめるのに3秒かかるなら、1,000,000を書きとめるのに7秒かかります。

対照的に、1からその数値までのすべての数字を書きとめる作業にかかる時間は、桁数の指数関数的です。 1000までのすべての数字を書き込むことは、すべての数字を100まで書き込むのと比べて10倍かかります。（実際には、数字の大部分が2桁ではなく3桁になるため、10倍をわずかに上回ります）。 100万(1000000)は1000のたった二倍ほどの桁数ですが、100万までの数字を全て書き留めるには、1000までの数字を書き留めることの2000倍ほどの時間がかかります。

計算量

コンピュータ科学者にとってはこの違いこそが重要なのです。 これは、ある問題の「計算量」あるいは「計算複雑性」と呼ばれています。

(n)桁の数字を書き留めてください。(n)秒で終わるでしょう。 しかし列挙しようとしたときは、 (10^{n})秒以上かかる場合があります。

今日でも、多くの問題に対する最善の解法は指数関数的な時間を要します。コンピュータは、情報をソートする(並べ替える)のに非常に優れています。またソートされた情報を検索するのも大変得意です。しかし、様々なサイズの沢山の箱をコンテナに効率よく積むというような、沢山の解があるような問題の場合、私たちが知る限り、実際には指数関数的に困難です。

ここでいう困難さを「問題のサイズ」の増大と捉えることが重要です。もし変数の数が2倍(私たちが詰める箱が(n)個の代わりに(2n)個だったり、並べ替えしたいデータベースのエントリ数が二倍だったりする)になると、その問題を解くのにかかる時間は、二倍でしょうか？ それとも指数関数的に増えるでしょうか？

もちろん、中くらいに難しい問題も多くあります。 たとえば、問題のサイズを2倍にした場合に (n^2)時間を要するものが、時には4倍ほどで終わることもあります。 計算機科学者は、固定値(k)に対してその問題解決に(n^k)ステップがかかる場合、多項式時間と呼びます。(e^n)や(2^n)、(10^n)ステップを要する場合は、指数関数時間と呼ばれます。

正式には、表記(O(n))で線形を、(O(n^k))で多項式を、(O(e^n))で指数関数を表わします。これをBig-O表記(ビッグオーノーテーション)といいます。

量子計算

量子コンピュータは、この高速コンピュータと難しい問題の戦いの中で、力のバランスを変えることを目指しています。 古典的なコンピュータで計算量(O(e^n))という問題を量子コンピュータ上で計算量(O(n^k))にすることができれば、人類が効率的に解ける問題の種類を変えられるかもしれません。

現在、このような効果を可能にする量子コンピュータのアルゴリズムが数百ほど存在します。大多数は指数関数から多項式への改良を提供するのではなく、多項式からより効率のよい多項式への改良（たとえば(n^4)から(n^2)へ）がほとんどです。中には、多項式より難しいけれど指数関数ほどには難しくない問題を多項式問題にする、というものもあります。