原书：《Quantum Computing for Computer Architects》Second Edition - Tzvetan S. Metodi, Arvin I. Faruque, Frederic T. Chong（Morgan&Claypool Publishers - Synthesis Lectures On Computer Architecture）出版时间：Mar 2011

个人汉化了此书的目录与前言，以便大家在搜索相关中文关键词时能获得参考，但也仅供参考。相关术语仅为个人翻译，一切请以原文或已出版物中的翻译为准。

这本书涉及到了一些量子力学知识，没有物理学背景的话，可能会觉得非常抽象而难以理解。因此我在这里推荐一个面向非物理学专业的，非常棒的量子力学科普文：

PeiLingX：深度科普|从线性代数到量子力学(1)：量子力学的打开方式 (上)

其中就介绍了Dirac符号、本征态、叠加态、量子态等量子力学基础概念，并且也理清了这些概念的物理背景。

关键词：quantum computing（量子计算）, computer architecture（计算机体系结构）, fault tolerance（容错）, error correction（纠错）, trapped ions（阱俘粒子）, teleportation（隐形传态）, qubit（量子比特）, quantum logic array（量子逻辑阵列）, quantum simulation（量子模拟）, quantum algorithms（量子算法）

目录汉化

• ■■1 引言 Introduction
• ■■2 量子计算的基本单元 Basic Elements for Quantum Computation
• ■ 1 经典信号状态 vs. 量子信号状态（比特 vs. 量子比特） Classical vs. Quantum Signal States (bits vs. qubits)
• ■ 2 逻辑操作与电路 Logic Operations and Circuits
• ■ 3 量子策略 Quantum Measurement
• ■ 4 例：3-Qubit量子Toffoli门 Example: The 3-Qubit Quantum Toffoli Gate
• ■ 5 例：量子傅里叶变换 Example: Quantum Fourier Transform (QFT)
• ■ 6 例：量子隐形传态 Example: Quantum Teleportation
• ■ 7 例：Deutsch量子算法 Example: Deutsch's Quantum Algorithm
• ■ 8 量子纠缠与ERP对 Quantum Entanglement and EPR Pairs
• ■ 9 量子计算的其它模型 Other Models of Quantum Computation
• ■■3 关键的量子算法 Key Quantum Algorithms
• ■ 1 量子整数分解 Quantum Integer Factorization
• 1 整数分解问题 The Integer Factorization Problem
• 2 量子整数分解算法 A Quantum Integer Factorization Algorithm
• 3 量子整数分解：经典部分的证明 Quantum Integer Factorization: Proof of Classical Part
• ■ 2 寻找阶 Order Finding
• 1 将寻找阶看作是量子本征态估计 Order Finding as Quantum Eigenvalue Estimation
• 2 寻找阶：连分数 Order Finding: Continued Fractions
• ■ 3 量子相位估计 Quantum Phase Estimation
• 1 有关相位估计电路正确性的证明思路 Proof Sketch of the Correctness of the Phase Estimation Circuit
• ■ 4 本征态估计 Eigenvalue Estimation
• ■ 5 隐含子群问题 The Hidden Subgroup Problem
• ■ 6 Grover量子搜索算法 Grover's Algorithm for Quantum Search
• 1 通过量子黑盒进行搜索 Searching with a Quantum Black Box
• 2 Grover算法 Grover's Algorithm
• 3 有关Grover迭代正确性的证明 Proof Sketch of the Correctness of Grover Iteration
• ■ 7 量子绝热算法 Quantum Adiabatic Algorithms
• 1 3-SAT：量子绝热算法的一个例子 3-SAT: An example of a Quantum Adiabatic algorithm
• ■■4 构建可靠且可扩展的量子架构 Building Reliable and Scalable Quantum Architectures
• ■ 1 可靠且实际的实现技术 Reliable and realistic implementation technology
• 1 光量子计算：将光子作为量子比特 Optical Quantum Computation: Photons as Qubits
• 2 阱俘离子量子计算：将离子阱作为量子比特 Trapped-Ion Quantum Computation: Ions as Qubits
• ■ 2 稳健的纠错与容错结构 Robust Error Correction and Fault-Tolerant Structures
• 1 噪声模型假设 Noise Model Assumptions
• 2 纠错：基础与记号 Error Correction: Basics and Notation
• 3 例：Steane [[7,1,3]]编码 Example: The Steane [[7,1,3]]Code
• 4 量子计算中的逻辑量子比特 Logical Qubits in Quantum Computation
• 5 量子纠错与容错：阈结果^[1] Quantum Error Correction and Fault-Tolerance: The Threshold Result
• 6 量子纠错的成本 The Cost of Quantum Error Correction
• 7 纠错引起的系统规模增大 Scale-Up in System Size due to Error Correction
• 8 纠错引起的减速^[2] Error Correction Slowdown
• ■ 3 量子资源分配 Quantum Resource Distribution
• 1 物理量子比特的移动^[3] Physical Qubit Movement
• 2 基于隐形传态的通信与量子中继器 Teleportation-Based Communication and Quantum Repeaters
• ■■5 量子计算的模拟 Simulation of Quantum Computation
• ■ 1 误差传递的模拟 Simulation of Error Propagation
• ■ 2 量子模拟的稳定子方法 Stabilizer Method for Quantum Simulation
• ■■6 架构的基本单元 Architectural Elements
• ■ 1 量子处理单元（PE's） Quantum Processing Elements (PE's)
• ■ 2 量子存储层次结构 Quantum Memory Hierarchy
• ■ 3 经典存储器的量子寻址方案 Quantum Addressing Scheme for Classical Memory
• ■ 4 纠错与量子架构设计 Error Correction and Quantum Architecture Design
• 1 辅助准备与（硬件）布局的影响 Effects of Ancilla Preparation and Layout
• 2 根据关键路径对纠错进行优化 Optimizing Error Correction along Critical Paths
• ■■7 案例研究：量子逻辑阵列架构 Case Study: The Quantum Logic Array Architecture
• ■ 1 QLA架构概览 QLA Architecture Overview
• ■ 2 QLA中的逻辑量子比特设计 The Logical Qubit Design in the QLA
• ■ 3 逻辑量子比特互连 Logical Qubit Interconnect
• ■ 4 压缩的QLA架构：CQLA Compressed QLA Architecture: CQLA
• 1 增益积（GP）：架构的性能比较 The Gain Product: Architecture Performance Comparison
• 2 通信主题：Toffoli门的实施 Communication Issues: Executing the Toffoli Gate
• 3 CQLA架构中的存储层次结构 Memory Hierarchy in the CQLA Architecture
• 4 对CQLA缓存的模拟 Simulating the Cache in the CQLA
• ■ 5 Qualypso架构 Qualypso
• ■■8 量子架构上的编程 Programming the Quantum Architecture
• ■ 1 物理层指令调度 Physical-Level Instruction Scheduling
• ■ 2 高层编译器设计 High-Level Compiler Design
• ■ 3 架构无关的电路综合 Architecture-Independent Circuit Synthesis
• ■ 4 将电路映射至架构 Mapping Circuits to Architecture
• ■ 5 逻辑量子比特分片^[4]的优化 Optimization of the Logical Qubit Tiles
• 1 容错阈估计 The Fault-Tolerant Threshold Estimates
• 2 电路调度与容错约束 Circuit Scheduling and The Fault-Tolerance Constraint
• 3 阈计算 Threshold Calculations
• 4 小结讨论 Summary Discussion
• ■■9 将QLA用于量子模拟：横向Ising模型（TIM） Using the QLA for Quantum Simulation: The Transverse Ising Model
• ■ 1 横向Ising模型的概览 The Transverse Ising Model Overview
• ■ 2 TIM量子模拟资源估计 TIM Quantum Simulation Resource Estimates
• 1 相位估计电路 Phase estimation circuit
• 2 将TIM量子电路分解为容错门 Decomposition of the TIM quantum circuit into fault-tolerant gates
• ■ 3 将TIM电路映射到QLA架构 Mapping the TIM circuit onto the QLA architecture
• 1 一维TIM问题的资源估计 Resource estimates for the 1-D TIM problem
• ■■10 基于隐形传态的量子架构 Teleportation-Based Quantum Architectures
• ■ 1 基于隐形传态的cnot门与单量子比特门 The cnot Gate and Single-Qubit Gates through Teleportation
• ■ 2 架构 The Architecture
• ■ 3 基于隐形传态的纠错 Error Correction through Teleportation
• ■■11 总结 Concluding Remarks

摘要汉化

对于某些问题的求解，量子计算机的速度（在理论上）要远快于在经典计算机上运行的任何已知算法。尽管目前量子计算机的建造技术还处在起步阶段，但现在就开始考虑大型量子计算机设计中的可扩展性（scalability）和可靠性（reliability）并不算早。在构架系统的同时，我们也必须去了解该如何设计一个平衡（balance）且容错（fault-tolerant）的量子计算机架构（quantum computer architecture）。本讲座的目的就在于为量子计算机的设计提供一个架构级的抽象（architectural abstraction），并在系统级别（system-level）探讨有关实现可扩展（scalable）和可容错（falut-tolerant）量子计算中的挑战。

我们会在本讲座中为量子计算提供一个面向工程的介绍，并且概览藏在关键量子算法背后的理论基础。随后，根据实验数据以及未来的预测，对基于离子阱（trapped ions）实现的量子计算进行架构案例研究。尽管这里的讨论集中于基于离子阱实现的架构，但本讲座中所描述的量子计算机架构、量子容错和编译技术也同样适用于那些，其它用于构建大型量子计算系统的候选技术。此外我们还讨论了量子计算机编程所涉及的一般问题（general issue），以及基于量子隐形传态（quantum teleportation）的量子架构。最后我们还考虑了一些在量子计算机设计中仍存在的开放问题（open problem）。

序言汉化

对于某些问题的求解，量子计算机的速度（在理论上）要远快于在经典计算机上运行的任何已知算法。尽管目前量子计算机的建造技术还处在起步阶段，但现在就开始考虑大型量子计算机设计中的可扩展性（scalability）和可靠性（reliability）并不算早。在构架系统的同时，我们也必须去了解该如何设计一个平衡（balance）且容错（fault-tolerant）的量子计算机架构（quantum computer architecture）。本讲座的目的就在于为量子计算机的设计提供一个架构级的抽象（architectural abstraction），并在系统级别（system-level）探讨有关实现可扩展（scalable）和可容错（falut-tolerant）量子计算中的挑战。

我们会在本讲座中为量子计算提供一个面向工程的介绍，并且概览藏在关键量子算法背后的理论基础。随后，根据实验数据以及未来的预测，对基于离子阱（trapped ions）实现的量子计算进行架构案例研究。尽管这里的讨论集中于基于离子阱实现的架构，但本讲座中所描述的量子计算机架构、量子容错和编译技术也同样适用于那些，其它用于构建大型量子计算系统的候选技术。此外我们还讨论了量子计算机编程所涉及的一般问题（general issue），以及基于量子隐形传态（quantum teleportation）的量子架构。最后我们还考虑了一些在量子计算机设计中仍存在的开放问题（open problem）。

第二版的新内容

本书的第二版包含了新的内容，旨在让读者更深入地理解量子计算的背景，以及量子计算机架构中的新概念与成果。新的一章（第3章）对第2章讨论的量子计算进行了进一步的具体讨论，详细介绍了一些关键的量子算法，包括多项式时间的整数分解Shor算法，以及Grover量子搜索算法。第7章还增加了粒子阱量子计算机架构方面的最新研究成果。此外我们还增加了另一个新的章节（第8章），提供了第7章所描述的架构，在量子模拟任务方面应用的案例研究。

本书结构

本书首先从第2章以一个简短的背景知识介绍开始，在计算的角度（而不是物理学）将量子计算的基本操作与传统计算方案进行了对比。我们较为详细地介绍了量子比特、量子逻辑门的概念，以及与量子计算电路模型有关的，量子计算的其它重要组成部分。

随后，我们在第3章概述了几个著名量子算法背后的数学原理。

在第4章，我们介绍了可扩展量子架构（scalable quantum architecture）在高层次（high-level）方面的三个要求，并在后续的章节中分别独立地描述了每个要求：

• 4.1节：可靠的实现技术（reliable implementation technology）
• 4.2节：高效的纠错方案（efficient error correction schemes）
• 4.3节：高效的量子资源分配（efficient quantum resource distribution）

第5章介绍了量子计算架构的建模和仿真，以及周期级的量子模拟方法，包括简要地介绍了量子计算中的稳定子体系（stabilizer formalism）与纠错方法。

第6章描述了一套量子架构中的架构元件（architecural element），第6.2节介绍了量子存储层次结构的概念。

第7章中我们在先前工作 [60, 140]的基础上，提供了一个量子架构的案例研究，即所谓的量子逻辑阵列（QLA, Quantum Logic Array）。

第8章说明了该如何对量子架构进行编程。

第9章我们介绍了QLA架构的量子模拟应用。

第10章讨论了可用于实现容错通用量子逻辑的其它方法，即通过隐形传态进行量子操作。

最后在第11章中我们对所做的工作进行了简要的总结。

Tzvetan S. Metodi, Arvin I. Faruque, and Frederic T. Chong

March 2011

引言汉化

量子计算听起来像是一个科幻小说中的主题，但实际上小型的量子计算机已经存在了好几年 [212]，更大的机器也已经有了草图 [114]。这些尝试都是被一个诱人的特性所推动的：在传统计算机所采用的二进制表示下，所处理的信息量最多只能随资源线性地扩展；而量子计算所利用的能相互作用量子现象，可以让所处理的信息量在系统中随“量子比特（Qubit）”的数量呈指数级增长。

通过构架大型系统来开发这一潜力是本书的重点。我们的目标在于，为具有潜力的技术提供共有的架构抽象（common architectural abstraction），并探讨可扩展、容错量子计算在系统级别（system-level）上的挑战。

尽管量子技术尚处于起步阶段，但我们可以看到的是，现在就开始考虑可扩展性和可靠性也并不算早。事实上，这些考虑对可行设备技术发展的指导也是至关重要的。

这本书的前提是针对量子计算（QC, quantum computation）的架构主题。我们所强调的一个事实是：大型量子计算的基本原理，是通过系统平衡（system balance）来实现可靠性（reliability）的——即需要让保护和控制量子信息的时间足够长，以使得算法能够完成执行。要构架一个QC系统，就必须去了解，设计和模拟一个平衡、容错的量子架构所需要的东西，正如平衡概念所驱动的传统架构设计那样。例如，在经典处理器中，功能单元的数量要与寄存器文件的深度相匹配，或者内存带宽需要与缓存缺失率相匹配。

为体现“平衡（balance）”这一概念在量子架构设计中的应用，我们会对两种用于实现Shor量子整数分解算法的量子架构进行比较，即量子逻辑阵列（QLA, quantum logic array）架构 [140]，以及随后的压缩量子逻辑阵列（CQLA, compressed quantum logic array）架构 [60]。它们都是为电路计算模型（circuit-based model of computation）所设计的同质（homogeneous）分片（tiled）^[4]架构。这两种架构都可以被看作是由 计算分片组成的网格（gird of computational tiles），其中每个分片都代表1个容错量子比特或逻辑量子比特。然后，1个逻辑量子比特是由多个物理量子比特所编码的，以为量子纠错提供必要的资源（量子纠错是目前为止量子计算机最主要的操作 [153]）。

这两种架构的主要区别在于，在CQLA中，设计者将一些额外的可靠性换取为了面积和架构速度方面的增益（trade-off），从而创建了一个更为平衡（balance）的量子比特资源的系统级组织结构。

图1.1中的性能设计金字塔就展现了这种可靠性（reliability）和速度、面积间的权衡。这三个性能参数（可靠性、面积、速度）中的每个都在朝着金字塔顶端的方向改进。然后，量子计算机中的每个操作都会有一个最低可靠性标志（minimum reliability mark），一旦处于该标记下方，就不可能对大于2048bits的整数进行分解 [60, 140]。除此之外，金字塔的另外两个轴线（面积和速度）上也可能会存在类似的约束，这都取决于应用程序集或技术限制。文献[103][220]就对这种限制进行了一些探索。

我们希望我们针对特定架构模型的描述能够让读者继续推进可扩展量子架构的研究，并解决一些关键的开放问题。例如，容错可扩展数据存储结构、计算结构、可扩展通信机制和用于协调程序执行的经典（classical）调度器这些东西的最佳整合方式是什么？读完本书后，读者应该能够去识别出可扩展量子计算中各种需求间的权衡，以及最重要的（通过巧妙的系统设计），能够创建出一个能够平衡可靠性、面积和时间性能的量子架构，并成为未来技术进步中的一部分。

不过不幸的是，大型量子机器的建造是相当困难的。这种困难与，自然界中的量子信息只能在非常小、且仔细隔离的物理系统（如单光子和原子）中控制，这一直觉是相符的。量子力学系统中，二进制信息可以被存储在单个脆弱的量子数据单位（称作量子比特 [177]）中，即原子的不同能态（energy states）或者光子的偏振态中。

另一方面，更大尺度系统也自然地与环境耦合，并表现出符合生活经验的，被经典物理学所支配的行为。这一观察的一个推论是：量子计算的物理学往往是违背我们经典直觉的，这也是QC的潜力之处，以及在可靠量子计算机理解方面困难的原因。

自从Feynman观察到了经典计算模型与量子力学模型间的巨大差异后^[5]，量子图灵机下的第一个模型就由Benioff提出了 [20]。随后，Deutsch [63, 64]将量子电路模型描述为了一个量子图灵机的通用模拟器，其开销是指数级的。紧随着Deutsch的工作，Bernstein和Vazirani [26]随后就描述出了一个具有多项式级开销（polynomial overhead）的通用量子图灵机。

自通用量子电路模型的建立以来，已经提出了数个基于量子门（quantum gate）的量子算法，这些算法与基于传统计算的已知算法相比具有非常大的优势。其中最重要的是Peter Shor的算法，能够在多项式时间内分解两个大素数乘积 [184]^[6]。其它量子算法以及应用包括Grover的快速数据库搜索算法 [89]；最优化问题的绝热解 [48]；精确的时钟同步 [51]；量子密匙分配 [24]；以及最近的，高斯和 [211]和Pell方程 [91]。在商业方面，量子技术也已被证明能够实现无条件的安全通信^[7]，并带来了公司的真实产品 [81, 170]。

一台实用的大型量子计算机，要充分发挥这些算法的潜力，就必须达到 S=KQ\ge 10^{12} 个逻辑操作（logical operations）的系统规模，其中 K 表示计算步骤的数目， Q 表示计算单元的数量。问题在于，在维护如此大规模的量子计算同时，量子信息的载体（量子比特）也会不断地与环境中的外部噪声源相互作用，并最终失去它的量子数据。此外，与经典的比特位串不同，不同的量子态相互之间是可能纠缠在一起的。尽管纠缠是量子计算的力量所在，但如果不在微架构层面上注意对错误传播的限制的话，它也会使得错误扩散到整个纠缠量子比特体系中。

对于可扩展QC（scalable QC），一个重要的理论突破就是容错量子纠错（FTQEC, fault tolerant quantum error correction）理论的发展。FTQEC通过将单个量子比特状态递归地编码为2或多个低级量子比特的状态，来实现大型系统可靠性的任意提高。为在带噪声的物理门（physical gates）上维持较长时间的可靠计算，逻辑门必须直接地在逻辑量子比特上实现，并且在不解码的情况执行逻辑功能，以确保错误不会通过编码状态的数据干涉状态样式（data interference pattern）。在本讲座的后面（Chapter 4.2.8），我们就会讨论这些量子计算的潜在好处与开销挑战的管理之间的关系影响。

大型冗余结构的物理实现还有另一个基本挑战，那就是量子数据的长距传输，这对于目前的技术来说是不可行的。因此在设计实用的大型量子计算机的最大挑战之一，就是在找到一个满足容错需求的架构同时，又尽可能地减少通信和资源的开销。在我们这本书讨论的两个案例架构中，通信的挑战就是通过采用以下设计原则来解决的：

• 首先，将架构组件（component）专门分为计算和存储两个区域是有利的；
• 其次，量子隐形传态的概念 [21]在大型架构的长距传输是有利的；

从这两个设计原则出发，我们描绘了一个可扩展量子架构的一般抽象，其中最主要的成本来源于计算和存储区域间的通信（基于隐形传态）。在该系统下，用于调度量子计算的编译器基础设施能最大限度地利用处在计算区域的数据，并最小化它们进出内存的移动（类似最小化传统处理器中的寄存器溢出（register spiling））。

计算机架构师（computer architect）看完这本书后，应该可以了解的与可扩展量子计算机系统设计相关的关键思想是：

• ^[8]要实现“良好”的系统性能（performance），就要在量子架构实现中对可靠性、通信资源和计算延迟相互之间进行可行的平衡（balance）。
• ^[9]量子信息无法被克隆——因此它从源头沿着量子通道转移到目的地时，无法在源头留下痕迹。
• ^[10]可以通过物理方式移动量子比特，来将量子信息传输到共享介质上，如量子总线或者允许量子比特高效移动，或者允许相邻量子比特相互之间进行连续交换的量子系统，或者通过隐形传态。
• ^[11]可靠性的需求使得系统的各个组件之间进行要进行非常有趣的搭配。例如，由于编码数据（encoded data）在通过逻辑门处理时需要花费大量的资源和延迟开销进行纠错，通信和计算还可以在系统层次（system level）上重叠（overlapping）起来。
• ^[12]存在许多在应用程序实现量子逻辑的不同方法。门（gate）可以内嵌在通信协议中，或者就按照传统的方式应用于量子数据，类似于经典电路。
• ^[13]系统的平衡性与容错性取决于，架构中不同区域所采用的不同量子数据纠错编码^[14]，以及它们在不同区域间的转移，其中从一个区域转移至另一个区域所需的成本与资源需要让所执行的应用程序仔细谨慎地确定。
• ^[15]经典计算中的存储层次结构（memory hierarchy）与量子系统中的编码层次（code hierarchy）非常类似。从存储区域转移至计算区域可能需要让数据从一种编码转移到另一种编码上，而不是从一种工艺技术类型（technology type）转移到另一种工艺技术类型上。

参考

1. ^这里的意思是满足阈（Threshold：阈值/阈）条件的结果。
2. ^指的是算法速度变慢。
3. ^这个“移动”指的是数据移动。
4. ^^ab这个“同质（homogeneous），分片（tiled）”的意思是，该架构由许多同质（或者说相同）的“片”组成。比如经典FPGA中的每个LB就是一个片/分片（tile）。
5. ^原文注释：这一观点是Feynman与1981年在MIT举行的第一届Conference on the Physics of Computation中所提出的。Feynman指出，在经典计算机上有效地模拟量子系统的演化是不可能的，除非构建出一个固有的量子计算机。
6. ^原文注释：被广泛使用的RSA公钥密码系统的安全性依赖于这样一个假设，即大整数的分解在常规计算机上是非常困难的 [172]，其中最著名的因数分解经典算法也是超多项式的 [40]。
7. ^原文注释：在数学上，量子密钥分配（QKD, quantum key distribution）已被证明是不可破解的 [17, 23, 65, 134]，但最近的实验观察表明，由于协议的概率性质，加上充满噪声的用于收发量子状态设备，还是能够允许攻击者以一个较高的成功率破解系统 [147]。
8. ^原文：Achieving "good" system performance is synonymous with the realization of a workable balance between reliability, communication resources, and latency of computation in a quantum architecture.
9. ^原文：Quantum information cannot be cloned - thus, when transferred from source to destination along a quantum channel, it must be transferred in such a way that no trace is left at the source.
10. ^原文：Quantum information can be transported by physically moving the qubits, transferring the information to a shared medium such as a quantum bus or a secondary quantum system that allows efficient qubit movement, successive swapping between adjacent qubits, or through the concept of teleportation.
11. ^原文：The need for reliability allows for interesting match-ups between various system components. For example, communication and computation can be overlapped at the system level, due to the considerable resources and latency overhead spent on error correction during logic gate execution of encoded data.
12. ^原文：There are many different ways to implement universal quantum logic at the application level. Gates can be built into the communication protocols or applied to the quantum data in a traditional manner analogous to classical circuits.
13. ^原文：System balance and fault-tolerance depends on the balance between different encodings of the quantum data defined by the error correcting codes used across different regions in the architecture, where the cost and resources required to transfer from one region to another are carefully determined by the executed application.
14. ^这句话原文：different encodings of the quantum data defined by the error correcting codes used.
15. ^原文：The memory hierarchy in classical computation is analogous to code hierarchy in quantum systems.The transfer from storage regions to computational regions may require transfer from one encoding of the data to another, not a transfer from one technology type to another.