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:1207.5105 · Physical Review A

Discord and quantum computational resources

Aharon Brodutch

Published Aug 8, 2013• 37 citations
arXivHTMLPDF

Abstract

Discordant states appear in a large number of quantum phenomena and seem to be a good indicator of divergence from classicality. While there is evidence that they are essential for a quantum algorithm to have an advantage over a classical one, their precise role is unclear. We examine the role of discord in quantum algorithms using the paradigmatic framework of restricted distributed quantum gates and show that manipulating discordant states using local operations has an associated cost in terms of entanglement and communication resources. Changing discord reduces the total correlations and reversible operations on discordant states usually require nonlocal resources. Discord alone is, however, not enough to determine the need for entanglement. A more general type of similar quantities, which we call $K$ discord, is introduced as a further constraint on the kinds of operations that can be performed without entanglement resources.

DOI
10.1103/physreva.88.022307

Related papers

Quantum correlations and global coherence in distributed quantum computing

Farid Shähandeh, Austin P. Lund, Timothy C. Ralph

Deviations from classical physics when distant quantum systems become correlated are interesting both fundamentally and operationally. There exist situations where the correlations enable collaborative tasks that are impossible within the classical formalism. Here, we consider the efficiency of quantum computation protocols compared to classical ones as a benchmark for separating quantum and classical resources and argue that the computational advantage of collaborative quantum protocols in the discrete variable domain implies the nonclassicality of correlations. By analyzing a toy model, it turns out that this argument implies the existence of quantum correlations distinct from entanglement and discord. We characterize such quantum correlations in terms of the net global coherence resources inherent within quantum states and show that entanglement and discord can be understood as special cases of our general framework. Finally, we provide an operational interpretation of such correlations as those allowing two distant parties to increase their respective local quantum computational resources only using locally incoherent operations and classical communication.

arXiv:1706.00478•Physical Review A•May 2, 2019•38 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

Operational significance of discord consumption

Thomas Symul, Helen M. Chrzanowski, Syed M. Assad +5 more

For many years, the notion of quantum correlations was equated with the notion of quantum entanglement. The wide range of quantum protocols whose extra-powers over classical protocol were shown to originate from quantum entanglement mostly motivated this. For example, it was shown that for certain class of problems, a quantum computer could provide exponential speed-up over its classical counterpart, given that it relied on quantum entangled resources. Recently, however, the requirement of possessing entanglement to perform efficient quantum computation has been questioned both theoretically [1] and experimentally [2]. It appears that a non-classical quantity called quantum discord [3] is all that is required.

Conference on Lasers and Electro-Optics Europe & European Quantum Electronics Conference (CLEO/Europe-EQEC)•May 1, 2013•1 citation

Entanglement, discord, and the power of quantum computation

Aharon Brodutch, Daniel R. Terno

We show that the ability to create entanglement is necessary for execution of bipartite quantum gates even when they are applied to unentangled states and create no entanglement. Starting with a simple example we demonstrate that to execute such a gate bilocally the local operations and classical communications (LOCC) should be supplemented by shared entanglement. Our results point to the changes in quantum discord, which is a measure of quantumness of correlations even in the absence of entanglement, as the indicator of failure of a LOCC implementation of the gates.

arXiv:1009.2571•Physical Review A•Jan 7, 2011•80 citations

Entanglement as minimal discord over state extensions

Shunlong Luo

The characterization and quantification of quantum correlations, which play an instrumental role in exploring and exploiting the quantum world, have been extensively and intensively studied in the past few decades. Of special prominence and significance are the concepts of entanglement and discord, which are usually regarded as very distinctive quantum correlations, with the latter going beyond the former. In this work we establish a direct and natural link between entanglement and discord via state extensions and reveal that entanglement is actually the intrinsic discord, by which we mean that entanglement is the irreducible residue of discord viewed from ambient spaces. Our approach, taking into account the contextuality of a quantum state and being of a global nature, stands in sharp contrast to the local operations and classical communication paradigm of entanglement, which focuses on the state itself via a local approach. Furthermore, we introduce a figure of merit which, on the one hand, captures the essence of entanglement, i.e., nonlocality and quantumness of correlations, and, on the other hand, leads to a quantitative decomposition of total correlations into classical correlations, dissonance, and entanglement. This demystifies the meaning of entanglement from the perspective of quantum measurements and provides a unified framework for the interplay of various correlations in terms of quantum measurements and mutual information.

Physical Review A•Sep 29, 2016•18 citations

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
Discordant states appear in a large number of quantum phenomena and seem to be a good indicator of divergence from classicality. While there is evidence that they are essential for a quantum algorithm to have an advantage over a classical one, their precise role is unclear. We examine the role of discord in quantum algorithms using the paradigmatic framework of restricted distributed quantum gates and show that manipulating discordant states using local operations has an associated cost in terms of entanglement and communication resources. Changing discord reduces the total correlations and reversible operations on discordant states usually require nonlocal resources. Discord alone is, however, not enough to determine the need for entanglement. A more general type of similar quantities, which we call KKK discord, is introduced as a further constraint on the kinds of operations that can be performed without entanglement resources.
Deviations from classical physics when distant quantum systems become correlated are interesting both fundamentally and operationally. There exist situations where the correlations enable collaborative tasks that are impossible within the classical formalism. Here, we consider the efficiency of quantum computation protocols compared to classical ones as a benchmark for separating quantum and classical resources and argue that the computational advantage of collaborative quantum protocols in the discrete variable domain implies the nonclassicality of correlations. By analyzing a toy model, it turns out that this argument implies the existence of quantum correlations distinct from entanglement and discord. We characterize such quantum correlations in terms of the net global coherence resources inherent within quantum states and show that entanglement and discord can be understood as special cases of our general framework. Finally, we provide an operational interpretation of such correlations as those allowing two distant parties to increase their respective local quantum computational resources only using locally incoherent operations and classical communication.
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.
For many years, the notion of quantum correlations was equated with the notion of quantum entanglement. The wide range of quantum protocols whose extra-powers over classical protocol were shown to originate from quantum entanglement mostly motivated this. For example, it was shown that for certain class of problems, a quantum computer could provide exponential speed-up over its classical counterpart, given that it relied on quantum entangled resources. Recently, however, the requirement of possessing entanglement to perform efficient quantum computation has been questioned both theoretically [1] and experimentally [2]. It appears that a non-classical quantity called quantum discord [3] is all that is required.
We show that the ability to create entanglement is necessary for execution of bipartite quantum gates even when they are applied to unentangled states and create no entanglement. Starting with a simple example we demonstrate that to execute such a gate bilocally the local operations and classical communications (LOCC) should be supplemented by shared entanglement. Our results point to the changes in quantum discord, which is a measure of quantumness of correlations even in the absence of entanglement, as the indicator of failure of a LOCC implementation of the gates.
The characterization and quantification of quantum correlations, which play an instrumental role in exploring and exploiting the quantum world, have been extensively and intensively studied in the past few decades. Of special prominence and significance are the concepts of entanglement and discord, which are usually regarded as very distinctive quantum correlations, with the latter going beyond the former. In this work we establish a direct and natural link between entanglement and discord via state extensions and reveal that entanglement is actually the intrinsic discord, by which we mean that entanglement is the irreducible residue of discord viewed from ambient spaces. Our approach, taking into account the contextuality of a quantum state and being of a global nature, stands in sharp contrast to the local operations and classical communication paradigm of entanglement, which focuses on the state itself via a local approach. Furthermore, we introduce a figure of merit which, on the one hand, captures the essence of entanglement, i.e., nonlocality and quantumness of correlations, and, on the other hand, leads to a quantitative decomposition of total correlations into classical correlations, dissonance, and entanglement. This demystifies the meaning of entanglement from the perspective of quantum measurements and provides a unified framework for the interplay of various correlations in terms of quantum measurements and mutual information.
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.