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.
I’m just going to link wikipedia because it does an infinitely better job of explaining what Grover’s is:
https://en.wikipedia.org/wiki/Grover%27s_algorithm
This article is horribly confused.
“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.”
This, again, seems to confuse what is going on. How is a web service inherently a better analogy for a black box? Is that the only example of a program you can think of?
When people say it is “database search” they are not saying that the black box function is a database. They’re saying you can treat the problem space, the inputs and outputs of the function, like columns in a database, in that each is directly mapped to another, and you’re trying to guess or find one of the columns values given the other the other column value, which is exactly what database search does.
“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.”
Irony
Cliff how about you take some of that energy telling hackaday how much they suck and write your own accessible article(s) on the subject. Oh yeah. I guess this is easier.
“You might get lucky and hit the first time. Or it might take 16 times.” Wouldn’t that take 15 tries max?
Depends on how bad you program.
Yeah its technically N-1 but as N grows the -1 becomes negligible. But you’re right, for 16 elements you can do 15 checks and then default to the last case.
Doesn’t the last case technically count as the 16th “time”? It’s just the else after the loop.
Not really, on architectures like ARM, with condition execution of any instruction, the Nth one is free.
As long as že guessed number doesn’t change with every try…
Ok, I’ll cop to that. If you knew the number was 1-16 and you tried 1-15 you could assume the number was 16. But my point is you have to linear search.
Well I’ve clearly pushed your buttons and I should probably just let it lie. But I will say one thing on the subject. This is exactly the problem I’m talking about in so much as people either oversimply (database search) or go into a math hole and then the repeats get more and more off the mark.
I’m not sure what part of this you have issue with. The oracle function does know the answer. That’s why it is the oracle. If you go too far, you do get the wrong answer (unless you go even further and then it is right again). Guessing what some secret number from 1 to 16 could take 16 tries using conventional logic.
As far as “mapping inputs to output” — well, call it what you like. I had a professor who talked about maximizing the boolean variable when he meant set the bit to 1 because he couldn’t stand to speak plainly. Now if you posit — and we don’t have this today that I’m aware of — an “oracle function” that is not part of the same system, then sure. But the fact is, the oracle function is providing information about what the right answer is. And to most normal people that’s not what database search means. Where it makes sense is when you don’t know what the oracle function does but you can get the behavior out of it.
Hopefully, most people will work through the example, read around, and draw their own conclusions.
Wow you’re still not getting this, and rather than try to understand you’re digging in and getting defensive.
You’re right, people do oversimplify. You’ve oversimplified. You’re part of the very problem you discussed. This article is going to confuse people, not teach them.
And saying “you can call it what you like” is really dismissive and ignores the issue. You can call it what YOU like, you can pretend its a web service. I could say the exact same thing about you. I don’t need to hear your story about some professor who did something completely unrelated to the matter at hand; that’s basically gaslighting. You’re not arguing logic. Its fallacious.
“Where it makes sense is when you don’t know what the oracle function does but you can get the behavior out of it”
LIKE DATABASE SEARCH. A database doesn’t even necessarily have an “algorithm” just a mapping, so its a perfect example. Meanwhile, guessing random numbers for a website, what kind of nonsense example is that? It makes no sense. You’d never have to do that in real life.
The perfect example as well is trying to guess results from a reverse encryption, in other words, breaking encryption. You know the forward function so you can test results (the oracle function) but you don’t necessarily know how to calculate the original value given the encrypted key. So you can use Grover’s.
I’m sorry dude but you literally did exactly what you accused other people of.
“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.”
And this article is one of them.
How is this generally handled, a Clifford algebra?
This is a great article and I learn new things with each instalment. Please keep up the good work. Quantum computing is a complex topic, but it’s articles like this that help us begin to understand what it’s all about (for those of us that don’t already know it all).
I see a section disappeared. ;-) But as far as the math, most schools teach up to (and beyond) trigonometry and linear algebra, so at worst it’ll just be lengthy. The other is forest for the trees in not seeing the picture math is suppose to be portraying. And last quantum anything is nonintuitive so one can’t rely on that for understanding.
You know if you take the rig in the picture and turn it upside-down and place it in the middle of a hexagonal console in the middle or a room with panels on the wall, each with large circular indentations….you’ve got the inside of the tardis.