WebRTC第一课:从信令、ICE到NAT穿透的连接建立全流程

本文永久链接 – https://tonybai.com/2024/12/14/webrtc-first-lesson-how-connection-estabish

在上一篇文章《WebRTC第一课:网络架构与NAT工作原理》中,我们介绍了WebRTC的网络架构和NAT的基本概念,学习了WebRTC采用端对端(P2P)的通信模型,知道了NAT(网络地址转换)的概念以及给像WebRTC这样的直接P2P通信带来的挑战。

在实际的网络环境中,建立WebRTC这样的端到端连接的确并非易事。因此,在这篇文章中,我将继续上一篇文章的内容,全面探讨一下WebRTC连接建立的全流程,涵盖信令交换、ICE候选信息采集和选择、NAT穿透的各个关键步骤,希望能给大家理解WebRTC技术栈带去帮助。

1. WebRTC连接建立概览

在深入细节之前,我们先用一个时序图来概览WebRTC连接建立的主要步骤:

注:上图由mermaid生成,对应的脚本在webrtc-first-lesson/part2/process-overview.mermaid。

这个过程可以概括为以下几个主要步骤:

  • 信令交换:客户端通过信令服务器交换必要的连接信息,包括会话描述协议(SDP)数据。
  • ICE候选收集:每个客户端收集可能的连接方式(称为ICE候选)。
  • 候选交换:通过信令服务器交换ICE候选信息。
  • 连通性检查:客户端尝试各种可能的连接方式。
  • 建立P2P连接:选择最佳的连接路径,建立直接的端到端连接。

在这个过程中,我们会涉及到几个关键概念:

  • 信令(Signaling):用于协调通信并交换元数据的过程。
  • ICE(Interactive Connectivity Establishment):一种用于在各种网络情况下协助建立端到端连接的框架。
  • NAT穿透(NAT Traversal):克服网络地址转换带来的通信障碍的技术。

接下来,我们将详细探讨这些概念,并基于这些概念详细说明WebRTC建连的全流程。

我们先来看看信令(Signaling)。

2. 信令:WebRTC连接的基础

WebRTC技术栈中唯一没有标准化的就是信令(Signaling),但信令却又是WebRTC连接的基础和必不可少的部分。

信令是WebRTC中用于协调通信过程的“指令”,它负责在对等端之间交换建立连接所需的元数据,但不会直接传输音视频数据。信令的主要作用包括:

  • 交换会话描述协议(SDP)信息
  • 交换网络配置信息(ICE候选)
  • 协调会话的开始和结束
  • 处理错误和会话状态变化

WebRTC本身并未定义信令协议标准,这主要考虑的是信令的设计与实现依赖于具体应用的需求,同时也有兼容性方面的考虑,比如:使WebRTC能够与现有的通信系统集成。在安全性方面,自定义信令也可以允许应用层来控制如何交换敏感信息。

目前用于WebRTC信令协议实现的常见方案主要包括基于WebSocket的自定义协议、SIP协议(Session Initiation Protocol)以及一些像XMPP(eXtensible Messaging and Presence Protocol)这样的成熟的即时通讯协议等。

就我个人而言,SIP和XMPP这样的传统协议都太重了,协议自身理解起来就有门槛!基于WebSocket的自定义协议,既简单又灵活,适合大多数业务不那么复杂的场景,在本文中,我们的信令协议就基于WebSocket自定义协议来实现。

Why Websocket?用WebSocket承载自定义信令协议的主要原因是几乎所有现代浏览器和后端框架都支持WebSocket,并且它是全双工通信,允许服务器和客户端随时发送消息,并且建立连接后,消息交换的开销也很小。

在设计信令语义时,我们通常会采用“Room”这个抽象模型来管理参与通信的客户端,这与WebRTC常用于互联网音视频应用不无关系。Room模型有助于组织和管理多个参与者,控制消息的广播范围,并可以实现更复杂的通信场景(如多人会议系统)。

下面是基于Room模型设计的信令交互的典型流程:

注:上图由mermaid生成,对应的脚本在webrtc-first-lesson/part2/signaling-room-model-flow.mermaid。

下面对图中几个关键流程做一些简要说明:

  • 房间创建

Client1向SignalingServer发送创建房间的请求,SignalingServer创建房间并返回房间ID给Client1。

  • 客户端加入

Client2使用房间ID向SignalingServer发送加入房间的请求,SignalingServer通知Client1有新客户端加入。SignalingServer向Client2确认加入成功,并返回房间信息。重复相同的过程,Client3也如此加入了房间。

  • WebRTC连接建立(以Client1和Client2为例)

Client1创建Offer并通过SignalingServer向Client2发送Offer,SignalingServer将Offer转发给Client2。Client2创建Answer,并通过SignalingServer向Client1转发Answer。之后,Client1和Client2还会以类似的方式互相交换ICE候选信息,通过SignalingServer进行转发。

注:offer是由发起者(通常是调用方)创建的SDP(Session Description Protocol)消息,表示希望建立的媒体会话的描述。answer是由接收者(通常是被叫方)回复的SDP消息,表示其对offer的响应。SDP中通常包含媒体格式、网络信息、编解码器等详细信息,供双方协商和确认,具体可参考我之前的文章《使用Go和WebRTC data channel实现端到端实时通信》。

  • 客户端离开(以Client2离开为例)

Client2向SignalingServer发送离开房间的请求,SignalingServer通知房间内的其他客户端(Client1 和 Client3)有客户端离开。

  • 房间关闭

Client1(假设是房主)向SignalingServer发送关闭房间的请求。SignalingServer通知剩余的客户端(Client3)房间已关闭。

我们看到:这个流程展示了Room模型在WebRTC信令过程中的典型应用:

  • Room作为一个逻辑单元,管理多个参与者之间的通信。
  • SignalingServer负责转发所有的信令消息,包括房间管理消息和WebRTC相关的SDP和ICE候选信息。
  • 客户端可以动态地加入和离开房间,SignalingServer会及时通知房间内的其他客户端。
  • 房间可以由创建者(通常是第一个加入的客户端)来关闭。

由此来看,支持Room模型的信令服务器要支持房间创建、加入房间、转发Offer和Answer、离开房间、房间关闭等关键API。同时我们也能看出这种模型非常适合于实现多人音视频通话、在线教室、游戏大厅等应用场景,它提供了一种结构化的方式来管理复杂的多方实时通信。

有了信令服务器,WebRTC通信两端就可以交换元信息了,这其中就包含用于建立端到端通信的ICE候选信息。接下来,我们就来看看WebRTC端到端建连的关键流程:交互式连接建立(ICE, Interactive Connectivity Establishment),以及这个过程中可能发生的NAT穿透。

3. ICE、NAT穿透与连接最终建立

ICE是一种用于在NAT(网络地址转换)环境中建立对等连接的协议,它允许两个agent(在RFC8445中用AgentL和AgentR指代,如下图)发现彼此的最佳通信路径,进而完成端到端的连接。


图:ICE典型部署场景(from RFC8445)

在这个过程中,我们还会涉及两个概念,一个是STUN(Session Traversal Utilities for NAT)服务器,一个是ICE Candidiate。

STUN服务器是帮助上述agent(AgentL和AgentR)发现其公网IP地址和端口的服务网元,这对于NAT穿透至关重要。而ICE Candidiate则是agent采集并与对端交换的、可能用于通信的潜在端点地址(IP地址和端口的组合)。

为了更直观的理解,下面我们来看一下通过ICE选择最佳通信路径的一般流程:

注:上图由mermaid生成,对应的脚本在webrtc-first-lesson/part2/ice-protocol-sequence.mermaid。

在信令流程发起和转发Offer/Answer之后,两个端都会开启ICE最佳通信路径选择的流程。

3.1 ICE Candidate Gathering

这第一步就是ICE Candidate Gathering,即收集ICE候选者(端点)信息。

在这个过程中,每个agent收集可能的候选者类型包括如下几种:

  • 主机候选者(Host Candidate)

主机候选者,即本地接口的地址。通过直接使用本地网络接口的IP地址和端口即可获得,比如:192.168.1.2:5000。

  • 反射候选者(Server Reflexive Candidate)

反射候选者是通过STUN服务器查询公网IP地址和端口获得的,比如203.0.113.1:6000。

STUN通常是位于公网的一个服务器,比如最知名的公共stun是Google的“stun:stun.l.google.com:19302”。在收集反射候选者时,Agent(客户端)会向STUN服务器发送Binding Request(绑定请求),STUN服务器会响应一个Binding Response(绑定响应),其中包含客户端的公共IP地址和端口信息。

  • 中继候选者(Relay Candidate)

中继候选者是通过TURN服务器(Traversal Using Relays around NAT)获得的端点地址(在上图中未显示),是在开启中继模式的情况下,由客户端向TURN服务器发送请求以获取中继地址。只有在WebRTC通信双方(AgentL和AgentR)无法直连的情况下(通常是NAT穿透失败导致的),才会使用中继候选者,并通过TURN服务器进行数据中继来实现两端的数据通信。

注:在本文中,我们暂不考虑中继模式。

  • 对端反射候选者(Peer Reflexive Candidates)

严格来说,对端反射候选者并非是在这个环节能获取到的候选者。对端反射是在ICE连接检查过程中动态发现的候选者,只有在连接检查过程中才能发现,且不太可预测,取决于网络拓扑和NAT行为。对比反射候选者,反射后选者是通过STUN服务器发现的。当一个端点向STUN服务器发送请求时,STUN服务器会回复该端点在公网上的IP地址和端口。而对端反射候选者是在两个端点尝试直接通信时发现的。当一个端点通过其已知的候选者(如主机候选者或反射候选者)向另一个端点发送数据时,如果成功到达,接收端会发现一个新的、之前未知的远程地址。这个新发现的地址就成为了对端反射候选者。

在ICE候选者信息收集的过程中,两端的Agent还要通过定期发送的STUN Binding请求,确保收集到的ICE反射/中继候选者信息在连接建立期间保持有效。这个过程在RFC 8445中被称为“Keeping Candidates Alive”,它可以帮助检测网络环境的变化,比如IP地址或端口的变化。通过定期的STUN请求,ICE可以确保候选者在NAT设备中的映射保持活跃,避免因长时间没有通信而被关闭。

3.2 Candidate Priorization

两端的Agent在收集完候选者信息后,会通过信令服务器交换他们收集到的候选者信息,这个流程在前面的信令交互流程图中也是有的,是信令协议要支持的功能的一部分。

一旦ICE Candidate Gathering以及candidate交换结束,两端的agent会对自己收集到的candidate以及收到的对端的candidate信息进行”Candidate Priorization”,即对自己收集到候选者集合和交换得到的对端候选者集合分别按优先级进行排序。

RFC8445中给出推荐的候选者的优先级公式如下:

priority = (2^24)*(type preference) +
           (2^8)*(local preference) +
           (2^0)*(256 - component ID)

在公式中有三个名词:type preference、local preference和component ID。下面分别介绍一下这三个名词的含义:

  • type preference

Type preference一个表示候选者类型优先级的值。不同类型的候选者会被赋予不同的type preference值,以反映它们在ICE过程中的相对重要性。

它的取值范围通常是0到126之间的整数,值越大,优先级越高。 RFC8445中常见候选者类型及其推荐值如下:

主机候选者 (Host candidates): 126
反射候选者 (Server Reflexive candidates): 100
对端反射候选者 (Peer Reflexive candidates): 110
中继候选者 (Relay candidates): 0

通过不同类型的候选者的推荐值,我们也能看出:主机候选者 > 对端反射候选者 > 反射候选者 > 中继候选者。

注:Peer Reflexive candidates被赋予比Server Reflexive candidates更高的优先级,前面提过,是因为它不是在ICE候选者收集阶段就能发现的,而是在后面的连接检查阶段才能发现,因此可能代表更直接的连接路径。

  • local preference

local preference是一个表示本地优先级的数值,其取值范围0~65535。这个值由本地ICE agent根据自己的策略来设置。

RFC 8421(Guidelines for Multihomed and IPv4/IPv6 Dual-Stack Interactive Connectivity Establishment (ICE))进一步补充了关于local preference的使用建议,特别是在多宿主和双栈(IPv4/IPv6)环境下。建议为IPv6候选地址分配比IPv4更高的local preference值,比如:IPv6地址可以分配65535(最高优先级),IPv4地址可以分配65535-1=65534(次高优先级)。在多宿主(Multihomed)环境中,可以根据网络接口的特性(如带宽、延迟、成本等)来分配不同的local preference值。

注:多宿主环境(Multihomed)指的是一个设备或系统通过多个网络接口连接到网络的情况。这些接口可以连接到同一个网络,也可以连接到不同的网络。多宿主环境下,每个网络接口都可能产生多个ICE候选者,需要为不同接口的候选者分配合适的优先级,可能需要考虑不同网络接口的特性(如带宽、延迟、成本)。

  • Component ID

Component ID用于区分同一媒体流中的不同组件。在ICE中,一个媒体流可能包含多个组件,例如RTP和RTCP。Component ID通常是从1开始的连续整数。在公式中使用(256 – component ID)是为了确保值较小的component ID得到较高的优先级。RTP组件通常被赋值为1,RTCP组件(如果存在)通常被赋值为2。Component ID在优先级计算中的作用相对较小,主要用于在其他因素相同的情况下,为同一流的不同组件提供细微的优先级区分。

下面我们用一个示例来演示一下候选者计算优先级的过程。示例将展示一个ICE agent如何计算自己的candidates和对端candidates的优先级。我们假设这是一个音频流的情况,涉及RTP组件。假设我们有两个agent:AgentL和AgentR,我们将关注AgentL的视角。

AgentL的收集的候选者集合如下:

Host candidate (IPv4): 192.168.1.10:50000
Server Reflexive candidate: 203.0.113.5:50000
Relay candidate: 198.51.100.1:50000

AgentL通过信令交换获得的AgentR的候选者集合如下:

Host candidate (IPv6): 2001:db8::1:5000
Host candidate (IPv4): 192.168.2.20:5000
Server Reflexive candidate: 203.0.113.10:5000

上面优先级计算公式中各个参数值选择如下:

Type preferences:

- Host: 126
- Server Reflexive: 100
- Relay: 0

Local preferences:

- IPv6: 65535
- IPv4: 65534

Component ID: 1 (RTP)

下面是AgentL的候选者优先级的计算过程:

- Host (IPv4): (2^24) * 126 + (2^8) * 65534 + (256 - 1) = 658871
- Server Reflexive: (2^24) * 100 + (2^8) * 65534 + (256 - 1) = 658195
- Relay: (2^24) * 0 + (2^8) * 65534 + (256 - 1) = 655595

AgentR的候选者优先级(从AgentL的角度计算)计算过程:

- Host (IPv6): (2^24) * 126 + (2^8) * 65535 + (256 - 1) = 658881
- Host (IPv4): (2^24) * 126 + (2^8) * 65534 + (256 - 1) = 658871
- Server Reflexive: (2^24) * 100 + (2^8) * 65534 + (256 - 1) = 658195

最终优先级排序(从高到低):

AgentR: Host (IPv6) - 658881
AgentR: Host (IPv4) - 658871
AgentL: Host (IPv4) - 658871
AgentR: Server Reflexive - 658195
AgentL: Server Reflexive - 658195
AgentL: Relay - 655595

这个优先级排序将用于指导下一阶段的ICE连接检查(ICE Connectivity Checks)顺序,但最终的连接选择还会考虑连接检查的结果。在实际场景中,可能会有更多的候选者,包括不同网络接口的多个Host候选者等等。

3.3 ICE Connectivity Checks

有了两端的候选者集合以及优先级值后,两个Agent就可以进入下一阶段ICE Connectivity Checks(连接检查)了。

连接检查实际也可以划分为三个阶段,我们逐一来看一下。

3.3.1 确定角色(Determining Role)

在 WebRTC 的 ICE(Interactive Connectivity Establishment)连接过程中,角色的确定对于连接检查非常重要。ICE 的角色分为两种:控制方(Controlling)和被控方(Controlled)。这些角色用于决定在多个候选路径中选择哪一条作为最终的连接路径。控制方(Controlling Agent) 负责最终选择使用哪个候选对进行通信,而受控方(Controlled Agent)则需遵循控制方的决定。

在offer/answer的信令模型中,通常发起offer的一方会被指定为控制方,而应答(answer)的一方会成为受控方。有时可能会出现两个agents都认为自己是控制方的情况。ICE提供了解决这种冲突的机制:每个agent生成一个随机数(称为tie-breaker),当发现冲突时,比较tie-breaker,tie-breaker较大的agent成为控制方。

ICE(Interactive Connectivity Establishment)连接检查是由控制方和被控方的两个ICE agent同时进行的。两者会各自发起连接检查,以确保双方能够建立有效的连接。控制方通过在检查中包含USE-CANDIDATE属性来提名(Nomination)候选对。

在某些情况下,角色可能会在ICE过程中切换,比如如果发现角色冲突并解决冲突后,又比如在ICE重启(restart)的特定场景下。

3.3.2 形成检查列表(Forming checklist)

通信的双方,无论是控制端还是被控端都会独立形成自己的检查列表。

检查列表是所有可能的候选者对(Candidate Pair)的组合。让我们结合上面的示例,详细说明这个过程。

在我们的例子中,以AgentL为例,每个本地候选与每个远程候选会形成一对,这里会形成9个候选者对:

(L-Host, R-Host-IPv6)
(L-Host, R-Host-IPv4)
(L-Host, R-Server-Reflexive)
(L-Server-Reflexive, R-Host-IPv6)
(L-Server-Reflexive, R-Host-IPv4)
(L-Server-Reflexive, R-Server-Reflexive)
(L-Relay, R-Host-IPv6)
(L-Relay, R-Host-IPv4)
(L-Relay, R-Server-Reflexive)

根据之前计算的优先级,对候选对对优先级进行计算,并按从高到底进行排序。RFC8445中给出了候选者对优先级计算的公式:

// Let G be the priority for the candidate provided by the controlling agent.
// Let D be the priority for the candidate provided by the controlled agent.
pair priority = 2^32*MIN(G,D) + 2*MAX(G,D) + (G>D?1:0)

具体的计算过程这里就不体现了,排序后的检查列表可能如下:

(L-Host, R-Host-IPv6)
(L-Host, R-Host-IPv4)
(L-Server-Reflexive, R-Host-IPv6)
(L-Server-Reflexive, R-Host-IPv4)
(L-Host, R-Server-Reflexive)
(L-Server-Reflexive, R-Server-Reflexive)
(L-Relay, R-Host-IPv6)
(L-Relay, R-Host-IPv4)
(L-Relay, R-Server-Reflexive)

AgentR(被控方) 也会形成自己的检查列表,与AgentL类似,但AgentR并不主动选择最终的路径。

有了排序后的候选者对后,我们接下来便可以执行连接检查了,AgentL和AgentR会各自执行自己的检查。

3.3.3 执行连接检查(Performing Connectivity Checks)

我们以AgentL为例,看看执行连接检查的主要步骤。

AgentL开始按照检查列表的顺序(优先级由高到低)发送STUN Binding请求:

  • AgentL向R-Host-IPv6发送STUN Binding请求;
  • 如果第一个检查失败或超时,AgentL会继续向第二个候选者对的R-Host-IPv4发送STUN Binding请求;
  • 如果失败,继续下一个候选对…,依次类推

同时,AgentR也会执行类似的过程,按照他自己的检查列表发送自己的STUN Binding请求。

当AgentL收到STUN Binding响应时,可能有以下几种可能:

  • 如果是成功的响应,这个候选对被标记为有效。
  • 如果响应来自一个未知地址,创建一个新的Peer Reflexive候选。

之后,AgentL便会更新候选列表,将新候选与所有远程候选配对,形成新的候选对,并根据ICE优先级算法重新排序检查和更新检查列表。AgentL还可能对新形成的候选对立即开始连接性检查。

3.3.4 NAT穿透与最终候选路径的形成

如果两端都在NAT后面,那么Peer Reflexive候选者就是NAT穿透的关键!我们结合下图详细说说ICE过程是如何一步步的选出由新发现的Peer Reflexive组成的最终候选路径的。

注:上图由mermaid生成,对应的脚本在webrtc-first-lesson/part2/ice-nat-traversal-sequence.mermaid

图中使用A、B作为两个端点,通过stun服务器获取的反射候选为A’和B’,通过连接检查阶段发现的对端反射候选(Peer Reflexive)分别为A”和B”。接下来,我们详细说明一下图中流程。

  • ICE候选收集阶段

端点A和B都收集主机候选。A和B都通过各自的NAT向STUN服务器发送请求,获取服务器反射候选(A’和B’)。

  • 候选交换

A和B交换各自的候选列表,包括主机候选和反射候选(A’和B’)。

  • 连接检查开始

A向B的反射候选B’发送STUN绑定请求,这个请求经过A的NAT和B的NAT。

B收到请求后,发现源地址(A”)与A提供的候选(A’)不匹配,因此创建一个新的Peer Reflexive候选A”。

B通过NAT链回复STUN绑定响应。

A收到响应后,从响应中的XOR-MAPPED-ADDRESS字段获知并创建自己的Peer Reflexive候选A”。

注:STUN协议中的XOR-MAPPED-ADDRESS字段可用于帮助对等方(peer)在ICE连接检查阶段找到自己的Peer Reflexive地址。

  • B也向A发送STUN绑定请求

类似的过程在反向发生。A创建B的Peer Reflexive候选B”。B从A的响应中获知并创建自己的Peer Reflexive候选B”。

  • 更新候选对和继续检查

A和B都更新各自的检查列表,包括新的(A”, B”)对。

  • 选择最佳路径

最终,(A”, B”)被选为最佳路径,实现双向NAT穿透。

一旦选定了最佳候选者对,ICE过程就结束了,可以开始实际的数据传输。

3.4 ICE重启

最后我们简单说说ICE重启(restart)。ICE restart提供了一种在不中断现有应用会话的情况下重新建立和优化网络连接的机制。这通常是因为网络条件发生了变化或者需要切换到更优的连接路径。下面序列图展示了ICE重启的基本流程:

注:上图由mermaid生成,对应的脚本在webrtc-first-lesson/part2/ice-restart-sequence.mermaid

ICE restart可能由多种原因触发,如网络变化、切换到更优路径、或解决连接问题。任何一方都可以发起ICE restart。

和前面的ICE流程不同之处在于重启时,发起restart的一方会生成新的ICE ufrag和password。这些新的凭证用于区分新的ICE会话和旧的会话。

之后的流程就和正常的ICE交互选出最优通信路径没有太大区别了!这里也就不重复说明了。

注:ICE restart不一定会改变控制方(controlling)和受控方(controlled)的角色。通常情况下,原有的角色分配会被保持。

4. 小结

在这篇文章中,我们深入探讨了WebRTC连接建立的全流程,涵盖了以下关键概念:

  • 信令:我们讨论了信令的重要性,并了解了基于Room抽象的常见的信令服务器模型;
  • ICE框架:我们学习了ICE候选信息的收集、交换以及连接检查;
  • NAT穿透:我们在ICE连接检查过程中,详细说明了ICE是如何实现NAT穿透并选出最终最优的通信路径的。

在实际生产应用中,我们可能还需要考虑以下几点:

  • 连接建立优化:可以通过使用ICE Lite、预先收集候选信息等方式来加速连接建立过程。
  • 安全性考虑:在生产环境中,应该使用HTTPS和WSS来保护信令通道。
  • 错误处理和重连:实际应用中需要处理各种可能的错误情况,并实现自动重连机制。

在接下来的系列文章中,我将用一个相对完整的演示示例来展示WebRTC应用端到端建连的所有细节(通过TRACE级别日志),希望通过这些细节的分析能帮助大家更好地理解WebRTC的建连过程。

本文涉及的Mermaid源码在这里可以下载到 – https://github.com/bigwhite/experiments/blob/master/webrtc-first-lesson/part2

5. 参考资料


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

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

量子计算入门与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

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

如发现本站页面被黑,比如:挂载广告、挖矿等恶意代码,请朋友们及时联系我。十分感谢! 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