[ExI] Researchers have found a parallel computing algorithm that could offer quantum computer-speed performance

[Anders Sandberg]

On 2010-12-31 04:26, John Grigg wrote:
> I was curious what the computer professionals here thought of this new
> development...
>
> http://nextbigfuture.com/2010/12/esearchers-have-found-parallel.html

Personally I have no clue. Some computer scientist I am :-)

But generally, whenever an algorithmic improvement occurs we ought to 
sit up and take notice. Over the last few weeks I have started 
collecting data and papers on how much improvements of hardware and 
software improve performance of things, and generally software wins. It 
is just that hardware improves rather smoothly most of the time (lots of 
little incremental improvements on a broad front) while software jumps 
ahead rarely but a long distance (it takes rare insights, but then you 
get an order of magnitude or more instantly).

BTW, Scott Aaronson has a paper out that might be of interest here:
http://www.scottaaronson.com/blog/?p=473
It is on the computational complexity of linear optics, and if I get the 
idea, they demonstrate that if there is an efficient way for classical 
computers to simulate a fairly "normal" quantum optical system a lot of 
other hard computational problems can be solved - which can be seen as a 
bet that it is not even possible to simulate this system (or a 
challenge, "I DARE you to efficiently simulate this!")

-- 
Anders Sandberg
Future of Humanity Institute
Oxford University