[ExI] A Working Quantum Computer by 2017?

[Anders]

On 2016-09-03 17:36, John Clark wrote:
> ​Add quantum computers to the list of things that could create a 
> singularity. Google now thinks that as early as the end of next year 
> they will have a working 50 Qubit quantum computer that can achieves 
> something they call "quantum supremacy", it means solving a problem 
> that no existing conventional computer can.

Ahem. People always get confused about this. Quantum computers give 
exponential speedups for problems that have quantum algorithms, but not 
all practically important problems have quantum algorithms or can be run 
with a small number of qubits. Grover's search algorithm for example 
finds an element in an unsorted list in O(sqrt(N)) time, as opposed to 
O(N) time - great, except that the list needs to be in a quantum state, 
so 50 or even 5000 qubits will not change much. Same thing for quantum 
sorting - better than classical, but you need to have a quantum array. 
Quantum computing really beats classical in problems where the memory 
demands are tiny but the search space big, like some simulations, 
optimization or decryption algorithms.


> This is much earlier than anybody thought just 5 years ago.

Yup, progress is faster than expected. Still, I had a senior computer 
scientist tell me to my face *this week* that he doubted there will ever 
be a quantum computer that is usable for anything.


-- 
Dr Anders Sandberg
Future of Humanity Institute
Oxford Martin School
Oxford University

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.extropy.org/pipermail/extropy-chat/attachments/20160903/049301ee/attachment.html>