Quantum computing is an emerging field on the multidisciplinary interface between physics, engineering, and computer science with the potential to make a large impact on computational intelligence (CI). The aim of this paper is to introduce quantum approximate optimization methods to the CI community because of direct relevance to solving combinatorial problems. We introduce quantum computing and variational quantum algorithms (VQAs). VQAs are an effective method for the near-term implementation of quantum solutions on noisy intermediate-scale quantum (NISQ) devices with less reliable qubits and early-stage error correction. Then, we explain Farhi et al.'s quantum approximate optimization algorithm (Farhi's QAOA, to prevent confusion). This VQA is generalized by Hadfield et al. to the quantum alternating operator ansatz (QAOA), which is a nature-inspired (particularly, adiabatic) quantum metaheuristic for approximately solving combinatorial optimization problems on gate-based quantum computers. We discuss connections of QAOA to relevant domains, such as computational learning theory and genetic algorithms, discussing current techniques and known results regarding hybrid quantum-classical intelligence systems. We present a schematic of how QAOA is constructed, and also discuss how CI techniques can be used to improve QAOA. We conclude with QAOA implementations for the well-known maximum cut, maximum bisection, and traveling salesperson problems, which can serve as templates for CI practitioners interested in using QAOA.
Quantum computing is an emerging field on the multidisciplinary interface between physics, engineering, and computer science with the potential to make a large impact on computational intelligence (CI). The aim of this paper is to introduce quantum approximate optimization methods to the CI community because of direct relevance to solving combinatorial problems. We introduce quantum computing and variational quantum algorithms (VQAs). VQAs are an effective method for the near-term implementation of quantum solutions on noisy intermediate-scale quantum (NISQ) devices with less reliable qubits and early-stage error correction. Then, we explain Farhi et al.'s quantum approximate optimization algorithm (Farhi's QAOA, to prevent confusion). This VQA is generalized by Hadfield et al. to the quantum alternating operator ansatz (QAOA), which is a nature-inspired (particularly, adiabatic) quantum metaheuristic for approximately solving combinatorial optimization problems on gate-based quantum computers. We discuss connections of QAOA to relevant domains, such as computational learning theory and genetic algorithms, discussing current techniques and known results regarding hybrid quantum-classical intelligence systems. We present a schematic of how QAOA is constructed, and also discuss how CI techniques can be used to improve QAOA. We conclude with QAOA implementations for the well-known maximum cut, maximum bisection, and traveling salesperson problems, which can serve as templates for CI practitioners interested in using QAOA.
The promise of quantum computing to address complex problems requiring high computational resources has long been hindered by the intrinsic and demanding requirements of quantum hardware development. Nonetheless, the current state of quantum computing, denominated Noisy Intermediate-Scale Quantum (NISQ) era, has introduced algorithms and methods that are able to harness the computational power of current quantum computers with advantages over classical computers (referred to as quantum advantage). Achieving quantum advantage is of particular relevance for the combinatorial optimization domain, since it often implies solving an NP-Hard optimization problem. Moreover, combinatorial problems are highly relevant for practical application areas, such as operations research, or resource allocation problems. Among quantum computing methods, Variational Quantum Algorithms (VQA) have emerged as one of the strongest candidates towards reaching practical applicability of NISQ systems. This paper explores the current state and recent developments of VQAs, emphasizing their applicability to combinatorial optimization. We identify the Quantum Approximate Optimization Algorithm (QAOA) as the leading candidate for these problems. Furthermore, we implement QAOA circuits with varying depths to solve the MaxCut problem on graphs with 10 and 20 nodes, demonstrating the potential and challenges of using VQAs in practical optimization tasks. We release our code, dataset and optimized circuit parameters under https://github.com/DanielFPerez/VQA-for-MaxCut.
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.
Noisy intermediate-scale quantum computers (NISQ computers) are now readily available, motivating many researchers to experiment with Variational Quantum Algorithms (VQAs). Among them, the Quantum Approximate Optimization Algorithm (QAOA) is one of the most popular one studied by the combinatorial optimization community. In this tutorial, we provide a mathematical description of the class of Variational Quantum Algorithms, assuming no previous knowledge of quantum physics from the readers. We introduce precisely the key aspects of these hybrid algorithms on the quantum side (parametrized quantum circuit) and the classical side (guiding function, optimizer). We devote a particular attention to QAOA, detailing the quantum circuits involved in that algorithm, as well as the properties satisfied by its possible guiding functions. Finally, we discuss the recent literature on QAOA, highlighting several research trends.
Combinatorial optimization problems play a vital role in computer science and engineering, with applications in logistics, network design, finance, and resource allocation. However, many of these problems are NP-hard, making them computationally expensive to solve using classical optimization techniques, especially for large-scale instances. In recent years, quantum computing has emerged as a promising paradigm capable of addressing these limitations by leveraging quantum mechanical principles such as superposition and entanglement. This study investigates the application of quantum computing for solving combinatorial optimization problems, with a focus on algorithm design, complexity analysis, and real-world applicability. The research primarily employs the Quantum Approximate Optimization Algorithm (QAOA) and Grover's search algorithm to solve representative problems such as Max-Cut and the Knapsack problem. The performance of these algorithms is evaluated using key metrics including accuracy, execution time, and approximation ratio, and is compared with classical optimization techniques. The results demonstrate that QAOA is capable of generating near-optimal solutions, achieving accuracy levels of up to 93% for small problem instances. However, the study also highlights the challenges associated with current quantum systems, including noise, limited qubit availability, and increased execution time. Comparative analysis reveals that while classical methods remain more efficient for small-scale problems, quantum algorithms show significant potential for scalability and handling complex optimization tasks. The findings suggest that hybrid quantum-classical approaches offer a practical solution in the current Noisy Intermediate-Scale Quantum (NISQ) era. The study concludes that although quantum computing is still evolving, it holds strong potential for transforming combinatorial optimization in the future.
In this thesis, I explore the domain of hybrid quantum-classical computation, the foremost approach for utilizing Noisy Intermediate-Scale Quantum (NISQ) devices. The opening chapter presents an overview of Variational Quantum Algorithms (VQAs), highlighting the primary algorithmic challenges. It offers an in-depth review of the Quantum Approximate Optimization Algorithm (QAOA), discussing its variants for ground state preparation. In the second chapter, we apply QAOA for the supervised learning of a simple Binary Neural Network. This model represents an idealized yet prototypical example of classical combinatorial optimization problems involving multi-spin interactions. In the following chapters, the discussion shifts toward quantum many-body ground state preparation, focusing on the one-dimensional Heisenberg XYZ model and the longitudinal-transverse-field Ising model (LTFIM). We have developed a novel technique that, at any point in the phase diagram, leverages the transferability of a specific class of optimal schedules from systems with small to those with larger numbers of qubits. This approach mitigates trainability issues, specifically vanishing gradients (Barren Plateaus). Next, we tailor a QAOA scheme to characterize a topological quantum phase transition within a lattice gauge theory model. This investigation is particularly significant due to its implications for high-energy physics and relevance to quantum error correction and surface codes. In the concluding chapter, I propose new stimulating research directions and help to identify core challenges and unresolved questions in variational quantum computing that transcend any particular application domain.
Variational Quantum Algorithms are a major method of harnessing Noisy Intermediate-Scale Quantum devices to solve classically intractable problems in physics, chemistry, optimization, and machine learning. The current review offers a critical overview of VQAs, with special emphasis on their theoretical backgrounds, algorithmic structures, and application performance within realistic models of noise. Several key variants, such as the Variational Quantum Eigensolver, Quantum Approximate Optimization Algorithm, and Quantum Neural Networks, are compared in terms of noise robustness, ansatz archi- tecture, and hybrid quantum-classical methods of optimization. Benchmarks in fields such as quantum chemistry, finance modeling, and particles and nuclei physics reveal the poten- tial of VQAs in achieving practical quantum advantage. Fundamentally limiting factors 1such as barren plateaus, optimization overhead, and hardware constraints are considered in addition to mitigation strategies, including adaptive construction of ansatz, informed training in the presence of noise, and quantum error correction using QVECTOR. The paper is concluded with an overview of the scalability and future of VQAs in the direction of transitioning toward fault-tolerant quantum computing.