When scheduling quantum operations, a shorter overall execution time of the resulting schedule yields a better throughput and higher fidelity output. In this paper, we demonstrate that quantum operation scheduling can be interpreted as a special type of job-shop problem. On this basis, we provide its formulation as Constraint Programming while taking into account commutation between quantum operations. We show that this formulation improves the overall execution time of the resulting schedules in practice through experiments with a real quantum compiler and quantum circuits from two common benchmark sets.
When scheduling quantum operations, a shorter overall execution time of the resulting schedule yields a better throughput and higher fidelity output. In this paper, we demonstrate that quantum operation scheduling can be interpreted as a special type of job-shop problem. On this basis, we provide its formulation as Constraint Programming while taking into account commutation between quantum operations. We show that this formulation improves the overall execution time of the resulting schedules in practice through experiments with a real quantum compiler and quantum circuits from two common benchmark sets.
Abstract Combinatorial optimization problems are considered to be an application, where quantum computing can have transformative impact. In the industrial context, job shop scheduling problems that aim at finding the optimal schedule for a set of jobs to be run on a set of machines are of immense interest. Here we introduce an efficient encoding of job shop scheduling problems, which requires much fewer bit-strings for counting all possible schedules than previously employed encodings. For problems consisting of N jobs with N operations, the number of required bit-strings is at least reduced by a factor N / log 2 ( N ) as compared to time indexed encodings. This is particularly beneficial for solving job shop scheduling problems on quantum computers, since much fewer qubits are needed to represent the problem. Our approach applies to the large class of flexible and usual job-shop scheduling problems, where operations can possibly be executed on multiple machines. Using variational quantum algorithms, we show that the encoding we introduce leads to significantly better performance of quantum algorithms than previously considered strategies. Importantly, the encoding we develop also enables significantly more compact classical representations and will therefore be highly useful even beyond applicability on quantum hardware.
Even as quantum computers continue to increase in number of qubits, high error rates limit the size of quantum circuits that can be executed. This results in low throughput and poor resource utilization on quantum computers. To address this, recent research has focused on extending circuit optimization and compilation techniques to support simultaneous execution of quantum circuits (i.e. quantum parallelism). While much work has been spent developing parallel mapping and gate scheduling techniques, there are few approaches to the problem of parallel job scheduling on quantum computers. There are several constraints that make quantum job scheduling different from classical scheduling. We propose a scheduling algorithm, QGroup, for parallelizing circuits of different lengths and shot counts while mitigating parallel slowdowns due to measurement synchronization. QGroup achieves a better parallelism-runtime tradeoff, with significant speedup and fidelity increase over existing methods. QGroup achieves improvement in both fidelity and runtime for noise-sensitive, diverse workloads.
Rapid progress in quantum technology in this decade has dramatically increased the coherence time of qubits (quantum bits) and the fidelity of operations on qubits.Although currently available quantum computers are noisy and intermediate in scale, it is believed that they will be used in some specific applications such as quantum chemistry, machine learning, optimization, and sampling in the near future.Along with progress in quantum computing hardware, development of the software stack has also become more active.A quantum compiler, which translates a quantum program into a sequence of control instructions, is one of the most essential software components to provide a human-friendly programming interface for quantum algorithms.In quantum compilers, optimizing the output instructions is very important: For noisy quantum computers, it increases the probability of completing all the operations before any qubit decoheres, yielding computational results with higher fidelity.Even for fault-tolerant quantum computers, optimization increases the throughput.In this thesis, we address two important optimization tasks in quantum compilers: quantum circuit mapping and quantum circuit scheduling.We provide their formulations as classical optimization problems considering commutation between quantum gates, which are not fully considered in previous studies.We also provide exact and heuristic algorithms for solving them.We examine how considering gate commutation in our algorithms improves the quality of solutions by computational experiments in practical settings.The thesis is organized as follows.After reviewing studies on quantum compilers, we consider the problem of mapping quantum circuits to quantum computers, whose operations are limited by their coupling architecture, with as few additional gates as possible.We propose exact and heuristic algorithms for quantum circuit mapping, which use gate commutation rules and a gate transformation rule of Bridge gate.We compare these algorithms with the state-of-the-art algorithms by computational experiments with circuits of a commonly used benchmark dataset.Next, we consider the problem of scheduling operations in a given circuit with the shortest total execution time.We demonstrate that quantum circuit scheduling can be seen as an optimization problem only when we consider gate commutation and can be interpreted as a special type of job-shop problem.We provide Constraint Programming and Mixed Integer Programming formulations and show how solving circuit scheduling independently improved the schedule length through experiments with real circuits and a compiler.We believe that our algorithms are useful in practical quantum compilers and the developed techniques provide new insight into optimization in quantum compilers.We hope that they will be helpful to advance software stack development and improve the utility of quantum computers.
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.
Undoubtedly, quantum computing offers valuable acceleration for solving intricate problems. One of the primary hurdles lies in executing large-scale quantum applications on backend machines. Qubit noise, among other factors, dramatically influences the execution process. Implementing effective scheduling techniques for quantum circuits is crucial for practical quantum computing and preventing excessive waiting times. The quantum realm is distinct from classical computing in terms of optimization, performance, utilization, and waiting periods. Consequently, the parameters and components of quantum circuit scheduling diverge from those of classical computing. This paper presents Quantum Noise Mitigation: Introducing the Robust Quantum Circuit Scheduler for Enhanced Fidelity and Throughput, a straightforward yet effective scheduling framework and policy that enhances noise resilience, throughput, and the fidelity of quantum circuits. Drawing inspiration from classical methods, our scheduling approach incorporates additional constraints tailored for quantum logic. The outcome demonstrates a substantial improvement in fidelity and resource management, which is vital for real-world quantum applications.
Efficient production planning is essential in modern manufacturing to improve performance indicators such as lead time and to reduce reliance on human intuition. While mathematical optimization approaches, formulated as job shop scheduling problems, have been applied to automate this process, solving large-scale production planning problems remains computationally demanding. Moreover, many practical scenarios involve conflicting objectives, making traditional scalarization techniques ineffective in finding diverse and useful Pareto-optimal solutions. To address these challenges, we developed a quantum-classical hybrid algorithm that decomposes the problem into two subproblems: resource allocation and task scheduling. Resource allocation is formulated as a quadratic unconstrained binary optimization problem and solved using annealing-based methods that efficiently explore complex solutions. Task scheduling is modeled as a mixed-integer linear programming problem and solved using conventional solvers to satisfy detailed scheduling constraints. We validated the proposed method using benchmark instances based on foundry production scenarios. Experimental results demonstrate that our hybrid approach achieves superior solution quality and computational efficiency compared to traditional monolithic methods. This work offers a promising direction for high-speed, multi-objective scheduling in industrial applications.