Slashdot Mirror

← Back to Stories (view on slashdot.org)

A Quantum Linear Equation Solver

Posted by kdawson on from the traveling-salesman-gets-a-break dept.

joe writes "Aram Harrow and colleagues have just published on the arXiv a quantum algorithm for solving systems of linear equations (paper, PDF). Until now, the only quantum algorithms of practical consequence have been Shor's algorithm for prime factoring, and Feynman-inspired quantum simulation algorithms. All other algorithms either solve problems with no known practical applications, or produce only a polynomial speedup versus classical algorithms. Harrow et. al.'s algorithm provides an exponential speedup over the best-known classical algorithms. Since solving linear equations is such a common task in computational science and engineering, this algorithm makes many more important problems that currently use thousands of hours of CPU time on supercomputers amenable to significant quantum speedup. Now we just need a large-scale quantum computer. Hurry up, guys!"

5 of 171 comments (clear)

  1. Re:Hm by FrozenFOXX · · Score: 5, Funny

    Is this algorithm in Haskell or somethin'?

    I'll wait until I can program in VB. Will it take long?

    It may or may not.

    --
    "Just a fox, a whisper."
  2. Re:Hm by AdmiralXyz · · Score: 5, Funny

    Quantum computing is nondeterministic and probability-based: when you put in a certain input, you have a finite probability of getting the right answer out, it could just as easily be anything else. So in other words, coming from VB, you'll be at a major advantage.

    --
    Dislike the Electoral College? Lobby your state to join the National Popular Vote Interstate Compact.
  3. Re:Implications by Anonymous Coward · · Score: 5, Funny

    Does this mean they can solve P=NP?

    Yes: N=1.

  4. Avinatan Hassidim and Seth Lloyd by aram.harrow · · Score: 5, Informative
    are my coauthors, and the ordering of author names was alphabetical, and doesn't reflect our level of contributions (which were more or less equal).

    So please cite this as "Harrow, Hassidim and Lloyd" and not "Harrow and coauthors."

    That said, we're pleased about that attention. :)

    In response to one question: the matrix inversion problem for the parameters we consider is (almost certainly) not NP-complete, but instead is BQP-complete, meaning that it is as difficult as any other problem that quantum computers can solve. We plan to update our arXiv paper shortly with an explanation of this point.

  5. Re:Implications by lenester · · Score: 5, Funny

    Oh come on, this deserves +P Funny.