Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1305.5941 · New Journal of Physics

Computing quantum discord is NP-complete

Yichen Huang

Published Mar 21, 2014• 286 citations
arXivHTMLPDF

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.

DOI
10.1088/1367-2630/16/3/033027

Related papers

Reducing computational complexity of quantum correlations

Titas Chanda, Tamoghna Das, Debasis Sadhukhan +3 more

We address the issue of reducing the resource required to compute information-theoretic quantum correlation measures such as quantum discord and quantum work deficit in two qubits and higher-dimensional systems. We show that determination of the quantum correlation measure is possible even if we utilize a restricted set of local measurements. We find that the determination allows us to obtain a closed form of quantum discord and quantum work deficit for several classes of states, with a low error. We show that the computational error caused by the constraint over the complete set of local measurements reduces fast with an increase in the size of the restricted set, implying usefulness of constrained optimization, especially with the increase of dimensions. We perform quantitative analysis to investigate how the error scales with the system size, taking into account a set of plausible constructions of the constrained set. Carrying out a comparative study, we show that the resource required to optimize quantum work deficit is usually higher than that required for quantum discord. We also demonstrate that minimization of quantum discord and quantum work deficit is easier in the case of two-qubit mixed states of fixed ranks and with positive partial transpose in comparison to the corresponding states having nonpositive partial transpose. Applying the methodology to quantum spin models, we show that the constrained optimization can be used with advantage in analyzing such systems in quantum information-theoretic language. For bound entangled states, we show that the error is significantly low when the measurements correspond to the spin observables along the three Cartesian coordinates, and thereby we obtain expressions of quantum discord and quantum work deficit for these bound entangled states.

arXiv:1504.04727•Physical Review A•Dec 1, 2015•13 citations

The role of quantum correlations beyond entanglement in quantum information theory

Alexander Streltsov

Quantum entanglement is the most popular kind of quantum correlations. Its role in several tasks in quantum information theory like quantum cryptography, quantum dense coding and quantum teleportation is indisputable. The role of entanglement in quantum algorithms has also attracted enormous amount of attention in the literature. The research in this direction is motivated by the finding that a quantum computer can efficiently factorize arbitrary integer numbers. Since no classical algorithm is known today that can solve this problem efficiently, this example clearly demonstrates the superiority of a quantum computer compared to its classical counterpart. In this context, entanglement also plays a crucial role: if the quantum computer operates on a pure state without entanglement, then the computational process can be simulated efficiently on a classical computer. In this case entanglement is the key ingredient that makes the difference between a quantum and a classical computer. However, the situation is more involved if the computational process is not perfect. In this case the quantum computer operates on a mixed state, and the role of entanglement is less obvious. A seminal result in this direction is a quantum algorithm known under the acronym DQC1. This algorithm operates on an almost maximally mixed state with vanishingly little entanglement. However, DQC1 can still perform tasks efficiently for which no efficient classical algorithm is known today. Thus, it is reasonable to assume that entanglement in general is not related to the efficiency of a quantum algorithm. Triggered by this observation other kinds of quantum correlations have been studied. In this context a particular measure of quantum correlations known as quantum discord is referred to frequently in the literature. Quantum discord is a measure of quantum correlations beyond entanglement, i.e., a quantum state can have no entanglement, but nonvanishing quantum discord. Quantum discord is also regarded as the key resource in the DQC1 algorithm. Although this statement is still controversial, it was shown under very general assumptions that quantum discord is required if a quantum computer is to show an exponential speedup over any classical algorithm. In this thesis we give a short introduction into the theory of entanglement and general quantum correlations, and further discuss our results. In particular, we show that two different kinds of entanglement measures can coincide. This result is used to build an algorithm for computing entanglement. We also consider the role of quantum correlations for the distribution of entanglement and for the quantum measurement process. We further discuss the behavior of quantum correlations under local noise, and their monogamy properties.

•Jan 1, 2013•1 citation

Quantum discord for two-qubit systems

Shunlong Luo

Quantum discord, as introduced by Olliver and Zurek [Phys. Rev. Lett. 88, 017901 (2001)], is a measure of the discrepancy between two natural yet different quantum analogs of the classical mutual information. This notion characterizes and quantifies quantumness of correlations in bipartite states from a measurement perspective, and is fundamentally different from the various entanglement measures in the entanglement vs separability paradigm. The phenomenon of nonzero quantum discord is a manifestation of quantum correlations due to noncommutativity rather than due to entanglement, and has interesting and significant applications in revealing the advantage of certain quantum tasks. We will evaluate analytically the quantum discord for a large family of two-qubit states, and make a comparative study of the relationships between classical and quantum correlations in terms of the quantum discord. We furthermore compare the quantum discord with the entanglement of formation, and illustrate that the latter may be larger than the former, although for separable states, the entanglement of formation always vanishes and thus is less than the quantum discord.

Physical Review A•Apr 3, 2008•1,060 citations

Entanglement Irreversibility from Quantum Discord and Quantum Deficit

Marcio F. Cornelio, M. C. de Oliveira, F. F. Fanchini

We relate the problem of irreversibility of entanglement with the recently defined measures of quantum correlation--quantum discord and one-way quantum deficit. We show that the entanglement of formation is always strictly larger than the coherent information and the entanglement cost is also larger in most cases. We prove irreversibility of entanglement under local operations and classical communication for a family of entangled states. This family is a generalization of the maximally correlated states for which we also give an analytic expression for the distillable entanglement, the relative entropy of entanglement, the distillable secret key, and the quantum discord.

arXiv:1007.0228•Physical Review Letters•Jul 5, 2011•109 citations

Quantum discord for two-qubit X states

Mazhar Ali, A. R. P. Rau, G. Alber

Quantum discord, a kind of quantum correlation, is defined as the difference between quantum mutual information and classical correlation in a bipartite system. In general, this correlation is different from entanglement, and quantum discord may be nonzero even for certain separable states. Even in the simple case of bipartite quantum systems, this different kind of quantum correlation has interesting and significant applications in quantum information processing. So far, quantum discord has been calculated explicitly only for a rather limited set of two-qubit quantum states and expressions for more general quantum states are not known. In this article, we derive explicit expressions for quantum discord for a larger class of two-qubit states, namely, a seven-parameter family of so called $X$ states that have been of interest in a variety of contexts in the field. We also study the relation between quantum discord, classical correlation, and entanglement for a number of two-qubit states to demonstrate that they are independent measures of correlation with no simple relative ordering between them.

arXiv:1002.3429•Physical Review A•Apr 12, 2010•835 citations

Optimization of Quantum Discord in Projector Space

Chitradeep Gupta

In a pair of correlated quantum systems a measurement in one corresponds to a change in the state of the other. In the process, information is lost. Measurement along which set of projectors would accompany minimum loss in information content is the optimization problem of quantum discord and is an important aspect of a classical to quantum transition because it asks us to look for the most classical states. This optimization problem is known to be NP-complete and is important because discord is defined through it making it a major obstacle on every computation. The standard zero discord condition helps us move to a stronger measure that addresses the correlated observables, in such a context we show that discord minimizes at the diagonal basis of the reduced density matrices and present an analytical expression of the measure.

•Sep 1, 2018•0 citations
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.
We address the issue of reducing the resource required to compute information-theoretic quantum correlation measures such as quantum discord and quantum work deficit in two qubits and higher-dimensional systems. We show that determination of the quantum correlation measure is possible even if we utilize a restricted set of local measurements. We find that the determination allows us to obtain a closed form of quantum discord and quantum work deficit for several classes of states, with a low error. We show that the computational error caused by the constraint over the complete set of local measurements reduces fast with an increase in the size of the restricted set, implying usefulness of constrained optimization, especially with the increase of dimensions. We perform quantitative analysis to investigate how the error scales with the system size, taking into account a set of plausible constructions of the constrained set. Carrying out a comparative study, we show that the resource required to optimize quantum work deficit is usually higher than that required for quantum discord. We also demonstrate that minimization of quantum discord and quantum work deficit is easier in the case of two-qubit mixed states of fixed ranks and with positive partial transpose in comparison to the corresponding states having nonpositive partial transpose. Applying the methodology to quantum spin models, we show that the constrained optimization can be used with advantage in analyzing such systems in quantum information-theoretic language. For bound entangled states, we show that the error is significantly low when the measurements correspond to the spin observables along the three Cartesian coordinates, and thereby we obtain expressions of quantum discord and quantum work deficit for these bound entangled states.
Quantum entanglement is the most popular kind of quantum correlations. Its role in several tasks in quantum information theory like quantum cryptography, quantum dense coding and quantum teleportation is indisputable. The role of entanglement in quantum algorithms has also attracted enormous amount of attention in the literature. The research in this direction is motivated by the finding that a quantum computer can efficiently factorize arbitrary integer numbers. Since no classical algorithm is known today that can solve this problem efficiently, this example clearly demonstrates the superiority of a quantum computer compared to its classical counterpart. In this context, entanglement also plays a crucial role: if the quantum computer operates on a pure state without entanglement, then the computational process can be simulated efficiently on a classical computer. In this case entanglement is the key ingredient that makes the difference between a quantum and a classical computer. However, the situation is more involved if the computational process is not perfect. In this case the quantum computer operates on a mixed state, and the role of entanglement is less obvious. A seminal result in this direction is a quantum algorithm known under the acronym DQC1. This algorithm operates on an almost maximally mixed state with vanishingly little entanglement. However, DQC1 can still perform tasks efficiently for which no efficient classical algorithm is known today. Thus, it is reasonable to assume that entanglement in general is not related to the efficiency of a quantum algorithm. Triggered by this observation other kinds of quantum correlations have been studied. In this context a particular measure of quantum correlations known as quantum discord is referred to frequently in the literature. Quantum discord is a measure of quantum correlations beyond entanglement, i.e., a quantum state can have no entanglement, but nonvanishing quantum discord. Quantum discord is also regarded as the key resource in the DQC1 algorithm. Although this statement is still controversial, it was shown under very general assumptions that quantum discord is required if a quantum computer is to show an exponential speedup over any classical algorithm. In this thesis we give a short introduction into the theory of entanglement and general quantum correlations, and further discuss our results. In particular, we show that two different kinds of entanglement measures can coincide. This result is used to build an algorithm for computing entanglement. We also consider the role of quantum correlations for the distribution of entanglement and for the quantum measurement process. We further discuss the behavior of quantum correlations under local noise, and their monogamy properties.
Quantum discord, as introduced by Olliver and Zurek [Phys. Rev. Lett. 88, 017901 (2001)], is a measure of the discrepancy between two natural yet different quantum analogs of the classical mutual information. This notion characterizes and quantifies quantumness of correlations in bipartite states from a measurement perspective, and is fundamentally different from the various entanglement measures in the entanglement vs separability paradigm. The phenomenon of nonzero quantum discord is a manifestation of quantum correlations due to noncommutativity rather than due to entanglement, and has interesting and significant applications in revealing the advantage of certain quantum tasks. We will evaluate analytically the quantum discord for a large family of two-qubit states, and make a comparative study of the relationships between classical and quantum correlations in terms of the quantum discord. We furthermore compare the quantum discord with the entanglement of formation, and illustrate that the latter may be larger than the former, although for separable states, the entanglement of formation always vanishes and thus is less than the quantum discord.
We relate the problem of irreversibility of entanglement with the recently defined measures of quantum correlation--quantum discord and one-way quantum deficit. We show that the entanglement of formation is always strictly larger than the coherent information and the entanglement cost is also larger in most cases. We prove irreversibility of entanglement under local operations and classical communication for a family of entangled states. This family is a generalization of the maximally correlated states for which we also give an analytic expression for the distillable entanglement, the relative entropy of entanglement, the distillable secret key, and the quantum discord.
Quantum discord, a kind of quantum correlation, is defined as the difference between quantum mutual information and classical correlation in a bipartite system. In general, this correlation is different from entanglement, and quantum discord may be nonzero even for certain separable states. Even in the simple case of bipartite quantum systems, this different kind of quantum correlation has interesting and significant applications in quantum information processing. So far, quantum discord has been calculated explicitly only for a rather limited set of two-qubit quantum states and expressions for more general quantum states are not known. In this article, we derive explicit expressions for quantum discord for a larger class of two-qubit states, namely, a seven-parameter family of so called XXX states that have been of interest in a variety of contexts in the field. We also study the relation between quantum discord, classical correlation, and entanglement for a number of two-qubit states to demonstrate that they are independent measures of correlation with no simple relative ordering between them.
In a pair of correlated quantum systems a measurement in one corresponds to a change in the state of the other. In the process, information is lost. Measurement along which set of projectors would accompany minimum loss in information content is the optimization problem of quantum discord and is an important aspect of a classical to quantum transition because it asks us to look for the most classical states. This optimization problem is known to be NP-complete and is important because discord is defined through it making it a major obstacle on every computation. The standard zero discord condition helps us move to a stronger measure that addresses the correlated observables, in such a context we show that discord minimizes at the diagonal basis of the reduced density matrices and present an analytical expression of the measure.