# It’s like the quantum computer is playing 20 questions…

I’ve been thinking about the BlackBox compiler recently and came up with a very interesting analogy to the way it works. There are actually lots of different ways to think about how BlackBox works, and we’ll post more of them over time, but here is a very high level and fun one.

The main way that you use BlackBox is to supply it with a classical function which computes the “goodness” of a given bitstring by returning a real number (the lower this number, the better the bitstring was).

Whatever your optimization problem is, you need to write a function that encodes your problem into a series of bits (x1, x2, x3…. xN) to be discovered, and which also computes how “good” a given bitstring (e.g. 0,1,1…0) is. When you pass such a function to Blackbox, the quantum compiler then repeatedly comes up with ideas for bitstrings, and using the information that your function supplies about how good its “guesses” are, it quickly converges on the best bitstring possible.

So using this approach the quantum processor behaves as a co-processor to a classical computing resource. The classical computing resources handles one part of the problem (computing the goodness of a given bitstring), and the quantum computer handles the other (suggesting bitstrings). I realized that this is described very nicely by the two computers playing 20 questions with one another.

The quantum computer suggests creative solutions to a problem, and then the classical computer is used to give feedback on how good the suggested solution is. Using this feedback, BlackBox will intelligently suggest a new solution. So in the example above, Blackbox knows NOT to make the next question “Is it a carrot?”

There is actually a deep philosophical point here. One of the pieces that is missing in the puzzle of artificial intelligence is how to make algorithms and programs more creative. I have always been an advocate of using quantum computing to power AI, but we now start to see concrete ways in which it could really start to address some of the elusive problems that crop up when trying to build intelligent machines.

At D-Wave, we have been starting some initial explorations in the areas of machine creativity and machine dreams, but it is early days and the pieces are only just starting to fall into place.

I was wondering if you could use the QC to actually play 20 questions for real. This is quite a fun application idea. If anyone has any suggestions for how to craft 20 questions into an objective function, let me know. My first two thoughts were to do something with Wordnet and NLTK. You could try either a pattern matching or a machine learning version of ‘mining’ wordnet for the right answer. This project would be a little Watson-esque in flavour.

# New tutorials on devPortal: WMIS and MCS

There are two new tutorials on the website, complete with code snippets! Click on the images to go to the tutorial pages on the developer portal:

This tutorial (above) describes how to solve Weighted Maximum Independent Set (WMIS) problems using the hardware. Finding the Maximum Independent Set of a bunch of connected variables can be very useful. At a high level, the MIS it gives us information about the largest number of ‘things’ that can be achieved from a set when lots of those ‘things’ have conflicting requirements. In the tutorial, an example is given of scheduling events for a sports team, but you can imagine all sorts of variants: Train timetabling to improve services, assigning patients to surgeons to maximize the throughput of vital operations and minimize waiting lists, adjusting variable speed limits on motorways to reduce traffic jams during periods of congestion, etc etc.

This tutorial (above) describes how to find Maximum Common Subgraphs given two graphs. The example given in this tutorial is in molecule matching. Looking for areas where sub-structures in molecules are very similar can give us information about how such molecules behave. This is just one simple example of MCS. You can also imagine the same technique being applied to social networks to look for matches between the structuring of social groups. This technique could be used for improving ad placement or even for detecting crime rings.

These two tutorials are closely linked – as finding the MCS involves finding the MIS as part of the process. There are also lots of interesting applications of both these methods in graph and number theory.

If anyone would like to implement WMIS or MCS to solve any of the problem ideas mentioned in this post, please feel free!

# The dreams of spiritual machines

When I was in middle school, every year we had to select a project to work on. These projects came from a list of acceptable projects. The projects were typical science-ish projects you’d expect a seventh grader to take on. One year my project was about whooping cranes. Not sure why I picked that one. Maybe I thought it might be related to whooping cough.

One year the subject I picked was dreams. What were they? How did they come about? What, if anything did they tell us about our waking life? I remember being intensely fascinated by the topic at the time, feeling that the answers I was getting to my questions from grown-ups and the encyclopedias checked out from the school library (there was no internet back then, at least in a form I could access) were not satisfactory at all. This was one of my earliest realizations that there were questions no-one yet knew the answers to.

The subject of dreams has come up in my adult life several times, and each time the same questions about them bubble up from my early encounter with them. An acquaintance of mine went through a period of having night terrors, where she would scream so loud that it would wake people in neighboring houses. She described them as being a sense of horror and dread of the most intense and indescribable kind, with sure knowledge that it would never end. This led to multiple 911 calls over periods of years. Several trips to specialists and tests revealed nothing out of the ordinary. Then one day they suddenly stopped. To this day no one has a good explanation for why they started, or why they stopped.

One of my friends has multiple vivid, realistic dreams every night, and he remembers them. They are also often terrifying. I on the other hand rarely dream, or if I do, I don’t remember them.

Recently I have been thinking of dreams again, and I have four computer scientists to thank. One of them is Bill Macready, who is my friend and colleague at D-Wave, and inventor of the framework I’ll introduce shortly. The second is Douglas Hofstadter. The third is Geoff Hinton. The fourth is David Gelertner.

Gelertner is a very interesting guy. Not only is he a rock star computer scientist (Bill Joy called him “one of the most brilliant and visionary computer scientists of our time”), he is also an artist, entrepreneur and a writer with an MA is classical literature. He was injured badly opening a package from the Unabomber in 1993. He is the author of several books, but the one I want to focus on now is The Muse in the Machine, which  is must-read material for anyone interested in artificial intelligence.

In this book, Gelertner presents a compelling theory of cognition that includes emotion, creativity and dreams as a central critically important aspect of the creation of machines that think, feel and act as we do. In this theory, emotion, creativity, analogical thought and even spirituality are viewed as being essential to the creation of machines that behave as humans do. I can’t do the book justice in a short post – you should read it.

I am going to pull one quote out of the book though, but before I do I want to briefly touch on what Geoff Hinton has to do with all of this. Hinton is also a rock star in the world of artificial intelligence, and in particular in machine learning. He was one of the inventors of back propagation, and a pioneer in deep belief nets and unsupervised learning. A fascinating demo I really like starts around the 20:00 mark of this video. In this demo, he runs a deep learning system ‘in reverse’, in generative mode. Hinton refers to this process as the system “fantasizing” about the images it’s generating; however Hinton’s fantasizing can also be thought of as the system hallucinating, or even dreaming, about the subjects it has learned. Systems such as these exhibit what I believe to be clear instances of creativity – generating instances of objects that have never existed in the world before, but share some underlying property. In Hinton’s demo, this property is “two-ness”.

Alright so back to Gelertner, and the quote from The Muse in the Machine:

A computer that never hallucinates cannot possibly aspire to artificial thought.

While Gelertner speaks a somewhat different language than Hinton, I believe that the property of a machine that he is referring to here – the ability to hallucinate, fantasize or dream – is exactly the sort of thing Hinton is doing with his generative digit model. When you run that model I would argue that you are seeing the faintest wisps of the beginning of true cognition in a machine.

Douglas Hofstadter is probably the most famous of the four computer scientists I’ve been thinking about recently. He is of course the author of Godel, Escher, Bach, which every self-respecting technophile has read, but more importantly he has been a proponent for the need to think about cognition from a very different perspective than most computer scientists. For Hofstadter, creativity and analogical reasoning are the key points of interest he feels we need to understand in order to understand our own cognition. Here he is in the “Pattern-finding as the Core of Intelligence” introduction to his Fluid Analogies book:

In 1977, I began my new career as a professor of computer science, aiming to specialize in the field of artificial intelligence. My goals were modest, at least in number: first, to uncover the secrets of creativity, and second, to uncover the secrets of consciousness, by modeling both phenomena on a computer. Good goals. Not easy.

All four of these folks share a perspective that understanding how analogical thinking and creativity work is an important and under-studied part of building machines like us.

Recently we’ve been working on a series of projects that are aligned with this sort of program. The basic framework is introduced here, in an introductory tutorial.

This basic introduction is extended here.

One of the by-products of this work is a computing system that generates vivid dreamscapes. You can look at one of these by clicking on the candle photograph above, or by following through the Temporal QUFL tutorial, or by clicking on the direct link below.

The technical part of how these dreamscapes are generated is described in these tutorials.  I believe these ideas are important. These dreamscapes remind me of H.P. Lovecraft’s Dreamlands, and this from Celephais:

There are not many persons who know what wonders are opened to them in the stories and visions of their youth; for when as children we learn and dream, we think but half-formed thoughts, and when as men we try to remember, we are dulled and prosaic with the poison of life. But some of us awake in the night with strange phantasms of enchanted hills and gardens, of fountains that sing in the sun, of golden cliffs overhanging murmuring seas, of plains that stretch down to sleeping cities of bronze and stone, and of shadowy companies of heroes that ride caparisoned white horses along the edges of thick forests; and then we know that we have looked back through the ivory gates into that world of wonder which was ours before we were wise and unhappy.

I hope you like them.

# The Developer Portal

Keen-eyed readers may have noticed a new section on the D-Wave website entitled ‘developer portal’. Currently the devPortal is being tested within D-Wave, however we are hoping to open it up to many developers in a staged way within the next year.

We’ve been getting a fair amount of interest from developers around the world already, and we’re anxious to open up the portal so that everyone can have access to the tools needed to start programming quantum computers! However given that this way of programming is so new we are also cautious about carefully testing everything before doing so. In short, it is coming, but you will have to wait just a little longer to get access!

A few tutorials are already available for everyone on the portal. These are intended to give a simple background to programming the quantum systems in advance of the tools coming online. New tutorials will be added to this list over time. If you’d like to have a look you can find them here: DEVELOPER TUTORIALS

In the future we hope that we will be able to grow the community to include competitions and prizes, programming challenges, and large open source projects for people who are itching to make a contribution to the fun world of quantum computer programming.

# Finding the Most Probable Explanation using a quantum computer II: An example

Here is a simple example, which I found here, modified somewhat to be in line with my previous example related to rain.

What we want to know is this: when I wake up tomorrow morning, what is the probability that I will hear a rain-like tapping sound on my roof? One of the things we might think is important is the weather forecast. Is it projected to be cloudy? If so, it’s more likely to rain, which increases my chances.  Another important item to consider is that where I live, there is a horde of rabid squirrels who often run on the roof in preparation for attack, yet strangely they don’t come out much if it’s cloudy.

So we make a model with a total of 4 boolean (TRUE/FALSE) variables: Is it cloudy (C)? Is it raining (R)? Are there rabid squirrels out (S)? And is there a Tapping Sound (TS) on my roof? The relationships between these are stored in a set of Conditional Probability Tables (CPTs) shown in the picture below.

The first of these tables says that there is a 50% chance of being cloudy or not cloudy (I can change this as desired). The CPT on the right shows the conditional probability of variable Rain being true or false, depending on the value of the variable Cloudy (more likely Rain is True if Cloudy is True). The CPT on the left shows that if Cloudy is True, Squirrel is likely to be False (as squirrels don’t like the clouds), but if Cloudy is False, Squirrel is equally likely to be True or False. The bottom CPT shows the probability of Tapping Sound being True given the values of Squirrel and Rain.

Alright now that we’ve got our Bayesian net set up, we want to use it. Here we’ll use it as follows: we present evidence, which are known fixed values of one or more of our boolean variables, and we want to compute the Most Probable Explanation consistent with that evidence. For example, if I provide the evidence that Tapping Sound is True, the Most Probable Explanation is that Rain and Squirrel are both True, and Cloudy is False (note this may not be completely obvious, and depends on the numerical values we assign to the CPTs).

Let’s convert this problem to Weighted MAX-SAT. Using the prescription in the paper cited in the previous post. The idea is very simple. For every row in every CPT, create a clause formed of the negation of all the variables OR’ed together, and raise this clause to – log of the probability associated with that row. For example, I have my Cloudy CPT, whose first row is

C    Pr(C)

c     0.5

So I make a clause like $(\bar{c})^{-\log 0.5}$.

When I have more variables influencing the probability I get more variables in the clause. For example If I have a CPT entry, for Rain,

C    R    Pr(R|C)

c     r    0.8

ie if C is True, the probability of R being true also is 0.8, then I create a clause

$(\bar{c} V \bar{r})^{-\log 0.8}$.

After I’m done creating all of these clauses, I AND them all together, and that’s my Weighted MAX-SAT problem, which we can then run directly on the hardware!

I coded all this up in Matlab and ran it on the hardware. It works! See Bayesian networks are exciting!

# Finding the Most Probable Explanation using a quantum computer

The optimization problem that our hardware natively solves is known in physics as an Ising model. Defining a set of $\pm 1$ variables $s_j$, the hardware returns a set of these variables $\{s_j\}^*$ that, if our algorithm is working, minimizes the cost function

$E(s_1, ..., s_N) = \sum_{j=1}^N h_j s_j + \sum_{i

where $h_j$ and $J_{ij}$ are real numbers originating from the problem instance we want to solve.

Note that the hardware is inherently stochastic. Regardless of how we run the quantum algorithm we are never guaranteed to get the global minimum of $E$. What we get instead are samples from some probability distribution that, as algorithm designers, we try to engineer so that it is very likely that the samples we draw are “good” in the sense of providing an approximate solution to the problem.

Alright so we have some heuristic solver for the type of Ising model shown above. What can we do with it that might be useful? One idea is to use the hardware to solve what are known as Most Probable Explanation (MPE) problems. MPE is a problem encountered when you have a Bayesian network, with some evidence, and you’re trying to compute what values of the variables in your Net are most probable given the evidence you’ve got.

Before I show how to do this, first I should mention that the Ising model I just wrote down goes by other names. One of these is Weighted MAX-SAT. In the Weighted MAX-SAT problem, we are given a set of clauses with associated weights, and we’re asked to find the instantiation that produces the largest sum of the weights of the satisfied clauses. While it looks a little different at first blush, they are actually exactly the same problem under the hood.

The ideas I’ll be discussing here are mainly from “Using Weighted MAX-SAT Engines to solve MPE” by James D. Park. A great book about Bayesian stuff (and more generally about science and human nature that every human should read) is E. T. Jaynes’ Probability Theory: The Logic of Science.

What’s a Bayesian network? Wikipedia says:

A Bayesian network, belief network or directed acyclic graphical model is a probabilistic graphical model that represents a set of random variables and their conditional independencies via a directed acyclic graph (DAG). For example, a Bayesian network could represent the probabilistic relationships between diseases and symptoms. Given symptoms, the network can be used to compute the probabilities of the presence of various diseases.

BOORRRINGGG!!!!!!. … see previous post. Bayesian networks aren’t really boring, they are exciting! Here’s how I would describe them:

A Bayesian network is a framework that allows a computer to make inferences and decisions based on incomplete information.

That’s a big part of what humans do! Think about everything you’ve done today. You have reasoned about the world around you and used that reasoning to make decisions. For example, you might have heard raindrops on your roof, reasoned that it was raining, and grabbed your umbrella before heading out the door. However it is possible it wasn’t raining. Maybe it was the sound of a horde of angry rabid squirrels running across your roof, preparing to attack you as soon as you open the door. A Bayesian network is a way to quantify all of these possibilities. When we provide evidence to the network, we can try to calculate what the Most Probable Explanation is consistent with that evidence. Your own brain-based Bayesian network solved the MPE problem for you when you heard what you thought were raindrops. It computed the MPE for those sounds — rain. You then used that info and grabbed your umbrella. If you think about it, pretty much all your actions are conditioned on MPE decisions that can be formalized in a Bayesian way. With enough computing power, 99.999% (maybe more ) of what you do can be modeled using Bayesian methods.

We can solve the MPE problem directly in a quantum computer, via the mapping from MPE to Weighted MAX-SAT described in the J. D. Park article referenced above, and then by solving the Weighted MAX-SAT problem in hardware using an adiabatic quantum optimization algorithm.

In the next post I’ll reduce this to practice with a specific example.

# Applications ideas and a resolution

Yall may have noticed the cornucopeia of posty goodness appearing here yesterday. Each of these posts was about an idea for an application built using the Orion API. The client side API is now available on sourceforge (see sidebar under For Developers), as is a set of documentation, guidelines, help, enhancement requests, manual job submission, etc. also linked to in the sidebar under For Developers: Orion web services. Together these two resources are enough to start incorporating state-of-the-art optimization and constraint satisfaction solvers into your applications. Currently we are not connecting the web services to the AQC-based systems, although when we do the programming interface will be identical.

Each of the posts yesterday are about potential applications / applets that range from silly to important commercial applications. The amount of information about how to enable the application also has a wide range, from detailed step by step instructions to vague pointers to papers.

I would love to have folks code real applications around some or all of these ideas (and others too, there are lots!), and that is the real motivation for these posts. We are currently setting up an applications gallery where developers can post applications they have built using Orion web services, share code, and discuss what’s working well and what isn’t. One of the things I am really interested in are mash-ups of Orion and other web services interfaces, such as Facebook and Google offer.

I am going to try to stick to the following resolution: I am going to try to post one applications idea per day for the next year, for a total of 365 applications ideas, starting today. I think there are enough out there to be able to hit this goal… we’ll see!

# Strange ideas about intelligence (while my QUBO solver runs)

Having just read Jeff Hawkins’ On Intelligence, Danny Hillis’ PhD thesis The Connection Machine and Peter Norvig’s Artificial Intelligence: A Modern Approach, I have been having some strange ideas about intelligence.

What got me thinking about intelligence in the first place was the observation that many of the tasks that seem to be difficult for computers, but relatively easy for biological brains, are most naturally thought of as NP-hard optimization problems. Basically anything that involves complex pattern matching–recognizing speech, inference, relational database search, vision, and learning, for example.

Another thing that seems interesting is this: take any algorithm that scales linearly with input size. For the problem this algorithm solves, can you think of a single example where a human could beat a computer? I can’t think of one.

Finally: biological brains operate with small amounts of input data (five senses). For example if we look at a photograph the total data we receive is quite small.

Is it possible that the notion of complexity classes is important for asking the right questions about intelligence? Here’s a rough outline of an idea.

1. Categorize all of the problems that biological brains have to solve as well-posed computational problems.
2. The subset of these problems that can be solved with algorithms that scale polynomially can always be done better with silicon than with bio-brains. Note that this isn’t true in general–it requires the observation that the input problem instance size is small for bio-brains (# of pixels in a photograph eg.).
3. There are problems that have survival value to solve that are harder than P.
4. Brains evolved excellent heuristics to provide quick approximate solutions to the problems harder than P, and currently it is that subset where bio-brains beat silicon.
5. In a hierarchy of difficulty, some problems will be too hard for bio-brains to evolve heuristics for. This means that the primary differentiator in this picture of things will be the “easiest hard problems”. The hard hard problems are too hard for evolution to create hardware heuristics for.
6. The easiest hard problems (the group most likely to have good hardware heuristics and bad software heuristics) are NP-hard optimization problems.

In this view of the world, the key to mimicking bio-brains (at least from the computational viewpoint) is being able to quickly solve (in the heuristic sense) the types of NP-hard problems generally associated with intelligence. This is an algorithmic issue, and not so much a hardware capability issue. This argues against Ray Kurzweil’s implicit assumption that hardware capability is sufficient for intelligence to arise in machines. I tend to think now that breakthroughs in machine intelligence are going to come from algorithms–either new classical algorithms, or the capability to run quantum algorithms on quantum hardware, and not on Moore’s Law advances.

# Green quantum computers

As I mentioned in an earlier post, many of the chemical reactions that are vital to life as we know it require quantum mechanics to proceed. Many of the machines that make up living creatures function by exploiting QM in some way.

Progress is being made in tracking down how exactly this happens in specific cases. This scientific american article discusses some recent experimental work showing how the mechanisms of photosynthesis exploit QM to enhance the efficiency of converting sunlight to chemical energy.

Here’s a quote from the introductory segment in Nature:

… the observation of electronic coherences in such a complex system is remarkable. Assuming that the effect is general — that similar coherences occur in many different natural light-harvesting systems, and are observed at non-cryogenic temperatures — we may find that nature, through its evolutionary algorithm, has settled on an inherently quantum-mechanical process for the critical mechanism of efficient light harvesting. This is an interesting lesson to be considered when designing artificial systems for this purpose.

Here’s a link to the actual Nature article. You need a subscription to Nature to see it.

What I find most interesting about the article isn’t the underlying science. It has been known for a long time that photosynthesis involves processes that have to be described using QM (as are lots of other important processes like catalysis via enzymes). What’s interesting to me is that the scientists involved are starting to bridge the chasm between the field of quantum chemistry (which is usually how these types of things are described) and quantum computing (which has historically been a separate island from quantum chemistry).

BTW I was going to do a bit about how the non-photosynthetic plant & animal scientific community was “sceptical” of the photosynthetic plants’ claims to be quantum computers, containing irate statements from representatives of various communities, such as the holoparasitic plants (can’t do photosynthesis)… good piece for the Onion. I think I have too much real work to do though.