Quantum Speedups Require Structure or Depth

Guy Blanc, Jordan Docter, Carmen Strassle +1

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…