The Quantum Approximate Optimization Algorithm (QAOA) is a heuristic for unconstrained combinatorial optimization.It prepares a statefrom which one would like to sample good solutions with high probability.QAOA is specified by • the initial state + 𝑛 , the uniform superposition over all basis states,• a Cost Hamiltonian 𝐻 𝐶 , used to phase basis states proportional to their cost 𝐶 𝑥 : 𝑥 ↦ 𝑒 -𝑖𝛾𝐶(𝑥) |𝑥⟩ and to evaluate the expectation value of the QAOA state, ⟨𝜷, 𝜸 𝐻 𝐶 𝜷, 𝜸⟩,• a Transverse Field Mixer ∑ 𝑖=1 𝑛 𝑋 𝑖 , used to interfere states in order to boost good solutions,• 𝑝 rounds with individual angle parameters 𝛽 1 , … , 𝛽 𝑝 , 𝛾 1 , … , 𝛾 𝑝 .
The Quantum Approximate Optimization Algorithm (QAOA) is a heuristic for unconstrained combinatorial optimization.It prepares a statefrom which one would like to sample good solutions with high probability.QAOA is specified by • the initial state + 𝑛 , the uniform superposition over all basis states,• a Cost Hamiltonian 𝐻 𝐶 , used to phase basis states proportional to their cost 𝐶 𝑥 : 𝑥 ↦ 𝑒 -𝑖𝛾𝐶(𝑥) |𝑥⟩ and to evaluate the expectation value of the QAOA state, ⟨𝜷, 𝜸 𝐻 𝐶 𝜷, 𝜸⟩,• a Transverse Field Mixer ∑ 𝑖=1 𝑛 𝑋 𝑖 , used to interfere states in order to boost good solutions,• 𝑝 rounds with individual angle parameters 𝛽 1 , … , 𝛽 𝑝 , 𝛾 1 , … , 𝛾 𝑝 .
The quantum approximate optimization algorithm (QAOA) is a near-term quantum algorithm aimed at solving combinatorial optimization problems. Since its introduction, various generalizations have emerged, spanning modifications to the initial state, phase unitaries, and mixer unitaries. In this work, we present an analytical study of broad families of QAOA variants. We begin by examining a family of QAOA with product mixers, which includes single-body mixers parametrized by multiple variational angles, and derive exact analytical expressions for the cost expectation on weighted problem graphs in the single-layer ansatz setting. We then analyze a family of QAOA that employs many-body Grover-type mixers, deriving analogous analytical expressions for weighted problem hypergraphs in the setting of arbitrarily many circuit ansatz layers. For both families, we allow individual phase angles for each node and edge (hyperedge) in the problem graph (hypergraph). Our results reveal that, in contrast to product mixers, the Grover mixer is sensitive to contributions from cycles of all lengths in the problem graph, exhibiting a form of non-locality. Our study advances the understanding of QAOA's behavior in general scenarios, providing a foundation for further theoretical exploration.
The classical homotopy optimization approach has the potential to deal with highly nonlinear landscapes, such as the energy landscape of quantum approximate optimization algorithm (QAOA) problems. Following this motivation, we introduce Hamiltonian-oriented homotopy QAOA (HOHo-QAOA), a heuristic method for combinatorial optimization using QAOA, based on classical homotopy optimization. The method consists of a homotopy map that produces an optimization problem for each value of the interpolating parameter. Therefore, HOHo-QAOA decomposes the optimization of QAOA into several loops, each using a mixture of the mixer and the objective Hamiltonian for cost function evaluation. Furthermore, we conclude that the HOHo-QAOA improves the search for low-energy states in the nonlinear energy landscape and outperforms other variants of QAOA.
The Quantum Approximate Optimization Algorithm (QAOA) is a hybrid quantum algorithm described as ansatzes that represent both the problem and the mixer Hamiltonians. Both are parameterizable unitary transformations executed on a quantum machine/simulator and whose parameters are iteratively optimized using a classical device to optimize the problem's expectation value. To do so, in each QAOA iteration, most of the literature uses a quantum machine/simulator to measure the QAOA outcomes. However, this poses a severe bottleneck considering that quantum machines are hardly constrained (e.g. long queuing, limited qubits, etc.), likewise, quantum simulation also induces exponentially-increasing memory usage when dealing with large problems requiring more qubits. These limitations make today's QAOA implementation impractical since it is hard to obtain good solutions with a reasonably-acceptable time/resources. Considering these facts, this work presents a new approach with two main contributions, including (I) removing the need for accessing quantum devices or large-sized classical machines during the QAOA optimization phase, and (II) ensuring that when dealing with some k-bounded pseudo-Boolean problems, optimizing the exact problem's expectation value can be done in polynomial time using a classical computer.
The Quantum Approximate Optimization Algorithm (QAOA) and its variants are leading algorithms to help solve challenging combinatorial optimization problems. QAOA maps these problems to Ising Hamiltonians such that their ground state is the desired solution. Candidate solutions are then drawn from a variational quantum circuit. The performance of QAOA hinges on a set of variational angles. However, finding good angles is an instance-specific and computationally expensive non-convex classical optimization task. Here, we learn the mapping from the problem instance to high-quality QAOA angles. Our learned models replace the per-instance optimization, that we call the solver, with a single forward pass that is several orders of magnitude faster than the solver with a near identical quality. Our models further generalize to unseen topologies such as Barabási-Albert and 2D grid graphs. Experiments on quantum hardware confirm that QAOA samples with angles produced by our open-source models are indistinguishable from solver angles. Crucially, models sensitive to the topology of the problem instance increase the quality of the QAOA angles. Our work amortizes a major bottleneck in QAOA by an up-front data generation and training cost. Importantly, this cost can be amortized over time in settings where many similar problems are optimized on a regular basis, as is often the case in applications for industry.
The quantum approximate optimization algorithm (QAOA) is a promising quantum algorithm that can be used to approximately solve combinatorial optimization problems. The usual QAOA ansatz consists of an alternating application of the cost and mixer Hamiltonians. In this work, we study how using Hamiltonians other than the usual cost Hamiltonian, dubbed custom phase operators, can affect the performance of the QAOA. We derive an expected value formula for the QAOA with custom phase operators at p=1 and show numerically that some of these custom phase operators can achieve higher approximation ratios than the original algorithm implementation. Out of all the graphs tested at p=1, 0.036% of the random custom phase operators, 75.9% of the subgraph custom phase operators, 95.1% of the triangle-removed custom phase operators, and 93.9% of the maximal degree edge-removed custom phase operators have a higher approximation ratio than the original QAOA implementation. Furthermore, we numerically simulate these phase operators for p=2 and p=3 levels of QAOA and find that there exist a large number of subgraph, triangle-removed, and maximal degree edge-removed custom phase operators that have a higher approximation ratio than the QAOA at the same depth. These findings open up the question of whether better phase operators can be designed to further improve the performance of the QAOA.
The Quantum Approximate Optimization Algorithm (QAOA) is one of the promising near-term algorithms designed to find approximate solutions for combinatorial optimization problems. The algorithm prepares a parametrized state that is aimed to maximize the expectation value of the objective function of the problem. The circuit for QAOA consists of p layers, and it depends on 2p parameters, the determination of which can be carried out using a variational quantum eigensolver (VQE) subroutine. This is a variational approach for finding optimal parameters, where the quantum state is prepared with a quantum computer, and a classical computer is used for calculating the corresponding objective function value and performing an outer loop optimization routine in order to find optimal parameters. Earlier work on the algorithm has shown that QAOA is closely related to the Quantum Adiabatic Algorithm, which results in noticeable patterns in the optimal parameters. To this purpose, two methods, INTERP and FOURIER, were proposed to exploit this structure by Zhou et al. (2018). In this thesis, I extend upon these results by examining the effectiveness of one of their methods, the INTERP method, on the Max-Cut problem from graph theory. The performance of QAOA using this method was studied on several classes of graphs and benchmarked against the currently best-known classical algorithm Goemans-Williamson, which achieves an approximation ratio of ρ ≈ 0.878 on arbitrary graphs. The classes of graphs examined include cyclic, weighted and unweighted 3-regular, and Erdős–Rényi graphs with edge probabilities of 0.5 and 0.75 and graph sizes ranging from 4 to 16. Moreover, it was investigated if the INTERP method offers an advantage compared to random initialization of parameters and whether or not the method is polynomial in p. It was found that different graph classes lead to similar but different parameter patterns. Furthermore, the performance of QAOA using the INTERP method was dependent on the graph class considered. For the small graphs investigated it was found that QAOA outperforms Goemans-Williamson on ER-0.50, ER-0.75 and weighted 3-regular graphs from p=7 and beyond with respect to how well the expectation of the objective function approximates the optimal value, while for unweighted 3-regular graphs p=6 suffices. However, the calculation of the parameters is costly and requires a number of function evaluations that is on the order of the number of possible bipartitions of small graph with sizes n ≤ 16. Moreover, the numerical results suggested that indeed the method is polynomial in p advocating that the algorithm might be a strong alternative to Goemans-Williamson for large graph sizes, once hardware allows it.