The classical homotopy optimization approach has the potential to deal with highly nonlinear landscape, such as the energy landscape of QAOA problems. Following this motivation, we introduce Hamiltonian-Oriented Homotopy QAOA (HOHo-QAOA), that is 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 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 classical homotopy optimization approach has the potential to deal with highly nonlinear landscape, such as the energy landscape of QAOA problems. Following this motivation, we introduce Hamiltonian-Oriented Homotopy QAOA (HOHo-QAOA), that is 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 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 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 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 , … , 𝛾 𝑝 .
Constructing an optimal mixer for Quantum Approximate Optimization Algorithm (QAOA) Hamiltonian is crucial for enhancing the performance of QAOA in solving combinatorial optimization problems. We present a systematic methodology for constructing the QAOA tailored mixer Hamiltonian, ensuring alignment with the inherent symmetries of classical optimization problem objectives. The key to our approach is to identify an operator that commutes with the action of the group of symmetries on the QAOA underlying Hilbert space and meets the essential technical criteria for effective mixer Hamiltonian functionality. We offer a construction method specifically tailored to the symmetric group Sd, prevalent in a variety of combinatorial optimization problems. By rigorously validating the required properties, providing a concrete formula and corresponding quantum circuit for implementation, we establish the viability of the proposed mixer Hamiltonian. Furthermore, we demonstrate that the classical mixer B commutes only with a subgroup of Sd of significantly smaller order than the group itself, enhancing the efficiency of the proposed approach. To evaluate the effectiveness of our methodology, we compare two QAOA variants utilizing different mixer Hamiltonians: conventional B=∑Xi and the newly proposed HM in edge coloring and graph partitioning problems across various graphs. We observe statistically significant differences in mean values, with the new variant consistently demonstrating superior performance across multiple independent simulations. Additionally, we analyze the phenomenon of poor performance in alternative warm-start QAOA variants, providing a conceptual explanation supported by recent literature findings.
Abstract Proposed hybrid algorithms encode a combinatorial cost function into a problem Hamiltonian and optimize its energy by varying over a set of states with low circuit complexity. Classical processing is typically only used for the choice of variational parameters following gradient descent. As a consequence, these approaches are limited by the descriptive power of the associated states. We argue that for certain combinatorial optimization problems, such algorithms can be hybridized further, thus harnessing the power of efficient non-local classical processing. Specifically, we consider combining a quantum variational ansatz with a greedy classical post-processing procedure for the MaxCut-problem on three-regular graphs. We show that the average cut-size produced by this method can be quantified in terms of the energy of a modified problem Hamiltonian. This motivates the consideration of an improved algorithm which variationally optimizes the energy of the modified Hamiltonian. We call this a twisted hybrid algorithm since the additional classical processing step is combined with a different choice of variational parameters. We exemplify the viability of this method using the quantum approximate optimization algorithm (QAOA), giving analytic lower bounds on the expected approximation ratios achieved by twisted QAOA. We observe that for levels p = 1, …, 5, these lower bounds are comparable to the known lower bounds on QAOA at level p + 1 for high-girth graphs. This suggests that using twisted QAOA can reduce the circuit depth by 4 and the number of variational parameters by 2.
Quantum Approximate Optimization Algorithm (QAOA) is a leading candidate algorithm for solving combinatorial optimization problems on quantum computers. However, in many cases QAOA requires computationally intensive parameter optimization. The challenge of parameter optimization is particularly acute in the case of weighted problems, for which the eigenvalues of the phase operator are non-integer and the QAOA energy landscape is not periodic. In this work, we develop parameter setting heuristics for QAOA applied to a general class of weighted problems. First, we derive optimal parameters for QAOA with depth p=1 applied to the weighted MaxCut problem under different assumptions on the weights. In particular, we rigorously prove the conventional wisdom that in the average case the first local optimum near zero gives globally-optimal QAOA parameters. Second, for p≥1 we prove that the QAOA energy landscape for weighted MaxCut approaches that for the unweighted case under a simple rescaling of parameters. Therefore, we can use parameters previously obtained for unweighted MaxCut for weighted problems. Finally, we prove that for p=1 the QAOA objective sharply concentrates around its expectation, which means that our parameter setting rules hold with high probability for a random weighted instance. We numerically validate this approach on general weighted graphs and show that on average the QAOA energy with the proposed fixed parameters is only 1.1 percentage points away from that with optimized parameters. Third, we propose a general heuristic rescaling scheme inspired by the analytical results for weighted MaxCut and demonstrate its effectiveness using QAOA with the XY Hamming-weight-preserving mixer applied to the portfolio optimization problem. Our heuristic improves the convergence of local optimizers, reducing the number of iterations by 7.4x on average.
The Quantum Approximate Optimisation Algorithm (QAOA) is a widely studied quantum-classical iterative heuristic for combinatorial optimisation. While QAOA targets problems in complexity class NP, the classical optimisation procedure required in every iteration is itself known to be NP-hard. Still, advantage over classical approaches is suspected for certain scenarios, but nature and origin of its computational power are not yet satisfactorily understood. By introducing means of efficiently and accurately approximating the QAOA optimisation landscape from solution space structures, we derive a new algorithmic variant of unit-depth QAOA for two-level Hamiltonians (including all problems in NP): Instead of performing an iterative quantum-classical computation for each input instance, our non-iterative method is based on a quantum circuit that is instance-independent, but problem-specific. It matches or outperforms unit-depth QAOA for key combinatorial problems, despite reduced computational effort. Our approach is based on proving a long-standing conjecture regarding instance-independent structures in QAOA. By ensuring generality, we link existing empirical observations on QAOA parameter clustering to established approaches in theoretical computer science, and provide a sound foundation for understanding the link between structural properties of solution spaces and quantum optimisation.