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
- 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
- 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?)
- 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 and inseparable mixed states with positive partial transposition.
- Separability Criterion for Density Matrices
- 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)- Entanglement of purification in free scalar field theories
- SLOCC orbit of rank-deficient two-qubit states: quantum entanglement, quantum discord and EPR steering
- Accurate calculation of the geometric measure of entanglement for multipartite quantum states
- One-norm geometric quantum discord and critical point estimation in the XY spin chain
- Quantum discord of states arising from graphs
- Quantum discord for two-qubit systems in the Bloch channel: effects of longitudinal and transversal relaxation times
- Problem of quantifying quantum correlations with non-commutative discord
- Quantum coherence and correlation in spin models with Dzyaloshinskii-Moriya interaction
- A brief overview of bipartite and multipartite entanglement measures
- Calculation of quantum discord in higher dimensions for \(X\)- and other specialized states
- The dynamics of local quantum uncertainty and trace distance discord for two-qubit \(X\) states under decoherence: a comparative study
- Dynamics of measurement-induced nonlocality under decoherence
- Analytic expression of quantum correlations in qutrit Werner states undergoing local and nonlocal unitary operations
- Analytical expression of genuine tripartite quantum discord for symmetrical X-states
- Geometric Rényi divergence and its applications in quantum channel capacities
- Preparing tunable Bell-diagonal states on a quantum computer
- Sharma-Mittal quantum discord
- Optimized search for complex protocols based on entanglement detection
- Quantum separability criteria based on realignment moments
- Information-theoretical discord for a class of three-qubit X states
- Characterizing nonclassical correlation using affinity
- Local quantum uncertainty for the thermal state of a four-qubit spin chain under decoherence channels
- Exploring the effects of intrinsic decoherence on quantum-memory-assisted entropic uncertainty relation in a Heisenberg spin chain model
- Controlling steady-state entanglement and quantum discord through squeezing angle
- Construction of genuinely entangled multipartite subspaces from bipartite ones by reducing the total number of separated parties
- Entanglement quantification from collective measurements processed by machine learning
- Trade-off between squashed entanglement and concurrence in bipartite quantum states
- Scales of time where the quantum discord allows an efficient execution of the DQC1 algorithm
- Entanglement branes, modular flow, and extended topological quantum field theory
- General bounds for quantum discord and discord distance
- Analytical solutions and criteria for the quantum discord of two-qubit \(X\)-states
- Study of quantum correlation swapping with relative entropy methods
- Classification of two-qubit states
- A note on one-way quantum deficit and quantum discord
- Quantum coherence, correlations and nonclassical states in the two-qubit Rabi model with parametric oscillator
- Study on estimating quantum discord by neural network with prior knowledge
- Dynamics of quantum correlations under intrinsic decoherence in a Heisenberg spin chain model with Dzyaloshinskii-Moriya interaction
- A family of separability criteria and lower bounds of concurrence
- Computable measure of total quantum correlations of multipartite systems
- Geometric quantum discord under noisy environment
- Computing coherence vectors and correlation matrices with application to quantum discord quantification
- Strong NP-hardness of the quantum separability problem
- Physical consequences of P NP and the density matrix renormalization group annealing conjecture
- Computing the maximum violation of a Bell inequality is an NP-problem
- Lieb's concavity theorem, matrix geometric means, and semidefinite optimization
- Fidelity-based measurement-induced nonlocality over two-sided measurements
- Condition for zero and nonzero discord in graph Laplacian quantum states
- Quantum discord and quantum computing -- an appraisal
- Logarithmic negativity in Lifshitz harmonic models
- Contributions of different parts of spin-spin interactions to quantum correlations in a spin ring model in an external magnetic field
- Measurement-induced qudit geometric discord
- Construction of genuinely entangled subspaces and the associated bounds on entanglement measures for mixed states
- Diagonal quantum discord
- Multipartite quantum and classical correlations in symmetric \(n\)-qubit mixed states
- Computable entanglement conversion witness that is better than the negativity
- Lower bounds on concurrence and negativity from a trace inequality
- One-way quantum deficit for \(2\otimes d\) systems
- The squashed entanglement of the noiseless quantum Gaussian attenuator and amplifier
- Fidelity-based unitary operation-induced quantum correlation for continuous-variable systems
- Quantum correlations and Bell's inequality violation in a Heisenberg spin dimer via neutron scattering
- Geometric quantum discord signals non-factorization
- Quantitative bounds to propagation of quantum correlations in many-body systems
- Quantum advantage beyond entanglement in Bayesian game theory
- Finite temperature negativity Hamiltonians of the massless Dirac fermion
- Versatile relative entropy bounds for quantum networks
- Relating an entanglement measure with statistical correlators for two-qudit mixed states using only a pair of complementary observables
- Entanglement meter: estimation of entanglement with single copy in interferometer
- Non-commutative measure of quantum correlations under local operations
- Generalized approach to quantify correlations in bipartite quantum systems
- Dynamic evolution of quantum entanglement with quantum Lyapunov control in a two-qubit Heisenberg XXZ model under the effect of DM and KSEA interactions
- Quantum discord is not extremalized by Gaussian states
- Quantum correlations in one parameter mixed quantum states
- Analytic formulas for quantum discord of special families of N-qubit states
- Quantum obesity and steering ellipsoids for fermionic fields in a dilation black hole
- On the quantum discord of general \(X\) states
- A comparative study of local quantum Fisher information and local quantum uncertainty in Heisenberg XY model
- An easy measure of quantum correlation
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)
