NP vs QMA_(2)

MaRDI QIDQ3400478zbMATH OpenFDO

Authors Salman Beigi

Publication date 5 February 2010

Full work available at URL https://arxiv.org/abs/0810.5109

zbMATH Keywords

Merlin-Arthurseparable states

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Quantum coherence, entanglement, quantum correlations (81P40) Quantum computation (81P68)

Recommendations

• On QMA protocols with two short quantum proofs
• A quantum characterization of NP
• The power of unentanglement
• Quantum information and the PCP theorem
• Improved soundness for QMA with multiple provers

Cited in

(12)

• When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one
• Limitations of semidefinite programs for separable states and entangled games
• Shorter unentangled proofs for ground state connectivity
• Quantum generalizations of the polynomial hierarchy with applications to \(\mathrm{QMA(2)}\)
• On the satisfiability of quantum circuits of small treewidth
• On QMA protocols with two short quantum proofs
• On the power of a unique quantum witness
• A quantum characterization of NP
• Epsilon-net method for optimizations over separable states
• Quantum generalizations of the polynomial hierarchy with applications to QMA(2)
• Approximating the set of separable states using the positive partial transpose test
• Faithful squashed entanglement

This page was built for publication: NP vs QMA\(_{\log}(2)\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3400478)