Skip main navigation

Caveat: Function Growth

Read about the difference between constant factors and the growth of a function, and how that impacts the practicality of solving problems.

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 では、量子コンピュータがいかに高速に計算できるかについて話しましたが、これから二回のステップでより詳しくみていきましょう。


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


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





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



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

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


© Keio University
This article is from the free online

Understanding Quantum Computers

Created by
FutureLearn - Learning For Life

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.

Start Learning now