Computational universality

Last week I watched a great internet video produced by the people at code.org about the importance of teaching kids how to code. One description in particular was compelling. Near the end, Gabe Newell from Valve says “the programmers of tomorrow are the wizards of the future. You’re going to look like you have magic powers compared to everybody else.”

I like this idea. I have three young kids who I would like to get interested in programming. An interesting analogy that works for them is this. Wizards are cool, because they have powers and can cast spells. In order to cast these spells, they need to learn powerful magic, usually from ancient grimoires (best when from dubious origin). The most powerful magicians can do spectacularly cool things, like make themselves immortal, raise the dead, and suchlike.

Programmers are a lot like olde tyme wizards.

May or may not be a D-Wave software engineer at work.

May or may not be a new OCTO hire.

Programmers are a lot like olde tyme wizards. We learn a lot of arcane knowledge from musty old tomes, then we design and cast spells (programs) that can, if our kung fu is strong enough, affect the entire world (and even beyond!). II really like this identification. And not only because it gives me an excuse to dress up in a velvet robe and recite incantations at work.

In thinking about why it is that programming is such a profound, magic-like activity, I got to thinking about computational universality. Have you ever wondered how it’s possible that your phone can be a phone, music player, internet video streamer and calculator all at the same time, and why your toaster doesn’t do all these things? The reason is very profound.

There is an intimate connection between physics and computation. An implication of this is that we know how to build machines that can mimic the physics of any item in the classical world. We call these machines computers, and this property is called Turing completeness. Now usually you don’t think of a computer as mimicking the physics of objects in the physical world. However it is astonishing that any physical event in the real world describable by classical physics can be efficiently simulated using the type of computer we build today.

Intelligently designing 3D printed artificial life and other hilarities

Suzanne's 3D printed InMoov robot hand. Yes you will hear more about this.

Suzanne’s 3D printed InMoov robot hand. Yes you will hear more about this.

Why is this so dramatically cool? Because computers can now reach into the real world and change it via programs. It used to be that the world of the computer and the “real world” were easily distinguishable. This is no longer the case. From artificial life, to augmented reality, to 3D printed physical objects, to controlling the flow of the world’s wealth, computers and programs are increasingly becoming more difficult to separate from the “real world”. (As a personal aside, I find it increasingly difficult to accept any other ontological program than the “simulation hypothesis” — seems overwhelmingly the most likely of any humankind has come up with).

The fact that computers can simulate classical physics increasingly means that programs that we and our children will write will be just like magic in the stories. Virtually anything you can imagine can be done using programs. These programs will be just like spells. We’re starting to see this starting even now.

Now in the above I keep saying “classical physics” because computers as we build them today can’t do everything that Nature does. Today’s computers are like miniature clockwork universes, and can do anything that could be done in a “real” clockwork universe. We know that our Universe isn’t exactly like this (although for most purposes it’s pretty close).

There’s another concept that has been recently introduced which is called a universal quantum computer. Such a machine is capable of simulating all quantum physics, which presumably includes as a subset all of classical physics.

Level 9 Create Black Hole spell. Requires quantum gravity computer.

Level 9 Create Black Hole spell. Requires quantum gravity computer.

Quantum computers probably aren’t the end of the story, at some point we will likely have quantum gravity computers or suchlike where the programs will cause the vacuum state of our universe to tunnel or something. But even so, programs running on a universal quantum computer (which doesn’t exist yet, but likely will at some point, especially if I’m right that the simulation hypothesis is correct :-)) would be totally kick-ass 8th level type spells (we’ll reserve 9th level for the universal quantum gravity computer c. 2054).

By the way

By the way, D-Wave’s current processor architecture is classically universal (can do anything a classical computer can do), but not quantumly universal, although it’s really easy to make it so (just add a new coupling device) if some day it turns out there’s a good reason to do this.

Boltzmann machines can be used to help find Waldo.

Boltzmann machines can be used to help find Waldo.

It’s an interesting and somewhat disturbing point that quantum computers that can run quantum annealing (the kind we build) and quantum computers that can run any quantum algorithm (the as-yet-imaginary-existing-only-in-powerpoint-slide-deck-format kind) don’t actually differ much in utility.

If someone were to plop down a perfect universal quantum computer with a hundred trillion logical qubits on my desk right now, there’s only one useful thing we would know what to use it for — quantum annealing. Faster and better optimization & lightning quick Boltzmann machines.

9 thoughts on “Computational universality

  1. “By the way, D-Wave’s current processor architecture is classically universal (can do anything a classical computer can do), but not quantumly universal, although it’s really easy to make it so (just add a new coupling device) if some day it turns out there’s a good reason to do this.”

    So it would be able to run Shor’s? I realize this isn’t an area of interest for you personally, but successfully implementing quantum cryptographic stuff might quiet the naysayers.

    And speaking of cryptography, what happened to “Better than Shor’s”?
    i.e. https://dwave.wordpress.com/2011/05/11/learning-to-program-the-d-wave-one/#comment-22008

    • Yes a universal quantum computer can run Shor’s algorithm (and anything else you could dream up consistent with quantum physics). Re. cryptanalysis, it’s not something our partners are interested in — machine learning is where all the interest lies and so that’s the area we’ve been investing in.

  2. Gelfnlak Thunkberboob, you should not name this terrifying monster algorithm that surely will end all encryption the way we know it! http://wp.me/p2lHU6-wQ

    D-Wave’s machine is not able to execute it, as it isn’t quantum universal. But Geordie’s point is well taken, outside of the NSA headquarters, how much practical relevance does a factoring algorithm have?

  3. somebody played _way_ too much Dungeons n Dragons… typical neckbeard foolishness and arrogance. Have fun competing with all the Indian programmers who will work for 5$ an hour!

  4. Pingback: » Blog Archive TransAlchemy Today March 21, 2013 » TransAlchemy

  5. Wizardry?🙂

    I remember the “hacker test” of the eighties, you had to answer some odd questions, depending on your answers you was ranked from user (lowest) to demi-god (that was above wizard).

    For sure quantum computers are extremly fascinating, but I am still very impressed by any brain (even if some people obviously do not use it properly) and the DNA. And by the master of this brilliance the emergence.

    So I am very suspicious about all claims regarding “artificial intelligence” also because intelligence as such can not be artificial, because intelligence should be a principal that results out of emergent conditions.

    There is really a lot knowledge to master left over:-)

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s