The procedure of Lemma 15 is specifically designed in such a way that, if the promise is violated, then it doesn’t matter which answer is returned. If “no,” then you’ll just look elsewhere for the great measurement that’s guaranteed to exist. If “yes,” then you may keep looking in this region, where a measurement necessarily exists that’s *almost* as good as the best one.

Thanks!

]]>Is this a purely engineering problem, or could it be that nature makes it an extremely hard thing to do at a fundamental level (a bit like the non-cloning theorem and such)?

]]>We also know that for the true complexity of computing the permanent to be 2^n we need that it’s no easier to count the number of matchings in a bipartite graph than in a general graph. This is because there is a 2^n time algorithm for the latter problem. This seems surprising, if true.

]]>(In a sense, the problem where I had to put 0s on the diagonal is just a special case of this — a fixed point is just a type of odd cycle, after all. But that was only enough to get things up by 4×4…)

]]>What’s odd though is that for a 4×4 symmetric matrix with 0s on the diagonal, the permanent *is* the Hafnian squared. (And also trivially for 2×2 and 0x0, but nothing surprising there.) Like, just write them out as polynomials, one is the square of the other. And yet for higher numbers it doesn’t work. I don’t know what to make of that.

http://www.mercurynews.com/2017/11/10/ibm-ups-pressure-on-rivals-with-quantum-computer-prototype-2/

]]>