XiaoMi-AI文件搜索系统
World File Search SystemShor
将量子近似优化算法应用于组合优化问题
量子计算领域始于1980年代初，著名的物理学家Paul Benioff，Yuri Manin和Richard Feynman，独立和同时概念化了量子计算机的概念[2-5]。这个想法是基于这样的观察结果，即在classical计算机上模拟量子系统需要以量子系统大小为指数缩放的资源。因此，如果我们想模拟量子物理学，我们最好使用量子物理。后来，David Deutsch正式化了Quantur Turing机器的想法，并提出了量子电路模型[6，7]。接下来是彼得·谢尔（Peter Shor），彼得·谢尔（Peter Shor）发现了一种量子算法，该算法可以比任何已知的经典算法更快地求解质量分解[8]。发现大量的主要因素对于古典计算机来说很难，并且这种计算硬度已用于公用密钥密码系统，例如RSA [9]。但是，有了足够大的量子计算机，公用密钥系统很容易被黑客入侵。今天，量子计算机仍处于早期阶段，它们对噪声的敏感性比其经典对应物更敏感。这设置了量子电路大小的限制。尽管从理论上讲量子误差校正是驯服错误，但它仍然需要大量的Qubits [10，11]。例如，对运行Shor的算法的要求的估计值证明，有数百万量子数具有错误校正[12]。
攻击经典和后量子密码学中的难度假设的量子算法
量子计算机是一种利用量子力学现象进行计算的计算机，不同于当今利用经典物理现象的传统计算机。功能足够强大的大规模量子计算机（不易出错或可纠错）将对目前广泛部署的大多数非对称密码系统构成威胁。这是因为 Shor [1] 引入了多项式时间量子算法来解决循环群中的整数因式分解问题 (IFP) 和离散对数问题 (DLP)。例如，如果量子计算机能够执行 Shor 算法，那么对于足够大的问题实例，它将能够破解基于 IFP 的 RSA [ 2 ] 以及基于 DLP 的 DSA [ 3 ] 和 Diffie-Hellman (DH) [ 4 ]——主要是在有限域的乘法群或椭圆曲线点群（在椭圆曲线密码 (ECC) 的情况下）中。[ 5, 6 ]。上述密码系统目前用于保护互联网上大多数交易的安全。
量子计算及应用 Rahul Jain 教授
课程概述 量子计算在世界范围内越来越受欢迎，一些国家提供了旗舰资助，一些大型私营公司也在尝试制造量子计算机。其中一个原因是与密码学相关的战略重要性，因为 Shor 的量子算法可以破解许多现有的密码系统。量子计算还在金融、化学、人工智能 (AI)、模拟、通信等不同领域得到应用。本课程提供了熟悉这种日益流行和重要发展技术的机会。本课程的主要目标如下：本课程将首先介绍量子计算的基础知识。然后，它将介绍各种众所周知的量子算法，例如 Deutsch-Jozsa 算法、Simon 算法、量子傅里叶变换、相位估计、顺序查找、Shor 算法和 Grover 算法。最后，它将介绍一些应用，包括量子金融、量子密码学等。在课程结束时，学员将：
攻击难度的量子算法 攻击经典中的难度假设和后量子假设的量子算法
量子计算机是一种利用量子力学现象进行计算的计算机，不同于当今利用经典物理现象的传统计算机。功能足够强大的大规模量子计算机（不易出错或可纠错）将对目前广泛部署的大多数非对称密码系统构成威胁。这是因为 Shor [1] 引入了多项式时间量子算法来解决循环群中的整数因式分解问题 (IFP) 和离散对数问题 (DLP)。例如，如果量子计算机能够执行 Shor 算法，那么对于足够大的问题实例，它将能够破解基于 IFP 的 RSA [ 2 ] 以及基于 DLP 的 DSA [ 3 ] 和 Diffie-Hellman (DH) [ 4 ]——主要是在有限域的乘法群或椭圆曲线点群（在椭圆曲线密码 (ECC) 的情况下）中。[ 5, 6 ]。上述密码系统目前用于保护互联网上大多数交易的安全。
减少量子因式分解中的量子比特数量
背景。Shor 的突破性算法 [13] 表明，因式分解和计算离散对数的问题可以在量子计算机上在多项式时间内解决。从那时起，许多作者引入了该算法的变体并改进了其成本估算，以尽量减少对量子比特、门数或电路深度的要求 [2、15、14、8、5、12]。由于 Shor 算法被认为是量子计算机与密码分析最相关的应用，这些工作也旨在确定量子计算架构可能变得“与密码相关”的点。在本文中，我们专注于空间优化。考虑群 Z ∗ N 中的离散对数 (DL) 问题，其中 N 为素数。让我们记 n = log 2 N。我们取乘法生成器 G。A 的 DL 是数量 D，使得 A = GD mod N。它是通过对在 Z 2 上定义的函数 f ( x, y ) = G x A − y mod N 调用 Shor 的量子周期查找子程序来找到的。这个子程序只是在所有 ( x, y ) ∈ [0; 2 m 1 − 1] × [0; 2 m 2 − 1] 上调用叠加的 f，执行 QFT 和测量（图 1）。经过一些有效的后处理后，可以找到周期 ( D, 1 )。因此，逻辑量子比特的数量取决于两个参数：输入大小 m 1 + m 2 和工作区大小。对 RSA 半素数 N 进行因式分解可以简化为求解 Z ∗ N 中的 DL 实例，其中 DL 的预期大小为 1
量子计算机——一种新兴的网络安全威胁
广泛使用的 RSA（Rivest 等人，1978 年）公钥密码术被认为特别容易受到量子攻击。RSA 密钥由两个 N 位素数因子的乘积生成。它们的安全性依赖于一般假设，即素数分解的逆过程（其计算时间随 N 呈指数增长）在足够大 N 的情况下几乎不可能在任何有限时间内完成。目前，即使使用最强大的经典超级计算机和最先进的算法，分解的最大数字也是 829 位 RSA-250 数字（250 位十进制数字）（Boudot，2020 年）。而下一个挑战始终是一个挑战——素数分解仍然没有通用的经典算法。然而，量子计算机和量子算法有望改变这一事实。Shor 的量子算法（Shor，1997 年）被证明可以将指数计算时间减少到多项式时间，因此可能危及公钥密码系统。
CTS-2022-0054 最新技术
5 Vandersypen, LMK、Steffen, M.、Breyta, G.、Yannoni, CS、Sherwood, MH 和 Chuang, IL (2001)。利用核磁共振实验实现 Shor 量子因式分解算法。《自然》，414(6866)，883-887。https://doi.org/10.1038/414883a
对比特币及其衍生加密货币的量子威胁评估
摘要 — 并非所有加密货币都一样。如今，它们通过使用非量子安全的椭圆曲线数字签名算法 (ECDSA) 数字签名而具有共同的量子漏洞，但它们遭受量子攻击的风险却大不相同。加密货币遭受攻击的风险取决于许多已知因素，例如区块间隔时间、延迟未处理交易完成时间的攻击漏洞以及加密货币用户的行为，从而增加量子计算机攻击的成本。Shor 算法可用于使用量子计算机破解 ECDSA 签名。这项研究解决了两个问题：量子计算机何时才足够强大，可以执行 Shor 算法？量子计算机需要多快才能破解特定的加密货币？在本文中，我们观察到，通过对量子计算机上的电路速度和量子加法时间进行基准测试，我们可以确定何时对特定加密货币存在潜在威胁。