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.
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.
This record contains the main manuscript and technical supplement for a version-specific mathematical audit of arXiv:2604.07639v1. The manuscript analyzes the quantum-oracle-sketching proof chain in the public v1 version and identifies exact counterexamples, proof gaps, and interface gaps concerning Theorem D.16/D.99, limited-independence requirements, repeated-use oracle composition, sparse-access interfaces, block-encoding interfaces, and related constructions. The accompanying technical supplement provides exact certificates, repeated-use lemmas, F.23 diagnostics, and a reproducibility protocol. The scope of this record is limited to arXiv:2604.07639v1 and does not assess any later revised version.
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.
[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.
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.
Consider two PAC learning algorithms, both having access to quantum computation, but differing in the types of examples they obtain: one is provided with classical samples, while the other is given quantum samples. Are there any learning tasks that can be efficiently performed by the latter, but not by the former? This question, the focus of our work, is surprisingly still open. Our main result is to show that \emph{relative to an oracle}, there are distributions that can be efficiently generated by a quantum learner with access to quantum samples, but not by a quantum learner with access to only classical samples, making progress to answering this question in the affirmative.
We extend Yamakawa-Zhandry codeword search to graph-correlated predicates in one iid bit oracle. Sequential preparation replaces independent-coordinate preparation; classical list recovery counts active vertices. The scalar theorem has jointly polynomial quantum cost and exp(Ω(λ/log λ)) classical queries for fixed parameters. A folded-dual block refinement replaces the squared-rate restriction by a linear-rate margin, improving the sufficient cutoff and real cap exponent. Its full cost is λO(D+1) poly(Lin+|Γ|), polynomial for fixed degree D; jointly polynomial growing-D time remains open, and its cutoff-boundary classical cap is polynomial. Large-alphabet normalization is a small-error check. These are purely asymptotic results. MSC 2020: 68Q12, 68Q17, 94B35. The accompanying package contains the manuscript source, figures, and integrity manifests.