Reply to post: Re: Conventional supercomputer?

Google and IBM square off in Schrodinger’s catfight over quantum supremacy

Michael Wojcik Silver badge

Re: Conventional supercomputer?

Part of IBM's objection was that the problem solved was not one that has been studied enough to have figured out the fastest algorithm, so there may well be an algorithm that allows an existing conventional computer to beat Google's quantum computer.

It's difficult to prove an algorithm is "the fastest", and impossible, in general, to prove that an implementation is optimal (from AIT; see Chaitin or Kolmogorov).

But I'm with Scott Aaronson on this: It seems very unlikely that there's a sub-exponential classical algorithm for the random-QC problem. He proposed offhand (and probably wouldn't be held to this, but it's suggestive) that P=PSPACE is about as likely.

Objections that hold more water are that what Google have shown is either near quantum computational supremacy ("we can do that on a really big conventional machine"), or that it's "baby" QCS, since without error correction (which would require a whole lot more physical qubits) the hardware is only suitable for a small subset of problems, without a lot of practical applications.

Random-QC does have at least one application, though - Aaronson notes it can be used to implement his protocol for generating a stream of computationally-provably-random bits. And as I noted in another post, things like quantum physics simulations have requirements that may be more achievable than those of things like Shor's and Grover's algorithms.

POST COMMENT House rules

Not a member of The Register? Create a new account here.

  • Enter your comment

  • Add an icon

Anonymous cowards cannot choose their icon


Biting the hand that feeds IT © 1998–2021