Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

National Conference on Artificial Intelligence

Explorations of Quantum-Classical Approaches to Scheduling a Mars Lander Activity Problem

Tony T. Tran, Zhihui Wang, N. Minh, Eleanor Gilbert Rieffel, Jeremy Frank, Bryan O’Gorman, Davide Venturelli, J. Christopher Beck

Published Feb 12, 2016• 10 citations
OpenAlex

Abstract

An effective approach to solving problems involving mixed (continuous and discrete) variables and constraints, such as hybrid systems, is to decompose them into subproblems and integrate dedicated solvers geared toward those subproblems. Here, we introduce a new framework based on a tree search algorithm to solve hybrid discrete-continuous problems that incorporates: (1) a quantum annealer that samples from the configuration space for the discrete portion and provides information about the quality of the samples, and (2) a classical computer that makes use of information from the quantum annealer to prune and focus the search as well as check a continuous constraint. We consider four variants of our algorithm, each with progressively more guidance from the results provided by the quantum annealer. We empirically test our algorithm and compare the variants on a simplified Mars Lander task scheduling problem. Variants with more guidance from the quantum annealer have better performance.

Related papers

A Hybrid Quantum-Classical Approach to Solving Scheduling Problems

Tony T. Tran, Minh Do, Eleanor Gilbert Rieffel +5 more

An effective approach to solving complex problems is to decompose them and integrate dedicated solvers for those subproblems. We introduce a hybrid decomposition that incorporates: (1) a quantum annealer that samples from the configuration space of a relaxed problem to obtain strong candidate solutions, and (2) a classical processor that maintains a global search tree and enforces constraints on the relaxed components of the problem. Our framework is the first to use quantum annealing as part of a complete search. We consider variants of our approach with differing amounts of guidance from the quantum annealer. We empirically test our algorithm and compare the variants on problems from three scheduling domains: graph-coloring-type scheduling, simplified Mars Lander task scheduling, and airport runway scheduling. While we were only able to test on problems of small sizes, due to the limitation of currently available quantum annealing hardware, the empirical results show that results obtained from the quantum annealer can be used for more effective search node pruning and to improve node selection heuristics when compared to a standard classical approach.

Proceedings of the International Symposium on Combinatorial Search•Sep 1, 2021•73 citations

Quantum-classical hybrid algorithm using quantum annealing for multi-objective job shop scheduling

Kenta Sawamura, Kensuke Araki, Naoki Maruyama +2 more

Efficient production planning is essential in modern manufacturing to improve performance indicators such as lead time and to reduce reliance on human intuition. While mathematical optimization approaches, formulated as job shop scheduling problems, have been applied to automate this process, solving large-scale production planning problems remains computationally demanding. Moreover, many practical scenarios involve conflicting objectives, making traditional scalarization techniques ineffective in finding diverse and useful Pareto-optimal solutions. To address these challenges, we developed a quantum-classical hybrid algorithm that decomposes the problem into two subproblems: resource allocation and task scheduling. Resource allocation is formulated as a quadratic unconstrained binary optimization problem and solved using annealing-based methods that efficiently explore complex solutions. Task scheduling is modeled as a mixed-integer linear programming problem and solved using conventional solvers to satisfy detailed scheduling constraints. We validated the proposed method using benchmark instances based on foundry production scenarios. Experimental results demonstrate that our hybrid approach achieves superior solution quality and computational efficiency compared to traditional monolithic methods. This work offers a promising direction for high-speed, multi-objective scheduling in industrial applications.

quant-pharXiv:2511.03257•Nov 6, 2025•0 citations

Solve Crude Oil Scheduling Problems by Using Quantum-Classical Hybrid Algorithms

Jian Yang, Bohang Wang, Lina Wang +5 more

The optimization of front-end crude oil scheduling is a critical determinant of refinery profitability and operational stability. However, the coupling of discrete logistics events (e.g., vessel berthing) with continuous material flows (e.g., pipeline transfers) renders this problem an NP-hard Mixed-Integer Linear Programming (MILP) challenge, often intractable for classical solvers at industrial scales. This study proposes a novel hybrid quantum-classical framework to address these computational bottlenecks. We employ Benders Decomposition to decouple the monolithic model into a discrete Master Problem (MP) and a continuous Subproblem (SP). To exploit the search capabilities of quantum computing, the MP is reformulated as a Quadratic Unconstrained Binary Optimization (QUBO) model and solved via a hybrid quantum solver, while the SP enforces mass balance and quality constraints through iterative optimality and feasibility cuts. Extensive experiments on 15 multi-scale instances demonstrate that the proposed framework significantly outperforms traditional metaheuristics (e.g., Genetic Algorithms, Tabu Search), reducing total operating costs by approximately 73--80% and achieving computational speeds comparable to state-of-the-art commercial solvers (Gurobi). By effectively leveraging global optimality cuts, the method overcomes the tendency of heuristic approaches to trap in local optima, providing a robust and scalable solution for complex refinery logistics.

quant-pharXiv:2604.26459•Apr 30, 2026•0 citations

A Hybrid Quantum-Classical Approach to the Electric Mobility Problem

Margarita Veshchezerova, Mikhail Somov, D. Bertsche +4 more

We suggest a hybrid quantum-classical routine for the NP-hard Electric Vehicle Fleet Charging and Allocation Problem. The original formulation is a Mixed Integer Linear Program with continuous variables and inequality constraints. To separate inequality constraints that are difficult for quantum routines we use a decomposition in master and pricing problems: the former targets the assignment of vehicles to reservations and the latter suggests vehicle exploitation plans that respect the battery state-of-charge constraints. The master problem is equivalent to the search for an optimal set partition. In our hybrid scheme, the master problem is reformulated in a quadratic unconstrained binary optimization problem which can be solved with quantum annealing on the DWave Advantage system. On large instances, we benchmark the performance of the decomposition technique with classical and quantum-inspired metaheuristics: simulated annealing, tabu search, and vector annealing by NEC. The numerical results with purely classical solvers are comparable to the solutions from the traditional mixed integer linear programming approaches in terms of solution quality while being faster. In addition, it scales better to larger instances. The major advantage of the proposed approach is that it enables quantum-based methods for this realistic problem with many inequality constraints. We show this by initial studies on DWave hardware where optimal solutions can be found for small instances.

arXiv:2310.02760•IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•9 citations

Hybrid Classical-Quantum Optimization Techniques for Solving Mixed-Integer Programming Problems in Production Scheduling

Akshay Ajagekar, Kumail Al Hamoud, Fengqi You

Quantum computing (QC) holds great promise to open up a new era of computing and has been receiving significant attention recently. To overcome the performance limitations of near-term QC, utilizing the current quantum computers to complement classical techniques for solving real-world problems is of utmost importance. In this paper, we develop QC-based solution strategies that exploit quantum annealing and classical optimization techniques for solving large-scale scheduling problems in manufacturing systems. The applications of the proposed algorithms are illustrated through two case studies in production scheduling. First, we present a hybrid QC-based solution approach for the job-shop scheduling problem. Second, we propose a hybrid QC-based parametric method for the multi-purpose batch scheduling problem with a fractional objective. The proposed hybrid algorithms can tackle optimization problems formulated as mixed-integer linear and mixed-integer fractional programs, respectively, and provide feasibility guarantees. Performance comparison between state-of-the-art exact and heuristic solvers and the proposed QC-based hybrid solution techniques is presented for both job-shop and batch scheduling problems. Unlike conventional classical solution techniques, the proposed hybrid frameworks harness quantum annealing to supplement established deterministic optimization algorithms and demonstrate performance efficiency over standard off-the-shelf optimization solvers.

IEEE Transactions on Quantum Engineering•Jan 1, 2022•48 citations

Title: Quantum-Enhanced Constraint Satisfaction Problem Solving with Hybrid Search

Jincheng Zhang

Quantum annealing is a promising approach to solving constraint satisfaction problems (CSPs) due to its potential to escape local optima and explore the solution space more efficiently. However, traditional CSP solvers often struggle with highly complex, multi-variable problems. This paper investigates a novel hybrid search strategy that integrates quantum annealing with a modified CSP solver, leveraging quantum tunneling to accelerate the search process. We demonstrate that this approach significantly improves the speed and accuracy of solving complex CSPs compared to existing methods. The core mechanism involves combining quantum annealing with a dynamically adjusted CSP solver to effectively manage the high dimensionality of the problem. This work presents a new framework for tackling challenging CSPs with enhanced search capabilities.

•Sep 2, 2026•0 citations
An effective approach to solving problems involving mixed (continuous and discrete) variables and constraints, such as hybrid systems, is to decompose them into subproblems and integrate dedicated solvers geared toward those subproblems. Here, we introduce a new framework based on a tree search algorithm to solve hybrid discrete-continuous problems that incorporates: (1) a quantum annealer that samples from the configuration space for the discrete portion and provides information about the quality of the samples, and (2) a classical computer that makes use of information from the quantum annealer to prune and focus the search as well as check a continuous constraint. We consider four variants of our algorithm, each with progressively more guidance from the results provided by the quantum annealer. We empirically test our algorithm and compare the variants on a simplified Mars Lander task scheduling problem. Variants with more guidance from the quantum annealer have better performance.
An effective approach to solving complex problems is to decompose them and integrate dedicated solvers for those subproblems. We introduce a hybrid decomposition that incorporates: (1) a quantum annealer that samples from the configuration space of a relaxed problem to obtain strong candidate solutions, and (2) a classical processor that maintains a global search tree and enforces constraints on the relaxed components of the problem. Our framework is the first to use quantum annealing as part of a complete search. We consider variants of our approach with differing amounts of guidance from the quantum annealer. We empirically test our algorithm and compare the variants on problems from three scheduling domains: graph-coloring-type scheduling, simplified Mars Lander task scheduling, and airport runway scheduling. While we were only able to test on problems of small sizes, due to the limitation of currently available quantum annealing hardware, the empirical results show that results obtained from the quantum annealer can be used for more effective search node pruning and to improve node selection heuristics when compared to a standard classical approach.
Efficient production planning is essential in modern manufacturing to improve performance indicators such as lead time and to reduce reliance on human intuition. While mathematical optimization approaches, formulated as job shop scheduling problems, have been applied to automate this process, solving large-scale production planning problems remains computationally demanding. Moreover, many practical scenarios involve conflicting objectives, making traditional scalarization techniques ineffective in finding diverse and useful Pareto-optimal solutions. To address these challenges, we developed a quantum-classical hybrid algorithm that decomposes the problem into two subproblems: resource allocation and task scheduling. Resource allocation is formulated as a quadratic unconstrained binary optimization problem and solved using annealing-based methods that efficiently explore complex solutions. Task scheduling is modeled as a mixed-integer linear programming problem and solved using conventional solvers to satisfy detailed scheduling constraints. We validated the proposed method using benchmark instances based on foundry production scenarios. Experimental results demonstrate that our hybrid approach achieves superior solution quality and computational efficiency compared to traditional monolithic methods. This work offers a promising direction for high-speed, multi-objective scheduling in industrial applications.
The optimization of front-end crude oil scheduling is a critical determinant of refinery profitability and operational stability. However, the coupling of discrete logistics events (e.g., vessel berthing) with continuous material flows (e.g., pipeline transfers) renders this problem an NP-hard Mixed-Integer Linear Programming (MILP) challenge, often intractable for classical solvers at industrial scales. This study proposes a novel hybrid quantum-classical framework to address these computational bottlenecks. We employ Benders Decomposition to decouple the monolithic model into a discrete Master Problem (MP) and a continuous Subproblem (SP). To exploit the search capabilities of quantum computing, the MP is reformulated as a Quadratic Unconstrained Binary Optimization (QUBO) model and solved via a hybrid quantum solver, while the SP enforces mass balance and quality constraints through iterative optimality and feasibility cuts. Extensive experiments on 15 multi-scale instances demonstrate that the proposed framework significantly outperforms traditional metaheuristics (e.g., Genetic Algorithms, Tabu Search), reducing total operating costs by approximately 73--80% and achieving computational speeds comparable to state-of-the-art commercial solvers (Gurobi). By effectively leveraging global optimality cuts, the method overcomes the tendency of heuristic approaches to trap in local optima, providing a robust and scalable solution for complex refinery logistics.
We suggest a hybrid quantum-classical routine for the NP-hard Electric Vehicle Fleet Charging and Allocation Problem. The original formulation is a Mixed Integer Linear Program with continuous variables and inequality constraints. To separate inequality constraints that are difficult for quantum routines we use a decomposition in master and pricing problems: the former targets the assignment of vehicles to reservations and the latter suggests vehicle exploitation plans that respect the battery state-of-charge constraints. The master problem is equivalent to the search for an optimal set partition. In our hybrid scheme, the master problem is reformulated in a quadratic unconstrained binary optimization problem which can be solved with quantum annealing on the DWave Advantage system. On large instances, we benchmark the performance of the decomposition technique with classical and quantum-inspired metaheuristics: simulated annealing, tabu search, and vector annealing by NEC. The numerical results with purely classical solvers are comparable to the solutions from the traditional mixed integer linear programming approaches in terms of solution quality while being faster. In addition, it scales better to larger instances. The major advantage of the proposed approach is that it enables quantum-based methods for this realistic problem with many inequality constraints. We show this by initial studies on DWave hardware where optimal solutions can be found for small instances.
Quantum computing (QC) holds great promise to open up a new era of computing and has been receiving significant attention recently. To overcome the performance limitations of near-term QC, utilizing the current quantum computers to complement classical techniques for solving real-world problems is of utmost importance. In this paper, we develop QC-based solution strategies that exploit quantum annealing and classical optimization techniques for solving large-scale scheduling problems in manufacturing systems. The applications of the proposed algorithms are illustrated through two case studies in production scheduling. First, we present a hybrid QC-based solution approach for the job-shop scheduling problem. Second, we propose a hybrid QC-based parametric method for the multi-purpose batch scheduling problem with a fractional objective. The proposed hybrid algorithms can tackle optimization problems formulated as mixed-integer linear and mixed-integer fractional programs, respectively, and provide feasibility guarantees. Performance comparison between state-of-the-art exact and heuristic solvers and the proposed QC-based hybrid solution techniques is presented for both job-shop and batch scheduling problems. Unlike conventional classical solution techniques, the proposed hybrid frameworks harness quantum annealing to supplement established deterministic optimization algorithms and demonstrate performance efficiency over standard off-the-shelf optimization solvers.
Quantum annealing is a promising approach to solving constraint satisfaction problems (CSPs) due to its potential to escape local optima and explore the solution space more efficiently. However, traditional CSP solvers often struggle with highly complex, multi-variable problems. This paper investigates a novel hybrid search strategy that integrates quantum annealing with a modified CSP solver, leveraging quantum tunneling to accelerate the search process. We demonstrate that this approach significantly improves the speed and accuracy of solving complex CSPs compared to existing methods. The core mechanism involves combining quantum annealing with a dynamically adjusted CSP solver to effectively manage the high dimensionality of the problem. This work presents a new framework for tackling challenging CSPs with enhanced search capabilities.