Abstract
We propose and study Th-QAOA (pronounced Threshold QAOA), a variation of the Quantum Alternating Operator Ansatz (QAOA) that replaces the standard phase separator operator, which encodes the objective function, with a threshold function that returns a value for solutions with an objective value above the threshold and a otherwise. We vary the threshold value to arrive at a quantum optimization algorithm. We focus on a combination with the Grover Mixer operator; the resulting GM-Th-QAOA can be viewed as a generalization of Grover's quantum search algorithm and its minimum/maximum finding cousin to approximate optimization. Our main findings include: (i) we provide intuitive arguments and show empirically that the optimum parameter values of GM-Th-QAOA (angles and threshold value) can be found with iterations of the classical outer loop, where is the number of QAOA rounds and is an upper bound on the solution value (often the number of v