A case study of variational quantum algorithms for a job shop scheduling problem
arXiv:2109.03745 · doi:10.1140/epjqt/s40507-022-00123-4
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.
arXiv comment16 pages, 8 figures, 3 tables. Additional hardware experiments, minor clarifications. As published in EPJ Quantum Technol
References in corpus (33)
- Quantum Computing in the NISQ era and beyond
- A variational eigenvalue solver on a quantum processor
- Variational Quantum Algorithms
- Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
- Ising formulations of many NP problems
- Barren plateaus in quantum neural network training landscapes
- A Quantum Approximate Optimization Algorithm
- Quantum Circuit Learning
- Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits
- Evaluating analytic gradients on quantum hardware
- Expressibility and entangling capability of parameterized quantum circuits for hybrid quantum-classical algorithms
- Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
- Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution
- Variational ansatz-based quantum simulation of imaginary time evolution
- Hybrid quantum-classical algorithms and quantum error mitigation
- Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
- Quantum Natural Gradient
- Theory of variational quantum simulation
- tket : A Retargetable Compiler for NISQ Devices
- Quantum Approximate Optimization of the Long-Range Ising Model with a Trapped-Ion Quantum Simulator
- Improving Variational Quantum Optimization using CVaR
- Unsupervised Machine Learning on a Hybrid Quantum Computer
- Quantum Supremacy through the Quantum Approximate Optimization Algorithm
- Topological and subsystem codes on low-degree graphs with flag qubits
- Hardware-efficient variational quantum algorithms for time evolution
- Performance of hybrid quantum/classical variational heuristics for combinatorial optimization
- Filtering variational quantum algorithms for combinatorial optimization
- Classical Optimizers for Noisy Intermediate-Scale Quantum Devices
- Practical optimization for hybrid quantum-classical algorithms
- A Comparison of Various Classical Optimizers for a Variational Quantum Linear Solver
- Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization
- Using models to improve optimizers for variational quantum algorithms
- To quantum or not to quantum: towards algorithm selection in near-term quantum optimization
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