Advances in Engineering Advances in Engineering features breaking research judged by Advances in Engineering advisory team to be of key importance in the Engineering field. Papers are selected from over 10,000 published each week from most peer reviewed journals.
GENERAL SCIENTIFIC SUMMARY
Introduction and background. Quantum correlation is a fundamental feature of quantum mechanics as it is intrinsically different from correlations in classical physics. Quantum entanglement is the most prominent manifestation of quantum correlation, but nontrivial quantum correlation also exists in certain separable states. Quantum discord is the most popular measure of quantum correlation beyond entanglement, and has been an active research topic over the past few years. For instance, it has been argued that it is responsible for the quantum speed-up of DQC1 (a model of mixed-state quantum computation with little entanglement) over classical algorithms. However, computing quantum discord is a difficult problem. Despite considerable effort, few analytical results are known.
Main results. We study the computational complexity of quantum discord and prove that computing quantum discord is NP-complete (a notion of hardness in theoretical computer science). 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 are also NP-hard/NP-complete to compute.
Wider implications. These complexity-theoretic results may offer significant insights into quantum information processing: they are directly applicable in quantum channel capacity, common randomness distillation, quantum state merging and a family of protocols. We provide evidence that working with classical states is generically computationally intractable. We expect this work to be of general interest to researchers in quantum correlation or even quantum information.
Journal Reference
New Journal of Physics Volume 16 March 2014.
Yichen Huang
Department of Physics, University of California, Berkeley, CA 94720, USA
Abstract
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.
