Performance of Parity QAOA for the Signed Max-Cut Problem

Combinatorial optimization is a key area in quantum computing, with the potential to drive significant advancements across various industries. Recently, the Quantum Approximate Optimization Algorithm (QAOA) has gained attention as a promising candidate to showcase quantum advantage, especially on current NISQ devices. 

QAOA is a type of variational quantum algorithm (VQA), which prepares quantum states that approximate solutions to optimization problems using shallow quantum circuits. However, practical implementations of the algorithm on existing NISQ devices face challenges due to limited hardware connectivity and gate error rates. To address these issues, various QAOA variants were introduced, with the goal of reducing the algorithm’s execution times and hardware requirements. 

Among these variants, Parity QAOA (Quantum Approximate Optimization Algorithm based on the ParityQC Architecture) stands out as a solution specifically designed to tackle the qubit connectivity issues found in today’s quantum chips. Traditional implementations of QAOA (“vanilla QAOA”) rely on SWAP-gates and rerouting strategies, which increase the depth of the quantum circuit and reduce the efficiency of the algorithm. These operations are difficult to parallelize and add significant overhead in terms of time and resources. In contrast, Parity QAOA distributes the computational tasks more efficiently across qubits and takes advantage of the planar structure of quantum chips, using only local gates that can be highly parallelized. This makes the algorithm much more hardware-efficient. When applied to common binary optimization problems, Parity QAOA typically requires shallower circuits and in some cases also fewer entangling gates compared to vanilla QAOA. Additionally, the redundancy in Parity QAOA, where information is distributed across multiple qubits, helps to mitigate the impact of gate errors—one of the significant challenges for NISQ devices.

With the paper “Performance of Parity QAOA for the Signed Max-Cut Problem”, a group of physicists from ParityQC and the University of Innsbruck (Anita Weidinger, Glen Bigan Mbeng, Michael Fellner, Davit Khachatryan, and Wolfgang Lechner) set out to perform an in-depth study of Parity QAOA to evaluate its advantages and disadvantages compared to vanilla QAOA. Parity QAOA and vanilla QAOA are compared by analyzing their performances on the signed Max-Cut problem, a complex optimization problem that includes the Sherrington-Kirkpatrick (SK) spin-glass model as a special case.

The findings reveal that Parity QAOA consistently outperforms vanilla QAOA when the circuit depth is fixed and an appropriate objective function is used. Addressing the fact that Parity QAOA’s planar structure can sometimes limit the spread of correlations between qubits (which can affect the algorithm’s efficiency in certain cases) the authors introduce Parity Recursive QAOA (RQAOA). This variant is shown to improve the algorithm’s performance by overcoming the limitations of local geometry, similar to how recursive methods enhance vanilla QAOA.

Publication:

• Anita Weidinger, Glen Bigan Mbeng, Michael Fellner, Davit Khachatryan, Wolfgang Lechner. Performance of Parity QAOA for the Signed Max-Cut Problem. arXiv:2409.14786 (2024)