Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

On the Optimality and Generalization of Quantum Oracle Sketching

Alfredo Sepulveda-Jimenez

Published May 2, 2026• 0 citations
Publisher

Abstract

[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.

DOI
10.5281/zenodo.19985472

Related papers

Expanding Quantum Oracle Sketching and Classical Shadows

Alfredo Sepulveda-Jimenez

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.

•May 2, 2026•0 citations

Exponential quantum advantage in processing massive classical data

Haimeng Zhao, Alexander Zlokapa, Hartmut Neven +4 more

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.

quant-pharXiv:2604.07639•Apr 10, 2026•0 citations

Practical Considerations for Processing Massive Classical Data via Quantum Oracle Sketching

Stefano Markidis

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.

quant-pharXiv:2609.13549•Sep 15, 2026•0 citations

Quantum Oracle Sketching from Correlated Classical Samples

Carmelo Vellón Gascón

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.

•Jul 22, 2026•1 citation

Quantum Sketches, Hashing, and Approximate Nearest Neighbors

Sajjad Hashemian

Motivated by Johnson--Lindenstrauss dimension reduction, amplitude encoding, and the view of measurements as hash-like primitives, one might hope to compress an $n$-point approximate nearest neighbor (ANN) data structure into $O(\log n)$ qubits. We rule out this possibility in a broad quantum sketch model, the dataset $P$ is encoded as an $m$-qubit state $ρ_P$, and each query is answered by an arbitrary query-dependent measurement on a fresh copy of $ρ_P$. For every approximation factor $c\ge 1$ and constant success probability $p>1/2$, we exhibit $n$-point instances in Hamming space $\{0,1\}^d$ with $d=Θ(\log n)$ for which any such sketch requires $m=Ω(n)$ qubits, via a reduction to quantum random access codes and Nayak's lower bound. These memory lower bounds coexist with potential quantum query-time gains and in candidate-scanning abstractions of hashing-based ANN, amplitude amplification yields a quadratic reduction in candidate checks, which is essentially optimal by Grover/BBBV-type bounds.

quant-pharXiv:2602.19259•Feb 24, 2026•0 citations

A provable quantum advantage for approximate optimization via decoded quantum interferometry

Maximilian J. Kramer, Elies Gil-Fuster, Benjamin D. M. Jones +2 more

Decoded quantum interferometry (DQI) is a novel paradigm for tackling approximate optimization problems on quantum computers. This framework comes with strong performance guarantees and exploits a well-established duality between optimization and coding theory. A central question, however, is whether DQI can actually provably outperform all polynomial-time classical algorithms. In this work, we establish such an advantage in an oracle setting: we consider an optimization task called folded optimal polynomial intersection (folded OPI), where the acceptance sets are chosen randomly and accessed through membership oracles. We establish a strict gap between the approximation ratio achievable by any polynomial-time classical algorithm and the approximation ratio achieved by the DQI algorithm. Our proof builds on Jordan et al.'s DQI framework for approximate optimization and extends the classical lower-bound method underlying Yamakawa and Zhandry's exact-search oracle separation to approximation. Building on recent developments by Sun and Wootters, Horinaga and Yamakawa, and Jo, we further show that a modified version of the DQI algorithm achieves a strictly higher score guarantee on typical sampled folded OPI instances. As a concrete example, for code rate $0.3$, DQI achieves expected scores of approximately $0.85$. In contrast, exceeding the classical threshold of $0.65$ by any fixed amount with constant probability on sampled instances requires super-polynomially many classical membership queries.

quant-pharXiv:2610.02145•Oct 2, 2026•0 citations
[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.
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.
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.
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.
Motivated by Johnson--Lindenstrauss dimension reduction, amplitude encoding, and the view of measurements as hash-like primitives, one might hope to compress an nnn-point approximate nearest neighbor (ANN) data structure into O(log⁡n)O(\log n)O(logn) qubits. We rule out this possibility in a broad quantum sketch model, the dataset PPP is encoded as an mmm-qubit state ρPρ_PρP​, and each query is answered by an arbitrary query-dependent measurement on a fresh copy of ρPρ_PρP​. For every approximation factor c≥1c\ge 1c≥1 and constant success probability p>1/2p>1/2p>1/2, we exhibit nnn-point instances in Hamming space {0,1}d\{0,1\}^d{0,1}d with d=Θ(log⁡n)d=Θ(\log n)d=Θ(logn) for which any such sketch requires m=Ω(n)m=Ω(n)m=Ω(n) qubits, via a reduction to quantum random access codes and Nayak's lower bound. These memory lower bounds coexist with potential quantum query-time gains and in candidate-scanning abstractions of hashing-based ANN, amplitude amplification yields a quadratic reduction in candidate checks, which is essentially optimal by Grover/BBBV-type bounds.
Decoded quantum interferometry (DQI) is a novel paradigm for tackling approximate optimization problems on quantum computers. This framework comes with strong performance guarantees and exploits a well-established duality between optimization and coding theory. A central question, however, is whether DQI can actually provably outperform all polynomial-time classical algorithms. In this work, we establish such an advantage in an oracle setting: we consider an optimization task called folded optimal polynomial intersection (folded OPI), where the acceptance sets are chosen randomly and accessed through membership oracles. We establish a strict gap between the approximation ratio achievable by any polynomial-time classical algorithm and the approximation ratio achieved by the DQI algorithm. Our proof builds on Jordan et al.'s DQI framework for approximate optimization and extends the classical lower-bound method underlying Yamakawa and Zhandry's exact-search oracle separation to approximation. Building on recent developments by Sun and Wootters, Horinaga and Yamakawa, and Jo, we further show that a modified version of the DQI algorithm achieves a strictly higher score guarantee on typical sampled folded OPI instances. As a concrete example, for code rate 0.30.30.3, DQI achieves expected scores of approximately 0.850.850.85. In contrast, exceeding the classical threshold of 0.650.650.65 by any fixed amount with constant probability on sampled instances requires super-polynomially many classical membership queries.