A New Complexity Theory for the Quantum Age

Computer science, at its most fundamental, is all about inputs and outputs. Consider the simple case of multiplying two numbers on a pocket calculator. You punch in some inputs — the specific numbers you want to multiply — and the screen displays an output representing their product. The reverse problem of breaking a number into its prime factors can be much harder, but it has the same basic structure. Solving a problem on a computer always boils down to transforming numerical inputs, usually written as strings of 0s and 1s, into outputs.

Researchers in the field of computational complexity theory study why some of these transformations are harder to implement than others. They’ve discovered that certain tasks that ordinary “classical” computers struggle with, like the prime factor problem, are much easier for computers that exploit the laws of quantum physics.

For over 30 years, complexity theorists have used this theoretical framework to identify problems where quantum computers surpass classical ones. But there’s a broader class of problems that they’ve barely begun to study, whose inputs and outputs aren’t ordinary strings of bits. These are the problems that most interest the complexity theorist Henry Yuen. How do you make sense of problems whose inputs and outputs are themselves inherently quantum?

“Traditional complexity theory is just silent on this,” Yuen said. “Maybe we need a separate theory to understand this other class of problems.”

Yuen, a professor at Columbia University who co-authored a landmark proof in traditional complexity theory in 2020, is now leading an ambitious effort to build a new “fully quantum” theory that can accommodate these unusual inputs and outputs.

His own life speaks to what’s possible with atypical inputs. Born in 1989, he grew up working in his family’s Southern California restaurant, the son of refugees from rural Cambodia who had fled genocide in the 1970s. He learned computer programming because he wanted to design video games. That early interest led him to major in computer science in college, where he grew fascinated by the theoretical foundations of quantum computing.

Quanta spoke with Yuen about where complexity theory falls short, what quantum cryptography has to do with black holes, and the importance of open-ended research. The interview has been condensed and edited for clarity.

Researchers have studied the power of quantum computers using traditional complexity theory for decades. What does this approach miss?

In traditional complexity theory, the inputs and outputs are always classical. What happens in between is up to you. You can try to use a classical computer to solve your problem, or you can use a quantum computer, and we’re hoping that quantum computers will be better at some problems. But why do inputs and outputs have to be classical?