A case study of variational quantum algorithms for a job shop scheduling problem

Abstract

Combinatorial optimization models a vast range of industrial processes aiming at improving their efficiency. In general, solving this type of problem exactly is computationally intractable. Therefore, practitioners rely on heuristic solution approaches. Variational quantum algorithms are optimization heuristics that can be demonstrated with available quantum hardware. In this case study, we apply four variational quantum heuristics running on IBM's superconducting quantum processors to the job shop scheduling problem. Our problem optimizes a steel manufacturing process. A comparison on 5 qubits shows that the recent filtering variational quantum eigensolver (F-VQE) converges faster and samples the global optimum more frequently than the quantum approximate optimization algorithm (QAOA), the standard variational quantum eigensolver (VQE), and variational quantum imaginary time evolution (VarQITE). Furthermore, F-VQE readily solves problem sizes of up to 23 qubits on hardware without error mitigation post processing.

16 pages, 8 figures, 3 tables. Additional hardware experiments, minor clarifications. As published in EPJ Quantum Technol

References in corpus (7)

• A Quantum Approximate Optimization Algorithm
• Hybrid quantum-classical algorithms and quantum error mitigation
• t$|$ket$⟩$ : A Retargetable Compiler for NISQ Devices
• Unsupervised Machine Learning on a Hybrid Quantum Computer
• Filtering variational quantum algorithms for combinatorial optimization
• Practical optimization for hybrid quantum-classical algorithms
• A Comparison of Various Classical Optimizers for a Variational Quantum Linear Solver

Cited by in corpus (25)

• Barren plateaus in quantum tensor network optimization
• Graph neural network initialisation of quantum approximate optimisation
• Hybrid quantum ResNet for car classification and its hyperparameter optimization
• Doubly optimal parallel wire cutting without ancilla qubits
• Variational quantum algorithm for unconstrained black box binary optimization: Application to feature selection
• Encoding-Independent Optimization Problem Formulation for Quantum Computing
• Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems
• Multiobjective variational quantum optimization for constrained problems: an application to Cash Management
• Towards Finding an Optimal Flight Gate Assignment on a Digital Quantum Computer
• QOPTLib: a Quantum Computing Oriented Benchmark for Combinatorial Optimization Problems
• Sequential optimal selection of a single-qubit gate and its relation to barren plateau in parameterized quantum circuits
• Exploring the neighborhood of 1-layer QAOA with Instantaneous Quantum Polynomial circuits
• Optimal Parameter Configurations for Sequential Optimization of Variational Quantum Eigensolver
• Approaching Collateral Optimization for NISQ and Quantum-Inspired Computing
• An approach to solve the coarse-grained Protein folding problem in a Quantum Computer
• Inductive Construction of Variational Quantum Circuit for Constrained Combinatorial Optimization
• Quantum-enhanced mean value estimation via adaptive measurement
• Benchmarking Variational Quantum Algorithms for Combinatorial Optimization in Practice
• Global optimization in variational quantum algorithms via dynamic tunneling method
• Warm Start of Variational Quantum Algorithms for Quadratic Unconstrained Binary Optimization Problems
• Performance analysis of a filtering variational quantum algorithm
• Digitized Counter-Diabatic Quantum Optimization for Bin Packing Problem
• QTIS: A QAOA-Based Quantum Time Interval Scheduler
• Large Scale Diverse Combinatorial Optimization: ESPN Fantasy Football Player Trades
• Exploiting biased noise in variational quantum models