The major advances in quantum computing over the last few decades have sparked great interest in applying it to solve the most challenging computational problems in a wide variety of areas. One of the most pronounced domains here are optimization problems and a number of algorithmic approaches have been proposed for their solution. For the current noisy intermediate-scale quantum (NISQ) computers the quantum approximate optimization algorithm (QAOA), the variational quantum eigensolver (VQE), and quantum annealing (QA) are the central algorithms for this problem class. The two former can be executed on digital gate-model quantum computers, whereas the latter requires a quantum annealer. Across all hardware architectures and manufactures, the quantum computers available today share the property of being too error-prone to reliably execute involved quantum circuits as they typically arise from quantum optimization algorithms. In order to characterize the limits of existing quantum computers, many component and system level benchmarks have been proposed. However, owing to the complex nature of the errors in quantum systems these benchmark fail to provide predictive power beyond simple quantum circuits and small examples. Application oriented benchmarks have been proposed to remedy this problem, but both, results from real quantum systems as well as use cases beyond constructed academic examples, remain very rare. This paper addresses precisely this gap by considering two industrial relevant use cases: one in the realm of optimizing charging schedules for electric vehicles, the other concerned with the optimization of truck routes. Our central contribution are systematic series of examples derived from these uses cases that we execute on different processors of the gate-based quantum computers of IBM as well as on the quantum annealer of D-Wave.
The major advances in quantum computing over the last few decades have sparked great interest in applying it to solve the most challenging computational problems in a wide variety of areas. One of the most pronounced domains here are optimization problems and a number of algorithmic approaches have been proposed for their solution. For the current noisy intermediate-scale quantum (NISQ) computers the quantum approximate optimization algorithm (QAOA), the variational quantum eigensolver (VQE), and quantum annealing (QA) are the central algorithms for this problem class. The two former can be executed on digital gate-model quantum computers, whereas the latter requires a quantum annealer. Across all hardware architectures and manufactures, the quantum computers available today share the property of being too error-prone to reliably execute involved quantum circuits as they typically arise from quantum optimization algorithms. In order to characterize the limits of existing quantum computers, many component and system level benchmarks have been proposed. However, owing to the complex nature of the errors in quantum systems these benchmark fail to provide predictive power beyond simple quantum circuits and small examples. Application oriented benchmarks have been proposed to remedy this problem, but both, results from real quantum systems as well as use cases beyond constructed academic examples, remain very rare. This paper addresses precisely this gap by considering two industrial relevant use cases: one in the realm of optimizing charging schedules for electric vehicles, the other concerned with the optimization of truck routes. Our central contribution are systematic series of examples derived from these uses cases that we execute on different processors of the gate-based quantum computers of IBM as well as on the quantum annealer of D-Wave.
The reduction of CO2emissions is one of the major challenges in the current century. A game-changer might be quantum computing due to the proposed capabilities. A key field of interest for reducing CO2emissions is the energy sector being transformed from fossil-based to be based on renewable energies and simultaneously combining electricity, heating, mobility, and manufacturing industries.Here, we study an use case for optimal charging scheduling of battery-electric service vehicles considering the requirements of their tasks, local solar power generation, and their battery capabilities to minimize power grid usage and so CO2emissions from fossil-based electricity generation.The study compares benchmark results obtained classically with results obtained by the quantum approximate optimization algorithm (QAOA) to show the current capability of gate-based quantum optimization for a real-world use case. We present different formulations of the optimization problem and specific considerations for our use case necessary to yield optimal solutions reproducible with IBM’s gate-based quantum computers. Here, we used Qiskit’s built-in QAOA method but also self-made methods to examine the influence of the complexity of the problem formulation (penalty factors, landscape of cost function, etc.) as well as the dependence on parameters of the QAOA method (classical optimizer, result extraction, etc.). To obtain reliable results, we used different physical backends and simulations.Finally, we summarize or results and address future improvements for the used QAOA approach for automated real-world applications.
Quantum optimization allows for up to exponential quantum speedups for specific, possibly industrially relevant problems. As the key algorithm in this field, we motivate and discuss the Quantum Approximate Optimization Algorithm (QAOA), which can be understood as a slightly generalized version of Quantum Annealing for gate-based quantum computers. We delve into the quantum circuit implementation of the QAOA, including Hamiltonian simulation techniques for higher-order Ising models, and discuss parameter training using the parameter shift rule. An example implementation with Pennylane source code demonstrates practical application for the Maximum Cut problem. Further, we show how constraints can be incorporated into the QAOA using Grover mixers, allowing to restrict the search space to strictly valid solutions for specific problems. Finally, we outline the Variational Quantum Eigensolver (VQE) as a generalization of the QAOA, highlighting its potential in the NISQ era and addressing challenges such as barren plateaus and ansatz design.
Quantum computing is an important developing technology with the potential to revolutionise the landscape of scientific and business problems that can be practically addressed. The widespread excitement derives from the potential for a fault tolerant quantum computer to solve previously intractable problems. Such a machine is not expected to be available until 2030 at least. Thus we are currently in the so-called NISQ era where more heuristic quantum approaches are being applied to early versions of quantum hardware. In this paper we seek to provide a more accessible explanation of many of the more technical aspects of quantum computing in the current NISQ era exploring the 2 main hybrid classical-quantum algorithms, QAOA and VQE, as well as quantum annealing. We apply these methods, to an example of combinatorial optimisation in the form of a facilities location problem. Methods explored include the applications of different types of mixer (X, XY and a novel 3XY mixer) within QAOA as well as the effects of many settings for important meta parameters, which are often not focused on in research papers. Similarly, we explore alternative parameter settings in the context of quantum annealing. Our research confirms the broad consensus that quantum gate hardware will need to be much more capable than is available currently in terms of scale and fidelity to be able to address such problems at a commercially valuable level. Quantum annealing is closer to offering quantum advantage but will also need to achieve a significant step up in scale and connectivity to address optimisation problems where classical solutions are sub-optimal.
Optimization problems are pervasive across various domains, including logistics, finance, machine learning, and operations research. Quantum computing has emerged as a promising frontier to address these challenges, offering potential speedups for certain classes of optimization tasks. This paper explores the development and application of quantum algorithms, such as the Quantum Approximate Optimization Algorithm (QAOA), Variational Quantum Eigensolver (VQE), and Grover’s search algorithm, tailored for optimization. Recent advancements in hardware, hybrid quantum-classical approaches, and variational techniques have enabled practical implementations on Noisy Intermediate-Scale Quantum (NISQ) devices. Challenges such as noise, scalability, and performance limitations are also discussed. Through theoretical analysis and case studies, this work demonstrates how quantum computing can complement classical methods, paving the way for breakthroughs in solving complex optimization problems.
Quantum computing is a rapidly developing field that has seen a huge amount of interest in the last couple of decades due to its promise of revolutionizing several domains of business and science. It presents a new way of doing computations by making use of fundamental properties of quantum mechanics such as superposition and entanglement. Optimization, on the other hand, is a field that is omnipresent in the industry and where small improvements can have a significant impact. This thesis aims to tackle optimization problems using quantum algorithms.NP-hard optimization problems are not believed to be exactly solvable through general polynomial time algorithms. Variational quantum algorithms (VQAs) to address such combinatorial problems have been of great interest recently. Such algorithms are heuristic and aim to obtain an approximate solution. The hardware, however, is still in its infancy and the current Noisy Intermediate Scale Quantum (NISQ) computers are not able to optimize industrially relevant problems. Moreover, the storage of qubits and introduction of entanglement require extreme physical conditions.An issue with contemporary quantum optimization algorithms such as the Quantum Approximate Optimization Algorithm (QAOA) is that they scale linearly with problem size. To tackle this issue, we present the LogQ encoding, using which we can design quantum variational algorithms that scale logarithmically with problem size - opening an avenue for treating optimization problems of unprecedented scale on gate-based quantum computers. We show how this algorithm can be applied to several combinatorial optimization problems such as Maximum Cut, Minimum Partition, Maximum Clique and Maximum Weighted Independent Set (MWIS). Subsequently, these algorithms are tested on a quantum simulator with graph sizes of over a hundred nodes and on a real quantum computer up to graph sizes of 256. To our knowledge, these constitute the largest realistic combinatorial optimization problems ever run on a NISQ device, overcoming previous problem sizes by almost tenfold.Next, we apply the LogQ encoding to two use-cases for large companies such as TotalEnergies. Fleet conversion is the process of transitioning a fleet of vehicles to more sustainable and environmentally friendly alternatives. It is modeled as a column generation scheme with the MWIS problem as the sub-problem or worker problem. We use the LogQ method to solve the MWIS Workers and demonstrate how quantum and classical solvers can be used together in a hybrid manner to approach an industrial-sized use-case. Mesh segmentation refers to the process of dividing a complex mesh (composed of vertices, edges, and faces) into meaningful and semantically coherent parts or regions. Mesh segmentation plays an important part in computer modeling, which is extensively used in the core domains of TotalEnergies' activities such as Earth imaging, physical modeling for reservoirs, and others. We define the problem as a graph optimization problem and use the LogQ encoding to solve it.
Vehicle Routing Problem (VRP) is considered one of the most challenging problems with application in several domains, including transportation and logistics distribution. VRP is known to be NP-Hard problem. Several algorithms have been proposed to solve VRP in polynomial time. However, these algorithms are inefficient if the VRP instance increases. Recently, researchers investigated how quantum computing can be used to solve VRP. In particular, two promising variational quantum algorithms have been studied, i.e., Variational Quantum Eigensolver (VQE) and Quantum Approximate Optimization Algorithm (QAOA). In this paper, we implement both algorithms on IBM Qiskit and compare their evaluation in solving several instances of VRP. We observe that current Noisy-Intermediate Scale Quantum (NISQ) devices cannot solve VRP instances beyond 5 nodes and 2 vehicles. Furthermore, we observe that classical optimizers still provide better results. However, we believe that with the rapid advancement of quantum computing manufacturing, VQE and QAOA can provide better performance as compared to classical computing,