标签 Go 下的文章

量子计算入门与Go模拟

本文永久链接 – https://tonybai.com/2024/12/11/simulate-quantum-computing-in-go

2019年,Google宣布实现”量子霸权”,声称其53量子比特的量子计算机完成了一个经典超级计算机需要1万年才能完成的计算任务。这一宣告在当时引发了广泛关注和热议。而在这个过程中,我们也看到了太多对量子计算的误解。有人将其想象成未来取代经典计算机的全能机器,认为它能以指数级速度解决所有计算问题;也有人认为量子计算只是一个遥不可及的科研概念,与实际应用毫无关联。

五年过去了,世界依然被经典计算机主宰,量子计算逐渐变成了“落魄网红”,淡出了公众视野。

如今,人们对量子计算机的印象似乎仅剩下那盏“豪华吊灯”:


量子计算机(图片来自网络)

作为领域局外人,我无法判断量子计算是否进入了技术成熟度曲线(Hype Cycle)的”泡沫破裂谷底期”。但现在的量子计算机在用途上与图形处理单元(GPU)很类似,都主要集中在特定领域的问题解决上,且在这些领域预期会展现出独特的优势

GPU主要设计用于图形渲染、图像处理等领域,后因其能够高效地处理并行计算任务,在机器学习模型训练和推理领域也取得了显著成功。类似地,量子计算机当前也专注于一些特定的应用领域,如量子模拟、优化问题和密码学等。它们在解决这些复杂问题时,理论上有可能实现远超经典计算机的性能。

但无论是GPU还是量子计算,目前看来都无法胜任经典计算机中通用处理器(CPU)所擅长的一般任务,这就决定了经典计算机势必仍将存在,并且是我们和GPU以及量子计算机彼此交流和互动的主要方式

从经典计算机的角度,GPU是其图形计算单元,经典计算机会将其擅长的任务分派到GPU上进行处理。按照这个思路,我们可以大胆地设想一种叫作QPU(Quantum Processing Unit)的量子处理单元,经典计算机会将量子计算擅长的计算任务分派到QPU上进行处理:

这样的计算机结构,对于程序员来说再熟悉不过了!

到这里,有人可能会问:那么大一个“豪华吊灯”,如何能变为一个小巧玲珑的QPU并放到我们常见的PC中呢?

回顾经典的通用计算机发展史,这种可能性还真的存在。你能想到80年前由冯·诺依曼主持设计的第一代存储程序的计算机(即冯·诺依曼机,现代计算机的原型)EDVAC(电子离散变量自动计算机,Electronic Discrete Variable Automatic Computer)有多大吗:


经典计算机EDVAC(图片来自网络)

这个庞然大物的算力可能还不如现在你手腕上带的智能手表。随着物理学、材料科学等前沿学科的突破,“豪华大吊灯”变成一块板卡也不是没有可能。

与经典计算机的融合意味着如今的开发人员依然可以使用熟悉的人机交互界面与量子计算机打交道,包括量子计算的编程。但要针对量子计算机编程,需要了解量子计算的一般原理,就像基于英伟达的CUDA进行GPU编程一样。

然而,目前的现实是量子计算机依然是“昂贵且稀缺的设备”,世界范围内只有巨头公司以及大型科研院所才拥有真实的量子计算机。但普通程序员仍然可以通过模拟器工具一窥其奥秘,理解其核心概念并为未来应用做好准备:


量子编程的层次结构

这些量子模拟器可以在经典计算机上模拟量子计算过程,让量子计算的学习和实验变得触手可及。在这篇文章中,我就和大家一起学习一下量子编程的基本概念和编程方法,并使用模拟器编写一些简单的量子计算程序。

1. 从经典计算到量子计算的认知跨越

要理解量子计算,我们需要先回顾经典计算的基本概念和抽象,然后建立起通向量子计算的认知桥梁。

1.1 经典计算机的基本抽象

在经典计算中,信息的基本单位是比特(bit),其值由两种电平状态来表示:

  • 低电平(0):通常表示为“0”或“低电压”,例如0伏特。
  • 高电平(1):通常表示为“1”或“高电压”,例如5伏特或3.3伏特。

即每个比特的值只能取0或1。这种电平的二元状态形成了数字电路的基础,使得计算机能够处理和存储信息。

比特的电平状态不仅用于计算,还用于信息的存储和传输。在存储器(如RAM)中,每个比特的位置对应于一个电平状态,通常通过电容或电感来保持电平。在数据传输中,信号的电平变化用于表示比特的流动,例如在串行或并行通信中。

1.1.1 比特与布尔逻辑

经典计算机使用比特进行所有信息处理。而布尔逻辑正是基于比特的逻辑运算,包括以下基本操作:

  • AND(与):仅当两个输入均为1时,输出才为1。
  • OR(或):只要有一个输入为1,输出即为1。
  • NOT(非):将输入的0变为1,1变为0。

这些基本逻辑门是构建更复杂运算的基础,所有复杂的计算都可以通过这些简单的逻辑操作组合而成。

1.1.2 门电路模型

门电路模型是经典计算的核心,利用逻辑门的连接来实现复杂的计算任务。电路由逻辑门(如与门、或门、非门等)构成,通过这些门的组合与连接,可以构建出加法器、乘法器等基本算术单元,以及更复杂的功能,比如处理器中的运算单元。门电路模型的优势在于其可组合性和可扩展性,使得计算机能够执行从简单到复杂的各种任务。

1.1.3 程序抽象

编程语言为程序员提供了更高级的抽象,使得比特操作不再需要直接进行,尤其是近半个世纪以来诞生的高级语言,如C/C++、Java、Go、Python等。通过这些高级编程语言,开发者可以使用更接近自然语言的语法来编写代码,底层的比特操作则由编译器或解释器自动处理。这种抽象不仅提高了编程效率,也使得程序员可以专注于算法和逻辑,而不必深入底层硬件细节。例如,C、Go、Python等编程语言提供了丰富的类型系统、控制结构与高级数据结构,使得程序员可以用简单的语句来处理复杂的数据操作。随着技术的发展,面向对象编程、函数式编程等新范式也相继出现,为软件开发提供了更灵活的方式。

以上对经典计算机的认知路径能够为理解量子计算机提供重要的基础和视角。接下来,我们就沿着这个路径认识一下量子计算的核心概念。

1.2 量子计算的核心概念

提及“量子”,人们首先想到的可能是大学物理中的量子力学。量子的概念来源于物理学,但和电子等真实存在的粒子不同,“量子”并不是指某个特定的粒子,而是一个广泛的基本概念,用来描述物质和能量在微观尺度上的离散性。在物理学中,量子具有以下主要特性:

  • 不确定性

海森堡的不确定性原理。该原理指出,某些物理量的精确值不能同时被完全确定,比如位置和动量。即使在理想情况下,测量一个量的精确性会导致对另一个量的测量不确定性增加。

  • 量子叠加态

在量子力学中,物体的状态被称为量子态。量子态可以通过波函数来描述,波函数包含了物体可能的所有状态的信息。此外,量子叠加原理允许一个量子系统同时处于多个状态。例如,电子可以同时占据多个能级,直到被测量时才“坍缩”到某个具体状态。(关于叠加态,后面详说)

  • 量子纠缠

量子纠缠是指两个或多个量子系统之间存在一种特殊的关联,使得对其中一个系统的测量会立即影响到另一个系统的状态,无论它们的距离有多远。量子纠缠是量子计算和量子通信的重要基础。

注:不要问我如何深入理解上述的特性,如果你对量子机制感兴趣,可以去读读费曼教授的物理学讲义,如果你能读懂的话:)。

而量子计算就是建构在量子的上述特性之上的。

1.2.1 量子比特(Qubit)

经典计算机中,信息和操作的基本单位是比特,在量子计算中,信息和操作的基本单位是量子比特(qubit)。不过与经典比特的确定的二元状态(0或1)不同,量子比特处于叠加态(Superposition)

要理解量子计算,首当其冲的就是理解什么是量子比特的叠加态。

注意!注意!烧脑内容即将来袭

学习大学物理时,估计大家都接触过量子力学的皮毛,可能让你印象最深的就是“薛定谔的猫(Schrödinger’s Cat)”!


图来自网络

这是奥地利著名物理学家薛定谔提出的一个思想实验,是指将一只猫关在装有少量镭和氰化物的密闭容器里。镭的衰变存在几率,如果镭发生衰变,会触发机关打碎装有氰化物的瓶子,猫就会死;如果镭不发生衰变,猫就存活。根据量子力学理论,由于放射性的镭处于衰变和没有衰变两种状态的叠加,猫就理应处于死猫和活猫的叠加状态。这只既死又活的猫就是所谓的“薛定谔的猫”。

我们的量子比特就好比那只“薛定谔的猫”,只不过它的状态不是“死”和“活”的叠加态,而是0和1的叠加态。要知道“薛定谔的猫”的最终状态,需要观察者。而要知道一个量子比特的最终状态,需要对其进行测量(measure)

这里有两个概念需要深入理解,一个是0和1的叠加态,另一个则是测量

经典计算机的比特的状态是确定性的,你设置为1,它就是1,你设置为0,它就是0。如果在其生命周期内,你不去修改它,它会一直保持其最初的状态。

但量子比特的状态却不是确定性的,而是概率性的,即量子比特是以概率的形式存在。不过要了解量子比特,我们需要先了解如何表示量子比特,就像我们在经典计算中用二进制数表示经典比特那样。

在量子计算领域,量子比特有两种表示法:狄拉克符号表示法(Dirac notation)和布洛克球(Bloch sphere)几何表示法,下面分别简单介绍一下。

1.2.2 狄拉克符号表示法

狄拉克符号是一种用于表示量子态的数学符号,也称为“凯特尔符号(ket notation)”,这个名称来源于单词“bracket”中的“bra”和“ket”。“Ket”指代右括号,用于量子态的表示,形式为|ψ⟩,其中ψ是量子态的名称或描述。而“Bra”是与“Ket”相对的符号,形式为⟨φ|,用于表示量子态的共轭转置。狄拉克符号的引入极大地方便了量子力学中的数学描述,使得量子态的表示更加简洁和直观。使用这些符号,物理学家可以轻松地进行状态的叠加、内积、外积等操作。

采用狄拉克符号的量子比特的通用状态,即叠加态的表示写法如下:

∣ψ⟩=α∣0⟩+β∣1⟩

其中|0⟩和|1⟩代表了量子比特的两个基本状态:

- |0⟩状态:称为基态(ground state)或零态(zero state)。这是量子比特的最低能量状态,对处于这个能量状态的量子比特进行测量时,它会坍缩为经典比特值0。
- |1⟩状态:称为激发态(excited state)或一态(one state)。这是量子比特的高能量状态,对处于这个能量状态的量子比特进行测量时,它会坍缩为经典比特值1。

而叠加态表示中的α和β是两个复数,且它们满足归一化条件,即它们模的平方和为1,表示在进行测量时,量子比特在状态|0⟩和|1⟩的概率总和为1:

|α|^2 + |β|^2 = 1

α和β也被称为|0⟩和|1⟩态的概率幅

而上面说的基态和激发态则是叠加态的两个特例:

∣ψ⟩= |0⟩ = α∣0⟩+β∣1⟩ = 1∣0⟩ + 0∣1⟩,即此时α=1,β=0;
∣ψ⟩= |1⟩ = α∣0⟩+β∣1⟩ = 0∣0⟩ + 1∣1⟩,即此时α=0,β=1;

还有一种量子比特的状态比较常用,那就是|0⟩状态量子比特通过Hadamard门(稍后会详细说明)生成的均匀叠加态量子比特。这个状态表示该量子比特在测量时有50%的概率得到|0⟩和50%的概率得到|1⟩。该量子比特可以表示为:

∣ψ⟩=(1/√2)|0⟩ + (1/√2)|1⟩

即α = β = 1/√2。而α、β这两个复数的值也可以推断一下,可以是:

α = 1/2 + (1/2)i
β = 1/2 - (1/2)i

也可以是:

α = 1/√2 + 0i
β = 1/√2 + 0i

它们都满足量子比特叠加态的归一化条件。

和任何计算对象一样,量子比特也有其图形化的表示法,即布洛克球。接下来,我们就来说明一下什么是布洛克球。

1.2.3 布洛克球几何表示法

布洛克球(如下图)是一种用于直观理解量子比特状态的表示法。


图来自《Quantum Computation and Quantum Information,10周年版》一书

量子比特的状态可以用球面上的点表示,通常使用极坐标。

如上图所示:

角度θ表示从正Z轴的倾斜角度(0到π),是布洛赫球上的纬度角,决定状态向量在z轴上的投影,描述了比特更接近|0⟩还是|1⟩。

角度ϕ表示在XY平面上的方位角(0到2π),是布洛赫球上的经度角,表示相对相位。不同的ϕ可能不会影响单独测量|0⟩或|1⟩的概率,但会影响量子态之间的干涉效应,因此对量子计算非常重要。

布洛克球的每个点代表一个量子比特的可能状态,其状态可以表示为下面公式:

球的北极(|0⟩)和南极(|1⟩)分别对应量子比特的基态和激发态,而球面上的其他点则表示叠加态。

1.2.4 测量(measure)

量子比特一直处于叠加态,其结果也是不确定的。但我们基于量子比特进行计算的目的是为了得到确定的结果,这就需要对量子比特进行测量。

测量是量子系统与经典系统之间的交互过程,通过这一过程,量子比特的叠加态将坍缩到一个确定的状态(基态0或激发态1)。

由前面的内容我们知道,量子比特的叠加状态是一种概率性的,在量子测量中,并没有一个固定的概率值来决定坍缩为基态或激发态,因此测量结果也是随机的。

测量结果为0的概率(基态)为P(0)=∣α∣^2,测量结果为1的概率(激发态)为:P(1)=∣β∣^2。

如果P(0) >= P(1),量子比特更有可能坍缩为|0⟩(经典比特值为0),反之,量子比特更有可能坍缩为|1⟩(经典比特值为1)。

测量将使得量子比特失去叠加状态,转变为经典状态。这意味着在测量之后量子比特的叠加态特性将不复存在了。

1.2.5 多个量子比特

在经典计算中,单个经典比特只能表示两个状态0和1,要表示更多状态需要多个经典比特。比如如果有两个经典比特,那么会有四种可能的状态:00、01、10和11。8个经典比特可以表示2^8个状态,以此类推。

在量子计算中,我们也可以将多个量子比特放到一起来表示组合状态,这种组合状态可以通过张量积表示和实现。

张量积(tensor product)是数学中一种组合两个向量空间的方法。对于两个复数向量空间A和B,它们的张量积A⊗B创建一个新的向量空间,表示两个空间的所有可能的“组合”。

对于量子比特而言,如果我们有两个量子比特的状态:∣ψ1⟩和|ψ2⟩,它们的组合状态,即张量积可以表示为:

∣ψ⟩ = ∣ψ1⟩⊗ |ψ2⟩

也可表示为|ψ1ψ2⟩ = ∣ψ1⟩⊗ |ψ2⟩

比如一个两量子比特的系统有四个计算基态,由每个量子比特的基态(|0⟩或|1⟩)组合而成,表示为|00⟩、|01⟩、|10⟩和|11⟩。

一对量子比特也可以存在于这四种状态的叠加中,这两个量子比特的量子叠加态|ψ⟩可以表示为下面公式:

|ψ⟩ = a|00⟩ + b|01⟩ + c|10⟩ + d|11⟩

即每种组合的计算基态的叠加,其中的a、b、c、d与前面的单个量子比特的基态的系数一样,都是一个复数,它们同样满足归一化条件,即它们模的平方和为1:

|a|^2 + |b|^2 + |c|^2 + |d|^2 = 1

两个量子比特的叠加态还有一个特殊的名字叫Bell态(Bell state)。由此类推,一个n量子比特的系统将可以表示2^n种状态的叠加,至于测量后会得到哪种状态,那就是随机的了,要看哪种状态的概率更大。

2. 量子门电路

抽象出量子比特的目的是为了运算,经典比特的运算由各种逻辑门电路实现,并通过门电路的组合实现更为强大和复杂的运算能力。量子比特的操作也是由量子门电路实现的。量子计算中的门电路是对量子比特进行操作的基本单元,其作用是对量子比特的状态进行变换。下面我们就来看看都有哪些常见的量子门电路。

2.1 单量子比特门

单量子比特门作用于一个量子比特,改变其状态。

  • Hadamard门(H门)

H门可以将量子比特从基态(|0⟩或|1⟩)转变为均匀叠加态,常用于初始化叠加态,是许多量子算法(如 Grover 和 Shor 算法)的基础:

对于基态|0⟩运用H门:

H|0⟩ = (1/√2)|0⟩ + (1/√2)|1⟩ 

对于基态|1⟩运用H门:

H|1⟩ = (1/√2)|0⟩ - (1/√2)|1⟩
  • Pauli-X门

类似经典计算中的NOT门,可以实现|0⟩和|1⟩的交换,即将|0⟩变为|1⟩,|1⟩变为|0⟩:

X∣0⟩=∣1⟩
X∣1⟩=∣0⟩
  • Pauli-Y门

Pauli-Y门不仅可以像Pauli-X门那样翻转比特的状态,还引入了一个相位因子:

Y∣0⟩=i∣1⟩
Y∣1⟩=−i∣0⟩
  • Pauli-Z门

Pauli-Z门主要负责相位反转。它不会改变|0⟩状态,但会对|1⟩状态施加相位反转。它在量子信息处理中用于引入相位差:

Z∣0⟩=∣0⟩
Z∣1⟩=−∣1⟩
  • S门(相位门)

S门,也称为相位门,能够对量子比特状态施加特定的相位。它只影响|1⟩态的相位,在|1⟩态上施加相位π/2(即i),而不改变|0⟩态。

S∣0⟩=∣0⟩
S∣1⟩=i∣1⟩
  • T门

T门,也称为四分之一相位门,类似于S门,但施加的相位为π/4,即|1⟩态上施加相位π/4,而对|0⟩态没有影响:

T∣0⟩=∣0⟩
T∣1⟩=e^(i*π/4)∣1⟩

S门和T门可以组合使用,形成更复杂的相位操作。例如,S门可以被看作是T门的平方。这些相位门在量子计算中具有重要作用,尤其是在量子态的干涉和量子算法(如量子傅里叶变换)中。

量子态的干涉是量子力学中的一个核心现象,类似于经典波动中的干涉现象。它描述了不同量子态之间相位关系的作用,导致量子态的概率幅相加或相消,从而影响测量结果。

干涉现象可以分为两种类型:

  • 加强干涉(Constructive Interference):当两种或多种量子态的概率幅相位相同或相近时,它们会相互叠加,增强某个测量结果的概率。例如,如果两个量子态均为∣1⟩,则它们的概率幅相加,导致更高的测量概率。
  • 削弱干涉(Destructive Interference):当不同量子态的概率幅相位相反时,它们会互相抵消,降低某个测量结果的概率。例如,如果一个状态为∣0⟩,另一个状态为∣1⟩的相位相反,则它们的叠加会导致测量结果的概率减少。

量子计算中常见的两种算法:Shor算法Grover算法就是利用量子干涉来提高计算效率的。

2.2 双量子比特门

双量子比特门是量子计算中用于处理两个量子比特之间关系的基本操作。这些门能够实现量子比特之间的纠缠(关于这个概念稍后再说)和相互作用,是量子计算的重要组成部分。下面介绍几种常见的双量子比特门:

  • CNOT门(受控-NOT门)

CNOT门(Controlled-NOT Gate)是最常用的双量子比特门之一。它对一个量子比特(目标比特)施加NOT操作,前提是另一个量子比特(控制比特)处于|1⟩状态,具体表现如下(第一个量子比特为控制比特,第二个量子比特为目标比特):

- 输入状态|00⟩,变为 |00⟩
- 输入状态|01⟩,变为 |01⟩
- 输入状态|10⟩,变为 |11⟩
- 输入状态|11⟩,变为 |10⟩

CNOT门能够创建量子比特之间的纠缠,是量子计算中实现量子算法的基础。

  • CZ门(受控-Z门)

CZ门是另一种重要的双量子比特门。它对目标量子比特施加Z门(相位反转)操作,前提是控制量子比特(第一个量子比特)的状态为|1⟩。其具体表现如下:

- 输入状态|00⟩, 变为|00⟩
- 输入状态|01⟩, 变为|01⟩
- 输入状态|10⟩, 变为|10⟩
- 输入状态|11⟩, 变为-|11⟩(施加相位反转)

CZ门用于引入相位关系,也常用于量子纠缠和量子算法中。

  • SWAP门

SWAP门是一种双量子比特门,它的主要功能是交换两个量子比特的状态。具体来说,如果有两个量子比特A和B,SWAP门会将它们的状态互换。

给定输入状态|AB⟩,SWAP门的作用如下:

|00⟩ → |00⟩
|01⟩ → |10⟩
|10⟩ → |01⟩
|11⟩ → |11⟩

我们看到:SWAP门将|0⟩和|1⟩的状态互换,而|00⟩和|11⟩保持不变。

在量子通信中,SWAP门可以用于在不同的量子比特之间交换信息。在量子电路中,SWAP门可以用来重排量子比特的位置,以实现特定的逻辑操作。

接下来,我们再来看看常用的多量子比特门,即三个或三个以上量子比特的门电路。

2.3 多量子比特门

  • Toffoli门(CCNOT门)

Toffoli门是一个三量子比特门,只有在前两个量子比特均为|1⟩时,才对第三个量子比特施加NOT操作。其具体行为表现如下:

- 输入状态|000⟩, 变为|000⟩
- 输入状态|001⟩, 变为|001⟩
- 输入状态|010⟩, 变为|010⟩
- 输入状态|011⟩, 变为|011⟩
- 输入状态|100⟩, 变为|100⟩
- 输入状态|101⟩, 变为|101⟩
- 输入状态|110⟩, 变为|111⟩
- 输入状态|111⟩, 变为|110⟩

Toffoli门也是经典计算的量子对应物,能够实现复杂的逻辑操作,常用于量子纠错和量子算法中。

  • CSWAP门(受控-SWAP门)

CSWAP门是一种受控的操作双量子的比特门,但因为有一个额外的控制量子比特,因此将其纳入多量子比特门一类。和SWAP门无条件交换两个量子比特状态不同,CSWAP门只有在控制量子比特处于|1⟩状态时,才会交换目标量子比特的状态。它可以看作是SWAP门的受控版本。

给定输入状态|CAB⟩,其中C为控制比特,A和B为目标比特,CSWAP门的作用如下:

当C = |0⟩时,|CAB⟩保持不变。
当C = |1⟩时:
    |101⟩ → |110⟩
    |100⟩ → |101⟩
    |011⟩ → |011⟩
    |010⟩ → |010⟩

2.4 特殊组合门

和经典计算的门电路组合一样,通过对上面量子门的组合,我们可以得到一些非常实用的门电路,其中贝尔态门(Bell State Gate)就是一种非常常用的量子门,它的主要功能是将两个量子比特从一个未纠缠的状态转换为一个纠缠状态。常见的实现方式是通过组合Hadamard门和CNOT门来生成贝尔态。贝尔态在量子通信、量子密码学和量子纠缠研究中都有着重要应用。

假设初始态是两个量子比特的分离态∣ψ⟩=∣00⟩,以下步骤可以生成Bell态:

  • 对第一个量子比特应用H门:
H∣0⟩= 1/√2(∣0⟩+∣1⟩)

这之后整体状态变为:

|ψ⟩= 1/√2(∣0⟩+∣1⟩)∣0⟩ = 1/√2(∣00⟩+∣10⟩)
  • 继续应用CNOT门(控制比特为第一个比特,目标比特为第二个比特)

如果控制比特是∣0⟩,目标比特保持不变。

如果控制比特是∣1⟩,目标比特翻转。

CNOT门作用后,状态变为:

|ψ⟩= 1/√2(∣00⟩+∣11⟩)

这就是Bell态!

2.5 量子纠缠态

好,到这里也该说一说之前提到的量子纠缠态了。

一提到量子纠缠,人们通常会想到它的神秘性和非经典特性,尤其是关于量子之间的瞬时关联和信息传递的潜能。这种现象挑战了经典物理的直觉,常常引发人们对量子计算、量子通信和量子隐形传态等前沿技术的兴趣与讨论。同时,量子纠缠也引发了关于量子力学基础的哲学思考,例如关于现实、因果关系和信息本质的深层次问题。

通过前面的学习,我们知道每个量子比特都有自己的状态,可以是初始基态∣0⟩或|1⟩,也可以是叠加态∣ψ⟩=α∣0⟩+β∣1⟩。我们还可以将多个量子比特的状态合并成一个更高维度的复合量子态,这种组合状态可以通过张量积表示和实现。

在量子计算中,量子纠缠也是一种量子态,但其中系统的整体状态无法写成各部分状态的简单张量积。例如,如果两个粒子的状态∣ψ⟩是纠缠态,则意味着我们无法将它分解为如下形式:

∣ψ⟩ =∣ψ1⟩⊗ ∣ψ2⟩ // 这里∣ψ1⟩和∣ψ2⟩分别是量子比特1和量子比特2的单独态。

纠缠态的独特之处在于以下两点:

  • 非局域性:两个粒子即使相距遥远,其状态仍然以某种方式相互关联。
  • 测量相关性:对其中一个粒子的测量结果会即时影响另一个粒子的测量结果。

以上面形成纠缠态的Bell态为例:

|ψ⟩= 1/√2(∣00⟩+∣11⟩)

量子纠缠使得两个比特的状态紧密关联,它表示系统有50%的概率处于∣00⟩,有50%的概率处于|11⟩。

在量子计算中,测量是一个不可逆的过程,它会强制系统状态从叠加态塌缩到与测量结果一致的确定态。在Bell状态下,纠缠的非局域性保证了两个比特始终保持一致,无论测量顺序如何。

测量第一个量子比特后,如果得到的结果是∣0⟩,则整个系统的状态立即塌缩为|00⟩,则第二个量子比特的测量结果也必定是∣0⟩。如果测量第一个量子比特的结果是|1⟩,则整个系统的状态立即塌缩为11⟩,则第二个量子比特的测量结果也必定是∣1⟩。

量子纠缠的测量相关性没有经典的对应物,但可以用下面这个隐喻来帮助理解:

  • 想象一对手套,左手套和右手套随机装进两个盒子,分别送到两个人手中。
  • 如果一个人打开盒子发现是左手套,他立刻知道另一个人拿到的是右手套。

只是与经典类比不同的是,量子纠缠中没有“预先分配”的状态,测量本身创造了这种确定性。

在真实的量子计算机中,量子纠缠已经得到了实现,并且被广泛用作验证量子计算机性能的基础实验之一。通过操纵量子比特,我们能够在单一量子计算机上生成并观察到纠缠态的特性。但这仅限于单台量子计算机中的两个量子比特。

而在远距离的两个量子之间建立纠缠,这是量子通信的核心研究目标。据公开报道,中国科学家已通过光子实现了远距离纠缠分发。中国“墨子号”量子科学实验卫星成功在1200公里的距离上分发了纠缠态光子对,这是量子通信中“量子纠缠分发”的成功案例。

到这里,我们已经介绍了量子计算的常见各种量子比特门电路,而基于上述量子比特门电路来解决经典计算难以高效解决的问题的算法,就被称为量子算法。下面我们再简单介绍一下量子算法的特性以及有哪些常见的量子算法。

3. 量子算法

由于量子比特的“超出经典直觉”的性质,相对于经典计算中的算法,量子算法的理解路径更为“崎岖”,有时候大脑需要一些“天马行空”。

我们以量子计算的经典入门示例算法:多伊奇-乔萨算法为起点,来看一下量子计算算法的一般特点和设计模式。

多伊奇-乔萨算法(Deutsch–Jozsa algorithm)是戴维·多伊奇和理查德·乔萨于1992年提出的一种确定性量子算法,该算法展示了量子算法在特定问题上指数级加速的能力,以及量子算法设计的一般模式。下面我们就来介绍一下该算法。

3.1 Deutsch–Jozsa algorithm

《量子计算和量子信息》一书在介绍这个算法时,使用了一个Alice和Bob的故事来解释,这里我们也借鉴一下,希望能更好的帮助大家理解其核心概念和量子计算的优势。

话说Alice和Bob是一对喜欢挑战逻辑问题的好朋友。某一天,Alice设计了一个“神秘黑箱”(即函数f(x)),可以接收n位二进制输入(例如x = 000, 101, 111),并输出一个二进制结果(0或1)。

但是,Alice做了一些特殊限制:

  • 要么黑箱的输出在所有可能输入上是完全一致的,即f(x)恒为0或1,称为“常值”。
  • 要么黑箱的输出在所有可能输入上是均匀分布的,即对一半输入,f(x) = 0,对另一半输入,f(x) = 1,称为“平衡”。

Alice给Bob的任务是:确定这个黑箱到底是常值还是平衡的

Bob起初考虑使用经典计算机来完成这个任务。他每次输入一个值x,黑箱会返回f(x)。为了判断f(x)是“常值”还是“平衡”,他必须测试多个x:

  • 如果他输入所有2^n个可能值,看到f(x)恒为0或1,他可以确定黑箱是常值。
  • 如果f(x)的输出在2^n个输入中有一半是0,一半是1,他就知道它是平衡的。

但问题是:最坏情况下,Bob需要检查2^(n-1) + 1次(即超过一半的输入),才能确定黑箱的性质!当n很大时(例如n = 100),需要有2^99+1次输入。这样的解决方案,经典计算机无法胜任,显然也会被Alice鄙视。

于是Bob想到用量子计算机来解决这个问题。他发现量子计算可以一次性对所有2^n个输入进行并行处理,并通过量子叠加和干涉提取答案。以下是他用量子计算的步骤:

  • 初始化

Bob将他的量子计算机初始化到以下起始状态:

- n个量子比特(输入),全部设置为基态∣0⟩
- 一个辅助比特(输出),设置为∣1⟩。

按照之前的量子比特联合态,我们可以得出当前初始状态为:

∣0⟩^⊗n ⊗ |1⟩

如果n=2,那么初始状态即为|00⟩|1⟩。

  • 进入叠加态

Bob对所有输入比特(包括辅助比特)施加Hadamard门(H门),使它们进入叠加态:

这一操作使得所有量子比特都进入叠加态,为后续的量子计算步骤奠定了基础。通过这种方式,算法能够有效地并行处理多个输入状态,尝试所有可能性。

  • 黑箱作用

Alice的黑箱被量子化,成为一个量子门,即用一个量子门来实现Alice的神秘黑箱f(x),它将输入态变换为下面状态:

∣x⟩∣y⟩ -> ∣x⟩|y ⊕ f(x)⟩

- ∣x⟩是工作寄存器,表示输入x
- ∣y⟩是辅助寄存器,用于存储函数的输出
-  ⊕ 表示模2加法(XOR),可以用CNOT门实现。

这个操作会根据f(x)的值改变辅助比特的状态(增加一个相位因子)。

f(x)也称为量子计算中的oracle函数,在真实的量子计算中,Oracle 函数通常是根据具体的算法和问题,通过量子门操作实现的。Deutsch–Josza Algorithm 在理论上描述了Oracle函数的行为,但在真实的量子计算中,需要具体设计量子电路来实现该函数。

几乎所有量子算法都有自己的oracle函数,它是量子算法的核心部分。通过精心设计Oracle函数,可以将量子计算应用于各种实际问题,包括优化、搜索和密码分析等领域。

  • 量子干涉(第二次应用H门)

在这一阶段,我们对前n个量子比特再次应用Hadamard门。这个步骤是干涉效应的关键,利用量子干涉增强他所需的信息。

如果当前状态为∣x⟩|y ⊕ f(x)⟩,应用H门后,前n个量子比特的状态会变为:

在应用Hadamard门后,整个量子态变为:

通过数学推导,结果可以证明:如果f(x)是常值,则只有∣x⟩^⊗n的概率幅为非零。如果f(x)是平衡的,则所有其他态的概率幅抵消,只留下非∣x⟩^⊗n的态。

  • 测量

最后,Bob测量输入比特的状态:如果结果是∣0⟩^⊗n,则得出f(x)是常值;如果结果不是∣0⟩^⊗n ,则f(x)是平衡的。

关键是:Bob只需要一次调用黑箱即可完成判断,而不是经典算法的2^(n-1) + 1次调用。

这个算法也代表了量子算法的一般模式,大致都是这样的:

  • 量子叠加:创建所有输入的可能性。
  • 量子黑箱操作:使用Oracle函数,编码问题的特性。
  • 量子干涉:通过相位和概率幅操控,筛选目标答案。
  • 测量:提取结果。

在上面Bob和Alice的故事中,我们提到了量子并行计算,这也是Bob只需要一次调用黑箱即可完成判断的原因,那到底什么是量子并行计算呢?我们继续往下看。

3.2 量子并行

如果说理解叠加态,我们还有概率这个熟知的经典概念可以利用。在理解量子并行性上,我们的大脑只能“天马行空”了。

巧的是,量子并行性的概念也是由David Deutsch(上面多伊奇-乔萨算法的作者)于1985年在一篇开创性论文”Quantum theory, the Church–Turing principle and the universal quantum computer“中首次提出的,并由David Deutsch、Richard Jozsa和Artur Ekert后续进一步发展。普林斯顿大学官网可以免费下载这篇论文

不过即便是近四十年后的今天,对于量子并行这种概念的理解可能还很模糊。在经典计算中,实现并行计算理解起来非常直接,如果我有n个处理器,理论上我就可以在这n个处理器上同时执行n个不同的task。

但在量子计算中,量子化后的Oracle函数究竟是如何“并行处理”n个量子比特的呢?在今年的一篇来自瑞典皇家理工学院Stefano Markidis的预印版论文“What is Quantum Parallelism, Anyhow?”的结论中,作者如是说:

值得注意的是,休·埃弗雷特的多世界解释和多元宇宙假说是最直观和优雅的解释之一(wallace2012emergent;deutsch1998fabric)。根据这一解释,时间被设想为一棵多分支的树,每一个量子并行性的可能结果都在一个单独的分支或宇宙中实现。这一解释表明,每个计算路径在不同的现实分支中同时存在。这一概念与量子并行性的观念相一致,暗示所有潜在的量子计算结果在多个宇宙中并行发生。多元宇宙理论的一个重要含义是,它能够支持超越可观测宇宙中粒子数量(>300个量子比特)的量子并行性。在这样的情况下,多个平行宇宙可以同时容纳在不同分支上展开的计算过程,而不受单一宇宙中的粒子数量限制(deutsch1998fabric)。

好吧!我刚好看完科幻美剧“人生复本”以及同名原著,对上述多重平行宇宙有了一个感性且直观的认知:)。

如果你相信上述引述中的解释,那么所谓量子并行,只是多元宇宙都独立对输入做了一次计算,而对于当前的现实来看,这看起来就是一种“并行”,我们将每个宇宙当做一个“处理器”了!

Stefano Markidis认为:量子并行本质上是量子态相互作用产生的干涉图样:每个量子态都有助于形成集体干涉图样,类似于天线阵列中信号的组合。然而,与多个独立进程同时运行的经典并行不同,量子并行的特点是复杂的干扰网。减少量子并行性的概念强调了量子算法中相长干涉和相消干涉之间的微妙平衡。虽然相长干扰会放大某些计算路径,但相消干扰会选择性地抑制其他计算路径,最终引导系统找到正确的解决方案。并且,传统的量子应用算法通常会经历一个初始阶段,其中它们利用所有可用的并行性、叠加计算、操纵阶段并执行测量。在此初始阶段,量子算法最大化并行性。然而,由于干扰现象,随着应用的进展,并行性会减弱,从而降低了量子并行性。也就是说在任何量子算法中,从经典输入状态产生量子并行性的机制以及减少数据并行性以识别正确答案的机制都是必不可少的。


图来自Stefano Markidis的论文,用天线阵列信号组合的集体干涉来阐释量子并行

不管你是否理解了,或理解了多少,我们都要向下进行了。我们来看看如何用模拟器来实现上面的Deutsch–Jozsa algorithm。

4. Go语言实现量子计算模拟

对于量子计算初学者而言,量子编程语言和模拟器就像是通往量子世界的入口和学习工具。

目前一些大厂提供了专门的量子编程语言以及模拟器甚至量子计算硬件(或者虚拟机)来帮助开发者了解量子计算。主流的语言包括IBM开发的Qiskit(python)、Google的Ciq(python)、微软的Q#(C#)等。量子模拟器方面,IBM Quantum Experience在线量子计算平台、Google Cirq Simulator以及Microsoft Azure Quantum等实验环境,开发者都可以以免费或较低的代价试用和使用。

不过这里我打算用一个知名度没那么高的Go实现的量子计算模拟器,它就是github.com/itsubaki/q这个Go语言量子计算模拟器项目。q是一个用Go语言实现的开源量子计算模拟器,无外部依赖,支持基本的量子逻辑门以及测量,提供了多种量子比特操作以及量子态概率幅计算,适合Go开发者量子计算入门时使用。不过它没有对应的量子计算硬件或虚拟机,无法对接上面提到的大厂的量子计算实验环境。

q项目有两个关键组件,一个是q.Q,这是量子模拟器核心结构,是模拟器的抽象;另外一个则是q.Qubit,是量子比特抽象。下面我们就用q来模拟一下Deutsch–Jozsa algorithm:

// quantum-simulate/deutsch–jozsa/main.go

package main

import (
    "fmt"

    "github.com/itsubaki/q"
)

// 实现常数函数的oracle
func constantOracle(qsim *q.Q, controls []q.Qubit, target q.Qubit) {
    // 对于常数函数,这里什么都不做
    // 因为常数函数要么总是返回0,要么总是返回1
}

// 实现平衡函数的oracle
func balancedOracle(qsim *q.Q, controls []q.Qubit, target q.Qubit) {
    // 对于平衡函数,我们对输入做CNOT操作
    for _, control := range controls {
        qsim.CNOT(control, target)
    }
}

func deutschJozsa(n int, isConstant bool) string {
    // 创建量子模拟器
    qsim := q.New()

    // 创建n+1个量子比特的寄存器
    // n个输入比特加1个输出比特
    qreg := make([]q.Qubit, n+1)
    for i := range qreg {
        qreg[i] = qsim.Zero()
    }

    // 将输出比特置为|1>
    qsim.X(qreg[n])

    // 对所有量子比特应用H门
    for _, qubit := range qreg {
        qsim.H(qubit)
    }

    // 应用oracle
    if isConstant {
        constantOracle(qsim, qreg[:n], qreg[n])
    } else {
        balancedOracle(qsim, qreg[:n], qreg[n])
    }

    // 对输入寄存器应用H门
    for i := 0; i < n; i++ {
        qsim.H(qreg[i])
    }

    // 测量输入寄存器
    result := ""
    for i := 0; i < n; i++ {
        m := qsim.Measure(qreg[i])
        result += m.BinaryString()
    }

    return result
}

func main() {
    // 测试5个输入比特的情况
    n := 5

    // 测试常数函数
    resultConstant := deutschJozsa(n, true)
    fmt.Printf("常数函数的结果: %v\n", resultConstant)
    if resultConstant == "00000" {
        fmt.Println("检测到常数函数!")
    }

    // 测试平衡函数
    resultBalanced := deutschJozsa(n, false)
    fmt.Printf("平衡函数的结果: %v\n", resultBalanced)
    if resultBalanced != "00000" {
        fmt.Println("检测到平衡函数!")
    }
}

前面的量子计算理论知识有助于你理解这段代码,这里简单解释一下。

这段代码模拟实现了Deutsch–Jozsa algorithm,并分别进行了两次不同实现的Oracle函数查询,当然正常的算法只需查询一次即可,这里是为了模拟演示两种不同的情况。

代码首先进行了量子寄存器初始化:创建了n+1个量子比特:n个输入比特和1个输出比特,初始状态都是|0>:

qreg := make([]q.Qubit, n+1)
for i := range qreg {
    qreg[i] = qsim.Zero()
}

然后对输出比特应用Pauli-X门进行翻转,将其转换为|1>状态:

qsim.X(qreg[n])

对所有量子比特应用Hadamard门,将输入比特和输出比特置于叠加态,目的是同时”探测”所有可能的输入组合:

for _, qubit := range qreg {
    qsim.H(qreg[i])
}

查询Oracle函数进行量子并行计算:

if isConstant {
    constantOracle(qsim, qreg[:n], qreg[n])
} else {
    balancedOracle(qsim, qreg[:n], qreg[n])
}

对输入寄存器再次应用H门进行量子干涉:

for i := 0; i < n; i++ {
    qsim.H(qreg[i])
}

测量输入寄存器,根据测量结果判断函数类型:

// 测量输入寄存器
result := ""
for i := 0; i < n; i++ {
    m := qsim.Measure(qreg[i])
    result += m.BinaryString()
}

运行这个程序,你应该能看到如下输出:

$go run main.go
常数函数的结果: 00000
检测到常数函数!
平衡函数的结果: 11111
检测到平衡函数!

注意:我们使用经典计算模拟量子计算,oracle函数并不存在真正的量子并行,从代码也可以看出,是用for循环对每个量子比特顺序处理了一遍来模拟量子并行。

5. 小结

本文探讨了量子计算的基本概念及其与经典计算的关系,包括回顾了经典计算机的基本原理,包括比特、布尔逻辑和门电路模型,并引入了量子计算的核心概念,如量子比特(qubit)、叠加态、量子纠缠等。量子比特的叠加态使其能够同时表示多种状态,显著提升了计算能力。

文章后半部分还以Deutsch–Jozsa这个入门级量子算法为例,介绍了量子算法以及算法的一般模式。并使用github.com/itsubaki/q这个Go语言量子计算模拟器项目模拟实现了该算法,以帮助大家理解。

不过相对于经典计算算法,量子计算算法在理解上依然有很高门槛,文中仅仅以Deutsch–Jozsa这个入门级量子算法举例,像Grover’s search algorithm、Shor’s factoring algorithm等常见的实用量子算法理解起来更有难度。

就目前量子计算机的发展来看,尽管量子计算展现出在特定领域的潜力,但目前对经典计算领域的影响依然不大,更别提无法全面取代经典计算机了。对于普通开发人员来说,可以逐步理解量子计算的概念、思路、算法和编程范式,为以后量子计算成熟打好基础。

不过,量子计算的指数级加速算力能力已经被证实,在密码学领域,科研人员已经发布了可以抵御量子计算破解的密码算法,比如: ML-KEM(之前称为Kyber)德根。这些密码学算法被统称为“后量子密码学算法(Post Quantum Cryptography)”。Go密码学团队已经在标准库中给出了ML-KEM的实现,预计将在Go 1.24版本落地。

本文是我个人学习量子计算的笔记,内容源自我查阅的大量书籍,同时也结合了AI大模型的辅助。由于这是我第一次学习量子计算,加之该领域的内容相对抽象且复杂,因此笔记中可能存在一些错误,敬请谅解。

本文涉及的源码可以在这里下载。

6. 参考资料


Gopher部落知识星球在2024年将继续致力于打造一个高品质的Go语言学习和交流平台。我们将继续提供优质的Go技术文章首发和阅读体验。同时,我们也会加强代码质量和最佳实践的分享,包括如何编写简洁、可读、可测试的Go代码。此外,我们还会加强星友之间的交流和互动。欢迎大家踊跃提问,分享心得,讨论技术。我会在第一时间进行解答和交流。我衷心希望Gopher部落可以成为大家学习、进步、交流的港湾。让我相聚在Gopher部落,享受coding的快乐! 欢迎大家踊跃加入!

img{512x368}
img{512x368}

img{512x368}
img{512x368}

著名云主机服务厂商DigitalOcean发布最新的主机计划,入门级Droplet配置升级为:1 core CPU、1G内存、25G高速SSD,价格5$/月。有使用DigitalOcean需求的朋友,可以打开这个链接地址:https://m.do.co/c/bff6eed92687 开启你的DO主机之路。

Gopher Daily(Gopher每日新闻) – https://gopherdaily.tonybai.com

我的联系方式:

  • 微博(暂不可用):https://weibo.com/bigwhite20xx
  • 微博2:https://weibo.com/u/6484441286
  • 博客:tonybai.com
  • github: https://github.com/bigwhite
  • Gopher Daily归档 – https://github.com/bigwhite/gopherdaily
  • Gopher Daily Feed订阅 – https://gopherdaily.tonybai.com/feed

商务合作方式:撰稿、出书、培训、在线课程、合伙创业、咨询、广告合作。

探索Docker默认网络NAT映射的分配与过滤行为

本文永久链接 – https://tonybai.com/2024/12/05/exploring-nat-mapping-assignment-and-filtering-behavior-of-docker-default-network

在《WebRTC第一课:网络架构与NAT工作原理》一文中,我们对WebRTC的网路架构进行说明,了解到了NAT的工作原理、RFC 3489对NAT的四种传统分类以及较新的RFC 4787中按分配行为和过滤行为对NAT行为的分类。

不过,“纸上得来终觉浅,绝知此事要躬行”,在这篇文章中,我打算选取一个具体的NAT实现进行案例研究(Case Study)。在市面上的NAT实现中,Docker容器的网络NAT绝对是最容易获得的一种实现。因此,我们将把Docker默认网络的NAT实现机制作为本篇的研究对象,探索该NAT的分配行为和过滤行为,以确定Docker默认网络的NAT类型。

为了这次探索,我们首选需要构建实验网络环境。

1. 构建实验环境

Docker默认网络使用NAT(网络地址转换)来允许容器访问外部网络。创建容器时,如果未指定网络设置,容器会连接到默认的”bridge”网络,并分配一个内部IP地址(通常在172.17.0.0/16范围内)。Docker在宿主机上创建一个虚拟网桥(docker0),作为容器与外部网络的接口。当容器尝试访问外部网络时,使用源网络地址转换(SNAT),将内部IP和端口转换为宿主机的IP和一个随机高位端口,以便与外部网络通信。Docker通过配置iptables规则来实现这些NAT功能,处理数据包的转发、地址转换和过滤。

基于上述描述,我们用两台主机来构建一个实验环境,拓扑图如下:

从上图可以看到:我们的实验环境有两台主机:192.168.0.124和192.168.0.125。在124上,我们基于docker默认网络启动一个容器,在该容器中放置一个用于NAT打洞验证的nat-hole-puncher程序,该程序通过访问192.168.0.125上的udp-client-addr-display程序在Docker的NAT上留下一个“洞”,然后我们在125上使用nc(natcat)工具验证是否可以通过这个洞向容器发送数据。

我们要确定Docker默认网络NAT的具体类型,需要进行一些测试来观察其行为。具体来说,主要需要关注两个方面:

  • 端口分配行为:观察NAT是如何为内部主机(容器)分配外部端口的。
  • 过滤行为:检查NAT如何处理和过滤入站数据的,是否与源IP、源Port有关等。

接下来,我们来准备一下验证NAT类型需要的两个程序:nat-hole-puncher和udp-client-addr-display。

2. 准备nat-hole-puncher程序和udp-client-addr-display程序

下图描述了nat-hole-puncher、udp-client-addr-display以及nc命令的交互流程:

三者的交互流程在图中已经用文字标记的十分清楚了。

根据该图中的逻辑,我们分别实现一下nat-hole-puncher和udp-client-addr-display。

下面是nat-hole-puncher的源码:

// docker-default-nat/nat-hole-puncher/main.go

package main

import (
    "fmt"
    "net"
    "os"
    "strconv"
)

func main() {
    if len(os.Args) != 5 {
        fmt.Println("Usage: nat-hole-puncher <local_ip> <local_port> <target_ip> <target_port>")
        return
    }

    localIP := os.Args[1]
    localPort := os.Args[2]
    targetIP := os.Args[3]
    targetPort := os.Args[4]

    // 向target_ip:target_port发送数据
    err := sendUDPMessage("Hello, World!", localIP, localPort, targetIP+":"+targetPort)
    if err != nil {
        fmt.Println("Error sending message:", err)
        return
    }
    fmt.Println("sending message to", targetIP+":"+targetPort, "ok")

    // 向target_ip:target_port+1发送数据
    p, _ := strconv.Atoi(targetPort)
    nextTargetPort := fmt.Sprintf("%d", p+1)
    err = sendUDPMessage("Hello, World!", localIP, localPort, targetIP+":"+nextTargetPort)
    if err != nil {
        fmt.Println("Error sending message:", err)
        return
    }
    fmt.Println("sending message to", targetIP+":"+nextTargetPort, "ok")

    // 重新监听local addr
    startUDPReceiver(localIP, localPort)
}

func sendUDPMessage(message, localIP, localPort, target string) error {
    addr, err := net.ResolveUDPAddr("udp", target)
    if err != nil {
        return err
    }

    lport, _ := strconv.Atoi(localPort)
    conn, err := net.DialUDP("udp", &net.UDPAddr{
        IP:   net.ParseIP(localIP),
        Port: lport,
    }, addr)
    if err != nil {
        return err
    }
    defer conn.Close()

    // 发送数据
    _, err = conn.Write([]byte(message))
    if err != nil {
        return err
    }

    return nil
}

func startUDPReceiver(ip, port string) {
    addr, err := net.ResolveUDPAddr("udp", ip+":"+port)
    if err != nil {
        fmt.Println("Error resolving address:", err)
        return
    }

    conn, err := net.ListenUDP("udp", addr)
    if err != nil {
        fmt.Println("Error listening:", err)
        return
    }
    defer conn.Close()
    fmt.Println("listen address:", ip+":"+port, "ok")

    buf := make([]byte, 1024)
    for {
        n, senderAddr, err := conn.ReadFromUDP(buf)
        if err != nil {
            fmt.Println("Error reading:", err)
            return
        }
        fmt.Printf("Received message: %s from %s\n", string(buf[:n]), senderAddr.String())
    }
}

我们将其编译完打到镜像中去,Makefile和Dockerfile如下:

// docker-default-nat/nat-hole-puncher/Makefile

all:
    CGO_ENABLED=0 GOOS=linux GOARCH=amd64 go build -o nat-hole-puncher main.go
image:
    docker build -t nat-hole-puncher .

// docker-default-nat/nat-hole-puncher/Dockerfile

# 使用 Alpine 作为基础镜像
FROM alpine:latest

# 创建工作目录
WORKDIR /app

# 复制已编译的可执行文件到镜像中
COPY nat-hole-puncher .

# 设置文件权限
RUN chmod +x nat-hole-puncher

执行构建和打镜像命令:

$ make
CGO_ENABLED=0 GOOS=linux GOARCH=amd64 go build -o nat-hole-puncher main.go
$ make image
docker build -t nat-hole-puncher .
[+] Building 0.7s (9/9) FINISHED                                                                                   docker:default
 => [internal] load .dockerignore                                                                                            0.0s
 => => transferring context: 2B                                                                                              0.0s
 => [internal] load build definition from Dockerfile                                                                         0.0s
 => => transferring dockerfile: 265B                                                                                         0.0s
 => [internal] load metadata for docker.io/library/alpine:latest                                                             0.0s
 => [1/4] FROM docker.io/library/alpine:latest                                                                               0.0s
 => [internal] load build context                                                                                            0.0s
 => => transferring context: 2.70MB                                                                                          0.0s
 => CACHED [2/4] WORKDIR /app                                                                                                0.0s
 => [3/4] COPY nat-hole-puncher .                                                                                            0.2s
 => [4/4] RUN chmod +x nat-hole-puncher                                                                                      0.3s
 => exporting to image                                                                                                       0.1s
 => => exporting layers                                                                                                      0.1s
 => => writing image sha256:fec6c105f36b1acce5e3b0a5fb173f3cac5c700c2b07d1dc0422a5917f934530                                 0.0s
 => => naming to docker.io/library/nat-hole-puncher                                                                          0.0s

接下来,我们再来看看udp-client-addr-display源码:

// docker-default-nat/udp-client-addr-display/main.go
package main

import (
    "fmt"
    "net"
    "os"
    "strconv"
    "sync"
)

func main() {
    if len(os.Args) != 3 {
        fmt.Println("Usage: udp-client-addr-display <local_ip> <local_port>")
        return
    }

    localIP := os.Args[1]
    localPort := os.Args[2]

    var wg sync.WaitGroup
    wg.Add(2)

    go func() {
        defer wg.Done()
        startUDPReceiver(localIP, localPort)
    }()

    go func() {
        defer wg.Done()
        p, _ := strconv.Atoi(localPort)
        nextLocalPort := fmt.Sprintf("%d", p+1)
        startUDPReceiver(localIP, nextLocalPort)
    }()

    wg.Wait()
}

func startUDPReceiver(localIP, localPort string) {
    addr, err := net.ResolveUDPAddr("udp", localIP+":"+localPort)
    if err != nil {
        fmt.Println("Error:", err)
        return
    }

    conn, err := net.ListenUDP("udp", addr)
    if err != nil {
        fmt.Println("Error:", err)
        return
    }
    defer conn.Close()

    buf := make([]byte, 1024)

    n, clientAddr, err := conn.ReadFromUDP(buf)
    if err != nil {
        fmt.Println("Error:", err)
        return
    }

    fmt.Printf("Received message: %s from %s\n", string(buf[:n]), clientAddr.String())
}

现在两个程序都就绪了,接下来我们就开始我们的探索。

3. 探索步骤

我们先在192.168.0.125上启动udp-client-addr-display,监听6000和6001 UDP端口:

// 在192.168.0.125上执行

$./udp-client-addr-display 192.168.0.125 6000

然后在192.168.0.124上创建client1容器:

// 在192.168.0.124上执行
$docker run -d --name client1 nat-hole-puncher:latest sleep infinity
eeebc0fbe3c7d56e7f43cd5af19a18e65a703b3f987115c521e81bb8cdc6c0be

获取client1容器的IP地址:

// 在192.168.0.124上执行
$docker inspect -f '{{range .NetworkSettings.Networks}}{{.IPAddress}}{{end}}' client1
172.17.0.5

启动client1容器中的nat-hole-puncher程序,绑定本地5000端口,然后向192.168.0.125的6000和6001端口发送数据包:

$ docker exec client1 /app/nat-hole-puncher 172.17.0.5 5000 192.168.0.125 6000
sending message to 192.168.0.125:6000 ok
sending message to 192.168.0.125:6001 ok
listen address: 172.17.0.5:5000 ok

之后,我们会在125的udp-client-addr-display输出中看到如下结果:

./udp-client-addr-display 192.168.0.125 6000
Received message: Hello, World! from 192.168.0.124:5000
Received message: Hello, World! from 192.168.0.124:5000

通过这个结果我们得到了NAT映射后的源地址和端口:192.168.0.124:5000。

现在我们在125上用nc程序向该映射后的地址发送三个UDP包:

$ echo "hello from 192.168.0.125:6000" | nc -u -p 6000 -v 192.168.0.124 5000
Ncat: Version 7.50 ( https://nmap.org/ncat )
Ncat: Connected to 192.168.0.124:5000.
Ncat: 30 bytes sent, 0 bytes received in 0.01 seconds.

$ echo "hello from 192.168.0.125:6001" | nc -u -p 6001 -v 192.168.0.124 5000
Ncat: Version 7.50 ( https://nmap.org/ncat )
Ncat: Connected to 192.168.0.124:5000.
Ncat: 30 bytes sent, 0 bytes received in 0.01 seconds.

$ echo "hello from 192.168.0.125:6002" | nc -u -p 6002 -v 192.168.0.124 5000
Ncat: Version 7.50 ( https://nmap.org/ncat )
Ncat: Connected to 192.168.0.124:5000.
Ncat: 30 bytes sent, 0 bytes received in 0.01 seconds.

在124上,我们看到nat-hole-puncher程序输出如下结果:

Received message: hello from 192.168.0.125:6000
 from 192.168.0.125:6000
Received message: hello from 192.168.0.125:6001
 from 192.168.0.125:6001

4. 探索后的结论

通过上面的执行步骤以及输出的结果,我们从端口分配行为和过滤行为这两方面分析一下Docker默认网络NAT的行为特征。

首先,我们先来看端口分配行为。

在上面的探索步骤中,我们先后执行了:

  • 172.17.0.5:5000 -> 192.168.0.125:6000
  • 172.17.0.5:5000 -> 192.168.0.125:6001

但从udp-client-addr-display的输出来看:

Received message: Hello, World! from 192.168.0.124:5000
Received message: Hello, World! from 192.168.0.124:5000

Docker默认网络的NAT的端口分配行为肯定不是Address and Port-Dependent Mapping,那么到底是不是Address-Dependent Mapping的呢?你可以将nat-hole-puncher/main.go中的startUDPReceiver调用注释掉,然后再在另外一台机器192.168.0.126上启动一个udp-client-addr-display(监听7000和7001),然后在124上分别执行:

$ docker exec client1 /app/nat-hole-puncher 172.17.0.5 5000 192.168.0.125 6000
sending message to 192.168.0.125:6000 ok
sending message to 192.168.0.125:6001 ok

$ docker exec client1 /app/nat-hole-puncher 172.17.0.4 5000 192.168.0.126 7000
sending message to 192.168.0.126:7000 ok
sending message to 192.168.0.126:7001 ok

而从125和126上的udp-client-addr-display的输出来看:

//125:
./udp-client-addr-display 192.168.0.125 6000
Received message: Hello, World! from 192.168.0.124:5000
Received message: Hello, World! from 192.168.0.124:5000

//126:
 ./udp-client-addr-display 192.168.0.126 7000
Received message: Hello, World! from 192.168.0.124:5000
Received message: Hello, World! from 192.168.0.124:5000

可以看出:即便是target ip不同,只要源ip+port一致,NAT也只会分配同一个端口(这里是5000),显然在端口分配行为上,Docker默认网络的NAT是Endpoint-Independent Mapping类型的

我们再来看过滤行为。nat-hole-puncher在NAT打洞后,我们在125上使用nc工具向该“洞”发UDP包,结果是只有nat-hole-puncher发过的目的ip和端口(比如6000和6001)才可以成功将数据通过“洞”发给nat-hole-puncher。换个端口(比如6002),数据都会被丢弃掉。即便我们没有测试从不同IP向“洞”发送udp数据,但上述过滤行为已经足够让我们判定Docker默认网络的NAT过滤行为属于Address and Port-Dependent Filtering

综合上述两个行为特征,如果按照传统NAT类型划分,Docker默认网络的NAT应该属于端口受限锥形

5. 小结

本文探讨了Docker默认网络的NAT(网络地址转换)行为。我们通过构建实验环境,使用两个自制程序(nat-hole-puncher和udp-client-addr-display)以及nc工具,来测试和分析Docker NAT的端口分配行为和过滤行为。

主要的探索结论如下:

  • 端口分配行为:Docker默认网络的NAT表现为Endpoint-Independent Mapping类型。即无论目标IP和端口如何变化,只要源IP和端口相同,NAT就会分配相同的外部端口。

  • 过滤行为:Docker默认网络的NAT表现为Address and Port-Dependent Filtering类型。只有之前通信过的特定IP和端口组合才能成功穿透NAT发送数据包到内部网络。

基于这两种行为特征,我们可以得出结论:按照传统NAT类型划分,Docker默认网络的NAT属于端口受限锥形(Port Restricted Cone)NAT。

不过,在真正实践中判断一个NAT的类型无需如此费劲,RFC3489给出检测NAT类型(传统四种类别)的流程图

github上也有上述算法的开源的实现,比如:pystun3。下面是利用pystun3检测网络NAT类型的方法:

$docker run -it python:3-alpine /bin/sh
/ # pip install pystun3
/ # pystun3
NAT Type: Symmetric NAT
External IP: xxx.xxx.xxx.xxx
External Port: yyyy

注:这里pystun3的检测结果是多层NAT的结果,并非单纯的Docker默认网络的NAT类型。

本文涉及的源码可以在这里下载 – https://github.com/bigwhite/experiments/blob/master/docker-default-nat


Gopher部落知识星球在2024年将继续致力于打造一个高品质的Go语言学习和交流平台。我们将继续提供优质的Go技术文章首发和阅读体验。同时,我们也会加强代码质量和最佳实践的分享,包括如何编写简洁、可读、可测试的Go代码。此外,我们还会加强星友之间的交流和互动。欢迎大家踊跃提问,分享心得,讨论技术。我会在第一时间进行解答和交流。我衷心希望Gopher部落可以成为大家学习、进步、交流的港湾。让我相聚在Gopher部落,享受coding的快乐! 欢迎大家踊跃加入!

img{512x368}
img{512x368}

img{512x368}
img{512x368}

著名云主机服务厂商DigitalOcean发布最新的主机计划,入门级Droplet配置升级为:1 core CPU、1G内存、25G高速SSD,价格5$/月。有使用DigitalOcean需求的朋友,可以打开这个链接地址:https://m.do.co/c/bff6eed92687 开启你的DO主机之路。

Gopher Daily(Gopher每日新闻) – https://gopherdaily.tonybai.com

我的联系方式:

  • 微博(暂不可用):https://weibo.com/bigwhite20xx
  • 微博2:https://weibo.com/u/6484441286
  • 博客:tonybai.com
  • github: https://github.com/bigwhite
  • Gopher Daily归档 – https://github.com/bigwhite/gopherdaily
  • Gopher Daily Feed订阅 – https://gopherdaily.tonybai.com/feed

商务合作方式:撰稿、出书、培训、在线课程、合伙创业、咨询、广告合作。

如发现本站页面被黑,比如:挂载广告、挖矿等恶意代码,请朋友们及时联系我。十分感谢! Go语言第一课 Go语言精进之路1 Go语言精进之路2 Go语言编程指南
商务合作请联系bigwhite.cn AT aliyun.com

欢迎使用邮件订阅我的博客

输入邮箱订阅本站,只要有新文章发布,就会第一时间发送邮件通知你哦!

这里是 Tony Bai的个人Blog,欢迎访问、订阅和留言! 订阅Feed请点击上面图片

如果您觉得这里的文章对您有帮助,请扫描上方二维码进行捐赠 ,加油后的Tony Bai将会为您呈现更多精彩的文章,谢谢!

如果您希望通过微信捐赠,请用微信客户端扫描下方赞赏码:

如果您希望通过比特币或以太币捐赠,可以扫描下方二维码:

比特币:

以太币:

如果您喜欢通过微信浏览本站内容,可以扫描下方二维码,订阅本站官方微信订阅号“iamtonybai”;点击二维码,可直达本人官方微博主页^_^:
本站Powered by Digital Ocean VPS。
选择Digital Ocean VPS主机,即可获得10美元现金充值,可 免费使用两个月哟! 著名主机提供商Linode 10$优惠码:linode10,在 这里注册即可免费获 得。阿里云推荐码: 1WFZ0V立享9折!


View Tony Bai's profile on LinkedIn
DigitalOcean Referral Badge

文章

评论

  • 正在加载...

分类

标签

归档



View My Stats