Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.15791

Quantum ordinal optimization under a fixed comparison budget

Hongyu Wu

quant-pheess.SYmath.OCSubmitted Oct 11, 2026• Announced Oct 13, 2026• 1 citation• Revised Oct 28, 2026 (v2)
v1 · Oct 11, 2026v2 · Oct 28, 2026
arXivHTMLPDF

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.

Little sign of AI-generated textAI use disclosedStrong assumptions
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

Related papers

Quantum ordinal selection with two comparisons

Hongyu Wu

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.

quant-pharXiv:2610.34762•Oct 27, 2026•0 citations

Rate-Optimal Quantum Discrete Simulation Optimization

Mingjie Hu, Jian-Qiang Hu

Quantum computing has developed rapidly in recent years and has shown potential advantages over classical computing in various domains. In this paper, we study whether quantum computing can accelerate the convergence rate of discrete simulation optimization in the fixed-budget setting. We first formulate the quantum discrete simulation optimization problem by defining the quantum simulation oracle, the algorithmic performance measure, and the corresponding optimality guarantee. Based on this formulation, we establish a minimax lower bound on the expected optimality gap for any quantum algorithm. The lower bound analysis reduces the discrete simulation optimization problem to a sequential quantum phase-testing problem, and the resulting lower-bound argument may be of independent interest. By comparing the quantum lower bound with its classical counterpart, we show that the optimal convergence rate in the quantum setting exhibits a quadratic improvement in its dependence on the simulation budget, at the cost of a worse dependence on the number of decisions. We then propose the first fixed-budget quantum algorithm, called \textsc{QUEST}, for discrete simulation optimization. The algorithm combines a quantum Monte Carlo subroutine with a sequential elimination framework and uses a slow-measurement mechanism to help preserve quantum superposition during the optimization process. We prove that \textsc{QUEST} achieves the optimal convergence rate up to logarithmic factors. Numerical experiments further show that \textsc{QUEST} outperforms its classical counterpart, which provides empirical evidence for the quantum advantage in improving the convergence rate of discrete simulation optimization algorithms.

quant-pharXiv:2610.03360•Oct 5, 2026•1 citation

Quantum algorithms for finding extrema with unary predicates

Man Hon Chan

We study the problem of finding the maximum or the minimum of a given set S = {x₀, X₁, ... X n₋₁}, each element X i drawn from some finite universe [Unary] of real numbers. We assume that the inputs are abstracted within an oracle O where we can only gain information through unary comparisons in the form "Is Xi greater than, equal to, or less than some constant k?" Classically, this problem is solved optimally with a runtime of Θ(n +lg|U|). In the setting of Quantum Computing, we show that at least Ω(√n+lg|U|) queries are required to solve the problem even with bounded error. Combining variants of the Grover's search [1, 2] algorithm and the optimal classical unary extrema finding algorithm, we have derived a series of new quantum algorithms, some running in time as fast as O(√n lg*n+lg|U|). This shows that quantum computers can accelerate the speed in the unary comparison model asymptotically. Inspecting our tools, we find convincing arguments that our lower bound is most probably tight, but we may need an entirely new approach to solve the problem optimally. The technique used in our algorithm can also be extended to solve variations of quantum statistics problems. For instance, our result can be directly extended to approximation of extrema of real numbers, similar to that of [3]. Moreover, we can also solve the quantum k-select problem optimally in time O(√kn) with constant success probability. We hope that our ideas and tools will prove to be useful in other areas.

•Jan 1, 2011•0 citations

Quantum Grover Adaptive Search for Discrete Simulation Optimization

Mingjie Hu, Jian-qiang Hu, Enlu Zhou

Quantum computing has advanced rapidly in recent years and has shown advantages in a variety of domains. In this paper, we investigate its potential for discrete simulation optimization in the fixed-confidence setting, a fundamental problem in the simulation literature. We first introduce a quantum simulation oracle that prepares a coherent superposition over all candidate solutions and provides the foundation for quantum algorithm design. Based on this oracle, we develop the first Grover-search-based quantum algorithm for discrete simulation optimization, called SOGAS. In particular, SOGAS uses a binary-search framework to progressively eliminate suboptimal solutions while carefully controlling the error probability, and eventually identifies a set of near-optimal solutions. We prove that SOGAS returns a near-optimal solution with probability at least the prescribed confidence level and achieves a quadratic speedup in the dependence of query complexity on the number of candidate solutions. Numerical experiments further show that SOGAS substantially outperforms classical benchmarks and provide empirical evidence for quantum advantage in discrete simulation optimization.

quant-pharXiv:2604.26277•Apr 30, 2026•3 citations

Quantum Algorithms for Fixed Qubit Architectures

Edward Farhi, Jeffrey Goldstone, Sam Gutmann +1 more

Gate model quantum computers with too many qubits to be simulated by available classical computers are about to arrive. We present a strategy for programming these devices without error correction or compilation. This means that the number of logical qubits is the same as the number of qubits on the device. The hardware determines which pairs of qubits can be addressed by unitary operators. The goal is to build quantum states that solve computational problems such as maximizing a combinatorial objective function or minimizing a Hamiltonian. These problems may not fit naturally on the physical layout of the qubits. Our algorithms use a sequence of parameterized unitaries that sit on the qubit layout to produce quantum states depending on those parameters. Measurements of the objective function (or Hamiltonian) guide the choice of new parameters with the goal of moving the objective function up (or lowering the energy). As an example we consider finding approximate solutions to MaxCut on 3-regular graphs whereas the hardware is physical qubits laid out on a rectangular grid. We prove that the lowest depth version of the Quantum Approximate Optimization Algorithm will achieve an approximation ratio of at least 0.5293 on all large enough instances which beats random guessing (0.5). We open up the algorithm to have different parameters for each single qubit $X$ rotation and for each $ZZ$ interaction associated with the nearest neighbor interactions on the grid. Small numerical experiments indicate that an enveloping classical algorithm can be used to find the parameters which sit on the grid to optimize an objective function with a different connectivity. We discuss strategies for finding good parameters but offer no evidence yet that the proposed approach can beat the best classical algorithms. Ultimately the strength of this approach will be determined by running on actual hardware.

arXiv:1703.06199•Mar 17, 2017•168 citations

Quantum and Classical Memory for Storage and Retrieval of Quantum Measurements

Filip Turoboś, Ludmiła Marcinkowska, Zbigniew Puchała

We study the persistent quantum and classical memory required for exact heralded storage and retrieval of quantum measurements. Given only black-box access to the measurement channel, we construct an exact compression of the port-based program into an outcome-type record and a quantum register, with total dimension polynomial in the query count. For every universal retrieval processor we prove the bounds $Q+C\ge\log_2 n$ and $2Q+C\ge\log_2\bigl((n-1)d^2+1\bigr)$ on the numbers $Q$ of qubits and $C$ of bits of the program, for $n$-outcome POVMs on $\mathbb{C}^d$ with $d\ge2$. For $n\ge2$, no finite classical memory removes the need for quantum memory: any such processor requires a quantum program of dimension at least $d$, at that dimension its classical alphabet must have at least $n$ symbols, and both minima are attained by a single-query protocol with success $1/d^2$. Combining direct-program compression with a converse from approximate measurement programming gives logarithmic total-memory scaling in $1/(1-p)$ as the uniform success probability $p$ approaches one, at fixed $d,n\ge2$. At fixed input dimension and target success below one, the optimal total-memory scaling is logarithmic in $n$. We also construct self-contained programs under branch-decomposition access and compare the quantum and classical costs of all constructions, including where the outcome-type record is kept: for POVMs with $n$ nonzero rank-one effects the direct program admits a purely quantum allocation whose register is never larger than that of the minimal-Naimark unitary program and which succeeds more often whenever $n>d$.

quant-pharXiv:2610.36972•Oct 28, 2026•0 citations
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 paper asks how much coherent comparison access improves fixed-budget selection of a good-enough design. It studies nnn designs with an unknown strict order, an exact pairwise-comparison oracle, and one output label. Success means returning a top-rrr design; the objective is worst-case success using at most qqq queries. Random relabeling makes this equivalent to optimizing average success over uniformly random orders.
For every q<nq<nq<n, the classical optimum is Cq(n,r)=1−(n−rq+1)/(nq+1)C_q(n,r)=1-\binom{n-r}{q+1}/\binom{n}{q+1}Cq​(n,r)=1−(q+1n−r​)/(q+1n​), attained by sampling q+1q+1q+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)\min(2q,n-1)min(2q,n−1), versus min⁡(q,n−1)\min(q,n-1)min(q,n−1) classically; both bounds are attainable.
The quantum optimum is determined exactly for one comparison and every n,rn,rn,r, through an explicit cubic. For best-design selection, Q1(n,1)=[3(n−1)+13n2−18n+9]/(2n2)Q_1(n,1)=[3(n-1)+\sqrt{13n^2-18n+9}]/(2n^2)Q1​(n,1)=[3(n−1)+13n2−18n+9​]/(2n2), approaching 3.3028/n3.3028/n3.3028/n, compared with 2/n2/n2/n classically. One quantum comparison beats two classical comparisons exactly when n>9n>9n>9. For a top-half target, success approaches 1/2+2/4≈0.85361/2+\sqrt{2}/4\approx0.85361/2+2​/4≈0.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.
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.
Quantum computing has developed rapidly in recent years and has shown potential advantages over classical computing in various domains. In this paper, we study whether quantum computing can accelerate the convergence rate of discrete simulation optimization in the fixed-budget setting. We first formulate the quantum discrete simulation optimization problem by defining the quantum simulation oracle, the algorithmic performance measure, and the corresponding optimality guarantee. Based on this formulation, we establish a minimax lower bound on the expected optimality gap for any quantum algorithm. The lower bound analysis reduces the discrete simulation optimization problem to a sequential quantum phase-testing problem, and the resulting lower-bound argument may be of independent interest. By comparing the quantum lower bound with its classical counterpart, we show that the optimal convergence rate in the quantum setting exhibits a quadratic improvement in its dependence on the simulation budget, at the cost of a worse dependence on the number of decisions. We then propose the first fixed-budget quantum algorithm, called \textsc{QUEST}, for discrete simulation optimization. The algorithm combines a quantum Monte Carlo subroutine with a sequential elimination framework and uses a slow-measurement mechanism to help preserve quantum superposition during the optimization process. We prove that \textsc{QUEST} achieves the optimal convergence rate up to logarithmic factors. Numerical experiments further show that \textsc{QUEST} outperforms its classical counterpart, which provides empirical evidence for the quantum advantage in improving the convergence rate of discrete simulation optimization algorithms.
We study the problem of finding the maximum or the minimum of a given set S = {x₀, X₁, ... X n₋₁}, each element X i drawn from some finite universe [Unary] of real numbers. We assume that the inputs are abstracted within an oracle O where we can only gain information through unary comparisons in the form "Is Xi greater than, equal to, or less than some constant k?" Classically, this problem is solved optimally with a runtime of Θ(n +lg|U|). In the setting of Quantum Computing, we show that at least Ω(√n+lg|U|) queries are required to solve the problem even with bounded error. Combining variants of the Grover's search [1, 2] algorithm and the optimal classical unary extrema finding algorithm, we have derived a series of new quantum algorithms, some running in time as fast as O(√n lg*n+lg|U|). This shows that quantum computers can accelerate the speed in the unary comparison model asymptotically. Inspecting our tools, we find convincing arguments that our lower bound is most probably tight, but we may need an entirely new approach to solve the problem optimally. The technique used in our algorithm can also be extended to solve variations of quantum statistics problems. For instance, our result can be directly extended to approximation of extrema of real numbers, similar to that of [3]. Moreover, we can also solve the quantum k-select problem optimally in time O(√kn) with constant success probability. We hope that our ideas and tools will prove to be useful in other areas.
Quantum computing has advanced rapidly in recent years and has shown advantages in a variety of domains. In this paper, we investigate its potential for discrete simulation optimization in the fixed-confidence setting, a fundamental problem in the simulation literature. We first introduce a quantum simulation oracle that prepares a coherent superposition over all candidate solutions and provides the foundation for quantum algorithm design. Based on this oracle, we develop the first Grover-search-based quantum algorithm for discrete simulation optimization, called SOGAS. In particular, SOGAS uses a binary-search framework to progressively eliminate suboptimal solutions while carefully controlling the error probability, and eventually identifies a set of near-optimal solutions. We prove that SOGAS returns a near-optimal solution with probability at least the prescribed confidence level and achieves a quadratic speedup in the dependence of query complexity on the number of candidate solutions. Numerical experiments further show that SOGAS substantially outperforms classical benchmarks and provide empirical evidence for quantum advantage in discrete simulation optimization.
Gate model quantum computers with too many qubits to be simulated by available classical computers are about to arrive. We present a strategy for programming these devices without error correction or compilation. This means that the number of logical qubits is the same as the number of qubits on the device. The hardware determines which pairs of qubits can be addressed by unitary operators. The goal is to build quantum states that solve computational problems such as maximizing a combinatorial objective function or minimizing a Hamiltonian. These problems may not fit naturally on the physical layout of the qubits. Our algorithms use a sequence of parameterized unitaries that sit on the qubit layout to produce quantum states depending on those parameters. Measurements of the objective function (or Hamiltonian) guide the choice of new parameters with the goal of moving the objective function up (or lowering the energy). As an example we consider finding approximate solutions to MaxCut on 3-regular graphs whereas the hardware is physical qubits laid out on a rectangular grid. We prove that the lowest depth version of the Quantum Approximate Optimization Algorithm will achieve an approximation ratio of at least 0.5293 on all large enough instances which beats random guessing (0.5). We open up the algorithm to have different parameters for each single qubit XXX rotation and for each ZZZZZZ interaction associated with the nearest neighbor interactions on the grid. Small numerical experiments indicate that an enveloping classical algorithm can be used to find the parameters which sit on the grid to optimize an objective function with a different connectivity. We discuss strategies for finding good parameters but offer no evidence yet that the proposed approach can beat the best classical algorithms. Ultimately the strength of this approach will be determined by running on actual hardware.
We study the persistent quantum and classical memory required for exact heralded storage and retrieval of quantum measurements. Given only black-box access to the measurement channel, we construct an exact compression of the port-based program into an outcome-type record and a quantum register, with total dimension polynomial in the query count. For every universal retrieval processor we prove the bounds Q+C≥log⁡2nQ+C\ge\log_2 nQ+C≥log2​n and 2Q+C≥log⁡2((n−1)d2+1)2Q+C\ge\log_2\bigl((n-1)d^2+1\bigr)2Q+C≥log2​((n−1)d2+1) on the numbers QQQ of qubits and CCC of bits of the program, for nnn-outcome POVMs on Cd\mathbb{C}^dCd with d≥2d\ge2d≥2. For n≥2n\ge2n≥2, no finite classical memory removes the need for quantum memory: any such processor requires a quantum program of dimension at least ddd, at that dimension its classical alphabet must have at least nnn symbols, and both minima are attained by a single-query protocol with success 1/d21/d^21/d2. Combining direct-program compression with a converse from approximate measurement programming gives logarithmic total-memory scaling in 1/(1−p)1/(1-p)1/(1−p) as the uniform success probability ppp approaches one, at fixed d,n≥2d,n\ge2d,n≥2. At fixed input dimension and target success below one, the optimal total-memory scaling is logarithmic in nnn. We also construct self-contained programs under branch-decomposition access and compare the quantum and classical costs of all constructions, including where the outcome-type record is kept: for POVMs with nnn nonzero rank-one effects the direct program admits a purely quantum allocation whose register is never larger than that of the minimal-Naimark unitary program and which succeeds more often whenever n>dn>dn>d.