The paper presents a quantum method to optimize the placement of sensors on the surface of a vehicle. The problem, as posted in the BMW Quantum Computing Challenge 2021, is to arrive at the optimal positions and configurations (type and orientation) of the sensors on the vehicle surface that maximizes coverage of the Region of Interest (RoI), while minimizing the total cost of the selected sensors. The dataset contains approximately 100,000 points in the RoI, with defined measures of criticality (ranging between 0 to 1), distributed over a volume of approximately 40,000 cubic metres around the vehicle. The types of sensors, their coverage parameters and costs are inputs to the problem.The optimization problem is decomposed and solved individually for each side of the vehicle, and the results for the entire vehicle are collated and presented in the paper. The approach considers a quadratic approximation to the maximum set-coverage formulation with the advantage of obtaining the optimal number of sensors as an output from the model itself. The resultant quadratic program is solved using quantum methods, as well as a standard, state-of-the-art Integer Quadratic Program (IQP) solver, respectively. The quadratic approximation consumes qubits that are linear in the number of total configurations and significantly reduces the number of decision variables required in an Ising formulation of the problem.The quantum and classical methods are found to perform on par with each other. A detailed comparison of the results is presented in the paper. Given the combinatorial nature of the optimization problem, the classical approach may become intractable while solving the problem in an integrated manner (instead of solving individually for each side). Under such scenarios, there is a possibility to expect benefits by adopting the proposed strategies with the availability of large-sized quantum computers in the near future.
The paper presents a quantum method to optimize the placement of sensors on the surface of a vehicle. The problem, as posted in the BMW Quantum Computing Challenge 2021, is to arrive at the optimal positions and configurations (type and orientation) of the sensors on the vehicle surface that maximizes coverage of the Region of Interest (RoI), while minimizing the total cost of the selected sensors. The dataset contains approximately 100,000 points in the RoI, with defined measures of criticality (ranging between 0 to 1), distributed over a volume of approximately 40,000 cubic metres around the vehicle. The types of sensors, their coverage parameters and costs are inputs to the problem.The optimization problem is decomposed and solved individually for each side of the vehicle, and the results for the entire vehicle are collated and presented in the paper. The approach considers a quadratic approximation to the maximum set-coverage formulation with the advantage of obtaining the optimal number of sensors as an output from the model itself. The resultant quadratic program is solved using quantum methods, as well as a standard, state-of-the-art Integer Quadratic Program (IQP) solver, respectively. The quadratic approximation consumes qubits that are linear in the number of total configurations and significantly reduces the number of decision variables required in an Ising formulation of the problem.The quantum and classical methods are found to perform on par with each other. A detailed comparison of the results is presented in the paper. Given the combinatorial nature of the optimization problem, the classical approach may become intractable while solving the problem in an integrated manner (instead of solving individually for each side). Under such scenarios, there is a possibility to expect benefits by adopting the proposed strategies with the availability of large-sized quantum computers in the near future.
To increase efficiency in automotive manufacturing, newly produced vehicles can move autonomously from the production line to the distribution area. This requires an optimal placement of sensors to ensure full coverage while minimizing the number of sensors used. The underlying optimization problem poses a computational challenge due to its large-scale nature. Currently, classical solvers rely on heuristics, often yielding nonoptimal solutions for large instances, resulting in suboptimal sensor distributions and increased operational costs. We explore quantum computing methods that may outperform classical heuristics in the future. We implemented quantum annealing with D-Wave, transforming the problem into a quadratic unconstrained binary optimization formulation with one-hot and binary encoding. Hyperparameters like the penalty terms and the annealing time are optimized and the results are compared with default parameter settings. Our results demonstrate that quantum annealing is capable of solving instances derived from real-world scenarios. Through the use of decomposition techniques, we are able to scale the problem size further, bringing it closer to practical, industrial applicability. Through this work, we provide key insights into the importance of quantum annealing parametrization, demonstrating how quantum computing could contribute to cost-efficient, large-scale optimization problems once the hardware matures.
It is imperative to reduce carbon dioxide emissions and fossil fuel consumption to ensure the Earth's sustainable future and mitigate negative impacts like extreme climate changes caused by greenhouse gases. Electric vehicles (EVs) play a pivotal role in this context, where the convenience of charging stations is crucial in influencing consumer choices. This paper formulates the placement of charging stations as an optimization problem, considering factors like station density, accessibility, coverage, and regional cost variations, to minimize total construction costs. The problem is mapped onto a quadratic unconstrained binary optimization (QUBO) model. The QUBO can efficiently represent and solve complex combinatorial optimization problems, making it suitable for quantum and advanced classical algorithms. Utilizing digital quantum annealing, the optimal or near-optimal solutions are efficiently identified. The performance of the proposed approach is compared with classical algorithms, including mixed linear programming and simulated annealing, demonstrating significant advancements of digital annealing.
The Maximal Covering Location Problem (MCLP) is an NP-hard Combinatorial Optimization Problem (COP) that aims to determine the optimal facility placements that maximize total coverage. It is characterized by both equality and inequality constraints, which ensure correct coverage but significantly increase the complexity of exploring the solution space as instance size grows. Hybrid quantum-classical approaches might offer a promising alternative to classical optimization methods by enabling the exploration of complex energy landscapes through quantum superposition and probabilistic sampling. In this work, the MCLP is formulated as a Quadratic Unconstrained Binary Optimization (QUBO) model, where constraint embedding plays a critical role in solution quality. In particular, Unbalanced Penalization (UP) is employed as an alternative to the Slack Variables (SV) for handling inequality constraints without increasing the number of variables. This study focuses on QAOA and one of its variants, the WS-QAOA, which leverages a biased initial state derived from a continuous relaxation of the problem. Additionally, a linear ramp (LR) parameter schedule is incorporated to reduce optimization complexity. The performance of these techniques is evaluated both individually and in combination, as a function of circuit depth p and problem size. Results show that the combined approach of UP, LR, and WS-QAOA consistently improves solution quality and feasibility metrics, while maintaining robust performance as the problem size increases, highlighting its potential within hybrid quantum-classical optimization frameworks.
Abstract Optimization of pre-production vehicle configurations is one of the challenges in the automotive industry. Given a list of tests requiring cars with certain features, it is desirable to find the minimum number of cars that cover the tests and obey the configuration rules. In this paper, we model the problem in the framework of satisfiability and solve it utilizing the newly introduced hybrid constrained quadratic model (CQM) solver provided by D-Wave. The problem definition is based on the “Optimizing the Production of Test Vehicles” use-case given in the BMW quantum computing challenge. We formulate a constrained quadratic model for the problem and use a greedy algorithm to configure the cars. We benchmark the results obtained from the CQM solver with the results from the classical solvers like coin-or branch and cut and Gurobi solver. We conclude that the performance of the CQM solver is comparable to the classical solvers in optimizing the number of test vehicles, given the noise-prone quantum hardware. However, the CQM solver takes much more time, which prohibits obtaining useful quantum advantages. As an extension to the problem, we describe how the scheduling of the tests can be incorporated into the model.
Introduction. The hope of solving the problem of the avalanche-like growth of requirements for computing power, essential for solving complex routing problems and other problems of combinatorial optimization, relies on the latest quantum computers, in the development of which governments and corporations invest multi-billion investments. The article examines modern routing algorithms and performs their analysis and verification, if the authors of the algorithm provided appropriate test programs. The purpose of the article is to review the current state of development in the field of development of routing algorithms for hybrid quantum-classical clouds, analyze them and propose a classification of algorithms. Results. Modern quantum computers (QCs) make it possible to find approximate solutions to some of mathematical problems faster than classical computers. The inaccuracy of the solutions obtained by the QC is a consequence of physical and technological limitations: calculation errors are caused by thermal noise, a small number of computational elements - qubits and connections between them, which requires the decomposition of the problem and the use of heuristic algorithms. The analysis of approaches to the solution of optimization problems on QC allows us to single out: quantum response and variational search of eigenvalues based on quantum logic gates as the general directions of development of the vast majority of algorithms for solving routing problems. The considered algorithms reduce the vehicle routing problem to a quadratic unconstrained binary optimization problem, which is isomorphic to the Hamilton-Ising model. In this form, the problem is suitable for embedding in QC, which finds an approximate solution that has the best statistical reliability or corresponds to the quantum state with the lowest energy. As a separate class, vehicle routing algorithms for classical computers that use quantum computing to accelerate problem solving can be distinguished. For example, neural networks that calculate weighting factors using QC or an ant algorithm that calculates a pheromone trail in a hybrid cloud. It should be mentioned the quantum-inspired algorithms, which are based on software tools for the simulation of QC and the corresponding libraries and allow creating an effective class of algorithms for solving problems of vehicle routing. Conclusions. Combining hardware quantum annealing with a number of software tools for calculating optimization problems for classical computers in a hybrid quantum-classical cloud service allows to obtain advantages in speed and accuracy of some types of complex optimization problems of a commercial scale, in particular, routing vehicles, which is already bringing substantial profits to a number of corporations. Keywords: vehicle routing problem, quantum computer, annealing, combinatorial optimization, traveling salesman problem, clustering, qubit.
We suggest a hybrid quantum-classical routine for the NP-hard Electric Vehicle Fleet Charging and Allocation Problem. The original formulation is a Mixed Integer Linear Program with continuous variables and inequality constraints. To separate inequality constraints that are difficult for quantum routines we use a decomposition in master and pricing problems: the former targets the assignment of vehicles to reservations and the latter suggests vehicle exploitation plans that respect the battery state-of-charge constraints. The master problem is equivalent to the search for an optimal set partition. In our hybrid scheme, the master problem is reformulated in a quadratic unconstrained binary optimization problem which can be solved with quantum annealing on the DWave Advantage system. On large instances, we benchmark the performance of the decomposition technique with classical and quantum-inspired metaheuristics: simulated annealing, tabu search, and vector annealing by NEC. The numerical results with purely classical solvers are comparable to the solutions from the traditional mixed integer linear programming approaches in terms of solution quality while being faster. In addition, it scales better to larger instances. The major advantage of the proposed approach is that it enables quantum-based methods for this realistic problem with many inequality constraints. We show this by initial studies on DWave hardware where optimal solutions can be found for small instances.