# Wrestling with two quantum Merlins

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 $O(2^n)$. 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 $O(2^{2^{n}})$!

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