Want to keep learning?

This content is taken from the Keio University's online course, Understanding Quantum Computers. Join the course to learn more.

Caveat: Function Growth

How fast does the cost of a function grow? Earlier this week, we talked about the computational class motiviation. In this article and the next, let us add some nuance to the notion.

We have just seen several algorithms, including factoring, quantum chemistry, and generalized search. Shor’s factoring algorithm promises superpolynomial speedup compared to the best known classical algorithm. Quantum chemistry, or quantum simulation, also offers superpolynomial speedups for some specific problems.

The most general quantum algorithm, known as Grover’s algorithm, is really a broad framework for solving problems on a quantum computer rather than an algorithm for a specific problem. It gives a square root speedup for any problem. That is, it takes a problem that is \(O(N)\) on a classical computer and makes it \(O(\sqrt{N})\) on a quantum computer.

Constant factors matter

With this advantage in computational complexity, there was much initial excitement about quantum computers that was naive. The importance of a critical caveat is now appreciated: constant factors matter.

In our example above, we assumed it takes you one second to write each digit of a number. Perhaps a friend is faster; it only takes her half a second per digit. This advantage seems large for writing down a single number, but for enumerating every number up to a million, it will still take her five weeks, and she will probably object to the task!

But if I give you a robot that can write at a hundred digits per second, it can complete the entire million-number task in just seventeen hours. Even though the task grows exponentially as our number of digits grows, in practice there is a range of problem sizes we care about, and if we or our computers or robots are fast enough for those cases, then we can still solve the problems to our satisfaction.

Range matters

The previous paragraph hints at another important factor: the range of the problem we are attacking. Perhaps it’s reasonable to ask a robot to write a million numbers for us, but is a billion reasonable? A trillion? Although theorists love to talk in terms of the asymptotic behavior as the problem size grows, when we build real systems we aim to solve problems of some particular size.

We can illustrate this effect with a simple example. This plot compares the two functions \(100x+5000\) and \(x^2\), over the range 0 to 1000.

100x+5000 versus x squared, 0 to 1000

A theorist would tell you that the yellow curve, \(x^2\), is \(O(x^2)\), which dominates the \(100x+5000\) function, which is only \(O(x)\). Thus, if the vertical axis is the time it takes to solve a problem of size \(x\), it seems obvious we would prefer the blue curve (\(100x+5000\)). But the next plot, showing the same functions over the range 0 to 100, suggests a different, more nuanced interpretation.

100x+5000 versus x squared, 0 to 100

If the largest problem we care to solve is of size \(x = 100\), then we would actually prefer the yellow line. Thus, the engineers might give you a different suggestion than the theorists. Although the goal of quantum computing is to develop machines with an asymptotic advantage, this distinction will matter for real systems.

Picking good problems

Leveraging the basic computational complexity advantage of Grover’s algorithm can be done for almost any problem. You’re still not going to be running a quantum version of Microsoft Word on a home quantum computer, though! Achieving larger gains requires a quantum algorithm suited to the problem, which requires the discovery of some structure in the problem.

In Step 1.13, we discuss some problems, such as climate modeling, that are commonly attacked using supercomputers. These are mostly not good candidates. In fact, there are two major constraints on problems we can solve effectively:

  1. modest input/output requirements: Quantum computers will be relatively bad at reading and writing classical data for the foreseeable future.
  2. modest memory requirements: Quantum computers also will not have gigabytes of quantum memory for the foreseeable future, so problems that can be solved using tens, hundreds or at most thousands of qubits are desirable.

    And a third requirement, of course, is:

  3. the problems must be hard to solve on a classical computer, generally meaning that the number of possible answers that must be tested grows quickly as the problem size increases.

We will see examples in more detail throughout this course.




注意するポイント:関数の増え方

関数の計算量はどのように増加していくのでしょうか?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までの幅で描いたものです。

100x+5000 versus x squared, 0 to 1000

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

100x+5000 versus x squared, 0 to 100

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

良い問題を選ぶ

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

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

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

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

Share this article:

This article is from the free online course:

Understanding Quantum Computers

Keio University