The First Quantum Computer

In a nondescript office park outside Vancouver with views of snow capped mountains in the distance is a mirrored business park where very special work is being done. The company is D-Wave, the quantum computing company. D-Wave's mission is to build a computer which will solve humanity's grandest challenges.

D-Wave aims to develop the first quantum computer in the world, perhaps they already have. The advent of quantum computers would be a sea change in the world that would allow for breaking of cryptography, better artificial intelligence, and exponential increases in computing speed for certain applications. The idea for quantum computers has been bubbling since Richard Feynman first proposed that the best way to simulate quantum phenomena would be with quantum systems themselves, but it has been exceedingly difficult to engineer a computer than can manipulate the possibilities of quantum information processing. Hardly a decade ago D-Wave began with a misstep which is the origin of their name. D-Wave got its name from their first idea which would have used yttrium barium copper oxide (YBCO) which is a charcoal looking material with a superconducting temperature above that of the boiling point of liquid nitrogen. This means that YBCO is the standard science lab demonstration of superconducting magnetic levitation. Ultimately the crystalline structure of YBCO was found to be an imperfect material, but the cloverleaf d-wave atomic orbital that lends YBCO its superconducting properties stuck as D-Wave's name. The vision of D-Wave did not change, but their approach did. They realized they would have to engineer and build the majority of the technology necessary to create a quantum computer themselves. They even built built their own superconducting electronics foundry to perform the electron beam lithography and metallic thin film evaporation processes necessary to create the qubit microchips at the heart of their machine.

I recently got to visit D-Wave, the factory of quantum dreams, for myself. The business park that D-Wave is in is so nondescript that we drove right by it at first. I was expecting lasers and other blinking lights, but instead our University of Washington rented van pulled into the wrong parking lot which we narrowly reversed out of. In the van were several other quantum aficionados, students, and professors, mostly from computer science who were curious at what a quantum computer actually looks like. I am going to cut the suspense and tell you now that a quantum computer looks like a really big black refrigerator or maybe a small room. The chip at the heart of the room is cooled to a few milikelvin, colder than interstellar space, and that is where superconducting circuits count electric quantum sheep. The tour began with us milling around a conference room and our guide, a young scientist and engineer, was holding in his hand a wafer which held hundreds of quantum processors. I took a picture and after I left that conference room they did not let me take any more pictures.

Entering the laboratory it suddenly dawned on me that this wasn't just a place for quantum dreams it was real and observable. The entire notion of a quantum computer was more tangible. A quantum computer is a machine which uses quantum properties like entanglement to perform computations on data.The biggest similarity between a quantum computer and a regular computer is that they both perform algorithms to manipulate data. The data, or bits, of a quantum computer are known as qubits. A qubit is not limited to the values of 0 or 1 as in a classical computer but can be in a superposition of these states simultaneously. Sometimes a quantum computer doesn't even give you the same answer to the exact same question. Weird. The best way to conceive of a quantum computing may be to imagine a computation where each possible output of the problem has either positive or negative probability amplitudes (a strange quantum idea there) and when the amplitudes for wrong answers cancel to zero and right answers are reinforced.

The power of quantum computers is nicely understood within the theoretical framework of computational complexity theory. Say for example that I give you the number 4.60941636 × 10¹⁸ and ask for the prime factors of this number. Now if someone were to give you the prime factors you could verify them as correct very quickly, but what if I asked you to generate the prime factors for me (I dare you. I have the answer. I challenge you. In actually this challenge is easy. Nine digit number aren't that hard to factor, a friend says they found a webpage that will do it. But the problem doesn't scale well to larger numbers). The quintessential problem here is the P versus NP question which asks whether if a problem can be verified quickly can it also be solved quickly. Quickly is defined as polynomial time meaning that the algorithm scales as the number of some inputs to some power. Computational complexity theory basically attempts to categorize different kinds of problems depending on how fast a solution can be found as the size of the problem grows. A P class problem is one in which the solution can be found within polynomial time. A NP class problem is one in which the solution can be verified in polynomial time. So if I ask you for the prime factors of my number above that is an NP problem because given the numbers you could verify the answer quickly, but it would be very difficult to calculate the numbers just given the number. It is an open question, but it appears likely that all P problems are a subset of NP. This means that problems verifiable in polynomial time are not necessarily solved in polynomial time. The issue is that for some very interesting problems in the real world we could verify the answer if we stumbled upon it, but we won't even be able stumble upon the answer in a time shorter than the age of the universe with current computers and algorithms. What we know we know and what we think we know is a sea of confusion, but the popular opinion and where people would take their wagers is that P is not equal to NP.

Suddenly, with mystique and spooky actions at a distance, quantum computing comes swooping in and claims to be able to solve some NP problems and all P problems very quickly. A general quantum computer would belong to the complexity class of BQP. There is a grand question at hand, is BQP in NP? (More generally, is BQP contained anywhere in the polynomial hierarchy? The polynomial hierarchy is a complexity class which generalizes P and NP problems to a particular kind of perfect abstract computer with the ability to solve decision problems in a single step. See this paper here on BQP and the Polynomial Hierarchy by Scott Aaronson who is a outspoken critic of D-Wave) At this time we cannot even claim to have evidence that BQP is not part of NP, but most scientists close to the problem think that BQP is not a subset of NP. Quantum computing researchers are trying to get better evidence that quantum computers cannot solve NP-complete problems in polynomial time (if NP was a subset of BQP then the polynomial hierarchy collapses). A reasonable wager I would take is that P is a (proper) subset of BQP and BQP is itself is a (proper) subset of NP. This claim has not been rigorously proved but it is suspected to be true and further there are some NP problems which it has been shown to be true for such as prime factorization and some combinatoric problems.

There might be an elephant in the room here. The D-Wave architecture is almost certainly attacking a NP complete problem and reasonable logic says that quantum computers will solve P problems and some NP problems, but not NP complete problems (this is also not proven, but suspected). An NP complete problem is a problem in which the time it takes to compute the answer may reach into millions or billions of years even for moderately large versions of the problem. Thus we don't know if this particular quantum computer D-Wave has built even allows us to do anything efficiently we couldn't already do on a classical computer efficiently; it doesn't seem to be a BQP class computer thus it cannot for example solve prime factorization cryptography problems. So, yes it is a quantum machine, but we don't have any evidence it is an interesting machine. At the same time we don't have any evidence it is an uninteresting machine. It is not general purpose enough to be clear it is a big deal, nor is it so trivial it is totally uninteresting.

The D-Wave lab was bigger than I expected and it was at once more cluttered and more precise than I thought it would be. It turns out the entire process of quantum computing follows this trend. There are a lot of factors they contend with and on the tour I saw people dead focused with their eyes on a microscope executing precise wiring, coders working in pairs, theoreticians gesturing at a chaotic white board, and even automated processes being carried on by computers with appropriately looking futuristic displays. The engineering problems D-Wave faces include circuit design, fabrication, cryogenics, magnetic shielding and so on. There is too much to discuss here so I will focus on what I think are scientifically the two most interesting parts of the D-Wave quantum computer which are the qubit physics and the quantum algorithm which they implement; in fact these two parts of their computer are deeply intertwined.

In the image above is a wafer of Rainer core superconducting microchips. The chips are built to exacting specifications and placed at the center of the D-Wave quantum computer in isolation from external noise such as magnetic fields and heat. In the quantum world heat is noise so the chips are kept at a temperature of a few milikelvin to preserve the quantum properties of the system. On each chip are 128 superconducting flux qubits. The qubit is the quantum of information with which this computer works. There are various ways to create a qubit such as quantum dots, photons, electrons, and so on, but D-Wave has gone with the flux qubit design for engineering concerns.

A flux qubit is a micrometer size loop of conducting material (in this case Niobium) wherein a current either circulates the loop clockwise or counterclockwise in a quantized manner such that the loop is either in a spin up (that is +1 or ↑) or a spin down (that is -1 or ↓)  state. There is an energy potential barrier between the loop spontaneous flipping spin (or current circulation direction) which can be modulated through various control schemes. They control these loops using compound Josephson junctions and SQUIDs using their own propriety techniques, but borrowing heavily on decades of advancement in solid state physics.

Perhaps even more important than the qubit itself is the architecture and the algorithm implemented by the computer. They use a quantum adiabatic algorithm based on the Ising model. When I realized that their algorithm was based on the Ising model I couldn't help but marvel at the powerful simplicity. The Ising model is a statistical mechanics model of ferromagnetism where the atoms (vertices or variables) in a metal (crystal lattice or graph) are discrete variables with spin values that take on spin up or spin down values and each spin interacts with its nearest neighbors. It is a simple model that leads to beautiful complexity (for example see this article on the Ising model here) especially when you allow the interaction of each spin with its neighbor to be finely controlled or when you allow the connectivity of the vertices to be varied. The Ising model is easily extended to more abstract problems. For example we can connect every single vertex to every other vertex, it wouldn't look like a crystalline structure any more, but it makes sense on paper or with wires on a chip.

The quantum adiabatic algorithm borrows ideas from physics such as the process of annealing and spin states in the Ising model to solve a generalized optimization problem. During my tour of D-Wave we continued to talk about the algorithm and what was possible and the whole concept slowly crystallized for me, but it is not immediately obvious why they designed the computer they way they did because their implementation would not create a universal quantum computer. Why the quantum adiabatic algorithm?

• Quantum annealing is physically motivated method for a quantum computers which is not thwarted by thermodynamics or decoherence.
• Real world optimization problems can be modeled using the Ising spin glass. The hardware mirrors this.
• More complicated architectures will borrow from the quantum annealing approach such as a universal adiabatic quantum computer.

D-Wave has not created a general purpose quantum computer. They have created a quantum computer which solves the adiabatic quantum algorithm or equivalently an optimization problem. They use quantum annealing to solve the global minimum of a given objective function with the form of... Wait, wait, let me have a kitten tell you instead (math warning next to paragraphs):

Here E is the value to be minimized over the total system state s subject to the constraint of J_ij (where J_ij <1) acting between each element s_i and s_j (where all s=+/-1). Each element s is weighted by the value h_i (where h_i >-1). The nearest neighbor spins of each ij pair is calculated according to the connections between vertices in a physics application or depending on the microchips graph architecture of actual physical connections on the D-Wave chip. ) The coupling between ij is determined by J_ij so this means that J represents your knowledge of how each component of the system interacts with its neighbors. Immediately we extend the above minimization parameterization to the physical implementation of quantum flux qubits.

In this new form the optimization problem is written as a Hamiltonian which determines the interaction and evolution of the system. The variables are modified, s_j →σ_z ⁱ and  s_i →σ_z ⁱ where σ_i ^z are are Pauli matrices at site i for a spin 1/2 qubit. Then h_i is the transverse field that represents transitions up and down between the two spin states ↑ and ↓, of each spin. Here K_ij is the weighting that defines the interaction between the qubits. The problem is to anneal the system as closely as possible to its classical ground state with the desired K_ij.


The D-Wave computer solves the the quantum adiabatic algorithm by initializing the spins of the flux qubits in their ground state with a simple Hamiltonian. Initially the potential well for the spin of qubits is U shaped; the ground state of the of the qubits when they are configured in this mode is a superposition of the |↑> and and |↓> flux basis. Then the qubits are adiabatically, or slowly, evolved to the specific Hamiltonian which encodes the optimization problem that is to be solved; the potential is evolved to the double-welled configuration at which point the ↑> and and |↓> states start to become the dominant basis. Actually, the final configuration is not exactly a double-welled symmetric state, but it has some relative energy difference between the to states which biases the machine towards the encoded problem. Evolving the Hamiltonian can be thought of as modifying the energy barrier between the spin up and down states for each flux qubit. In a real system each potential well has multiple energy levels possible in it besides the lowest energy state which is where the ideal calculation is performed. According to the adiabatic theorem the system remains in the ground state so that at the end the state of the system describes the solution to the problem. However, in a real machine noise, such as the ambient local heat, can still  disturb the system out of the ground state. A key advantage to the D-Wave approach is robustness to noise in many situations. The slower the Hamiltonian is evolved, the more the process adheres to the ideal adiabatic theoretical calculation. Performing the calculation more slowly decreases the chance of jumping out of the ground state. Adding more qubits makes the energy gap at the tipping point smaller. Thus engineering is a machine with more qubits is hard. Interestingly, because quantum machines have statistical uncertainties each computation will have uncertainties which can be reduced by either running each calculation slower (and we are talking a few microseconds here) or by running the same calculation many times and seeing what different answers come up. As it turns out it is usually faster to run the calculation many times and compare answers than run one long calculation.

The theoretical minimization problem that is solved is best understood separately from what the actual quantum qubits are doing. Over at the D-Wave blog, Hacking the Mulitiverse, they liken the optimization problem to finding the best setting for a bunch of light switches that have various weightings. Each light switch can be either on or off and can have an either positive or negative weighting, the h_i term above, and it can have a dependency on any other switch in the system determined by the J_ij term. It turns out to a be a really hard problem as for just 100 switches there would be 2¹⁰⁰ possible ways to arrange the switches.

Traditionally the first program a coder writes in a new language is a simple print statement which says Hello world. On a quantum computer the first program you write says Hello multiverse! You could write this program on a D-Wave. Yes, you really can because you can go out any buy one. Lockheed Martin bought one earlier this year for ten million dollars. The detractors to D-Wave would say you are not getting a real quantum computer,  but then why did Lockheed Martin buy one? It is legitimate to ask, is D-Wave if the first true quantum computer? This of course depends on your definition of a quantum computer. The answer is probably no if you want a universal quantum computer (which belonged to the BQP complexity class discussed earlier). Probably no here means that reasonable computer scientists studying quantum computers have excellent reason to believe the answer is no but they lack rigorous mathematical proof. On the other hand if you are looking for a computer which exploits quantum effects to implement a specific purpose quantum algorithm then I think you can safely say, yes, this is a quantum computer. I am just a naive astronomer though so don't take my word for it. So let me clarify and say that just because a computer exploits quantum mechanics does not make it a quantum computer. All microchips today are small enough that the designers know something about quantum mechanics, maybe they even have to account for it in the chip's design, but crucially the compilers and the code that is written for the machine has no knowledge of the quantum mechanics. The algorithms run on the machine assume nothing about quantum mechanics in our universe. However, a real quantum computer would obviously be programmed according to the rules of quantum mechanics. Indeed the the D-Wave computer is executing an algorithm which explicitly takes into account quantum mechanics. Further, whether or not the D-Wave computer is actually a quantum computer that will satisfy computer scientist's definition is a mute point compared to asking if it is useful. Currently D-Wave is running experiments that show that the speed scaling of their machine as a function of inputs is, hopefully, better than classical computers and algorithms. In the future they will have to show with double blind experiments that their machine scales better than classical machines. If they can execute calculations in a few microseconds which take classic computers decades I don't care if you call it the one true quantum computer or an oracle, I will just want one.


References


Harris, R., Johansson, J., Berkley, A., Johnson, M., Lanting, T., Han, S., Bunyk, P., Ladizinsky, E., Oh, T., Perminov, I., Tolkacheva, E., Uchaikin, S., Chapple, E., Enderud, C., Rich, C., Thom, M., Wang, J., Wilson, B., & Rose, G. (2010). Experimental demonstration of a robust and scalable flux qubit Physical Review B, 81 (13) DOI: 10.1103/PhysRevB.81.134510

Harris, R., Johnson, M., Han, S., Berkley, A., Johansson, J., Bunyk, P., Ladizinsky, E., Govorkov, S., Thom, M., Uchaikin, S., Bumble, B., Fung, A., Kaul, A., Kleinsasser, A., Amin, M., & Averin, D. (2008). Probing Noise in Flux Qubits via Macroscopic Resonant Tunneling Physical Review Letters, 101 (11) DOI: 10.1103/PhysRevLett.101.117003

Gödel's Proof

There is an idea of reason in the Universe. It is an abstraction which mathematicians have never been content with. Given that scientists exclusively use logic (or mathematical reasoning) for theories and experiments it is of incredible importance to know the limits of logic. It turns out that the study of math itself, metamathematics, has amazing insights on what is knowable.

In 1931 an unassuming paper was published in a German mathematics journal, the title of the paper (translated to English) was 'On Formally Undecidable Propositions of Principia Mathematica and Related Systems I'. It is a confusing title and the kind of paper which I would not understand. The author was a 26 year old Austrian named Kurt Gödel and he had just created a revolutionary idea, but as with so many great ideas it was not simple and it took great minds to fully appreciate it.

The ideas he put forth have been extremely influential and the collective name for the theories that grew from it are known as Gödel's incompleteness theorem. This theorem is a revolutionary outcome in mathematical logical that has implications for not only the philosophy of mathematics, but philosophy in general. It is thus surprising how relatively unknown the theorem is to the general public and even many scientists. I recently read the book Gödel's Proof by Nagel and Newman in just a few sittings at a coffee shop. It is a short and concise explanation of the proof that incrementally brought me closer to understanding the intricacies of Gödel's works.

Gödel's incompleteness theorem is a massive mountain of ideas that I will not attempt to conquer, but I think it is important that everyone at least gets a view. Gödel basically found that no solid guarantee is possible that mathematics is entirely free of internal contradiction. However, Gödel was not out to trash mathematics, contrarily he used mathematics itself to temper the reach of mathematics and place constraints on what is possible to known through mathematics much like a physicist theorizing that a black hole's event horizon places a limit on spaces which the physicist could actually go and measure. Gödel created a new technique of analysis and introduced new probes for logical and mathematical investigation.

The specifics of Gödel's proof even as outlined on wikipedia are extremely complicated (the entire proof is long and there are on the order of 200 links in the article so by the time you were done reading all of the prerequisite mathematical definitions you would have read thousands of pages) for anyone without (or with) extensive mathematical training, so I must admit that I don't understand it completely and not have I attempted to read the actual paper. I want to present here the shortest definition of Gödel's theorem not the the most rigorous.

The key to Gödel's incompleteness theorem is a concept of mapping. In the information age the concept of mapping or coding is familiar to many as in the case of mapping Morse code dots to letter characters. In the explanation that follows take it as a given that it can be shown that all logic systems are equivalent to or mappable to the operators we will be using; this assumption is vital, and I can't quite explain it without detail so I refer the inquisitive mind to read Nagel and Newman's book.

Let us construct a simple logic system using the arbitrary operators P, N, ⊃, and x that have certain properties which we take as given by the table defined below. In the left column a combination of operators is given and in the right column a definition in English of the operators meaning is given.

P⊃x	'print x'
NP⊃x	'never print x'
PP ⊃x	'print xx'
NPP⊃x	'never print xx'

We can combine these statements and create more complicated statements. For example P⊃y where y=P⊃x would mean 'print P⊃x' (note that implicitly I am also using the equals operator). Crucially then NPP⊃x would mean 'never print xx', and this statement could also be written NP⊃xx.

Next ponder what the last statement used on itself means. The statement NPP⊃y where y=NPP⊃ would mean 'never print NPP⊃NPP⊃', but this strange statement could also be written NPP⊃NPP⊃.

So either our system prints NPP⊃NPP⊃ or it never prints NPP⊃NPP⊃. It must do one or the other. If our system prints NPP⊃NPP⊃ then it has printed a false statement because the statement contradicts itself by self reference once it is printed. On the other hand if the system never prints NPP⊃NPP⊃ then we know that there is at least one true statement our system never prints.

So either there are logic statements which may be printed which are false statements, or there are true statements which are never printed. Our system must print some false statements if it is to print all true statements. Or our system will print only true statements, but it will fail to print some true statements.

In the example above I have taken arguments very similar to that in Raymond Smullyan's book Gödels Incompleteness Theorems in order to create an extremely concise, but hopefully accurate description of what lies at the core of Gödel's insight. In Nagel and Newman's book they explain Gödel's proof in much more detail by working out the details of mapping. For example in the explanation above I mapped mathematical statements to the idea of printing, but print could be equivalently be existence. Further, Nagel and Newman argue as Gödel did that all formal axiometric systems can be mapped in some way such that even the most complicated mathematical systems using the common operators of +,-,=, x,0,(,),⊃ and so on can be shown to be incomplete.

Gödel's incompleteness theorem has many forms and implications. Briefly I will demonstrate an analogous, but weaker form of Gödel's incompleteness theorem by analogy to the halting problem. I believe this demonstration is of importance to those of us immersed in the information age and perhaps easier to grasp or at least more applicable than Gödel's work.

The halting problem is to decide whether given a computer program and some input, whether the program will ever stop or will it continue computing infinitely. The key to the halting problem is the concept of computation and algorithms. In the original proof by the enduring Alan Turing specific meanings to the concepts of algorithm and computation were defined. He used a computational machine now known as a Turing complete computer, or a Turing machine. The definition of what constitutes a computer is to the halting problem what the mapping of symbols is to Gödel's theorem. It is at the heart of the problem, and thus actually one of the harder points to define so I will again leave that task as an exercise to the reader.

So lets look at two psuedocode programs and lets imagine that we also have a very special program written by a genius scientist which is called Halting. The scientist claims that Halting can correctly tell your own code B(P,i) whether a program halts.

Program B(P,i)
  if Halting(P,i)==true then
    return true // the program halts
  else
    return false // the program does not halt


Now here is the important part. The genius scientist claims we can analyze any kind of computer program, this is indeed the crux of the halting program, we want to know if any and every program stops. Now imagine a program E that takes X, which is any program, as an argument.

Program E(X)
  if B(X,X)==true then
    while(true) //loops forever
  else
   return true


The first thing E does is take B and passes it X for both arguments. Program E will get back from B either true or false. If it receives back true it will enter an infinite loop and if it receives back false it will terminate.

So suppose I take B and feed it E for both arguments. What answer will B(E,E) give? Think about it.

We will be running our special Halting program on E(E) which will then run the program B(E,E). The answer to B(E,E) will either be either true or false. If the result is false the program E actually returns true and halts immediately; if the result is true then Halting thinks our program does halt, but the program E throws itself into a loop upon this condition and will never halt. Either way program E lies. E was written very craftily to break B on purpose, but nonetheless the damage is done. E cannot be made reliable even in principle. It matters not how clever you are and or how powerful your computer is. There is simply no reliable computer program that can determine whether another program halts on an arbitrary input. The incompleteness problem may have seemed a little bit distant and philosophical, but if you have read this far it should be evident that the halting problem has deep implications computing.

What does Gödel's theorem mean for the real word, experimental verification, and deductive sciences? Well take for example the Banach-Tarski paradox which states that a solid ball in three dimensional space can be split into a finite number of non-overlapping pieces, and then be put back together in a different way to yield two identical copies of the original ball. This process violates sensible physic notions of conservation of volume and area. It turns out that Banach and Tarski came to this conclusion based upon deductions from the Axiom of choice. Now, whether we know anything at all about the axiom of choice we do know that the deductive conclusions drawn from it are in violation of physics. Thus, a physicist could argue that the axiom of choice is not a valid axiom for our Universe. Within mathematics it is unknown, unprovable Gödel says, whether or not we should accept the axiom of choice, because it is after all an axiom. The argument for whether a given axiom is to be accepted must be discussed outside the confines of the logic structure one is arguing about. It turns out that the axiom of choice is important for many other really important mathematical proofs which are used in physics all the time. I don't know what to make of it really, perhaps a mathematician out their should weigh in on this question.

Another important theorem that goes along with Gödel's theorem is Tarski's undefinability theorem. Tarski's undefinabtliy theorem makes a more direct assertion about language and self referential systems. Basically any language sufficiently powerful to be expressively satisfying is limited. In summation we have two vital points to the concept of incompleteness.

1.  If a system is consistent, it cannot be complete and is limited.
2. The consistency of the assumptions or axioms cannot be proven entirely within the system.

The repercussions of the meta analysis of logic are profound and subtle. Gödel really has thrown us for a loop. It is unclear if we should draw the line and say this is just a mere curiosity of mathematics or a deep truth about the Universe. It has been proposed by Douglas Hofstadter (author of Gödel, Escher, Bach) that consciousness itself comes from a kind of 'strange loop' induced by a self referential system in our minds. Primarily, I think we can conclude that Gödel's incompleteness theorem implies that in most situations the tools science has to analyze the world are more than adequate because the situations are not self referential. However, I do see a limit to what we can know about the Universe. As physicists forge forward, generally quite successfully, in understanding the Universe it appears that there really is some consistent mathematical basis for our Universe. Many physicists are searching for this mathematical basis to the Universe, it is the so called theory of everything. But does Gödel's result imply that this mathematical basis cannot be self consistent?

Consider this scenario. One day our most powerful, successful, and comprehensive theory ever will predict something that experiment cannot verify or worse an experiment will patently disagree with. Some will argue that the theory must be thrown out because classically the scientific method states that a theory disagreeing with experiment, or making nonsense predictions, is untenable. Another theory will be introduced that makes consistent and testable predictions, however this theory is not able to predict the most intricate traces of nature. Actually, that first case kind of sounds like string theory. Perhaps we will have to start talking about theories being incomplete instead of wrong one day.

Man vs. Machine: Computable Knowledge and Language Processing

Computers have come a long way since Charles Babbage's time. Babbage was the inventor of the concept of the programmable computer. He designed and attempted to build several machines including the Analytical Engine which was a programmable mechanical computer. It would have been the first Turing-complete (roughly implying it can simulate any other computer or proper program) machine ever. People at the time were confused by the entire concept of a computer.

"Mr. Babbage, if you put into the machine wrong figures, will the right answers come out?" I am not able rightly to apprehend the kind of confusion of ideas that could provoke such a question.

People thought that if a computer could do calculations it must be smart in the same way a person is smart, that is make deductions, inferences, and synthesize information to make conclusions. In the 1960's computers showed great promise and some researchers thought the age of truly intelligent machines was just a few years away. It turned out that the human mind is formidable opponent. Machines which think exactly like humans may not ever exist, but machines that 'think' are already here.

The final question, "William Wilkenson’s 'An Account of the Principalities of Wallachia and Moldavia' inspired this author's most famous novel." All contestants got the question right, but Jenning's knew he was not catching up.

Humans and machines were doing a lot of thinking this week when humans faced off against computers in a three day exhibition Jeopardy! match. The computer in the match was called Watson which was able to defeat Ken Jennings, the winngest ever Jeopardy player, and Brian Rutter, the all-time Jeopardy money winner. Watson is a purpose built technology demonstrating computer built by IBM which uses language processing and machine learning to play Jeopardy. A very good documentary produced by NOVA is available online which discuss the research and development that went into Watson, The Smartest Machine on Earth, which is a good watch even if you have been following the news on Watson. In the three day match things began slowly as Watson held is own, but occasionally stumbled. However, in the end Watson was light years ahead. Here is the recap:

This isn't the first time a human vs. machine battle has been played. In 1997 a highly publicized battle occurred between world chess champion Gary Kasparov and IBM's Deep Blue. Kasparov fell hard in the battle and even accused IBM of cheating. In retrospect his protests were in compete futility, as is proven by the fact that in 2006 world chess champion Vladimir Kramnik was beaten by a computer, Deep Fritz, running on a standard personal computer (running two Intel Core 2 Duo). Chess playing computers are not too 'smart'; they basically use their computing power to play out likely board configurations and so the techniques employed by chess playing programs have been excluded from some definitions of artificial intelligence. And of course maybe Watson isn't that smart either you could say. Watson uses knowledge humans have gathered, finds patterns, finds the relative strength of each answer, and returns the answer. It is hard to exactly define what intelligence is so I won't even try. Instead I will make two observations about the implications of machines besting humans. First, what takes a super computer at one point, will take a microchip in the future as indicated by the evolution of chess playing computers. Second, while the argument about what intelligence is goes on the pace and ability of computers also goes on.

How does Watson think? Watson uses machine learning. Basically Watson is fed a bunch of text documents like Wikipedia and IMDB (note that Watson was not online during the Jeopardy competition, but had access to these documents pre archived). Then programmers feed Watson questions and correct answer pairs which Watson can use to look through its database to find patterns. A complex architecture of rules and statistics allow Watson to choose the right answer, but amazingly programmers on the project don't explicitly tell Watson how or what the right answer is. Modern computer programs are big and complicated so it is best to let the computer take care of writing their own programs.

Watson's success means there is a bright future for language processing computers (at least IBM wants us to think so and buy their products). I have been contemplating the merger of Wolfram|Alpha and IBM's Watson as the ultimate language processing computational engine. Alpha if you have never used it is a live web program that anyone can use. The creator, Stephen Wolfram, calls Alpha a computational knowledge engine. This means that Alpha doesn't parse language in the most human receptive manner, but it has powerful database and computational algorithm resources such that if you want to know the error function of the GDP of Italy divided by the GDP of the US all divided by the 144th prime, well you can do that. Also, Alpha can do math, and how. IBM's Watson on the other hand could tell you the name of the country with its boot dipped in the Mediterranean. These smart computers are different for obvious reasons, they have access to different information databases and they are programed differently. An explanation of the difference recently came up on Stephen Wolfram's blog in pictorial form.

It would be a powerful combination to have Alpha's database and analytical skills paired with Watson's language processing. Perhaps we will have a Watson|Alpha soon. I remarked to a colleague in jest the other day that if they made such a machine I would be out of a job, but he replied that I would still have job as long as computers only have answers and not questions. True enough. I am reminded of the Hitchhikers Guide to the Galaxy where an immense computer calculates the answer to the universe, however, with the answer in hand it is realized a bigger more powerful computer must be constructed to determine the question.

A man of Seville

A man of Seville is shaved by the Barber of Seville if and only if the man does not shave himself. Does the barber shave himself?

Image from LOGICOMIX by Apostolos Doxiadis.