New Quantum Algorithm for NP-Complete problems: Efficiency to be determined

PIRSA ID: 23020034
Event Type: Seminar
Scientific Area(s):
End date:

Quantum algorithms have been found which are able to solve important problems exponentially faster than any known classical algorithm. The most well known example is Shor's algorithm which would be able to break all RSA encryption if fault tolerant quantum computers existed for it to be run on. It is currently not believed that quantum computers will be able to efficiently solve NP-Complete problems, but the answer is still unknown. I present a novel quantum algorithm which is able to solve 3-SAT along with numerical simulations to see how it performs on small instances, but new methods of analyzing the complexity of quantum algorithms will need to be developed before we can say exactly how it performs. This will be the goal of my PSI essay.

Zoom Link: