CMP设计分享 http://blog.sciencenet.cn/u/accsys 没有逆向思维就没有科技原创。 不自信是科技创新的大敌。

博文

仿量子计算机设计

已有 908 次阅读 2020-1-13 06:08 |个人分类:仿量子计算机|系统分类:论文交流| 限位数, 密钥分发, 子句包含消去法

                                          姜咏江 邮箱:accsys@126.com

 

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

 

1 前言

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

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

2 仿量子计算机结构

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

                                      图 1 仿量子计算机结构

3 指令系统

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

 

1 仿量子计算机指令系统

序号

指令

编码

功能

1

Add

000001

X+da->da

2

Sub

000010

Da-X->da

3

Addc

000011

Da+X+carry->da    c->carry

4

Subc

000100

Da-X+carry->da     c->carry

5

Out

000101

Da->O

6

Dal n

000110

->dal   8位接收数据

7

Dah n

000111

->dah  8位接收数据

8

Xda

001000

X->da

9

Dax

001001

Da->X

10

Lda r

001010

Dram->da

11

Str r

001011

Da->dram

12

Jmp r

001100

跳转

13

Jz r

001101

Da=0 跳转

14

Jn r

001110

Da<0 跳转

15

Jo r

001111

溢出跳转

16

Call r

010000

调用子程序

17

Ret

010001

返回

18

Lyu r

010010

19

Lhuo r

010011

20

Lfei r

010100

21

Lyh r

010101

异或

22

Inl

010110

输入到da8

23

Inh

010111

输入到da8

24

Jk r

011000

缓冲区空跳转

25

Incp

011001

Ptr+1

26

Decp

011010

Ptr-1

27

Srei

011011

输入到iram

28

Datp

011100

Da->ptr

29

Jend r

011101

程序输入结束

30

Inp

011110

da输入到ptr指示iram

33

daq

100001

Ptr->cmar,da->ccq

34

Sat

100010

Ptr->cmarccq->子句寄存器clr0

35

Jzp r

100011

ptr0跳转

36

Xout

100100

X寄存器内容输出

37

Mzj

100101

将满足解写入X寄存器

38

Clrr

100110

Sat计算初始化

39

End

100000

结束程序输入伪指令

 

 


 

 


 

4 并行计算实例

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

4.1  数据密码锁

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

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

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

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

1中我们在输入密码行,输入101011011,然后逐行检查那些满足消去条件的行。含有x8=1的行有23457行,将这些行消去。满足第二个数码0的行,剩下的行只有89这两行。以此类推,最终可将所有的行数据消去,则表明输入的变量值是这个数据密码锁的密码。

2   数据密码锁

行号

x8

x7

x6

x5

x4

x3

x2

x1

x0

1

0

1

1







2

1

0

1







3

1

1


0






4

1

0


1






5

1



1


1




6

0



1


1




7

1



1


0




8


1


0


0




9


0


1


0




10


0


0


0




11



1

1

1





12



0

1

1





13




1

1

1




1




0

0

1




15





1

1


1


16





0

0


1


17





0

1


0


18






0


1

0

19






1


0

0

20







0

1

1

21







1

0

1

22







0

0

0

23







0

0

1

24







0

0


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

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

输入其它变量值测试

输入密码:

1

0

1

0

1

0

0

1

1


x8

x7

x6

x5

x4

x3

x2

x1

x0


0

1

1







1

0

1







1

1


0






1

0


1






1



1


1




0



1


1





1



1


0






1


0


0






0


1


0






0


0


0







1

1

1








0

1

1









1

1

1








0

0

1









1

1


1







0

0


1







0

1


0








0


1

0







1


0

0








0

1

1








1

0

1








0

0

0








0

0

1








0

0


 

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

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

 

4.2  逻辑电路可靠性问题

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

4.2.1  Tsyetin变换

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


 

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

4  Tsyetin变换

逻辑符号

逻辑表达式

合取范式

C=AB

(A’+B’+C)(A+C’)(B+C’)

C=(AB)’

(A’+B’+C’)(A+C)(B+C)

C=A+B

(A+B+C’)(A’+C)(B’+C)

C=(A+B)’

(A+B+C)(A’+C’)(B’+C’)

C=A’

(A’+C’)(A+C)

C=A⊕B

(A’+B’+C’)(A+B+C’)(A+B’+C)(A’+B+C)

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

                      图 2 逻辑电路检测点

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

CNF=(x1+x4)(x1’+x4’)(x4+x5’)(x2+x5’)(x2’+x5+x4’)(x2+x6)(x7’+x1)(x6+x7’)(x1’+x6’+x7)(x2+x8)(x2’+x8’)(x8+x9’)(x3+x9’)(x3’+x8’+x9)(x5’+x10)(x7’+x10)(x5+x7+x10’) (x9’+x11)(x10’+x11)(x9+x10+x11’)x11                                                              (1)

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

二进制表示的CNF

0

1

1

1

1

0

0

0

0

1

1

x1

x2

x3

x4

x5

x6

x7

x8

x9

x10

x11

1



1








0



0











1

0








1



0








0


0

1








1




1







0




0






1






0










1

0





0





0

1






1






1





0






0











1

0





1






0





0





0

1







0





1








0



1






1


1



0










0


1










0

1









1

1

0











1

4.2.2  子句消去法

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

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

5 并行计算理论基础

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

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

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

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

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

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

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

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

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

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

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

6 子句包含消去法实例

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

解空间剩余的可能解

x1

x2

x3

x4

x5

x6

x7

x8

X9

x10

x11

0

1

0

1

1

0

0

0

0

0

0

0

1

1

1

1

0

0

0

1

0

0

1

0

0

0

0

1

1

1

1

0

0

1

0

1

0

0

1

1

1

1

0

0

1

1

0

0

1

0

1

0

0

1

0

 

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

7全部满足解

x1

x2

x3

x4

x5

x6

x7

x8

x9

x10

x11

1

0

1

0

0

1

1

1

1

1

1

1

0

0

0

0

1

1

1

0

1

1

0

1

0

1

1

0

0

0

0

1

1

0

1

1

1

1

0

0

0

0

1

1

0

0

1

1

0

1

0

1

1

0

1

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


 

7 并行计算程序

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

并行计算SAT程序

标号

汇编指令

解释

start

Dah 0



Dal 0

0起,子句数量减1


Datp

0000->ptr

Loop0

Jk  Loop0

缓冲区空跳转


Inl

输入低8

Loop1

Jk  loop1

缓冲区空跳转


Inh

输入高8


Jend exit0

结束输入跳转


daq

送入cnf存储器


Incp

Ptr+1


Jmp Loop0

读下一个字

Exit0

Clrr

清理反满足解寄存器

Loop2

Sat

子句并行处理求解


Jzp  exit1

子句结束跳转(放在sat后)


decp



Jmp loop2


Exit1

Mzj

保存第一个满足解


Xout

输出第一个满足解


Clrr

清理反满足解寄存器


Ret



End

结束程序输入伪指令

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

8 纠缠态数据结构

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

纠缠态数据表示

1

1

1

1

0

1

1

1


X7

X6

X5

X4

X3

X2

X1

X0

(并行数据)

1

0

0






80   9F

0

1

0






40   5F

1

0

1






A0   BF

1

1

0






C0   DF

0


1

0





20   6F

0


1

1





30   7F



0

0


1



04   CF



1


0

0



20   F3



0


0

1



04   D7



1


1

1



2C   FF






1

1

0

06   FE






1

0

1

05   FD






0

1

0

02   FA




1  




0

10   FE








1

01   FF

 

9 结束语


 

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


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

 

 

20191222  星期日








http://blog.sciencenet.cn/blog-340399-1213970.html

上一篇:目前我国能不能有真正的科技原创?
下一篇:原创注重同行评审还是注重实际?

0

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2020-11-30 01:07

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部