Henry Yuen is developing a new mathematical language to describe problems whose inputs and outputs aren’t ordinary numbers.

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(opens a new tab). 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.”

...read more at quantamagazine.org