*Addenda on QC*

The lay person tends to associate the word "quantum" with weird, mystical, almost magical properties of the material world. I've explained in past posts on my blog that, while quantum mechanics

*obsolesced*classical mechanics, quantum computation does not obsolesce classical computation, it only augments it. This is because both classical computation and quantum computation can be organized as two departments under a larger theoretical umbrella called information theory. Quantum information theory (QIT) does not revise or modify classical IT, it only tells you how IT behaves when you have access to quantum phenomena.

Another important point to keep in mind is that it is easy to specify classical problems that are so hard that even if you had an ideal quantum computer, it would provide no speedup in solving the problem. The famous halting problem is just one example of such a problem. And far from being arcane problems of purely academic interest, many of these problems are the very things we care most about solving. To understand this, let me give an example.

Suppose we have a math problem of interest (it could be some matrix multiplication or calculating some gradients or whatever). Now, we search through the literature and find that the best known algorithm is exponential time class. What this means is that, as the size of our problem grows, the running-time of the best known algorithm grows as an exponential. So, let's say when our problem size is 2 (say, a 2x2 matrix), the running time is 4 units of time. When the problem size is 3, the running time is 8, when the size is 4, the running time is 16, and so on, doubling the running time for each increment in problem size. Obviously, we are going to run into a brick wall very fast. At a problem size of just 30, our running time will already be 1,073,741,824 units of time. Even if our unit of time was 1 microsecond, the total running time would be over 16 minutes and would double to 32 minutes for a problem size of 31. So, it's obvious that this is a very tough problem, and there are a lot of tough problems like this that we would really like to be able to solve efficiently (e.g. simulating protein-folding).

An ideal quantum computer could provide what is called "exponential speedup". Let's apply exponential speedup to our hypothetical algorithm above and see what happens. When our problem size is 2, the running time (with exponential speedup) is 2. When the problem size is 3, the running time is 3. When the problem size is 30,

*the running time is just 30*, almost a billion times faster! And that's the reason that people are so excited by the possibility of QC. No one in the QC field thinks that we will be able to achieve ideal speedup, that is, exponential speedup. (In fact, there are theoretical reasons why we

*cannot*achieve maximum theoretical speedup). But even if we managed to build a crappy quantum computer that only achieves some polynomial speedup (e.g. square-power, or cube-power speedup), we could still solve huge swathes of very important problems! So, that's a good reason to want to build quantum computers.

But let's go back to those nasty classical problems like the halting problem. This is what makes them so nasty: even if you had a computer with

*exponential*speed-up, it would be no help whatsoever in solving these problems any faster. Do you see the issue here? The best speedup that an ideal (un-realizable) quantum computer can achieve is still not fast enough to even make a dent in huge swathes of classical problems that are superlatively important. So, even if we succeed in building quantum computers at scale, we are still stuck in the same rut we are currently in, that is, we are still stuck with huge swathes of important, unsolved (

*un-solvable*) problems. The only difference is that, yes, many important problems that we cannot solve today will become solvable. My reason for pointing this out is that it is important to keep the promises of QC in proportion to reality; much of the hyperventilated rhetoric surrounding QC makes it out to be some kind of universal panacea that is going to turn every important problem in math and science into a push-button calculation. This is not true, in fact, it's downright irresponsible for pop-science journalists to keep spreading this misinformation among the lay-public who simply don't have the qualifications required to discern pop-sci hype from grounded, scientific optimism.

If you're interested in learning more about the time-complexity of algorithms and this topic is new to you, I recommend the following video:

Key insight: Even having a quantum computer does not reduce NP to P (if P=NP, then a QC makes solving everything in NP faster, but if P=/=NP, then even a QC cannot help you solve problems in NP but not in P as though they were in P).