Optimized QAOA ansatz design for two-body Hamiltonian problems

Abstract

Quantum Approximate Optimization Algorithm (QAOA) is a probable candidate for providing quantum advantage in finding approximate solutions to optimization problems using near-term quantum devices. In this paper, first we show a generalized QAOA formulation for any Hamiltonian that involves upto two-body interactions. Such a Hamiltonian can be represented as a graph, and if the graph has n vertices and m edges then the circuit realization of the depth-p QAOA requires 2mp CNOT gates. In current quantum computers CNOT is one of the primary sources of error. We propose a heuristic algorithm which can eliminate n-1 CNOTs from the QAOA ansatz while retaining functional equivalence with the original circuit. This improves upon previously proposed Depth First Search (DFS) method by restricting the increase in depth of the circuit, which was a drawback of the method, by ~84.8% for Erdos-Renyi graphs. Finally, if the underlying connectivity and the initial qubit placement for a hardware is known, then we show that the greedy heuristic method can be tweaked to give higher preference to add those edges to the rooted spanning tree which respect the underlying hardware coupling map, thus resulting in a circuit with ~5% fewer SWAP gates for Erdos-Renyi graphs.