词条

秀尔算法

秀尔算法（Shor算法），以数学家彼得·秀尔命名，是一个在1994年发现的，针对整数分解这题目的的量子算法（在量子计算机上面运作的算法）。比较不正式的说，它解决题目如下：给定一个整数N，找出他的质因数。

在一个量子计算机上面，要分解整数N，秀尔算法的运作需要多项式时间（时间是log N的某个多项式这么长，log N在这里的意义是输入的档案长度）。更精确的说，这个算法花费 $O((log N) 3)$ 的时间，展示出质因数分解问题可以使用量子计算机以多项式时间解出，因此在复杂度类BQP里面。这比起传统已知最快的因数分解算法，普通数域筛选法，其花费次指数时间-- 大约 $O(e 1.9 (log N) 1/3 (log log N) 2/3)$ ，还要快了一个指数的差异。

秀尔算法非常重要，因为它代表使用量子计算机的话，我们可以用来破解已被广泛使用的公开密钥加密方法，也就是RSA加密算法。RSA算法的基础在于假设了我们不能很有效率的分解一个已知的整数。就目前所知，这假设对传统...

秀尔算法相关文献

Paxos算法

问题和假设分布式系统中的节点通信存在两种模型：共享内存（Sharedmemory）和消息传递（Messagespassing）。基于消息传递通信模型的分布式系统，不可避免的会发生以下错误：进程可能会慢、被杀死或者重启，消息可能会延迟、丢失、重复，在基础Paxos场景中，先不考虑可能出现消息篡改即拜占庭错误的情况。Paxos算法解决的问题是在一个可能发生上述异常的分布式系统中如何就某个值达成一致，保证不论发生以上任何异常，都不会破坏决议的一致性。一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。一个通用的一致性算法可以应用在许多场景中，是分布式计算中的重要问题。因此从20世纪80年代起对于一致性算法的研究就...

查看全文

伯利坎普－韦尔奇算法

算法伯利坎普－韦尔奇算法通常被用于解码里德-所罗门码。假使在有限体GF(q){displaystyleGF(q)}上有n{displaystylen}个数字m1,……-->,mn{disp

查看全文

秀尔算法

程序我们要试着解决的问题是：给定一个合成数N,找到整数p在1和N之间且不包含1和N,并且N整除于p。秀尔算法包含两个部分：一个以传统的电脑运作的简化算法，将因数分解简化成搜寻阶的问题。一个量子算法，解决搜寻阶的问题。传统部分选择任意数字aQN}）。输入和输出量子位元暂存器需要储存从0到Q-1所有值的叠加态，因此分别需要q个量子位元。这里使用看起来比所需的数量还要更多一倍的量子位元，保证了即使周期r的大小逼近N/2，也至少有N个不同的x会产生相同的f(x)。程序如下：将暂存器初始化成Q−−-->1/2∑∑-->x=0Q−−-->1|x〉|0〉{\displaystyleQ^{-1/2}\sum_{x=0}^{Q-1}\left|x\right\rangle\left|0\right\rangle}x从0到Q−1。所以这一个初始态是Q个状态的叠加。建立量子函式版本的f(x)，并且应用于上面的叠

查看全文

算法

历史算法在中国古代文献中称为“术”，最早出现在《周髀算经》、《九章算术》。特别是《九章算术》，给出四则运算、最大公约数、最小公倍数、开平方根、开立方根、求素数的埃拉托斯特尼筛法，线性方程组求解的算法。三国时代的刘徽给出求圆周率的算法：刘徽割圆术。自唐代以来，历代更有许多专门论述“算法”的专著：唐代：《一位算法》一卷，《算法》一卷；宋代：《算法绪论》一卷、《算法秘诀》一卷；最著名的是杨辉的《杨辉算法》；元代：《丁巨算法》；明代：程大位《算法统宗》清代：《开平算法》、《算法一得》、《算法全书》。而英文名称“Algorithm”来自于9世纪波斯数学家花拉子米（比阿勒·霍瓦里松，波斯语：خوارزمی‎，拉丁转写：al-Khwarizmi），因为比阿勒·霍瓦里松在数学上提出了算法这个概念。“算法”原为“algorism”，即“al-Khwarizmi”的音转，意思是“花拉子米”的运算法则，在18世...

查看全文

CYK算法

相关参数定义G=(V,ΣΣ-->,S,P){displaystyle~G=(V,Sigma,S,P)}是一个上下文无关文法对于任意字符串w=σσ-->1...σσ--&gt

查看全文

秀尔算法相关标签

量子算法

整数分解算法

包含证明的条目

量子信息

家族谱大览