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 \u2014 the specific numbers you want to multiply \u2014 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.<\/p>\n
Researchers in the field of computational complexity theory study why some of these transformations are harder to implement than others. They\u2019ve discovered that certain tasks that ordinary \u201cclassical\u201d computers struggle with, like the prime factor problem, are much easier for computers that exploit the laws of quantum physics.<\/p>\n
For over 30 years, complexity theorists have used this theoretical framework to identify problems where quantum computers surpass classical ones. But there\u2019s a broader class of problems that they\u2019ve barely begun to study, whose inputs and outputs aren\u2019t ordinary strings of bits. These are the problems that most interest the complexity theorist Henry Yuen<\/a>. How do you make sense of problems whose inputs and outputs are themselves inherently quantum?<\/p>\n \u201cTraditional complexity theory is just silent on this,\u201d Yuen said. \u201cMaybe we need a separate theory to understand this other class of problems.\u201d<\/p>\n