## Video URL

https://pirsa.org/23020034# New Quantum Algorithm for NP-Complete problems: Efficiency to be determined

### APA

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

### MLA

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

### BibTex

@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

**Source Repository**PIRSA

**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