Quantum Approximate Optimization with Parallelizable Gates. (arXiv:1802.01157v1 [quant-ph])

The quantum approximate optimization algorithm (QAOA) has been recently
introduced as a heuristic digital quantum computing scheme to solve
combinatorial optimization problems with shallow circuits. We present a scheme
to parallelize this approach for arbitrary all-to-all connected problem graphs
in a layout of quantum bits (qubits) with nearest neighbor interactions. The
optimization protocol consisting of single qubit operations that encode the
optimization problem while all interactions are problem-independent pair-wise
CNOT gates among nearest neighbors. This allows for a parallelizable
implementation in quantum devices with a square lattice geometry. The basis of
this proposal is a lattice gauge model which also introduces additional
parameters and protocols for QAOA to improve the efficiency.

Article web page: