Category: Computer Science

(Warning: partially valid arguments ahead, but at some points reality takes a hit and runs for the hills and then returns to make some sort of point.)
What I love about the threshold theorem for computation (classical or quantum) is that it is essentially a theorem about immortality. Whah? Immortality? Indeed. (For those unfamiliar with the ideas of the threshold theorem see a quantum discussion in quant-ph/0507174 by Daniel Gottesman.)
Well first of all, let me rephrase that. The thresholds theorems of computation are about immortality. We should pluralize the “theorem” since there are many different versions of the theorem applicable under many different assumptions. We should pluralize the “threshold” since there are many different parameters which describe the different assumptions.
Now given the assumptions of the thresholds theorems, we can ask the question about whether these assumptions are satisfied in the real world. If they are, then the particular theorem you are concerned with states that it is possible to design a computer whose rate of failing can be made arbitrarily small by building bigger computers out of the faulty components (and this size overhead scales in such a way that changing the rate of failure by k orders of magnitude only incures an overhead of increasing the size by a polynomial in k.) So, in essence, the theorem states that you can make your computer effectively immortal. Say you want it to live for a billion years, then you can build such a device. Say you want it to live for trillion years, then you can build a bigger device. Etc. etc. onward to effectively immortality. (Okay, so there are those of you who might object to me calling a computer a living thing and personifying it with the atributes of life and death, but I have too little time to spend arguing against mythical beasts in the machine for which we have no evidence of and which somehow make biology an independent branch of the laws of the universe 😉 )
So given that the threshold theorems somehow “prove” that we can make immortal machines, the question is obviously whether the universe actually obeys the conditions of one of the threholds theorems. I would certainly be inclined to believe that the answer to this question is that no, there is no thresholds theorem which actually holds in our universe. The threshold is zero. Why do I say this? Well, let’s just think of the most common forms of the quantum therhold theorems. One thing that these models don’t consider is a form of error in which the entire quantum computer is blown up by, to put it in a modern context, terrorists (you see, it all makes sense, because quantum computers can be used to hack the codes that these terrorists use to plot their evil deads. To misquote a famous 19th century author: A useless consistency is the hobgoblin of a creative but bored mind.) Now this form of error can certainly happen. There is certainly a probability that it will happen (at which point we might begin to worry whether it was a Republican or Democrat who calculated this probability.) And I am equally certain that the current threshold theorems do not apply to this form of error. Thus I can at least argue that today’s theorems do not have assumptions which are satisfied in the real world.
Of course the lack of a current theorem which is not satisfied by how the real world works, does not imply that there isn’t some thresholds theorem which is satisfied in the real world. So can we put our arguments on more rigorous (snicker) grounds? Well I would maintain that the lack of the Borg is quiet evidence that there is no threshold theorem for immortality in our universe. Huh? Well suppose that we try to extend our threshold theorem for quantum computation to the type of errors I described above (so-called “t-errors.”) Certainly I can imagine a way to do this (okay maybe not so realistic!) but at the cost of designing a large computer. Indeed I suspect that there are turtles all the way up, and that if we keep pressing higher into the heirarchy of errors we wish to be robust against, we will always be making larger and large computers. And certainly even with our current constructions to truely obtain immortality, we need larger and larger machines. This argument suggests that if there is such a theorem, then to achieve immortality we must construct larger and larger computers whose size, eventually must engulf the entire universe (okay I’m way out on a limb here, but I am currently in California where this is only a little more flakey than your average citizen’s view of the world.) So, since when I look around I do not see such a construction, and I believe that (in this case alien) technology will always expand to fill the void of what is possible (over the edge 😉 ) this implies to me that there the threshold for computation in the universe is zero. Of course I have discounted the possibility that just because I do not see the construction, that the construction does not exist. Indeed we ourselves may be this construction (quoteth Philip K. Dick “the Empire never ended.”) So, no Borg, no threshold. 🙂
Now you might think that believing the thresholds for computation are zero might lead me to choose another field than quantum computation. In fact you might even go so far as to say that maybe we should trash the classical computer revolution, since certainly, there are no fault-tolerant classical computers. But of course, this, like my argument above, is absurd. The thresholds theorems are meant to only be a step in the direction of establishing the possibility of a technology whose use and capacities are not infinite, but are indeed only designed to achieve as much as is possible given the assumptions of the theorems. The thresholds theorems is never about taking the limit of the theorems, by nailing our probability of failure to zero. The thresholds theorems is always about figuring out what you can do with the resources you have. Thus we shouldn’t view the thresholds theorems as a magic potion on the path towards building a quantum computer, but instead as a way to most optimize our construction of a computer.
More importantly for the field of quantum computation, the question of relevance is whether large quantum computers can be build which outperform classical computers. But this always has the context of what classical computer we are talking about. So really the thresholds theorems for quantum computation are more about whether we will be able to build a quantum computer which outperforms a classical computer. Now because we believe that quantum computers have exponentially benefits over classical computers for some tasks, this means that for these tasks, once you get a modern technology where quantum computers outperform classical computers, for the relevant task, building better classical computers becomes an exponential waste over building a better quantum computer. For me, this is the real threshold for quantum computation: the day we cross over from classical computers to quantum computers which outperform these classical computers. The thresholds theorems are just ways of stating that we don’t see any theoretical obstacles towards such a day.

A Knight talks about quantum entanglement. In fact he’s a double Knight: Sir Peter Knight.