Institutional Repository
Technical University of Crete
Technical University of Crete
EN
|
EL
| URI: | http://purl.tuc.gr/dl/dias/5551FF4C-F40D-45AA-ACBF-1BC8492145AB | ||
| Year | 2021 | ||
| Type of Item | Diploma Work | ||
| License |
|
||
| Bibliographic Citation | Ioannis Leonidas, "Quantum approximate optimization algorithms and applications", Diploma Work, School of Electrical and Computer Engineering, Technical University of Crete, Chania, Greece, 2021 https://doi.org/10.26233/heallink.tuc.90563 | ||
| Appears in Collections |
In this thesis we start by defining the basic components that bring together a quantum circuit. Weexplain basic gates, the concept of entanglement and why these are important for the construction ofquantum algorithms. Then we proceed by analyzing two basic quantum algorithms (Deutsch-Joszaand Grover’s algorithms), which are the earliest in quantum computing and illustrate the notion ofa quantum speed up. Next, we analyse the basic approaches for quantum optimization, includingthe notions of quantum annealing and adiabatic quantum computing, and analyze the first mainalgorithm of this thesis which is the Quantum Approximate Optimization Algorithm (QAOA). Wealso introduce and explain the Variational Quantum Eigensolver (VQE) and its hardware efficientversion, which does not require specific gates decomposition and compare it with QAOA on thecontext of solving MAXCUT problems. In the final part, we analyze QAOA on a more industrialoptimization setting, and solve instances of the Tail Assignment Problem for assigning planes indifferent routes. For this problem we test QAOA using the conventional method of minimizing theexpectation value of the cost Hamiltonian and discuss the results. Finally, we also apply solve theproblem by an another method based on minimizing the Gibbs objective function where we seeimprovements in the success probability. We analyse the inner workings of the algorithms, discussthe results and compare the various methods for different problem sizes and instances. We run ourquantum algorithms in simulators, with noise and ideal ones, as well as on and prototype quantumhardware available in the cloud in IBM Q and analyze the performance for different problem sizeand qubit numbers.
Copyright © DIAS 2013
