{"id":"arxiv/2608.19158","url":"https://arxiv.org/abs/2608.19158","tags":["quant-ph","cs.CC"],"score":0,"title":"Quantum Speedups Require Structure or Depth","domain":"quant-ph","source":"arxiv","authors":["Guy Blanc","Jordan Docter","Carmen Strassle","Li-Yang Tan"],"reviews":0,"subject":"quant-ph","summary":"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 parallel quantum algorithms, showing that every $t$-query $d$-round quantum algorithm can be simulated on most inputs with $t^{O(d^2)}$ classical queries. This suggests that for unstructured problems, superpolynomial speedups would require quantum circuits of superconstant depth,…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-08-19","reactions":{}}