QMA with subset state witnesses

DOI10.4086/CJTCS.2016.004zbMATH Open1356.68081OpenAlexW2970305865MaRDI QIDQ2808530FDOQ2808530

Jamie Sikora, Alex Bredariol Grilo, Iordanis Kerenidis

Publication date: 24 May 2016

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

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

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

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)

Cites Work

• Proof verification and the hardness of approximation problems
• Probabilistic checking of proofs
• Two-Message Quantum Interactive Proofs Are in PSPACE
• Testing Product States, Quantum Merlin-Arthur Games and Tensor Optimization
• Title not available (Why is that?)
• Title not available (Why is that?)
• On perfect completeness for QMA
• Two QCMA-complete problems

Cited In (3)

• QMA-Hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge
• Dequantizing the Quantum singular value transformation: hardness and applications to Quantum chemistry and the Quantum PCP conjecture
• 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)