Quantum Searching in Your Browser

If you’ve made it through the last two posts on quantum computing (QC), then you’ve seen the Quirk simulator, a little of IBM’s web-based offering, and how entanglement and superposition can do strange and possibly wonderful things. However, the superdense encoding I showed you didn’t really feel like a real computer algorithm. This time we will look at Grover’s algorithm which is often incorrectly billed as an “unstructured database search.” In reality, it is an algorithm for making a state — that is a set of qubits — match some desired state without simply setting the state.

By analogy, consider a web service where you guess a number. Most discussions of Grover’s algorithm will tell you that the service will only tell you if the number is correct or not. If the number was from 1 to 16, using traditional computing, you’d have to query the values one at a time to see which is correct. You might get lucky and hit the first time. Or it might take 16 times. With qubits you can get the same result in only four attempts. In fact, if you try more times, you might get the wrong answer. Of course, what you really get is an answer that is probably correct, because that how QC works.

Going Through a Phase

The secret to Grover’s algorithm is there has to exist an oracle function. This function will reverse the phase of the qubits when they have the correct answer. Because of superposition, the values are all at least somewhat likely, but only one gets its phase reversed.

This is why I dislike the database search analogy. Because the oracle function has to know what the answer is ahead of time. I think that a better analogy is a web service, because the rest of the code doesn’t get to know what is happening in the oracle function. With QC, the web service takes all the possible numbers and marks the one that is correct.

Just having the phase reversed isn’t enough, though. We need an operation to effectively subtract the phases from each other. The phases that we didn’t change will cancel out, and the phase that we flipped will become larger. This is known as amplitude amplification. Depending on the total number of qubits, you may have to repeat the entire process, but for now, let’s consider two qubits which can have state |00>, |01>, |10>, and |11>.

The first part of the circuit will create the superimposed states. The inverters set up the original bits in the |1> state and then the H gates create the superposition. I added a chance probe so you can see that now there is exactly a 1 in 4 chance of any single state being the one we’d get if we observed it now.

 

Match Game

The next step inverts the phase of the item you want to match. Exactly how you’d do that depends on what you want to find, but in our case, we are just going to plug in a constant. That’s easy. The Z gate flips phase and we can control it. By using solid dots and hollow dots on the Probes toolbox, you can ask for any arrangement of 1s (solid) and 0s (hollow) you like. Just put the Z block on a qubit you want to be 1 and then use the dots for the rest. Oddly, it doesn’t matter which qubit the Z box is on (as you will see later) as long as it is a 1 in the resulting pattern. Here’s a search for 10 which is, in this case, our oracle.

Now we get to the Grover diffusion operation which is the heart of the algorithm. What we really want now is to invert the state’s X axis. In Quirk, you can do that by using an X control and then using the small circle with the cross in it under X/Y probes called X-Axis control. Like this:

However, that hides a lot of what is going on. It is really just shorthand for this:

This rotates the qubit around so that X now points to Z , inverts Z (which is now X), and rotates it back. In other words, it inverts around X axis instead of the Z. In practice, I’d use the Quirk shorthand, but for learning purposes, it is nicer to see what’s really happening. Since we only need one pass of the algorithm for two bits, we are done. If you had more, you’d repeat the oracle function and do another diffusion, repeating both until you had enough passes.

You can look at the entire setup with a lot of extra instrumentation in the simulator. Note the phase angle after the Z gate. Only the state of interest flipped. Then notice the probabilities as the qubits flow past the diffusion. You’ll notice that going into the final H gate, the phase angle for the top qubit is 90 degrees instead of 180. That’s because it is only going to be on in one state and not the other.

Try replacing the hollow dot with a solid one, and you’ll “find” |11>. You can also reverse the position of the Z gate and the hollow dot and things will still work.

Bigger, My My

Scaling this up to five qubits is pretty trivial. Here I used the controlled Z gate instead of breaking it out and I put in a lot less instrumentation. You can change the solid dots and the position for the Z gates to control the “search” pattern. Just remember that if you change them in one place, you have to make the same change everywhere else.

Quirk has a way to make a part of the circuit a custom gate. You can also specify custom gates by rotation angles or from a matrix, but I won’t cover that here. The only problem is, once you make a gate, you can’t go back and change it easily. Of course, since everything is stored in the URL (if you haven’t noticed, look in your address bar), you can brute force edit things, if you like.

What’s Next?

These have been three fairly long posts. However, this is just the tiniest tip of the iceberg. There are plenty of gates on Quirk that we haven’t used or talked about. If you use IBM’s real hardware, there’s also a lot more you have to create to do useful things and additional practical considerations, too.

The good news is that there is plenty of material out there on the Internet. The bad news is there isn’t a lot in that middle ground between handwaving generalization and bone-crunching math. What’s more, as I’ve mentioned before, a lot of the generalizations that you’ll hear are oversimplifications that can get in your way of understanding.

If you want to go much further, you are probably going to have to take the math pill. If you know linear algebra and trigonometry, you should be set. If you don’t, take heart because it isn’t as hard as some math out there. You could do worse than start with Kahn Academy.

The other thing I’ve been silent on is how all these qubits exist in physical devices. That’s a fascinating story, too, but just like you don’t need to understand MOSFETS to program a modern CPU, I didn’t think diving into that particular rabbit hole would help gain understanding.

If you are determined and not put off by the math, [Michael Nielsen] has 20 or so videos that are very comprehensive, appropriately titled “Quantum Computing for the Determined.” These are good, but you will need the math. Unfortunately, he never finished the series and the deeper you go, the more the start dealing with proofs and things that you probably should know, but might be more interested in after you get a real understanding.

The IBM User’s Guide has a lot of information that is useful even if you aren’t using their simulator as does the home page for Quirk. IBM also has an interesting example that plays a game using Grover’s algorithm as a web service. Two caveats. Because it is a web-based program, there’s a lot of underpinnings you don’t care about if you are just learning about QC. Also, some of their example code has strings of gates that could be simplified. If you just want to try out the result, you can just open it up from their site.

Finally, MIT has some good examples of how to create complex gates from simpler ones. Sometimes you have to dig a little bit to translate nomenclature between MIT, IBM, and Quirk. It also helps if you learn QASM, which IBM supports but Quirk does not.

Go Forth and Hack

This technology is still in its infancy. While it is hard to get practical devices in your hands, especially when even big labs have fairly small devices, it is easy to work things out in simulation and it is clear there is still more to be developed. The picture to the right is IBM’s newest 50 qubit device. Of course, they aren’t letting you use it on the web. At least, not yet.

To me the danger is the way — deliberately or not — the technology is overhyped. I think some of it is just people generalizing the generalizations they’ve heard somewhere else and you get a little further off the mark each time. Some of it is probably also just marketing hype, which is nothing new. People have to get research grant money and sell stock, after all.

Of course, even if the market is disappointed, the promise that moderately large QC devices will be able to find prime factors quickly (look up Shor’s algorithm) and break military-grade encryption is enough to ensure that those bigger machines will get built. They may get locked away from the likes of us, though.

Without ready access to hardware, I suppose we’ll have to settle for virtual hacking. For today, at least. The hardware is coming and just as in the 1960s no one could guess that computers would be cheap and everywhere, there’s no telling how ubiquitous quantum computing devices will be in fifty years.

from Hackaday http://ift.tt/2sipP5X
via IFTTT