PIRSA: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. https://pirsa.org/23020034

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

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

Cole Coughlin

Perimeter Institute for Theoretical Physics

Talk number
PIRSA:23020034
Collection
Talk Type
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