论文标题
基本量子算法
Basic Quantum Algorithms
论文作者
论文摘要
量子计算的发展迅速，以至于迫使我们重新审视，重写和更新理论的基础。基本量子算法会重新审视最早的量子算法。旅程始于1985年，德意志试图同时评估两个域点的功能。然后，在1992年，Deutsch和Jozsa创建了一种量子算法，该算法决定了布尔函数是恒定还是平衡。次年，伯恩斯坦（Bernstein）和Vazirani意识到，可以使用相同的算法来识别一组线性布尔函数中的特定布尔函数。 1994年，西蒙（Simon）引入了一种新颖的量子算法，该算法确定函数是一对一还是指数级比任何经典算法的速度要快。同年，Shor开发了两种开创性的量子算法，用于整数分解和计算离散对数，对广泛使用的加密方法构成威胁。 1995年，基塔耶夫（Kitaev）提出了Shor算法的替代版本，该版本在许多其他应用中都很有价值。次年，格罗弗（Grover）设计了一种量子搜索算法，该算法在四边形上比其经典等效物更快。该工作强调了电路模型，提供了所有这些出色算法的详细描述。
Quantum computing is evolving so rapidly that it forces us to revisit, rewrite, and update the foundations of the theory. Basic Quantum Algorithms revisits the earliest quantum algorithms. The journey began in 1985 with Deutsch attempting to evaluate a function at two domain points simultaneously. Then, in 1992, Deutsch and Jozsa created a quantum algorithm that determines whether a Boolean function is constant or balanced. The following year, Bernstein and Vazirani realized that the same algorithm could be used to identify a specific Boolean function within a set of linear Boolean functions. In 1994, Simon introduced a novel quantum algorithm that determined whether a function was one-to-one or two-to-one exponentially faster than any classical algorithm for the same problem. That same year, Shor developed two groundbreaking quantum algorithms for integer factoring and calculating discrete logarithms, posing a threat to the widely used cryptography methods. In 1995, Kitaev proposed an alternative version of Shor's algorithms that proved valuable in numerous other applications. The following year, Grover devised a quantum search algorithm that was quadratically faster than its classical equivalent. With an emphasis on the circuit model, this work provides a detailed description of all these remarkable algorithms.
