什么是量子计算机?用一个简单例子来解释

译者:王亮 
作者:YK Sugi 
原文:http://t.cn/EZAElk0

Hi,大家好!

不久前,我参观了加拿大温哥华的D-Wave Systems公司,这是一家制造前沿量子计算机的公司。

我在那里学到了很多关于量子计算机的知识,所以我写这篇文章来和大家分享我在那里所学到的一些知识。

本文的目的是通过一个简单的例子让你清楚地了解什么是量子计算机。

本文所讲的内容很容易理解,不要求你具备量子物理或计算机科学的知识。

好了,我们开始吧。

什么是量子计算机?

下面用一句话来概括什么是量子计算机:

量子计算机是一种使用量子力学的计算机,它能比普通计算机更高效地执行某些特定的计算。

这句话有很多东西需要解释,所以让我用一个简单的例子来告诉你它到底是什么。

为了解释什么是量子计算机,我首先需要解释一下普通(非量子)计算机。

普通计算机如何存储信息

目前一台普通的计算机是用一系列的0和1来存储信息的。

不同类型的信息,比如数字、文本和图像都可能用这种方式来表示。

0和1系列中的每个单位被称为比特(bit,中文也叫位),因此一比特可以被设置为0或1。

那么量子计算机呢?

量子计算机并不是用比特来存储信息的,而是用一种叫量子比特(qubit,quantum bit的简写,中文也叫量子位)的东西。

每个量子比特不仅能设置为1或0,还可以设置为1和0。但,这究竟是什么意思呢?

让我来用一个简单的例子来解释一下。这是一个拟人的例子,但它依然可以帮助理解量子机算机如何工作。

一个用来理解量子计算机的例子

现在,假设你现在经营一家旅行社,你需要把一群人从一个地方运送到另一个地方。

为了简单起见,不妨假设你现在需要运送的只有3人——Alice,Becky和Chris。

并且假设你为此预定了2辆出租车,你得分清楚谁乘坐哪一辆出租车。

另外,你知道谁和谁是朋友关系,谁和谁是敌人关系。

这里,我们认为她们的关系是这样的:

◇ Alice和Becky是朋友
◇ Alice和Chris是敌人
◇ Becky和Chris是敌人

现在你要将这3个人分配到2辆出租车,并要达到下面的目标:

◇ 最大化共用一辆车的朋友对数
◇ 最小化共用一辆车的敌人对数

译注:朋友/敌人的对数,这里的“对”是单位,不是指数学中的对数。比如“一对”就是两人的意思。

好了,这是这个问题的基本前提。让我们先来思考一下如何用普通计算机解决这个问题。

用普通计算机解决这个问题

为了用普通的非量子计算机来解决这个问题,你首先需要弄清楚如何用比特存储相关的信息。

我们先标识这两辆出租车为出租车#1和出租车#0。

然后,你可以用3个比特表示谁进入哪辆车。

例如,我们可用0和1来表示:

◇ Alice乘坐出租车#0
◇ Becky乘坐出租车#0
◇ Chris乘坐出租车#1

由于每个人都有两个选择,因此有2*2*2=8种组合来把她们分配给两辆车。下面是所有可能的组合:

A | B | C
0 | 0 | 0
0 | 0 | 1
0 | 1 | 0
0 | 1 | 1
1 | 0 | 0
1 | 0 | 1
1 | 1 | 0
1 | 1 | 1

你可以用3个比特来表示这些组合中的任意一个。

计算每个组合的分数

现在,用普通计算机我们如何来判断哪一个组合是最佳组合呢?为此,让我们来定义如何计算每个组合的得分。这个得分将代表每个组合达到前面提到的两个目标的程度:

◇ 最大化共用一辆车的朋友对数
◇ 最小化共用一辆车的敌人对数

让我们简单地这样定义我们的分数:

(给定组合的得分)=(#共用一辆车的朋友对数)-(#共用一辆车的敌人对数)

例如,假设Alice,Becky和Chris都乘坐出租车#0,可以用3个比特表示为111

在这种情况下,只有一对朋友共用一辆车——Alice和Becky。

然而,有两对敌人共用一辆车——Alice和Chris,Becky和Chris。

所以,这个组合的总分是1-2 = -1。

解决这个问题

有了所有这些预设,我们终于可以着手解决这个问题了。

对于一台普通的计算机,要找到最好的组合,你基本上需要遍历所有的组合,看看哪个得分最高。

你可以构建这样一个表格:

A | B | C | Score
0 | 0 | 0 | -1
0 | 0 | 1 |  1 <- 最佳组合之一
0 | 1 | 0 | -1
0 | 1 | 1 | -1
1 | 0 | 0 | -1
1 | 0 | 1 | -1
1 | 1 | 0 |  1 <- 最佳组合之一
1 | 1 | 1 | -1

如你所见,这里有两个正确的组合——001和110,都达到了1分。

这是个相当简单的问题。然而随着越来越多的人参与到这个问题中来,用一台普通计算机就很难解决这个问题。

我们看到,3个人需要遍历8种可能的组合。

如果有4个人呢?在这种情况下,我们需要遍历2*2*2*2 = 16个组合。

对于n个人,我们需要通过2的n次方个组合来找到最佳组合。

所以,如果有100个人,我们需要遍历:

2¹⁰⁰ ~= 10³⁰ = 一百万百万百万百万百万个组合。

要遍历这么多的组合,对普通计算机来说是不现实的。

用量子计算机解决这个问题

我们如何用量子计算机来解决这个问题呢?

让我们回到把3个人分配给2辆出租车的例子。

正如我们前面看到的,这个问题有8种可能的组合:

A | B | C
0 | 0 | 0
0 | 0 | 1
0 | 1 | 0
0 | 1 | 1
1 | 0 | 0
1 | 0 | 1
1 | 1 | 0
1 | 1 | 1

用一台普通计算机,用3个比特,我们一次只能表示其中一个组合——例如001。

然而,使用量子计算机,3个量子比特可以同时表示所有8个组合

关于量子比特这个词的确切含义存在争议,但我的看法是这样的。

首先,检查这3个量子比特中的第一个量子比特。当你同时将它设置为0和1时,就像是创建了两个平行世界。(是的,很奇怪,但随我看下去。)

译注:一个世界相当于一个普通计算机,理解这点很重要。

在平行世界中,其中一个的量子比特被设置为0,另一个的量子比特被设置为1。

现在,如果你把第二个量子比特也设为0和1呢?然后,这就有点像创造了4个平行世界了。

在第一世界中,两个量子比特被设置为00,第二个是01,第三个是10,第四个是11。

类似地,如果你将这三个量子比特都设置为0和1,你就创建了8个平行世界——000,001,010,011,100,101,110和111。

这是一种奇怪的思考方式,但它是解释量子比特在现实世界中的行为的正确方式之一。

现在,当你对这三个量子比特进行某种计算时,你实际上是在同时对这8个平行世界进行同样的计算。

因此,我们可以同时计算所有组合的分数,而不是按顺序遍历所有这些可能的组合。

有了这个特殊的例子,理论上,你的量子计算机可以在几毫秒内找到最好的组合, 即我们之前看到的001或110:

A | B | C | Score
0 | 0 | 0 | -1
0 | 0 | 1 |  1 <- 最佳组合之一
0 | 1 | 0 | -1
0 | 1 | 1 | -1
1 | 0 | 0 | -1
1 | 0 | 1 | -1
1 | 1 | 0 |  1 <- 最佳组合之一
1 | 1 | 1 | -1

实际上,要解决这个问题,你需要让你的量子计算机做两件事情:

◇ 所有可能的组合都用量子比特表示。
◇ 将每个可能的组合转换成分数的函数。在本例中,这个函数计算共用一辆车的朋友对数和敌人对数。

能做这两件事,你的量子计算机将在几毫秒内得出最好的组合。在本例中,最好的组合是分数为1的001或110。

现在,从理论上讲,量子计算机每次运行都能找到最好的解。

然而,实际上,在运行量子计算机时会存在错误。所以,它可能会找到次优解,第三优解,等等。

随着问题变得越来越复杂,这些错误会变得越来越突出。

因此,在实践中,你可能希望在量子计算机上数十次甚至数百次地运行相同的操作,然后从你得到的结果中选出最好的。

量子计算机的计算规模如何

即使有我提到的错误,量子计算机也没有和普通计算机那样的计算规模问题。

当有3个人需要分配给2辆车时,我们需要在量子计算机上执行的操作次数是1。这是因为量子计算机会同时计算所有组合的分数。

当有4个人的时候,操作次数仍然是1。

当有100人的时候,操作次数仍然是1。量子计算机在同一时间计算所有2¹⁰⁰ ~= 10³⁰ = 一百万百万百万百万百万个组合的分数只需一次操作。

正如我之前提到的,在实践中,最好是运行量子计算机几十次或几百次,然后从得到的结果中选出最好的结果。

然而,它仍然比在普通计算机上运行同样的问题并且必须重复同样类型的计算一百万百万百万百万百万次要好得多。

最后

特别感谢D-Wave Systems公司的每个人耐心地向我解释这一切。

D-Wave最近推出了一个与量子计算机交互的云环境。

如果你是一名开发人员,并且想尝试使用量子计算机,使用云环境可能是最简单的方法。

它叫Leap,网址是:

https://cloud.dwavesys.com/leap

你可以免费用它来解决成千上万的问题,而且一旦你注册了量子计算机,他们还提供了手把手的教程。

补充说明:

在本文中,我使用术语“普通计算机”来指代非量子计算机。然而,在量子计算领域,非量子计算机通常被称为经典计算机。