Solving Hard Problems Faster: The Benefit Incentive
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).
Computer scientists care about this difference. They refer to it as the computational complexity of a problem.
If is the number of digits in the number I ask you to write down, it will take you seconds. But for the enumeration task, it will take you more than 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 ( instead of 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 time, for example, results in four times as long a computation when you double the problem size. Computer scientists call any program that takes steps to run, for some fixed , polynomial time. Any problem that takes (or, equivalently, or ) steps is called exponential time.
Formally, we write these facts down using the notation to mean linear, for polynomial, and for exponential. This is called the Big-O notation.
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 on a classical computer and make it into one that is 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 to ). Some take problems that are harder than polynomial but not quite as hard as exponential and make them into polynomial problems.
© Keio University