Quantum computing so close or so far?

Quantum computing so close or so far? The following promotional video is quite optimistic, but it does a decent job of explaining the most basic workings and potential of quantum computing so I thought I would share. For a more in depth perspective on the physics and prospects for quantum computers see my post about my visit to D-wave and their attempts to build the first quantum computer.

Fusion for the Future: ITER

The way of the future is fusion. I dream of a world where humans have harnessed the power of the Sun. Clean, safe, energy. But there is no clear path to fusion. The most exciting possibility for a future with fusion may be the International Thermonuclear Experimental Reactor or ITER. ITER is not the only option of course. Previously, I have discussed the National Ignition Facility or NIF which has pioneered unique technologies is the field, but their success is not ensured. Many small research projects around the world are also struggling to realize the dream of fusion, but with budget shortfalls and increasing pressure to produce results we as a society may shortsightedly end the dreams of a fusion future.

Fusion is what powers the Sun and all stars in our Universe. Fusion is the joining of two or more separate atomic nuclei into a larger nuclei. Fusion can create energy because the mass of the input and output nuclei are not necessarily equal in mass. An overview of what fusion is and why it is so important can be seen on my previous post on Fusion for the Future. Many scientists in the field acknowledge that a rapid development of fusion is unlikely, much less a commercial development, but there is hope. A reasonable time frame may be half a century before we see a world powered by the same process which drives the Sun. It will be an almost entirely clean, limitless, reliable, and safe source of power.

Christopher Llewellyn Smith states some cold hard numbers that are worth mentioning again. The price of ITER is at least 13 billion Euros or $17 billion. This cost is justified and dwarfed by the magnitude of the energy usage on Earth which amounts to a $5 trillion dollar a year market (I checked some of these numbers and they seem approximately correct. Did you know that you can download the International Energy Agency's annual reports as an iPhone or iPad app?). Particularly shocking are the subsides to fossil fuels which are over $500 billion a year worldwide (I am not so sure about this number, but the United States alone subsides fossil fules to the tune of $10 billion a year) while the subsides to renewables are only $45 billion worldwide. Smith says that the renewable energy sources of wind, bio, geothermal, and marine will never be able to meet the world's energy needs a current consumption rates. We must use solar, fission, or fusion energy.

It is a curious thing to ask a scientist to speculate on the future, but these two scientists have indulged us with a time frame for achieving fusion. Maybe the middle of this century at best they say. What makes fusion so difficult?

The key to releasing the energy of the Sun is forcing the nuclei of atoms close enough together for them to overcome their electrical repulsion and allow the strong force which binds nuclei to merge the nuclei together. Such favorable conditions for atoms to smash into each other can only occur under extreme temperatures and pressures, like say at the center of a star, but it is almost impossible to hold a star on earth. Anything which is hot enough to undergo fusion is also hot enough to burn through any container, thus we must contain something without quite touching it. Enter the magnetic doughnut known as the tokamak. A tokamak is a toroidal or doughnut shaped container that uses magnetic fields to confine plasma. Plasma is a state of matter where all the atoms are ionized (the electrons that normally orbit the protons in the nucleus have escaped)—and at these temperatures the atoms contained in the tokamak are definitely ionized. Magnetic fields apply a force on the charged particles of plasma such that the plasma can be corralled and kept away from the walls of the container. In an actual tokamak huge magnets encircle the enclosure as shown in the figure here where the magnetic coils and the ITER plasma surface is shown. The colors and contour lines indicate the magnetic field strength which is not quite perfect, the lines are wavy, due to deviations from perfect symmetry in the structure because the tordioal magnetic field is made of a finite number of magnetic coils. The ITER tokamak will be huge. Check out the tiny little person (bottom left) in the image below.

The complexity of this machine is astounding. One key challenge that must be overcome is the confinement of the plasma in a controlled manner. The Confinement Topical Group will determine exactly how to accomplish the confinement and avoid the performance degrading effects of Edge Localized Modes or (ELM modes). The hotter the plasma is the more internal plasma pressure is that must be balanced by stronger magnetic pressure fields; we could view this system in analogy to a balloon where that the plasma is the air under pressure and balloon's walls are the magnetic fields. The exact ratio of the plasma's internal current, the physical size of the tokamak, and the torodial magnetic field is a carefully tuned parameter to balance the gas temperature and magnetic pressures which does not yet have a known optimal configuration (the goal is I/aB < 2.5 where I is the plasma current, a is the minor radius, and B is the toroidal field on axis). It has been observed that the ELM modes periodically become unstable and have breakouts. This creates a large energy flux in a short time, like that of a solar flare on the Sun, where hot plasma breaks free of the magnetic fields. When this occurs the plasma may touch the side walls of the tokamak and overheat the internal surfaces to many thousands of degrees. The side wall surfaces will be evaporated and eroded inside the plasma chamber. In this way the ELM modes result in the introduction of plasma impurities which contribute to raising the effective atomic number (the number of free protons per particle) of the plasma which results in greatly reduced fusion efficiency or even the halting of the fusion reaction entirely; the target is to keep the effective atomic number below two. The aggregate erosion is large and the lining of the tokamak walls may  need be replaced often. In order to operate the machine continuously and cost effectively the ELM modes must be controlled. The control of ELM is paramount for a successful fusion tokamak. In the video below Alberto Loarte tells us a little more about the control of ELM modes and clever ways that the ELMs are dealt with.

The plasma instabilities inside a fusion reactor are a serious engineering challenge, but they are not a safety concern at all. Unlike a fission reactor, when a fusion reactor is compromised it does not go critical in a dangerous explosion (like a fission reactor would), instead it just fizzles out harmlessly. This technology is not perfect though because while some may claim that a fusion reactor would create no dangerous radioactive material in fact it would produce some radioactive material that would need to be handled. It is the walls of the reactor which will become slightly radioactive (through neutron activation). Conveniently though the half life of such radioactive waste materials is less than 100 years and could be entirely handled on site.

We should all be hoping for fusion. I spoke with Michel Claessens, the head of communications for ITER,  and one of the questions I asked him was, what should the public know about fusion and ITER?

As much as possible. More seriously, I would be happy if people understood the differences between fission and fusion.

And he has a point I think. Most people simply don't understand what is at stake and what our options our. If you are reading this then you are already more informed than most. Tell people about the difference between fusion and fission and encourage your government (no matter what country you live in) to follow a wise energy policy. While I was writing this article the United States changed its funding proposition for ITER which was a welcome change because at one point the United States looked like it would falter on its commitment to fusion research and ITER completely. This is an investment in our future and the Earth. I asked Claessens a question about this topic too, how important is worldwide collaboration in achieving a successful ITER project?

Worldwide collaboration is useful and even necessary - to pool and ensure the best use of resources (human and financial). The ITER project is so complex that no single country has the scientific and technological skills to build the machine alone. In addition, the international collaboration was seen by ITER fathers (Gorbachev and Reagan) as a way out to cold war.

The idea of harnessing the power of the Sun on the Earth is so much more than just a scientific endeavor. It is a very human dream to hold the Sun (what culture does not have some kind of original creation story or explanation for the sun?) and it is possible that realizing this dream may bring us together for all of the right reasons.

Disassociate Galaxy Clusters

A dissociative galaxy cluster is a cluster of galaxies that just can't keep it together any longer. This may sound like an unnecessary anthropomorphication of galaxies, but it is actually a description of galaxy clusters which have collided and experienced stratification of their constituent parts. In the standard and successful model of cosmology the largest scale structures in the universe, like super clusters of thousands of galaxies, form via the merger of filamentary structures composed of smaller clusters of galaxies. Gravity keeps pulling clusters together along highways of galaxy clusters. Occasionally it is expected and observed that galaxy clusters meet each other head on in cosmic train wrecks moving at thousands of kilometers per second. These traumatic merging events scar the galaxy clusters for life. Their post traumatic stress afflictions include hot shocked X-ray gas and galaxies displaced from their gas halos. Lets consider the three main constituents of a galaxy cluster: stars, gas, and dark matter.

• Clusters are made of aggregates of hundreds or thousands of galaxies and each galaxy is made of hundreds of billions of stars. The stars of the galaxy cluster are conspicuous in that they shine and are observable in pictures, but they account for only about 5% or less of the cluster's mass. The luminous stars of galaxies don't interact much during a collision with another cluster of galaxies and so they act like people in two crowds which are moving in opposite directions. Stars are part of the cosmic ghost train.
• The gas in galaxy clusters accounts for about 10% of the regular (or baryonic) mass in clusters. Gas does interact during a collision. The gas clouds in colliding galaxy clusters slams together like two waves of water meeting and stalls out, but not without undergoing a process known as shock heating first which raises the gas temperature to millions of degrees.Gas is part of the cosmic train wreck.
• The dark matter in galaxy clusters is the most dominant part of the cluster by mass making up about 90% the mass. Dark matter does not interact much. The dark matter halos travel right through each other like ghosts when two clusters collide. However, it is possible that the dark matter does interact slightly and dissociative collisions are a powerful tool in constraining this dark matter interaction. The dark matter halos of the colliding clusters should sail right past each other like two ghost trains, but if the trains slow down even in the slightest it may indicate something strange.

These so called dissociation mergers are difficult to observe and analyze. They require telescopes in space, follow up observations on the ground, observations in multiple wavelength regimes, and algorithms to predict the distribution of dark matter. So far there are six such dissociation mergers systems detected. You would think it would be obvious to spot some of the most massive structures in the universe smashing into each other, but spotting galaxy clusters is actually very difficult because of their great distance. Perhaps in an optical survey, like that in the image below taken by the Hubble Space telescope, over densities of galaxies are detected.

In practice many times it is easier to first identify galaxy clusters through their gas content because the gas content is more massive than the stellar component. Many new clusters are identified by observing the cluster gas's effect in the microwave regime or in the X-ray regime. In the image below taken by the the NASA Chandra X-ray observatory the hot intracluster gas is seen in pink. This image corresponds to exactly the same field of view on the sky as the optical image above.

It may dawn on you that by the very definition of dark matter there is no telescope which can observe it directly. The only in way in which dark matter interacts strongly is through gravity and thus that is how astronomers look for it. Through theoretical predictions and confirmed observations we know that gravity bends light and thus massive galaxy clusters will bend the light of even more distant galaxies. Thus through weak gravitational lensing the dark matter betrays its presence. A careful statistical analysis of galaxy shapes in the optical image above reveals that the galaxies which are confirmed not to be in the foreground cluster are slightly distorted in shape via the gravitational force of the dark matter which is in the foreground. A reconstruction of the total mass in the clusters is shown in the image below where the parts of the cluster which have the most mass are shown in blue. This image corresponds to exactly the same field of view on the sky as optical and X-ray images above.

Finally, a superposition of all the data allows us to glimpse at what a crisis this merging cluster is in. Note that the optical image remains in its original color, the gas is in pink, and the mass is in blue. The image below is known as the Musket Ball Cluster. The actual collision of galaxies occurred about 700 million years ago. We can rewind the collisions in our heads and envision that blue/optical cluster on the right of the image was once on the left and so the blue/optical cluster on the left of the image was once on the right; the clusters collided head on and the gas stopped dead at the center, but the galaxies and dark matter hardly stopped. There are several other images below of other dissociative cluster mergers with the same color scheme. Notice the different morphologies and distributions of mass, stars, and gas. The collisions are not always so straight forward.

Musket Ball Cluster. X-ray: NASA/CXC/UCDavis/W.Dawson et al; Optical: NASA/STScI/UCDavis/W.Dawson et al.

Train Wreck Cluster. X-ray: NASA/CXC/UVic./A.Mahdavi et al. Optical/Lensing: CFHT/UVic./A.Mahdavi et al.

Bullet Cluster. Credit: X-ray: NASA/CXC/CfA/M.Markevitch et al.; Optical: NASA/STScI; Magellan/U.Arizona/D.Clowe et al.; Lensing Map: NASA/STScI; ESO WFI; Magellan/U.Arizona/D.Clowe et al.

The awesome thing about these cosmic mergers is how they can constrain the dark matter self-interaction cross-section. That is, exactly who much does dark matter interact with itself? The interpretation of these collisions is not always simple such as in the Train Wreck Cluster (seen above) where there seems to be an extra dark matter core not associated with any bright galaxy at the center of the image, but nonetheless these mergers can be thought of as astrophysical laboratories of dark matter. It would be very interesting to discover that dark matter self-interacts at all, however dissociate clusters will only be one piece of the extraordinary evidence necessary to make that claim.



Dawson, W., Wittman, D., Jee, M., Gee, P., Hughes, J., Tyson, J., Schmidt, S., Thorman, P., Bradač, M., Miyazaki, S., Lemaux, B., Utsumi, Y., & Margoniner, V. (2012). DISCOVERY OF A DISSOCIATIVE GALAXY CLUSTER MERGER WITH LARGE PHYSICAL SEPARATION The Astrophysical Journal, 747 (2) DOI: 10.1088/2041-8205/747/2/L42

Jee, M., Mahdavi, A., Hoekstra, H., Babul, A., Dalcanton, J., Carroll, P., & Capak, P. (2012). A STUDY OF THE DARK CORE IN A520: THE MYSTERY DEEPENS The Astrophysical Journal, 747 (2) DOI: 10.1088/0004-637X/747/2/96

Markevitch, M., Gonzalez, A., Clowe, D., Vikhlinin, A., Forman, W., Jones, C., Murray, S., & Tucker, W. (2004). Direct Constraints on the Dark Matter Self‐Interaction Cross Section from the Merging Galaxy Cluster 1E 0657−56 The Astrophysical Journal, 606 (2), 819-824 DOI: 10.1086/383178

The Most Astounding Fact

We are part of this Universe, but perhaps more important is that the Universe is in us. You may have even heard it stated as a fact that we are made of stardust. What does this mean? Well in the early early Universe, a few minutes after the big bang, the Universe consisted of only hydrogen, helium, and a smidgen of lithium. There was no oxygen, carbon, or any other heavy elements. Complex life had to wait. It took hundreds of thousands of years for stars to form. Eventually in the cores of massive stars the atoms of which we exist were forged under massive pressure and heat through the process of fusion—the merging of lighter atoms to create heavier atoms. The key to unlocking those delicious elements was fantastic stellar explosions. We could say the stars died for us.

Humans are at least 60% water by mass (this is the most uncertain number here because after you drink a few beers this number quickly starts to change). Water is by mass is 11% hydrogen. Thus the mass of hydrogen in our body from water is at least 7% though of course there is lots of other hydrogen in our body from other molecules (lipids, amino acids, and so on). A better estimate is that we are 10% hydrogen by mass (if we do our accounting by number of atoms in the body we are 63% hydrogen atoms). Ultimately every atom in us is that is not hydrogen was forged in stars, and so 90% of the mass in our bodies is stardust.

What entropy is or is not

A primer of what entropy is or is not at 3 Quarks Daily by Rishidev Chaudhuri and Jason Merrill:

C.P. Snow famously said that not knowing the second law of thermodynamics is like never having read Shakespeare. Whatever the particular merits of this comparison, it does speak to the centrality of the idea of entropy (and its increase) to the physical sciences. Entropy is one of the most important and fundamental physical concepts and, because of its generality, is frequently encountered outside physics. The pop conception of entropy is as a measure of the disorder in a system. This characterization is not so much false as misleading (especially if we think of order and information as being similar). What follows is a brief explanation of entropy, highlighting its origin in the particular ways we describe the world, and an explanation of why it tends to increase. We've made some simplifying assumptions, but they leave the spirit of things unchanged.

Read on.

Perspectives on the Vertical

Cabinet Magazine has an interesting cultural perspective on human's attempts to zoom in and out of nature in the vertical. Particularly they focus on one of my favorite science films ever, Power of Ten.

Powers of Ten was originally inspired by a 1957 book by the Dutch educator Kees Boeke titled Cosmic View. By 1963, the Eameses were experimenting with tracking shots that gave the effect of a camera pulling away with accelerating motion from an object, and in 1968 used these in a film called A Rough Sketch for a Proposed Film Dealing with the Powers of Ten and the Relative Size of Things in the Universe. Shot in black and white, it was followed by an extended color version—the one known as Powers of Ten—made in 1977. The basic set-up of the latter film is well-known. It opens with a picnic scene in a park in Chicago. From a ground level view, the camera then switches to a vertical, aerial position from which it looks down, the frame centered—as we later find out—on an atom in the man’s hand. At this point the narrator tells us that we are one meter away and looking at a square one meter by one meter. Now the camera pulls away vertically and begins to accelerate so that every ten seconds our distance from the initial scene is ten times greater. The camera continues its upward trajectory until just after 10²⁴ meters (100 million light years) when it gradually slows and begins its descent, collapsing beyond its original position and now decelerating through the ever-smaller dimensions of cells, molecules, atoms, and beyond.

Read on.

Temporal Cloak

The physics and optics blog, Skulls in the Stars, ask this what is a “temporal cloak”, anyway?

I’ve been saying for a few years that optical science has entered a truly remarkable new era: instead of asking the question, “What are the physical limitations on what light can do?”, we are now asking, “How can we make light do whatever we want it to do?” Among other things, we can make light travel “faster than light“, we can focus light through a highly scattering material, we can take high-resolution pictures with low-resolution sensors, and even make particles “fly” on a “wind” of light!

Inevitably, though, many of these discoveries get misinterpreted in popular news accounts to the point that their real significance is lost in a haze of science fictional, or even supernatural, hype. A good example of this is the “picosecond camera” that I described last week, which is an amazing achievement but also possesses a number of technical limitations that make it not quite a “camera” in the ordinary sense of the word.

This week, the experimental realization of a “space-time cloak” or “temporal cloak” by researchers at Cornell University has made national news.

Read on.

Nothing

Ethan Siegel over at his blog Starts With a Bang has some more interesting ideas on the physics of nothing and everything here and here.

The Boundary Between Knowledge and Belief

The director of CERN, Rolf-Dieter Heuer, talks to European Magazine.

It’s a quest for knowledge. The questions we are examining have been asked since the beginning of mankind. We are humans, we want to understand the world around us. How did things begin? How did the universe develop? That distinguishes us from other creatures. If you go outside at night and look up into the sky, you cannot help but dream. Your fantasy develops, you are naturally drawn to these questions about being and existence. And at the same time, our work has very practical consequences. When antimatter was introduced into the theoretical framework 83 years ago, nobody thought that this had any practical relevance. Yet today, the concept is used in hospitals around the world on a daily basis. Positron Emission Tomography (PET) is based on the positron, which is the anti-particle to the electron. Or take the internet. The idea of a worldwide network started in 1989 here at CERN, because we needed that kind of digital network for our scientific work. That’s the beauty of our research: We gain knowledge but we also gain the potential for technological innovation.

More here.

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

Superluminal claims require super evidence

Neutrinos, those mercurial smidgens of the particle world, travel faster than the speed of light. That's the claim the OPERA collaboration makes in a paper subtly titled: Measurement of the neutrino velocity with the OPERA detector in the CNGS beam. This is a big claim that could have implications for particle physics and time travel. It has made the news, news, news, news, but what does it all mean? Lets talk about neutrinos.

First, let me say that if neutrinos do travel faster than the speed of light then physicists have a lot of explaining to do. The repercussions of faster that light travel for any particle (also known as superluminal travel) would be revolutionary. So revolutionary that most physicists I spoke to this past week at a conference did not take the news too seriously: it was too extraordinary to comment on without further thought and details. The OPERA collaboration is actually very brave for putting this paper out there (i.e. on the ArXiV) and asking for outside analysis. They don't even pretend to begin to consider the ramifications. The last line of the paper sums up their position:

We deliberately do not attempt any theoretical or phenomenological interpretation of the results.

So let me ignore the wild theoretical implications and discussions of tachyons and just talk about the experiment and an astrophysical constraint on the velocity of neutrinos.

Why are physicists so confident that neutrinos travel at the speed of light? Well, start with the fact that every piece of credible data ever taken has never seen anything—be it particle or information—travel faster than the speed of light. Given previous observations it is hard to understand how neutrinos could be any different. Of course neutrinos are very difficult to measure because they interact very weakly with regular matter. Consider that 60 billion neutrinos generated from the core of the sun pass through your pinky each second and none of them interact with you (nor do they interact with the Earth, they are passing through you day and night).

The creation and detection of neutrinos is complicated. The process begins for the OPERA experiment over at CERN where the Super Proton Synchrotron (SPS) creates high energy (400 GeV/c) protons that collide with a graphite target producing pions and kaons which decay into muons and muon neutrinos. The neutrinos coming out of SPS are almost pure muon type neutrinos with an average energy of 17 GeV. The neutrinos travel through the solid Earth in a straight path unimpeded into a cavern below a mountain, Gran Sasso, in Italy. The OPERA neutrino experiment was designed to look for the direct appearance of muon to tau neutrinos (ν_μ → ν_τ), but their anomalous findings on the velocity of neutrinos is much more interesting.

The OPERA experiment found that the velocity of neutrinos was about 0.00248% faster than the speed of light. This measurement was made by precisely measuring the distance traveled by neutrinos and the time of travel. The OPERA collaboration did a lot of work to measure both parameters precisely. They found this velocity by measuring that the time of arrival of neutrinos at their detector by using atomic clocks. Their measurement was precise to a few nanoseconds. Wow, that is quick. Light only travels about a foot in a single nanosecond.

In order to measure the distance between CERN and Gran Sasso the OPERA team used very precise GPS systems. For example, they noticed a 2009 earthquake in that area produced a sudden displacement of 7 centimeters. So the exact distance the neutrinos traveled was 730534.61±.20 meters (or about 2.44 light milliseconds), however some have suggested that the GPS based positioning they used has errors introduced by atmospheric refraction. Intriguing possibility.

In order to measure the time, what OPERA calls the time of flight measurement, they used atomic cesium clocks. But the 'time' cannot be precisely measured at the single interaction level since the protons from the SPS source have a 10.5 microsecond extraction window. They had to look at time distributions where the most likely time for a burst of neutrinos to be created was inferred to higher precision. Additionally, the actual moment where the meson produces a neutrino in the decay tunnel is unknown, but it introduces negligible inaccuracy in the time of flight measurement. So, these distance and time measurements are really important, but really subtle. I recommend reading the paper if you are a glutton for punishment.

There is a very interesting constraint on the speed of neutrinos that comes from astronomy. It was the neutrinos and photons released from the death of a star. Supernova 1987A (SN 1987A) exploded 168,000 years ago when fusion in the core of an old star ceased and the weight of the outer layers of the stars caused the core to collapse. The protons in the atoms of the core of the star merged with the electrons present and converted themselves into neutrinos and electron neutrinos. A mega amount of electron neutrinos, about 10⁵⁸, were generated and they began their epic journey to Earth. Some of these neutrinos arrived on Earth one morning in February of 1987 in a burst lasting less than 13 seconds. Of those many neutrinos two dozen interacted with detectors on Earth.

Astronomers observed light from SN 1987A just three hours after the neutrinos arrived. Just such a delay is expected as the fireball of the supernova had to have some time to expand and become transparent to photons, whereas neutrinos could escape much sooner. The explosion occurred at a known distant out in the Large Magellenic Cloud. This distant explosion created photons and neutrinos in a timed race to the Earth. With the these measurements in hand (the distance to the supernova and the time of arrival of the photons compared to neutrinos) we can determine the speed of neutrinos from SN1987A.

The accuracy and precision of measurements from SN 1987A are actually much greater than measurements taken at Gran Sasso despite the three hour time window difference between neutrino and photon travel. It comes down to the fact that the relative distance between Earth and SN 1987A is about 10¹⁶ times larger than the distance between CERN and Gran Sasso. This means that time measurements from SN 1987A can be extremely imprecise and still be much more precise than the OPERA measurements.

If the neutrinos from supernova 1987A had been traveling as fast as the neutrinos detected at Gran Sasso they would have arrived about four years sooner than the light from SN 1987A.

This supernova constraint on the velocity of neutrinos is very nice, but it doesn't answer every question because the comparison may not be apples to apples. The OPERA neutrinos are tau type, not electron type. And they are traveling through the Earth, not empty space. And they were much higher energy. The neutrinos from SN 1987A were only about 10 MeV, about one hundred times lower energy than the neutrinos in this study. Some may argue that higher energy neutrinos travel faster than lower energy neutrinos. However, a velocity-energy dependence should have stretched out the 13 second arrival time of neutrinos. Further, part of the OPERA collaborations analysis involved splitting the data into two bins with mean energies of 13.9 and 42.9 GeV; a comparison between the two bins indicated no energy dependence on velocity. Thus, while it may still be true that GeV neutrinos move faster than MeV neutrinos, the theoretical wiggle room is shrinking.

This experiment may be a signal of new physics or a case of systematic errors. Yet, even physicists who have developed theories that allow for superluminal velocities are doubtful so I would not bet on proof of hidden extra dimensions or time travel to come from this experiment. Much more extraordinary evidence is necessary to confirm such an extraordinary claim as breaking the speed limit of our Universe.

You've been Westinghoused Mr. Edison

Recently while glancing through an old physics text I found a line I had underlined, Westinghouse Electirc Corporation, and I remembered a little phrase that I used to use with other physics students. The phrase was, you've been Westinghoused. Let me explain. There is a curious episode in history know as the the war of the currents wherein the early pioneers of electricity were trying to commercialize the transmission of electricity. Nikola Tesla with the financing of George Westinghouse supported alternating current (AC) against Thomas Edison who supported direct current (DC). Edison tried to discredit the idea of AC transmission by showing how dangerous it was. Edison attempted shenanigans like electrocuting an elephant in public, but in the end practicality and economics prevailed. AC transmission is much more viable than DC transmission because of the pure physics: with DC transmission in order to get adequate power transmitted either the wires would have to be copper as thick as your arm or you would have to have power stations every block or so. It was probably a combination of physics and the shrewd business sense of Westinghouse that it came to pass that Edison lost the war of the currents. This history, like the story of Bohr and Heisenberg, has interesting characters and a certain mystique that lends itself to historical plays and documentaries.

Tesla was a modern Prometheus. Some say that history overlooked Tesla, however, there is a current (pun intended) revival in interest for Nikola Tesla, if not always for his science, for his eccentric personality. This documentary about Tesla talks about his life and work. The part about the war of the currents begins at 18:35.

Now, as Edison fought against AC current he tried to be really clever and he wanted to brand death by electrocution as being Westinghoused. However, Edison's electric empire faded and history summarily shows that he was bested by Tesla and Westinghouse. Scientists are a competitive bunch, so I propose that when one colleague bests another colleague in an academic pursuit, we proclaim that the the defeated has been Westinghoused. It isn't the worst thing to be Westinghoused, it just means you were bested in that pursuit. Edison was a great inventor and is still famous to this day, but he surely got Westinghoused.

Sailing

There was an amazing article up on Wired today about the America's Cup. It reminded of just how cool competitive sailing is. I wrote about sailing upwind in 2009 before the last America's Cup race and I mentioned a revolutionary solid wing multihull boat created by team Oracle. That boat was in fact as fast as promised and it won the race and by doing so team Oracle won the right to dictate the rules of the next America's cup. What they did was create the America's Cup World Series of standarized fixed wing catamaran sailing boats (you can read more about the entire thing in the Wired article). These boats are super fast and super intense. The America's Cup World Series is the water equivalent of Formula 1, but instead of crashes there are capsizes. Well, actually there are crashes too. Here is a hectic highlight real of these boats racing in the first ever event a few days ago in Cascais, Portugal.

Modern sailing is a paradoxical mix of elements. The boats are designed with advanced knowledge of physics and constructed of carbon fiber, yet they are powered by the simplicity of the wind. I think there is an appeal to working with nature to accomplish work rather than fighting against it. Working with nature always seems to be the most graceful option. In space travel rather than firing rockets to propel ships it is advantages to use gravitational assists by swinging by planets. And then of course there are solar sails in space too. The Japanese IKAROS satellite recently successfully unfurled itself in space and is now being pushed by photons on a unique journey. If you think about it astronomy and sailing go together.

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.