A team of researchers from Friedrich-Alexander-Universität Erlangen-Nürnberg and Siemens Technology have developed an efficient encoding for job shop scheduling problems, which are of significant interest in industrial contexts. The new encoding requires fewer bitstrings, reducing the number of qubits needed to represent the problem on quantum computers. This development is particularly beneficial for combinatorial optimization problems like job shop scheduling, which involves finding the optimal schedule for a set of jobs on a set of machines. The team’s approach significantly improves the performance of near-term quantum algorithms and can be used in both quantum and classical algorithms.
Quantum Computing and Job Shop Scheduling Problems
Mathias Schmid and Michael J Hartmann from the Physics Department at Friedrich-Alexander-Universität Erlangen-Nürnberg, Germany, along with Sarah Braun and Rudolf Sollacher from Siemens Technology, Munich, Germany, have developed an efficient encoding for job shop scheduling problems. These problems, which involve finding the optimal schedule for a set of jobs to be run on a set of machines, are of immense interest in the industrial context. The team’s encoding requires fewer bitstrings for counting all possible schedules than previously used encodings. This is particularly beneficial for solving job shop scheduling problems on quantum computers, as fewer qubits are needed to represent the problem.
Quantum Computing and Combinatorial Optimization Problems
Combinatorial optimization problems are considered a promising use case for quantum computing. Quantum computers can examine many configurations of the considered variables in parallel, potentially providing a significant advantage. Job shop scheduling is a combinatorial optimization problem of paramount relevance in industry, computation, and economics. It involves scheduling a set of jobs with varying processing times on machines with varying processing capabilities. The goal is to minimize the makespan, the time it takes to complete the last finishing job.
Quantum Approaches to Job Shop Scheduling
There are already quantum approaches to job shop scheduling, which mainly consider casting the problem into a quadratic unconstrained binary optimization (QUBO) formulation. However, these approaches often require a large number of variables, which is not practical in quantum computing. The team’s new approach allows for a more efficient encoding of the problem, reducing the number of required variables and thus significantly lowering the requirements for solving job shop scheduling problems on quantum computers.
The New Encoding and Variational Quantum Algorithms
The new encoding developed by the team can be used in variational quantum algorithms. These algorithms require the classical routine used to optimize a parameterized quantum gate sequence to be compatible with the chosen cost function. The team used the recently proposed filtering variational quantum eigensolver (FVQE) as it does not require formulating the cost function of the problem as a Hamiltonian. This approach, in combination with the efficient encoding strategy, allows for testing the quantum algorithm in numerical simulations for much larger instances than previously considered.
The Efficiency of the New Encoding
The new encoding developed by the team leads to significantly improved performance of near-term quantum algorithms. It can be employed in both quantum and classical algorithms, so its benefits are largely independent of the progress in quantum hardware development. The team conducted numerical experiments showing the efficiency of the resulting quantum algorithms. The objective of the problem is to find a schedule of operations and a choice for the machines such that the finishing time of the last job is minimal. This time is called the makespan.
The article “Highly Efficient Encoding for Job-Shop Scheduling Problems and its Application on Quantum Computers“ was published on January 29, 2024. The authors of this article are Mathias Schmid, Sarah Braun, Rudolf Sollacher, and Michael J. Hartmann. The article was sourced from arXiv, a repository maintained by Cornell University. The article discusses the efficient encoding for job-shop scheduling problems and its application in quantum computing.
