Google $5M XPRIZE for best uses for Quantum Computers

Google is looking for practical problems/algorithms that can be solved on quantum computers:

https://www.xprize.org/prizes/qc-apps

jedishrfu said:

Google is looking for practical problems/algorithms that can be solved on quantum computers:

Does this mean QC now appears to be a useless toy, and that they need to find a real application that justifies the expenditure, so they can keep their jobs ?

Pretty much.

We have the technology now give us your problems.

Baluncore said:

Does this mean QC now appears to be a useless toy, and that they need to find a real application that justifies the expenditure, so they can keep their jobs ?

No, not at all.
We are very confident that large-scale, fully error corrected quantum computers will be able to solve a lot of real world problems; and we already have good algorithms that can be used for this (Shor's algorithm being the most famous, but probably not the most useful)

However, we are not there yet. The current generation of quantum computers have relatively few (~!00) qubits and these are still very noisy (no proper error correction) and that severely limits what can be done.; you can't e.g. run Shor's algorithm for anything but very small numbers. If you want to e.g., break RSA you might need a computer with lots fully error corrected logical qubits; and that might (if we are unlucky) require ~millions of physical qubits. That is we need to scale another factor of x1000 or so (plus solve a bunch of other problems).

There are a few "hard" problems (problems that are not practically solvable on a classical computer) that can be solved on current quantum computers, but none of these algorithms have any real practical use.

Hence, the prize is mainly about developing useful algorithms that can run on current or near-term hardware.

f95toli said:

Hence, the prize is mainly about developing useful algorithms that can run on current or near-term hardware.

But anything useful, that will run on current QC hardware, will run faster on a PC or GPU.

Baluncore said:

... they need to find a real application that justifies the expenditure, so they can keep their jobs ?

Baluncore said:

But anything useful, that will run on current QC hardware, will run faster on a PC or GPU.

Right now, that is probably true; but I guess that is the point of the prize(!)

Note that the algorithms/circuits that are used for the current generation of QC is quite different from what would be used on a fully error-corrected machine. Right now, all circuits have to finish running in a relatively short amount of time which severely limits the number of operations that can be run in each shot. In a fully error-corrected machine you should -in principle- be able to run arbitrary long circuits. Hence, you can't really "extrapolate" from what can be done today to what might be possible in the future.

The fact that there are some algorithms (say boson sampling) which DO run very quickly (much faster than what can be done using a supercomputer) even on current generation HW presumably means that there is no fundamental reason for why someone couldn't develop a fast algorithm that was actually useful.