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
