Impossibility of succinct quantum proofs for collision-freeness

zbMATH Open1268.81044MaRDI QIDQ3166192FDOQ3166192

Authors: Scott Aaronson 

Publication date: 21 October 2012

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

zbMATH Keywords

query complexitypolynomial methodcollision problemQMA

Mathematics Subject Classification ID

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

Cited In (13)

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

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)