NP search problems solvable in quantum polytime but not classically, relative to a random oracle
StefanoGogioso · x · 2026-11-10
Stefano Gogioso highlights the key context for the Aaronson–Ambainis discussion: Yamakawa & Zhandry's "Verifiable Quantum Advantage without Structure" (arXiv:2204.02063) shows that, relative to a random oracle, there are NP search problems in FBQP but not FBPP. This yields functions that are one-way/collision resistant against classical adversaries yet easily inverted by quantum ones; replacing the random oracle with a concrete cryptographic hash gives plausible Minicrypt instantiations. Quoted addendum: they even showed exponential quantum query speedups on random inputs for search (not decision) problems.
More from Research
- billion-context: open-source gene expression tokenizer hits 92.4% accuracy on cell-type classification — udmrzn · 2026-11-10
- NVIDIA and Lilly jointly hiring for Bay Area AI drug discovery lab — BenBlaiszik · 2026-11-10
- Stanford's MessyMem (CoRL 2026): persistent memory lets mobile robots reuse experience — leto__jean · 2026-11-10
- Hugging Face now previews 3D models in-browser, with 350+ 3D datasets to explore — lhoestq · 2026-11-10
- New topical review: Deep Learning Theory through the Lens of Statistical Physics — udmrzn · 2026-11-10
- AgenticGenTAMP: coding agents synthesize reusable TAMP policies across 28 simulated environments — tomssilver · 2026-11-10