QMA with Subset State Witnesses

DOI10.1007/978-3-662-48054-0_14zbMath1465.68096arXiv1410.2882OpenAlexW1548627985MaRDI QIDQ2946385

Iordanis Kerenidis, Alex Bredariol Grilo, Jamie Sikora

Publication date: 16 September 2015

Published in: Mathematical Foundations of Computer Science 2015 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items

QMA with Subset State Witnesses

Cites Work

• Quantum Arthur-Merlin games
• Complexity Classification of Local Hamiltonian Problems
• QMA with Subset State Witnesses
• Stronger methods of making quantum interactive proofs perfectly complete
• Proof verification and the hardness of approximation problems
• Probabilistic checking of proofs
• Two-Message Quantum Interactive Proofs Are in PSPACE
• The detectability lemma and quantum gap amplification
• Product-state approximations to quantum ground states
• The complexity of theorem-proving procedures
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item