Sunday, June 2, 2013

What IS a Quantum Computer?

Having a delightful time in Beijing visiting the Computational Science Research Center, which last week hosted the Fifth International Workshop on Quantum Optics and New Materials — this time to celebrate the 60th birthday of my old friend and collaborator, M. Suhail Zubairy.

On the last day, Wednesday, I sat at lunch at the vegetarian table with Zubairy, Barry Sandars, Selim Shahriar, Wolfgang Schleich, Girish Agarwal, and J├Ârg Evers. The discussion turned to the computational complexity of linear optical interferometers (the topic of my talk that morning) and then more broadly to D-Wave's machine and then somebody (might have been me but I had so many vegetables who can tell) asked each person in turn to define a quantum computer.

To us quantum opticians the fact that there was no agreement at all came as a bit of a surprise. Shahriar held out for a universal machine capable of running Shor's algorithm. I pointed out that, as per a 1998 article by Seth Lloyd, that coherence and strong projective measurements were necessary and sufficient to run Grover's algorithm with a quadratic speedup — shouldn't such a machine be called a type of quantum computer?

Shahriar rejected that as it was not universal. Then came the D-Wave discussion. If the D-Wave machine can do something useful, also exploiting quantum coherence, should it not also be classified as a type of quantum computer? Sanders seemed to side against this. I was more positive.

And so the discussion continued as the vegetables arrived in an never-ending sea of serving platters. In the end Zubairy thought it was quite surprising that we all could not agree on the definition of a quantum computer. I rejoined that people still argue over what was the first classical computer. The Babbage difference engine? The ENIAC? The Atanasoff–Berry Computer? How about that ancient Greek computer the Antikythera Mechanism? If historians of computer science can't even agree on what is a a classical computer what hope do we have of now agreeing on what is a quantum computer.

My own definition? Any computer that exploits some of the weirder features of quantum mechanics to attain a computational advantage over the best classical machine, no matter how slight, should be at least entertained as a type of quantum computer.

No comments:

Post a Comment