rose.blog

… check out the whole series.

The first of a series of publications on solving artificial intelligence problems with quantum computers.

Image recognition with an adiabatic quantum computer I. Mapping to quadratic unconstrained binary optimization

Abstract:

Many artificial intelligence (AI) problems naturally map to NP-hard optimization problems. This has the interesting consequence that enabling human-level capability in machines often requires systems that can handle formally intractable problems. This issue can sometimes (but possibly not always) be resolved by building special-purpose heuristic algorithms, tailored to the problem in question. Because of the continued difficulties in automating certain tasks that are natural for humans, there remains a strong motivation for AI researchers to investigate and apply new algorithms and techniques to hard AI problems. Recently a novel class of relevant algorithms that require quantum mechanical hardware have been proposed. These algorithms, referred to as quantum adiabatic algorithms, represent a new approach to designing both complete and heuristic solvers for NP-hard optimization problems. In this work we describe how to formulate image recognition, which is a canonical NP-hard AI problem, as a Quadratic Unconstrained Binary Optimization (QUBO) problem. The QUBO format corresponds to the input format required for D-Wave superconducting adiabatic quantum computing (AQC) processors.

Here are a couple of articles about D-Wave in MIT Technology Review magazine this month.

The first is by Seth Lloyd, the second is by Scott Aaronson.

The reason that Scott’s is so much shorter is that he is busy trying to solve the four problems I presented when I last visited MIT and working on being a professional shut-in.

Here are some new job postings.

20080205_quantum_information_theory.pdf

20080205_condensed_matter_theory.pdf

20080205_computational_physicists.pdf

Race walking is really stupid. Angry crazed Samurais are awesome. Put them together and you get this.

I have spent a lot of time thinking about who is the greatest puppet ever. I have finally come to a decision. I think it’s Alf.

When I was a kid, I had this cardboard record which I got from Burger King that had songs written by and sung by Alf. One of them was called “Melmac Girls” and had lyrics like

“It’s cool the way they can braid the hair all over their face.”

Genius. Here it is on Ebay.

OK I also found it online. You have to listen to ten minutes of idiocy first but it’s worth it.

Here are some Alf facts.

What do I mean by red herring, you might ask?

The etymology of the phrase may be the practice of saving a hunted fox by dragging a smoked herring across its trail - creating a new, useless scent trail. When smoked, herring turns bright red and is quite odoriferous. The latter trait made it possible to deliberately leave a strong trail on the ground to facilitate training hounds to track a scent. Having been so trained, hounds would readily follow the scent of the fish over that of the fox, allowing their quarry to escape.

Analogy clarification:: Fish –> factoring; Fox –> ever other application of QCs.

Scott Aaronson over at Shtetl-optimized recently posted a great description of Shor’s algorithm for non-specialists, in response to a request from JR Minkel, a Scientific American writer. Even though Scott has an alarming lack of musical taste he has few peers when it comes to describing complex technical issues to non-specialists.

The premise of Shor’s algorithm is this: take one (large) QC, one large product of prime numbers, shake well, out comes the factors of the large product of primes.

The algorithm is interesting because it produces this output (the factors) much faster than you can without a QC. It is also possibly interesting from the applications perspective because the problem it solves is important for certain types of code-breaking.

There is a particular type of encryption in use that uses the “hardness” of factoring large products of prime numbers to keep data secure. This particular approach would become vulnerable in a world with large QCs.

So let’s say we lived in a world with factoring machines available at Walmart. Would internet commerce collapse? Of course not. The most likely thing that would happen is that encryption software providers–the people who keep your credit card numbers secure–would change the “hard” part of their encryption to something that (1) wasn’t factoring and (2) was impervious to QCs. Is this technically possible? Absolutely. Also over time it’s likely that encryption — even retail encryption — will migrate over to quantum encryption.

So you might ask why the NSA cares about factoring at all. I can only speculate, but here are three possible reasons: (1) they have a mandate to be at the leading edge of understanding all things cryptanalytic, regardless of practical application; (2) the possibility that messages encrypted today have been stored somewhere and will be decrypted in 5-10 years with some new advanced technology (QC); (3) they are concerned that new non-factoring crypto algorithms will be developed.

Alright so why am I going on about this? The reason is that when asked what QCs are good at, many QC experts respond with the factoring example, when there are several other perfectly great quantum algorithms that would also fit the bill. Why the focus on factoring? I’m not entirely sure, but here are two possible reasons: (1) how the algorithm works is technically very interesting (when people understand it, they usually say, man that’s cool!); (2) usually researchers are financed by the NSA, so it’s self-serving to put a line in the intro to your paper that lists code-breaking as an application, and then every paper written about QC starts with the same sentence, and the meme takes hold.

Why does it matter that experts focus on factoring? There are two reasons. The first is that factoring isn’t interesting from the applications/commercial perspective. It is hard to imagine how a company could become successful building machines that did nothing but factor products of primes.

The second reason is that the application is very negative in the sense that it makes the world worse than it was before the tech was introduced. There is no social benefit to adding factoring to the list of things humans can do well (or if there is, I haven’t heard anyone mention it). This “no social benefit” issue is often ignored by scientists and technologists, but I think this is a huge mistake. Most people feel great about supporting technologies with a clear social benefit (cures for cancer, etc.); not so much for weapons.

I think it would do the whole QC field a lot of good if the people “out there” who aren’t experts could hear about the algorithms/applications that stand a chance of creating real value, like quantum simulation, or possibly applications of the recent NAND tree algorithm, or optimization.

Whenever people ask what QCs can do, there’s a tendency for people to respond with the factoring example, which I think is making it very difficult for any non NSA people (ie pretty much everybody) to get excited about QCs. It’s hard to get really excited about something that’s both commercially worthless and has no positive social upside.

If the scientists & management at Merck/Pfizer/Exxon/DE Shaw/Amgen/Corning/Dow etc. understood (in the same way the NSA understands Shor’s algorithm) that QCs could exponentially speed up their quantum chemistry calculations there would be 100s of millions of dollars of investment from these sources flowing into practical QC R&D. This is a wonderful thing called market pull which would benefit everybody in the QC field, even if you don’t personally care about actually getting these machines into the hands of end users.

In contrast to factoring, quantum simulation is both extremely commercially valuable (a large fraction of the world’s supercomputer cycles are currently spent solving the Schrodinger equation) and offers the possibility for huge social good (new clean energy sources, better medicines, cleaner chemical plants, etc.).

Maybe it’s time to put away the fish.

On the front page of wordpress.com, three of the “hot posts” are:

1. Richard Dawkins’ documentary

2. Our QC announcement

3. About the UFC

!!!

An excellent morning all around.

Very cool. If you’re not terrified by the end of this check your pulse.

Here’s a link.

I thought this was quite interesting. It’s the slides from the 1998 Turing lecture, given by Jim Gray talking about what enabling technologies would have the most value for IT. Remarkably prescient given the date of the talk and how fast things change.

Here is a particularly interesting screen grab from p.47:

Gray sees such a system “discussing” the system with the designer…and mentions that this is a type of Turing test–the automated programming system is imitating a programmer.

I wonder how close to this vision a good declarative language would be?