arXiv:2610.03360
Rate-Optimal Quantum Discrete Simulation Optimization
Mingjie Hu, Jian-Qiang Hu
Abstract
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.
AI Summary
The paper studies fixed-budget selection of the largest-mean decision among $K$ stochastic alternatives, measuring performance by expected optimality gap (simple regret) after $T$ simulation queries. Its oracle model provides a separate quantum sampling unitary for each decision, rather than coherent access across decision indices. Outputs are assumed sub-Gaussian with fixed noise scale, with means in $[0,1]$. For $K>1$ and $T\ge K-1$, it establishes a quantum minimax lower bound $\Omega(K/T)$, compared with the classical bound $\Omega(\sqrt{K/T})$. The quantum argument constructs Bernoulli instances and alternatives in which a different decision becomes optimal, reduces their discrimination to sequential quantum phase testing, and uses the polynomial method to bound testing error in terms of the expected number of queries to that decision. The proposed QUEST algorithm combines sequential elimination with a quantum mean-estimation subroutine requiring $O(\epsilon^{-1}\log(1/\delta))$ queries at fixed noise scale. It halves estimation tolerances between rounds, measures estimates after each batch, and eliminates inferior candidates. Controlling estimation failures and the final tolerance yields expected gap $O(K\log T/T)$, matching the lower bound up to logarithmic factors. Qiskit simulations compare QUEST with a Monte Carlo counterpart on small decision sets and several output distributions. The analysis assumes quantum simulation oracles are available and concerns query budgets; continuous distributions require finite discretization. The experiments also include Student-$t$ observations outside the sub-Gaussian assumptions. Continuous decision spaces and more complex simulation objectives remain future directions.
Central claim may not hold: The central minimax-optimality claim depends on a sequential quantum testing lemma whose proof, along with the promised technical appendix, is absent from the supplied manuscript. The continuous-distribution experiments compare a 16-point quantum approximation with an insufficiently specified classical comparator, without controlling truncation or discretization bias.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.