Computing quantum discord is NP-complete
From MaRDI portal
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 5595794 (Why is no real title available?)
- scientific article; zbMATH DE number 1282443 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- A new criterion for zero quantum discord
- A quasipolynomial-time algorithm for the quantum separability problem
- An introduction to entanglement measures
- Can Quantum-Mechanical Description of Physical Reality Be Considered Complete?
- Classical complexity and quantum entanglement
- Classical deterministic complexity of Edmonds' Problem and quantum entanglement
- Classical randomness in quantum measurements
- Classical, quantum and total correlations
- Common randomness in information theory and cryptography. I. Secret sharing
- Common randomness in information theory and cryptography. II. CR capacity
- Communication via one- and two-particle operators on Einstein-Podolsky-Rosen states
- Computational complexity of the quantum separability problem
- Distance bounds on quantum dynamics
- Distillation of secret key and entanglement from quantum states
- Distilling Common Randomness From Bipartite Quantum States
- Distinguishability of quantum states under restricted families of measurements with an application to quantum data hiding
- Entanglement Detection: Complexity and Shannon Entropic Criteria
- Equivalence of additivity questions in quantum information theory
- Erratum to: Faithful squashed entanglement
- Faithful squashed entanglement
- Geometric measure of quantum discord
- Inequalities in Fourier analysis
- Mixed-state entanglement and quantum error correction
- Necessary and sufficient condition for nonzero quantum discord
- Proposed experiment to test local hidden-variable theories
- Quantifying Entanglement
- Quantum discord as a resource in quantum communication
- Quantum discord: a measure of the quantumness of correlations
- Quantum entanglement
- Quantum locking of classical correlations and quantum discord of classical-quantum states
- Quantum state merging and negative information
- Remarks on additivity of the Holevo channel capacity and of the entanglement of formation
- Semidefinite Programming
- Separability Criterion for Density Matrices
- Separability criterion and inseparable mixed states with positive partial transposition.
- Strong NP-hardness of the quantum separability problem
- Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels
- The asymptotic entanglement cost of preparing a quantum state
- The capacity of the quantum channel with general signal states
- The complexity of theorem-proving procedures
- The mother of all protocols: restructuring quantum information's family tree
- “Squashed entanglement”: An additive entanglement measure
Cited in
(77)- Physical consequences of P NP and the density matrix renormalization group annealing conjecture
- A comparative study of local quantum Fisher information and local quantum uncertainty in Heisenberg XY model
- Fidelity-based measurement-induced nonlocality over two-sided measurements
- Entanglement branes, modular flow, and extended topological quantum field theory
- Entanglement meter: estimation of entanglement with single copy in interferometer
- Classification of two-qubit states
- Study of quantum correlation swapping with relative entropy methods
- A note on one-way quantum deficit and quantum discord
- Preparing tunable Bell-diagonal states on a quantum computer
- Sharma-Mittal quantum discord
- Construction of genuinely entangled subspaces and the associated bounds on entanglement measures for mixed states
- Information-theoretical discord for a class of three-qubit X states
- Characterizing nonclassical correlation using affinity
- Calculation of quantum discord in higher dimensions for \(X\)- and other specialized states
- Quantum discord and quantum computing -- an appraisal
- Trade-off between squashed entanglement and concurrence in bipartite quantum states
- Local quantum uncertainty for the thermal state of a four-qubit spin chain under decoherence channels
- One-way quantum deficit for \(2\otimes d\) systems
- Entanglement of purification in free scalar field theories
- Lower bounds on concurrence and negativity from a trace inequality
- Problem of quantifying quantum correlations with non-commutative discord
- Quantum discord is not extremalized by Gaussian states
- A brief overview of bipartite and multipartite entanglement measures
- On the quantum discord of general \(X\) states
- Fidelity-based unitary operation-induced quantum correlation for continuous-variable systems
- Geometric quantum discord signals non-factorization
- The dynamics of local quantum uncertainty and trace distance discord for two-qubit \(X\) states under decoherence: a comparative study
- Controlling steady-state entanglement and quantum discord through squeezing angle
- Quantum correlations and Bell's inequality violation in a Heisenberg spin dimer via neutron scattering
- Quantum correlations in one parameter mixed quantum states
- Geometric Rényi divergence and its applications in quantum channel capacities
- Measurement-induced qudit geometric discord
- Computable measure of total quantum correlations of multipartite systems
- Geometric quantum discord under noisy environment
- One-norm geometric quantum discord and critical point estimation in the XY spin chain
- General bounds for quantum discord and discord distance
- Diagonal quantum discord
- Analytic formulas for quantum discord of special families of N-qubit states
- Quantum discord for two-qubit systems in the Bloch channel: effects of longitudinal and transversal relaxation times
- Computable entanglement conversion witness that is better than the negativity
- Computing coherence vectors and correlation matrices with application to quantum discord quantification
- Analytic expression of quantum correlations in qutrit Werner states undergoing local and nonlocal unitary operations
- Quantum separability criteria based on realignment moments
- Quantum obesity and steering ellipsoids for fermionic fields in a dilation black hole
- Strong NP-hardness of the quantum separability problem
- Analytical solutions and criteria for the quantum discord of two-qubit \(X\)-states
- Construction of genuinely entangled multipartite subspaces from bipartite ones by reducing the total number of separated parties
- Dynamics of quantum correlations under intrinsic decoherence in a Heisenberg spin chain model with Dzyaloshinskii-Moriya interaction
- Computing the maximum violation of a Bell inequality is an NP-problem
- Exploring the effects of intrinsic decoherence on quantum-memory-assisted entropic uncertainty relation in a Heisenberg spin chain model
- Quantum coherence and correlation in spin models with Dzyaloshinskii-Moriya interaction
- Optimized search for complex protocols based on entanglement detection
- Entanglement quantification from collective measurements processed by machine learning
- Finite temperature negativity Hamiltonians of the massless Dirac fermion
- Accurate calculation of the geometric measure of entanglement for multipartite quantum states
- SLOCC orbit of rank-deficient two-qubit states: quantum entanglement, quantum discord and EPR steering
- Lieb's concavity theorem, matrix geometric means, and semidefinite optimization
- An easy measure of quantum correlation
- The squashed entanglement of the noiseless quantum Gaussian attenuator and amplifier
- Versatile relative entropy bounds for quantum networks
- Contributions of different parts of spin-spin interactions to quantum correlations in a spin ring model in an external magnetic field
- Study on estimating quantum discord by neural network with prior knowledge
- Condition for zero and nonzero discord in graph Laplacian quantum states
- Dynamic evolution of quantum entanglement with quantum Lyapunov control in a two-qubit Heisenberg XXZ model under the effect of DM and KSEA interactions
- Relating an entanglement measure with statistical correlators for two-qudit mixed states using only a pair of complementary observables
- Multipartite quantum and classical correlations in symmetric \(n\)-qubit mixed states
- Logarithmic negativity in Lifshitz harmonic models
- A family of separability criteria and lower bounds of concurrence
- Analytical expression of genuine tripartite quantum discord for symmetrical X-states
- Quantum discord of states arising from graphs
- Scales of time where the quantum discord allows an efficient execution of the DQC1 algorithm
- Quantum coherence, correlations and nonclassical states in the two-qubit Rabi model with parametric oscillator
- Generalized approach to quantify correlations in bipartite quantum systems
- Non-commutative measure of quantum correlations under local operations
- Dynamics of measurement-induced nonlocality under decoherence
- Quantitative bounds to propagation of quantum correlations in many-body systems
- Quantum advantage beyond entanglement in Bayesian game theory
This page was built for publication: Computing quantum discord is NP-complete
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5143185)
