# Solving Hard Problems Faster: The Benefit Incentive

Writing down the number one million is faster than counting to a million. Learn what this tells us about how hard problems are to solve.

Let’s begin by talking about the motivation.

Why do we want to build quantum computers? The reason that’s most talked about is that quantum computers will be able to compute “fast”. So what does fast mean? What kinds of problems will they be able to solve?

Changes in computational capability can have an enormous impact on society. We have seen over the last half century how computers can model climate and weather and earthquakes, study the early Universe, discover new drugs, and design better airplanes, to say nothing of how they have enabled the very Internet technology on which you are studying this course. Interestingly, quantum computers will significantly advance our capabilities in some ways, but not in others; understanding that distinction is one of the goals of this course.

## Counting to a million

Let’s say I ask you to write down the number one hundred. It’s simple; just three digits: one, zero, zero. It takes you perhaps three seconds if you have a pen and paper handy and write carefully. If, instead, I ask you to write down all of the numbers from one to a hundred, you might grumble a bit, but you can do it in a couple of minutes.

Now if I raise that number to one million and ask you to write it down, it still takes only a few seconds, and you will do it without batting an eyelash. But if I ask you to write down all of the numbers from one to one million, you will definitely complain! If it takes you one second per digit, it would take you about ten weeks, working twenty-four hours a day.

Why? What is the difference between the two tasks of writing down a number, or counting all the way?

We can say that writing down a number is linear in the number of digits. If it takes you three seconds to write down 100, it will take you seven seconds to write down 1,000,000.

In contrast, the task of writing down all of the numbers is exponential in the number of digits. Writing all the numbers to a thousand takes ten times as long as writing all of the numbers to one hundred. (Actually, slightly more than ten times as long, since most of the numbers are three digits instead of two.) Writing down all of the numbers to a million takes about two thousand times as long as writing down all of the numbers to a thousand, even though the numbers are only twice as long (most are six digits instead of three).

## Computational complexity

Computer scientists care about this difference. They refer to it as the computational complexity of a problem.

If (n) is the number of digits in the number I ask you to write down, it will take you (n) seconds. But for the enumeration task, it will take you more than (10^{n}) seconds.

Today, our best solutions to many problems require exponential time. Computers are extraordinarily good at sorting information, and at searching it once it’s sorted, for example. But problems involving many possible solutions, such as tasks like packing odd-sized boxes into a shipping container, are much harder – in fact, exponentially hard, as far as we know.

It is important to note that we measure this growth as the problem size increases. If we want to solve a problem with twice as many variables ((2n) instead of (n) boxes we want to pack, or entries in our database), will it take us twice as long, or exponentially longer?

There are, of course, many problems of intermediate difficulty. Something that take (n^2) time, for example, results in four times as long a computation when you double the problem size. Computer scientists call any program that takes (n^k) steps to run, for some fixed (k), polynomial time. Any problem that takes (10^n) (or, equivalently, (e^n) or (2^n)) steps is called exponential time.

Formally, we write these facts down using the notation (O(n)) to mean linear, (O(n^k)) for polynomial, and (O(e^n)) for exponential. This is called the Big-O notation.

## Quantum computing

Quantum computers aim to change the balance of power in this faster-computer-versus-harder-problem contest. If we can take a problem that is (O(e^n)) on a classical computer and make it into one that is (O(n^k)) on a quantum computer, we might be changing the kinds of problems humanity is effectively capable of solving.

There are now several hundred known algorithms for quantum computers that offer some advantage like this. The vast majority do not give us an exponential-to-polynomial improvement, but instead a polynomial-to-better-polynomial improvement (for example, from (n^4) to (n^2)). Some take problems that are harder than polynomial but not quite as hard as exponential and make them into polynomial problems.

# 難問をより早く解く：量子コンピュータもたらす有益性

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

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

## 100万まで数える

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

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

## 計算量

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

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

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

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