@sambodhi
2018-11-02T08:42:31.000000Z
字数 3967
阅读 2206
一个简单的案例看懂量子计算机
作者|YK Sugi
译者|Sambodhi
编辑|Vincent
AI 前线导读：量子计算机是一种使用量子逻辑进行通用计算的设备。不同于电子计算机（或称经典计算机），量子计算用来存储数据的对象是量子比特，它使用量子算法来进行数据操作。对于没有相关背景的人们来说，要理解量子计算机的工作原理并不容易。不过，YK Sugi 前不久参观了 D-Wave Systems 公司，回来给我们分享了他对于量子计算机的最基本的认识，他使用了一个非常简单的例子来讲解，通俗易懂。D-Wave Systems 于 2011 年 5 月 11 日发布了一款号称 “全球第一款商用型量子计算机” 的计算设备“D-Wave One”。
前几天，我参观了位于加拿大温哥华的 D-Wave Systems（https://www.dwavesys.com），这是一家制造尖端量子计算机的公司。
我在那里学到了很多关于量子计算机的知识，所以我想在这篇文章中与读者们分享我在那里学到的一些东西。
本文的目的是通过一个简单的例子让读者们准确地了解什么是量子计算机。
本文不要求读者具备量子物理或计算机科学的先验知识才能理解它。
好了，我们开始吧。
什么是量子计算机？
下面是量子计算机的一句话总结：
量子计算机是一种使用量子力学的计算机，因此它能比普通计算机更有效地执行某些类型的计算。
在这句话中有许多东西需要解释，所以让我用一个简单的例子来告诉你它究竟是什么。
为了解释什么是量子计算机，我需要先解释一下普通（非量子）计算机。
普通电脑是如何储存信息的
现在，一台普通的计算机以 0 和 1 的序列来存储信息。
不同类型的信息，如数字、文本和图像都可以用这种方式表示。
这个由 0 和 1 组成的序列中的每个单元都被称为比特（亦称位元）。所以，一个比特可以设置为 0 或 1。
那么量子计算机呢？
量子计算机不使用比特来存储信息。相反，它使用的是称为量子比特的东西。
每个量子比特不仅可以设置为 1 或 0，还可以设置为 1 和 0，但这究竟意味着什么呢？
让我用一个简单的例子来解释一下，这是一个有些人为因素的例子。但它仍然有助于理解量子计算机是如何工作的。
量子计算机工作原理示例
现在，假设你经营一家旅行社，你需要把一群人从一个地方带到另一个地方。
为了简单起见，假设您现在只需要带三个人：Alice、Becky 和 Chris。
假设你为此预定了两辆出租车，你想知道谁上了哪辆出租车。
另外，假设你得到了关于谁和谁是朋友，谁和谁是敌人的信息。
现在，我们假设如下：
- Alice 和 Becky 是朋友；
- Alice 和 Chris 是敌人；
- Becky 和 Chris 是敌人。
假设你的目标是将这三个人分成两组乘坐出租车来实现以下两个目标：
- 以尽量多地增加共乘同一辆车的朋友对的数量；
- 以尽量少地减少共乘同一辆车的敌人对的数量。
这些就是这个问题的基本前提。让我们首先思考，如何使用普通计算机来解决这个问题。
普通电脑如何解决这个问题
要使用普通的非量子计算机解决这个问题，首先我们要弄清楚如何用比特存储相关信息。
我们把这两个出租车命名为 Taxi #1 和 Taxi #0。
然后，你可以用 3 个比特表示谁上了哪辆车。
例如，我们可以将三个比特设置为0、0、1 表示：
- Alice 上了 Taxi #0；
- Becky 上了 Taxi #0；
- Chris 上了 Taxi #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 都乘坐 Taxi #1。用 3 个比特，可以表示为 111。
在这种情况下，只有一对朋友共乘同一辆车：Alice 和 Becky。
然而，在这种情况下有两对敌人共乘同一辆车：Alice 和 Chris，以及 Becky 和 Chris。
所以，这个配置的总分是 1-2 = -1。
解决问题
有了这些设置，我们终于可以着手解决这个问题了。
对于一台普通计算机来说，要找到最佳配置，你基本上需要遍历所有配置，看看哪个达到了最高分。
你可以这样构建一个如下所示的表格：
| A | B | C | 得分 | |
|---|---|---|---|---|
| 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³⁰ = 1,000,000,000,000,000,000,000,000,000,000 种配置（1 后面跟 30 个 0）。
若使用普通计算机，则根本无法解决这个问题。
量子计算机如何解决这个问题？
我们如何用量子计算机来解决这个问题呢？
好好想一想，让我们回到把 3 个人分乘两辆出租车的那个例子。
正如我们之前看到的，这个问题有 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。
这种思考方式确实非常奇怪，但它却能正确解释量子比特在现实世界中的行为方式。
现在，当你对这 3 个量子比特进行某种计算时，实际上，你是同时在所有这 8 个并行世界中进行同样的计算。
因此，我们可以同时计算所有解决方案的得分，而不是按顺序遍历所有这些可能的解决方案。
有了这个特殊的例子，理论上，你的量子计算机可以在几毫秒内找到最佳解决方案之一。正如我们之前看到的，这里是 001 或 110。
| A | B | C | 得分 | |
|---|---|---|---|---|
| 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 个人需要分乘两辆车时，我们需要在量子计算机上执行的操作数为 1。这是因为量子计算机同时计算所有配置的分数。
当有 4 个人的时候，操作数仍然为 1。
当有 100 人的时候，操作数仍然为 1。通过单次操作, 量子计算机同时计算所有2¹⁰⁰ ≈ 10³⁰=1,000,000,000,000,000,000,000,000,000,000 种配置的分数。
正如我之前提到的，在实践中，最好是运行量子计算机几十次或几百次，然后从得到的结果中选出最佳结果。
但是，与其普通计算机上运行同样的问题，并且必须重复同样类型的计算执行 10³⁰次相比，量子计算机要好得多。
结语
在本文即将结束时，我要特别感谢 D-Wave Systems 公司耐心为我解释了所有心头疑问。
D-Wave 最近推出了一个与量子计算机交互的云环境。
如果你是一名开发人员，并且想尝试使用量子计算机，那么这就可能是最简单的方法。
这种云环境叫做 Leap，网址为 https://cloud.dwavesys.com/leap ，你可以免费使用它来解决成千上万的问题。而且你一旦注册了账户，它们还会给你提供易于学习的量子计算机入门的教程。
补充说明：
- 在本文中，我使用术语 “普通计算机” 来指代非量子计算机。然而，在量子计算领域中，非量子计算机通常被称为经典计算机。
