A parallelizable QAOA with local-only interactions
20/09/2022
Recent developments in quantum technologies bring quantum advantage within reach, and there is a great focus on how to use quantum devices to solve optimization problems that can’t be mastered with a classical computer.
One promising algorithm for the near future is the Quantum Approximate Optimization Algorithm (QAOA). It has been introduced in 2014 by Farhi, Goldstone and Gutmann as a digital quantum computing scheme to find approximate solutions of combinatorial optimization problems. The scheme of QAOA consists of a sequence of quantum gates represented by unitary operators that correspond to a driver Hamiltonian and the problem Hamiltonian, respectively. The number of iterations can be small and angles of each unitary are free parameters that are optimized via a classical feedback loop.
The biggest challenges in the implementation of QAOA are programmability and scalability. It is difficult to program arbitrary optimization problems independently from the qubits’ arrangement and connectivity. While larger connectivity can be achieved through a series of swap operations, these operations are problem-dependent and thus difficult to parallelize, which is a limiting factor in scalability and execution speed.
In the paper “Quantum Approximate Optimization With Parallelizable Gates”, ParityQC co-founder Wolfgang Lechner presents a novel approach to QAOA: a parallelizable QAOA consisting only of nearest-neighbor CNOT gates and single qubit rotations. Implementing the ParityQC Architecture is what makes the difference in this approach. In the ParityQC Architecture, the optimization problem is fully determined by local fields, and interactions between qubits are uniform and problem-independent. Hence, it is possible to solve optimization problems using the same chip just by adjusting the applied local fields.
When implementing QAOA on the ParityQC Architecture, the protocol consists of single qubit operations that encode the optimization problem, and problem-independent pairwise CNOT gates with nearest neighbor connectivity, executed in parallel. This allows for a parallelized implementation in quantum devices with a planar lattice geometry. The required gates, in turn, consist of three terms: 1) a unitary with local σx terms; 2) a unitary that defines the problem with local σzterms; and 3) problem-independent interactions consisting of nearest-neighbor CNOT gates and qubit Z-rotations.
This novel approach to QAOA, one of the most well-known schemes in the field of quantum computing, makes it possible to overcome many obstacles that are ingrained in the hardware.
The paper was published in October 2020 in IEEE Transactions on Quantum Engineering