On the role of entanglement in quantum-computational speed-up
On the role of entanglement in quantum-computational speed-up
复制标题
DOI：
10.1098/rspa.2002.1097
复制
发表时间：
2003-08-08
影响因子：
3.5
通讯作者：
Linden, N
中科院分区：
文献类型：
--
作者：
Jozsa, R;Linden, N
对于任何量子算法操作纯态，我们证明了存在的多方纠缠，与输入大小无限增加的缔约方的数量，是必要的，如果量子算法是提供一个指数级的速度超过经典计算。此外，我们证明了该算法可以有效地模拟经典规定的公差77内，即使是一个适当的少量的全球纠缠。我们明确地确定发生增加的多体纠缠在谢尔的算法。我们的研究结果不适用于量子算法的混合状态一般，我们讨论的建议，一个指数级的计算速度可能与混合状态在完全没有纠缠。最后，尽管纠缠在纯态算法中扮演着重要的角色，但我们认为，将纠缠视为量子计算能力的关键资源是一种误导。
For any quantum algorithm operating on pure states, we prove that the presence of multi-partite entanglement, with a number of parties that increases unboundedly with input size, is necessary if the quantum algorithm is to offer an exponential speed-up over classical computation. Furthermore, we prove that the algorithm can be efficiently simulated classically to within a prescribed tolerance 77 even if a suitably small amount of global entanglement is present. We explicitly identify the occurrence of increasing multi-partite entanglement in Sher's algorithm. Our results do not apply to quantum algorithms operating on mixed states in general and we discuss the suggestion that an exponential computational speed-up might be possible with mixed states in the total absence of entanglement. Finally, despite the essential role of entanglement for pure-state algorithms, we argue that it is nevertheless misleading to view entanglement as a key resource for quantum-computational power.