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

1 Comment

Filed under Science

One response to “Wrestling with two quantum Merlins

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s