Quantum Algorithms for Discrete Optimization

Stefan Creemers, Luis Fernando Pérez Armas

Ioannis Liliopoulos, Georgios D. Varsamis, Ioannis G. Karafyllidis

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.

M. Gushansky, V. A. Prilip, M. V. Vershina

Variational quantum algorithms are at the forefront of modeling fault-tolerant quantum devices of the near future. While most variational quantum algorithms use only continuous optimization variables, their representative power can sometimes be greatly increased by adding certain discrete optimization variables, as illustrated by the example of the generalized quantum approximation optimization algorithm. However, the hybrid discrete-continuous optimization problem poses an optimization problem. The paper proposes a new algorithm that combines the Monte Carlo tree search method with an improved gradient solver to optimize discrete and continuous variables in a quantum circuit, respectively. The algorithm has been found to have excellent noise tolerance properties and is superior to prior algorithms in the field.

Ansh Bansal

Dilnoz Muhamediyeva, Rustam Raximov, Shavkat Urokov