  The quantum approximate optimization algorithm (QAOA) is an approach for
near-term quantum computers to potentially demonstrate computational advantage
in solving combinatorial optimization problems. However, the viability of the
QAOA depends on how its performance and resource requirements scale with
problem size and complexity for realistic hardware implementations. Here, we
quantify scaling of the expected resource requirements by synthesizing
optimized circuits for hardware architectures with varying levels of
connectivity. Assuming noisy gate operations, we estimate the number of
measurements needed to sample the output of the idealized QAOA circuit with
high probability. We show the number of measurements, and hence total time to
solution, grows exponentially in problem size and problem graph degree as well
as depth of the QAOA ansatz, gate infidelities, and inverse hardware graph
degree. These problems may be alleviated by increasing hardware connectivity or
by recently proposed modifications to the QAOA that achieve higher performance
with fewer circuit layers.

Quantum Physics