  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 $1$ for solutions with an objective value above
the threshold and a $0$ 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 $O(\log(p) \times \log M)$
iterations of the classical outer loop, where $p$ is the number of QAOA rounds
and $M$ is an upper bound on the solution value (often the number of vertices
or edges in an input graph), thus eliminating the notorious outer-loop
parameter finding issue of other QAOA algorithms; (ii) GM-Th-QAOA can be
simulated classically with little effort up to 100 qubits through a set of
tricks that cut down memory requirements; (iii) somewhat surprisingly,
GM-Th-QAOA outperforms non-thresholded GM-QAOA in terms of approximation ratios
achieved. This third result holds across a range of optimization problems
(MaxCut, Max k-VertexCover, Max k-DensestSubgraph, MaxBisection) and various
experimental design parameters, such as different input edge densities and
constraint sizes.
