Physics Seminar: Computational Complexity and Quantum Algorithms

Physics Seminar: Computational Complexity and Quantum Algorithms

Dr. Larry Merkle, AFIT

Abstract: Computational complexity studies the computational resources (e.g., time and space) required to solve decision problems in relation to the size of the problem instance. Perhaps the best-known complexity classes are P and NP, which include those problems that can be solved in polynomial time by Turing machines of the deterministic and nondeterministic varieties, respectively. Assuming these classes are distinct, as all evidence suggests, would imply that for many problems of practical importance, the time requirements for the best classical algorithms available grow exponentially as a function of instance size. However, there is reason to believe that at least some such problems may be amenable to polynomial-time quantum algorithms.

When: Sept. 15, 2023

Time: 2:30 PM to 4:00 PM

Where: 112 Oelman Hall