Quantum’s data-loading problem: the oracle-sketching escape route, tested on fraud detection

The gate we could not open

Our audit of quantum computing for AI reduced the whole quantum machine-learning question to four gates — loading, conditioning, readout, repetition — and the first gate did the decisive damage. Quantum linear algebra runs in time logarithmic in the dimension N, but only after the data exists inside the machine. If the data is a table of numbers in classical memory, getting it in costs either a state-preparation circuit of depth O(N) or a quantum random-access memory (QRAM) built from O(N) quantum hardware cells. Either way, something scales with N, and — as we put it then — the exponential advantage is spent before the algorithm begins. That single observation disqualifies most of what has been marketed as quantum machine learning on classical data, and it is why our MERIQ assessment fails such proposals at the data-basis screening question, before anyone discusses hardware.

So when a paper appears whose entire purpose is to attack that gate — with proofs, with an implementation, and with numbers on real datasets — it deserves more than the one-line acknowledgement we could give it in the audit. Exponential quantum advantage in processing massive classical data (arXiv:2604.07639, April 2026) comes from a team spanning Caltech, Google Quantum AI and MIT — Haimeng Zhao, Alexander Zlokapa, Hartmut Neven, Ryan Babbush, John Preskill, Jarrod McClean and Hsin-Yuan Huang. Its central claim: a quantum computer of poly(log N) size can perform large-scale classification, dimension reduction and linear-system solving on massive classical data by processing samples on the fly, while any classical machine matching the same performance needs exponentially larger size — or superpolynomially more samples. The claim is information-theoretic and unconditional: it survives even if BPP = BQP (that is, even if quantum computers turn out to have no time advantage over classical randomised ones at all). And the numerical experiments run it on real data — movie-review sentiment from the Internet Movie Database (IMDb) and single-cell RNA sequencing — showing four to six orders of magnitude reduction in machine size with fewer than 60 logical qubits.

This article does three things. First, it explains the mechanism — quantum oracle sketching — precisely enough that you can see both why it works and what it costs. Second, it re-runs our audit’s four gates against it, honestly: what changes, what does not, and in which currency the advantage is denominated. Third, it takes the technology to a real workload with the right shape — credit-card fraud detection — and reports on the implementation we have built around it: a Qiskit verification of the paper’s error law, the design of a streaming-sketched fraud classifier on the standard public fraud dataset, and a small construction of our own — oracle stacking — aimed at the one cost the paper concedes remains.

Oracle sketching: pay for data in samples, not in hardware

Quantum algorithms consume data through oracles — unitaries that answer queries in superposition. The canonical example is the phase oracle of a Boolean function f : [N] → {0,1}:

O : |x⟩ → (−1)f(x) |x⟩

The data-loading problem, stated in oracle language, is that building O for an arbitrary f given as classical data seems to require touching all N function values with quantum hardware — QRAM again. The paper’s move is to stop demanding the exact oracle and instead sketch it from random samples of the data, the way a streaming algorithm sketches a statistic. Suppose samples (xt, f(xt)) arrive one at a time, with xt drawn uniformly from [N]. For each sample, apply one small multi-controlled phase rotation to an n = log2 N-qubit register:

Vt = exp( iτ f(xt) |xt⟩⟨xt| / M )

— a phase nudge of size τ/M on the single basis state |xt⟩, identity everywhere else. Then discard the sample. After M samples the accumulated unitary is diagonal, with the phase on |x⟩ proportional to the empirical frequency with which x appeared. Frequencies concentrate around 1/N, so calibrating the evolution time to τ = πN makes each phase converge to πf(x) — which is exactly the phase oracle: eiπf(x) = (−1)f(x).

The subtlety — and the paper’s core technical insight — is why the randomness of the samples does not decohere the machine. Generic randomised-Hamiltonian arguments would put the error at ε ~ N²/M, which would demand so many samples that the whole idea dies. But here the per-sample Hamiltonians for distinct x act on mutually orthogonal subspaces, so their fluctuations cannot compound across basis states, and the error drops to ε ~ N/M (Theorem D.12 of the paper gives the leading constant: π²N/2M for the expected unitary). Consequently M = Θ(N/ε) samples suffice per oracle, and a quantum algorithm making Q oracle queries at total error ε consumes M = Θ(NQ²/ε) samples in total — a scaling the paper proves is optimal, the quadratic in Q being the Born-rule price of converting classical samples into coherent amplitudes.

The dataset is never stored — not on disk waiting for a QRAM, not in the machine. Each sample becomes one small rotation and is thrown away. The quantum computer stays at poly(log N) qubits; the data is paid for in samples and wall-clock time, not in hardware.

The single-bit uniform case is the demonstration kernel; the paper’s Appendix D builds it out into a full data-access toolkit. Multi-bit function values (Algorithm 2). Non-uniform and even unknown sampling distributions, handled through the quantum singular value transformation (QSVT — the polynomial-of-a-matrix framework our audit described as the grand unification of quantum algorithms). Correlated and time-varying data, at a cost that grows only with the repetition number of the data process. And, crucially for linear algebra: quantum state sketching — preparing |b⟩ from samples of a vector’s entries — and sketched sparse-matrix oracles that feed directly into block encodings. In other words, the entire input side of the HHL/QSVT machinery our audit priced out under QRAM assumptions can instead be fed from a stream.

What is actually claimed — and in which currency

Precision matters here, because the headline — “exponential quantum advantage on classical data” — is exactly the sentence our audit spent five thousand words disassembling. The paper’s theorems are advantages in machine size, not runtime. For the three application tasks — solving a sparse well-conditioned linear system, binary classification with a least-squares support-vector machine (LS-SVM, also known as the ridge classifier), and dimension reduction by principal component analysis (PCA) — the statements have the same shape: a quantum computer of poly(log N) size solves the task with Õ(N) samples, while any classical machine of size O(N0.99) cannot, no matter how much computation it spends. Behind them sits a clean information-theoretic trade-off: any classical machine of memory size S needs M S ≥ Ω(N QC) samples-times-size to extract what the task requires, where QC is the classical query complexity of the underlying property. For dynamic variants — the dataset refreshes every τ samples while the thing being learned stays approximately fixed — small classical machines do not just need more memory; they need superpolynomially more samples, because they cannot carry enough context across refresh boundaries.

Two consequences are worth pulling out. First, this separation cannot be dequantised. The Tang-style results that gutted the last generation of quantum machine-learning claims were algorithms — cleverer classical sampling that matched the quantum exponent. Here the classical side is closed off by a counting argument about memory, not by lack of imagination; a better classical algorithm cannot beat an information-theoretic lower bound. Second, the claim does not violate Holevo’s bound (an n-qubit state can only ever yield n classical bits). The machine never tries to output the dataset; it exploits the structure of the task so that the few bits that matter — a label, a principal-component overlap — are extractable. The readout side has its own tool, interferometric classical shadows: a Hadamard-test-flavoured variant of shadow tomography that turns the trained quantum state into a compact classical model which can then predict labels for arbitrarily many sparse test vectors, with no further quantum access at all.

And now the honesty ledger, because the currency of the advantage is the whole story:

1. The runtime is still linear in the data. The quantum machine touches every sample once: Õ(N) loading time, which the authors state plainly is unavoidable when each gate carries a constant number of degrees of freedom. What collapses is the memory: poly(log N) qubits instead of Ω(N) classical or QRAM cells. If your problem is compute-bound, nothing here helps you. If it is memory-bound at scale, everything here is aimed at you.
2. The audit’s verdict on deep learning stands. A frontier language model’s weights are not a stream you sample from once; they are a fixed dense matrix the workload must consult in full, per layer, per token, ~10¹² times a day. Re-sketching an oracle at Θ(N/ε) samples per instantiation, per use, multiplies exactly the way Gate 4 (repetition) said it would. Oracle sketching does not resurrect quantum transformers — and notably, the paper does not claim it does.
3. The demonstrated scale is simulation. The fewer-than-60-logical-qubits figure is a machine-size count in numerical experiments, not an executed fault-tolerant computation. It is, however, the first quantum machine-learning claim we have reviewed whose qubit budget sits inside published hardware roadmaps — IBM targets ~200 logical qubits in 2029 — rather than three orders of magnitude beyond them.

With that ledger in hand, re-run the four gates from the audit — not against deep learning this time, but against the task family the theorems actually cover: learning compact models from massive streams.

Four gates, four different answers than the ones that closed the QML-for-AI door. The catch — and it is a real one — is that this only holds for workloads shaped like the theorems: data that arrives as a stream, models that are compact, outputs that are decisions rather than vectors, and value that lies in memory rather than speed. Which raises the obvious question: does such a workload exist outside of theory papers?

Fraud detection: a workload with the right shape

Card fraud is a machine-learning problem with unusual economics. Global card-fraud losses run at roughly $34 billion a year (Nilson Report); a large payment network clears on the order of 10⁴ transactions per second; and an issuer must score each authorisation in tens of milliseconds. Three structural features make it interesting here, and none of them is the latency:

1. The data is a stream by nature and by law. Transactions arrive, are scored, and move on. Storing full histories for model training is constrained by retention rules and by the sheer scale of the feature stores — production fraud systems maintain in-memory aggregates for hundreds of millions of cards, and the state, not the arithmetic, is what costs money. A learner that consumes each sample once and keeps poly(log N) state is native to this setting, not retrofitted.
2. The features are sparse and enormously high-dimensional. Academic demos use a few dozen features, but production fraud models famously featurise categorical crosses — merchant × device × location n-grams, hashed into sparse vectors of dimension 10⁷ and beyond. That is precisely the regime of the paper’s classification theorem: D-dimensional sparse features, machine of poly(log D) size, classical lower bound Ω(D^0.99).
3. The distribution drifts. Fraud patterns change week to week as adversaries adapt — concept drift is the defining operational headache of the field, and models are retrained continually. This is, almost verbatim, the paper’s dynamic classification task: the accessible data refreshes every τ samples while the decision rule stays approximately fixed — the setting where the classical penalty is not just memory but superpolynomially more samples.

A decision problem over a massive sparse stream, one output bit per decision, drift as a first-class citizen, and memory as the binding classical cost. Fraud detection is not a workload we squeezed into the theorem’s shape; it is roughly what the theorem’s shape was always describing. Through the MERIQ lens: oracle sketching is the first mechanism we have reviewed that lifts a classical-data machine-learning use case off the floor of the data-basis criterion on the merits — the data access model in the proof is the data access model of the business. The criterion it must then answer honestly is advantage type: this is a space and sample advantage, not a time advantage, so the business case must be memory-bound or drift-bound — which fraud, unusually among ML workloads, actually is. What that is worth in points, criterion by criterion, is a question with a numerical answer, and we run it at the end of this article.

What we built

Papers with theorems this strong earn replication, not applause. Our engineering programme around the paper has three layers, in increasing order of ambition.

First: verify the error law

Everything downstream rests on the claim that a sketched oracle converges to the true one at ε ≈ π²N/2M. We implemented Algorithm 1 (Boolean function, uniform sampling) twice — a NumPy reference that manipulates the diagonal unitaries directly, and a Qiskit package pinned to it by a 37-test suite that enforces seed-for-seed agreement to 10⁻¹² — and measured the operator-norm distance to the ideal phase oracle across N = 8…64 and M = 103…106, with our reproduction of the paper’s Figure 3a extending the sweep to N = 1,024 and M = 108. Two predictions, two confirmations. In expected-unitary mode the measured error lands at 0.85–0.98 of the predicted π²N/2M in every cell of the sweep — the bound holds, with its leading constant confirmed to about 15% — and both clean scalings show up exactly as Theorem D.12 demands: doubling M halves the error, quadrupling N doubles it. In random-sample mode the error follows the π√(N/M) square-root law within a factor of 2.6, the mild drift with N being the √(log N) factor from the bound’s union argument, which our diagnostic does not divide out. On a log–log plot the curves fall on parallel lines of slope −1, vertically offset by log N — the visual signature of ε = O(N/M), and the same signature the paper’s own Figure 3 shows. The whole apparatus — parameter sweeps, diagnostic ratios, circuit rendering — ships as an interactive Streamlit test bed alongside the library and command-line interface. One implementation note worth passing on: all M per-sample rotations are diagonal and commute, so a simulation can batch them into a single diagonal gate — the difference between a sweep that finishes in minutes and one that never does. That commuting structure is not just a simulation convenience; it is the paper’s own hint about parallelisation, and we return to it below.

Second: a fraud classifier trained from the stream

The target demonstration is a streaming-sketched ridge classifier on the standard public benchmark — the ULB (Université Libre de Bruxelles) credit-card fraud dataset: 284,807 real European card transactions over two days, 492 of them fraudulent (0.172%), with 28 anonymised PCA features plus amount. The pipeline maps the classical ridge fit onto the paper’s primitives end to end:

The stream adapters are the conceptually load-bearing piece: each training transaction contributes samples (i, j, xt[i] xt[j]) whose running mean is the Gram matrix — so the sketch builds G the way the paper’s matrix data process defines it, from independent single looks at a stream, exactly the discipline that keeps the streaming claim honest. The regulariser λ doubles as the conditioning dial: we choose it so that κ(G) ≤ 10, keeping the QSVT polynomial degree modest — Gate 2 answered by construction. The whole fit runs at feature dimensions d = 4…64 in roughly 10–22 qubits on a statevector simulator, and is judged the only way a hybrid pipeline should be: against scikit-learn’s RidgeClassifier on identical splits, with acceptance thresholds fixed in advance — label agreement of at least 95% and a fraud-class F1 score (the harmonic mean of precision and recall) within 0.05 of the classical baseline. We will report the measured numbers when the pipeline lands, whichever way they fall. The headline artifact, once the sweep completes, is the real-data analogue of the error-law plot: quantum–classical disagreement against sample budget M, which Theorem D.12 predicts falls on a slope −1 line.

The limitations list is part of the result, as always. Test vectors are loaded exactly rather than sketched, so the streaming claim covers training only. Two normalisation constants are calibrated in one classical pass over the training data — a small leak the paper’s full construction avoids and our proof of concept does not. Class imbalance (0.17% positives) is handled by oversampling before the stream is formed. And at d ≤ 64, any laptop beats any quantum computer at this task by an absurd margin — the demonstration validates the mechanism and its scaling law on real data, not an advantage at demo scale. The advantage regime is where D has seven digits, which no simulator reaches.

Oracle stacking: attacking the cost that remains

The one cost oracle sketching does not remove is wall-clock: Θ(N/ε) samples must pass through the machine, sequentially, per oracle. The paper flags this openly — its discussion notes that the sketching circuit is “largely composed of commuting operations, suggesting significant opportunities for parallelization,” and files that under future work. Some arithmetic says this is not a footnote. On the error-corrected hardware of our QEC article, a logical machine executes on the order of 10⁵ operations per second; a multi-controlled phase rotation on 15–20 qubits compiles to a few hundred logical operations; so one device sketches perhaps 10²–10³ samples per second. An issuer’s authorisation stream runs at 10³–10⁴ transactions per second. The shortfall is one to two orders of magnitude — annoying, but nothing like the ten-to-fourteen orders that separated quantum linear algebra from GPU clusters in our audit. Gaps of that size have an engineering answer: parallelism.

The commuting structure makes one form of parallelism free. Two sketches of the same oracle, each built from half the samples, are diagonal unitaries that commute — running one circuit after the other simply adds their phases, and the composition is exactly the single sketch built from all the samples. Same domain, trivial merge. The interesting case is the opposite one: sketches over different shards of the index space, built concurrently on separate registers or separate devices. Can they be recombined into one oracle over the full domain?

That is the question our OracleEngineering notebook answers with a construction we call oracle stacking. Take oracle A over shard 0 and oracle B over shard 1, each on n qubits. Add one selector qubit. Apply A controlled on the selector being 0, swap the data register onto B’s register, and apply B controlled on the selector being 1. The result is a single oracle on n + 1 qubits whose action on basis states with a leading 0 is A and with a leading 1 is B — the direct sum OA ⊕ OB, which is precisely the full-domain oracle when the shards partition the index space by leading bit. Doubling the covered domain costs one qubit and the controls; k shards sketched concurrently cut the wall-clock of the loading phase by a factor of k while consuming the same total number of samples. The controlled versions come cheap in principle — the paper notes that control can be added to each of a sketch’s gates individually — and the register freed by the swap is reusable.

Full disclosure of altitude: this is a circuit identity plus an engineering argument, not a theorem about distributed sketching. Stitching shards sketched on physically separate devices presupposes a modular architecture that can bring the registers together coherently; adding control to every gate of a sketch has a constant-factor cost; and the variance analysis for stacked noisy sketches is work we have not done. But it is the right kind of open problem to have — the paper reduced quantum data loading from “impossible without QRAM” to “slow by a factor of ten to a hundred,” and factors of ten to a hundred are what parallel engineering is for.

Re-scoring the 48: what unblocking one criterion does

Last week we published MERIQ, our five-criterion assessment for quantum use cases, and scored a deliberately instructive contrast case: quantum machine learning for fraud detection, in its usual form — a variational classifier fed by amplitude-encoded transaction data. It earned 48/100, provisionally Level 2 — and then the weakest-link rule did its work. With the data basis blocked at 1/5, the verdict fell to Level 1, Exploratory, horizon undatable, because what blocked it was not a machine on anyone’s roadmap but two open research problems: a rigorous advantage on natural data, and a loading route that does not consume the speedup.

Oracle sketching is a candidate answer to precisely those two problems — which makes this the cleanest live demonstration we are likely to get of how a single research result propagates through a scorecard. One piece of doctrine first, because it keeps the exercise honest: MERIQ scores the triple (question, algorithm, data model), never a business domain and never a technology. Oracle sketching does not raise the score of the variational pitch; that card still reads 48. It defines a new triple — same question, same transactions, different algorithm and access model: a streaming least-squares support-vector machine, loaded by oracle sketching, solved by QSVT, read out through interferometric classical shadows. New triple, new card, scored against the same published anchors — in each row, the left of the arrow is July’s variational card, the right is the sketched pipeline:

The arithmetic: 4 + 3 + 3 + 3 + 3 = 16 of 25 — 64/100, the 55–74 band — and this time the cap does not bite: no criterion sits below 3, so the verdict stands at Level 3, Demonstrated. From 48 to 64, from Level 1 to Level 3, and the mechanism of the jump is worth stating precisely, because it is the general lesson about how research results move scorecards. One paper moved one criterion — data basis — two rungs. But evidence does not respect criterion boundaries: the same paper dragged the floor up under two neighbours, advantage (from heuristic to proven-in-a-different-currency) and resources (from unbounded to counted), and left two others untouched — feasibility, which holds its rung on firmer evidence, and value, which never moves because it was never the problem. Sixteen points, of which not one came from enthusiasm.

The horizon verdict changes character too, and this is the part a steering committee should care about. July’s card was undatable: its blockers were open research problems. The new card’s blockers are, in order: a first-generation error-corrected machine (tens of logical qubits — the class IBM, Google and Quantinuum roadmaps place around 2029), a demonstration that parallel sketching closes the one-to-two-order throughput gap (the oracle-stacking engineering above), and one question that is scoping rather than physics — identifying the fraud deployments where memory and drift, not latency, are the binding cost. Datable milestones and an engineering programme, where a week ago there were research prayers. Level 3’s instruction in our rubric reads: build the pipeline; track the hardware. That is, literally, what the middle of this article reports us doing.

Three footnotes for the careful reader. First, the MERIQ post noted that the same business domain already contained a 48 and something considerably stronger — the SoftBank–Quantinuum topological route to telecom fraud — and called that the rubric having resolution. This is now a third card in the same domain, and the resolution has acquired a time axis: the same executive pitch, re-instantiated with a different algorithm and access model, spans Level 1 to Level 3. Second, a caveat on the advantage row carries over from the paper itself: the classical baselines its theorems beat are general-purpose algorithms with provable guarantees — not the tuned gradient-boosted heuristics a production fraud desk actually runs, so the rubric’s opening gate question about cheap classical shortcuts still hovers over this card. Third, the exercise exposed a gap in the instrument itself: our advantage ladder prices speedups, and the strongest claim on this card — an unconditional exponential separation in machine size — has no rung of its own. That is a defect in the ruler, not the object; the anchor notes in the forthcoming MERIQ whitepaper will need to say how space-denominated advantages are scored, and this use case is the reason why.

An honest position, August 2026

In yesterday’s audit, the strongest true sentence about quantum machine learning on classical data was brutal: the loading gate fails, the low-rank escape route is dequantised, and the workloads that dominate the economy are the constructed counterexample. That sentence needed an asterisk even as we wrote it, and the Zhao et al. result is the asterisk. For tasks whose data arrives as a stream and whose answers are compact — classification, dimension reduction, linear systems consumed as observables — there is now a provable path into the machine that costs no QRAM, holds unconditionally, cannot be Tang-dequantised because it is an information-theoretic memory bound rather than an algorithmic claim, and prices its demonstrations at tens of logical qubits rather than tens of thousands.

What it does not do is equally sharp. It buys memory, not time: the machine still reads every sample, and per-operation it remains slower than classical hardware by the full error-correction bill. It does nothing for dense, stored, endlessly re-read weight matrices — our audit’s verdict on quantum transformers survives this paper untouched, and the paper’s authors are conspicuously careful not to claim otherwise. And its demonstrations, like ours, live on simulators; the fraud classifier we are building at d ≤ 64 validates an error law on real transactions, not a production advantage.

Our position: this is the most consequential development on the data question since dequantisation, and the data question is the one our MERIQ framework weighs most heavily for machine-learning use cases. It converts “quantum machine learning on classical data” from a category error into a scoping exercise — find the workloads that are genuinely stream-shaped, memory-bound and drift-bound, and price the advantage in the currency the theorems actually pay. The scorecard above — 48 to 64, Level 1 to Level 3, one criterion unblocked and two dragged upward behind it — is that exercise run once, in public, against the published anchors; running it against yours, with calibrated weights and the weakest-link rule doing its honest work, is exactly what MERIQ exists to do. If you run a workload that looks like this — massive streams, compact decisions, models that age out weekly — we would like to hear about it.