If I ask you what comes to mind when you think of physics, what would you answer?

When I was an undergraduate, I did my best to stay away from a computer to do physics. I saw myself as a theorist, and in my head, a good theorist could get everything they wanted done with pencil and paper. I remember one particularly vivid time that I used a computer algebra system to calculate Riemann tensors for my research in gravitation theory, and I hated dealing with the complexity of the program. It wasn’t easy to work with, the answers were often garbled and not simplified, and it almost felt like I was wasting more time using a computer.

As a quantum theorist, my job is to study quantum systems and understand their inner workings. However, since I’m a theoretical physicist and not a experimental physicist, most of my “experiments” come in the form of simulations. My laboratory is my computer, and this means writing numerical experiments.

But wait a second, you tell me. Isn’t the whole point of quantum computers to do things that our regular computers can’t? And aren’t there issues with exponential memory?

These are both very good questions, and we’ll dive into them below. But in short: Yes, these are issues that limit the experiments I can do. And it’s a reason I’d like to get my hands on a good, error-correcting quantum computer!

If condensed matter theorists have the Ising model, gravitational physicists have the Schwarzschild solution, and quantum foundation theorists have the Bell inequalities, then theoretical computer scientists have satisfiability, or SAT. In the world of computer science (and particularly computational complexity), many discussions inevitably circle back to SAT. In fact, SAT isn’t just something that theoretical computer scientists study. Satisfiability has a rich history with statistical physics, a field which wields powerful tools to probe the properties of SAT. As such, SAT is a problem which touches several fields, which makes it a breeding ground for cross-disciplinary ideas.