Have you been bluffing your way through conversations about quantum computing? I have. People say they can make faster computers with them. I hear than and nod my head. I want to know how, but I’m afraid to ask. Over the Thanksgiving holiday break, I got a chance to ask without losing face.
Me and Superposition
I long ago accepted Schrodinger’s cat’s life-and-death dichotomy as an illustration of superposition, and superposition as an example of the implicit strangeness of the Standard Model. What I didn’t see is how that related to making faster computers. I just went along with it, just like I did long ago as an undergraduate taking the required class in Fields. (Do you really have any more idea how Charge relates to action at a distance? Can you explain it without reference to Vector Analysis? *)
So getting back to quantum computing, I find it easy to accept Wikipedia’s definition of a Qbit: “A two-state quantum-mechanical system, such as the polarization of a single photon: here the two states are vertical polarization and horizontal polarization. In a classical system, a bit would have to be in one state or the other, but quantum mechanics allows the qbit to be in a superposition of both states at the same time, a property which is fundamental to quantum computing.” Someday, it would be interesting to know how a photon changes its polarization or how you would tell whether one single photon was polarized one way or the other after it had previously been polarized both ways at once. (Not really at once, but in superposition of polarization states; I realize that’s different than being both at once. I think. One can do searches, but that leads to sentences like: “The possible states for a single qbit can be visualized using a Bloch sphere,” and I feel like I’m back in that Fields classroom. )
But I don’t actually want to know about the gender roles of subatomic particles. That’s for physicists. I’m an engineer. I want to know how come somebody can use qbits to make faster computers.
Thanksgiving Breakthrough
The kids were down from the University of Washington. My Daughter Kathleen is wrapping up a Ph.D. in computer science there; Adam, her fiancé, is a post-doc, also in computer science. Feeling mellow after turkey and wine, I put it to Adam: “What the heck does it mean when they say they can make a faster computer with qbits? What, exactly, does “faster” mean in that context?
Adam, typically, gave a succinct answer. Essentially, he explained, what is supposed to happen faster are database searches. There is an algorithm for searching memory arrays that lets you look at all the locations at once, rather than riffling through them sequentially, as you would in a conventional array. But there is a catch: when you get a hit, the probability that it is a correct hit is less than one. You have to perform multiple iterations of your search if you want to close in on (but never achieve) absolute certainty.
Armed with that certain knowledge, I went to the Web and searched for “Qbit search algorithm". That turned up approximately 196,000 hits in about two seconds, most of which involve something called “Grover’s Algorithm,” so this is not exactly computer science’s best kept secret, but I swear, amidst the stuff I’ve been encountering about quantum computing, it’s the first time it’s popped up for me.
Now I know what “faster” means in the context of quantum computing versus the kind that uses old fashioned discrete bits, and it’s kind of interesting because it’s less about doing mere arithmetic and more about finding matches in ginormous databases, but that does seem to be exactly where most new applications are headed.
*I have a friend, a truly creative EE, who told me once that he was okay with Gradient and Divergence because he could sort of visualize what was going on. (At which point I would nod my head sagely.) But that he threw in the towel when it came to really grokking Curl. He could do the math, each separate evolution of which made sense, but, in the end, he had to take Curl on faith.