Max-Cut Problem: Effect of depth on the Quantum Approximate Optimization Algorithm

Compared to classical technologies, quantum technologies demonstrate tremendous potential for providing computational advantages in various fields. We investigate the effect of the depth of the circuit on the performance of the Quantum Approximate Optimization Algorithm (QAOA). The QAOA algorithm, a hybrid quantum-classical variational algorithm, is intended to provide a quantum advantage in finding approximate solutions to combinatorial optimization problems. It has demonstrated capability in computing graph partitions with maximum separations between edges, also known as maximum cuts (max-cut). The max-cut problem belongs to the class of nondeterministic polynomial (NP) combinatorial optimization problems. To solve this problem, we define the cost function and translate it to the Hamiltonian of the system by substituting the bitstrings as Pauli Operators. In order to simulate the experiment, an ideal simulator and a noisy simulator were used, which modeled thermal relaxation errors, and the results were compared with a table of the values for the cuts which had been performed in a conventional manner. Our results demonstrate that increasing depth does not increase the average cut value in either simulator. Furthermore, the noisy simulator generally produces a lower cut value than the noiseless simulator.