Quantum Iterative-QAOA Solves Job Shop Scheduling on 97 Qubit IonQ Forte QPUs

The challenge of efficiently scheduling complex tasks, such as those found in manufacturing and logistics, often pushes the limits of classical computing power. Miguel Angel Lopez-Ruiz from IonQ Inc., Emily L. Tucker and Emma M. Arnold from Clemson University, along with Evgeny Epifanovsky, Ananth Kaushik and Martin Roetteler from IonQ Inc., present a new approach to tackling this problem using quantum computation. Their work introduces a novel algorithm that sidesteps the limitations of current quantum hardware by employing a shallow-depth circuit and an iterative refinement process. The team successfully demonstrates the algorithm’s ability to find optimal and near-optimal solutions for complex job shop scheduling problems, even on some of the largest instances yet run on actual quantum processors, and simulations suggest it holds promise for solving industrial-scale challenges on future, more powerful quantum computers.

This method employs a quantum-enhanced local search, utilising a quantum circuit to generate and evaluate potential solutions, harnessing the superposition and entanglement capabilities of quantum systems to explore a wider range of possibilities than classical algorithms. The quantum circuit creates diverse schedules, and a classical cost function assesses their performance, guiding the iterative improvement process. This allows the algorithm to efficiently navigate the complex landscape of possible schedules, seeking optimal or near-optimal solutions. The team demonstrates the feasibility of this approach on small to medium-sized problems, achieving competitive results compared to classical heuristics, establishing a pathway for utilising near-term quantum computers to address challenging combinatorial optimisation problems.

QAOA Advances for Combinatorial Optimisation

Research broadly explores core quantum optimisation algorithms and techniques, including a significant focus on the Quantum Approximate Optimisation Algorithm (QAOA). Investigations cover understanding when QAOA can outperform classical algorithms, how its performance scales with problem size, and techniques for optimising the algorithm’s parameters, with warm-starting, using classical solutions to improve convergence, as a key area. Researchers are also exploring different quantum circuit structures and mixers to improve QAOA’s expressibility, leveraging problem symmetries to reduce the search space, and investigating the Variational Quantum Eigensolver (VQE). Techniques to map continuous optimisation problems into discrete quantum circuits, and quantum circuit learning using machine learning, are also prominent themes.

Addressing the challenges of quantum optimisation, with researchers investigating problem decomposition, efficient embedding strategies, noise mitigation techniques, and scalability, is another key focus, alongside classical-quantum hybrid approaches. Specific applications, such as the job shop scheduling problem, are also being investigated, with research focusing on decomposition techniques, constraint modelling, and hybrid algorithms. The research also includes relevant hardware and implementation aspects, including trapped ion quantum computers, quantum hardware benchmarking, and scalable quantum computing architectures. The progression of research is evident, starting with basic QAOA principles, then addressing limitations, and increasingly focusing on hybrid approaches, problem decomposition, and hardware-aware algorithms.

Iterative Algorithm Solves Complex Scheduling Problems

This research presents a novel quantum algorithm,Iterative-QAOA, designed to address combinatorial optimisation problems, specifically the Just-in-Time Job Shop Scheduling Problem. The team successfully demonstrated the algorithm’s ability to converge to optimal and high-quality near-optimal solutions on problem instances executed on current quantum hardware, representing some of the largest such problems solved to date, outperforming both Variational Quantum Imaginary Time Evolution and a non-variational Linear Ramp approach. Further investigation using simulations with up to 97 qubits suggests potential for scaling to tackle industrial-scale problems on future fault-tolerant quantum computers. The researchers observed that the computational resources required, including circuit depth and gate counts, scale favourably, indicating a path towards solving problems that become classically impractical as they grow in size.

However, the authors acknowledge limitations inherent in the tensor network approximations used in their simulations, and note that a single measurement shot occasionally yielded unexpectedly low cost solutions, likely due to statistical fluctuations and noise. Future work will focus on improving gate fidelities, developing techniques to reduce gate counts, and refining error mitigation methods to enhance the algorithm’s performance and scalability. The team intends to explore the quantum scaling behaviour further, as this is crucial for determining the feasibility of solving increasingly complex problems with quantum computers.