Insider letter:
- A collaboration between Volkswagen Data:Lab and the University of Innsbruck shows how QUBO can effectively model and solve the ride pooling problem.
- Quantum computing has already been used to solve QUBO formulations and has the potential to effectively provide high-quality approximations for complex, highly interconnected problems.
- While QUBO-based solutions are promising, the paper points out that quadratic scaling of variables remains a challenge for current quantum devices.
A recent study in Nature conducted by the Volkswagen Data: Lab and the Institute for Theoretical Physics at the University of Innsbruck investigated QUBO as a framework to model the ride pooling problem (RPP). The RPP captures the optimization challenge that arises when bundling multiple customer requests for on-demand pickups and drops using only a limited fleet of shared vehicles.
Modelling the problem with QUBO:
At a time when convenient doorstep delivery and shared transportation are becoming increasingly popular, the ridepooling problem is a common scenario where multiple customers can make on-demand requests from a limited number of shared vehicles. The number of variables to optimize makes this problem computationally intensive – the requests must be optimized for maximum efficiency, minimum travel time, and within the constraints of the fleet.
To effectively explore solutions to this problem, researchers from Volkswagen Data:Lab and the University of Innsbruck defined the RPP in the context of QUBO, as QUBO models have been extensively studied in NP-hard real-world optimization problems. The versatility of QUBO comes from its ability to represent complex problems with binary variables where the goal is to minimize or maximize a quadratic objective function.
Among the methods presented in the literature to solve QUBO problems, quantum computing has shown great potential. For example, a paper by Silva et al. implements QUBO to minimize losses in power distribution networks using quantum annealing. Another study by Tang et al. on driverless transport vehicle planning showed that using a coherent Ising machine to solve QUBO formulations can reduce computation times by up to 92% compared to classical methods.
According to the paper, quantum computing is a valuable tool for solving optimization problems. The quantum mechanical nature of quantum computing allows relationships between strongly connected variables to be effectively investigated. Even though quantum algorithms do not always succeed in finding the absolutely optimal solution, they still have the potential to provide high-quality approximations much faster than classical algorithms. This becomes particularly relevant when classical methods reach their limits due to the complexity or size of a problem.
When investigating QUBO formulations for the RPP, researchers from Volkswagen Data:Lab experimented with different methods, each chosen to find the most efficient and scalable solution. The paper emphasizes the importance of finding the most minimal QUBO representations to reduce the number of variables and constraints. This becomes particularly relevant when considering quantum computer implementations, as increased variables in a QUBO formulation directly contribute to deeper quantum circuits. As mentioned in the paper, deeper circuits are not ideal on current quantum processors due to limited qubit connectivity and coherence times.
The team points out that while the overall results of this study are directly applicable to modern routing challenges, such as those encountered in ride-sharing services, their importance does not end there. Investigating QUBO in the context of the RPP is relevant not only for routing and logistics problems, but also for better understanding what role quantum computing will play in complex, real-world optimization challenges.
Future prospects for quantum optimization:
Although the QUBO formulations presented in the study are promising, the paper acknowledges that quadratic scaling of variables would not be ideal for implementation on current quantum devices. This limitation points to the need for further research and development to make these methods feasible on today’s quantum hardware.
As quantum technology becomes more widespread, the practical application of QUBO-based solutions such as those proposed for RPP will also expand, providing optimization methods that have the potential to outperform classical approaches.
Those involved in the study included Michele Cattelan from the Volkswagen Data:Lab and the University of Innsbruck as well as Sheir Yarkoni from the Volkswagen Data:Lab.
