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.

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

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

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

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