Two QCMA-complete problems

MaRDI QIDQ3522461zbMATH OpenFDO

Authors Pawel Wocjan, Dominik Janzing, Thomas Beth

Publication date 3 September 2008

Full work available at URL https://arxiv.org/abs/quant-ph/0305090

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Quantum computation (81P68) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• The Complexity of the Local Hamiltonian Problem
• "NON-IDENTITY-CHECK" IS QMA-COMPLETE
• QMA with subset state witnesses
• Quantum versus classical proofs and advice

Cited in

(15)

• Characterising the intersection of QMA and coQMA
• Total functions in QMA
• QMA with subset state witnesses
• QMA with subset state witnesses
• Quantum versus classical proofs and advice
• Exact non-identity check is NQP-complete
• Testing non-isometry is QMA-complete
• Quantum SAT for a Qutrit-Cinquit Pair Is QMA 1-Complete
• scientific article; zbMATH DE number 5320331 (Why is no real title available?)
• Consistency of Local Density Matrices Is QMA-Complete
• On perfect completeness for QMA
• "NON-IDENTITY-CHECK" IS QMA-COMPLETE
• StoqMA meets distribution testing
• Guidable local Hamiltonian problems with implications to heuristic ansatz state preparation and the quantum PCP conjecture
• Quantum sat problems with finite sets of projectors are complete for a plethora of classes

This page was built for publication: Two QCMA-complete problems

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