|||
姜咏江
最近读了一篇网传中国科学院院士,南方科技大学创校校长关于“量子纠缠”等方面的报告文,院士主张“人类的主观意识是客观物质世界的基础——客观世界很有可能并不存在!”真是“科学透顶”!
我研究P/NP问题的SAT问题求解,一不小心竟然整出了二进制数域的“纠缠态”,看来我也进了量子力学的空前大世界了。
纠缠态源自量子态,据说量子有0、1和纠缠态。纠缠态如何用数码来表示?因为是0,又是1,只要一观察就出现0或1状态,这叫“坍塌”。我将n位二进制数表示成n个“*”组成的字符串,用来代表0~2n-1那些n位二进制数,每一个*代表0或1,具体是0还是1,只有需要做子句标志消去法时,才能看到。你看是不是同量子一样纠缠了?
我在2015年搞过这个东西(http://blog.sciencenet.cn/blog-340399-908661.html),只是当时尚不很明确,也没想到“纠缠”这个概念。现在明白了,这是二进制限位数的纠缠态!
我们知道,n个逻辑变量构成的合取范式CNF为1的可能解,应当是一个n位二进制数。在没求出CNF=1的解时,这0~2n-1个二进制数都可能是解。把它们全表示出来,最简单就是我上面提到的n个*,亦即我现在说的纠缠态,我们不妨称之为“解纠缠”。解纠缠也可以在可以配合0和1数码表示数。
我的子句计数法,又叫子句标志消去法。什么叫子句标志?就是将子句用0 和1表示,如果子句的数码位置和n位二进制数对应位置数码相同,那么就称这个n位二进制数是这个子句的标志,也可以叫属于这个子句的可能解。
现在我举例来说明怎么用这个“解纠缠”来表示的n位二进制数求SAT的解。表1是一个逻辑电路的合取范式,可以用作电路检测(https://en.wikipedia.org/wiki/Tseytin_transformation)。这个SAT的可能解有11位,为***********,这代表了0000000000~1111111111这些数,这就是纠缠态。
让解纠缠的某一位塌缩,是通过消去子句来“观察”的。塌缩会会产生解纠缠分裂。如何分裂?
*表示0或1的纠缠态,如果我们用0测试,它就塌缩成了1,如果用1测试,它就塌缩成了0。如果是两个**,它可以纠缠表示00,01,10,11,用其中任何一个去测试,都会塌缩成剩余的3个。一般地,用k位二进制数测试k位解纠缠,就会塌缩出2k-1个不包含测试二进制数的k位二进制数集合。如果一个数有i位对应*,0≤i≤k,那么这个解纠缠就会裂变成2i-1个。因此,我又将所谓的塌缩叫裂变。
需要说明,在论文中我将子句标志消去法叫ECPS(Elimination ofclause and Possible Solutions ),把“量子塌缩”求解的算法叫SSFA (Split Solution Form Algorithm)。
下面我们就来看看求SAT全解的例题吧。
将参考网页上的电路改变一下变量的表示,就得到了表1。
表1 一个逻辑电路的合取范式
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
| 序 |
|
|
|
|
|
|
|
|
|
| 1 |
| 1 |
1 | 1 |
|
| 2 | ||||||||
0 | 0 |
|
| 3 | ||||||||
1 | 0 |
|
| 4 | ||||||||
1 | 0 |
|
| 5 | ||||||||
1 | 1 |
|
| 6 | ||||||||
0 | 0 |
|
| 7 | ||||||||
1 | 1 |
|
| 8 | ||||||||
0 | 0 |
|
| 9 | ||||||||
1 | 0 |
|
| 21 | ||||||||
1 | 0 |
|
| 10 | ||||||||
0 | 1 |
|
| 11 | ||||||||
1 | 0 |
|
| 12 | ||||||||
0 | 1 |
|
| 15 | ||||||||
1 | 0 |
|
| 16 | ||||||||
0 |
| 1 |
| 13 | ||||||||
|
|
|
|
|
|
|
|
| 0 | 1 |
| 14 |
0 | 0 | 1 |
|
| 17 | |||||||
0 | 0 | 1 |
|
| 18 | |||||||
0 | 0 | 1 |
|
| 19 | |||||||
1 | 1 | 0 |
|
| 22 | |||||||
|
|
|
|
|
|
|
| 1 | 1 | 0 |
| 20 |
(0)初始解纠缠
表2 初始解纠缠
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
* | * | * | * | * | * | * | * | * | * | * |
消去子句x11=1,那么***********就分裂成了**********0,第11位“坍塌”了。
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
* | * | * | * | * | * | * | * | * | * | 0 |
消去子句x1x4=11,第一和第四位置去掉1,那么**********0就分裂成了0**0******0,0**1******0,1**0******0。这是第一和第四位“坍塌”了。
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
0 | * | * | 0 | * | * | * | * | * | * | 0 |
0 | * | * | 1 | * | * | * | * | * | * | 0 |
1 | * | * | 0 | * | * | * | * | * | * | 0 |
消去子句x1x4=00,第一和第四位置是0,那么与0**0******0一致,消去它,剩下了0**1******0,1**0******0。
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
0 | * | * | 1 | * | * | * | * | * | * | 0 |
1 | * | * | 0 | * | * | * | * | * | * | 0 |
消去子句x1x7=10,那么与1**0******0一致,消去它,剩下了0**1******0,1**0**1***0。
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
0 | * | * | 1 | * | * | * | * | * | * | 0 |
1 | * | * | 0 | * | * | 1 | * | * | * | 0 |
消去子句x2x5=10,第2和第5位,因为对应2个星,都裂变成3个解纠缠。
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
0 | 0 | * | 1 | 0 | * | * | * | * | * | 0 |
0 | 0 | * | 1 | 1 | * | * | * | * | * | 0 |
0 | 1 | * | 1 | 1 | * | * | * | * | * | 0 |
1 | 0 | * | 0 | 0 | * | 1 | * | * | * | 0 |
1 | 0 | * | 0 | 1 | * | 1 | * | * | * | 0 |
1 | 1 | * | 0 | 1 | * | 1 | * | * | * | 0 |
消去子句x2x6=11。
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
0 | 0 | * | 1 | 0 | * | * | * | * | * | 0 |
0 | 0 | * | 1 | 1 | * | * | * | * | * | 0 |
0 | 1 | * | 1 | 1 | 0 | * | * | * | * | 0 |
1 | 0 | * | 0 | 0 | * | 1 | * | * | * | 0 |
1 | 0 | * | 0 | 1 | * | 1 | * | * | * | 0 |
1 | 1 | * | 0 | 1 | 0 | 1 | * | * | * | 0 |
消去子句x2x6=00。
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
0 | 0 | * | 1 | 0 | 1 | * | * | * | * | 0 |
0 | 0 | * | 1 | 1 | 1 | * | * | * | * | 0 |
0 | 1 | * | 1 | 1 | 0 | * | * | * | * | 0 |
1 | 0 | * | 0 | 0 | 1 | 1 | * | * | * | 0 |
1 | 0 | * | 0 | 1 | 1 | 1 | * | * | * | 0 |
1 | 1 | * | 0 | 1 | 0 | 1 | * | * | * | 0 |
消去子句x2x8=11。
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
0 | 0 | * | 1 | 0 | 1 | * | * | * | * | 0 |
0 | 0 | * | 1 | 1 | 1 | * | * | * | * | 0 |
0 | 1 | * | 1 | 1 | 0 | * | 0 | * | * | 0 |
1 | 0 | * | 0 | 0 | 1 | 1 | * | * | * | 0 |
1 | 0 | * | 0 | 1 | 1 | 1 | * | * | * | 0 |
1 | 1 | * | 0 | 1 | 0 | 1 | 0 | * | * | 0 |
消去子句x2x8=00。
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
0 | 0 | * | 1 | 0 | 1 | * | 1 | * | * | 0 |
0 | 0 | * | 1 | 1 | 1 | * | 1 | * | * | 0 |
0 | 1 | * | 1 | 1 | 0 | * | 0 | * | * | 0 |
1 | 0 | * | 0 | 0 | 1 | 1 | 1 | * | * | 0 |
1 | 0 | * | 0 | 1 | 1 | 1 | 1 | * | * | 0 |
1 | 1 | * | 0 | 1 | 0 | 1 | 0 | * | * | 0 |
变量x3x9在解纠缠中都是星,暂往后放,找分裂较少子句。
消去子句x4x5=10。
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
0 | 0 | * | 1 | 1 | 1 | * | 1 | * | * | 0 |
0 | 1 | * | 1 | 1 | 0 | * | 0 | * | * | 0 |
1 | 0 | * | 0 | 0 | 1 | 1 | 1 | * | * | 0 |
1 | 0 | * | 0 | 1 | 1 | 1 | 1 | * | * | 0 |
1 | 1 | * | 0 | 1 | 0 | 1 | 0 | * | * | 0 |
消去子句x5x10=01。
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
0 | 0 | * | 1 | 1 | 1 | * | 1 | * | * | 0 |
0 | 1 | * | 1 | 1 | 0 | * | 0 | * | * | 0 |
1 | 0 | * | 0 | 0 | 1 | 1 | 1 | * | 0 | 0 |
1 | 0 | * | 0 | 1 | 1 | 1 | 1 | * | * | 0 |
1 | 1 | * | 0 | 1 | 0 | 1 | 0 | * | * | 0 |
消去子句x6x7=10。
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
0 | 0 | * | 1 | 1 | 1 | 1 | 1 | * | * | 0 |
0 | 1 | * | 1 | 1 | 0 | * | 0 | * | * | 0 |
1 | 0 | * | 0 | 0 | 1 | 1 | 1 | * | 0 | 0 |
1 | 0 | * | 0 | 1 | 1 | 1 | 1 | * | * | 0 |
1 | 1 | * | 0 | 1 | 0 | 1 | 0 | * | * | 0 |
消去子句x9x11=01 。
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
0 | 0 | * | 1 | 1 | 1 | 1 | 1 | * | * | 0 |
0 | 1 | * | 1 | 1 | 0 | * | 0 | * | * | 0 |
1 | 0 | * | 0 | 0 | 1 | 1 | 1 | * | 0 | 0 |
1 | 0 | * | 0 | 1 | 1 | 1 | 1 | * | * | 0 |
1 | 1 | * | 0 | 1 | 0 | 1 | 0 | * | * | 0 |
消去子句x10x11=01 。
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
0 | 0 | * | 1 | 1 | 1 | 1 | 1 | * | * | 0 |
0 | 1 | * | 1 | 1 | 0 | * | 0 | * | * | 0 |
1 | 0 | * | 0 | 0 | 1 | 1 | 1 | * | 0 | 0 |
1 | 0 | * | 0 | 1 | 1 | 1 | 1 | * | * | 0 |
1 | 1 | * | 0 | 1 | 0 | 1 | 0 | * | * | 0 |
消去子句x7x10=01。
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
0 | 0 | * | 1 | 1 | 1 | 1 | 1 | * | * | 0 |
0 | 1 | * | 1 | 1 | 0 | 0 | 0 | * | 0 | 0 |
0 | 1 | * | 1 | 1 | 0 | 1 | 0 | * | 0 | 0 |
0 | 1 | * | 1 | 1 | 0 | 1 | 0 | * | 1 | 0 |
1 | 0 | * | 0 | 0 | 1 | 1 | 1 | * | 0 | 0 |
1 | 0 | * | 0 | 1 | 1 | 1 | 1 | * | * | 0 |
1 | 1 | * | 0 | 1 | 0 | 1 | 0 | * | * | 0 |
消去子句x8x9=10。
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
0 | 0 | * | 1 | 1 | 1 | 1 | 1 | 1 | * | 0 |
0 | 1 | * | 1 | 1 | 0 | 0 | 0 | * | 0 | 0 |
0 | 1 | * | 1 | 1 | 0 | 1 | 0 | * | 0 | 0 |
0 | 1 | * | 1 | 1 | 0 | 1 | 0 | * | 1 | 0 |
1 | 0 | * | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 |
1 | 0 | * | 0 | 1 | 1 | 1 | 1 | 1 | * | 0 |
1 | 1 | * | 0 | 1 | 0 | 1 | 0 | * | * | 0 |
消去子句x1x6 x7=001。
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
0 | 0 | * | 1 | 1 | 1 | 1 | 1 | 1 | * | 0 |
0 | 1 | * | 1 | 1 | 0 | 0 | 0 | * | 0 | 0 |
1 | 0 | * | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 |
1 | 0 | * | 0 | 1 | 1 | 1 | 1 | 1 | * | 0 |
1 | 1 | * | 0 | 1 | 0 | 1 | 0 | * | * | 0 |
消去子句x2x4 x5=001。
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
0 | 0 | * | 1 | 1 | 1 | 1 | 1 | 1 | * | 0 |
0 | 1 | * | 1 | 1 | 0 | 0 | 0 | * | 0 | 0 |
1 | 0 | * | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 |
1 | 1 | * | 0 | 1 | 0 | 1 | 0 | * | * | 0 |
消去子句x5x7x10=110。
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
0 | 0 | * | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 |
0 | 1 | * | 1 | 1 | 0 | 0 | 0 | * | 0 | 0 |
1 | 0 | * | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 |
1 | 1 | * | 0 | 1 | 0 | 1 | 0 | * | 1 | 0 |
消去子句x9x10x11=110。
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
0 | 1 | * | 1 | 1 | 0 | 0 | 0 | * | 0 | 0 |
1 | 0 | * | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 |
1 | 1 | * | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
消去子句x3x9=10。
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 |
0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 |
1 | 0 | * | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 |
1 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
消去子句x3x8x9=001。
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 | 1 | 1 | 1 | 1 | 0 | 0 |
1 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
最后剩余可能解如表3所示。
表3 剩余可能解
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 |
表3.每行的反码数就是这个SAT问题的全部解(见表4)。
表4 SAT全部解
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 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 |
0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 |
0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 |
我们知道,11个逻辑变量的SAT的全部可能解有211=2048个,如果用穷举法,得验证2048次。这里我们仅用了22次就求出全部SAT解了。这种“量子纠缠态”的方法不值得推广吗?
我相信这将带来数学和计算机科学的空前变革。数据纠缠态的计算机编程将PK量子计算机。
最后说一句,科学家要实事求是地探讨问题,瞎想会进入唯心主义的泥坑。
2017/3/1
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-12-5 14:57
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社