Learning at the Edge of Causality: Optimal Learning-Sample Complexity from No-Signaling Constraints
What ultimately fixes the sample cost of quantum learning -- algorithmic ingenuity or physical law? We study this question in an arena where computation, learning, and causality collide. A twist on Grover's search that reflects about an a priori unknown state can collapse the query complexity from $O(\sqrt{N})$ to $O(\log N)$ over a...