Solving Unsolvable Problems: Taming Infinity with Quantum Measurements

According to Alan Turing, some problems cannot be solved in a finite amount of time. Turing described one such problem, the Halting Problem, in a landmark 1936 paper. Since then, dozens of problems have been shown to be unsolvable, including the problem of deciding whether certain equations can be solved using integers and even some air travel planning problems. A program to solve any of these might require infinitely many steps to run, so no known computer (not even quantum computers) can solve such problems.

In 2015, three physicists studied the problem of computing a system's spectral gap -- the least possible energy difference between a system's ground state and its excited state. They showed that certain spectral gap problems are unsolvable. That is, solving such problems would require infinitely many steps. This opens both interesting questions and interesting possibilities.

On a philosophical level, we may wonder what feature of nature allows it to do infinite-step calculations. On a more practical level, we can consider ways to convert hard problems into not-so-hard problems. Think about the Karate Kid trying to learn how to block punches. Instead of practicing punch-blocking, he practices car-waxing.

Physicists can't compute every system's spectral gap. But when they encounter a physical system, they know how to measure its spectral gap. So, if we start with the air travel problem, we might be able to create a quantum-mechanical system whose gap mimics the travel problem's structure and then measure that system's gap.

In this talk, Dr. Burd will discuss some of the details of Turing's original result and provide insight into the workings of the spectral gap problem.

Bio: Dr.Barry Burd received a Ph.D. in Mathematics at the University of Illinois. He teaches Quantum Computing in his role as a Professor of Mathematics and Computer Science at Drew University in Madison, New Jersey. He's the author of eleven books on technical topics such as Java programming and mobile application development. He's honored to have been named a Java Champion.