EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

3765. A quantum search algorithm exploiting specific time windows structure. Application to production units planning problems.

Invited abstract in session MB-42: Decomposition methods for Quantum Optimization, stream Quantum Computing Optimization.

Monday, 10:30-12:00
Room: 98 (building: 306)

Authors (first author is the speaker)

1. Rodolphe Griset

Abstract

Quantum search, spurred by Grover's algorithm in 1996, has long held promise in quantum computing for its quadratic speedup over classical algorithms in unsorted set searches. However, demonstrating a quantum advantage on finding the best solution to a combinatorial problems is not straightforward due to the existence of efficient classical heuristics, unsufficient speedup and inherent quantum noise. In this study, we investigate a novel approach: constructing a superposition of states of reduced size by leveraging problem structure before employing quantum search algorithms. We apply this methodology to a multi-machine job scheduling problem characterized by specific time window structures, local job constraints within machines, and resource limitations. Our objective is to minimize costs associated with job dates, aiming to identify solutions below a predefined threshold. This model is particularly suited for multi-year planning in power plant maintenance, where machines represent production units and jobs signify maintenance outages for specific units. We exploit the unique structure of spacing constraints between jobs and structured time windows to create a superposition of state subspaces. Subsequently, we apply amplitude amplification by designing two oracles to account for resource constraints and the cost function. This innovative approach holds promise for improving the efficiency and effectiveness of quantum optimization techniques in real-world applications.

Keywords

Status: accepted

Back to the list of papers