Learning at the Edge of Causality: Optimal Learning-Sample Complexity from No-Signaling Constraints
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917209601736704 |
|---|---|
| author | Bang, Jeongho Cho, Kyoungho Jae, Jeongwoo |
| author_facet | Bang, Jeongho Cho, Kyoungho Jae, Jeongwoo |
| contents | 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 amplitude amplification with state learning. Embedding this amplify-learn into the Bao-Bouland-Jordan no-signaling framework, we show that the logarithmic-round dream would open a super-luminal communication channel unless each round expends the learning-sample and reflection-circuit budgets scaling at least as $Ω(\sqrt{N}/\log N)$. In parallel, we derive tight computational learning-theoretic sample bounds for learning circuit-generated pure states, revealing a state-universal ansatz ``lock'' at order $N$ in the worst case. The dramatic closure is that no-signaling does not merely veto the unphysical primitive, but it fixes the only consistent reflection-circuit complexity, and feeding this causality-enforced complexity into the computational learning bound makes it collapse onto the very same $\sqrt{N}/\log N$ scaling demanded by no-signaling alone. No-signaling thus acts as a regulator of learnability: a constraint that mediates between physics and computation, welding query, gate, and sample complexities into a single causality-compatible triangle. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_12651 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Learning at the Edge of Causality: Optimal Learning-Sample Complexity from No-Signaling Constraints Bang, Jeongho Cho, Kyoungho Jae, Jeongwoo Quantum Physics 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 amplitude amplification with state learning. Embedding this amplify-learn into the Bao-Bouland-Jordan no-signaling framework, we show that the logarithmic-round dream would open a super-luminal communication channel unless each round expends the learning-sample and reflection-circuit budgets scaling at least as $Ω(\sqrt{N}/\log N)$. In parallel, we derive tight computational learning-theoretic sample bounds for learning circuit-generated pure states, revealing a state-universal ansatz ``lock'' at order $N$ in the worst case. The dramatic closure is that no-signaling does not merely veto the unphysical primitive, but it fixes the only consistent reflection-circuit complexity, and feeding this causality-enforced complexity into the computational learning bound makes it collapse onto the very same $\sqrt{N}/\log N$ scaling demanded by no-signaling alone. No-signaling thus acts as a regulator of learnability: a constraint that mediates between physics and computation, welding query, gate, and sample complexities into a single causality-compatible triangle. |
| title | Learning at the Edge of Causality: Optimal Learning-Sample Complexity from No-Signaling Constraints |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2601.12651 |