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.
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.
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.
When a quantum system is divided into two local subsystems, measurements on the two subsystems can exhibit correlations beyond those possible in a classical joint probability distribution; these are partially explained by entanglement, and more generally by a wider class of measures such as the quantum discord. In this paper, I introduce a simple thought experiment defining a measure of quantum correlations, which I call the accord, and write the result as a minimax optimization over unitary matrices. I find the exact result for pure states as a simple function of the Schmidt coefficients and provide a complete proof, and I likewise provide and prove the result for several classes of mixed states, notably including all states of two qubits and the experimentally relevant case of a pure state mixed with colorless noise. I demonstrate that for two qubit states the accord provides a tight lower bound on the discord; for Bell diagonal states it is also an upper bound on entanglement.
We examine the evaluation of the minimum information loss due to an unread local measurement in mixed states of bipartite systems, for a general entropic form. Such a quantity provides a measure of quantum correlations, reducing for pure states to the generalized entanglement entropy, while in the case of mixed states it vanishes just for classically correlated states with respect to the measured system, as the quantum discord. General stationary conditions are provided, together with their explicit form for general two-qubit states. Closed expressions for the minimum information loss as measured by quadratic and cubic entropies are also derived for general states of two-qubit systems. As an application, we analyze the case of states with maximally mixed marginals, where a general evaluation is provided, as well as X states and the mixture of two aligned states.
Quantum systems may contain underlying correlations which are inaccessible to computationally bounded observers. We capture this distinction through a framework that analyses bipartite states only using efficiently implementable quantum channels. This leads to a complexity-constrained max-divergence and a corresponding computational min-entropy. The latter quantity recovers the standard operational meaning of the conditional min-entropy: in the fully quantum case, it quantifies the largest overlap with a maximally entangled state attainable via efficient operations on the conditional subsystem. For classical-quantum states, it further reduces to the optimal guessing probability of a computationally bounded observer with access to side information. Lastly, in the absence of side information, the computational min-entropy simplifies to a computational notion of the operator norm. We then establish strong separations between the information-theoretic and complexity-constrained notions of min-entropy. For pure states, there exist highly entangled families of states with extremal min-entropy whose efficiently accessible entanglement in terms of computational min-entropy is exponentially suppressed. For mixed states, the separation is even sharper: the information-theoretic conditional min-entropy can be highly negative while the complexity-constrained quantity remains nearly maximal. Under the cryptographic Learning with Errors hardness assumption, we construct efficiently preparable states exhibiting both separations, even when their preparation circuits are fully known. Overall, our results demonstrate that computational constraints can fundamentally limit the quantum correlations that are observable in practice.
We examine the behavior of quantum correlations of spin pairs in a finite anisotropic XY spin chain immersed in a transverse magnetic field, through the analysis of the quantum discord and the conventional and quadratic one way-information deficits. We first provide a brief review of these measures, showing that the last ones can be obtained as particular cases of a generalized information deficit based on general entropic forms. All these measures coincide with an entanglement entropy in the case of pure states, but can be non-zero in separable mixed states, vanishing just for classically correlated states. It is then shown that their behavior in the exact ground state of the chain exhibits similar features, deviating significantly from that of the pair entanglement below the critical field. In contrast with entanglement, they reach full range in this region, becoming independent of the pair separation and coupling range in the immediate vicinity of the factorizing field. It is also shown, however, that significant differences between the quantum discord and the information deficits arise in the local minimizing measurement that defines them. Both analytical and numerical results are provided.
We examine the behavior of quantum correlations of spin pairs in a finite anisotropic XY spin chain immersed in a transverse magnetic field, through the analysis of the quantum discord and the conventional and quadratic one-way information deficits. We first provide a brief review of these measures, showing that the last ones can be obtained as particular cases of a generalized information deficit based on general entropic forms. All of these measures coincide with an entanglement entropy in the case of pure states, but can be non-zero in separable mixed states, vanishing just for classically correlated states. It is then shown that their behavior in the exact ground state of the chain exhibits similar features, deviating significantly from that of the pair entanglement below the critical field. In contrast with entanglement, they reach full range in this region, becoming independent of the pair separation and coupling range in the immediate vicinity of the factorizing field. It is also shown, however, that significant differences between the quantum discord and the information deficits arise in the local minimizing measurement that defines them. Both analytical and numerical results are provided.