a perspective on mathematics, the pattern, and the abstract

Posts tagged: Scott Aaronson

"Whether or not God plays dice, I do"

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.

Logicians on safari

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
nothave to trust the alien or its exotic technology, and we wouldnothave 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,
everyformal 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.

This article by Scott Aaronson is an interesting read! Here’s another example:

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 forbreakingRSA! For example, if you proved that RSA with an n-bit key took n^{5}steps to break, you would’ve discovered an algorithm for breaking it in 2^{n^1/5}steps. If you proved that RSA took 2^{n^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:

W:Blut

Generator.x

Data is Nature

Algorithmic Worlds (on Tumblr)

Syntopia

Math blogs:

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

Mathematical Poetics

Science is Beauty

Incomprehensible Universe

Quantum Mechanics

Troll Physics

Infinity Imagined ( and also Small Stuff)

DVDP

People on Tumblr that I know in real life:

Manifold

Pretentious Elitism

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:

d/dt