We study a job-shop scheduling problem for an automatized robot in a high-throughput laboratory and a traveling-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 noisy intermediate-scale quantum hardware and can solve logistics scheduling problems, where other digital quantum algorithms show insufficient performance.
We study a job-shop scheduling problem for an automatized robot in a high-throughput laboratory and a traveling-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 noisy intermediate-scale quantum hardware and can solve logistics scheduling problems, where other digital quantum algorithms show insufficient performance.
We introduce a method for solving combinatorial optimization problems on digital quantum computers, where we incorporate auxiliary counterdiabatic (CD) terms into the adiabatic Hamiltonian, while integrating bias terms derived from an iterative digitized counterdiabatic quantum algorithm. We call this protocol bias-field digitized counterdiabatic quantum optimization (BF-DCQO). Designed to effectively tackle large-scale combinatorial optimization problems, BF-DCQO demonstrates resilience against the limitations posed by the restricted coherence times of current quantum processors and shows clear enhancement even in the presence of noise. Additionally, our purely quantum approach eliminates the dependency on classical optimization required in hybrid classical-quantum schemes, thereby circumventing the trainability issues often associated with variational quantum algorithms. Through the analysis of an all-to-all connected general Ising spin-glass problem, we exhibit a polynomial scaling enhancement in ground-state success probability compared to traditional DCQO and finite-time adiabatic quantum optimization methods. Furthermore, it achieves scaling improvements in ground-state success probabilities, increasing by up to two orders of magnitude, and offers an average 1.3 × better approximation ratio than the quantum approximate optimization algorithm for the problem sizes studied. We validate these findings through experimental implementations on both trapped-ion quantum computers and superconducting processors, tackling a maximum weighted independent set problem with 36 qubits and a spin glass on a heavy-hexagonal lattice with 100 qubits, respectively. These results mark a significant advancement in gate-based quantum computing, employing a fully quantum algorithmic approach.
Large-scale combinatorial scheduling problems -- job-shop scheduling, flow-shop scheduling, and vehicle routing among them -- remain NP-hard at practically relevant scale, and quantum computing has entered this space along two related tracks: genuinely quantum solvers, principally quantum annealers and gate-based devices running the quantum approximate optimization algorithm (QAOA), and quantum-inspired classical solvers, such as coherent Ising machines and digital annealers, that borrow the same Ising/QUBO problem structure without requiring quantum hardware. This article synthesizes both tracks as applied specifically to scheduling. We trace the theoretical foundations from quantum and simulated annealing through the QUBO formulation techniques that make scheduling problems solver-ready, then review direct applications to job-shop, flow-shop, and vehicle-routing problems, reporting the concrete, verified numbers the underlying studies provide. The consistent finding is that quantum hardware remains constrained by qubit connectivity, embedding overhead, and shallow achievable circuit depth to small benchmark instances, while quantum-inspired classical solvers, unconstrained by qubit count, already reach scheduling-relevant problem sizes with reported performance competitive with or exceeding classical heuristics. We close by identifying benchmarking rigor, hardware connectivity, and the near-total absence of work on dynamic, online scheduling as the field's clearest open problems.
We propose a faster digital quantum algorithm for portfolio optimization using the digitized counterdiabatic quantum optimization paradigm in the impulse regime, that is, where the counterdiabatic terms are dominant. Our approach notably reduces the circuit depth requirement of the algorithm and enhances the solution accuracy, making it suitable for current quantum processors. We apply this protocol to a real-case scenario of portfolio optimization with 20 assets, using purely quantum and hybrid classical-quantum paradigms. We demonstrate the advantages of our protocol using up to 20 qubits on an IonQ trapped-ion quantum computer. By benchmarking our method against the standard quantum approximate optimization algorithm and finite-time digitized adiabatic algorithms, we obtain a significant reduction in the circuit depth by factors of 2.5 to 40, while minimizing the dependence on the classical optimization subroutine. Besides portfolio optimization, the proposed method is applicable to a large class of combinatorial optimization problems.
The Job Shop Scheduling Problem (JSSP) has always been considered as one of the most complex and industry essential scheduling problems. Optimizing the makespan of a given schedule generally involves using dedicated algorithms, local search strategies, or metaheuristics. These approaches, however, heavily rely on classical computational power, which is bounded by the physical limits of microcontrollers and power issues. Inspired by the promising results achieved for Quantum Annealing (QA) based approaches to solve JSSP instances, we propose a new approach that uses gate-model quantum architecture as an alternative to QA. We find that we can make use of the time-indexed JSSP instance representation to build a cost Hamiltonian, which can be embedded into Quantum Approximate Optimization Algorithm (QAOA) to find an optimal solution to a basic JSSP instance. We demonstrate the use of QAOA to solve the JSSP, and we evaluate its efficiency and accuracy for this problem from experimental results, as there is an increased urgency to demonstrate the applicability of quantum optimization algorithms. We also find that optimal variational parameters form patterns that can facilitate computation in bigger quantum circuits. Additionally, we compare the obtained noiseless simulation results of gate-model quantum circuits demonstrating the relationship between two evaluation criteria - makespan and energy. Finally, we analyze and present the overall performance of our approach with the increasing deadline and simulated depth of QAOA circuits.
Branch-and-bound algorithms effectively solve combinatorial optimization problems, relying on the relaxation of the objective function to obtain tight lower bounds. While this is straightforward for convex objective functions, higher-order formulations pose challenges due to their inherent non-convexity. In this work, we propose branch-and-bound digitized counterdiabatic quantum optimization (BB-DCQO), a quantum algorithm that addresses the relaxation difficulties in higher-order unconstrained binary optimization (HUBO) problems. By employing bias fields as approximate solutions to the relaxed problem, we iteratively enhance the quality of the results compared to the bare bias-field digitized counterdiabatic quantum optimization (BF-DCQO) algorithm. We refer to this enhanced method as BBB-DCQO. In order to benchmark it against simulated annealing (SA), we apply it on sparse HUBO instances with up to 156 qubits using tensor network simulations. To explore regimes that are less tractable for classical simulations, we experimentally apply BBB-DCQO to denser problems using up to 100 qubits on IBM quantum hardware. We compare our results with SA and a greedy-tuned quantum annealing baseline. In both simulations and experiments, BBB-DCQO consistently achieved higher-quality solutions with significantly reduced computational overhead, showcasing the effectiveness of integrating counterdiabatic quantum methods into branch-and-bound to address hard non-convex optimization tasks.
A promising use of quantum computers lies in the logistics and scheduling of industrial problems, such as space mission planning, maritime management, and many others. This field is expected to provide useful applications for quantum computing at the current stage of hardware development. Quantum annealing techniques have been proposed to solve scheduling problems, along with many other optimization problems. In this work, we test quantum annealing and hybrid techniques based on the D-Wave hardware to solve scheduling problems in the framework of job shop scheduling (JSP), which consists of optimally assigning operations to certain resources, while satisfying specific constraints and minimizing the total scheduling time, known as timespan. We devised an iterative algorithm that produces valid schedules for decreasing timespan values. We implemented a refined iterative variable pruning technique, which significantly reduces the number of spin variables in the corresponding Ising model, whose low-energy configurations are sampled by using the D-Wave Hybrid Solver Service. Our novel iterative algorithm leverages a directed acyclic graph (DAG) representation of partial or complete solutions of the JSP instance, which enables an efficient update of the feasible processing time windows for each operation. This approach leads to significantly improved results compared to the standard state-of-the-art applications of quantum annealing for the JSP. Remarkably, we can often prove the absolute optimality of the obtained solution, namely that a more efficient schedule within a shorter timespan can not exist.