Impossibility of succinct quantum proofs for collision-freeness

MaRDI QIDQ3166192zbMATHFDO

Authors Scott Aaronson

Publication date 21 October 2012

zbMATH Keywords

query complexitypolynomial methodcollision problemQMA

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68)

Recommendations

• Quantum lower bounds for the collision and the element distinctness problems
• Quantum lower bound for the collision problem with small range
• Quantum collision-resistance of non-uniformly distributed functions
• Quantum versus classical proofs and advice
• The need for structure in quantum speedups

Cited in

(13)

• Quantum lower bounds for approximate counting via Laurent polynomials
• Conditional disclosure of secrets: amplification, closure, amortization, lower-bounds, and separations
• Public-coin statistical zero-knowledge batch verification against malicious verifiers
• An exponential separation between MA and AM proofs of proximity
• An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity
• Approximate Degree in Classical and Quantum Computing
• Zero-knowledge proofs of proximity
• The NISQ complexity of collision finding
• scientific article; zbMATH DE number 7716601 (Why is no real title available?)
• A nearly optimal lower bound on the approximate degree of \(\mathrm{AC}^0\)
• Quantum commitments from complexity assumptions
• The polynomial method strikes back: tight quantum query bounds via dual polynomials
• On the power of statistical zero knowledge

This page was built for publication: Impossibility of succinct quantum proofs for collision-freeness

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