Variational quantum algorithms for combinatorial optimisation : navigating the NISQ era

Abstract

Optimisation algorithms aim to solve a wide range of problems, including those related to physical systems and everyday challenges. Examples include optimising the shape or material distribution of structures to maximise strength and minimise weight, designing optimal investment portfolios, balancing risks and returns, planning efficient routes, optimising container placement on ships, and improving the manufacturing plan in factories. Optimising manufacturing plans in factories is the primary focus of my research. The goal of each optimisation problem typically involves reducing the costs by adjusting the algorithm’s configuration. For instance, in route optimisation, costs typically involve time and fuel, but constraints such as time windows or availability at destinations must also be considered. Incorporating more parameters can lead to solutions that better reflect real-world scenarios. However, increasing the number of parameters adds complexity to the problem, and more resources are required to achieve an optimal solution. In many practical applications, finding the exact optimal solution is often unnecessary. In many cases, finding a solution optimising the current status within an acceptable time frame is sufficient. The challenge of optimising the manufacturing plan in factories, often referred to as the Job-Shop Scheduling Problem (JSSP), involves balancing several parameters. These include sale orders and their requested delivery dates, the expected arrival dates for raw materials derived from the bill of materials of the products listed in sale orders, and resource availability, both machines and human resources required in the production process. Additionally, the process is subject to several constraints, such as sequential dependencies—for example, producing one component before another—and process coordination, such as synchronising different production stages, where manufacturing must be completed before packaging can begin. Operators balance these parameters and constraints to minimise costs, such as reducing changes in the configuration of machines or reducing clean-up tasks between the manufacturing of different components and maximising resource utilisation while keeping up with promised delivery dates to customers. The JSSP is a combinatorial optimisation problem that is NP-hard, meaning it becomes computationally difficult to compute as the number of parameters increases using classical computing methods. However, there are still various classical approaches to the problem, which result primarily in heuristic solutions. These include Integer Linear Programming (ILP), Dispatching Rules, Genetic Algorithms, or Simulated Annealing. In this dissertation, I investigate the quantum computing algorithm Quantum Approximate Optimization Algorithm (QAOA) to address the JSSP problem. Quantum computing is still in its infancy. Its foundation lies in quantum mechanics, which involves mathematical concepts such as linear algebra, complex numbers, and probability amplitudes. Key properties of quantum mechanics like superposition, entanglement and quantum interference allow quantum computers to explore the solution space of a problem more effectively than classical computers. In this dissertation, I first examine the properties of quantum mechanics, which can help me investigate QAOA and study tools that I can use to program a quantum computer. Then, I explore the mathematical models used to represent the problem, in this case, the Job-Shop Scheduling Problem (JSSP). JSSP involves several interdependent parameters. I expressed these parameters in mathematical models containing these interactions, some containing three or more parameters interacting with each other. The result was mathematical formulations involving problems with multivariate objective functions, which were then solved with QAOA. Another objective of my dissertation was to explore the possibility of reducing resource requirements while still achieving sufficiently good results based on relevant figures of merit. In this dissertation, I investigate various configurations of QAOA, evaluating their success while factoring in the computational resources required for execution to achieve an optimal result. I propose a configuration of QAOA, which I call k-interaction Angle QAOA (ka-QAOA). I show that ka-QAOA performs comparably to other proposed QAOA configurations while reducing the computational resources required to achieve similarly good approximations. While the results are promising, as parameters in problems increase, testing the different configurations of QAOA becomes a daunting task. More robust, error-free quantum computers are needed to model and solve real-world optimisation problems like JSSP. In the interim, we can still experiment with problems having few parameters to find optimal quantum algorithms.