  Because noisy, intermediate-scale quantum (NISQ) machines accumulate errors
quickly, we need new approaches to designing NISQ-aware algorithms and
assessing their performance. Algorithms with characteristics that appear less
desirable under ideal circumstances, such as lower success probability, may in
fact outperform their ideal counterparts on existing hardware. We propose an
adaptation of Grover's algorithm, subdividing the phase flip into segments to
replace a digital counter and complex phase flip decision logic. We applied
this approach to obtaining the best solution of the MAX-CUT problem in sparse
graphs, utilizing multi-control, Toffoli-like gates with residual phase shifts.
We implemented this algorithm on IBM Q processors and succeeded in solving a
5-node MAX-CUT problem, demonstrating amplitude amplification on four qubits.
This approach will be useful for a range of problems, and may shorten the time
to reaching quantum advantage.
