QMA with subset state witnesses

DOI10.4086/CJTCS.2016.004MaRDI QIDQ2808530zbMATH OpenOpenAlexFDO

Authors Alex Bredariol Grilo, Iordanis Kerenidis, Jamie Sikora

Publication date 24 May 2016

Published in Chicago Journal of Theoretical Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/cjtcs.2016.004

zbMATH Keywords

computational complexityquantum computation

Mathematics Subject Classification ID

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

Recommendations

• QMA with subset state witnesses
• Two QCMA-complete problems
• Quantum vs. classical proofs and subset verification
• On perfect completeness for QMA
• On the power of a unique quantum witness

Cites work

• scientific article; zbMATH DE number 5320237 (Why is no real title available?)
• Achieving perfect completeness in classical-witness quantum Merlin-Arthur proof systems
• On perfect completeness for QMA
• Probabilistic checking of proofs
• Proof verification and the hardness of approximation problems
• Testing product states, quantum Merlin-Arthur games and tensor optimization
• Two QCMA-complete problems
• Two-Message Quantum Interactive Proofs Are in PSPACE

Cited in

(7)

• On the power of a unique quantum witness
• Quantum vs. classical proofs and subset verification
• QMA with subset state witnesses
• The role of piracy in quantum proofs
• QMA-hardness of consistency of local density matrices with applications to quantum zero-knowledge
• StoqMA meets distribution testing
• Quantum generalizations of the polynomial hierarchy with applications to \(\mathrm{QMA(2)}\)

This page was built for publication: QMA with subset state witnesses

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