QLunch: Itai Leigh

Speaker: Itai Leigh

Title: Quantum Merlin-Arthur with an Internally Separable proof

Abstract: Quantum complexity investigates the computational power of models allowing quantum information and computation in various settings, which allows for a new perspective to probe the very nature of quantum phenomena. One of the simplest models of computation is QMA -- an all-powerful but untrustworthy Merlin gives a "proof" to try convincing Arthur of a claim. This proof is just a quantum state and Arthur is allowed to perform quantum computation using this state in order to decide whether the given state actually proves the claim. This framework can be used to compare properties of quantum states by restricting Merlin to send only proofs satisfying different ones and noting the change in the complexity power of the resulting models.

One of the earlier proposed such properties was to require two unentangled proofs, with the corresponding class denoted by QMA(2). Although this class is more than 20 years old, we still do not have any bound on it beyond the trivial QMA and NEXP. Essentially the question is "what is the proof-power of unentanglement?"

 [Jeronimo-Wu'23] Showed that if Merlin's two unentangled proofs are also both restricted to be of real non-negative amplitudes (in the computational basis decomposition), then the complexity power is QMA+(2)=NEXP. [Bassirian-Fefferman-Marwaha'23] showed the NEXP power is gained already by a single non-negative amplitudes proof QMA+=NEXP, so this in fact does not reflect on the proof-power of unentanglement.

In this work we show an entanglement structure for which a single proof results in a class contained in EXP, while two unentangled proofs achieve NEXP, demonstrating a strict complexity power for unentanglement (assuming EXP is not NEXP).

Joint work with Roozbeh Bassirian, Bill Fefferman, Kunal Marwaha and Pei Wu https://www.arxiv.org/abs/2410.19152