QISS: Quantum Industrial Shift Scheduling Algorithm
- URL: http://arxiv.org/abs/2401.07763v1
- Date: Mon, 15 Jan 2024 15:20:41 GMT
- Title: QISS: Quantum Industrial Shift Scheduling Algorithm
- Authors: Anna M. Krol, Marvin Erdmann, Rajesh Mishra, Phattharaporn Singkanipa,
Ewan Munro, Marcin Ziolkowski, Andre Luckow, Zaid Al-Ars
- Abstract summary: We show the design and implementation of a quantum algorithm for industrial shift scheduling (QISS)
We give an explicit circuit construction of the Grover's oracle, incorporating the multiple constraints present in the problem.
We provide an open-source repository with our code, available onanneriet.com/anneriet/QISS.
- Score: 1.2746940882175868
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we show the design and implementation of a quantum algorithm
for industrial shift scheduling (QISS), which uses Grover's adaptive search to
tackle a common and important class of valuable, real-world combinatorial
optimization problems. We give an explicit circuit construction of the Grover's
oracle, incorporating the multiple constraints present in the problem, and
detail the corresponding logical-level resource requirements. Further, we
simulate the application of QISS to specific small-scale problem instances to
corroborate the performance of the algorithm, and we provide an open-source
repository with our code, available on github.com/anneriet/QISS . Our work
shows how complex real-world industrial optimization problems can be formulated
in the context of Grover's algorithm, and paves the way towards important tasks
such as physical-level resource estimation for this category of use cases.
Related papers
- Quantum Algorithms for Drone Mission Planning [0.0]
Mission planning often involves optimising the use of ISR (Intelligence, Surveillance and Reconnaissance) assets in order to achieve a set of mission objectives.
Finding such solutions is often an NP-Hard problem and cannot be solved efficiently on classical computers.
We investigate near term quantum algorithms that have the potential to offer speed-ups against current classical methods.
arXiv Detail & Related papers (2024-09-27T10:58:25Z) - Multi-Objective Optimization and Network Routing with Near-Term Quantum
Computers [0.2150989251218736]
We develop a scheme with which near-term quantum computers can be applied to solve multi-objective optimization problems.
We focus on an implementation based on the quantum approximate optimization algorithm (QAOA)
arXiv Detail & Related papers (2023-08-16T09:22:01Z) - Qubit efficient quantum algorithms for the vehicle routing problem on
NISQ processors [48.68474702382697]
Vehicle routing problem with time windows (VRPTW) is a common optimization problem faced within the logistics industry.
In this work, we explore the use of a previously-introduced qubit encoding scheme to reduce the number of binary variables.
arXiv Detail & Related papers (2023-06-14T13:44:35Z) - MARLIN: Soft Actor-Critic based Reinforcement Learning for Congestion
Control in Real Networks [63.24965775030673]
We propose a novel Reinforcement Learning (RL) approach to design generic Congestion Control (CC) algorithms.
Our solution, MARLIN, uses the Soft Actor-Critic algorithm to maximize both entropy and return.
We trained MARLIN on a real network with varying background traffic patterns to overcome the sim-to-real mismatch.
arXiv Detail & Related papers (2023-02-02T18:27:20Z) - Solving workflow scheduling problems with QUBO modeling [0.0]
We develop a novel QUBO to represent our scheduling problem and show how the QUBO depends complexity on the input problem.
We derive and present a decomposition method for this specific application to mitigate this complexity.
arXiv Detail & Related papers (2022-05-10T12:38:17Z) - Optimizing Tensor Network Contraction Using Reinforcement Learning [86.05566365115729]
We propose a Reinforcement Learning (RL) approach combined with Graph Neural Networks (GNN) to address the contraction ordering problem.
The problem is extremely challenging due to the huge search space, the heavy-tailed reward distribution, and the challenging credit assignment.
We show how a carefully implemented RL-agent that uses a GNN as the basic policy construct can address these challenges.
arXiv Detail & Related papers (2022-04-18T21:45:13Z) - Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
We quantify scaling of the expected resource requirements by optimized circuits for hardware architectures with varying levels of connectivity.
We show the number of measurements, and hence total time to synthesizing solution, grows exponentially in problem size and problem graph degree.
These problems may be alleviated by increasing hardware connectivity or by recently proposed modifications to the QAOA that achieve higher performance with fewer circuit layers.
arXiv Detail & Related papers (2022-01-06T21:02:30Z) - Adaptive Discretization in Online Reinforcement Learning [9.560980936110234]
Two major questions in designing discretization-based algorithms are how to create the discretization and when to refine it.
We provide a unified theoretical analysis of tree-based hierarchical partitioning methods for online reinforcement learning.
Our algorithms are easily adapted to operating constraints, and our theory provides explicit bounds across each of the three facets.
arXiv Detail & Related papers (2021-10-29T15:06:15Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem.
We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
arXiv Detail & Related papers (2020-09-15T18:17:27Z) - Iterative Algorithm Induced Deep-Unfolding Neural Networks: Precoding
Design for Multiuser MIMO Systems [59.804810122136345]
We propose a framework for deep-unfolding, where a general form of iterative algorithm induced deep-unfolding neural network (IAIDNN) is developed.
An efficient IAIDNN based on the structure of the classic weighted minimum mean-square error (WMMSE) iterative algorithm is developed.
We show that the proposed IAIDNN efficiently achieves the performance of the iterative WMMSE algorithm with reduced computational complexity.
arXiv Detail & Related papers (2020-06-15T02:57:57Z)
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.