Quantum interference as a resource for quantum speedup
Quantum interference as a resource for quantum speedup
复制标题
量子干涉作为量子加速的资源
DOI：
10.1103/physreva.90.022302
复制
发表时间：
2013
影响因子：
2.9
通讯作者：
D. Stahlke
中科院分区：
文献类型：
--
作者：
D. Stahlke
量子态在某种意义上可以被认为是经典概率分布的推广，但在用于计算或通信时比概率分布更强大。因此，量子加速需要量子态的一些经典概率分布所缺乏的特征。一个这样的特征是干涉。我们量化了干扰，并表明由于少量的操作无法产生大量的干扰（尽管大量的此类操作实际上可以导致量子加速），因此不可能有量子加速。低干扰操作包括稀疏酉、Grover反射、短时间/低能量Hamilton演化和Haar小波变换。从这种操作建立的电路可以通过蒙特卡罗技术利用两个马尔可夫链的凸组合进行经典模拟。应用查询的复杂性，通信的复杂性，和Wigner表示进行了讨论。
Quantum states can in a sense be thought of as generalizations of classical probability distributions, but are more powerful than probability distributions when used for computation or communication. Quantum speedup therefore requires some feature of quantum states that classical probability distributions lack. One such feature is interference. We quantify interference and show that there can be no quantum speedup due to a small number of operations incapable of generating large amounts of interference (although large numbers of such operations can in fact lead to quantum speedup). Low-interference operations include sparse unitaries, Grover reflections, short time/low energy Hamiltonian evolutions, and the Haar wavelet transform. Circuits built from such operations can be classically simulated via a Monte Carlo technique making use of a convex combination of two Markov chains. Applications to query complexity, communication complexity, and the Wigner representation are discussed.