Grant: Alliance Grants

To produce food, clothing, products, and all the necessities of modern life, raw materials have to be extracted or produced, then they need to flow uninterrupted from the source to factories, distribution centers, to stores and markets, and finally to homes and consumers. The problem of finding the shortest or most cost-effective delivery routes is called the vehicle routing problem (VRP). The goal of the partnership between researchers at the Université de Sherbrooke and PASQAL Canada Inc. is to develop a quantum algorithm for solving the VRP using a neutral atom quantum processing unit (QPU) as manufactured by the industrial partner PASQAL. The VRP is a complex optimization problem which aims at finding the best set of routes for a fleet of vehicles (or autonomous vehicles) that is more cost effective (in terms of time, fuel, or risks). Finding the best solution is computationally very challenging as the number of possible routes grows very rapidly with the number of vehicles and locations. Modern numerical approaches to this problem often rely on a combination of approximate methods to find the best routes possible, leading to an increase the efficiency of logistics. The research team will develop and validate a quantum algorithm and associated software that can generate quick and cost-effective solutions of real-world industrial instances of the VRP using a neutral atom QPU. This type of quantum computer uses the interactions between trapped Rubidium atoms to encode complex optimization problems, while laser pulses drive transitions between quantum states of the system. Such analog quantum algorithms harness the principles of superposition, entanglement, and interference of quantum physics to explore faster a large space of potential solutions, so that the final measurement of the atom's quantum state represents a feasible solution to the considered problem. This analog mode of operation of PASQAL's QPU is ideally suited to solve complex optimization problems, such as the VRP, where it can lead to higher quality delivery routes. The objective of this project is thus to demonstrate a quantum advantage on the industrially relevant VRP with a method that utilizes PASQAL's quantum computer.