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.

Quantum computer 20 questions

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.

“Inside the chip” – new video showing Rainier 128 processor

Here is a video showing how some of the parts of a D-Wave Rainier processor go together to create the fabric of the quantum computer.

The animation shows how the processor is made up of 128 qubits, 352 couplers and nearly 24,000 Josephson junctions. The qubits are arranged in a tiling pattern to allow them to connect to one another.

Enjoy!

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:

Quantum computer tutorial quantum programming

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.

Quantum computer tutorial quantum programming

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!

Physics World blog article featuring D-Wave

On Friday Hamish Johnston from Physics World visited D-Wave to have a look round and investigate the ‘inside’ of the D-Wave box. Read his report here!

Physics World Blog >> Inside the box at D-Wave

Quantum Computing PhysicsWorld Blog

Here are a few of the photos from his visit on Flickr:

Visit to D-Wave Systems Flickr set

Vesuvius: A closer look – 512 qubit processor gallery

The next generation of D-Wave’s technology is called Vesuvius, and it’s going to be a very interesting processor. The testing and development of this new generation of quantum processor is going well. In the meantime, here are some beautiful images of Vesuvius!

quantum computer quantum computing D-Wave Systems Vesuvius

Above: An entire wafer of Vesuvius processors after the full fabrication process has completed.

.

quantum computer quantum computing D-Wave Systems Vesuvius

Above: Photographing the wafer from a different angle allows more of the structure to be seen. Exercise for the reader: Estimate the number of qubits in this image :)

.

quantum computer quantum computing D-Wave Systems Vesuvius

Above: A slightly closer view of part of the wafer. The small scale of the structures (<1um) produces a diffraction grating effect (like you see on the underside of a CD) resulting in a beautiful spectrum of colours reflecting from the wafer surface.

.

quantum computer quantum computing D-Wave Systems Vesuvius

Above: A different angle of shot produces different colours and allows different areas of the circuitry to become visible.

.

quantum computer quantum computing D-Wave Systems Vesuvius

Above: A close-up image of a single Vesuvius processor on the wafer. The white square seen to the right of the image contains the main ‘fabric’ of 512 connected qubits.

.

quantum computer quantum computing D-Wave Systems Vesuvius

Above: An image of a processor wire-bonded to the chip carrier, ready to be installed into the computer system. The wires carry the signals to the quantum components and associated circuitry on the chip.

.

quantum computer quantum computing D-Wave Systems Vesuvius

Above: A larger view of the bonded Vesuvius processor. More of the chip packaging is now also visible in the image.

.

quantum computer quantum computing D-Wave Systems Vesuvius

Above: The full chip packaging is visible, complete with wafer.

.

Quantum computing and light switches

So as part of learning how to become a quantum ninja and program the D-Wave One, it is important to understand the problem that the machine is designed to solve. The D-Wave machine is designed to find the minimum value of a particular mathematical expression which I can write down in one line:

quantum computing

As people tend to be put off by mathematical equations in blogposts, I decided to augment it with a picture of a cute cat. However, unless you are very mathematically inclined (like kitty), it might not be intuitive what minimizing this expression actually means, why it is important, or how quantum computing helps. So I’m going to try to answer those three questions in this post.

.
1.) What does the cat’s expression mean?

The machine is designed to solve discrete optimization problems. What is a discrete optimization problem? It is one where you are trying to find the best settings for a bunch of switches. Here’s a graphical example of what is going on. Let’s imagine that our switches are light switches which each have a ‘bias value’ (a number) associated with them, and they can each be set either ON or OFF:

The light switch game

quantum computing

The game that we must play is to set all the switches into the right configuration. What is the right configuration? It is the one where when we set each of the switches to either ON or OFF (where ON = +1 and OFF = -1) and then we add up all the switches’ bias values multiplied by their settings, we get the lowest answer. This is where the first term in the cat’s expression comes from. The bias values are called h’s and the switch settings are called s’s.

quantum computing

So depending upon which switches we set to +1 and which we set to -1, we will get a different score overall. You can try this game. Hopefully you’ll find it easy because there’s a simple rule to winning:

quantum computing

We find that if we set all the switches with positive biases to OFF and all the switches with negative biases to ON and add up the result then we get the lowest overall value. Easy, right? I can give you as many switches as I want with many different bias values and you just look at each one in turn and flip it either ON or OFF accordingly.

OK, let’s make it harder. So now imagine that many of the pairs of switches have an additional rule, one which involves considering PAIRS of switches in addition to just individual switches… we add a new bias value (called J) which we multiply by BOTH the switch settings that connect to it, and we add the resulting value we get from each pair of switches to our overall number too. Still, all we have to do is decide whether each switch should be ON or OFF subject to this new rule.

quantum computing

But now it is much, much harder to decide whether a switch should be ON or OFF, because its neighbours affect it. Even with the simple example shown with 2 switches in the figure above, you can’t just follow the rule of setting them to be the opposite sign to their bias value anymore (try it!). With a complex web of switches having many neighbours, it quickly becomes very frustrating to try and find the right combination to give you the lowest value overall.

quantum computing
.

2.) It’s a math expression – who cares?

We didn’t build a machine to play a strange masochistic light switch game. The concept of finding a good configuration of binary variables (switches) in this way lies at the heart of many problems that are encountered in everyday applications. A few are shown in figure below (click to expand):

quantum computing

Even the idea of doing science itself is an optimization problem (you are trying to find the best ‘configuration’ of terms contributing to a scientific equation which matches our real world observations).

.
3.) How does quantum mechanics help?

With a couple of switches you can just try every combination of ON’s and OFF’s, there are only four possibilities: [ON ON], [ON OFF], [OFF ON] or [OFF OFF]. But as you add more and more switches, the number of possible ways that the switches can be set grows exponentially:

quantum computing

You can start to see why the game isn’t much fun anymore. In fact it is even difficult for our most powerful supercomputers. Being able to store all those possible configurations in memory, and moving them around inside conventional processors to calculate if our guess is right takes a very, very long time. With only 500 switches, there isn’t enough time in the Universe to check all the configurations.

Quantum mechanics can give us a helping hand with this problem. The fundamental power of a quantum computer comes from the idea that you can put bits of information into a superposition of states. Which means that using a quantum computer, our light switches can be ON and OFF at the same time:
quantum computing
Now lets consider the same bunch of switches as before, but now held in a quantum computer’s memory:

quantum computing

Because all the light switches are on and off at the same time, we know that the correct answer (correct ON/OFF settings for each switch) is represented in there somewhere… it is just currently hidden from us.

What the D-Wave quantum computer allows you to do is take this ‘quantum representation’ of your switches and extract the configuration of ONs and OFFs with the lowest value.
Here’s how you do this:

quantum computing

You start with the system in its quantum superposition as described above, and you slowly adjust the quantum computer to turn off the quantum superposition effect. At the same time, you slowly turn up all those bias values (the h and J’s from earlier). As this is performed, you allow the switches to slowly drop out of the superposition and choose one classical state, either ON or OFF. At the end, each switch MUST have chosen to be either ON or OFF. The quantum mechanics working inside the computer helps the light switches settle into the right states to give the lowest overall value when you add them all up at the end. Even though there are 2^N possible configurations it could have ended up in, it finds the lowest one, winning the light switch game.

The Developer Portal

quantum computer programming - 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.

IEEE talk at Johns Hopkins University

I gave a talk at Johns Hopkins University on Monday entitled ‘Why the world needs quantum computing’. The video was for a general audience (no specific quantum physics background required). Here is a link to the talk. The video is available for download from this site!



Do not disturb my quantum circles

Quantum computingWhy do some people say a quantum computer has 4 bits, and others say they have hundreds? Why is it more complicated than a regular computer? As a scientist in this field myself, I can’t help but feel bad about the confusion surrounding this topic. People are really just curious about the potential of this cool sounding technology, and although news reports continue to promise the appearance of these machines very soon, the exact definition of a quantum computer still seems to be elusive.

I’m going to try and explain one of the main problems in the field of quantum computing today through the use of a visual analogy. The following explanation gets to the heart of a real disagreement, even between experts in the field. There are heated debates in the scientific community over this problem (yes, scientists get into dogfights too). So be aware that you’re getting some juicy inside knowledge here about what really stumps even expert scientists! Of course we don’t often want to shout about the fact that we get stumped by things… but it is true :) I should mention that this explanation is a very conceptual and abstract way to look at quantum computing so there won’t be any implementations or specific algorithms discussed. It compares the ‘conventional’ approach of quantum computing with a new approach, called ‘Natural Quantum Computing’ (NQC). The quantum computers built by D-Wave are of the NQC type.

.
Building blocks – in theory and in practice

Let’s begin with some background. When engineers and scientists build a new technology, there are two factors that come into play. There’s the theoretical model of the technology or system, and then there’s the practical implementation of that technology or system. These two companions are like yin and yang, both are necessary for the whole to function, yet they are forever competing with one another, two sides of the same coin.
In my analogy, my yin and yang are going to be represented by circles:
.

quantum computing

.
Which circle is better? You might argue that the perfect yin circle is mathematically more beautiful, but if it is never found in nature, then is it really of any use to us? The more natural yang circle has its own bumpy beauty in that it really represents the true nature of what we see around us. You just don’t see perfect circles in nature.

Now, what does this have to do with computing? Well, when we want to build a system, we build it out of bumpy circles (we have to, as they are the only things we can find around us). But we understand it – and predict how it will behave mathematically – by approximating it with perfect circles, because those are easier for us to calculate with. So, let’s pretend that our circles are now building blocks:
.

quantum computing

.
In most cases, this works pretty well. Our mathematical models now predict the behaviour of the circles pretty much the same way as they behave in nature (if you’d like to think about this system ‘behaving’ dynamically, imagine removing one of the circles on the lower layer and trying to predict where they would all end up). Our model of the circles would probably get it roughly right.

When we try to understand classical digital circuits, the same thing happens. We build a ‘model’ of a classical digital computer, like the picture above, and that model behaves in a similar way to its real-world counterpart.

.
Building a ‘conventional’ Quantum Computer using circles

However, (and here begins the juicy bit) – quantum computers don’t work like that. At least, not the ones that people have been trying to build up to now. I’m going to use the phrase ‘conventional QC’ to describe those, because there IS a different way of doing things which I’ll describe later. It turns out that in a conventional QC that slight difference between the yin and yang descriptions really does make ALL the difference.

What would a conventional quantum computer look like if we used the circle analogy to describe it? Well our mathematical yin model of it would probably look something like this:

.
quantum computing
.

What happens when you try and build this model using real, bumpy, yang circles? Well, you can try…

.
quantum computing
.

Oops! What happened? It didn’t work like we thought it would. The imperfections in the circles just made our delicate system come crashing down. Try again? The same thing happens. You can never get those circles to behave like their yin counterparts. The bumpiness just makes it impossible.

This is exactly what happens when we try to build a quantum computer. Our theories tell us that if we can just get 50, or 100, or maybe 500 of those darned circles to balance on top of one another then our technology will be able to fulfil our every dream! But we just can’t do it in real life – the thing keeps falling over! That is exactly what is meant by a system undergoing ‘decoherence’ if you are familiar with quantum computing parlance.

Well, something has to be done about this. We still want to be able to build a quantum computing system, right?

Yes – but there is an important problem to be addressed here. Who is at fault? Something didn’t add up, and blame must be assigned! Most people blame the yang engineers of the system for using bumpy circles: “Your circles are not perfect enough. Your system falls over. You’re not trying hard enough.”

So the diligent engineers try to find ways to make their circles more and more smooth. Little by little, they are able to balance one or two more on top of each other, for a little longer. But the circles can never be exactly perfect – so although that mathematically stable equilibrium of hundreds of balanced circles can be easily be modelled in theory, it is questionable as to whether it can it ever be built.

The interesting thing is that the question is almost never asked the other way round:
Are the yin circles perhaps too perfect?

In other words: Why do we create models of things that we then can’t ever practically make for real? All approximate models break down at some point, but the difference is usually small enough to still be able to inform our practical building of things. But in this case the model seems useless for anything we try to build that is more complex than a few building blocks!

.
Natural Quantum Computation

There is another way to build quantum computers that DO behave like their models. There is a type of quantum computing known as Natural Quantum Computing (NQC). This is a way of using quantum systems that we CAN build, in a way that is practical, and doesn’t go against what nature intended to happen to those circles.

A natural quantum computer system would be represented more like this:

.
quantum computing
.

Now the bumpiness doesn’t matter as much, because once again our model behaves a lot more like the real thing we are building. We have attacked the problem from both sides here – we have taken a reality check on our expectations of building with bumpy circles, and we have designed a mathematical model that respects that. We can still build up our quantum computer to be bigger and bigger using this method, and to do more and more, but it now captures the essence of how nature’s elements really do behave. Now this should answer the question about why different people have built quantum computers with different numbers of ‘qubits’ (quantum bits) – try and balance them using the conventional approach, and it depends how well you smooth out your bumpy circles. You might be able to get four, five, or even seven wobbling precariously on top of one another. People are working all over the world on trying to improve what nature has given to us, to get those circles smoother and smoother.

But using Natural QC and you can easily build systems with hundreds of bits. The system works differently, and it doesn’t fall over so much!

.
So why isn’t everyone taking this Natural QC approach?

Some people feel that it is better to just keep trying to make the circles ever smoother, because people are very familiar with the theoretical ‘yin model’ and have worked with this system mathematically for many years, developing algorithms to allow such a system (once built) to solve problems very quickly. But natural quantum computing is also very good at solving specific types of problems, like those in artificial intelligence and optimization. I myself feel that these NQC-suited problems are more interesting. Given that we also know that it is much easier to build these natural quantum computers, for me it’s really a no-brainer! But some people still like the idea of building the precariously-balancing conventional type of quantum computer. And it’s a matter of opinion about whether or not you believe that it is possible to make those circles smooth enough to get them to balance. But that’s half the fun in science – there are some questions that just haven’t been answered yet!

Even so, I think that we are sometimes a little too biased towards the yin theoretical description of a perfect system, hypnotized by the beauty and simplicity of our mathematical models. And we become disheartened and frustrated when real systems don’t behave like this. But this is not necessarily a problem with nature; it can also be thought of as a problem with our models! Sure, we can make nature behave more like our models by polishing those bumpy circles. But we can also make our models behave more like nature too. We can meet half way, and have the best of both worlds. And personally I’d rather build problem solving things (and models of them!) with natural bumpiness than spend my entire life trying to polish circles to an unachievable smoothness.