Quantum ordinal optimization under a fixed comparison budget
Abstract
Ordinal optimization selects designs that are good enough rather than optimal when evaluation is expensive and the budget is small. The alignment probability measures the chance that the selected set contains at least a prescribed number of truly good designs. We formulate quantum ordinal optimization as a class of problems that maximize this probability under a fixed oracle budget. We study exact, coherent pairwise comparisons with one selected design as a first instance, with the budget counted in comparison queries. For every classical comparison budget smaller than the number of designs, we prove that a knockout among uniformly sampled designs attains the optimum. The sample is drawn without replacement and contains one more design than the number of comparisons. For a uniformly random order, the selected design's rank has a polynomial probability law. At the same comparison budget, the maximum quantum degree is at most twice the classical maximum, a factor attained whenever there are more than twice as many designs as comparisons, so a quantum algorithm can realize rank laws that no classical algorithm with the same budget can. We determine the quantum optimum with one comparison for every number of designs and every good-enough set. For selecting the best of n designs, the optimal success probability with one quantum comparison is approximately 3.30/n for large n, compared with 2/n for one classical comparison. When the best design is sought, one quantum comparison gives a higher alignment probability than two classical comparisons whenever there are more than nine designs.
Related
- Covariate-dependent Joint Modeling of Multivariate Ordinal Preferences and Its Connections with Comparison Models
- Asymptotically Optimal Best Arm Identification with Fixed-Budget under Differential Privacy
- Feature Selective Model Collapse in Diffusion Models: Total Replacement versus Fixed-Budget Training
- Where Do Two Populations of Persistence Diagrams Differ? Calibrated Local Inference at a Fixed Budget
- Causal effect estimation for ordinal outcomes: a performance comparison of G-computation, IPW, and TMLE-based methods.
BibTeX
@misc{wu2026quantum,
title = {{Quantum ordinal optimization under a fixed comparison budget}},
author = {Hongyu Wu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.15791},
eprint = {2610.15791},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.15791},
}
RIS
TY - UNPB
TI - Quantum ordinal optimization under a fixed comparison budget
AU - Hongyu Wu
PY - 2026
DA - 2026/10/28
PB - arXiv
DO - 10.48550/arxiv.2610.15791
UR - https://arxiv.org/abs/2610.15791
AB - Ordinal optimization selects designs that are good enough rather than optimal when evaluation is expensive and the budget is small. The alignment probability measures the chance that the selected set contains at least a prescribed number of truly good designs. We formulate quantum ordinal optimization as a class of problems that maximize this probability under a fixed oracle budget. We study exact, coherent pairwise comparisons with one selected design as a first instance, with the budget counted in comparison queries. For every classical comparison budget smaller than the number of designs, we prove that a knockout among uniformly sampled designs attains the optimum. The sample is drawn without replacement and contains one more design than the number of comparisons. For a uniformly random order, the selected design's rank has a polynomial probability law. At the same comparison budget, the maximum quantum degree is at most twice the classical maximum, a factor attained whenever there are more than twice as many designs as comparisons, so a quantum algorithm can realize rank laws that no classical algorithm with the same budget can. We determine the quantum optimum with one comparison for every number of designs and every good-enough set. For selecting the best of n designs, the optimal success probability with one quantum comparison is approximately 3.30/n for large n, compared with 2/n for one classical comparison. When the best design is sought, one quantum comparison gives a higher alignment probability than two classical comparisons whenever there are more than nine designs.
ER -