Aaronson–Ambainis conjecture resolved: no exponential quantum speedup for unstructured problems
fortnow · x · 2026-11-09
Lance Fortnow notes the resolution of the Aaronson–Ambainis conjecture confirms what we've known since the 90s: no exponential quantum advantage for non-structured black-box problems. The new result extends this even to algorithms that only need to be correct on most inputs — a theoretical cooldown on quantum-advantage hype.
More from Research
- LoRA-tuned Qwen3 skips first output line whenever the caption is under ~4 tokens — prathamdmehta · 2026-11-09
- Ramez: OpenAI's Productivity Gain Per ECI Point Appears to Decline Over Time — ramez · 2026-11-09
- Betting on transformers: incremental improvements will beat radically new LLM architectures — max_paperclips · 2026-11-09
- FragBench benchmark paper shared, details in the paper itself — arthurcolle · 2026-11-09
- Economist Paul Novosad proposes a 4-step AI-assisted peer review workflow — paulnovosad · 2026-11-09
- CoRL 2026 to host 'Do Robots Need World Models?' debate workshop in Austin — YunzhuLiYZ · 2026-11-09