SAT Solvers and Quantum Computing: Potential and Challenges

Robert Wille

Technical University of Munich, Germany

Software Competence Center Hagenberg, Austria

Abstract:

SAT or SMT solvers are well-established in conventional computing where they are used to solve a broad variety of problems, e.g., in the design of circuits and systems. With the emerging of quantum computers, it is natural to wonder whether the prospects of SAT-based solutions can also be materialized for this emerging technology. For one thing, many of the design tasks for quantum computing have been proven to be NP-hard—a class of problems for which SAT solvers are rather suited. Then again, quantum computing deals with quantum-mechanical concepts such as superposition and entanglement—easily rendering SAT unfeasible at a first glance. In this talk, we are investigating whether SAT solvers and quantum computing harbor potential; and, if so, what are the challenges in fully exploiting them.

Short Bio:

Robert Wille is a Full and Distinguished Professor at the Technical University of Munich, Germany, and Chief Scientific Officer at the Software Competence Center Hagenberg, Austria. He received the Diploma and Dr.-Ing. degrees in Computer Science from the University of Bremen, Germany, in 2006 and 2009, respectively. Since then, he worked at the University of Bremen, the German Research Center for Artificial Intelligence (DFKI), the University of Applied Science of Bremen, the University of Potsdam, and the Technical University Dresden. From 2015 until 2022, he was a Full Professor at the Johannes Kepler University Linz, Austria, until he moved to Munich. His research interests are in the design of circuits and systems for both conventional and emerging technologies. In these areas, he published more than 400 papers and served on editorial boards as well as program committees of numerous journals/conferences such as TCAD, ASP-DAC, DAC, DATE, and ICCAD. For his research, he was awarded, e.g., with Best Paper Awards, e.g., at TCAD and ICCAD, an ERC Consolidator Grant, a Distinguished and a Lighthouse Professor appointment, a Google Research Award, and more.