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.
Broadly applicable quantum advantage, particularly in classical data processing and machine learning, has been a fundamental open problem. In this work, we prove that a small quantum computer of polylogarithmic size can perform large-scale classification and dimension reduction on massive classical data by processing samples on the fly, whereas any classical machine achieving the same prediction performance requires exponentially larger size. Furthermore, classical machines that are exponentially larger yet below the required size need superpolynomially more samples and time. We provide evidence for these quantum advantages in real-world applications, including single-cell RNA sequencing and movie review sentiment analysis, demonstrating four to six orders of magnitude reduction in size with fewer than 60 logical qubits. These quantum advantages are enabled by quantum oracle sketching, an algorithm for accessing the classical world in quantum superposition using only random classical data samples. Combined with classical shadows, our algorithm circumvents the data loading and readout bottleneck to construct succinct classical models from massive classical data, a task provably impossible for any classical machine that is not exponentially larger than the quantum machine. These quantum advantages persist even when classical machines are granted unlimited time or if BPP = BQP, and rely only on the correctness of quantum mechanics. Together, our results establish machine learning on classical data as a broad and natural domain of quantum advantage and a fundamental test of quantum mechanics at the complexity frontier.
[Zha+26] introduce quantum oracle sketching (QOS), a streaming algorithm that constructsan approximate phase oracle of a Boolean function f : [N] → {0, 1} from M =Θ(NQ2/ε) classical samples and then executes any quantum query algorithm of complexityQ on the sketched oracle. Combined with an interferometric variant of classical shadowtomography, QOS yields exponential separations in machine size between quantum and classicallearners for linear systems, classification, and dimensionality reduction. The argumentis information–theoretic and unconditional, depending only on quantum mechanics.This work offers a rigorous critique and constructive extension. We (i) sharpen the diamond–norm guarantee using non–commutative matrix Bernstein, recovering the linear N/Mbias scaling without the spurious logarithmic factor and with explicit constants; (ii) recastthe optimal Q2 scaling as a quantum Cram´er–Rao bound on the symmetric–logarithmic–derivative (SLD) Fisher information of the random oracle channel; (iii) generalize QOSto non–uniform priors by showing that sample complexity is governed by the effective dimensionNeff = ∥p∥21/2, allowing genuine improvements when data are heavy–tailed; (iv) replacethe hard spectral–gap assumption in PCA by a polynomial–filter analysis that pays onlyquadratically in the soft gap; (v) building on the parallel manuscript of [Sep26], extendQOS to non–linear kernel learning via random Fourier features, deriving the explicit samplecomplexity for shift–invariant kernels via an independent route and connecting it to the information–geometric framework of (ii) and the effective–dimension framework of (iii); (vi) provethat QOS is structurally compatible with R´enyi differential privacy, achieving a per–sampleprivacy budget that scales as ε2DP = Θ(1/(NM)); (vii) analyse a hybrid scheme that pre—composes QOS with a Johnson–Lindenstrauss embedding, isolating the regimes in which thequantum advantage survives classical compression; (viii) building further on [Sep26], give amatrix Bernstein proof of the QOS noise threshold pg ≲ ε2/(NQ2) with explicit constants,and pose the matching tight–threshold question as an open problem alongside the recentnoisy–random–circuit obstruction [Aha+23]. We close with a candid critique of the resourceaccounting underlying the “60–logical–qubit” demonstration and a list of open problems insoft–gap, non–Hermitian, and continuous–domain QOS.
Classical-to-quantum I/O is a critical bottleneck for data-intensive quantum workloads. Quantum Oracle Sketching (QOS) has been proposed to address this problem. We identify its practical requirements, including the representation of data as a probability distribution over oracle addresses, the relation between sample count, approximation error, and update cost, and the coherence and runtime support required for online execution. To study QOS on current quantum computing devices, we develop an offline realization that compiles sample blocks into empirical phase oracles and evaluate it using DNA fingerprinting. The application converges with relatively few samples, while exact phase fusion combines repeated updates to the same address. However, the compiled circuits remain too deep for current quantum computing devices. Practical QOS therefore requires lower depth oracle synthesis and interactive quantum runtimes.
Shadow Tomography is a fundamental problem in quantum information theory. Given multiple copies of an unknown d-dimensional quantum state ρ and a known collection of observables E1,…,EM, the goal is to estimate all expectation values {Tr(ρEi)}i=1M to additive accuracy ε with probability at least 1−δ.
An elusive open question from the seminal shadow tomography work of Aaronson is whether this task admits a dimension-independent sample complexity with only polylogarithmic dependence on M, as suggested by the best-known lower bounds. In this work, we propose two different quantum protocols for shadow tomography with the best sample complexity O(ε2log(M)log(M/δ)), which is polylogarithmic in the number of observables and independent of the dimension of the unknown state, thereby answering Aaronson's original question while also providing an exponential improvement in the prior best dimension independent sample complexity of shadow tomography from Sinha (STOC 2025) and, more recently, Chen, O'Donnell, Pelecanos, and Wright.
Our approach first reduces the general shadow tomography problem to a finite-ensemble estimation problem via a minimax argument. We then develop an observable-independent protocol that repeatedly applies the pretty-good measurement while updating the prior distribution over the finite ensemble according to the measurement outcomes. A tail analysis of the resulting estimation error yields simultaneous accuracy guarantees for all observables and a cubic-logarithmic upper bound. We also introduce a refined recovery-label measurement for the same finite ensemble, which yields the bound in our main theorem.
Efficiently learning expectation values of unknown quantum states via classical shadows has become an important primitive in both theoretical and experimental aspects of quantum computation. Typically, classical shadow protocols involve randomised measurements induced by sampling uniformly randomly from a compact group, a situation which is now quite well understood. In this work we go beyond this standard assumption, studying the classical shadow protocols occasioned by sampling uniformly randomly from the so-called compact symmetric spaces. We uncover a unifying theory of such protocols, extending the extent to which the general theory of classical shadows is understood at a mathematical level. Interestingly, for the estimation of observables sampled from certain distributions we further find that some of these protocols allow for slight improvements in sample-complexity over existing shadow schemes. As part of our technical analysis we obtain ε-approximate relative-error k-designs over the n-qubit symplectic group in depth O(nk+log(1/ε)), which is optimal with respect to n, and may be of some independent interest.
This record contains the main manuscript and technical supplement for Quantum Oracle Sketching from Correlated Classical Samples. The manuscript develops a constructive conditional framework for compiling quantum-oracle-sketching interfaces from correlated classical samples. Under explicit additional assumptions, it addresses complete aligned IID refresh blocks, observable variance certificates, repeated-use oracle composition, total sparse access, norm-safe block encodings, and static finite-list PCA. The work is logically separate from the version-specific audit in the companion record Exact Counterexamples and Interface Gaps in Quantum Oracle Sketching. It does not claim to retroactively establish the arguments in arXiv:2604.07639v1; rather, it presents conditional constructions and explicit interface requirements under which related results can be recovered. The accompanying technical supplement provides complete proofs, imported-theorem contracts, and typed resource ledgers.