Quantum Grover Adaptive Search for Discrete Simulation Optimization

• URL: http://arxiv.org/abs/2604.26277v1
• Date: Wed, 29 Apr 2026 04:17:22 GMT
• Title: Quantum Grover Adaptive Search for Discrete Simulation Optimization
• Abstract summary: We introduce a quantum simulation oracle that prepares a coherent superposition over all candidate solutions.<n>We develop the first Grover-search-based quantum algorithm for discrete simulation optimization, called SOGAS.
• Score: 5.848643785361479
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Stochastic Pauli-path simulator for large-scale quantum optimization [57.179828941706006]
  Pauli-path simulators offer a promising route to large-scale classical simulation of quantum circuits in the low-magic regime.<n>Existing approaches either lack native support for gradient-based optimization or suffer from severe gradient bias.<n>Here we propose the Pauli-path simulator (SPPS), a computational framework for large-scale quantum optimization.
  arXiv  Detail & Related papers  (2026-07-20T10:43:44Z)
• Quantum optimisation applied to the Quadratic Assignment Problem [4.483208369550461]
  This paper investigates the performance of the emerging non-variational Quantum Walk-based optimisation algorithm (NV-QWOA) for solving small instances of the Quadratic Assignment Problem (QAP)<n>Performance is evaluated using two metrics: the number of objective function evaluations and the number of algorithm iterations required to consistently reach optimal or near optimal solutions across QAP instances with 5 to 10 facilities.<n>Our findings highlight the practical utility of quantum walks for complex quantum problems and establish a foundation for future quantum optimisation algorithms.
  arXiv  Detail & Related papers  (2026-01-03T07:50:03Z)
• Hot-Starting Quantum Portfolio Optimization [39.916647837440316]
  Combinatorial optimization with a smooth and convex objective function arises naturally in applications such as discrete mean-variance portfolio optimization.<n>We introduce a novel approach that restricts the search space to discrete solutions in the vicinity of the continuous optimum by constructing a compact Hilbert space.<n> Experiments on software solvers and a D-Wave Advantage quantum annealer demonstrate that our method outperforms state-of-the-art techniques.
  arXiv  Detail & Related papers  (2025-10-13T08:47:43Z)
• Quantum Simulation-Based Optimization of a Cooling System [0.0]
  Quantum algorithms promise up to exponential speedups for specific tasks relevant to numerical simulations.<n>However, these advantages quickly vanish when considering data input and output on quantum computers.<n>The recently introduced Quantum Simulation-Based Optimization (QuSO) treats simulations as subproblems within a larger optimization.
  arXiv  Detail & Related papers  (2025-04-21T21:58:21Z)
• Branch-and-bound digitized counterdiabatic quantum optimization [39.58317527488534]
  Branch-and-bound algorithms effectively solve convex optimization problems, relying on the relaxation the objective function to obtain tight lower bounds.<n>We propose a branch-and-bound digitized counterdiabatic quantum optimization (BB-DCQO) algorithm that addresses the relaxation difficulties.
  arXiv  Detail & Related papers  (2025-04-21T18:19:19Z)
• Performance Benchmarking of Quantum Algorithms for Hard Combinatorial Optimization Problems: A Comparative Study of non-FTQC Approaches [0.0]
  This study systematically benchmarks several non-fault-tolerant quantum computing algorithms across four distinct optimization problems. Our benchmark includes noisy intermediate-scale quantum (NISQ) algorithms, such as the variational quantum eigensolver. Our findings reveal that no single non-FTQC algorithm performs optimally across all problem types, underscoring the need for tailored algorithmic strategies.
  arXiv  Detail & Related papers  (2024-10-30T08:41:29Z)
• Quantum evolutionary algorithm for TSP combinatorial optimisation problem [0.0]
  This paper implements a new way of solving a problem called the traveling salesman problem (TSP) using quantum genetic algorithm (QGA) We compared how well this new approach works to the traditional method known as a classical genetic algorithm (CGA)
  arXiv  Detail & Related papers  (2024-09-20T08:27:42Z)
• Optimization by Decoded Quantum Interferometry [38.063836468778895]
  We introduce Decoded Quantum Interferometry (DQI), a quantum algorithm that uses the quantum Fourier transform to reduce optimization problems to decoding problems.<n>For approximating optimal fits over finite fields, DQI achieves a superpolynomial speedup over known classical algorithms.
  arXiv  Detail & Related papers  (2024-08-15T17:47:42Z)
• Guess What Quantum Computing Can Do for Test Case Optimization [43.89456212504871]
  In the near term, quantum approximate optimization algorithms (QAOAs) hold great potential to solve optimization problems. We present the first effort to formulate a software test case optimization problem as a QAOA problem and solve it on quantum computer simulators. To solve bigger test optimization problems that require many qubits, which are unavailable these days, we integrate a problem decomposition strategy with the QAOA.
  arXiv  Detail & Related papers  (2023-12-24T21:25:31Z)
• A Review on Quantum Approximate Optimization Algorithm and its Variants [47.89542334125886]
  The Quantum Approximate Optimization Algorithm (QAOA) is a highly promising variational quantum algorithm that aims to solve intractable optimization problems. This comprehensive review offers an overview of the current state of QAOA, encompassing its performance analysis in diverse scenarios. We conduct a comparative study of selected QAOA extensions and variants, while exploring future prospects and directions for the algorithm.
  arXiv  Detail & Related papers  (2023-06-15T15:28:12Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem. The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
  arXiv  Detail & Related papers  (2023-04-18T11:57:15Z)
• A Hybrid Quantum-Classical Algorithm for Robust Fitting [47.42391857319388]
  We propose a hybrid quantum-classical algorithm for robust fitting. Our core contribution is a novel robust fitting formulation that solves a sequence of integer programs. We present results obtained using an actual quantum computer.
  arXiv  Detail & Related papers  (2022-01-25T05:59:24Z)
• Quantum-Enhanced Simulation-Based Optimization [0.8057006406834467]
  Simulation-based optimization seeks to optimize an objective function that is computationally expensive to evaluate exactly. Quantum Amplitude Estimation (QAE) can achieve a quadratic speed-up over classical Monte Carlo simulation.
  arXiv  Detail & Related papers  (2020-05-21T17:02:59Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.