A Non-Variational Quantum Approach to the Job Shop Scheduling Problem
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908701199171584 |
|---|---|
| author | Lopez-Ruiz, Miguel Angel Tucker, Emily L. Arnold, Emma M. Epifanovsky, Evgeny Kaushik, Ananth Roetteler, Martin |
| author_facet | Lopez-Ruiz, Miguel Angel Tucker, Emily L. Arnold, Emma M. Epifanovsky, Evgeny Kaushik, Ananth Roetteler, Martin |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_26859 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Non-Variational Quantum Approach to the Job Shop Scheduling Problem Lopez-Ruiz, Miguel Angel Tucker, Emily L. Arnold, Emma M. Epifanovsky, Evgeny Kaushik, Ananth Roetteler, Martin Quantum Physics Emerging Technologies 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. |
| title | A Non-Variational Quantum Approach to the Job Shop Scheduling Problem |
| topic | Quantum Physics Emerging Technologies |
| url | https://arxiv.org/abs/2510.26859 |