arXiv:2610.15791
Quantum ordinal optimization under a fixed comparison budget
Hongyu Wu
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.
AI Summary
The paper asks how much coherent comparison access improves fixed-budget selection of a good-enough design. It studies $n$ designs with an unknown strict order, an exact pairwise-comparison oracle, and one output label. Success means returning a top-$r$ design; the objective is worst-case success using at most $q$ queries. Random relabeling makes this equivalent to optimizing average success over uniformly random orders. For every $q<n$, the classical optimum is $C_q(n,r)=1-\binom{n-r}{q+1}/\binom{n}{q+1}$, attained by sampling $q+1$ designs without replacement and running a knockout. The upper bound conditions on comparison-tree leaves and bounds the output’s rank through its connected comparison component. Symmetrized quantum output-rank laws have polynomial degree at most $\min(2q,n-1)$, versus $\min(q,n-1)$ classically; both bounds are attainable. The quantum optimum is determined exactly for one comparison and every $n,r$, through an explicit cubic. For best-design selection, $Q_1(n,1)=[3(n-1)+\sqrt{13n^2-18n+9}]/(2n^2)$, approaching $3.3028/n$, compared with $2/n$ classically. One quantum comparison beats two classical comparisons exactly when $n>9$. For a top-half target, success approaches $1/2+\sqrt{2}/4\approx0.8536$. The quantum proof combines symmetry-reduced moment matrices, a semidefinite upper certificate, and an explicit attaining state and measurement. These are query results, not running-time guarantees. Comparisons are noiseless and coherently accessible; constructing one from value evaluations can require four evaluation calls, eliminating the stated one-query advantage per evaluation. General larger-budget optima, noisy comparisons, multiple outputs, feasibility checks, and implementation costs remain outside the solved model.
The author used AI tools to assist with literature research, mathematical analysis, code development, and manuscript preparation.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 22 pages, 4 tables. Adds a fixed-fraction limit and updates the discussion of two-comparison results