**UPDATE:** A bug has been found in the proof, the paper has been withdrawn.

—

It has long been known, that if an all-powerful quantum wizard called Merlin can convince a quantum verifier called Arthur of some statement by sending a single quantum message, then a classical computer by itself can compute the same result in exponential time . The game changes, though, if two independent quantum Merlins send a message to Arthur. It was not clear if in this case a classical computer can simulate this situation in less than *double* exponential time !

Today I have shown, that indeed even the latter situation can be simulated by a classical computer in at most exponential time. Eventhough the two scenarios are still *not* known to be equivalent in terms of certain other complexity measures, at least for the practical purpose of simulation on a classical computer in the shortest possible time, they are – up to our best current knowledge – of comparable difficulty.

In particular, the important *Pure State N-Representability* problem in quantum chemistry is now known to be solvable in at most exponential time.

For details, please find my paper here: http://arxiv.org/abs/1510.08447

### Like this:

Like Loading...

Pingback: Shtetl-Optimized » Blog Archive » A breakthrough on QMA(2)