Quantum Computing since Democritus

by Scott Aaronson

if you travel at a v fraction of the speed of light for a proper time t, then the elapsed time in your computer's reference frame is

“real” computation to diverge from our abstract mathematical model of

K. Thorne, Black Holes and Time Warps: Einstein's Outrageous Legacy, W. W. Norton & Company, 1995 (reprint edition).

Why are we safe? Well, you have to look at what the energy density of the universe is made up of. There's matter, including ordinary matter as well as dark matter, there's radiation, and then there's the famous cosmological constant detected a decade ago, which describes the energy density of empty space.

The answer, then, to whether the universe is finite or infinite, is unfortunately that we don't know.

If this expansion is such an important force in the universe, why doesn't it matter within our own planet or galaxy? Because on the scale that we live, there are other forces like gravity that are constantly counteracting the expansion.

In Planck units, the cosmological constant is about 10-121, and so we find that 10122 is about the maximum number of bits that could ever be used in a computation in the physical world.

Basically, this formula combines π, Boltzmann's constant, Planck's constant and the speed of light. It has to be true. (I’m learning to think like a physicist. Kidding!)

There's a joke where a farmer hires a mathematician to build a fence in as efficient a fashion as possible – that is, to build a fence with the most area inside given some perimeter. So the mathematician builds a tiny circle of fence, steps inside and declares the rest of the Earth to be outside.

So what does any of this have to do with computation? You might say that if the universe is infinite, then clearly in principle you could perform an arbitrarily long computation. You just need enough Turing machine tape. What's the problem with that argument?

“I don't know.” I guess the whole idea with science is that if we don't know the answer, we don't try to sprout one out of our butt or something. We try to base our answers on something.

to be easier than NP-complete, but that are still too hard to efficiently solve with a quantum computer. Two examples are Graph Isomorphism and approximate shortest vector.

What's the complexity class for creativity?

Someone asked me if humans have an oracle in their head for NP. Well, maybe Gauss or Wiles did. But for most of us, finding proofs is a very hit-or-miss business.

You can change your perspective and it seems pathetic that after three billion years of natural selection and after this time building up civilizations, all the wars and everything else, we can solve a few instances of SAT – but if you switch to the Riemann Hypothesis or Goldbach's Conjecture instances, suddenly we can't solve those.

we should first make sure the data actually supports the hypothesis that humans are good at finding proofs. I’m not convinced that it does.

“why is that?” That's a very big question, but I think part of the answer is we've got a billion-year head start. We've got the advantage of a billion years of natural selection giving us a very good toolbox of heuristics for solving certain kinds of search problem. Not all of them and not all the time, but in some cases, we can do really well.

Sure. And after the computers take over from us, maybe they'll worry that they'll be out of a job once some NP oracle comes along.

There are as many complexity classes as there are different notions of computation. So, the richness of the complexity zoo just seems like an inevitable reflection of the richness of the computational world.

For example, maybe people who believe God is on their side are braver in battle. Or maybe religion is one of the factors (besides more obvious factors) that induces men and women to get married and have lots of babies, and is therefore adaptive just from a Darwinian point of view. Years ago I was struck by an irony: in contemporary America, you've got these stereotypical coastal elites who believe in Darwinism and often live by themselves well into their thirties or forties, and then you've got these stereotypical heartland folks who reject Darwinism but marry young and have 7 kids, 49 grandkids and 343 great-grandkids.

So then it's not really a contest between “Darwinists” and “anti-Darwinists”; it's just a contest between Darwinian theorists and Darwinian practitioners!