Preprint
Aug 2026
Quantum Speedups Require Structure or Depth
One of the most basic conjectures in quantum complexity theory states that every $t$-query quantum algorithm can be simulated on most inputs by a $\mathrm{poly}(t)$-query classical algorithm. If true, this would provide broad justification for the need for structure in quantum speedups. We settle this conjecture for pa...
Guy Blanc, Jordan Docter, Carmen Strassle et al.
· 2 citations
· ⚡1