先说结论：有些量子算法中无需量子纠缠，仍然可以实现指数加速。量子纠缠在量子计算中是非必要条件。

量子纠缠是物理学家理解量子世界的一个重要的概念。纠缠的两个系统可以表现出奇异的性质，与我们传统理解的世界大不一样。

关于量子纠缠的一般性定义（也沿用至今）是在1989年 Werner 提出来的[1]，并很快将纠缠的概念用在了纠缠在量子密码学、量子压缩编码和量子传态等应用中。

但量子纠缠在量子算法中的作用仍然不明确。

Jozsa 和 Linden 首先指出在纯态量子计算中，需要有纠缠来达到超越经典计算的指数加速效果，此观点在著名的 Shor 算法中得到了印证。由于在 Shor 算法 [2] 中存在纠缠，使得人们认为纠缠是量子计算指数加速的重要资源。

然而，在 1998 年 Knill 和 Laflamme[3] 提出了一个基于混合态的量子算法 – DQC1，比起经典算法，此算法具有指数加速的效果，令大家惊奇的是，此算法中的量子态没有纠缠。

另一方面，C.H. Bennett 等人在1999年指出 [4]，存在没有量子纠缠的量 子态仍然可以表现出非定域性。

这些发现促使人们思考，量子纠缠是不是没那么重要？

2001 年， Zurek[5] 和 Vedral [6]提出了量子失谐的概念。

2008 年， Datta 等人 [7] 将量子失谐的概念应用于 DQC1 算法中，他们发现，在此算法中没有纠缠但量子失谐一直存在，并提出量子失谐可能是量子加速的主要原因，此方法在随后的实验中得到验证 [8]。

这个过程在2011年nature有篇文章做过梳理 [Nature 474, 24 (2011)]

参考文献：

[1] R. F. Werner, Phys. Rev. A 40 , 4277 (1989).

[2]P.W. Shor, Algorithms for quantum computation： discrete logarithms and factoring. IEEE Press, CA:124 (1994).

[3] E. Knill and R. Laflamme, Power of One Bit of Quantum Information. Phys. Rev. Lett. 81 , 5672 (1998).

[4]Charles H. Bennett, David P. DiVincenzo, Christopher A. Fuchs, Tal Mor, Eric
Rains, Peter W.Shor, John A. Smolin, and William K. Wootters, Quantum nonlocality
without entanglement. Phys. Rev. A 59 , 1070 (1999).

[5] Harold Ollivier and Wojciech H. Zurek, Quantum Discord: A Measure of the
Quantumness of Correlations. Phys. Rev. Lett. 88 , 017901 (2001).

[6] L.Henderson and V. Vedral, Classical, quantum and total correlations. J. Phys. A 34 , 6899 (2001).

[7]Animesh Datta, Anil Shaji, and Carlton M. Caves, Quantum Discord and
the Power of One Qubit. Phys. Rev. Lett. 100 , 050502 (2008).

[8] B.P. Lanyon, M. Barbieri, M. P. Almeida, and A. G. White, Experimental
Quantum Computing without Entanglement. Phys. Rev. Lett. 101 , 050502 (2008).

[9] Zeeya Merali, Quantum computing: The power of discord. Nature 474, 24 (2011)

补充：

为了进一步说明量子纠缠在量子计算中是非必要条件，再举个例子。

某些量子体系在发展之初时为了说明此体系可以用作量子计算机，一般会演示一个最简单的量子算法来证明，即单量子比特的D-J算法。单量子比特何谈纠缠，但却可以用来演示量子计算算法。