PIRSA:23020034

Video URL

https://pirsa.org/23020034

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

Coughlin, C. (2023). New Quantum Algorithm for NP-Complete problems: Efficiency to be determined. Perimeter Institute for Theoretical Physics. https://pirsa.org/23020034

Coughlin, Cole. New Quantum Algorithm for NP-Complete problems: Efficiency to be determined. Perimeter Institute for Theoretical Physics, Feb. 06, 2023, https://pirsa.org/23020034 

          @misc{ scivideos_PIRSA:23020034,
            doi = {10.48660/23020034},
            url = {https://pirsa.org/23020034},
            author = {Coughlin, Cole},
            keywords = {Other Physics},
            language = {en},
            title = {New Quantum Algorithm for NP-Complete problems: Efficiency to be determined},
            publisher = {Perimeter Institute for Theoretical Physics},
            year = {2023},
            month = {feb},
            note = {PIRSA:23020034 see, \url{https://scivideos.org/pirsa/23020034}}
          }

Cole Coughlin Perimeter Institute for Theoretical Physics

Talk numberPIRSA:23020034
DOI10.48660/23020034
Source RepositoryPIRSA
Collection
Talk Type Scientific Series
Subject

Abstract

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: https://pitp.zoom.us/j/95795655548?pwd=aU5jNFhFZHEzUWpLK1FvWjd2Q1c2Zz09