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 search space $N$, i.e., an exponential speedup. Yet, standard quantum theory forbids such a unknown-state reflection (no-reflection theorem). We therefore build a state-learning-assisted architecture, called ``amplify-learn,'' which alternates the coherent…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2601.12651
curl -X POST /api/v1/records/arxiv/2601.12651/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2601.12651/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'