Where Grover Search Could Help Author Disambiguation, and What It Would Cost

When an author's surname is misspelled, the misspelled paper usually drops out of that person's record. "Wojciechowki" never gets compared against "Wojciechowski", and the author's citation count quietly splits in two. Disambiguation systems avoid comparing every record with every other by first sorting records into small groups that share an initial and a surname, a step called blocking. A typo defeats blocking. Grover-style amplitude amplification is a quantum procedure that finds a marked item among $N$ candidates with about $\sqrt{N}$ checks instead of $N$. It looks like a natural fix: search the whole database for the one record that matches an orphaned mention. This note argues that the obvious version of the idea fails. The part worth pursuing is a narrower, testable claim about where the quadratic speedup could still apply.

The central observation is this. Most typo recovery is not unstructured search, so Grover has nothing to add there. A misspelled name is found by classical string indexes that return every edit-distance-one neighbour almost instantly. The only step of disambiguation that resembles an unstructured "find the needle" problem is recovering an orphaned mention when the match criterion is the learned pairwise classifier: a gradient-boosted model over co-authors, venues and document embeddings. No classical index exists for that score. We propose to build a typo-corruption benchmark from real correction notices, measure how often classical indexes fail to recover orphans, and write an end-to-end quantum resource model for the residual learned-oracle search. The outcome is a crossover map: at what database size, classifier cost and orphan rate a Grover rescue step could beat a parallel classical scan. We fully expect the map may say "not at any realistic scale." That would still be the first such accounting for entity resolution.

Core Claim

For author disambiguation, amplitude amplification is a candidate for a speedup only on the orphan-rescue subproblem under a learned match score. Its practical value then depends on two things. The first is whether classical indexes leave a meaningful residue of orphans that only the learned score can recover. The second is whether the reversible circuit cost of that classifier, multiplied by $\sqrt{N/M}$ oracle calls, beats a many-threaded classical scan of $N$ classifier evaluations. Here $M$ is the number of true matches, typically very small. Both conditions can be measured, and neither has been measured before.

Grounding in Prior Work

The quantum side supplies the mechanism. The statistician-oriented tutorial An introduction to quantum computing for statisticians and data scientists derives the geometry of Grover search, reaching a marked state in $O(\sqrt{N})$ queries. It also stresses that loading classical data into quantum form can cost $O(N)$ and cancel the gain. Quantum Computing for Databases: A Short Survey and Vision envisions quantum coprocessors for database selection, joins and fuzzy similarity search, but never formulates entity resolution. Quantum Perceptron Models uses Grover to find misclassified points and relies on the same oracle-access assumption we must price. Quantum minimum-finding, as used in Quantum speedup for track reconstruction in particle accelerators to connect detector hits in $O(\sqrt{n})$, is the variant we would use when the task is "best-scoring candidate" rather than "any match." The fixed-point search in A query-based quantum eigensolver matters because the number of true matches $M$ for an orphan is unknown, and standard Grover overshoots when $M$ is misjudged.

The quantum clustering and embedding papers, q-means and Fast Variational Knowledge Graph Embedding, both assume quantum RAM (QRAM), a hypothetical memory that serves a whole dataset to a quantum circuit in superposition. They target Euclidean clustering and link prediction. We do not reuse them. They mainly show that the most-cited quantum learning speedups rest on hardware assumptions our cost model must state explicitly.

The disambiguation side supplies the problem and the constraints. S2AND defines the standard three-stage pipeline of blocking, a LightGBM pairwise classifier with SPECTER document embeddings, and average-linkage clustering. It notes that initial-plus-surname blocking breaks under misspellings and transliteration. Learning CNF Blocking for Large-scale Author Name Disambiguation and Scaling Author Name Disambiguation with CNF Blocking show that learned blocking rules scale classically to all of PubMed. They also show that disjoint blocks, needed for parallelism, cap completeness; that capped completeness is exactly the orphan residue we study. Author name disambiguation for PubMed reports a splitting error of 7.7%, meaning one person scattered across several clusters. That is the error class a rescue step targets.

Formal correction notices provide real corruption patterns rather than synthetic ones. The file's examples cover a dropped letter ("Wojciechowki" in Correction to: Farkas Bounds on Horn Constraint Systems) and a dropped letter in a given name ("Xinglin"→"Xinlin" in the black rockfish genomics correction). They also cover a mid-surname deletion ("Stuckeschmidt" in Correction: Anytime bottom-up rule learning), a name-order and capitalization fix (Erratum to: A visual analysis approach for data imputation), and a misattribution inside a 49-author list (Author Correction: A deep-learning pipeline for ... chest X-ray images). Notices such as Correction: Corrigendum: Decoding tumour phenotype are administrative patches. They fix the record only when someone notices and files them, which leaves unreported corruptions in place.

Research Program

The first component is a corruption benchmark. We collect correction notices whose only change is an author name and extract the before/after pairs. We then build an empirical distribution over edit types: deletion, substitution, transposition, given-name/surname swap, transliteration, and misattribution. The file's examples show the categories; the full collection must come from indexed errata. We inject corruptions drawn from this distribution into S2AND records and into the PubMed benchmark of 214 authors and 3,964 mentions used by the CNF blocking papers. We then record which true pairs each blocking scheme loses. Each lost pair defines an orphan query: a corrupted mention whose true co-cluster lies outside its block.

The second component is a classical rescue ladder. Orphans pass through increasingly expensive classical recovery. The first rung is a symmetric-deletion or character n-gram index over surnames that returns neighbours within a small edit distance. The second rung is a vector-similarity index, HNSW, over SPECTER embeddings of the mention's paper plus co-author context. The last rung is an exhaustive scan that applies the learned S2AND pairwise classifier to every record in the database. The residue that only the exhaustive scan recovers is the sole region where amplitude amplification has an unstructured-search argument. Its size is our first key measurement.

The third component is the quantum cost model for that residue. The oracle is the S2AND pairwise classifier, a fixed-depth tree ensemble, compiled into a reversible circuit that also evaluates its features. We count logical gates, circuit depth and memory qubits. The comparison is:

$$ T_Q = c_O \cdot \tfrac{\pi}{4}\sqrt{N/M} + L(N), \qquad T_C = \frac{c_C \, N}{P}, $$

The symbols are defined as follows. $c_O$ is the wall-clock time of one oracle call on error-corrected hardware. $c_C$ is the time of one classical classifier evaluation. $P$ is the number of parallel classical workers. $L(N)$ is the per-query share of the cost of making the database available to the oracle. The $\sqrt{N/M}$ factor is the Grover query count for $M$ marked items out of $N$. We evaluate two regimes for $L(N)$. In the pessimistic regime, data is loaded classically, so $L(N)$ is linear in $N$ and no advantage is possible. In the charitable regime, QRAM is loaded once and amortized over every orphan query against a fixed snapshot. We report the crossover $N^*$ at which $T_Q < T_C$ as a function of $c_O / c_C$, with $c_O$ taken from a stated range of assumed fault-tolerant gate times. We use fixed-point search because $M$ is unknown and varies between queries. We compare it with quantum minimum-finding over classifier scores, which returns the best candidate without a threshold.

Baselines

The naive reference is standard initial-plus-surname blocking with no rescue step, run on the corrupted benchmark. It sets the floor for how many true pairs typos destroy, and so how much splitting error is available to recover. The strongest blocking competitor is learned disjoint CNF blocking from Learning CNF Blocking for Large-scale Author Name Disambiguation. It reports a Reduction Ratio of 0.882 at Pairs Completeness 0.99 on the PubMed benchmark, and removes 82.17% of candidate pairs over 80 million PubMed mentions in 10.5 minutes on 24 threads. We retrain it on the same clean data and measure its completeness on corrupted records. We expect completeness to drop under corruption, but that expectation must be measured rather than assumed. For end-to-end accuracy, the strongest system is the S2AND reference pipeline. The file reports only that it cuts the Semantic Scholar production system's error by over 50% in B³ F1; no reported result found on Lacuna for its absolute B³ F1 on individual sub-benchmarks, so we rerun it from the public code.

The comparison that matters most is the classical rescue ladder. It plays the role of the ablation that isolates the proposal's key ingredient, the non-indexable learned oracle. We run the quantum cost model twice. In one run the oracle is an edit-distance test, for which a classical index exists. In the other the oracle is the learned classifier. Any apparent advantage in the edit-distance case is spurious and should vanish against the n-gram index. A quantum rescue step counts as beating the classical ladder only under three conditions. It must recover orphans the ladder misses. It must recover them at the same classifier threshold. And its modelled wall-clock time must fall below a many-threaded scan with the same thread budget CNF blocking used, at a database size we actually observe.

Why not just…?

Why not just use CNF blocking and accept the losses? This may be the right answer. Blocking is fast and completeness of 0.99 is high on clean data. The open question is completeness on typo-corrupted mentions, which the CNF papers do not report. The corruption benchmark measures that loss directly. If CNF completeness stays near 0.99 under errata-derived corruptions, the rescue problem is too small to matter, and we would report that.

Why not just add a fuzzy string index for surnames? This is the most serious threat, and we expect it to win on most orphans. Edit-distance neighbours are cheap to enumerate classically, so Grover offers nothing for that sub-case. The ablation with the edit-distance oracle makes this explicit. The proposal survives only if a measurable residue of orphans cannot be recovered by string similarity. Candidates for that residue include transliterations, given-name/surname swaps, and misattributions within large author lists.

Why not just use nearest-neighbour search over SPECTER embeddings? Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations shows that HNSW, DiskANN and similar indexes can degrade to scanning at least 10% of a dataset on adversarial inputs. Bibliographic data is not adversarial, though, so that result does not rule the method out. We measure HNSW recall on real orphans. Whatever the embedding index recovers at high recall is removed from the quantum-relevant residue.

Why not just rely on publisher corrections and author identifiers? Correction notices fix only errors that someone notices and files. They also act on individual records rather than on the disambiguated clusters that produce the reported splitting errors. They remain useful as ground truth for corruption patterns, which is how we use them.

Proposed Experiments

The first decisive check is the size of the residue. On S2AND and the PubMed benchmark with errata-derived corruptions, we measure the fraction of lost true pairs recovered by each classical rung. If the n-gram index and HNSW together recover nearly all orphans, the quantum question is closed for this application, and the paper reports a negative result with the benchmark as its main contribution. The second check is whether rescue helps accuracy at all. We run the S2AND pipeline with and without the exhaustive learned-classifier rescue and measure the change in B³ F1 and splitting error. Rescue that adds lumping errors (merging different people) faster than it removes splits is not worth accelerating. The third check is the crossover map. We compile the classifier oracle and report $N^*$ under both loading regimes and a range of oracle-to-classical cost ratios. We then compare $N^*$ with the 80-million-mention PubMed scale. The analysis succeeds if these three checks together tell a disambiguation engineer, with numbers, whether amplitude amplification could ever earn a place in the pipeline.