1305.5941 (Yichen Huang)
Yichen Huang
This Letter studies the computational complexity of quantum discord -- a measure of quantum correlation beyond quantum entanglement, and proves the NP-completeness of computing quantum discord. Therefore quantum discord is commonly believed computationally intractable in the sense that the running time of any algorithm for quantum discord scales at least exponentially with the dimension of the Hilbert space, which imposes serious fundamental limitations on the future development of quantum discord. As by-products several entanglement measures, namely entanglement cost, entanglement of formation, relative entropy of entanglement, and squashed entanglement are NP-hard (or NP-complete) to compute. These complexity-theoretic results are directly applicable in common randomness distillation, quantum state merging, entanglement distillation, superdense coding, quantum teleportation, etc. In addition, I prove the NP-completeness of two relevant problems: linear optimization over classical states and determining whether there are classical states in a given convex set of states, providing strong evidence that working with classical states is generically computationally intractable.
View original:
http://arxiv.org/abs/1305.5941
No comments:
Post a Comment