Techniques and Applications of the Quantum Approximate Optimization Algorithm
Date Issued
May 2026
Author(s)
Wilkie, Anthony
University of Tennessee at Knoxville
Advisor(s)
Rebekah Herrman
Additional Advisor(s)
James Ostrowski
Soham Das
George Siopsis
Abstract
The quantum approximate optimization algorithm (QAOA) is a variational quantum algorithm that has been shown to be effective at solving combinatorial optimization problems. While QAOA performs well at these problems, new methods of improving the performance of the algorithm are still being explored. This thesis examines three novel methods of improving QAOA's performance and expanding the types of problems it can solve. In the first part of this work, we study how using Hamiltonians other than the usual cost Hamiltonian, dubbed custom phase operators, can affect the performance of QAOA. We derive an expected value formula for QAOA with custom phase operators at $p = 1$. We construct four classes of custom phase operators and shown numerically up to $p=3$ that a large percentage of these operators outperform the standard cost Hamiltonian on MaxCut problems. We next modify QAOA to solve quadratic constrained binary optimization problems. Specifically, we develop a variational approach which creates a superposition with flag qubits to identify when a constraint is violated or not. The resulting state is then used in Grover-mixer QAOA to solve the constrained problem. We test the approach on sets of linear inequality constraints and find we are able to generate the state with an accuracy of 98\%. Finally, use QAOA to solve multi-stage stochastic binary optimization problems, which are used to model decision-making under uncertainty in a variety of fields. These problems are challenging to solve due to the exponentially growing number of possible solutions with the number of stages and scenarios. We propose three encoding strategies for mapping these problems to quantum circuits using QAOA. To handle the non-anticipativity constraints inherent in stochastic programming, we integrate QAOA into the Progressive Hedging Algorithm (PHA). We compare the performance as well as the quantum resources required for each encoding strategy. The results show an increase the solution quality of the first-stage solution, with the average Hamming distance of the first-stage solutions decreasing from $0.2256$ without PHA to $0.1427$ with PHA across all problems tested.
Disciplines
Degree
Doctor of Philosophy
Major
Industrial Engineering
File(s)![Thumbnail Image]()
Name
WilkieDiss_2026.pdf
Size
5.1 MB
Format
Adobe PDF
Checksum (MD5)
8085e8e397d9e731cd756290dd7fdc05