Want to read Slashdot from your mobile device? Point it at m.slashdot.org and keep reading!

 



Forgot your password?
typodupeerror

Slashdot videos: Now with more Slashdot!

  • View

  • Discuss

  • Share

We've improved Slashdot's video section; now you can view our video interviews, product close-ups and site visits with all the usual Slashdot options to comment, share, etc. No more walled garden! It's a work in progress -- we hope you'll check it out (Learn more about the recent updates).

×

Comment: Re:Comparing Apples to Apples (Score 1) 171

by aram.harrow (#26007989) Attached to: A Quantum Linear Equation Solver
What I'm wondering is whether similarly relaxing the requirements on the classical computation (so that you only require such an approximate solution in the same sense, not an exact solution) will reduce the classical computational complexity of the problem significantly.

We plan to soon update our arxiv post to explain that the matrix inversion problem (with the parameters we consider) is BQP-complete, meaning it is as hard as anything that quantum computers can solve in polynomial time. This is strong evidence that classical computers need exponentially more time to solve the problem in general. Of course, there may be special cases, some of practical interest, where good classical algorithms exist.

The goal of Computer Science is to build something that will last at least until we've finished building it.

Working...