betaFeedback

WorksPhysics and Astronomy

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

Abstract

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.

Paper details

vlnc:W_vkv67mj2
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

Not recorded for this paper

View statement
Looking for related papers…