Symmetry-based quantum algorithms for open-shop scheduling with hard constraints

Abstract

Encoding hard-constrained optimization problems into a variational quantum algorithm often turns out to be a challenging task. In this work, we provide a solution for the class of open-shop scheduling problems (OSSPs), which we achieve by rigorously employing the symmetries of the classical problem. An established approach for encoding the hard constraints of the closely related traveling salesperson problem (TSP) into mixer Hamiltonians was recently given by Hadfield et al.'s Quantum Alternating Operator Ansatz (QAOA). For the OSSP, which contains TSP as a special case, we show that desired properties of similarly constructed mixers can be directly linked to a purely classical object: the group of feasibility-preserving bit value permutations. We also outline a generic way to construct QAOA-like mixers for these problems. We further propose a new variational quantum algorithm that incorporates the underlying group structure more naturally and, as a proof of principle, implement our new algorithm for a small OSSP instance on an IBM Q System One. Unlike the generic QAOA, our algorithm allows for bounding the amount and the domain of parameters necessary to reach every feasible solution from above: Optimizing at most quadratically many parameters should suffice to reach the optimum with certainty.

16 pages, 6 figures

References in corpus (34)

• Quantum Computing in the NISQ era and beyond
• A variational eigenvalue solver on a quantum processor
• Variational Quantum Algorithms
• Ising formulations of many NP problems
• A Quantum Approximate Optimization Algorithm
• Noisy intermediate-scale quantum (NISQ) algorithms
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• Training variational quantum algorithms is NP-hard
• Warm-starting quantum optimization
• Improving Variational Quantum Optimization using CVaR
• Barren Plateaus in Variational Quantum Computing
• Solving Vehicle Routing Problem Using Quantum Approximate Optimization Algorithm
• Entanglement Devised Barren Plateau Mitigation
• Avoiding barren plateaus using classical shadows
• Benchmarking the Quantum Approximate Optimization Algorithm
• Error mitigation for variational quantum algorithms through mid-circuit measurements
• Characterizing local noise in QAOA circuits
• Evaluation of QAOA based on the approximation ratio of individual samples
• QAOA Performance in Noisy Devices: The Effect of Classical Optimizers and Ansatz Depth
• Quantum Computing Techniques for Multi-Knapsack Problems
• Error Mitigation for Deep Quantum Optimization Circuits by Leveraging Problem Symmetries
• Quantum-Assisted Solution Paths for the Capacitated Vehicle Routing Problem
• Threshold-Based Quantum Optimization
• Wasserstein Solution Quality and the Quantum Approximate Optimization Algorithm: A Portfolio Optimization Case Study
• Knapsack Problem variants of QAOA for battery revenue optimisation
• Iterative Layerwise Training for Quantum Approximate Optimization Algorithm
• Characterizing Error Mitigation by Symmetry Verification in QAOA
• Elementary Proof of QAOA Convergence
• Digitized Counterdiabatic Quantum Algorithms for Logistics Scheduling
• Two-Step Quantum Search Algorithm for Solving Traveling Salesman Problems
• Inductive Construction of Variational Quantum Circuit for Constrained Combinatorial Optimization
• Theory and Implementation of the Quantum Approximate Optimization Algorithm: A Comprehensible Introduction and Case Study Using Qiskit and IBM Quantum Computers
• One for All: Universal Quantum Conic Programming Framework for Hard-Constrained Combinatorial Optimization Problems