Thursday, 9 July 2015

Breaking NP-completeness without quantum?

Early days, but this is a potential bomb.

Memcomputing NP-complete problems in polynomial time using polynomial resources and collective states

If we solve NP-complete efficiently then we may break TSP and all sorts of magical optimisation problems joyously drop out of the sky at our feet. It is not clear if this would also break integer factorisation and thus RSA, but perhaps it might.[2]

A slightly updated version (7 July 2015) of this paper is available on arxiv here.

In the the abstract you'll read this,
"We show an experimental demonstration of an actual memcomputing architecture that solves the NP-complete version of the subset sum problem in only one step and is composed of a number of memprocessors that scales linearly with the size of the problem."
That makes the paper exciting.

This is perhaps a little bit beyond factoring the number 15, as IBM did with a quantum implementation in 2001, but the smallishly sized subset-sum problem (SSP) example in the paper is nevertheless toyish. Popping out a magical solution to SSP doesn't necessarily mean that the reduction mechanism can be used for all NP-complete brethren.

There has been much noise and history in this space that has collapsed on further inspection, especially regarding physical models of computation.

You can read Aaronson's 2005 survey paper on various techniques for solving NP-complete problems in polynomial time which is critical of all techniques including quantum. The community now seems convinced quantum may indeed work so perhaps Aaronson has to be taken with a grain of salt. Update: See [1][4]

A critical review of the Memcomputing paper by Igor Markov that cites Aaronson's paper was published on 22nd April 2015.

When I tweeted about the SSP paper @jhonline92 quickly noted: potential issues with time / space complexity; if SSP is always solved; and, if other NP-complete problems could be similarly reduced in this model. Very good points and those issues are consistent with the critical review from Markov above.

D-Wave is arguably not a true quantum computer in that it couldn't run Shor's algo for factoring though Shor's algo is perhaps not the only way to factor and thus break RSA. Likewise, to be useful perhaps not all NP-complete problems may need to be solved for a memprocessor.

Extraordinary claims need extraordinary proof. There should be some scepticism about the SSP memcomputing paper as it may just be another notch in the belt of history regarding failed analogue attempts to breakdown NP-complete. It is different though. Is it different enough?

Let's see what happens...


PS: Well, that escalated quickly. A few thousand people read this last night and some provided some healthy commentary. The conclusion voiced being that the SSP paper above doesn't really stand up and it is another failed analogue attempt at breaking down NP-complete as consistent with Aaronson's point of view.

[1] Update: Here is Scott Aaronson's well written blog with specific consideration and refuting of the Memcomputing SSP paper. Interestingly in that blog post Aaronson holds his line on the belief that quantum computing will also not work for NP-complete problems which seems reasonable.
[2] Update: I'm told that integer factorisation will break if NP-complete breaks, so yeah, RSA would also fall.
[3] Update: A simplified summary by Scott Aaronson from SciAm and references to his BQP notes in his lecture notes.
[4] Update: I've misunderstood Aaronson. He is supportive of quantum for factorisation (as part of BQP) but points out that quantum will not be able to do NP-complete and I've not seen any reference to work suggesting otherwise.


  1. > The community now seems convinced quantum may indeed work...

    Can you provide a link which documents that the community thinks that? Aside from the adiabatic algorithm, I'm not aware of any such evidence, and the adiabatic algorithm may suffer from exponentially small spectral gaps.

    1. I don't have any special insight. It just represents the impression I have from news, funding allocations, and research activity.

      I value the reputations of groups such as:
      CQC2T from press such as Computer World article on UNSW team


      IBM PR

      Empirically, your implication is right. There is no imminent danger of quantum computers breaking out, but there is significant activity suggesting something real to the efforts.

      Then again, there is much to-do regarding Bitcoin and that emperor definitely has no clothes...

  2. The paper admits they can't solve NP-complete problems, but tries to handwave it away.

    "At the output, we have an exponentially decreasing probability of finding one solution of the SSP when we implement the algorithm by brute force, that is, without any error-correcting coding. However, from the Shannon theorem, there exists a code that allows us to send the required information with bounded error. The question then is whether there is a polynomial code that accomplishes this task. We briefly discuss the question here heuristically. If our machine were Turing-like, then the polynomial code could exist only if N P = P. Instead, our machine is not Turing-like, and the channel can perform an exponential number of operations at the same time. Because this is similar to what quantum computing does when solving difficult problems such as factorization, and we know that for quantum computing polynomial correcting codes do exist (9), we expect that similar coding can be applied to our specific machine as well."

    1. Yep. Makes you wonder how it passed review.

  3. I'm getting that tickle in my brain, like God just told me the biggest joke ever. The security cameras are swiveling in my direction. Time to pull all my money out of bank accounts and run away on a spaceship.

  4. Didn't know something like this ever exist, great ....