Digitized Counterdiabatic Quantum Algorithms for Logistics Scheduling

Abstract

We study a job shop scheduling problem for an automatized robot in a high-throughput laboratory and a travelling salesperson problem with recently proposed digitized counterdiabatic quantum optimization (DCQO)algorithms. In DCQO, we find the solution of an optimization problem via an adiabatic quantum dynamics, which is accelerated with counterdiabatic protocols. Thereafter, we digitize the global unitary to encode it in a digital quantum computer. For the job-shop scheduling problem, we aim at finding the optimal schedule for a robot executing a number of tasks under specific constraints, such that the total execution time of the process is minimized. For the traveling salesperson problem, the goal is to find the path that covers all cities and is associated with the shortest traveling distance. We consider both hybrid and pure versions of DCQO algorithms and benchmark the performance against digitized quantum annealing and the quantum approximate optimization algorithm (QAOA). In comparison to QAOA, the DCQO solution is improved by several orders of magnitude in success probability using the same number of two-qubit gates. Moreover, we implement our algorithms on cloud-based superconducting and trapped-ion quantum processors. Our results demonstrate that circuit compression using counterdiabatic protocols is amenable to current NISQ hardware and can solve logistics scheduling problems, where other digital quantum algorithms show insufficient performance.

13 pages, 10 figures

References in corpus (11)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum computational advantage using photons
• Quantum computing for finance
• Digitized-Counterdiabatic Quantum Algorithm for Protein Folding
• Towards adiabatic quantum computing using compressed quantum circuits
• Ordering of Trotterization: Impact on Errors in Quantum Simulation of Electronic Structure
• Shortcuts to Adiabaticity in Krylov Space
• Comparative study of variations in quantum approximate optimization algorithms for the Traveling Salesman Problem
• An Optimization Case Study for solving a Transport Robot Scheduling Problem on Quantum-Hybrid and Quantum-Inspired Hardware
• Efficient DCQO Algorithm within the Impulse Regime for Portfolio Optimization
• Digital-Analog Counterdiabatic Quantum Optimization with Trapped Ions

Cited by in corpus (7)

• Bias-Field Digitized Counterdiabatic Quantum Algorithm for Higher-Order Binary Optimization
• When Federated Learning Meets Quantum Computing: Survey and Research Opportunities
• Counterdiabatic ADAPT-VQE for molecular simulation
• Digitized Counter-Diabatic Quantum Optimization for Bin Packing Problem
• QTIS: A QAOA-Based Quantum Time Interval Scheduler
• Symmetry-based quantum algorithms for open-shop scheduling with hard constraints
• Direct entanglement ansatz learning (DEAL) with ZNE on error-prone superconducting qubits