rose.blog

A very interesting and fundamental question is whether or not there exist computational problems that just can’t be solved, even in principle. It’s common for people to assume that it’s just a matter of time and smarts and we can figure everything out.

Unfortunately this probably isn’t the case. One class of problems (called NP-complete) are probably not exactly solvable, no matter how big, fast or advanced computers get. How can we know this for sure, you ask?

Here’s one way: assume a certain set of laws of physics, and then use these to derive what can and can’t be calculated, and how resource requirements (time and memory) scale with problem size.

If the universe really ran using the laws of classical physics, then whether or not NP-complete problems are intractable is the P=NP question. It is overwhelmingly likely that P does not equal NP and therefore in a classical universe, NP-complete problems of sufficiently largeness can never be solved.

Ah, but you say, our universe isn’t classical. The fundamental laws of physics are probably something more like quantum mechanics. Unfortunately, even though the verdict isn’t fully in yet, it looks like even in a quantum mechanical universe (which is probably the one we live in) NP-complete problems are STILL intractable!

So you might be asking yourself, so what. OK well NP-complete problems show up everywhere. Let’s stretch a bit and imagine that we could cure cancer if only we could solve a certain NP-complete problem. If this problem could never be solved, even in principle, by anything obeying the laws of physics, then we could NEVER cure cancer,even if we evolved for another 1,000,000 years and our brains were quantum computers the size of the milky way.

Kind of humbling, eh?

Anyway, questions like this are really fun to think about, and motivate a particular way of studying the power of quantum computers, which brings me back to what I wanted to talk about in this post.

Usually what people mean by “solving a problem” is getting the exact solution. For example, if I ask what 4*6 is, you don’t get half marks for saying it’s 23.

But what do you do if you can’t get an exact solution, but something close to exact might be OK? You settle for an approximate solution.

Let me elaborate on this by talking a little bit about the particular NP-complete problem we attack using our systems - Max Clique.

Max Clique is a graph theory problem. It’s pretty simple. Given a graph (which is a set of vertices and edges between some of these vertices), find the largest set of vertices where each vertex in the set is connected by an edge to all other members of the set. Here’s an example from here:

The biggest set of vertices with the clique property is the red set {3, 4, 5, 6}.

Note that there are a bunch of cliques with 3 vertices (like {7, 8, 9}). These cliques aren’t the biggest (ie. not exact solutions), but they are “approximate” solutions, in the sense that 3 is almost 4. All NP-complete problems have this feature, that possible answers can be ranked using some “goodness” criteria.

This is important because even if we can’t exactly solve a problem, it may be possible to find a “good enough” solution by using an algorithm designed to get a good approximation quickly. In practice, everywhere NP-complete problems show up in real-world applications, this is the approach that is taken - first we figure out what “good enough” means, and then we find an algorithm that gives this “good enough” solution as quickly as possible.

For example, for Max Clique, lots of approximation algorithms that run in polynomial time are known. Here is one (called Qualex-MS) that scales like N^3, where N is the number of vertices in the input graph. Note that even though the algorithm terminates after order (N^3) steps, it’s of course not guaranteed to find the exact answer after it terminates, although in practice it usually gives a pretty good answer.

OK so what does this have to do with QCs? Well let’s assume for a moment that for QCs NP-complete problems remain intractable (which I believe is the case). If getting exact solutions is out of the question (which again I believe is the case), what should we do to figure out how one of these machines performs?

We have to do the same thing as we do in conventional approximation algorithms - run the machines using polynomial time, and see how good the answer we get out of the QC is. We don’t expect the answer to be exact, but maybe for alot of cases it will be (although we can’t guarantee this).

This way of looking at the performance of QCs (as “hardware heuristics”) is non-standard, and only makes sense for problems where “approximate solution” is a meaningful concept. For example if we want to break codes, an approximate key doesn’t cut it - we need the exact key or nothing happens. For QCs applied to NP-complete problems the “approximate is good enough” approach makes a lot of sense, especially if we want to apply the machines to real-world situations where today approximate answers are good enough.

So physically how does a QC operate to get an approximate answer to an NP-complete problem? Imagine we’ve built an AQC, and its energy levels are as shown in the picture below (think of the x-axis as time, with the beginning of the calculation the the left, and the end of the calculation to the right). At the end of the calculation we get the exact answer if we’re in the lowest energy level. If we’re not in the lowest energy level, we get an approximate answer. The lower the energy level is we end up in, the better the approximation.

The way AQC works is that at the beginning of the calculation (s=0) we always start in the lowest energy level (the lowest blue line). At the place labeled “minimum gap” we can skip up to a wrong answer (the green line), where we get stuck until the end of the calculation. If this happens, we get an approximate answer (in this case, the second-best solution, like the 3-clique above). So if we run this AQC on a problem with energy levels like this, with 100% certainty we’ll either get the exact solution or the next-to-best solution by the time we get to s=1.

So for any problem like this, we can sweep the s parameter (think of this like time) pretty quickly and guarantee a pretty good solution.

Which leads me to:

When people say QCs speed up the solution of NP-complete problems quadratically, they mean for the special case of requiring the exact solution. This speed-up has very little to do with the real question, which is how good an approximate answer do QCs get, given some fixed amount of computational time.

Today I’m going to talk about analog computers, but first I’m going to define what I mean by the term. Here is a beautiful definition from a beautiful paper:

…analog computation is quite different from the commonly used binary-digital computation. In the digital approach, you first devise an algorithm (a set of instructions for finding the solution to a problem), then execute each step of the algorithm in the manner of Boolean operation. In contrast, analog computation is concerned with no symbolic Boolean operation; instead it utilizes the properties of a physical system to perform the mathematical operations required for the solution.

Yeah that’s sweet.

Something important to note: The definition of analog computer I’m using is the one in the quote above. Note that NOWHERE does it say anything about continuous variables, etc, or any of the other additional stuff that sometimes people associate with analog computation. The core of the above is simply that an analog computer uses the natural physical evolution of some (hopefully programmable) system in order to solve a difficult computational problem.

If you’re interested in quantum computation, then it’s very important to understand the difference between the two computational models outlined in the above quote. In the “digital/gate” approach, algorithms are compiled to gates which are then “fed” to a circuit containing bits/qubits. In the analog approach, there are no gates; there is just the natural physical evolution of some system, which somehow is supposed to calculate something interesting.

Alot of research in quantum computation focuses on the “gate model” applied to quantum systems. Now if you know me you know I HATE the gate model. For various technical reasons (which eventually I’m going to enumerate) I don’t think gate model quantum computers are ever going to be commonplace.

This being said, the gate model is quite popular, and for many people learning about quantum computation, it’s the only model you learn about, which is a shame (since building them is verging on impossible). Some of the concepts people take for granted, such as the concept that noise is always harmful to quantum computation, really only apply to the gate model and aren’t generally useful concepts for other models of quantum computation.

OK so I hate the gate model. But I really love another model. It’s called adiabatic quantum computation.

Now we don’t exactly do adiabatic quantum computation (AQC) at D-Wave; our processors use a remarkable variant of it, developed internally here. Followers of our progress will note that we almost never talk about the technical details of what we’re doing. We are however going to disclose the computational model of the processor in order to show experts how it works “under the hood”. Stay tuned.

Anyway AQCs are analog computers. There are two very good papers that talk about how you might build an AQC using superconducting qubits here and here.

The way the AQC model works is that you build an array of qubits (say a square grid for example) with programmable couplers between qubits (see here for some published info on one of D-Wave’s programmable couplers). The settings of these couplers, together with individual biases (favoring one qubit state over the other) on each qubit, comprise the machine language of an AQC. The user of the AQC (1) starts the machine with all of the couplers turned off and all of the local biases favoring the 0 qubit state; (2) turns on a tunneling term between the qubit states of each qubit; (3) slowly turns off the tunneling term while tuning the couplers and local biases to their target values; (4) measures the final states of the qubits. That’s it. No gates.

There are alot of very nice features of the AQC model that make it MUCH easier to build one than a gate model quantum computer. I’m not going to go into all of them just yet (I’m going to later after our computational model paper publishes). So we must be giving something up, right? No! AQC is formally equivalent to the gate model in computational power.

It really is much easier to build an AQC (or its cousin cluster state QC, which is also an analog computational model) than a gate model QC. So why aren’t more people trying to build AQCs or cluster state QCs? I’m not sure exactly, but I think it is related to the interdisciplinary nature of this sort of development. In order to appreciate how much of a difference there is (practically) in difficulty between building two different hardware proposals, the input of a lot of engineers is needed.

Unfortunately, and to the field’s detriment, there are only a handful of places in the world where the type of infrastructure exists to separate practical models (such as AQC) from models that are probably only useful as theoretical abstractions (the gate model).

In the last post I implied that there are types of computational problems that are intractable, in the sense that they have exponential scaling with problem size. In this post I am going to discuss one particular type of problem like this: NP-complete problems.

I’m going to focus on these because this is the type of problem that our processors are designed for.

Obvious Statement #1: The first useful QC is going to be application - specific. What, you want us to build a general purpose QC right out of the gate?

Not only are our processors designed only for NP-complete problems, they actually are much more specific than this. They are designed to solve a particular NP-complete problem called Maximum Clique. This problem is equivalent to Maximum Independent Set and Minimum Vertex Cover.

So what do we know about Maximum Clique? A couple things. Since it’s NP-complete, it’s likely that the best possible algorithms (run on conventional computers) have exponential scaling. In addition, Max Clique is known to be “really really hard”, in the sense that it is intractable to even get good approximate solutions (experts: It’s APX-complete and see this). So right now, if you want to get an exact solution to a big Maximum Clique problem you’re usually out of luck.

We also know how good our systems have to be to beat conventional hardware/software on this problem, as there is good agreement amongst experts as to how well state-of-the-art exact and approximate algorithms perform on Max Clique (see here).

OK so what we’re building, if you ignore what’s going on under the hood, can be thought of as a “black box” for solving Maximum Clique. So this is the answer to the first question I get asked all the time (see my previous post), “what would you use one for?”. Our answer is: Getting real accurate and real fast solutions to big Maximum Clique problems.

Your response to this might be, uuuhhhh OK but what good is that? Great question. This is going to be the subject of lots of my posts. We have some cool ideas and have built one app already that we’re going to release shortly, probably via this blog.

I’m going to split this post up into a couple different posts as it is getting kinda lengthy.

What I want to discuss today is some jargon you should know in order to understand what quantum computers will ultimately be good at. It’s not too hard but some of the words aren’t that common, so here’s some groundwork for some follow-on posts where I’m going to try to clarify some common misunderstandings about quantum computation.

There are two questions I always get relating to our machines and quantum computation in general: (1) “what would you use one for?” and (2) “how good will they be at that?”. These questions are difficult to answer without using a computer science concept called computational scaling. So what I’m going to do is introduce the concept for beginners (if you’re an expert go and re-read Garey and Johnson).

Here’s the idea. Let’s say you want to watch your favorite movie (Rocky III) from beginning to end. This movie is 99 minutes long. So how long does it take to watch it once? 99 minutes, sucka!

Alright now let’s say you want to watch it two times. How many minutes is this? Assuming you don’t take a break (why would you), it’s two times 99 minutes = 198 minutes. How about three times. 3 times 99 minutes = 297 minutes. How about 15 times??? 15 times 99 minutes = 1485 glorious minutes!!! Eye of the tiger baby!

Every time we watch Rocky III we add 99 minutes to the total time. A shorthand notation for this is 99*N minutes, where N is the number of times we watch. This is called linear scaling, because the total time (99*N minutes) increases linearly with N.

Linear scaling is an example of what is more generally known as polynomial scaling. A problem scales polynomially if the difficulty of solving it increases like a polynomial of the problem size. In if the problem size is N, this means things like N^2, N^3, N^5, etc. as long as it’s N to the power of a fixed number, that’s polynomial. Generally polynomial scaling is a good thing, and the lower the power, the better, ie. N is better than N^2 etc.

OK now let’s say instead you are forced to watch the worst movie ever made (Secrets and Lies) at 142 horrible minutes. And let’s say that the time it takes you to recover from watching it doubles every time you watch it, starting at 1 week recovery time for watching it once. So one horrible viewing takes 1 week to recover from. If we are forced to watch it twice, we need 2*1 week = 2 weeks to recover. Three times, we need 2*2*1 week = 4 weeks to recover. The total number of weeks it takes to recover is [2*2*...*2 (multiply 2 by itself N-1 times) ] * 1 week if we’re forced to watch it N times. Writing this out in math shorthand, this is 2^(N-1) weeks. This is called exponential scaling (because the N is in the exponent).

Exponential scaling means something gets really big (or really small) really fast. If I make you watch Secrets and Lies 50 times in a row (taking a total of 142*50=7,100 minutes or about 120 hours), according to our formula above, it would take you 2^49 weeks to recover! This is about 10 trillion years!!!

OK so what does this have to do with anything. Let’s say we were to go back to Rocky III, and watch it in fast-forward, so that it only takes 10 minutes to watch. How much time does it take to watch it N times? 10*N minutes! Notice that it’s still linear scaling, just the number out in front has changed. Let’s say we watch it on super ultra fast forward, so that it only takes 1 microsecond to watch the whole movie. How long does it take to watch it N times? N microseconds! Still linear scaling.

Back to Secrets and Lies. Let’s say you’re allowed to wear earplugs while you watch, so that the time to recover from the first viewing is only one day instead of one week, but every time you watch the recovery time still doubles. How long does it take to recover from 50 back to back viewings? 2^49 days, or about 1.5 trillion years. Still exponential scaling, still a long time! What if we’re allowed to gouge out our eyes and wear earplugs? Let’s say it only takes 1 microsecond to recover from one viewing. How long does it take to recover from 50 viewings? 2^49 microseconds, or about 18 years! Still exponential, and still a really long time.

Computational problems where the best known algorithms scale exponentially are called intractable by computer scientists. What this means is that for big problems of this type, the problem can’t be solved no matter how “fast” or “parallel” a conventional computer is.

This is actually a very cool concept - that there exist computational problems that might not be solvable, even if we could use all of the computational resources of the universe.

Hi everybody,

Today I am going to provide some background information on the stuff we make our processors out of. As you’re probably aware, conventional processors, like Athlons and Pentiums, contain a lot of silicon. Maybe you have wondered why this is. Why silicon and not beryllium? Or lead?

There are many good reasons. One of them is that it is particularly easy to make a very important device, the transistor, using silicon. In fact even though Bell Labs invented the transistor, it was Texas Instruments who first commercialized it, mainly because they figured out how to switch from the Bell Labs style germanium version to a nice, simple and cheap silicon version.

The silicon based transistor worked so well that it, and its descendants, have been the workhorse of nearly every processor used from the very beginning of microprocessors through to today.

I say nearly because there is a different way to build processors (using metals) that has been lurking in the background for about 20 years, showing a lot of promise, but never taken up by any of the major processor companies as the basis for a product line (TRW’s efforts notwithstanding).

These metal-based processors are quite unusual. One thing about them is that in order for them to operate, they need to be cooled to nearly absolute zero using special refrigerators. At these very low temperatures the metals that form the processor’s circuits become what are called superconductors. Whenever anyone says “superconductor” just think “really cold metal”.

Why go to the trouble of doing something like this? Historically arguments for metal-based processors have been that (1) since they’re made out of superconductors, they generate much less heat than conventional processors (true); (2) for some technical reasons you can operate at clock speeds up to about 100 GHz without alot of problems (true); so if you want a really fast, really low power processor, here’s a way to do it.

History says though that these benefits by themselves just aren’t enough to even TRY to commercialize this type of metal-based processor, especially given the temperature constraints (which probably limits applicability to “capability class supercomputer” type stuff). Just too much risk for not enough reward.

BUT what if there was a way to use the “really low power & really fast” benefits to gain some other really valuable advantage?

What D-Wave has done is begun with the standard approaches to building metal-based processors and modified them in such a way that these processors use quantum mechanics in order to accelerate computation.

When you look at one of our processors with your naked eye, what you see is a fine mesh of metal circuitry (the metal is niobium) on a 5 square millimeter chip. This metal circuitry is the top metal layer in a multi-layer metal/insulator/metal/repeat many times/ sandwich. This top metal layer contains things like contact pads for connecting the chip to wires that carry information to and from the processor.

Here is a picture of one of our processors in a test system, to give an idea of what it looks like. The chip in the middle is 5 square mm in size.

Cool eh.

So why are we using these metal-based processors as the basis for our approach to building quantum computers? There’s one underlying fundamental reason: we know how to build really big things using superconducting metals that behave quantum mechanically.

Superconductors are the only type of material that we know of where big lithographically defined devices (like really big. Like centimeter on a side big.) can be built that behave just like they were atomic-sized. The reason for this behavior is highly technical - is has to do with the types of particles in the material. In a superconductor all of the “particles” that carry charge around can exist in the exact same state, so when you look at a whole lot of these particles (many trillions) it can be just like looking at only one (which is “very quantum mechanical”).

This property allows us to build circuits out of superconductors that, if we are really smart and really careful, can be made to act like “circuits of atoms”. We can use the fact that really big things (which we can easily build today using conventional fabrication techniques) can be made to behave like really small things to try to build real quantum computing architectures.

Ultimately what I’d like to do is show you guys what a quantum computer processor really looks like. A lot of this material would be confusing if I just dumped it without context, even for experts, so I’m going to try to provide some perspective and background for some of the things I’ll be showing you later on about our machines. I’ll start by introducing the basic idea behind the whole field of quantum computation.

This basic idea is really pretty simple. But it’s still pretty deep. This basic idea is that

Information always has to be written on something.

Often it’s convenient to forget this basic fact and to view information as something abstract - a collection of ones and zeroes that lives in the ether somewhere. But no matter how hard you try to imagine otherwise, those ones and zeroes ultimately reside as physical states of something - marks of graphite on paper, directions of magnets in a hard drive, assemblies of chemicals in your brain, etc.

This basic idea has a big consequence: if information is always written on something, then that information has to behave according to the laws of physics of the stuff it’s written on. For example, if I write some words on a piece of paper, and that paper could travel back in time, then I could send information back in time. If the laws of physics say I can’t send pieces of paper back in time, then I can’t send that information back in time either (by the way, I don’t know if the laws of physics allows this or not, closed timelike curves notwithstanding).

This is relevant how? Well, computers have always stored information on devices that to a good approximation obey the laws of classical physics. This means that all that information has always had to behave according to those same laws. Conventional computer science implicitly assumes this, and up until recently all of the results, theorems, algorithms, etc. of computer science were based on the assumption that the machine embodying all of the information, and the calculations done using it, were entirely classical.

Nowadays we can build things that obey different laws of physics - namely those of quantum mechanics, which are generally more likely to be required to describe things that are small and cold. Quantum mechanics is a framework within which we can describe the properties and behavior of (probably) all matter and energy, and is conceptually quite different than conventional physics.

When scientists store information in quantum mechanical devices in the lab, what is seen is that this information does, in fact, obey the laws of quantum physics. In theory, what this means is that a large part of computer science, developed over the past century or so, needs to be examined in order to find out what difference it makes to computation if information is stored in a quantum system as opposed to a classical one.

This re-examination of computer science, for quantum computers, is still in its early days. There are already several algorithms developed for quantum computers that vastly outperform their classical counterparts, but the story is by no means complete.

Another way of putting the basic idea that “information is physical” is this:

What can be computed depends only on the laws of physics obeyed by the machine running the computation.

I’m Geordie Rose. Back in 1999 I founded a company in Vancouver, BC called D-Wave, not to be confused with Swedish techno act D-Wave. We’re building a new kind of computer, called a quantum computer. There are quite a few good introductions to quantum computers; try Julian Brown’s or George Johnson’s books. They have also made appearances in a bunch of bestsellers, including The Footprints of God, Timeline, The Labyrinth Key, Digital Fortress, and many others. These machines have been the subject of conjecture and speculation for some time now, but no one has been able to build one yet that does anything useful. D-Wave is trying to change this.

I started this blog because I would like to provide my perspective, as the CTO of a company attempting to commercialize quantum computers, on how and when these machines will become useful to people struggling to solve hard problems with conventional (ie non-quantum) software and hardware.

In the process I may from time to time comment on stuff I see being said in the media or in academia if it’s stupid. I have a few examples lined up.