Key points are not available for this paper at this time.
The quantum approximate optimization algorithm (QAOA) is a promising algorithm for solving combinatorial optimization problems (COPs). In this algorithm, there are alternating layers consisting of a mixer and a problem Hamiltonian. Each layer i=0, , p-1 is parameterized by ᵢ and ᵢ. How to find these parameters has been an open question with the majority of the research focused on finding them using classical algorithms. In this work, we present evidence that fixed linear ramp schedules constitute a universal set of QAOA parameters, i. e. , a set of and parameters that rapidly approximate the optimal solution, x^*, independently of the COP selected, and that the success probability of finding it, probability (x^*), increases with the number of QAOA layers p. We simulate linear ramp QAOA protocols (LR-QAOA) involving up to Nq=42 qubits and p = 400 layers on random instances of 9 different COPs. The results suggest that probability (x^*) 1/2^ (Nq / p) for a constant. For example, when implementing LR-QAOA with p=42, the probability (x^*) for 42-qubit Weighted MaxCut problems (W-MaxCut) increases from 2/2^42 10^-13 to an average of 0. 13. We compare LR-QAOA, simulated annealing (SA), and branch-and-bound (B\&B) finding a fundamental improvement in LR-QAOA. We test LR-QAOA on real hardware using IonQ Aria, Quantinuum H2-1, IBM Brisbane, IBM Kyoto, and IBM Osaka, encoding random weighted MaxCut (W-MaxCut) problems from 5 to 109 qubits and p=3 to 100. Even for the largest case, Nq=109 qubits and p=100, information about the LR-QAOA optimization protocol is present. The circuit involved requires 21200 CNOT gates. These results show that LR-QAOA effectively finds high-quality solutions for COPs and suggests an advantage of quantum computation for combinatorial optimization in the near future.
Montanez-Barrera et al. (Wed,) studied this question.