Expanding Quantum Oracle Sketching and Classical Shadows
Abstract
The recent breakthrough by [Zha+26] demonstrates a provable exponential quantum advantagein processing massive classical data using polylogarithmic quantum space, primarilythrough the innovations of quantum oracle sketching (QOS) and interferometric classicalshadows. This brief manuscript reviews that framework, and as also discussed in the QuantumFrontiers forum [Qua26], and proposes two mathematical extensions: (i) a non–linearkernel–QOS protocol based on random Fourier features, with explicit sample complexity,and (ii) a rigorous noise analysis that distinguishes errors during sketch construction fromerrors during shadow readout. We close with practical implications for hybrid machinelearning pipelines.
The recent breakthrough by [Zha+26] demonstrates a provable exponential quantum advantagein processing massive classical data using polylogarithmic quantum space, primarilythrough the innovations of quantum oracle sketching (QOS) and interferometric classicalshadows. This brief manuscript reviews that framework, and as also discussed in the QuantumFrontiers forum [Qua26], and proposes two mathematical extensions: (i) a non–linearkernel–QOS protocol based on random Fourier features, with explicit sample complexity,and (ii) a rigorous noise analysis that distinguishes errors during sketch construction fromerrors during shadow readout. We close with practical implications for hybrid machinelearning pipelines.
Cite this paper
Sepulveda-Jimenez, Alfredo (2026). Expanding Quantum Oracle Sketching and Classical Shadows. Zenodo.