  Gate model quantum computers with too many qubits to be simulated by
available classical computers are about to arrive. We present a strategy for
programming these devices without error correction or compilation. This means
that the number of logical qubits is the same as the number of qubits on the
device. The hardware determines which pairs of qubits can be addressed by
unitary operators. The goal is to build quantum states that solve computational
problems such as maximizing a combinatorial objective function or minimizing a
Hamiltonian. These problems may not fit naturally on the physical layout of the
qubits. Our algorithms use a sequence of parameterized unitaries that sit on
the qubit layout to produce quantum states depending on those parameters.
Measurements of the objective function (or Hamiltonian) guide the choice of new
parameters with the goal of moving the objective function up (or lowering the
energy). As an example we consider finding approximate solutions to MaxCut on
3-regular graphs whereas the hardware is physical qubits laid out on a
rectangular grid. We prove that the lowest depth version of the Quantum
Approximate Optimization Algorithm will achieve an approximation ratio of at
least 0.5293 on all large enough instances which beats random guessing (0.5).
We open up the algorithm to have different parameters for each single qubit $X$
rotation and for each $ZZ$ interaction associated with the nearest neighbor
interactions on the grid. Small numerical experiments indicate that an
enveloping classical algorithm can be used to find the parameters which sit on
the grid to optimize an objective function with a different connectivity. We
discuss strategies for finding good parameters but offer no evidence yet that
the proposed approach can beat the best classical algorithms. Ultimately the
strength of this approach will be determined by running on actual hardware.
