Bioinspired Quantum Oracle Circuits for Biomolecular Solutions of the Maximum Cut Problem

Given an undirected, unweighted graph with n vertices and m edges, the maximum cut problem is to find a partition of the n vertices into disjoint subsets V1 and V2 such that the number of edges between them is as large as possible. Classically, it is an NP-complete problem, which has potential applications ranging from circuit layout design, statistical physics, computer vision, machine learning and network science to clustering. In this paper, we propose a biomolecular and a quantum algorithm to solve the maximum cut problem for any graph G. The quantum algorithm is inspired by the biomolecular algorithm and has a quadratic speedup over its classical counterparts, where the temporal and spatial complexities are reduced to, respectively, <m:math xmlns:m="http://www.w3.org/1998/Math/MathML" alttext="O(√{2ⁿ/r})" display="inline"><m:mrow><m:mi>O</m:mi><m:mo stretchy="false">(</m:mo><m:msqrt><m:mrow><m:mn>2</m:mn><m:msup><m:mi/><m:mi>n</m:mi></m:msup><m:mo>/</m:mo><m:mi>r</m:mi></m:mrow></m:msqrt><m:mo stretchy="false">)</m:mo></m:mrow></m:math> and <m:math xmlns:m="http://www.w3.org/1998/Math/MathML" alttext="O(m²)" display="inline"><m:mrow><m:mi>O</m:mi><m:mo stretchy="false">(</m:mo><m:mi>m</m:mi><m:msup><m:mi/><m:mn>2</m:mn></m:msup><m:mo stretchy="false">)</m:mo></m:mrow></m:math> . With respect to oracle-related quantum algorithms for NP-complete problems, we identify our algorithm as optimal. Furthermore, to justify the feasibility of the proposed algorithm, we successfully solve a typical maximum cut problem for a graph with three vertices and two edges by carrying out experiments on IBM’s quantum simulator.