What kind of quantum advantage is this?

Quantum advantage encompasses fundamentally different claims, from resource reductions to exponential separations in sample complexity. Evaluating these claims requires distinguishing how an algorithm achieves an advantage from what is necessary for the separation and how strongly it is supported against classical alternatives. We propose a multi-label taxonomy that makes these distinctions explicit, classifying structural, interference, and coherent mechanisms while separately recording their necessity and the evidence for the classical comparison. Coherent mechanisms are further divided into memory and output, reflecting distinct restrictions on quantum information processing. A two-part entanglement-breaking test distinguishes loss of information from loss of algorithmic efficiency. The hidden subgroup problem illustrates the distinction: among the cases examined, cross-copy coherence is information-theoretically necessary only for the symmetric group. We present this as a diagnostic methodology rather than a theory of quantum advantage: for a new claim, it identifies the relevant adversary, separates the mechanisms a protocol uses from those shown to be necessary, and records the strength of the evidence and the quality of the advantage separately.

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-11-16
DOI
https://doi.org/10.48550/arxiv.2611.21239
Primary Topic
Quantum Computing Algorithms and Architecture
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

What kind of quantum advantage is this?

Christophe Père
arXiv (Cornell University)
Quantum Computing Algorithms and Architecture
preprint

What kind of quantum advantage is this?

Christophe Père
preprint en

Abstract

Quantum advantage encompasses fundamentally different claims, from resource reductions to exponential separations in sample complexity. Evaluating these claims requires distinguishing how an algorithm achieves an advantage from what is necessary for the separation and how strongly it is supported against classical alternatives. We propose a multi-label taxonomy that makes these distinctions explicit, classifying structural, interference, and coherent mechanisms while separately recording their necessity and the evidence for the classical comparison. Coherent mechanisms are further divided into memory and output, reflecting distinct restrictions on quantum information processing. A two-part entanglement-breaking test distinguishes loss of information from loss of algorithmic efficiency. The hidden subgroup problem illustrates the distinction: among the cases examined, cross-copy coherence is information-theoretically necessary only for the symmetric group. We present this as a diagnostic methodology rather than a theory of quantum advantage: for a new claim, it identifies the relevant adversary, separates the mechanisms a protocol uses from those shown to be necessary, and records the strength of the evidence and the quality of the advantage separately.

arXiv (Cornell University)
Quantum Computing Algorithms and Architecture
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon