Parallel Quantum Advantage with Limited Adaptivity Requires Structure
The work investigates whether quantum algorithms with parallel queries or limited adaptivity can achieve exponential speedups universally. The findings show that such advantages only occur when inputs have underlying structure, specifically by proving simulation theorems for parallel-query and constant-round parallel-query algorithms. This establishes that quantum advantage is conditional on input density and algorithmic structure.