Quantum versus classical proofs and advice

DOI10.4086/TOC.2007.V003A007MaRDI QIDQ3002783zbMATH OpenOpenAlexFDO

Authors Scott Aaronson, Greg Kuperberg

Publication date 24 May 2011

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NoDerivs 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2007.v003a007

zbMATH Keywords

black-box groupshidden subgroup problemoraclesQMAquantum computing

Mathematics Subject Classification ID

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

Recommendations

• Quantum vs. classical proofs and subset verification
• Quantum proofs
• Two QCMA-complete problems
• On QMA protocols with two short quantum proofs
• Algorithms and Computation

Cited in

(19)

• Quantum commitments from complexity assumptions
• Total functions in QMA
• Two results about quantum messages
• Finite groups and complexity theory: from Leningrad to Saint Petersburg via Las Vegas
• Quantum commitments from complexity assumptions
• Impossibility of succinct quantum proofs for collision-freeness
• The learnability of quantum states
• Two QCMA-complete problems
• On perfect completeness for QMA
• Quantum vs. classical proofs and subset verification
• The complexity of quantum disjointness
• Shadow tomography of quantum states
• Classical verification of quantum proofs
• QMA-hardness of consistency of local density matrices with applications to quantum zero-knowledge
• Non-uniformity and quantum advice in the quantum random oracle model
• Quantum cryptography in Algorithmica
• How to model unitary oracles
• A qubit, a coin, and an advice string walk into a relational problem
• Untelegraphable encryption and its applications

This page was built for publication: Quantum versus classical proofs and advice

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