跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.21500 · v1

Exponential Quantum Memory Advantage for Late-Graph Smoothness and Spectral Estimation

首次提交 2026-11-17 02:00
版本更新 2026-11-17 02:00
雷达观测 2026-11-17 16:10
arXiv ↗PDF ↗

摘要

Graph signal processing tests how smoothly the decisions of next-generation massive sensor networks with NN nodes vary over their neighbour graph. Memory becomes the bottleneck when the neighbour graph arrives only after data erasure, a late-graph setting motivated by dispersed sensor networks and telemetry. We analyse three collection scenarios, reliable rounds, continuous broadcast and ordered capture, and test the Dirichlet energy EG=zTLz/N\mathcal E_G=\mathbf z^{\mathsf T}\mathbf L\mathbf z/N of the fused decision map z∈{±1}N\mathbf z\in\{\pm1\}^N, with late-graph Laplacian L\mathbf L, against two thresholds. Hidden Matching uses O(log⁡N)O(\log N) qubits on fused bits, but in reliable rounds and continuous broadcast, where nodes report bb sub-bits separately, a classical record buffer before it uses O(Nb)O(N b) bits; classical methods need Ω(N)Ω(\sqrt N) bits in the worst case. The recently introduced Quantum Oracle Sketching builds quantum oracles from random data streams without storing them. We combine coherent loading of separately reported sub-bits, exact in reliable rounds and by Quantum Oracle Sketching in continuous broadcast, with nonlinear fusion and Hidden Matching readout. The register count RR does not grow with NN, and the memory is O(log⁡N)O(\log N) logical qubits and classical bits, at fixed bb, graph bounds, thresholds and error targets: an exponential memory advantage over every classical receiver and over Hidden Matching with that buffer. We prove unbiasedness in reliable rounds, preparation bounds in continuous broadcast, classical lower bounds and, for a planner-supplied multi-hop coefficient stream, spectral error bounds. Broadcast simulations match analytic averages at N=1024N=1024, without resolved bias growth up to N=220N=2^{20}. Fault-tolerant hardware, gate rates and, in continuous broadcast, report counts remain open.

作者备注:19 pages, 8 figures

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-17 02:00 · 最新观测版本

Exponential Quantum Memory Advantage for Late-Graph Smoothness and Spectral Estimation

Graph signal processing tests how smoothly the decisions of next-generation massive sensor networks with NN nodes vary over their neighbour graph. Memory becomes the bottleneck when the neighbour graph arrives only after data erasure, a late-graph setting motivated by dispersed sensor networks and telemetry. We analyse three collection scenarios, reliable rounds, continuous broadcast and ordered capture, and test the Dirichlet energy EG=zTLz/N\mathcal E_G=\mathbf z^{\mathsf T}\mathbf L\mathbf z/N of the fused decision map z∈{±1}N\mathbf z\in\{\pm1\}^N, with late-graph Laplacian L\mathbf L, against two thresholds. Hidden Matching uses O(log⁡N)O(\log N) qubits on fused bits, but in reliable rounds and continuous broadcast, where nodes report bb sub-bits separately, a classical record buffer before it uses O(Nb)O(N b) bits; classical methods need Ω(N)Ω(\sqrt N) bits in the worst case. The recently introduced Quantum Oracle Sketching builds quantum oracles from random data streams without storing them. We combine coherent loading of separately reported sub-bits, exact in reliable rounds and by Quantum Oracle Sketching in continuous broadcast, with nonlinear fusion and Hidden Matching readout. The register count RR does not grow with NN, and the memory is O(log⁡N)O(\log N) logical qubits and classical bits, at fixed bb, graph bounds, thresholds and error targets: an exponential memory advantage over every classical receiver and over Hidden Matching with that buffer. We prove unbiasedness in reliable rounds, preparation bounds in continuous broadcast, classical lower bounds and, for a planner-supplied multi-hop coefficient stream, spectral error bounds. Broadcast simulations match analytic averages at N=1024N=1024, without resolved bias growth up to N=220N=2^{20}. Fault-tolerant hardware, gate rates and, in continuous broadcast, report counts remain open.

查看此版本解读 →查看此版本原文 ↗