561
个编辑
更改
跳到导航
跳到搜索
第329行：
第329行： − + − + 第339行：
第339行： − 整数分解是公开密码匙加密系统的保安基础，如果大型整数是少数素数的乘积(例如两个300位素数的乘积) ，一般电脑在计算上是不可行的。通过比较，量子计算机可以有效地解决这个问题使用肖尔的算法找到它的因素。这种能力将使量子计算机能够破解目前使用的许多密码系统，因为解决这个问题需要一个多项式时间(整数位数)算法。特别是，大多数流行的公钥密码都是基于整数因式分解的难度或者离散对数问题，这两个问题都可以通过 Shor 的算法来解决。特别是 RSA、 Diffie-Hellman 和椭圆曲线 Diffie-Hellman 算法可能被破解。它们用于保护安全网页、加密电子邮件和许多其他类型的数据。打破这些限制将对电子隐私和安全产生重大影响。+ + + 第347行：
第349行： − 但是，其他加密算法似乎不会被这些算法破解。一些公开密钥算法是基于问题以外的其他问题，而不是 Shor 的算法所适用的整数分解和离散对数问题，比如基于编码理论中的一个问题的 McEliece 密码系统。基于格的密码体制也不为量子计算机所破解，而求解二面体隐子群问题的多项式时间算法是一个被广泛研究的公开问题，它将破坏许多基于格的密码体制。已经证明，应用 Grover 的算法通过暴力破解对称密钥(secret Key)算法需要的时间大约相当于底层密码算法的调用时间，而在经典情况下，调用时间大约相当于2 < sup > n </sup > ，这意味着对称密钥长度可以有效地减半: 使用 Grover 的算法，AES-128可以对抗经典的暴力搜索法攻击(见密钥大小) ，AES-256具有相同的安全性。+ + + 第359行：
第363行： − + 第367行：
第371行： − 除了因式分解和离散对数，量子算法提供了一个超过多项式加速最知名的经典算法的几个问题，包括从化学和固体物理学的量子物理过程的模拟，琼斯多项式的逼近，和解决佩尔方程。没有任何数学证明能够证明同样快的经典算法不可能被发现，尽管这被认为是不可能的。然而，量子计算机为某些问题提供了多项式加速。这方面最著名的例子是量子数据库搜索，它可以通过 Grover 的算法解决，使用比经典算法所要求的数据库查询二次减少。在这种情况下，该算法的优点不仅是可证明的，而且是最优的。随后又发现了其他几个可证明的量子加速问题的例子，例如用于查找二对一函数中的碰撞和计算 NAND 树。+ + + 第378行：
第384行： + + 第396行：
第404行： − + 第456行：
第464行： − −
→Potential applications
任何'''<font color="#ff8000"> 量子计算</font>'''都可以表示为一个量子逻辑门网络，它来自一个相当小的量子门家族。使这种结构成为可能的门系列的选择被称为通用门系列。一个常见的这样的集合包括所有的单量子比特门以及上面的 量子受控非门CNOT 门。这意味着任何量子计算都可以通过执行一系列带有 量子受控非门CNOT 门的单量子比特门来完成。虽然这个门集合是无限的，但是它可以通过引用 Solovay-Kitaev 定理用一个有限的门集合来代替。多个量子位的表示可以用 Qsphere 来表示。
任何'''<font color="#ff8000"> 量子计算</font>'''都可以表示为一个量子逻辑门网络，它来自一个相当小的量子门家族。使这种结构成为可能的门系列的选择被称为通用门系列。一个常见的这样的集合包括所有的单量子比特门以及上面的 量子受控非门CNOT 门。这意味着任何量子计算都可以通过执行一系列带有 量子受控非门CNOT 门的单量子比特门来完成。虽然这个门集合是无限的，但是它可以通过引用 Solovay-Kitaev 定理用一个有限的门集合来代替。多个量子位的表示可以用 Qsphere 来表示。
== Potential applications ==
== Potential applications 潜在应用==
=== Cryptography ===
=== Cryptography 密码学===
{{Main|Quantum cryptography}}
{{Main|Quantum cryptography}}
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.
整数因式分解是公钥密码系统安全性的基础，如果大整数是几个素数的乘积（例如，两个300位素数的乘积），那么在普通计算机上计算大整数是不可行的。相比之下，量子计算机可以有效地解决这个问题，使用'''<font color="#ff8000"> 肖尔Shor算法</font>'''来寻找它的因子。这种能力将使量子计算机能够破解目前使用的许多密码系统，在这个意义上，将有一个多项式时间（整数位数）算法来解决这个问题。特别是目前流行的公钥密码算法大多是基于整数的因式分解困难或离散对数问题，这两个问题都可以用Shor算法来解决。特别是RSA、Diffie-Hellman和椭圆曲线Diffie-Hellman算法可能会被打破。它们用于保护安全网页、加密电子邮件和许多其他类型的数据。破坏这些将对电子隐私和安全产生重大影响。
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).
然而，其他密码算法似乎并没有被这些算法破解。有些公钥算法是基于除整数分解和离散对数问题以外的问题，Shor算法适用于这些问题，例如McEliece密码体制基于编码理论中的一个问题。基于格的密码体制也不被量子计算机破解，寻找一个多项式时间算法来解决二面体隐子群问题，这将打破许多基于格的密码体制，是一个研究得很好的开放性问题。已经证明，应用Grover算法以暴力破解对称（密钥）算法所需的时间大约相当于基础加密算法的2次调用<sup>n/2</sup>，而在经典情况下大约需要2<sup>n</sup>，这意味着对称密钥长度有效地减半：AES-256对于使用Grover算法的攻击的安全性与AES-128针对经典暴力搜索的安全性相同（参见密钥大小）。
=== Quantum search ===
=== Quantum search 量子搜索===
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>'''。目前还没有发现一个同样快速的经典算法无法被发现的数学证明，尽管这被认为是不可能的。然而，量子计算机为某些问题提供了多项式加速。最著名的例子是量子数据库搜索，它可以通过格罗夫Grover算法来解决，使用比经典算法所需的查询更少的数据库查询。在这种情况下，这种优势不仅是可证明的，而且是最优的，已经证明Grover的算法为任何数量的oracle查找提供了找到所需元素的最大可能概率。随后又发现了其他几个可证明的量子加速的例子，例如在两对一函数中寻找碰撞和评估NAND树。
|title=Quantum Computers|isbn=9781439243497
|title=Quantum Computers|isbn=9781439243497
}}{{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}}
}}{{self-published inline|date=May 2020}}</ref>然而，量子计算机为某些问题提供了多项式加速。这方面最著名的例子是“量子数据库搜索”，它可以通过[[格罗夫算法]]使用比经典算法要求的更少的对数据库的查询来解决。在这种情况下，这种优势不仅是可证明的，而且是最优的，已经证明Grover的算法为任何数量的oracle查询提供了找到所需元素的最大可能概率。随后又发现了其他几个可证明的量子加速的例子，例如在两对一函数中寻找碰撞和评估NAND树。{{citation needed|date=May 2020}}
There is no searchable structure in the collection of possible answers,
There is no searchable structure in the collection of possible answers,
#There is no searchable structure in the collection of possible answers,
#There is no searchable structure in the collection of possible answers,
#在可能的答案集合中没有可搜索的结构，
#The number of possible answers to check is the same as the number of inputs to the algorithm, and
#The number of possible answers to check is the same as the number of inputs to the algorithm, and
建造大型量子计算机存在许多技术挑战。物理学家 David DiVincenzo 列出了实用量子计算机的下列要求:
建造大型量子计算机存在许多技术挑战。物理学家 David DiVincenzo 列出了实用量子计算机的下列要求:
== Obstacles ==
== Obstacles ==