【摘 要】
：
This paper presents a quantum algorithm to decide whether a Boolean equation system F has a solution and to compute one if F does have solutions with any given success probability.The runtime complexity of the algorithm is polynomial in the size of F and
【机 构】
：
Academy of Mathematics and Systems Science,Chinese Academy of Sciences,Beijing 100190,China;Univer-s
论文部分内容阅读
This paper presents a quantum algorithm to decide whether a Boolean equation system F has a solution and to compute one if F does have solutions with any given success probability.The runtime complexity of the algorithm is polynomial in the size of F and the condition number of certain Macaulay matrix associated with F.As a consequence,the authors give a polynomial-time quantum algorithm for solving Boolean equation systems if their condition numbers are polynomial in the size of F.The authors apply the proposed quantum algorithm to the cryptanalysis of several important cryptosystems:The stream cipher Trivum,the block cipher AES,the hash function SHA-3/Keccak,the multivariate public key cryptosystems,and show that they are secure under quantum algebraic attack only if the corresponding condition numbers are large.This leads to a new criterion for designing such cryptosystems which are safe against the attack of quantum computers:The corresponding condition number.
其他文献
针对车位共享平台供给与需求均随机的特征,文章构建了随机动态规划模型对共享车位的预订控制策略进行研究.基于随机动态规划模型,进一步构造了单产品分解模型和单周期分解模型对问题最优解进行分析,并证明了单产品分解模型的超模性以及单周期分解模型的凹性性质.基于分解模型,分别设计了三种预订控制算法对模型进行求解.最后,通过数值仿真验证了模型和算法的有效性.本文的研究结果将为共享平台的预订控制提供决策支持.
Option pricing problem is one of the central issue in the theory of modern finance.Un-certain currency model has been put forward under the foundation of uncertainty theory as a tool to portray the foreign exchange rate in uncertain finance market.This pa
针对缝洞型碳酸盐岩油藏储集层非均质性强、连通单元识别难度大、井间连通性认识不清和油藏高效开发困难的问题,运用相控反演与最大似然属性刻画缝洞集合体与大尺度裂缝空间展布,识别连通单元,明确井间连通方式以及剩余油潜力,基于单井动态资料进行连通性分析,验证静态资料连通性刻画结果的合理性.应用于轮古7井区轮古7-5井组注气开发,为井组注替、开发策略制定提供依据,进一步提高油藏开发效益.
Different from previous viewpoints,multivariate polynomial matrix Diophantine equations are studied from the perspective of modules in this paper,that is,regarding the columns of matrices as elements in modules.A necessary and sufficient condition of the
This study is a detailed analysis of Speculation Game,a simple agent-based model of finan-cial markets,in which the round-trip trading and the dynamic wealth evolution with variable trading volumes are implemented.Instead of herding behavior,the authors f
针对现有差模注入等效试验方法局限性导致的误差,基于电磁场理论分析了误差产生原因,提出了天线耦合途径下的校正方法,实现了注入试验结果与测试标准要求的电磁辐射试验结果等效.以复杂电磁环境下易出现干扰损伤效应的用频装备为研究对象,将通信电台这一典型用频装备作为受试设备,开展了带内和带外阻塞效应强场电磁辐射等效注入试验,提出了工作信号和干扰信号同时存在的校正方法并进行试验验证.结果 表明,接收天线为主要耦合途径下,差模注入法等效电磁辐射法的精度高,等效注入试验所需电磁功率显著小于辐射试验.
Gao,et al.(2015) gave a simple algorithm to compute Gr(o)bner bases named GVW.It can be used to compute Gr(o)bner bases for both ideals and syzygies at the same time,and the latter plays an important role in free resolutions in homological algebra.In GVW
This paper mainly studies the strong convergence properties for weighted sums of extended negatively dependent (END,for short) random variables.Some sufficient conditions to prove the strong law of large numbers for weighted sums of END random variables a
The varying-coefficient single-index model (VCSIM) is widely used in economics,statistics and biology.A model averaging method for VCSIM based on a Mallows-type criterion is proposed to improve prodictive capacity,which allows the number of candidate mode
为解决区域边界曲线上收发分置雷达的优化布站问题,提出一种圆周栅栏覆盖的优化布站方法.首先,提出圆周栅栏覆盖最优布站序列应满足的条件,并通过理论分析证明了最优布站模式中接收器个数的上限阈值.接着,以此为基础构建基于布站成本最小的优化布站模型.然后,针对优化模型的非凸性和非线性,提出一种将整数线性规划与穷举法相联合的算法求解优化模型,确定最小布站成本及其对应的最优布站序列.最后,通过仿真实验和分析验证了所提方法的有效性.