• CommentComments Save ArticleRead LaterRead Later A New Complexity Theory for the Quantum Age February 17, 2026 Traditional complexity theory can’t accommodate problems with quantum inputs and outputs. • Henry Yuen wants to build a new theory that can. • Sasha Maslov forQuanta 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.

Article Summaries:

  • A team led by Columbia professor Henry Yuen is developing a “fully quantum” complexity theory to analyze problems whose inputs and outputs are themselves quantum states, a class largely ignored by traditional complexity theory that assumes classical bit strings. Yuen argues that existing frameworks miss key challenges, such as quantum bit‑commitment protocols used in cryptography, where classical assumptions break down. By extending complexity analysis to inherently quantum data, the new theory aims to clarify when quantum computers truly outperform classical ones and to guide research into quantum cryptography, quantum information processing, and related fields.
  • Researchers in computational complexity have long used classical inputs and outputs to compare the power of quantum and classical computers. However, many problems of interest involve inherently quantum data, a class that traditional theory largely ignores. Columbia University professor Henry Yuen, who helped prove a landmark result in 2020, is spearheading a new “fully quantum” complexity framework to analyze such problems. Yuen’s initiative aims to extend the field beyond classical strings, potentially reshaping our understanding of quantum advantage and informing areas like quantum cryptography. The effort reflects a broader push to broaden complexity theory’s scope in the quantum age.
  • A New Complexity Theory for the Quantum Age 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

Sources: