Become a fan of Slashdot on Facebook

 



Forgot your password?
typodupeerror
DEAL: For $25 - Add A Second Phone Number To Your Smartphone for life! Use promo code SLASHDOT25. Also, Slashdot's Facebook page has a chat bot now. Message it for stories and more. Check out the new SourceForge HTML5 Internet speed test! ×

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

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.

Slashdot Top Deals

We warn the reader in advance that the proof presented here depends on a clever but highly unmotivated trick. -- Howard Anton, "Elementary Linear Algebra"

Working...