The Quantum Approximate Optimization Algorithm (QAOA) is a promising variational quantum algorithm introduced to tackle classically intractable combinatorial optimization problems. This tutorial offers a comprehensive, first-principles introduction to QAOA and its properties, focusing on its application to Quadratic and Polynomial Unconstrained Binary Optimization (QUBO and PUBO) problems. The tutorial begins by outlining variational quantum circuits and QUBO problems, focusing on their key properties and the encoding of problem constraints through quadratic penalty terms. Next, it explores the QAOA in detail, covering its Hamiltonian formulation, gate decomposition, and example applications, along with their implementation and performance results. This is followed by an analysis of the algorithm's energy landscape, where proofs are provided for its symmetry and periodicity, and where a resulting parameter space reduction is proposed. Finally, the tutorial extends these concepts to PUBO problems by generalizing the results to higher-order Hamiltonians and discussing the associated symmetries and circuit construction.
This thesis is devoted to four modern quantum optimisation algorithms and their applications. In the first chapter, we provide a complete Quantum Approximate Optimisation Algorithm (QAOA) pipeline for the discrete global minimum-variance portfolio (DGMVP) problem. We introduce an ansatz with efficient initial-state preparation, new hard mixing operators satisfying the constraints of the DGMVP problem, and scalable cost operators utilising binary encoding of the qubits. Benchmarking the method with the most effective optimisation strategies---dual annealing and unfrozen layerwise optimisation---indicates a scaling advantage over classical methods in finding the global optimum of the DGMVP problem. In the second chapter, we show an end-to-end quantum/quantum-inspired Goemans-Williamson semidefinite programming (SDP) method for relaxing Quadratic Unconstrained Binary Optimisation (QUBO) problems and extracting their rounding energy. Our method identifies a class of QUBO instances that is effectively solvable in polylogarithmic time relative to the problem dimension, under the assumptions of Pauli sparsification of the QUBO cost matrix, reducibility of the diagonal constraints, and efficient evaluation of the corresponding Gibbs-state expectation values. Further, we identify the commuting 1D Hamiltonian and the Kronecker graph as practically important instances. Our numerical experiments show that our method solves the SDP and QUBO with up to
250 variables for 1D Hamiltonian instances and achieves results competitive with the best classical solver for Kronecker graphs, giving strong evidence of the power of our algorithm. In the third chapter, we improve the current QAOA method with an iterative warm-start initial-state preparation method. We implement the
t-th order statistic state as the warm-start initial state generated from each QAOA optimisation loop. We achieve an improved approximation ratio when solving the 3-regular MaxCut problem, and find that the worst-case approximation ratio converges to that of the best classical algorithm for
p=1 QAOA. Additionally, our method achieves more favourable scaling than standalone QAOA, single-string warm-started QAOA, and a classical constrained-sampling approach when solving the DGMVP problem. In the fourth chapter, we provide a hard-constrained Grover adaptive search (GAS) method for fixed-sum quadratic binary optimisation problems, and an extension of the alternating direction method of multipliers (ADMM) framework for fixed-sum quartic binary optimisation. Our method guarantees at least a quadratic speed-up over the classical method, and exponentially reduces the gate count for solving fixed-sum binary optimisation when compared with the soft-constrained GAS in the fault-tolerant quantum computing regime. In summary, our contributions include efficient algorithms and novel frameworks that substantially improve performance and broaden the applicability of these quantum optimisation methods. The proposed methods exhibit favourable scaling behaviour and indicate potential quantum advantages in solving challenging optimisation problems, thereby motivating further research at the interface of quantum computing and optimisation.
The Quantum Approximate Optimization Algorithm (QAOA) has shown promise in solving combinatorial optimization problems by leveraging quantum computational power. We propose a simple approach, the Two-Step QAOA, which aims to improve the effectiveness of QAOA by decomposing problems with k-hot encoding QUBO (Quadratic Unconstrained Binary Optimization) formulations. By identifying and separating the problem into two stages, we transform soft constraints into hard constraints, simplifying the generation of initial conditions and enabling more efficient optimization. The method is particularly beneficial for tackling complex societal problems that often involve intricate constraint structures.
Abstract The quantum approximate optimisation algorithm (QAOA) is a hybrid quantum–classical algorithm used to approximately solve combinatorial optimisation problems. It involves multiple iterations of a parameterised ansatz that consists of a problem and mixer Hamiltonian, with the parameters being classically optimised. While QAOA can be implemented on near-term quantum hardware, physical limitations such as gate noise, restricted qubit connectivity, and state-preparation-and-measurement (SPAM) errors can limit circuit depth and decrease performance. To address these limitations, this work introduces the eXpressive QAOA (XQAOA), an overparameterised variant of QAOA that assigns more classical parameters to the ansatz to improve its performance at low depths. XQAOA also introduces an additional Pauli-Y component in the mixer Hamiltonian, allowing the mixer to implement arbitrary unitary transformations on each qubit. To benchmark the performance of XQAOA at unit depth, we derive its closed-form expression for the MaxCut problem and compare it to QAOA, Multi-Angle QAOA (MA-QAOA) (Herrman et al 2022 Sci. Rep. 12 6781), a classical-relaxed algorithm, and the state-of-the-art Goemans–Williamson algorithm on a set of unweighted regular graphs with 128 and 256 nodes for degrees ranging from 3 to 10. Our results indicate that at unit depth, XQAOA has benign loss landscapes with local minima concentrated near the global optimum, allowing it to consistently outperform QAOA, MA-QAOA, and the classical-relaxed algorithm on all graph instances and the Goemans–Williamson algorithm on graph instances with degrees greater than 4. Small-scale simulations also reveal that unit-depth XQAOA invariably surpasses both QAOA and MA-QAOA on all tested depths up to five. Additionally, we find an infinite family of graphs for which XQAOA solves MaxCut exactly and analytically show that for some graphs in this family, special cases of XQAOA are capable of achieving a much larger approximation ratio than QAOA. Overall, XQAOA is a more viable choice for variational quantum optimisation on near-term quantum devices, offering competitive performance at low depths.
Over the past few years, many researchers around the world have been keen to know the potential and efficiency of quantum computers. The researchers have focused on specific issues that classical computers cannot solve or issues that quantum computers can handle in a better way. Among these various attractive research topics in quantum computers, this paper introduces the Quantum Approximate Optimization Algorithm (QAOA) which guarantees relatively considerable performances in many combinatorial optimization problems. For the comprehensive understanding of QAOA, this paper also describes the approximate optimization, the Quantum Alternating Operator Ansatz, and applications. Besides the theories of QAOA and Quantum Alternating Operator Ansatz, this paper explains the applications of QAOA to major combinatorial optimization problems such as maximum cut (MaxCut) problem and the max-independent set (MIS) problem.