Evaluation of Quantum Annealing-based algorithms for flexible job shop scheduling

• URL: http://arxiv.org/abs/2408.15671v1
• Date: Wed, 28 Aug 2024 09:52:14 GMT
• Title: Evaluation of Quantum Annealing-based algorithms for flexible job shop scheduling
• Authors: Philipp Schworm, Xiangqian Wu, Matthias Klar, Jan C. Aurich,
• Abstract summary: A flexible job shop scheduling problem (FJSSP) poses a complex optimization task. approximation methods are employed to ensure solutions are within acceptable timeframes. Quantum Annealing, a metaheuristic leveraging quantum mechanical effects, demonstrates superior solution quality in a shorter time.
• Score: 9.674641730446748
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A flexible job shop scheduling problem (FJSSP) poses a complex optimization task in modeling real-world process scheduling tasks with conflicting objectives. To tackle FJSSPs, approximation methods are employed to ensure solutions are within acceptable timeframes. Quantum Annealing, a metaheuristic leveraging quantum mechanical effects, demonstrates superior solution quality in a shorter time compared to classical algorithms. However, due to hardware limitations of quantum annealers, hybrid algorithms become essential for solving larger FJSSPs. This paper investigates the threshold problem sizes up to which quantum annealers are sufficient and when hybrid algorithms are required, highlighting the distribution of computing power in hybrid methods.

Related papers

• 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)
• Hybrid Quantum-HPC Solutions for Max-Cut: Bridging Classical and Quantum Algorithms [0.0]
  We develop a theoretical model to analyze the time complexity, scalability, and communication overhead in hybrid systems. We evaluate QAOA's performance on small-scale Max-Cut instances, benchmarking its runtime, solution accuracy, and resource utilization.
  arXiv  Detail & Related papers  (2024-10-21T04:10:54Z)
• A Monte Carlo Tree Search approach to QAOA: finding a needle in the haystack [0.0]
  variational quantum algorithms (VQAs) are a promising family of hybrid quantum-classical methods tailored to cope with the limited capability of near-term quantum hardware. We show that leveraging regular parameter patterns deeply affects the decision-tree structure and allows for a flexible and noise-resilient optimization strategy.
  arXiv  Detail & Related papers  (2024-08-22T18:00:02Z)
• Multi-objective Quantum Annealing approach for solving flexible job shop scheduling in manufacturing [0.0]
  This paper introduces Quantum Annealing-based solving algorithm (QASA) to address Flexible Job Shop Scheduling problem. Experiments on benchmark problems show QASA, combining tabu search, simulated annealing, and Quantum Annealing, outperforms a classical solving algorithm (CSA) in solution quality.
  arXiv  Detail & Related papers  (2023-11-16T07:45:57Z)
• Elastic Entangled Pair and Qubit Resource Management in Quantum Cloud Computing [73.7522199491117]
  Quantum cloud computing (QCC) offers a promising approach to efficiently provide quantum computing resources. The fluctuations in user demand and quantum circuit requirements are challenging for efficient resource provisioning. We propose a resource allocation model to provision quantum computing and networking resources.
  arXiv  Detail & Related papers  (2023-07-25T00:38:46Z)
• 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)
• Integer Programming from Quantum Annealing and Open Quantum Systems [0.8049701904919515]
  We develop an algorithm that solves integer linear programming problems, a classically NP-hard problem, on a quantum annealer. We find that the algorithm outperforms random guessing but is limited to small problems.
  arXiv  Detail & Related papers  (2020-09-24T22:18:01Z)
• 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)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)

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.