Caveat: Function Growth/注意するポイント:関数の増え方

関数の計算量はどのように増加していくのでしょうか？Step 1.3 では、量子コンピュータがいかに高速に計算できるかについて話しましたが、これから二回のステップでより詳しくみていきましょう。

ここまで、素因数分解、量子化学、汎用検索など、いくつかの量子計算アルゴリズムを見てきました。Shorの素因数分解アルゴリズムを使うと、従来知られていた最速のアルゴリズムと比べ、超多項式的な計算効率の改善が図れます。量子化学や量子シミュレーション全般に至っても、特定の問題に関しては超多項式的な計算効率の改善が可能になります。

Gvoverのアルゴリズムと呼ばれる、もっとも一般的な量子アルゴリズムは、特定の問題に対するアルゴリズムというよりは、あらゆる量子演算を解く上でのフレームワークであるとも言えます。このアルゴリズムを使えば、全ての問題の計算時間を平方根的に高速化することができます。。例えば、古典コンピュータで(O(N))のオーダーの問題に対して、量子コンピュータでは、(O(sqrt{N})) のオーダでの問題解決が可能となります。

定数倍問題

量子コンピュータの、計算複雑性におけるこれらの利点に、当初大変な期待が寄せられましたが、いくらか過剰評価されている部分もありました。現在では、この点に関する批判的意見が「定数倍問題」として受け入れられていることに注意が必要です。前述の、数字を書き出す例を思い出してください。各数字の桁を書くのにあなたは1秒かかり、友達が0.5 秒で終わるとしましょう。この差は、一つの数字を書く上では非常に有効かもしれません。しかし、100万までの全ての数字を書くことになったらどうでしょうか。その友達のスピードであっても5週間もかかります。途中でやめてしまうかもしれません！

しかし、もし1秒間に100桁かけるロボットがあったとしたら、100万個の数字を書くのは、17時間ほどで終わります。たとえ、桁数が増えることで計算量が指数関数的に増加したとしても、コンピューターやロボットが十分に早ければ、満足行く結果を得ることができます。

範囲が重要

ここでの重要な点は、私達が解こうとする問題の大きさです。例えば、ロボットに対して、100万の数字を書くように指示することは合理的かもしれませんが、10億、1兆だったらどうでしょうか？理論家は問題サイズの増加に伴う漸近特性という観点から、話そうとしますが、私達が実際のシステムを構築するときには、特定の大きさの問題を解くことを考えます。

簡単な例をお見せしましょう。下の図は(100x+5000)と、(x^2)という2つの関数を、(x)を0から1000までの幅で描いたものです。

上の図では、(x^2)である黄色のカーブは (O(x^2))で上昇し、 (O(x))で上昇している (100x+5000)に比べて、大きな値をとっています。それゆえに、縦軸が(x)のサイズの問題を解くためにかかる時間とすると、私達にとっては、(100x+5000)という関数を選ぶほうが妥当かもしれません。しかし下の図では、同じ関数の0から100までの範囲を表しており、先ほどとは逆の結果となっています。このように、微妙な範囲の違いによって、結果は変わってきてしまうのです。

解く問題の大きさが、(x = 100)までの大きさであれば、黄色の曲線を選ぶこととなるでしょう。そのためエンジニアたちは、理論家とは異なる提案をすることもあるのです。量子コンピューティングの目標は、漸近的な利点を活かせる機械を開発することではありますが、問題の範囲によって生じるこの差異は、実際のシステムにおいては問題となりうるのです。

良い問題を選ぶ

ほとんどのどのような問題にも、Groverのアルゴリズムの基本的な計算複雑性の利点は活用することができます。とはい、まだMicrosoft社のWordを、家庭用の量子コンピュータで動かすことすらできてはいませんが！大きな結果を得るには、量子アルゴリズムを問題に適応させなくてはなりません。そしてそのためには、問題の構造を発見することが重要となるのです。

Step 1.13では、気象モデリングのような、その解決にスーパーコンピューターがよく使われている類の問題について議論しますが、これらは量子コンピューティングにとって、良い問題の候補とは言えません。実際、量子コンピュータが効率的に解くことのできる問題には、主に以下の2つ制約があるのです。

1. データの入出力が得意ではない：量子コンピュータは、少なくともしばらくの間、現在のいわゆるデータの読み書きについては比較的適していません。
2. あまり大きいメモリは使えない：量子コンピュータは、少なくともしばらくの間、何ギガバイトものメモリを積むことはできません。そのため、10、100、多くても1000程度の量子ビットを用いる程度の問題が限界です。
3. そして3つ目の制約はもちろん古典コンピュータには解くことが難しい問題であるべきという点です。問題の大きさが大きくなるに連れて、取りうる答えが非常に速いスピードで増えていくという特徴をもつような問題です。

このコースで、より詳しい例を見ていきましょう。