On the power of quantum computation
On the power of quantum computation
复制标题
DOI：
10.1109/sfcs.1994.365701
复制
发表时间：
1994-11
期刊：
影响因子：
--
通讯作者：
Daniel R. Simon
中科院分区：
文献类型：
--
作者：
Daniel R. Simon
计算的量子模型是一个概率模型，类似于概率图灵机，其中的概率定律是量子力学尺度上的粒子遵守的定律，而不是我们从宏观世界中熟悉的规则。我们在这里提出了一个区分两个相当自然的函数类的问题，当函数被给出时，在量子模型中可以证明比在经典概率模型中求解的速度要快得多，当函数被给出时，可能是从任一类上的均匀分布得出的相同的预言。因此，我们提供了令人信服的证据，证明量子模型可能比概率图灵机具有显著更高的复杂性理论能力。事实上，在这项工作的基础上，Shor(1994)最近为离散对数和整数分解问题发展了引人注目的新的量子多项式时间算法。
The quantum model of computation is a probabilistic model, similar to the probabilistic Turing Machine, in which the laws of chance are those obeyed by particles on a quantum mechanical scale, rather than the rules familiar to us from the macroscopic world. We present here a problem of distinguishing between two fairly natural classes of function, which can provably be solved exponentially faster in the quantum model than in the classical probabilistic one, when the function is given as an oracle drawn equiprobably from the uniform distribution on either class. We thus offer compelling evidence that the quantum model may have significantly more complexity theoretic power than the probabilistic Turing Machine. In fact, drawing on this work, Shor (1994) has recently developed remarkable new quantum polynomial-time algorithms for the discrete logarithm and integer factoring problems.>