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 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 of the fused decision map , with late-graph Laplacian , against two thresholds. Hidden Matching uses qubits on fused bits, but in reliable rounds and continuous broadcast, where nodes report sub-bits separately, a classical record buffer before it uses bits; classical methods need 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 does not grow with , and the memory is logical qubits and classical bits, at fixed , 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 , without resolved bias growth up to . Fault-tolerant hardware, gate rates and, in continuous broadcast, report counts remain open.