Chapter 1: The Quantum Information Landscape | 第一章：量子信息全景

The Quantum Information Landscape | 量子信息全景

Introduction: The End of Computation as We Know It | 引言：我们所知的计算的终结

The year 1981 marked a pivotal moment in the history of science and computation. At a conference at MIT's Endicott House, physicist Richard Feynman stood before an audience of computer scientists and physicists, posing a question that would fundamentally reshape our understanding of computation itself. "Nature isn't classical," Feynman declared, "if you want to make a simulation of nature, you'd better make it quantum mechanical." This seemingly simple observation contained within it the seeds of an entirely new computational paradigm—one that would challenge the very foundations of how we think about information, complexity, and the limits of what machines can compute.

1981年，麻省理工学院Endicott House的一次会议上，物理学家理查德·费曼站在计算机科学家和物理学家面前，提出了一个问题，这个问题将彻底重塑我们对计算本身的理解。“自然不是经典的，”费曼宣称，“如果你想模拟自然，你最好用量子力学来模拟。”这个看似简单的观察包含了一个全新计算范式的种子——这个范式将挑战我们关于信息、复杂性以及机器计算能力的认知基础。

The significance of Feynman's observation cannot be overstated. For decades, the prevailing assumption in computer science had been that the classical computer—a machine operating on bits that exist in definite states of either 0 or 1—could, in principle, simulate any physical process given sufficient time and resources. This assumption, rooted in the Church-Turing thesis, had served as a guiding principle for the development of modern computing. Yet Feynman recognized a fundamental flaw in this reasoning: classical computers face an exponential barrier when attempting to simulate quantum systems. The very laws of physics that govern the behavior of matter at the atomic and subatomic scales operate according to quantum mechanical principles that seem to defy efficient representation on classical hardware.

费曼这一观察的重要性再怎么强调也不为过。几十年来，计算机科学领域一直有一个普遍假设：经典计算机——一种以明确的0或1状态运行的机器——原则上可以模拟任何物理过程，只要有足够的时间和资源。这一假设植根于丘奇-图灵论题，曾是现代计算发展的指导原则。然而，费曼认识到了这一推理中的一个根本缺陷：经典计算机在尝试模拟量子系统时面临着指数级的障碍。支配物质在原子和亚原子尺度行为的物理定律，按照量子力学原理运行，而这些原理似乎无法在经典硬件上得到有效表示。

This recognition led Feynman to propose what would become one of the most influential ideas in theoretical computer science: the quantum simulator. If nature is quantum mechanical, then perhaps the most efficient way to simulate quantum systems is to build a quantum computer—a machine that harnesses quantum mechanical phenomena itself to perform computation. This insight would take years to fully develop and appreciate, but it established the intellectual foundation for what we now call quantum computing.

这一认识促使费曼提出了后来成为理论计算机科学中最具影响力的想法之一：量子模拟器。如果自然是量子力学的，那么模拟量子系统最有效的方法可能是建造量子计算机——一种本身利用量子力学现象进行计算的机器。这一见解需要数年时间才能充分发展和理解，但它为后来我们所说的量子计算奠定了知识基础。

In the decades since Feynman's proposal, quantum computing has evolved from a speculative theoretical idea into a thriving field of research and development. Major technology companies—including IBM, Google, Microsoft, Intel, and Amazon—have invested billions of dollars in quantum computing research. National governments have launched substantial quantum initiatives, recognizing the strategic importance of this technology for both economic and security reasons. Universities worldwide have established dedicated quantum computing research programs, training a new generation of researchers and engineers. And yet, despite this remarkable progress, we remain in the early stages of a journey whose ultimate destination we cannot fully foresee.

自费曼提出这一观点以来的几十年里，量子计算已从一个推测性的理论想法发展成为一个蓬勃发展的研究和开发领域。IBM、谷歌、微软、英特尔和亚马逊等主要技术公司已向量子计算研究投资了数十亿美元。各国政府已启动了重大量子计划，认识到这项技术对经济和安全的重要性。世界各地的大学已建立了专门的量子计算研究项目，培养新一代研究人员和工程师。然而，尽管取得了这一显著进展，我们仍处于一段旅程的早期阶段，其最终目的地我们无法完全预见。

This book is designed to guide readers through this exciting and challenging landscape. But before we can appreciate the potential of quantum computing or understand the obstacles that must be overcome, we must first develop a deep understanding of the quantum information landscape—its historical development, its theoretical foundations, and its practical manifestations. This chapter serves as that foundation, establishing the context and motivation for everything that follows.

本书旨在引导读者穿越这个令人兴奋且充满挑战的领域。但在我们能够欣赏量子计算的潜力或理解必须克服的障碍之前，我们必须首先深入理解量子信息全景——其历史发展、理论基础和实际表现。本章作为这一基础，确立后续所有内容的背景和动机。

The Classical Computing Foundation | 经典计算基础

The Turing Machine and Universal Computation | 图灵机与通用计算

To understand why quantum computing represents a paradigm shift, we must first appreciate the remarkable power and elegance of classical computation. The theoretical framework for understanding computation was established in the 1930s, long before the advent of practical electronic computers. Alan Turing, working independently of and simultaneously with Alonzo Church, developed what would become known as the Turing machine—a hypothetical device that formalized our intuitive notion of computation.

要理解为什么量子计算代表范式转变，我们首先必须认识经典计算的非凡力量和优雅。理解计算的理论框架是在1930年代建立的，远在实用电子计算机出现之前。阿兰·图灵与阿隆佐·丘奇独立且同时地提出了后来被称为图灵机的理论——一种将我们直观计算概念形式化的假想设备。

The Turing machine consists of an infinite tape divided into discrete cells, a read-write head that can move along the tape, a finite set of states, and a transition function that determines the machine's behavior based on its current state and the symbol it reads. Despite its apparent simplicity, this abstract device can perform any computation that any other computing machine can perform—a property known as Turing completeness. Church and Turing formalized this observation in what became known as the Church-Turing thesis: any function that can be computed by any algorithmic process can be computed by a Turing machine.

图灵机由一条划分为离散单元的无限纸带、一个可以沿纸带移动的读写头、一组有限状态以及一个转移函数组成，该函数根据机器的当前状态和读取的符号决定其行为。尽管看起来很简单，但这个抽象设备可以执行任何其他计算设备可以执行的计算——这一特性被称为图灵完备性。丘奇和图灵在后来被称为丘奇-图灵论题的理论中将这一观察形式化：任何可由任何算法过程计算的函数都可以由图灵机计算。

The Church-Turing thesis, while not a formal mathematical theorem, has proven to be one of the most enduring and insightful principles in computer science. It establishes a fundamental equivalence between what we intuitively mean by "computation" and what Turing machines can do. More importantly, it suggests that the limitations of computation are not artifacts of our particular computing technology but rather inherent in the nature of computation itself. If a Turing machine cannot efficiently solve a problem, then no classical computer ever can.

丘奇-图灵论题虽然不是一个正式的数学定理，但已被证明是计算机科学中最持久、最具洞察力的原理之一。它在我们直观理解的"计算"与图灵机所能做的事情之间建立了根本的等价。更重要的是，它表明计算的局限性不是我们特定计算技术的产物，而是计算本身固有的。如果图灵机不能有效地解决某个问题，那么任何经典计算机都不可能做到。

Complexity Classes and the Structure of Computational Difficulty | 复杂度类与计算难度结构

The Turing machine framework allows us to categorize computational problems according to their inherent difficulty. The most fundamental distinction is between problems that can be solved in principle (decidable problems) and those that cannot (undecidable problems). The existence of undecidable problems, famously demonstrated by Turing's proof of the halting problem, establishes that there are inherent limits to what computation can achieve.

图灵机框架使我们能够根据问题的固有难度对计算问题进行分类。最基本的区别是原则上可以解决的问题（可判定问题）和不能解决的问题（不可判定问题）。不可判定问题的存在——图灵对停机问题的著名证明——表明计算存在固有的局限性。

For problems that are decidable, we can further classify them according to the resources required to solve them. The most important resource is time, measured in the number of steps the computation requires. Complexity theory classifies problems based on how the required time (or space) grows as a function of the input size:

对于可判定的问题，我们可以根据解决它们所需的资源进一步分类。最重要的资源是时间，以计算所需的步数来衡量。复杂度理论根据所需时间（或空间）随输入规模增长的函数对问题进行分类：

Complexity Classes | 复杂度类

1. P (Polynomial time): Problems solvable by a deterministic Turing machine in time $O(n^k)$ for some constant $k$. These are considered "efficiently solvable" problems. Examples include sorting, shortest path finding, and linear programming.

• **P（多项式时间）**：可由确定性图灵机在 $O(n^k)$ 时间内解决的问题，其中 $k$ 为某个常数。这些被认为是"可有效解决"的问题。例子包括排序、最短路径查找和线性规划。

2. NP (Nondeterministic Polynomial time): Problems for which a propose