姜咏江 邮箱：accsys@126.com

关键词：量子计算机 并行计算器 SAT SPU

1 前言

理论上量子计算机能够同时计算2ⁿ个数据，但结果需要概率处理。实现量子计算机任重而道远。能不能在传统计算机的基础上，设计出可以同时计算同量子计算机一样多的数据？这是可以做到的。

本文向读者介绍一个实用的带有并行运算器SPU(SAT Process Unit)的计算机。该机虽然结构基本，但完全可以实现传统计算机的各种计算，同时又能够实现并行计算，完成传统计算机不能完成的工作，达到了量子计算机所能达到目标。

2 仿量子计算机结构

仿量子计算机的基本结构如图 1所示。MU是存储单位，其包含以程序数据为中心的各种存储环境设备。PU是顺序运算器，负责处理传统程序顺序执行的运算。SPU是同时并行运算器，负责2ⁿ个二进制数据的运算。

                                      图 1 仿量子计算机结构

3 指令系统

这台仿量子计算机的指令系统如表 1所示。其中Da是累加器，X是通用寄存器，Dram是数据存储器，Iram是程序存储器，Ptr是通用指针，ccq是并行运算合成器。本机指令采用16位的精简指令系统编码，指令代码占据高6位。

表 1 仿量子计算机指令系统

4 并行计算实例

为了直观通俗一点说明仿量子计算机的特点，我们以数据密码锁和SAT问题来说明。

4.1  数据密码锁

通信中直接传送密钥是一个很危险的事情。用下面的数据密码锁可以增强保密性。数据密码锁是将密码隐藏在一组看似杂乱无章的数据中，需要通过特殊的处理方法，才能够将密码找出来。当数据密码锁变量相当多时，短时间根本无法找出隐藏的密码。因此，数据密码锁既可以作为隐蔽的密码传送工具，又可以担当数据锁，确保重要数据的安全。

数据密码锁的制作简单，可以根据需要来设置密码的长短。再者本身是一组数据，可以实现明码传输，可以利用现有的数据通信方式，传输适时变动密码，特别是加密数据的密钥传输极为方便。

下面表1是一个数据密码锁，隐藏着9位的密码。用这个密码锁可以控制任何操作通路。数据密码锁工作原理非常简单：当数据密码锁中每行的数据，都至少有一个数码与输入变量的值的对应数码相同时，锁就打开；只要有一行不满足这个条件，锁就不开。

此锁隐藏的密码是101011011。读者可以试试，输入这个9位二进制数给x₈~x₀，寻找列变量值与表中数码相同的行，将其消去。如果全部行数据都消去了，那么输入的数就是密码，就可以开锁。

表1中我们在输入密码行，输入101011011，然后逐行检查那些满足消去条件的行。含有x₈=1的行有2、3、4、5、7行，将这些行消去。满足第二个数码0的行，剩下的行只有8、9这两行。以此类推，最终可将所有的行数据消去，则表明输入的变量值是这个数据密码锁的密码。

表 2   数据密码锁

如果输入不是该锁的打开密码，那么就会有的数据行无法消去。例如，令x₃=0，则如表3所示，通过消去的方法，会有剩余行数据不能被消去。这表明输入的变量值不是数据密码锁承载的密码。本例隐藏的密码是唯一的，故而除了101011011都不可能将锁打开。

假设数据密码锁打开输出“高电位1”，打不开输出“低电位0”，那么就可以用其输出控制任何开关线路。如果传输密钥，则可以直接将数据密码锁送出。接收方可以使用仿量子计算机破解软件，短时间找到隐藏其中的密钥。

表 3  输入其它变量值测试

破解数据密码锁中的密钥，一般化是一个指数时间复杂度的过程。需要用量子计算机或仿量子计算机，才能在短时间完成这项工作。

目前，庞大而复杂的量子计算机距离应用尚远，而仿量子计算机业已成熟。破解数据密码锁中隐藏的密钥，不成问题。

4.2  逻辑电路可靠性问题

并行计算比较典型的例子是逻辑电路可靠性检测问题（SAT问题）。由于数字电路检测点很多，需要通过Tsyetin变换转化成合取范式，然后求出合取范式的满足解。用传统计算机求满足解，当合取范式中的变量较多时，机器运行时间不可忍受。如果用同时可以计算2ⁿ个数据的运算器SPU，才能在短时间内求出合取范式的满足解。

4.2.1  Tsyetin变换

下面给出Tsyetin变换公式及二进制限位数表示方法。

逻辑门电路可以变换成合取范式，这些变换公式如表 4所示。当这些合取范式值为1时，就说明对应的门电路可靠。

表 4  Tsyetin变换

图 2是设置了检测点的逻辑电路，用Tsyetin变换可以转化成合取范式CNF。

                      图 2 逻辑电路检测点

以下规定x’是x的非，加号是逻辑或运算符，与运算符省略。图1中逻辑电路检测点经过Tsyetin变换得到的合取范式为：

CNF=(x₁+x₄)(x₁’+x₄’)(x₄+x₅’)(x₂+x₅’)(x₂’+x₅+x₄’)(x₂+x₆)(x₇’+x₁)(x₆+x₇’)(x₁’+x₆’+x₇)(x₂+x₈)(x₂’+x₈’)(x₈+x₉’)(x₃+x₉’)(x₃’+x₈’+x₉)(x₅’+x₁₀)(x₇’+x₁₀)(x₅+x₇+x₁₀’) (x₉’+x₁₁)(x₁₀’+x₁₁)(x₉+x₁₀+x₁₁’)x₁₁                                                              (1)

可以用0表示变量否定，1表示变量肯定。这个合取范式的表示如表 5所示。其中每一行叫子句，变量相同的子句形成子句块。

表 5  二进制表示的CNF

4.2.2  子句消去法

从公式（1）可以看出，只要子句有变量值能够和表 5中对应数码相同，那么这个子句的逻辑值就是1，这样就可以在求CNF=1的问题中，将这个子句消去。如果找到一组变量值，对每个子句都会至少有一个数码与它的变量值相同，那么这组值就是这个CNF=1的满足解。

满足解的实际意义在于，当逻辑电路输入端输入那些已知值时，其余各检测节点的值刚好也是满足解的变量值，那么电路的逻辑结果是真，是可靠的，反之电路就不可靠。

5 并行计算理论基础

利用子句消去法，如果子句的一个数码与其变量的取值相同，就可以将这个子句消去，再求剩余部分的满足解。如果有n元变量的CNF要消去全部子句，就要设定n个变量的值。因为逻辑变量有2个值，所以最坏要进行的是2ⁿ次选择数。这2ⁿ个n位二进制数叫可能解空间。本文介绍的是子句包含消去法。是利用可能解空间中的可能解，来求CNF全部满足解。这要利用子句块的性质。

能够将子句块中所有子句消去的子句块变量值叫子句块的解。

对应数码互反的两个子句叫互反子句。

显然，合取范式的某个子句块无解，那么这个合取范式一定无满足解。子句块有一些特殊的性质是子句包含消去法的基石。

性质1. 子句块中不是互反子句，至少有一个对应位置的数码相同。

性质2. 反子句不在子句块中，那么这个子句是该子句块的解。

性质3. 互反子句都不在所属子句块，它们都是该子句块的解。

性质4. 互反子句都在子句块中，它们都不是子句块的解。

定理：将子句和包含子句那些可能解都消去，剩余的可能解的反码是原合取范式的满足解。

证明：因为剩余的可能解都由不在合取范式中的那些子句构成，其中或者是子句块中子句的反子句，或者都不在子句块中。根据性质2、3，则取反之后的可能解，一定由在子句块的子句或都不在子句块中的子句构成，则取反之后的可能解一定能将全部子句消去。

上面的定理就是子句包含消去法。

6 子句包含消去法实例

在表 5解空间中，将包含子句的那些可能解消去，剩余的那些可能解如表 6所示。

表 6  解空间剩余的可能解

对剩余的可能解取其反码数，就得到了此问题的全部满足解（见表7）。

表 7全部满足解

将表 7得到的这5个满足解带到表 5进行验证，都可以得到CNF=1。

7 并行计算程序

仿量子计算机的并行计算程序如表 8所示。

表 8  并行计算SAT程序

在设计的仿量子计算机上，这个程序常驻内存，使用时用call指令调用就可以计算。输入4430 4400 8000（先送低8位后送高8位），就可以调用这个并行计算SAT问题的程序，然后输入并行处理数据，就能够得到CNF=1的满足解。另外在320的位置，将上面例题数据放入内存了，可以输入4420 4400 8000，直接得到结果。不过数据要转换成纠缠态表示。

8 纠缠态数据结构

表 9中有许多空位置，要将空位置表达出来，才可以进行并行计算。用01或10来表示空格，用00表示0，11表示1。这样表 9左面的8列，就可以写成右面一列的并行处理数据。方法是一行数据用两行表示，上下对位表示0、1和空格。并行处理器SPU处理的是并行数据。

表 9  纠缠态数据表示

9 结束语

量子计算机有诸多的问题尚未解决，因而成为实用的计算机还要假以时日。量子计算的要点是同时计算2ⁿ个数据，这样就将指数时间复杂度的计算转变成了多项式时间复杂度计算。仿量子计算机的同时处理器SPU，也可以同时计算2ⁿ个数据，并且添加到传统的计算机之后，能使传统计算机成为实用的，既可以执行顺序计算又可以进行并行计算的完备计算机。

计算机科学界已经证，明诸多的计算机难题都可以在多项式时间转化为SAT问题求解。仿量子计算机解决了SAT问题的计算，其余那些难题都将会迎刃而解。

2019年12月22日  星期日