内容来源：https://www.quantamagazine.org/a-new-complexity-theory-for-the-quantum-age-20260217/

内容总结：

量子计算新前沿：理论物理学家构建“全量子”复杂性理论框架

传统计算复杂性理论主要研究经典计算机（输入输出均为0/1比特串）解决问题的难度差异，并发现量子计算机在因数分解等特定问题上具有显著优势。然而，当问题本身的输入与输出均为量子态时，传统理论便显露出局限性。

哥伦比亚大学理论计算机科学家亨利·袁（Henry Yuen）指出：“传统复杂性理论对此类问题保持沉默，我们需要建立一套全新的‘全量子’理论框架。”袁教授曾于2020年在传统复杂性理论领域完成里程碑式证明，如今正领导团队探索量子输入/输出问题的内在逻辑。

当“信封”变成量子态
袁以密码学中的“比特承诺”技术为例解释该研究方向的意义：经典比特承诺如同将信息封入信封，其安全性依赖于特定数学问题的计算难度。但若使用量子态承载信息（“量子信封”），即使拥有破解经典难题的超强算力，也可能无法破解量子封装。这表明量子输入输出问题可能具有与传统问题本质不同的逻辑结构。

核心挑战：两类理论的逻辑关系
袁团队关注的核心问题是：若传统复杂性理论的所有问题均已明晰，能否据此推导全量子复杂性理论的内在关联？该问题可转化为“酉合成问题”——若存在能瞬间解决所有经典输入问题的“神谕”，能否借助它高效实现任意量子态转换？若答案是否定的，则证明量子输入输出问题确实具有独特性。

理论突破：乌尔曼变换成为枢纽
袁与合作者近年发现，量子信息论中的乌尔曼定理可转化为典型的量子输入输出问题：当两个纠缠粒子处于不同量子态时，仅对其中一个粒子进行操作以实现状态转换的难度如何？研究显示，该问题与黑洞霍金辐射解码、量子信息压缩等多个重要课题在复杂性上等价。乌尔曼变换如同枢纽，串联起量子密码学、黑洞物理等领域的核心计算难题。

从柬埔寨难民之子到理论开拓者
袁教授的学术之路始于非典型背景。其父母在1970年代逃离柬埔寨红色高棉政权后移民美国，经营餐馆维生。童年听闻家族逃亡经历使他深刻意识到学术研究的珍贵。大学期间，他通过斯科特·阿伦森的博客接触量子计算，并在导师伦·阿德尔曼“摒弃百年传统，另辟蹊径”的科研理念影响下，走上理论创新之路。

当前，袁团队正致力于构建描述量子输入输出问题的理论语言。他强调：“寻找合适的表述体系比证明具体技术结论更重要——缺乏准确的语言，我们甚至无法清晰思考问题。”这项探索或将重新定义量子时代计算复杂性的理论边界。

中文翻译：

量子时代的新复杂性理论

引言

计算机科学最根本的研究对象，就是输入与输出。以袖珍计算器上两个数字相乘这个简单例子来说：你输入一些数字——你想相乘的特定数值——屏幕则显示出代表它们乘积的输出。而将一个数分解为质因数这个逆向问题可能困难得多，但其基本结构是相同的。在计算机上解决问题，归根结底总是将数值输入（通常写作0和1的字符串）转化为输出。

计算复杂性理论领域的研究者探究的，正是为何其中一些转化过程比其他过程更难实现。他们发现，某些普通“经典”计算机难以应对的任务（例如质因数分解问题），对于利用量子物理定律的计算机来说却要容易得多。

三十多年来，复杂性理论家一直运用这一理论框架来识别量子计算机优于经典计算机的问题领域。但还有一类更广泛的问题，他们几乎尚未开始研究，这类问题的输入和输出并非普通的比特串。这正是复杂性理论家亨利·袁最感兴趣的问题。当问题的输入和输出本身在本质上就是量子态时，我们该如何理解它们？

“传统复杂性理论对此完全沉默，”袁说道。“或许我们需要一套独立的理论来理解这另一类问题。”

袁是哥伦比亚大学教授，曾在2020年合作完成了一项传统复杂性理论领域的里程碑式证明。如今，他正领导一项雄心勃勃的计划，旨在构建一个能够容纳这些非常规输入和输出的全新“全量子”理论。

他个人的成长经历，恰恰说明了非典型输入所能带来的可能性。他出生于1989年，在家族经营的南加州餐馆里长大。他的父母是来自柬埔寨农村的难民，在1970年代为逃离种族灭绝而流亡。他学习计算机编程是因为想设计电子游戏。这一早期兴趣引导他在大学主修计算机科学，并由此对量子计算的理论基础产生了浓厚兴趣。

《量子》杂志与袁探讨了复杂性理论的不足、量子密码学与黑洞的关联，以及开放式研究的重要性。为求清晰，访谈内容经过压缩和编辑。

问：研究人员运用传统复杂性理论研究量子计算机的能力已有数十年。这种方法遗漏了什么？

袁： 在传统复杂性理论中，输入和输出始终是经典的。中间发生的过程则由你决定。你可以尝试用经典计算机解决问题，也可以用量子计算机，我们期望量子计算机在某些问题上表现更佳。但为什么输入和输出必须是经典的呢？

问：能否举例说明一个因量子输入或输出而难以理解的问题？

袁： 密码学中有一种称为“比特承诺”的技术，类似于将信息放入密封信封。这能在信息揭示前保护其私密性，同时也防止信息放入后被更改。你可以用这种方案进行拍卖出价或投秘密选票。

经典比特承诺方案是密码学中各种其他方法的基本构建模块。但它们都依赖于一个假设：某些数学问题本质上是困难的。如果你拥有解决这些著名难题的能力，就能破解任何比特承诺方案。

现在想象你的信封是量子的。在这种情况下，即使你拥有同样惊人的计算能力，也不清楚如何用它来破解这些量子信封。

问：因为破解比特承诺方案现在成了一个量子输入问题？

袁： 没错。这个问题似乎不那么数学化，而更物理化。不知何故，拥有强大的经典计算能力并不必然转化为强大的量子处理能力。这暗示着，这两类计算任务的世界可能在本质上是不同的。在我看来，该领域最大的开放问题是：这两个世界之间的逻辑关系是什么？

问：您具体指什么？

袁： 假设我们已知晓传统复杂性理论的一切知识。那是否能告诉我们全量子复杂性理论中所有问题之间的关系？也许我们所有的理解都能轻松移植过去。但也可能，全量子复杂性理论在逻辑上独立于传统复杂性理论。

这个问题有一个优美的表述，称为“酉合成问题”。如果我能够访问一个无限强大的经典预言机——一种能瞬间解决任何经典输入问题的假设设备——我能否用它来高效地执行我选择的任何量子态变换？如果答案是否定的，那就意味着这些量子输入、量子输出问题的本质与经典问题截然不同。几年前这个问题取得了一些进展，但完整答案仍然悬而未决。

问：您在构建新理论方面已迈出初步步伐。目前有何发现？

袁： 这是我和合作者几年前启动的一个项目：描绘这个新世界的面貌，以及这些量子输入问题彼此之间如何关联。我们发现，有一个问题在许多不同地方反复出现。

它源于量子信息论中一个非常基本的结果，称为“乌尔曼定理”。假设你有两个纠缠的量子粒子，意味着它们共享一个量子态，并且这个共享态有两种可能性。量子力学认为，总有可能对两个粒子进行某些操作，将第一个态转化为第二个态。但如果我限制你只能对其中一个粒子进行操作——你还能将第一个态转化为第二个态吗？如果不能，那么你能达到的最接近状态是什么？乌尔曼定理恰恰量化了对于任何一对纠缠态，你所能做到的最佳程度。它在量子通信、量子复杂性、量子密码学等领域都非常重要。

我们所做的是将该定理视为一个量子输入、量子输出问题，其目标是通过仅对其中一个粒子进行局部操作，将一个态转化为另一个态。那么这个问题有多难？解决它需要什么资源？它的难度是否等同于我们关心的其他问题？

我们证明，实际上存在许多自然问题，其复杂性是完全等价的。一个例子是解码黑洞霍金辐射的计算问题。这是一个量子输入问题，因为你是在收集并分析所有这些纠缠粒子。而事实证明，它只是伪装下的乌尔曼变换问题。乌尔曼变换是一个中心枢纽，所有这些其他事物——比特承诺、黑洞解码、量子信息压缩等等——都由此辐射开来。

问：您的家庭背景对于学术研究者而言并不典型。能讲讲您父母如何来到美国的故事吗？

袁： 我的父母在柬埔寨长大，当时是1970年代，红色高棉接管了国家，强迫数百万人进入劳改营。我母亲的家庭被卷入这些营地，做了三四年苦役，之后才设法逃脱。他们花了数月时间穿越山脉和布满地雷的田野。我父亲的家庭则相对幸运一些——他们看到了警示迹象，较早逃离了该国。最终他们设法来到美国，经营一家餐馆，我和哥哥在那里工作直到离家上学。

童年时听他们的故事显然对我产生了巨大影响。

我能享受思考数学和量子物理的特权，并与那些对这些极其小众、深奥难懂话题感兴趣的人一起工作。这与我父母曾经的经历相去甚远。

问：那您是如何对那些极其小众的话题产生兴趣的？

袁： 上大学时，我计划同时主修物理和计算机科学——物理我觉得概念上有趣，计算机科学则源于高中时对电子游戏设计的兴趣。我很快放弃了物理，因为我的实验课非常糟糕。然后在2007或2008年，我发现了斯科特·阿伦森的博客，他在上面写关于量子计算和理论计算机科学的内容。我当时想：“这太棒了。我想研究这个。”这埋下了种子，但对我最具塑造性的经历是跟随莱恩·阿德曼做本科研究。他的信条是：“我们将忽略人们过去100年所做的一切。我们要在所有人都右转的地方左转。”感觉我们就像特立独行的人，在做一些有点叛逆的事情。

问：您当前的研究计划也有点类似。这与在既定理论框架内工作有何不同？

袁： 这与我习惯的研究方式非常不同。没有人递给你一个定理说：“来，证明它。”我们甚至不一定知道正确的问题是什么。但找到正确的语言确实非常重要，即使你没有证明任何真正技术性的东西。没有正确的语言实际上会阻碍你清晰地思考。

英文来源：

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.
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?
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?
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.
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.
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.