Stories
Slash Boxes
Comments

SoylentNews is people

SoylentNews is powered by your submissions, so send in your scoop. Only 18 submissions in the queue.
posted by martyb on Saturday October 20 2018, @06:27PM   Printer-friendly
from the quantum-improvement dept.

IBM finally proves that quantum systems are faster than classicals

In 1994, MIT professor of applied mathematics Peter Shor developed a groundbreaking quantum computing algorithm capable of factoring numbers (that is, finding the prime numbers for any integer N) using quantum computer technology. For the next decade, this algorithm provided a tantalizing glimpse at the potential prowess of quantum computing versus classical systems. However, researchers could never prove quantum would always be faster in this application or whether classical systems could overtake quantum if given a sufficiently robust algorithm of its own. That is, until now.

In a paper published Thursday in the journal Science, Dr. Sergey Bravyi and his team reveal that they've developed a mathematical proof which, in specific cases, illustrates the quantum algorithm's inherent computational advantages over classical.

[...] What's more, the proof shows that, in these cases, the quantum algorithm can solve the problem in a fixed number of steps, regardless of how many inputs are added. With a classical computer, the more inputs you add, the more steps it needs to take in order to solve. Such are the advantages of parallel processing.

There's now proof that quantum computers can outperform classical machines

In this paper, the researchers prove that a quantum computer with a fixed circuit depth is able to outperform a classical computer that's tackling the same problem because the classical computer will require the circuit depth to grow larger, while it can stay constant for the quantum computer.


Original Submission

 
This discussion has been archived. No new comments can be posted.
Display Options Threshold/Breakthrough Mark All as Read Mark All as Unread
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
  • (Score: 2) by maxwell demon on Sunday October 21 2018, @05:39AM (5 children)

    by maxwell demon (1608) on Sunday October 21 2018, @05:39AM (#751577) Journal

    No, they didn't. They proved that a quantum computer can solve a problem in constant time for which a classical computer requires logarithmic time. Note that both are in P; no NP problems were involved.

    --
    The Tao of math: The numbers you can count are not the real numbers.
    Starting Score:    1  point
    Karma-Bonus Modifier   +1  

    Total Score:   2  
  • (Score: 2) by bzipitidoo on Sunday October 21 2018, @12:45PM (4 children)

    by bzipitidoo (4388) on Sunday October 21 2018, @12:45PM (#751629) Journal

    No, it's not correct to say both problems are in P. Determining whether a number n is prime is in P.

    But Integer Factorization, the problem of finding the factors of a number that is not prime, may not be in P. No one really knows. No one has found a way to do it in polynomial time with a classical computer, or proven that it can't be done. It's thought not to be in P. It's definitely in NP.

    If they have indeed proven that Integer Factorization is not in P, then they have proven that P!=NP. But I'm skeptical that they have really done that. The writers of the articles don't seem to have realized what such a result means, as they made no mention of the famous P!=NP problem. So, I suspect the reporting is inaccurate. More likely the researchers have shown that, given a few assumptions that boil down to the crucial assumption that P!=NP, or by limiting the classical computer to known factoring algorithms, the quantum computer is superior, in that its memory needs are less. If that's what they have done, then this finding, while somewhat interesting, is not so earth shakingly big, and they have not won that million dollar prize after all.

    • (Score: 2) by maxwell demon on Sunday October 21 2018, @12:51PM (3 children)

      by maxwell demon (1608) on Sunday October 21 2018, @12:51PM (#751630) Journal

      No, it's not correct to say both problems are in P. Determining whether a number n is prime is in P.

      But Integer Factorization, the problem of finding the factors of a number that is not prime, may not be in P.

      Irrelevant because their paper concerned neither determining whether a number is prime, nor factorizing a prime.

      --
      The Tao of math: The numbers you can count are not the real numbers.
      • (Score: 2) by maxwell demon on Sunday October 21 2018, @12:52PM (2 children)

        by maxwell demon (1608) on Sunday October 21 2018, @12:52PM (#751631) Journal

        Err … I of course meant “factorizing a number.” Factorizing a prime is, of course, O(1) even on a classical computer. ;-)

        --
        The Tao of math: The numbers you can count are not the real numbers.
        • (Score: 2) by bzipitidoo on Sunday October 21 2018, @08:09PM (1 child)

          by bzipitidoo (4388) on Sunday October 21 2018, @08:09PM (#751759) Journal

          I read over the summary again, and realized it's more disconnected than I thought. It mentions the groundbreaking Integer Factorization algorithm that runs in polynomial time on a quantum computer. Then it says that some researchers have proven that a quantum computer needs less (algorithmically less) memory than a classic computer to solve a certain class of problems. It doesn't make it too clear they're now talking about another problem in a class that may or may not include Integer Factorization.

          I'd bet a large sum that their result includes the proviso that "if P≠NP" or a more specific "if P≠QP" or "if P≠BQP", and thus they haven't and weren't trying to prove that.

          • (Score: 2) by maxwell demon on Sunday October 21 2018, @09:53PM

            by maxwell demon (1608) on Sunday October 21 2018, @09:53PM (#751780) Journal

            Well, no need to guess; the actual article is linked from the summary. Here's the abstract (direct copy/paste from arXiv):

            We prove that constant-depth quantum circuits are more powerful than their classical counterparts. To this end we introduce a non-oracular version of the Bernstein-Vazirani problem which we call the 2D Hidden Linear Function problem. An instance of the problem is specified by a quadratic form q that maps n-bit strings to integers modulo four. The goal is to identify a linear boolean function which describes the action of q on a certain subset of n-bit strings. We prove that any classical probabilistic circuit composed of bounded fan-in gates that solves the 2D Hidden Linear Function problem with high probability must have depth logarithmic in n. In contrast, we show that this problem can be solved with certainty by a constant-depth quantum circuit composed of one- and two-qubit gates acting locally on a two-dimensional grid.

            --
            The Tao of math: The numbers you can count are not the real numbers.