A Non-Variational Quantum Approach to the Job Shop Scheduling Problem

• URL: http://arxiv.org/abs/2510.26859v1
• Date: Thu, 30 Oct 2025 16:14:13 GMT
• Title: A Non-Variational Quantum Approach to the Job Shop Scheduling Problem
• Authors: Miguel Angel Lopez-Ruiz, Emily L. Tucker, Emma M. Arnold, Evgeny Epifanovsky, Ananth Kaushik, Martin Roetteler,
• Abstract summary: We introduce Iterative-QAOA, a variant of QAOA designed to mitigate near-term hardware limitations.<n>We benchmark the algorithm on Just-in-Time Job Shop Scheduling Problem (JIT-JSSP) instances on IonQ Forte Generation QPUs.<n>We find that Iterative-QAOA robustly converges to find optimal solutions as well as high-quality, near-optimal solutions for all problem instances evaluated.
• Score: 0.3078691410268859
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum heuristics offer a potential advantage for combinatorial optimization but are constrained by near-term hardware limitations. We introduce Iterative-QAOA, a variant of QAOA designed to mitigate these constraints. The algorithm combines a non-variational, shallow-depth circuit approach using fixed-parameter schedules with an iterative warm-starting process. We benchmark the algorithm on Just-in-Time Job Shop Scheduling Problem (JIT-JSSP) instances on IonQ Forte Generation QPUs, representing some of the largest such problems ever executed on quantum hardware. We compare the performance of the algorithm against both the Variational Quantum Imaginary Time Evolution (VarQITE) algorithm and the non-variational Linear Ramp (LR) QAOA algorithm. We find that Iterative-QAOA robustly converges to find optimal solutions as well as high-quality, near-optimal solutions for all problem instances evaluated. We evaluate the algorithm on larger problem instances up to 97 qubits using tensor network simulations. The scaling behavior of the algorithm indicates potential for solving industrial-scale problems on fault-tolerant quantum computers.

Related papers

• Quantum Computing for Optimizing Aircraft Loading [1.055551340663609]
  The aircraft loading optimization problem is a computationally hard problem with the best known classical algorithm scaling exponentially with the number of objects.<n>We propose a quantum approach based on a multi-angle variant of the QAOA algorithm (MAL-VQA) designed to utilize a smaller number of two qubit gates in the quantum circuit.<n>We demonstrate the performance of the algorithm on different instances of the aircraft loading problem by execution on IonQ QPUs Aria and Forte.
  arXiv  Detail & Related papers  (2025-04-02T10:10:11Z)
• Classical optimization with imaginary time block encoding on quantum computers: The MaxCut problem [1.354560757162539]
  We develop a new method, called ITE-BE, based on a recent imaginary time algorithm.<n>We demonstrate that our method can be successfully combined with other quantum algorithms.
  arXiv  Detail & Related papers  (2024-11-16T08:17:36Z)
• Variational Quantum Algorithms for the Allocation of Resources in a Cloud/Edge Architecture [1.072460284847973]
  We show that Variational Quantum Algorithms can be a viable alternative to classical algorithms in the near future. In particular, we compare the performances, in terms of success probability, of two algorithms, i.e., Quantum Approximate Optimization Algorithm (QAOA) and Variational Quantum Eigensolver (VQE) The simulation experiments, performed for a set of simple problems, %CM230124 that involve a Cloud and two Edge nodes, show that the VQE algorithm ensures better performances when it is equipped with appropriate circuit textitansatzes that are able to restrict the search space
  arXiv  Detail & Related papers  (2024-01-25T17:37:40Z)
• 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)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time. As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware. We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
  arXiv  Detail & Related papers  (2022-02-17T18:59:20Z)
• 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)
• 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)
• Quadratic Unconstrained Binary Optimisation via Quantum-Inspired Annealing [58.720142291102135]
  We present a classical algorithm to find approximate solutions to instances of quadratic unconstrained binary optimisation. We benchmark our approach for large scale problem instances with tuneable hardness and planted solutions.
  arXiv  Detail & Related papers  (2021-08-18T09:26:17Z)
• 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)
• An adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer [0.0]
  The quantum approximate optimization algorithm (QAOA) is a hybrid variational quantum-classical algorithm that solves optimization problems. We develop an iterative version of QAOA that is problem-tailored, and which can also be adapted to specific hardware constraints. We simulate the algorithm on a class of Max-Cut graph problems and show that it converges much faster than the standard QAOA.
  arXiv  Detail & Related papers  (2020-05-20T18:00:01Z)

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.