Query Bounds and Explicit Quantum Circuits for Periodic Weighted Decisions

This paper establishes tight query complexity bounds showing a quadratic separation between randomized classical and quantum algorithms for deciding the sign of periodic weighted sums, and provides explicit quantum circuit constructions with concrete resource estimates that validate these theoretical advantages at large scales.

Original authors: Annan Chen