Quantum approximate optimization algorithm with random and subgraph phase operators

Abstract

The quantum approximate optimization algorithm (QAOA) is a promising quantum algorithm that can be used to approximately solve combinatorial optimization problems. The usual QAOA ansatz consists of an alternating application of the cost and mixer Hamiltonians. In this work, we study how using Hamiltonians other than the usual cost Hamiltonian, dubbed custom phase operators, can affect the performance of QAOA. We derive an expected value formula for QAOA with custom phase operators at $p=1$ and show numerically that some of these custom phase operators can achieve higher approximation ratio than the original algorithm implementation. Out of all the graphs tested at $p=1$, 0.036\% of the random custom phase operators, 75.9\% of the subgraph custom phase operators, 95.1\% of the triangle-removed custom phase operators, and 93.9\% of the maximal degree edge-removed custom phase operators have a higher approximation ratio than the original QAOA implementation. Furthermore, we numerically simulate these phase operators for $p=2$ and $p=3$ levels of QAOA and find that there exist a large number of subgraph, triangle-removed, and maximal degree edge-removed custom phase operators that have a higher approximation ratio than QAOA at the same depth. These findings open up the question of whether better phase operators can be designed to further improve the performance of QAOA.

References in corpus (12)

• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
• QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
• $XY$-mixers: analytical and numerical results for QAOA
• MAXCUT QAOA performance guarantees for p >1
• Expectation Values from the Single-Layer Quantum Approximate Optimization Algorithm on Ising Problems
• Large-scale quantum approximate optimization on non-planar graphs with machine learning noise mitigation
• An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation
• Training variational quantum algorithms with random gate activation
• Quantum Dropout: On and Over the Hardness of Quantum Approximate Optimization Algorithm
• Performance Analysis of Multi-Angle QAOA for p > 1

Cited by in corpus (2)

• Improving Quantum Approximate Optimization by Noise-Directed Adaptive Remapping
• Efficient Sparse State Preparation via Quantum Walks