Quantum computing and light switches

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

quantum computing

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

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

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

The light switch game

quantum computing

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

quantum computing

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

quantum computing

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

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

quantum computing

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

quantum computing
.

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

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

quantum computing

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

.
3.) How does quantum mechanics help?

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

quantum computing

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

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

quantum computing

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

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

quantum computing

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

21 thoughts on “Quantum computing and light switches

  1. This is absolutely brilliant in that it was fun to read, relatively easy to understand and made me feel smarter, instead of stupider at the end. I think I might actually be able to explain quantum superpositions to my son now.

    Kitty meowed all over my self-imposed critic also…bravo kitty tactics.

    You’re a fantastic writer.

    One question: “As this is performed, you allow the switches to slowly drop out of the superposition and choose one classical state, either ON or OFF. At the end, each switch MUST have chosen to be either ON or OFF.”

    You used the word chosen. Does the computer actually choose?

    • In my summary..

      Each switch has two values h & s
      Each switch has a unique h value which never changes
      Each switch has a s value limited to +1 & -1

      Therefore h never changes and s is limited to two values.

      Therefore J and the connected pair must be the selective influence that describes the problem being answered.

      The value of s chooses +1 or -1 based on the culmination influence of all J connectors for that switch as it drops out of superposition.

      My understanding may be incorrect.

  2. Hello Suzanne.

    I have a doubt, if the D-Wave gives you differents answers on differents reads and supposing than a particular bias values set has only *one* correct configuration that yields to the minimum result, so Does the D-Wave give us a wrong answer sometimes? Is there any measure of this desviation?

    • Bayron,

      not Suz here, but somewhat qualified to answer as well! ;-) — yes, all quantum computers are envisioned to be probabilistic machines (and classical too, but they are engineered in a way that probability of error is very small — but try removing that heatsink from your classical processor — it will fail for *exactly* the same reason D-Wave One sometimes give wrong answers! ;) ).

      D-Wave One is no exception, this is why one needs to run computation several times. Fortunately, while it is hard to see which “light switch configuration” is optimal, one can easily calculate value for all returned configurations and select ones which are the best.

      It is a real physical system sitting at very small but non-zero temperature, and energies of the answers are distributed according to Boltzmann distribution, with lowest ones *most probable*, but higher energy solutions are also sampled. In some applications it is actually considered to be an advantage, think about it this way:

      What if you are not exactly sure in your choice of h’s and J’s values? You can use additional information extracted not only from the obtained solution to the specified problem, but from other low-energy solutions (each of them could become “the” solution if h’s and J’s were varied slightly) to fine-tune your program specification.

      Hope this helps,

      Paul B.

      P.S. Suz, nice write-up! I actually started thinking about extending it to a physical sets of switches, with little weights attached, gravity (“on” and “off” not necessarily “up” and “down”), and ribbon strings (actually, for AFM couplers, they should be ribbon sticks), thanks for ruining my Sunday morning! ;)

  3. Hi
    I have a question for you and don’t see the answer yet out there if there is one. For quantum entanglement and set’s. If you take a set of particles and entangle them and then send them off to a target detector. One right after the other. Can you get the superposition and quadrant and over time work out the spin of the particle that has been entangled with the rest? Does the wave form of the superposition correlate to the frequency of the particle over time? Or does it just correlate to the energy level spin of the quantum particle used?

    Or quantum particle physics with a type of string theory that also shows and proves quantum entanglement or resonate coupling of like building blocks ( Quantum particles )? Any direction to or work of would be nice. Ty.

  4. I think there were some grammatical errors in your post. I have fixed them below. You may want to update other parts as needed.

    AS PEEPS TEND 2 BE PUT OFF BY MATHEMATICAL EQUASHUNS IN BLOGPOSTS, I DECIDD 2 AUGMENT IT WIF PICCHUR OV CUTE KAT. HOWEVR, UNLES U R VRY MATHEMATICALLY INCLIND (LIEK DIS KITTEH), IT MITE NOT BE INTUITIV WUT MINIMIZIN DIS EXPRESHUN AKSHULLY MEANZ, Y IT IMPORTANT, OR HOW QUANTUM COMPUTIN HELPS. SO INSTEAD OF SAYIN “LOOK, U R DOIN UR QUANTUM COMPUTIN WRONG.” I’M GOIN 2 TRY 2 ANZWR DOSE 3 QUESHUNS IN DIS POST IN HOPE U GIVE KAT CHEEZBURGER TO NOM.

  5. Could you please explain how is the “execution time” calculated/approximated on a quantum computer? I read something about “gate times” but I do not really understand it, could you please clarify? For example if I have an algorithm for a single qubit quantum computer, how does it scale with the number of qubits, how to approximate the “real-life” execution time of that algorithm? thanks

    • I assumed the execution time is that of loading the values (problem) and the time to transition out of superposition. I believe scaling describes the number of qbits needed for this parallel process, execution time is unchanged.

  6. Now that schrödinger’s cat is dead in a way ( don’t worry it died a nice old death ). http://www.physorg.com/news/2011-12-atoms-glass-fiber.html Can you please tell me if your able to set up a entanglement to detect the quantum spin by quadrant and over time threw batches. Then statistical analysis of the quadrant and particle type entangled and the temp and medium that it travels threw, even in a vacuum. Say a material similar to this http://www.physorg.com/news/2011-12-quantum-world-diamonds.html and knowing the chemical bond and structure and entangling set’s at room temp. Oh wait, let me guess I’ll get criticized for grammar instead of a answer or push to the right direction to tolerant enough people to help, or at least try to answer this some way and form. Unified Law or Final Theory http://en.wikipedia.org/wiki/Theory_of_everything Who can help? Ref. links also http://www.fnal.gov/pub/today/images08/ThreeFrontiersGraphic_RGB_060108.jpg and http://www.physorg.com/news/2011-12-world-smallest-electronic-circuits.html .

    N8 M0US3 PWND M!M3 K!TY BAD * BLK SWN 4 U 2 C . #%/T!M3/D!STANC3 = X,Y,Z P0S/SP33D/TRAG . P#0.1357 37331 B 4 U / , # @ !T R8 +-1 2373314U2C UN!F!3D UN!V3RS3 !S HAX3D P. ;-)~

    Thank you for any reply or direction to the right place or open a dialogue about it at least.

    Laborious Aftermath N81

  7. Very cool.
    But how does superposition work? Does it have to do with our inability to know exactly where an electron is, and because it’s moving so fast it’s considered to be in multiple places at once?

  8. Thanks for explaining that. It helped me figure out a cellular automata that implements something similar to relativistic quantum physics, which I call Physicsmata, open source program at the link if you click my name here. Its simply the algorithm of each set tries to add each of its childs to each of its other childs, and the bell curves of all that (standard deviation is square root of number of cycles) expand like each set is a light-cone superpositioned in many other light-cones. It implements black holes by the multiply routing (all pairs in every set get added to eachother) are all pointing at other sets in the black hole, so anything past the event horizon can’t get a word in to get them to point outside the black hole. What do you think?

  9. This will revolutionise genomics. There are now a whole bunch of SNP markers identified by GWAS studies which relate to disease risk but confer only modest individual effects. Intuitively one would think that a burden of these increases your risk of disease. The problem is they are all interconnected and there are external and internal influences. Assuming these SNPs and other factors carry the same weight, are multiplicative and are not influenced by the presence or absence of other factors is too simple. Unfortunately current medicine relies on reductionism and buries its head in the sand when it comes to complexity like this. Cox proportional hazard models is the method de jour with an overt focus on quantitative changes in values. “More is better”. Looking for qualitative changes and patterns in a number of interconnected values seems far more intuitive a method. Hopefully you will get to collaborate with someone involved in personalized medicine research as the QC will be immensely useful for analysis of the data.

  10. Pingback: Big Data | Riyaaz

  11. Pingback: Big Data | Riyaaz

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s