Events News

QSEC Quantum Computing Seminar Series: 10/27/2020

12 pm, October 27, 2020
Speaker: Professor Fei Li, GMU Department of Computer Science

Topic: Algorithmic Approaches to the MAX-CUT Problem

Location: Zoom

QSEC’s quantum computing subgroup will organize and host a seminar series throughout the upcoming semester.  These events are free and open to the public. For any questions, contact

The upcoming seminar on Tuesday October 27 will be given by Professor Fei Li of GMU Computer Science. Below is the abstract of the talk and meeting information:

Title: Algorithmic Approaches to the MAX-CUT Problem


In this talk, I am going to present three approximation algorithms to deal with the NP-hard problem MAX-CUT. The first one is a 0.5-approximation randomized algorithm, which can be de-randomized to be a deterministic one with the same performance. The second approximation algorithm is also a randomized algorithm and it has an approximation ratio 0.878. The third algorithm is a quantum approximation optimization algorithm (QAOA) with an approximation ratio 0.6942 on 3-regular graphs. In this talk, I will compare these algorithmic approaches. I will also discuss the inapproximability and some of my thoughts on solving MAX-CUT.

Meeting Information
Join Zoom Meeting ID:934 6880 2063