<html>
<head>
<meta content="text/html; charset=UTF-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
On 2016-09-03 17:36, John Clark wrote:<br>
<blockquote
cite="mid:CAJPayv2z=aNuvGgoA+zwRpLFct1f3FRioHGTC_wZM8ZcU8tnwQ@mail.gmail.com"
type="cite">
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<div dir="ltr">
<div>
<div class="gmail_default"><font size="4"><font face="arial,
helvetica, sans-serif">Add quantum computers to the
list of things that could create a singularity. </font>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.</font></div>
</div>
</div>
</blockquote>
<br>
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.<br>
<br>
<br>
<blockquote
cite="mid:CAJPayv2z=aNuvGgoA+zwRpLFct1f3FRioHGTC_wZM8ZcU8tnwQ@mail.gmail.com"
type="cite">
<div dir="ltr">
<div>
<div class="gmail_default"><font size="4"> This is much
earlier than anybody thought just 5 years ago.</font></div>
</div>
</div>
</blockquote>
<br>
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. <br>
<br>
<br>
<pre class="moz-signature" cols="72">--
Dr Anders Sandberg
Future of Humanity Institute
Oxford Martin School
Oxford University</pre>
</body>
</html>