561
个编辑
更改
跳到导航
跳到搜索
第308行：
第308行： − +
→Estimating Gauss sums估计高斯和
===Estimating Gauss sums估计高斯和===
===Estimating Gauss sums估计高斯和===
A [[Gauss sum]] is a type of [[exponential sum]]. The best known classical algorithm for estimating these sums takes exponential time. Since the discrete logarithm problem reduces to Gauss sum estimation, an efficient classical algorithm for estimating Gauss sums would imply an efficient classical algorithm for computing discrete logarithms, which is considered unlikely. However, quantum computers can estimate Gauss sums to polynomial precision in polynomial time.<ref>
A [[Gauss sum]] is a type of [[exponential sum]]. The best known classical algorithm for estimating these sums takes exponential time. Since the discrete logarithm problem reduces to Gauss sum estimation, an efficient classical algorithm for estimating Gauss sums would imply an efficient classical algorithm for computing discrete logarithms, which is considered unlikely. However, quantum computers can estimate Gauss sums to polynomial precision in polynomial time.
[[高斯和]]是[[指数和]]的一种。最著名的经典算法估计这些总和需要指数时间。由于离散对数问题归结为高斯和估计，一个有效的经典算法估计高斯和将意味着一个有效的经典算法计算离散对数，这被认为是不可能的。然而，量子计算机可以在多项式时间内精确地估计高斯和。<ref>
[[高斯和]]是[[指数和]]的一种。最著名的经典算法估计这些总和需要指数时间。由于离散对数问题归结为高斯和估计，一个有效的经典算法估计高斯和将意味着一个有效的经典算法计算离散对数，这被认为是不可能的。然而，量子计算机可以在多项式时间内精确地估计高斯和。<ref>