Depth Optimized Ansatz Circuit in QAOA for Max-Cut

Abstract

While a Quantum Approximate Optimization Algorithm (QAOA) is intended to provide a quantum advantage in finding approximate solutions to combinatorial optimization problems, noise in the system is a hurdle in exploiting its full potential. Several error mitigation techniques have been studied to lessen the effect of noise on this algorithm. Recently, Majumdar et al. proposed a Depth First Search (DFS) based method to reduce $n-1$ CNOT gates in the ansatz design of QAOA for finding Max-Cut in a graph G = (V, E), |V| = n. However, this method tends to increase the depth of the circuit, making it more prone to relaxation error. The depth of the circuit is proportional to the height of the DFS tree, which can be $n-1$ in the worst case. In this paper, we propose an $O(\Delta \cdot n^2)$ greedy heuristic algorithm, where $\Delta$ is the maximum degree of the graph, that finds a spanning tree of lower height, thus reducing the overall depth of the circuit while still retaining the $n-1$ reduction in the number of CNOT gates needed in the ansatz. We numerically show that this algorithm achieves nearly 10 times increase in the probability of success for each iteration of QAOA for Max-Cut. We further show that although the average depth of the circuit produced by this heuristic algorithm still grows linearly with n, our algorithm reduces the slope of the linear increase from 1 to 0.11.

arXiv comment12 pages, single column

References in corpus (6)

• A Quantum Approximate Optimization Algorithm
• QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
• Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem
• Measurement Error Mitigation for Variational Quantum Algorithms
• Quantum Approximate Optimization Algorithm with Adaptive Bias Fields
• Optimizing Ansatz Design in QAOA for Max-cut