A New Complexity Theory for the Quantum Age
Traditional complexity theory can’t accommodate problems with quantum inputs and outputs. Henry Yuen wants to build a new theory that can.
Sasha Maslov for Quanta Magazine
Introduction
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?
Yuen originally went into computer science because he wanted to design video games. “Looking back, I couldn’t have predicted any of the twists and turns that my interests have taken,” he said.
Sasha Maslov for Quanta Magazine
Can you give an example of a problem that’s hard to understand because of quantum inputs or outputs?
There’s a technique in cryptography called bit commitment, which is analogous to putting a message in a sealed envelope. This preserves the privacy of the message until it’s time to reveal it, and it also prevents you from changing the message once it’s inside. You could use a scheme like this to put in a bid for an auction or cast a secret vote.
Classical bit commitment schemes are essential building blocks for all sorts of other methods in cryptography. But they all rely on the assumption that certain mathematical problems are intrinsically hard. If you somehow had the power to solve these famously hard problems, you could break any bit commitment scheme.
Now imagine your envelopes are quantum. In that case, even if you had that same amazing computational power, it’s not clear how you could use it to break these quantum envelopes.
Because breaking the bit commitment scheme is now a quantum-input problem?
That’s right. The problem seems less mathematical and more physical. Somehow, having exorbitant classical computing power does not necessarily translate into exorbitant quantum processing power. This is a hint that maybe these two worlds of computational tasks might be intrinsically different. In my opinion, the biggest open problem in this area is: What is the logical relationship between the two worlds?
Yuen discusses a problem in quantum complexity theory with two graduate students.
Sasha Maslov for Quanta Magazine
What do you mean by that?
Suppose we knew everything there was to be known about traditional complexity theory. Would that tell us all the relationships between problems in fully quantum complexity theory? Maybe all of our understanding could just be easily ported over. But it’s possible that fully quantum complexity theory is logically independent of traditional complexity.
This question has a beautiful formulation called the unitary synthesis problem. If I had access to an infinitely powerful classical oracle — a hypothetical device that could instantly solve any classical-input problem — could I use it to efficiently perform any quantum state transformation of my choice? If the answer is no, that would mean these quantum-input, quantum-output problems are of an intrinsically different nature than classical ones. There was a bit of progress on this problem a few years ago, but the full question is still wide open.
You’ve taken some initial steps toward building a new theory. What have you discovered so far?
This is a project that my collaborators and I initiated a few years ago: To map out what this new world looks like, and how these quantum-input problems are related to each other. We found that one problem just showed up again and again in many different places.
In a recent paper, Yuen and his colleagues showed that many seemingly unrelated quantum problems are actually equivalent.
Sasha Maslov for Quanta Magazine
It comes from a very fundamental result in quantum information theory called Uhlmann’s theorem. Let’s say you have two quantum particles that are entangled, meaning they share a quantum state, and there are two possibilities for that shared state. Quantum mechanics says it’s always possible to do some operations on both particles that transform the first state into the second state. But what if I restrict you to only acting on one particle — can you still transform the first state into the second state? If not, then what is the closest that you can get? Uhlmann’s theorem exactly quantifies the best that you can do for any pair of entangled states. It’s very important in quantum communication, quantum complexity, quantum cryptography, and beyond.
What we did was view the theorem as a quantum-input, quantum-output problem, where your goal is to transform one state into the other by only acting locally on one of the particles. So how hard is that problem? What resources do you need to solve it? Is it equivalent in hardness to other problems that we care about?
We showed that there are actually a bunch of natural problems that are exactly equivalent in complexity. One example is the computational problem of decoding the Hawking radiation of a black hole. This is a quantum-input problem, because you’re scooping in and analyzing all these entangled particles. And it turns out that it’s just the Uhlmann transformation problem in disguise. The Uhlmann transformation is the hub from which all these other things radiate: bit commitments, black hole decoding, compressing quantum information, and more.
In 2020, Yuen helped prove a milestone result about the computational power of quantum entanglement.
Sasha Maslov for Quanta Magazine
Your family background isn’t exactly typical for an academic researcher. Can you tell me the story of how your parents made it to the U.S.?
My parents grew up in Cambodia in the 1970s, when the Khmer Rouge took over the country and forced millions of people into labor camps. My mom’s family got swept into these camps, doing slave labor for three or four years, before they managed to escape. They spent months crossing mountains and land mine–filled fields. My dad’s family was somewhat more fortunate — they saw the warning signs and fled the country earlier. Eventually they managed to come to the U.S., and they ran a restaurant, where my brother and I worked until we left for school.
Hearing their stories as a child obviously made a huge impression on me.
I get to enjoy this privilege of thinking about mathematics and quantum physics, and work with others who are interested in these extremely niche and insanely obscure topics. It’s so far removed from what they had to go through.
So how did you get interested in those extremely niche topics?
When I went to college, I planned to major in both physics and computer science — physics I just found conceptually interesting, computer science because of my high school interest in video game design. I quickly dropped physics because I was very bad at the labs. Then in 2007 or 2008 I discovered Scott Aaronson’s blog, where he wrote about quantum computing and theoretical computer science. I was like, “This is amazing. I want to study this.” That planted the seed, but the biggest formative experience for me was doing undergraduate research with Len Adleman. His mantra was: “We’re going to ignore everything that people have done for 100 years. We’re going to take a left turn where everyone took a right turn.” It felt like we were mavericks, doing something a bit rebellious.
Your current research program is a bit like that too. How does it differ from working within an established theoretical framework?
It’s a very different exercise from what I’m used to. No one hands you a theorem and says, “Here, prove it.” We don’t even necessarily know what the right questions are. But finding the right language is really important, even if you don’t prove anything really technical. Not having the right language actually prevents you from thinking clearly.
