Posts tagged: Scott Aaronson
A $100,000 offer is being made by quantum computing/complexity theory researcher Scott Aaronson to whomever can disprove the possibility of scalable quantum computation.
Although very primitive, small-scale quantum computers have been developed and realized in the field, the question of whether or not a large-scale quantum computer can exist to handle arbitrarily large computations is the focus of ongoing research and a matter of debate (at least to some researchers).
This is ultimately a matter of the possibility of quantum computers being able to exist in principle according to the laws of physics, and not one of just theoretical and technological advancement in a given period of time.
The way I see it is that any legitimate attempts to actually disprove the possibility of large scale quantum computation will only end up revealing more details and reasons to believe that large scale quantum computers can and will exist. I would even be willing to go as far as saying that the existence of large scale quantum computation ought to be demanded by the idea of computational universality.
Some cute examples of computability theory applied to specific problems.
- We now know that, if an alien with enormous computational powers came to Earth, it could prove to us whether White or Black has the winning strategy in chess. To be convinced of the proof, we would not have to trust the alien or its exotic technology, and we would not have to spend billions of years analyzing one move sequence after another. We’d simply have to engage in a short conversation with the alien about the sums of certain polynomials over finite fields.
- There’s a finite (and not unimaginably-large) set of boxes, such that if we knew how to pack those boxes into the trunk of your car, then we’d also know a proof of the Riemann Hypothesis. Indeed, every formal proof of the Riemann Hypothesis with at most (say) a million symbols corresponds to some way of packing the boxes into your trunk, and vice versa. Furthermore, a list of the boxes and their dimensions can be feasibly written down.
- Supposing you do prove the Riemann Hypothesis, it’s possible to convince someone of that fact, without revealing anything other than the fact that you proved it. It’s also possible to write the proof down in such a way that someone else could verify it, with very high confidence, having only seen 10 or 20 bits of the proof.
It would be great to prove that RSA is unbreakable by classical computers. But every known technique for proving that would, if it worked, simultaneously give an algorithm for breaking RSA! For example, if you proved that RSA with an n-bit key took n5 steps to break, you would’ve discovered an algorithm for breaking it in 2n^1/5 steps. If you proved that RSA took 2n^1/3 steps to break, you would’ve discovered an algorithm for breaking it in n(log n)^2 steps. As you show the problem to be harder, you simultaneously show it to be easier.
And an excerpt on the relevance of these examples:
So what are they then? Maybe it’s helpful to think of them as “quantitative epistemology”: discoveries about the capacities of finite beings like ourselves to learn mathematical truths. On this view, the theoretical computer scientist is basically a mathematical logician on a safari to the physical world: someone who tries to understand the universe by asking what sorts of mathematical questions can and can’t be answered within it. Not whether the universe is a computer, but what kind of computer it is! Naturally, this approach to understanding the world tends to appeal most to people for whom math (and especially discrete math) is reasonably clear, whereas physics is extremely mysterious.
In my opinion, one of the biggest challenges for our time is to integrate the enormous body of knowledge in theoretical computer science (or quantitative epistemology, or whatever you want to call it) with the rest of what we know about the universe. In the past, the logical safari mostly stayed comfortably within 19th-century physics; now it’s time to venture out into the early 20th century. Indeed, that’s exactly why I chose to work on quantum computing: not because I want to build quantum computers (though I wouldn’t mind that), but because I want to know what a universe that allows quantum computers is like.
If you are interested in where some of the content on this blog comes from I direct you to the following links:
http://paulbourke.net/fractals/ (I don’t think you need to know how to count or read to appreciate the content on this site)
Arithmancy photo pool ( pictures from flickr)
Some of my favorite blogs are:
Computer generated/algorithmic art:
Data is Nature
Algorithmic Worlds (on Tumblr)
These first three may require some mathematical maturity. Both Tao and Gowers have Fields medals!
Whats New (by Terrance Tao)
Gowers’ Weblog (by Tim Gowers)
The n-Category Cafe (group blog with John Baez)
Shtetl-Optimized ( by Scott Aaronson who does research in quantum computing/complexity theory)
Blogs on Tumblr:
Sense, Essence, and Existence
Science is Beauty
Infinity Imagined ( and also Small Stuff)
People on Tumblr that I know in real life:
Cut & Paste
Ryan Salge (maybe if you follow him he will post more of his art!)
A music blog I just started recently where I post songs that I like: