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.