The theory of Quantum Oracle Sketching

Quantum Oracle Sketching attempts to bypass a longstanding problem in quantum algorithms: how can a quantum computer access an enormous classical dataset without first building equally enormous quantum memory or QRAM?

The paper by Zhao and colleagues, posted on 8 April 2026, formulates an answer in the streaming model. The official repository now contains JAX implementations, tutorials, QSVT routines and experiments on datasets including PBMC68k. At the time of our check, the latest public main branch reached commit 10c092c from 21 May 2026, which added sparse Johnson–Lindenstrauss projections to the real-data route.

The data-access problem

Many quantum algorithms assume an oracle: a coherent operation that makes information about a vector, matrix or function accessible in superposition. Such an oracle is not free for classical data. If the entire dataset first has to be loaded into QRAM, the memory benefit can disappear before quantum computation begins.

QOS reverses the order. It receives random classical samples one by one. Each sample controls a small quantum rotation. Accumulating many such updates produces a quantum channel approximating the desired oracle operation. The sample can then be discarded.

Schematically:

sample z1 → small rotation ┐
sample z2 → small rotation ├→ compact quantum sketch → quantum algorithm
sample z3 → small rotation ┘

The quantum state does not store every data point separately. It stores a coherent summary suitable for a subsequent quantum query.

The classification theory

For binary classification, the paper writes the training data as a sparse matrix \(X \in \mathbb{R}^{N \times D}\) with labels \(y_i \in \{-1,+1\}\). The classical reference is a regularised least-squares support vector machine, equivalent to a ridge-like linear classifier:

\[
w = \operatorname*{argmin}_{w}\;\lVert Xw-y\rVert_2^2 + \lambda\lVert w\rVert_2^2.
\]

A new feature vector \(x'\) receives label \(\operatorname{sign}(x' \cdot w)\). QOS constructs quantum oracles with which a quantum linear-algebra algorithm can approximate the relevant decision information without storing the complete \(D\)-dimensional parameter space classically.

Under the formal assumptions of the model, Theorem 3 states that a quantum machine of size poly(log D) can solve the classification task with approximately linearly many samples in \(N\), whereas a classical machine of size \(O(D^{0.99})\) cannot. The dynamic variant adds a separation in sample efficiency when the data stream changes but the decision rule remains approximately constant.

Where exactly is the advantage?

The claimed advantage is primarily a space or machine-size advantage. The paper compares logical qubits with classical floating-point memory units. For PBMC68k and other datasets, the numerical study indicates that a QOS curve using fewer than sixty logical qubits can retain high performance while general classical streaming and sparse-matrix routes require much more storage.

This does not automatically mean:

  • that a current physical QPU is faster in wall-clock time;
  • that data loading is free;
  • that every domain-specific classical heuristic has been excluded;
  • that sixty noisy physical qubits equal sixty logical qubits;
  • that better accuracy defines the theoretical advantage.

The paper itself describes the real-data figures as numerical experiments. The implementation is a JAX simulation, and dataset-specific classical heuristics are listed as future work. The asymptotic theorem and the practical PBMC graph support one another, but they are not the same object of proof.

Why the Born rule matters

A striking element of the theory is the quadratic relationship between amplitudes and probabilities. Samples control small unitary updates; convergence to the expected oracle operation is related to that probabilistic structure. The paper proves that the quadratic sample scaling required by this construction is optimal.

QSVT and classical shadows are then needed to compute useful functions of vectors and matrices from the sketch and read them out compactly in classical form. This goes far beyond “putting a data point into rotation angles.” The complete theoretical protocol consists of data access, oracle construction, quantum linear algebra and controlled readout.

Official code versus our hardware translation

The official repository contains two numerical routes:

  • explicit random sampling in qos_sampling.py;
  • an expected-unitary route in qos.py for more efficient benchmarking.

Our Qiskit route is deliberately different. We construct a shallow, QOS-inspired feature map that fits present hardware. This lets us physically test the transition from large classical input to a small quantum machine, but it does not automatically inherit the complete guarantee of Theorem 3.

That distinction is the central rule of this article series: the theory motivates the route; the hardware experiment tests a restricted implementation of it.

In part 3 we follow exactly how 32,738 genes become four blocks of forty numbers.

Sources