2013/05/31 by Yichen Huang · 1 citation
Computer Science · Physics and Astronomy · #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Mechanics and Applications #cs.CC #quant-ph
paper · pdf · doi:10.1088/1367-2630/16/3/033027
published as New Journal of Physics 16, 033027 (2014) · The (published) journal version http://iopscience.iop.org/1367-2630/16/3/033027/article is more updated than the arXiv versions, and is accompanied with a general scientific summary for non-specialists in computational complexity
openalex publication_date 2014/03/21 · arxiv created 2014/03/28 · arxiv updated 2014/03/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30
We study the computational complexity of quantum discord (a measure of quantum correlation beyond entanglement), and prove that computing quantum discord is NP-complete. Therefore, quantum discord is computationally intractable: the running time of any algorithm for computing quantum discord is believed to grow exponentially with the dimension of the Hilbert space so that computing quantum discord in a quantum system of moderate size is not possible in practice. As by-products, some entanglement measures (namely entanglement cost, entanglement of formation, relative entropy of entanglement, squashed entanglement, classical squashed entanglement, conditional entanglement of mutual information, and broadcast regularization of mutual information) and constrained Holevo capacity are NP-hard/NP-complete to compute. These complexity-theoretic results are directly applicable in common randomness distillation, quantum state merging, entanglement distillation, superdense coding, and quantum teleportation; they may offer significant insights into quantum information processing. Moreover, we prove the NP-completeness of two typical problems: linear optimization over classical states and detecting classical states in a convex set, providing evidence that working with classical states is generically computationally intractable.