Quantum Search for the Disagreement Region in Active Learning

Active learning saves labels by asking a teacher only about the inputs the current model is unsure of. It also has a second cost that rarely gets counted. To find one uncertain input, the learner has to draw and inspect many ordinary ones, and late in training the uncertain inputs are rare. If only a fraction $p$ of the data distribution still confuses the model, a classical learner inspects about $1/p$ unlabeled examples per useful query. We propose to hand exactly this search to a quantum computer. The quantum computer would run Grover-style amplitude amplification, a procedure that finds a marked item among many with quadratically fewer look-ups than checking items one by one. Here the marked items are the inputs on which the surviving hypotheses disagree. Labels still come from a classical teacher, one at a time.

The design choice that makes this worth studying is what gets marked. The mark depends only on the models, never on labels. That brings three benefits at once. The search needs only a way to prepare unlabeled data in superposition, not an oracle for labeled examples and its inverse. The search targets model uncertainty and cannot be pulled toward mislabeled or inherently noisy points. And the quantum advantage becomes a measurable, data-dependent quantity, set by how quickly the region of disagreement shrinks on real data, rather than a worst-case exponent.

Core Claim

Recent quantum learning theory proves a quadratic advantage for learning from oracle access. Provable Advantage in Quantum PAC Learning shows that a learner with the labeled-state oracle $Q_c$ and its adjoint $Q_c^\dagger$ needs $\Theta(d/\sqrt{\epsilon})$ queries, up to logarithmic factors, against the classical passive $\Theta(d/\epsilon)$. Here $d$ is the VC dimension of the hypothesis class and $\epsilon$ the target error. The algorithm amplifies counterexamples, meaning points where the current hypothesis $h$ disagrees with the true concept $c$. That comparison is against a passive classical learner, which is the wrong opponent. A classical active learner in the realizable, well-behaved case already needs only on the order of $d\log(1/\epsilon)$ labels. The classical side's remaining weakness is the unlabeled search, not labels.

Our claim is that, once classical active learning is the baseline, the quantum advantage moves entirely into the cost of drawing unlabeled examples. It can be captured with a label-free marking oracle. Let round $t$ of an active learner have disagreement mass $p_t$, the probability under the data distribution that an input falls where the current committee or version space disagrees. Labels are identical in both regimes. The expected number of calls to the unlabeled sampler is

$$C_{\text{classical}} \approx \sum_{t=1}^{T} \frac{1}{p_t}, \qquad C_{\text{quantum}} \approx \sum_{t=1}^{T} \frac{1}{\sqrt{p_t}},$$

where $T$ is the number of label queries. The first form is geometric rejection sampling. The second is the expected cost of amplitude amplification with an unknown number of marked items, for example the Boyer–Brassard–Høyer–Tapp variant of Grover search that Salmon et al. use. If $p_t$ shrinks toward $\epsilon$, the quadratic gap reappears in unlabeled cost. If $p_t$ plateaus, as it does under label noise, the gap collapses to a constant. The central empirical question of this proposal is which of these happens on real benchmarks.

Why label-free marking matters

Salmon et al.'s oracle marks $x$ when $h(x)\neq c(x)$, so it consumes labels inside the quantum circuit. Under aleatoric noise, meaning label randomness no model can remove, every mislabeled point looks like a counterexample, and amplitude amplification retrieves exactly those points preferentially. This is the classical warning about maximal-uncertainty sampling taken to its limit. Privacy-preserving and Uncertainty-aware Federated Trajectory Prediction for Connected Autonomous Vehicles found it necessary to select median rather than maximal aleatoric uncertainty. Active Data Curation Effectively Distills Large-Scale Multimodal Models uses a teacher to keep only learnable points. Both results motivate our design.

Disagreement among hypotheses consistent with the data so far is a purely epistemic quantity, because it is computed without looking at the label of $x$. Marking by disagreement therefore sidesteps the noise-amplification failure by construction. It also answers one of Salmon et al.'s stated open problems: the adjoint of the labeled oracle is no longer needed. Only the unlabeled state-preparation circuit and its inverse remain, and these are plausible when the data distribution is itself a circuit or simulator.

The batch and noise theory of Achieving Minimax Rates in Pool-Based Batch Active Learning supplies the classical skeleton we reuse. Its algorithm prunes confident regions, selects diverse points inside the uncertain region, and retrains a logarithmic number of times, with excess risk $T^{-(1+\alpha)/(2+\alpha)}$ under Tsybakov noise exponent $\alpha$. Amplitude amplification returns samples from the data distribution restricted to the marked region. That is exactly the "draw from the uncertain region" primitive this algorithm assumes, and it gives batch diversity for free before any optimal-design step.

Research Program

The theoretical part proves unlabeled-oracle upper bounds for a quantum version of disagreement-based active learning, in both the realizable case and the Tsybakov-noise case. It also proves matching lower bounds from the optimality of Grover search for finding a region of mass $p$. A key step is showing that the label complexity of the classical skeleton is unchanged. We will state plainly the regime where the advantage is void. If the data distribution restricted to the disagreement region can be sampled classically, for instance because the distribution is a known Gaussian and the region is a slab, then classical rejection is unnecessary and nothing quantum is gained. This is the same trap On quantum ensembles of quantum classifiers identified when it dequantized accuracy-weighted quantum ensembles by rejection sampling. Our advantage is claimed only for black-box samplers, where Grover's lower bound applies.

The constructive part builds reversible marking circuits for committees small enough to simulate: linear threshold units, shallow trees, and $k$-juntas. It measures gate cost per oracle call, so that the quadratic reduction in calls is not eaten by a costly mark.

The empirical part has two layers. First, full statevector simulation, up to roughly 20 qubits, on synthetic concept classes such as juntas and halfspaces. This checks the amplitude-amplification cost curve end to end. Second, oracle-call accounting on real tabular benchmarks. There we run the exact classical active learner, record the realized $p_t$ trajectory, and compute both cost sums. The accounting is exact given $p_t$, so no hardware is needed to tell whether real data sits in the quadratic regime or the plateau regime.

Baselines

The naive reference point is passive learning with uniform random sampling and the same learner. It fixes the scale for both labels and unlabeled draws.

The strongest existing classical method is pool-based uncertainty sampling with a query model matched to the task model, following the protocol of Re-Benchmarking Pool-Based Active Learning for Binary Classification and An Expanded Benchmark that Rediscovers and Affirms the Edge of Uncertainty Sampling for Active Learning in Tabular Datasets. These papers report that uncertainty sampling achieved the best area under the budget curve on 18 of 29 binary and 5 of 7 multi-class datasets. We run it on the same datasets, with the same learner, the same initial seeds and label budgets, and the same hyperparameter search. Its label curve must be matched within noise: our method should neither gain nor lose labels. Beating it means strictly fewer unlabeled-sampler calls to reach the same label-budget accuracy. Since uncertainty sampling ranks points rather than thresholding them, we also include a threshold version, "margin below $\tau$", as the exact classical twin of our quantum search.

The strongest quantum method is the counterexample-amplification learner of Salmon et al., simulated with label-based marking. Its query bound is the reported number to beat in the noiseless case. Under label noise we expect it to degrade because it amplifies mislabeled points.

The key ablation swaps our label-free disagreement mark for the label-based counterexample mark while holding everything else fixed. This isolates whether label-free marking is what buys noise robustness.

As the practical reference demanded by ALPBench: A Benchmark for Active Learning Pipelines on Tabular Data, we also run CatBoost with random sampling. That paper reports no single scalar result for this pipeline. We found no reported result on Lacuna for any quantum active learner on these tabular suites.

Why not just…?

Why not just run classical uncertainty sampling over the stored pool? For a pool already in memory, this is the honest winner in wall-clock time. Scoring $N$ points is linear and cheap, and loading the pool into quantum memory would itself cost $N$. We do not claim otherwise. Our claim applies when unlabeled examples are expensive to produce, for example when each draw is a physics simulation, a generative-model sample, or a quantum state from an experiment, as in Quantum advantage in learning from experiments. The tabular experiments use pools only to measure $p_t$ trajectories. They do not suggest replacing a sort with Grover.

Why not just use Salmon et al.'s quantum PAC learner directly? It already has an optimal quadratic bound. However, its mark needs labels inside the circuit and it needs the labeled-oracle adjoint. Both are more demanding than our unlabeled oracle, and its target set grows with label noise. The mark-swap ablation under injected label flips at several rates is designed to show this. If the counterexample learner turns out to be equally robust, our noise argument fails and we will report that.

Why not just use a stronger classical learner, since the learner matters most? ALPBench shows that the choice of learner dominates the choice of query strategy for accuracy. Our quantity is unlabeled-oracle cost at a fixed learner, which is orthogonal to that finding. The real risk is that the learners that win ALPBench, such as boosted trees, have no cheap reversible disagreement circuit. We will report per-call gate cost for every committee type, including tree ensembles, so any accuracy we give up for circuit tractability is visible.

Why not just sample the uncertain region classically with a smarter proposal distribution? Where such a sampler exists, it removes the advantage, which is the dequantization lesson of Abbas et al. We will test this directly on synthetic Gaussian data, where the slab-shaped disagreement region can be sampled exactly. We expect the quantum gain to vanish there and to persist only for black-box samplers.

Proposed Experiments

The first decisive check is on synthetic juntas and halfspaces in statevector simulation. It asks whether measured unlabeled-oracle calls follow the $\sum_t p_t^{-1/2}$ law while the label count matches classical disagreement-based learning, and whether this holds as noise is added through the Tsybakov exponent.

The second check runs over the 40 datasets of Lu et al. and the 86 of ALPBench. We record $p_t$ under matched uncertainty sampling and report the ratio $C_{\text{classical}}/C_{\text{quantum}}$ at label budgets reaching 99% of full-data accuracy. The ratio tells us whether real data behaves like the quadratic regime, where it grows as the target error shrinks, or like the plateau regime, where it stays at a small constant. We also correlate that ratio with estimated label-noise level.

The third check injects label flips at increasing rates and compares label-free and label-based marking on final accuracy and on the fraction of queried points that were mislabeled.

A result showing near-constant ratios on real tabular data would itself be informative. It would locate the practical value of quantum search in active learning in noise-free, simulator-generated data rather than in standard benchmarks.