The project aims to measure the computational difficulty of determining various aspects of physical systems--?quantum mechanical systems in particular. One such computational task, of interest to physical chemists, is to distinguish the minimum-energy configuration of a system of nuclear spins. No efficient algorithm running on a traditional computer is known to solve this or similar problems.
Quantum computers are devices that directly harness the laws of quantum mechanics to do computation. Although not yet implemented at a large scale, they hold great promise in speeding up certain computations, including efficiently simulating actual physical systems. Yet several interesting questions about physical systems appear beyond the reach of even quantum computers. The project will investigate problems of this sort, using techniques from theoretical computer science to help determine their intrinsic quantum computational difficulty. Showing that some of these questions are difficult for a quantum computer will help guide scientists and engineers toward more practical, less ambitious approaches.
More broadly, the project will build on previous work of the Principal Investigator and colleagues to better understand the power of quantum information processing in general and how it relates to traditional information processing.
