Quantum ordinal selection with two comparisons
Abstract
We study the optimal probability of selecting an object within a prescribed rank threshold using at most two noiseless coherent pairwise comparisons of an unknown strict order. Polynomial degree bounds alone can overestimate the success attainable with two comparisons. We develop a comparison-specific semidefinite model that completely characterizes attainable success. Computer-assisted proofs establish the exact optimum for every rank threshold at seven objects and for minimum selection at eight. For minimum selection, we construct an explicit algorithm family and determine its exact optimum. Bounds for all admissible two-comparison algorithms show that the family's asymptotic success is within 0.016% of the unrestricted optimum. We also prove that this relative gap has a strictly positive limit. The optimal quantum-to-classical success ratio for minimum selection converges to approximately 2.48 under the same two-comparison budget.
Related
- Quantum ordinal optimization under a fixed comparison budget
- Rethinking free-space orbital angular momentum quantum key distribution: encoding selection and branch-cut-length-minimized adaptive optics
- Qmes: Quantum Meta-Learning for Encoding Selection in Quantum Kernel Methods
- Post-Selection-Free Quantum Automated Learning
- Graph Neural Post-selection for Quantum Error Correction
BibTeX
@misc{wu2026quantum,
title = {{Quantum ordinal selection with two comparisons}},
author = {Hongyu Wu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.34762},
eprint = {2610.34762},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.34762},
}
RIS
TY - UNPB
TI - Quantum ordinal selection with two comparisons
AU - Hongyu Wu
PY - 2026
DA - 2026/10/26
PB - arXiv
DO - 10.48550/arxiv.2610.34762
UR - https://arxiv.org/abs/2610.34762
AB - We study the optimal probability of selecting an object within a prescribed rank threshold using at most two noiseless coherent pairwise comparisons of an unknown strict order. Polynomial degree bounds alone can overestimate the success attainable with two comparisons. We develop a comparison-specific semidefinite model that completely characterizes attainable success. Computer-assisted proofs establish the exact optimum for every rank threshold at seven objects and for minimum selection at eight. For minimum selection, we construct an explicit algorithm family and determine its exact optimum. Bounds for all admissible two-comparison algorithms show that the family's asymptotic success is within 0.016% of the unrestricted optimum. We also prove that this relative gap has a strictly positive limit. The optimal quantum-to-classical success ratio for minimum selection converges to approximately 2.48 under the same two-comparison budget.
ER -