Max-Cut Problem Implementation and Analysis on a Quantum Computer

Advances in integrated circuit complexity are enabled by electronic design automation (EDA) tool developments. The field of EDA has many combinatorial optimisation problems that are NP-hard in nature. The complexity of these problems means that they are almost always computationally intractable and expensive to solve on classical computers for large problem instances. Heuristics are often used, and due to computation timing constraints, the results do not guarantee the optimal solution. This paper implements and analyses an instance of the max-cut problem, which is evaluated on IBM quantum computers as well as quantum simulators. As quantum computers are highly prone to noise, this paper also analyses quantum circuit noise and connectivity, proposing some ways to obtain reliable results on real quantum computers through experiments carried out in Qiskit.