  Quantum computers may provide good solutions to combinatorial optimization
problems by leveraging the Quantum Approximate Optimization Algorithm (QAOA).
The QAOA is often presented as an algorithm for noisy hardware. However,
hardware constraints limit its applicability to problem instances that closely
match the connectivity of the qubits. Furthermore, the QAOA must outpace
classical solvers. Here, we investigate swap strategies to map dense problems
into linear, grid and heavy-hex coupling maps. A line-based swap strategy works
best for linear and two-dimensional grid coupling maps. Heavy-hex coupling maps
require an adaptation of the line swap strategy. By contrast, three-dimensional
grid coupling maps benefit from a different swap strategy. Using known entropic
arguments we find that the required gate fidelity for dense problems lies deep
below the fault-tolerant threshold. We also provide a methodology to reason
about the execution-time of QAOA. Finally, we present a QAOA Qiskit Runtime
program and execute the closed-loop optimization on cloud-based quantum
computers with transpiler settings optimized for QAOA. This work highlights
some obstacles to improve to make QAOA competitive, such as gate fidelity, gate
speed, and the large number of shots needed. The Qiskit Runtime program gives
us a tool to investigate such issues at scale on noisy superconducting qubit
hardware.
