561
个编辑
更改
→Potential applications 潜在应用
Integer factorization, which underpins the security of public key cryptographic systems, is believed to be computationally infeasible with an ordinary computer for large integers if they are the product of few prime numbers (e.g., products of two 300-digit primes). By comparison, a quantum computer could efficiently solve this problem using Shor's algorithm to find its factors. This ability would allow a quantum computer to break many of the cryptographic systems in use today, in the sense that there would be a polynomial time (in the number of digits of the integer) algorithm for solving the problem. In particular, most of the popular public key ciphers are based on the difficulty of factoring integers or the discrete logarithm problem, both of which can be solved by Shor's algorithm. In particular, the RSA, Diffie–Hellman, and elliptic curve Diffie–Hellman algorithms could be broken. These are used to protect secure Web pages, encrypted email, and many other types of data. Breaking these would have significant ramifications for electronic privacy and security.
Integer factorization, which underpins the security of public key cryptographic systems, is believed to be computationally infeasible with an ordinary computer for large integers if they are the product of few prime numbers (e.g., products of two 300-digit primes). By comparison, a quantum computer could efficiently solve this problem using Shor's algorithm to find its factors. This ability would allow a quantum computer to break many of the cryptographic systems in use today, in the sense that there would be a polynomial time (in the number of digits of the integer) algorithm for solving the problem. In particular, most of the popular public key ciphers are based on the difficulty of factoring integers or the discrete logarithm problem, both of which can be solved by Shor's algorithm. In particular, the RSA, Diffie–Hellman, and elliptic curve Diffie–Hellman algorithms could be broken. These are used to protect secure Web pages, encrypted email, and many other types of data. Breaking these would have significant ramifications for electronic privacy and security.
'''<font color="#ff8000"> 整数因式分解Integer factorization</font>'''是'''<font color="#ff8000"> 公钥密码系统Public key cryptographic systems</font>'''安全性的基础，如果大整数是几个素数的乘积（例如，两个300位素数的乘积），那么在普通计算机上计算大整数是不可行的。相比之下，量子计算机可以有效地解决这个问题，使用'''<font color="#ff8000"> 肖尔Shor算法</font>'''来寻找它的因子。这种能力将使量子计算机能够破解目前使用的许多密码系统，在这个意义上，将有一个多项式时间（整数位数）算法来解决这个问题。特别是目前流行的公钥密码算法大多是基于整数的因式分解困难或离散对数问题，这两个问题都可以用'''<font color="#ff8000"> 肖尔Shor算法</font>'''来解决。特别是'''<font color="#ff8000"> RSA、Diffie-Hellman和椭圆曲线Diffie-Hellman算法</font>'''可能会被打破。它们用于保护安全网页、加密电子邮件和许多其他类型的数据。破坏这些将对电子隐私和安全产生重大影响。
However, other cryptographic algorithms do not appear to be broken by those algorithms. Some public-key algorithms are based on problems other than the integer factorization and discrete logarithm problems to which Shor's algorithm applies, like the McEliece cryptosystem based on a problem in coding theory. Lattice-based cryptosystems are also not known to be broken by quantum computers, and finding a polynomial time algorithm for solving the dihedral hidden subgroup problem, which would break many lattice based cryptosystems, is a well-studied open problem. It has been proven that applying Grover's algorithm to break a symmetric (secret key) algorithm by brute force requires time equal to roughly 2<sup>n/2</sup> invocations of the underlying cryptographic algorithm, compared with roughly 2<sup>n</sup> in the classical case, meaning that symmetric key lengths are effectively halved: AES-256 would have the same security against an attack using Grover's algorithm that AES-128 has against classical brute-force search (see Key size).
However, other cryptographic algorithms do not appear to be broken by those algorithms. Some public-key algorithms are based on problems other than the integer factorization and discrete logarithm problems to which Shor's algorithm applies, like the McEliece cryptosystem based on a problem in coding theory. Lattice-based cryptosystems are also not known to be broken by quantum computers, and finding a polynomial time algorithm for solving the dihedral hidden subgroup problem, which would break many lattice based cryptosystems, is a well-studied open problem. It has been proven that applying Grover's algorithm to break a symmetric (secret key) algorithm by brute force requires time equal to roughly 2<sup>n/2</sup> invocations of the underlying cryptographic algorithm, compared with roughly 2<sup>n</sup> in the classical case, meaning that symmetric key lengths are effectively halved: AES-256 would have the same security against an attack using Grover's algorithm that AES-128 has against classical brute-force search (see Key size).
然而，其他密码算法似乎并没有被这些算法破解。有些公钥算法是基于除整数分解和离散对数问题以外的问题，'''<font color="#ff8000"> 肖尔Shor算法</font>'''适用于这些问题，例如McEliece密码体制基于编码理论中的一个问题。基于格的密码体制也不被量子计算机破解，寻找一个多项式时间算法来解决二面体隐子群问题，这将打破许多基于格的密码体制，是一个研究得很好的开放性问题。已经证明，应用'''<font color="#ff8000"> Grover算法</font>'''以暴力破解对称（密钥）算法所需的时间大约相当于基础加密算法的2次调用<sup>n/2</sup>，而在经典情况下大约需要2<sup>n</sup>，这意味着对称密钥长度有效地减半：AES-256对于使用'''<font color="#ff8000"> Grover算法</font>'''的攻击的安全性与AES-128针对经典暴力搜索的安全性相同（参见密钥大小）。
Quantum cryptography could potentially fulfill some of the functions of public key cryptography. Quantum-based cryptographic systems could, therefore, be more secure than traditional systems against quantum hacking.
Quantum cryptography could potentially fulfill some of the functions of public key cryptography. Quantum-based cryptographic systems could, therefore, be more secure than traditional systems against quantum hacking.
'''<font color="#ff8000"> 量子密码学Quantum cryptography</font>'''可以实现公开密钥加密的一些功能。因此，基于量子的加密系统可能比传统系统更安全，可以抵御量子黑客攻击。
Besides factorization and discrete logarithms, quantum algorithms offering a more than polynomial speedup over the best known classical algorithm have been found for several problems, including the simulation of quantum physical processes from chemistry and solid state physics, the approximation of Jones polynomials, and solving Pell's equation. No mathematical proof has been found that shows that an equally fast classical algorithm cannot be discovered, although this is considered unlikely. However, quantum computers offer polynomial speedup for some problems. The most well-known example of this is quantum database search, which can be solved by Grover's algorithm using quadratically fewer queries to the database than that are required by classical algorithms. In this case, the advantage is not only provable but also optimal, it has been shown that Grover's algorithm gives the maximal possible probability of finding the desired element for any number of oracle lookups. Several other examples of provable quantum speedups for query problems have subsequently been discovered, such as for finding collisions in two-to-one functions and evaluating NAND trees.
Besides factorization and discrete logarithms, quantum algorithms offering a more than polynomial speedup over the best known classical algorithm have been found for several problems, including the simulation of quantum physical processes from chemistry and solid state physics, the approximation of Jones polynomials, and solving Pell's equation. No mathematical proof has been found that shows that an equally fast classical algorithm cannot be discovered, although this is considered unlikely. However, quantum computers offer polynomial speedup for some problems. The most well-known example of this is quantum database search, which can be solved by Grover's algorithm using quadratically fewer queries to the database than that are required by classical algorithms. In this case, the advantage is not only provable but also optimal, it has been shown that Grover's algorithm gives the maximal possible probability of finding the desired element for any number of oracle lookups. Several other examples of provable quantum speedups for query problems have subsequently been discovered, such as for finding collisions in two-to-one functions and evaluating NAND trees.
除了因式分解和离散对数外，在很多问题上发现，量子算法比最著名的经典算法提供了超过多项式的加速度，其中包括从化学和固态物理模拟量子物理过程，'''<font color="#ff8000"> 琼斯多项式Jones polynomials</font>'''的近似，和解'''<font color="#ff8000"> 佩尔方程Pell's equation</font>'''。目前还没有发现数学上的证明可证明同样快速的经典算法无法被发现，尽管这被认为是不可能的。然而，量子计算机为某些问题提供了多项式加速。最著名的例子是量子数据库搜索，它可以通过'''<font color="#ff8000">格罗夫Grover算法 </font>'''来解决，使用比经典算法所需的查询更少的数据库查询。在这种情况下，这种优势不仅是可证明的，而且是最优的，已经证明Grover的算法为任何数量的oracle查找提供了找到所需元素的最大可能概率。随后又发现了其他几个可证明的量子加速的例子，例如在两对一函数中寻找碰撞和评估NAND树。
Problems that can be addressed with Grover's algorithm have the following properties:
Problems that can be addressed with Grover's algorithm have the following properties:
可以通过 Grover 的算法解决的问题有以下属性:
可以通过 '''<font color="#ff8000">格罗夫Grover算法 </font>'''解决的问题有以下属性:
}}{{self-published inline|date=May 2020}}</ref> However, quantum computers offer polynomial speedup for some problems. The most well-known example of this is ''quantum database search'', which can be solved by [[Grover's algorithm]] using quadratically fewer queries to the database than that are required by classical algorithms. In this case, the advantage is not only provable but also optimal, it has been shown that Grover's algorithm gives the maximal possible probability of finding the desired element for any number of oracle lookups. Several other examples of provable quantum speedups for query problems have subsequently been discovered, such as for finding collisions in two-to-one functions and evaluating NAND trees.{{citation needed|date=May 2020}}
}}{{self-published inline|date=May 2020}}</ref> However, quantum computers offer polynomial speedup for some problems. The most well-known example of this is ''quantum database search'', which can be solved by [[Grover's algorithm]] using quadratically fewer queries to the database than that are required by classical algorithms. In this case, the advantage is not only provable but also optimal, it has been shown that Grover's algorithm gives the maximal possible probability of finding the desired element for any number of oracle lookups. Several other examples of provable quantum speedups for query problems have subsequently been discovered, such as for finding collisions in two-to-one functions and evaluating NAND trees.{{citation needed|date=May 2020}}