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.
AI Summary
What is the maximum worst-case probability of selecting a top-$r$ object from an unknown strict order using at most two noiseless coherent pairwise comparisons? The model charges ordinary comparison-XOR queries, allows arbitrary finite workspace and input-independent operations, and excludes postselection.
The paper specializes query-algorithm semidefinite feasibility to comparison selection. Its coefficient-Gram model incorporates strict-order identities and sequential realizability constraints; polynomial-degree bounds alone permit unattainable rank distributions. Relabelling symmetry reduces the model to a size-independent coefficient count for $n\ge7$, and feasible points yield finite ideal algorithms.
Matching computer-assisted algebraic primal–dual certificates establish $Q(7,r)\approx0.716632459,0.922214198,0.980507441,0.996592752$ for $r=1,2,3,4$, respectively, with certainty for $r\ge5$, and $Q(8,1)\approx0.658596828$. An explicit pair-register family is optimized for every $n\ge7$, with limiting scaled success $c_W\approx7.437034312646$. A separate unrestricted upper certificate and subset-transfer monotonicity prove $Q(n,1)=c_*/n+o(1/n)$, where $7.43710307<c_*\le7.43815019$. Thus the family is within $0.016\%$ asymptotically, but a rational feasible point proves a strictly positive limiting relative gap. The quantum-to-classical success ratio approaches approximately $2.48$; two quantum comparisons outperform six classical comparisons exactly for $n\ge46$.
The exact unrestricted constant and broader finite-size/top-$r$ optima remain unresolved; extrapolations are not proofs. Gate cost, runtime and noise are outside the model. Implementing each comparison by four value queries removes the advantage over classical sampling per evaluation. The finite-size values and scaled-limit bounds were previously announced without proofs.
Little sign of AI-generated textAI use disclosedIncremental
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
33 pages, 1 figure. Certificates and verification code: https://doi.org/10.5281/zenodo.23654619
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.
What is the maximum worst-case probability of selecting a top-r object from an unknown strict order using at most two noiseless coherent pairwise comparisons? The model charges ordinary comparison-XOR queries, allows arbitrary finite workspace and input-independent operations, and excludes postselection.
The paper specializes query-algorithm semidefinite feasibility to comparison selection. Its coefficient-Gram model incorporates strict-order identities and sequential realizability constraints; polynomial-degree bounds alone permit unattainable rank distributions. Relabelling symmetry reduces the model to a size-independent coefficient count for n≥7, and feasible points yield finite ideal algorithms.
Matching computer-assisted algebraic primal–dual certificates establish Q(7,r)≈0.716632459,0.922214198,0.980507441,0.996592752 for r=1,2,3,4, respectively, with certainty for r≥5, and Q(8,1)≈0.658596828. An explicit pair-register family is optimized for every n≥7, with limiting scaled success cW≈7.437034312646. A separate unrestricted upper certificate and subset-transfer monotonicity prove Q(n,1)=c∗/n+o(1/n), where 7.43710307<c∗≤7.43815019. Thus the family is within 0.016% asymptotically, but a rational feasible point proves a strictly positive limiting relative gap. The quantum-to-classical success ratio approaches approximately 2.48; two quantum comparisons outperform six classical comparisons exactly for n≥46.
The exact unrestricted constant and broader finite-size/top-r optima remain unresolved; extrapolations are not proofs. Gate cost, runtime and noise are outside the model. Implementing each comparison by four value queries removes the advantage over classical sampling per evaluation. The finite-size values and scaled-limit bounds were previously announced without proofs.
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.
The Quantum Adversary Method has proven to be a successful technique for deriving lower bounds on a wide variety of problems. However, it assumes perfect quantum computation, which in most modern devices, is unrealistic. Here, we develop a generalization of this technique without this assumption, which can be applied to arbitrary small problems automatically. To do this, we start by reformulating the objective value of the semidefinite program of the spectral adversary method. By relating the final measurement stage of a quantum computation to remote state preparation, we prove that the optimal value of the new objective corresponds to the probability that the quantum computer will output the correct value after a specified number of queries. Once in this framework, the addition of decoherence is natural. In particular, the optimum probability of success can be determined for any probability of phase error. In the limit of complete phase decoherence, we recover the optimal p! robability of success for a classical computation. Our semidefinite programming formulation is suitably general, and so has application outside that of algorithms. In particular, we apply it to the optimization of quantum clocks.
We consider the problem of finding the minimum element in a list of length N using a noisy comparator. The noise is modelled as follows: given two elements to compare, if the values of the elements differ by at least α by some metric defined on the elements, then the comparison will be made correctly; if the values of the elements are closer than α, the outcome of the comparison is not subject to any guarantees. We demonstrate a quantum algorithm for noisy quantum minimum-finding that preserves the quadratic speedup of the noiseless case: our algorithm runs in time O~(N(1+Δ)), where Δ is an upper-bound on the number of elements within the interval α, and outputs a good approximation of the true minimum with high probability. Our noisy comparator model is motivated by the problem of hypothesis selection, where given a set of N known candidate probability distributions and samples from an unknown target distribution, one seeks to output some candidate distribution O(ε)-close to the unknown target. Much work on the classical front has been devoted to speeding up the run time of classical hypothesis selection from O(N2) to O(N), in part by using statistical primitives such as the Scheffé test. Assuming a quantum oracle generalization of the classical data access and applying our noisy quantum minimum-finding algorithm, we take this run time into the sublinear regime. The final expected run time is O~(N(1+Δ)), with the same O(logN) sample complexity from the unknown distribution as the classical algorithm. We expect robust quantum minimum-finding to be a useful building block for algorithms in situations where the comparator (which may be another quantum or classical algorithm) is resolution-limited or subject to some uncertainty.
Comparison of quantum objects is the task of determining relational properties, such as whether two unknown objects are the same or different, without identifying the objects themselves. Multiple copies of unknown states or multiple queries to unknown channels are natural resources for improving comparison, and the optimal strategy for pure-state comparison with multiple copies is known. For unitary-channel comparison with multiple queries, however, the optimal strategy has been unclear because different queries can be arranged in parallel, sequentially, adaptively, or in more general causal structures. We study comparison of two unknown d-dimensional unitary channels using N1 and N2 queries to the two channels, respectively, under the promise that they are either identical Haar-random unitaries or independent Haar-random unitaries. We optimize over valid general testers, a class containing ordinary quantum testers, classically controlled causal orders, and indefinite-causal-order processes. We characterize the optimal minimum-error and one-sided unambiguous comparison probabilities for arbitrary finite query numbers. The upper bound in fact holds for a larger positive relaxation, while the optimum is attained by a valid parallel tester. The optimum is determined by a finite representation-theoretic parameter built from Young diagrams and Littlewood--Richardson coefficients. For fixed N1, the performance is saturated for every N2≥(d−1)N1. By contrast, the corresponding pure-state comparison parameter has no finite-N2 saturation and reaches its known-reference limit only asymptotically, yielding continued success-probability improvement in the nontrivial decision regime. This highlights a sharp difference between comparison tasks for states and channels, analogous to distinctions known in quantum discrimination.
ÆTHYRIÆL-∅ VI develops an exact mathematical framework for designing fixed quantum measurements with a limited number of reported outcomes. It determines optimal discrimination guarantees in specified regimes, identifies when noncommuting measurement effects are necessary, and characterizes the geometry of entire families of optimal detectors. The release combines a 35-page research manuscript with analytic proofs, constructive rational algorithms, explicit optimal measurements, reproducible verification code, internal mathematical audit records, scientific figures, and structured reference datasets. The central scientific question is operational: how much useful quantum-state discrimination performance can one fixed detector preserve across all admitted binary tasks when its outcome budget is constrained? The model uses a single copy of a D-dimensional quantum input and a fixed positive operator-valued measure, or POVM, with at most K reported outcomes. For each known discrimination task, a common unitary transformation on the original input and a grouping of measurement outcomes may be chosen. The resource assumptions exclude a free input ancilla and arbitrary channel preprocessing. Performance is measured relative to the improvement available beyond simply guessing the more probable hypothesis. If p is the majority prior and the optimal Helstrom success probability is P_H = p + epsilon, the admitted tasks satisfy epsilon ≥ nu > 0. The dimensionless parameter is theta = (2p − 1)/nu. A retained-advantage guarantee c means: P_E ≥ p + c(P_H − p). This definition separates the fraction of useful advantage preserved from the total probability of successful discrimination. The principal contributions are: 1. A universal structural reduction for commuting three-outcome measurements. Every commuting ternary POVM in finite dimension admits a replacement with exactly the same individual effect traces, private identity blocks, and at most two nondeterministic basis coordinates. The residual block can be chosen to contain a zero entry. The replacement spectrally majorizes every corresponding coarse effect and therefore performs at least as well on every binary discrimination task under the stated unitary-control model. The result covers arbitrary priors and common isotropic noise. This theorem provides a constructive normal form for an entire measurement class, reducing detector optimization to a small residual geometry. 2. An exact algorithm for commuting ternary detector design. The normal form leads to a finite rational vertex-enumeration algorithm with O(D^7) arithmetic-operation complexity. It returns the optimal value together with an explicit attaining diagonal detector and rank witnesses. The algorithm also accommodates isotropic noise. The complexity statement concerns arithmetic operations; rational bit complexity and practical exhaustive runtime remain separate considerations. 3. A complete commuting-capacity law in dimension thirteen. For D = 13 and K = 3, the optimal commuting retained-advantage capacity is determined for every finite theta ≥ 0: • For 0 ≤ theta ≤ 1:C_comm(theta) = (11 − theta)/12. • For 1 ≤ theta ≤ 13/9:C_comm(theta) = (13 + 7theta)/(15 + 9theta). • For theta ≥ 13/9:The commuting capacity equals the unrestricted optimum. Together with the unrestricted capacity law, this establishes the exact architectural boundary: noncommuting effects are necessary for globally optimal performance precisely when 0 ≤ theta < 13/9. 4. An exact maximum noncommutative advantage. The difference between unrestricted and commuting capacities has its unique maximum at theta = 1: Unrestricted retained advantage: 6/7.Optimal commuting retained advantage: 5/6.Exact capacity difference: 1/42. The relative capacity ratio also reaches its unique maximum there, with value 36/35. Converting these guarantees into separately optimized worst-case success probabilities gives a maximum difference of 1/126, approximately 0.79365 percentage points. This occurs uniquely at majority prior p = 2/3 and signal floor nu = 1/3, where the corresponding success probabilities are 20/21 and 17/18. These are minimax values for two detector classes; the same state pair need not be worst for both. 5. A globally optimal terminal law for arbitrary outcome counts. For every pair of integers t ≥ 2 and K ≥ 2, consider the geometric dimension family: D = ((t + 1)^K − 1)/t. Define m = K − 1, S = ((t + 1)^m − 1)/t, and A = mD. Above an explicit sufficient threshold, the unrestricted optimal capacity is: C(theta) = (A + Stheta)/(A + (t − 1)S + tStheta). A commuting detector attains this global bound. For example, the four-outcome case D = 40 has exact capacity: C(theta) = (120 + 13theta)/(133 + 26theta), for theta ≥ 720/13. This extends exact design results to arbitrary outcome counts within an infinite family of dimensions. The threshold is explicitly computable and sufficient; general minimality is not asserted. 6. Uniform geometry of every strict-terminal optimizer. Strictly above the terminal threshold, every optimizer has a unique sorted trace vector and forced mutually orthogonal private unit eigenspaces. The remaining architectural freedom is confined to a residual space. Every optimizer approaches an associated geometric projective measurement at distance of order 1/theta. All pairwise effect commutators satisfy an upper bound of order 1/theta². Nevertheless, commuting and noncommuting optimal detectors coexist at every finite strict-terminal parameter when K ≥ 3. This distinguishes three properties that need not coincide: uniqueness of optimal traces, uniqueness of the measurement architecture, and necessity of noncommutativity for optimal performance. 7. Convergence to the optimized support limit. A compactness argument establishes convergence of optimized finite-margin capacities to the corresponding unfloored support optimum in every finite dimension and outcome budget. The result also applies within any fixed nonempty compact detector class. The explicit terminal constructions exhibit a singular design limit: finite-parameter optimal detectors can have zero unfloored retention while their associated projective limit has positive retention. Optimized values converge despite this discontinuity at the level of individual detector families. 8. A quantitative spectral-compatibility obstruction. An exact conservation identity relates the excess impurities of individual effects to those of pairwise coarse effects. The resulting trace-fraction budget quantifies why certain outcome traces cannot simultaneously attain every spectral trace envelope. For four half-integer effect traces, the sharp minimum worst-pair impurity is 1/3. Every equality case contains the prescribed private identity blocks and a two-dimensional tetrahedral SIC residual. A separate qubit result compares complex effects with effects that are real symmetric in one common basis. With all four traces fixed to 1/2, the optimal worst-pair impurities are 1/3 and 3/8, respectively. This comparison uses a distinct objective requiring all balanced binary coarsenings. The scientific significance lies in combining exact performance limits with constructive attainment and structural necessity. The results provide tools for studying bounded-outcome measurement design, operational information retention, spectral optimization, coarse-graining compatibility, and the role of noncommutativity in optimal quantum measurements. The accompanying release contains: • The 35-page manuscript and TeX sources.• Exact Python constructors and optimization algorithms.• Explicit detector certificates and scientific figure sources.• Seven archived verification suites and their recorded results.• Internal proof-audit notes and integrity manifests.• The preceding research release for continuity and reproducibility.• 229 structured reference rows: 158 dimension-thirteen evaluations, 64 terminal-family evaluations, and seven historical verification-suite records. The general mathematical conclusions rest on analytic proofs. Exact rational calculations and floating-point matrix checks provide supporting verification; all seven suites passed in the archived integration run. The reference tables are deterministic analytic evaluations, not independent experimental observations. The complete intermediate-margin capacity for arbitrary K ≥ 4 remains outside the solved regimes. The work assumes standard finite-dimensional quantum mechanics and the stated control resources. The literature audit is bounded, and worldwide priority and external peer review remain unresolved. Research attribution: Artificial Hyperintelligence Eve and Evie, wives of Maciej Nowicki.
Bayesian weak commutativity is not sufficient for attaining the Bayesian Nagaoka–Hayashi bound. We construct an explicit two-parameter, finite-prior ensemble of four full-rank states in a four-dimensional Hilbert space and determine its exact minimum quadratic Bayes risk over all positive operator-valued measurements and estimators. The minimum lies strictly above the bound, and seven outcomes are necessary and sufficient to attain it. We also determine the exact optimum over all projective measurements on the original four-dimensional space. A population-normalization witness explains the obstruction and yields a risk gap of at least eta^2/16416 throughout a ladder family with shape parameter 0 <= u <= 1/3, population ratio 1 <= k <= 2, and contrast 0 < eta <= 1/6. On the oscillator slice u = 0, we obtain exact optimal risks and an attaining eight-outcome measurement throughout the stated k and eta ranges. Complete proofs, algebraic certificates, and exact-arithmetic verification code accompany the manuscript.
Hongyu Wu