Rate-Optimal Quantum Discrete Simulation Optimization

@misc{hu2026rateoptimal,
  title = {{Rate-Optimal Quantum Discrete Simulation Optimization}},
  author = {Mingjie Hu and Jian-Qiang Hu},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.03360},
  eprint = {2610.03360},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.03360},
}

TY  - UNPB
TI  - Rate-Optimal Quantum Discrete Simulation Optimization
AU  - Mingjie Hu
AU  - Jian-Qiang Hu
PY  - 2026
DA  - 2026/10/02
PB  - arXiv
DO  - 10.48550/arxiv.2610.03360
UR  - https://arxiv.org/abs/2610.03360
AB  - 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.
ER  -