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.
Comments
Extended version of manuscript accepted for publication at EuroQHPC2026 workshop at EURO-PAR 2026
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.
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.
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.
Practical realizations of quantum computers are poised to deliver outstanding computational capabilities far beyond the reach of any classical supercomputer. While classical systems are reliably implemented using CMOS technology, the fabrication of quantum hardware has not yet reached a commercially viable level of maturity. Nowadays, many different technologies are being developed as competing candidates to build the first error-corrected quantum computer. Among the software resources required to operate such a system, quantum compilers translate a high-level description of a quantum algorithm into low-level, technology-dependent quantum instructions. Many quantum algorithms, including Shor's and Grover's algorithms, require to compute some classical logic functions on the quantum computer. The first part of this thesis deals with the problem of compiling quantum circuits that perform such classical Boolean functions, called oracles, into a fault-tolerant set of instructions. Oracle circuits often demand many resources in terms of the number of qubits and gates. The focus is on compiling quantum circuits starting from multi-level logic networks representing large Boolean functions while minimizing the resource footprint of the obtained quantum circuits. At the same time, the trade-off between memory resources and the number of operations typical of such a compilation process is explored. As part of the effort in reducing the resources required to perform a given quantum program, I also present some quantum circuit optimization techniques. The researched algorithms leverage data structures and techniques borrowed and adapted from classical logic synthesis, e.g., SAT solvers, LUT mapping, and multi-level logic networks. I implemented all the compilation algorithms presented in this thesis as part of open-source projects. In particular, I develop and maintain caterpillar---a C++ header-only library dedicated to the quantum compilation of oracles and quantum memory management. The second part of this thesis describes how to equip quantum programming language compilers with automatic accuracy management. Despite the availability of many of such languages, resource estimation of quantum algorithms does not yet support taking approximation errors into account. This general methodology is applicable to any programming language and I demonstrate its integration into the Q# compiler. The technique consists of providing language support to ease the accuracy-aware programming task. The user can define accuracy parameters that will be automatically optimized according to a constraint and a cost function directly generated from the source code. In the presented practical evaluations, the constraint function is the overall allowed accuracy, while the cost function is application-dependent and related to the number of gates. During the optimization process, such functions are evaluated hundreds of times. For this reason, we extract them as (near-)symbolic expressions, whose evaluation time does not depend on the quantum algorithm size. The algorithms and the methodologies presented in this thesis are part of a widespread effort of the research community to build a complete and efficient software stack to program and control the first practical universal quantum computer.
Quantum computing has already been explored in several network-security applications. However, how quantum computing may contribute to network-security classification in both the near term and the longer term has not been systematically discussed. This paper studies this question through two complementary experiments. First, we evaluate near-term quantum-kernel support vector machines (SVMs) on practical network-security classification tasks and compare them with classical SVM baselines on KDD Cup 1999, CICIDS2017, and BoT-IoT. Across these runs, quantum kernels are competitive. They can match or improve classical baselines in some settings, while classical RBF kernels remain stronger in others. This suggests that near-term quantum-kernel methods should be evaluated as practical, dataset-dependent alternatives to classical kernels rather than as uniformly superior replacements. Second, we use quantum oracle sketching (QOS) to study a longer-term memory advantage for classification with streaming classical samples. In QOS, samples are processed online and used to incrementally construct an approximate quantum oracle, which provides coherent query access for downstream quantum algorithms without retaining the entire dataset. Under the QOS-inspired machine-size estimate, comparable accuracy corresponds to a substantially smaller effective memory-size proxy than explicit sparse/QRAM-style storage. Compared with a simple streaming proxy, the result is more nuanced because aggressive feature filtering can make the streaming dimension small. This suggests that the long-term value of quantum computing for network-security classification may lie in memory-efficient data access rather than immediate runtime speedup. Together, these experiments show how quantum computing may contribute to network-security classification from near-term classification performance and longer-term memory efficiency.