Abstract
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 V 1 and V 2 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, O(√2 n/r) and O(m 2). 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.
Original language | English |
---|---|
Pages (from-to) | 499-506 |
Number of pages | 8 |
Journal | IEEE Transactions on Nanobioscience |
Volume | 23 |
Issue number | 3 |
Early online date | 30 04 2024 |
DOIs | |
State | Published - 30 04 2024 |
Bibliographical note
Publisher Copyright:© 2002-2011 IEEE.
Keywords
- Approximation algorithms
- Electron tubes
- Partitioning algorithms
- Physics
- Quantum algorithm
- Qubit
- Registers
- data structures and algorithms
- quantum algorithms
- quantum computing
- quantum speedup
- the maximum cut problem
- Computational Biology/methods
- Quantum Theory
- Algorithms
- Computer Simulation
- Data structures and algorithms