On the power of quantum computation
On the power of quantum computation
复制标题
DOI：
10.1098/rsta.1998.0247
复制
发表时间：
1998-08
期刊：
影响因子：
--
通讯作者：
U. Vazirani
中科院分区：
文献类型：
--
作者：
U. Vazirani
本文综述了“混合参数”的使用，以证明量子校正是不敏感的小扰动。量子计算的这一性质被用来确定量子电路在其基本门的实现中对不准确性是鲁棒的。对小扰动的不敏感性也被用来建立下界，包括表明相对于预言机，NP类在量子计算机上需要指数时间;以及量子算法与黑盒模型中的确定性算法多项式相关。
This paper surveys the use of the ‘hybrid argument’ to prove that quantum corrections are insensitive to small perturbations. This property of quantum computations is used to establish that quantum circuits are robust against inaccuracy in the implementation of its elementary gates. The insensitivity to small perturbations is also used to establish lower–bounds, including showing that relative to an oracle, the class NP requires exponential time on a quantum computer; and that quantum algorithms are polynomially related to deterministic algorithms in the black–box model.