Computing quantum discord is NP-complete
arXiv:1305.5941 · doi:10.1088/1367-2630/16/3/033027
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.
The (published) journal version http://iopscience.iop.org/1367-2630/16/3/033027/article is more updated than the arXiv versions, and is accompanied with a general scientific summary for non-specialists in computational complexity
References in corpus (21)
- Entanglement detection
- Quantum discord and the power of one qubit
- Necessary and sufficient condition for non-zero quantum discord
- Distillation of secret key and entanglement from quantum states
- Quantum information can be negative
- Quantum discord and quantum phase transition in spin chains
- Quantum information with Gaussian states
- Interpreting quantum discord through quantum state merging
- Operational interpretations of quantum discord
- Linking Quantum Discord to Entanglement in a Measurement
- The mother of all protocols: Restructuring quantum information's family tree
- Optimal measurements to access classical correlations of two-qubit states
- Quantum discord for two-qubit X states: Analytical formula with very small worst-case error
- Broadcast copies reveal the quantumness of correlations
- An additive and operational entanglement measure: conditional entanglement of mutual information
- Quantum discord as a resource in quantum communication
- Scaling of quantum discord in spin models
- Detecting Multipartite Classical States and their Resemblances
- Distance Bounds on Quantum Dynamics
- Generalized information theoretic measure to discern the quantumness of correlations
- A quasipolynomial-time algorithm for the quantum separability problem
Cited by in corpus (159)
- Quantum discord and its allies: a review
- A Unified View of Quantum Correlations and Quantum Coherence
- Quantum Correlations and Coherence in Spin-1 Heisenberg Chains
- Machine Learning Assisted Many-Body Entanglement Measurement
- Multipartite entanglement measures
- Quantum correlated heat engine with nonlinear spin-spin interactions
- Single-copies estimation of entanglement negativity
- Optimality of Gaussian Discord
- Steered quantum coherence as a signature of quantum phase transitions in spin chains
- General Monogamy of Tsallis -Entropy Entanglement in Multiqubit Systems
- Measuring Fermionic Entanglement: Entropy, Negativity, and Spin Structure
- A comparative study of local quantum Fisher information and local quantum uncertainty in Heisenberg model
- Cost of quantum entanglement simplified
- Operational Entanglement of Symmetry-Protected Topological Edge States
- Singularity in Entanglement Negativity Across Finite Temperature Phase Transitions
- Excited-state entanglement and thermal mutual information in random spin chains
- Quantifying entanglement of formation for two-mode Gaussian states: Analytical expressions for upper and lower bounds and numerical estimation of its exact value
- Semidefinite programming relaxations for quantum correlations
- Quantum correlations in B and K meson systems
- Quantum correlation in degenerate optical parametric oscillators with mutual injections
- Quantifying high-dimensional entanglement with Einstein-Podolsky-Rosen correlations
- Improved Semidefinite Programming Upper Bound on Distillable Entanglement
- Entanglement of Purification in Free Scalar Field Theories
- The dynamics of local quantum uncertainty and trace distance discord for two-qubit X states under decoherence: a comparative study
- Experimental Simultaneous Learning of Multiple Non-Classical Correlations
- A Brief Overview of Bipartite and Multipartite Entanglement Measures
- On the quantum discord of general X states
- Generalized Geometric Measure of Entanglement for Multiparty Mixed States
- Measurement-device-independent entanglement and randomness estimation in quantum networks
- Experimentally accessible lower bounds for genuine multipartite entanglement and coherence measures
- Discordlike correlation of bipartite coherence
- Analytical solutions and criteria for the quantum discord of two-qubit X-states
- System-time entanglement in a discrete time model
- Quantum Discord for multiqubit Systems
- Nonadditivity of Rains' bound for distillable entanglement
- Two-body quantum absorption refrigerators with optomechanical-like interactions
- Equivalence of qubit-environment entanglement and discord generation via pure dephasing interactions and the consequences thereof
- Multipartite entanglement measures: a review
- Two-orbital quantum discord in fermion systems
- Entanglement quantification made easy: Polynomial measures invariant under convex decomposition
- Coherence, entanglement and quantumness in closed and open systems with conserved charge, with an application to many-body localisation
- Quantifying Unknown Quantum Entanglement via a Hybrid Quantum-Classical Machine Learning Framework
- Quantum Darwinism in a composite system: Objectivity versus classicality
- Overarching framework between Gaussian quantum discord and Gaussian quantum illumination
- Redundantly amplified information suppresses quantum correlations in many-body systems
- Calculation of quantum discord in arbitrary dimensions, especially for X- and other specialized states
- Of Local Operations and Physical Wires
- Analytical expression of Genuine Tripartite Quantum Discord for Symmetrical X-states
- Practical measurement-device-independent entanglement quantification
- Entanglement branes, modular flow, and extended topological quantum field theory
- Retrieving the lost fermionic entanglement by partial measurement in noninertial frames
- Dissipative evolution of quantum Gaussian states
- Enhancing the estimation precision of an unknown phase shift in multipartite Glauber coherent states via skew information correlations and local quantum Fisher information
- Entanglement of genuinely entangled subspaces and states: exact, approximate, and numerical results
- Nonequilibrium Effects on Quantum Correlations: Discord, Mutual Information and Entanglement of a Two-Fermionic System in Bosonic and Fermionic Environments
- Direct method for measuring and witnessing quantum entanglement of arbitrary two-qubit states through Hong-Ou-Mandel interference
- Hierarchies of multipartite entanglement for continuous-variable states
- Quantum Correlation Dynamics in Controlled Two-Coupled-Qubit Systems
- Nonstationary models for liquid crystals: A fresh mathematical perspective
- Entanglement entropy after selective measurements in quantum chains
- Quantum Fisher information and skew information correlations in dipolar spin system
- Scalable characterization of localizable entanglement in noisy topological quantum codes
- Estimating localizable entanglement from witnesses
- NMR dynamics of quantum discord for spin-carrying gas molecules in a closed nanopore
- Quantum separability criteria based on realignment moments
- Conclusive Identification of Quantum Channels via Monogamy of Quantum Correlations
- Geometric entanglement and quantum phase transitions in two-dimensional quantum lattice models
- Quantum discord protection from amplitude damping decoherence
- How to observe and quantify quantum-discorded states
- Numerical and analytical results for geometric measure of coherence and geometric measure of entanglement
- Monogamy inequality for entanglement and local contextuality
- Hierarchy of efficiently computable and faithful lower bounds to quantum discord
- How to observe and quantify quantum-discorded states via correlations
- Bounding the amount of entanglement from witness operators
- Preparing tunable Bell-diagonal states on a quantum computer
- Reducing Computational Complexity of Quantum Correlations
- Nonclassicality and criticality in symmetry-protected magnetic phases
- Resonant Multilevel Amplitude Damping Channels
- Generalized conditional entropy optimization for qudit-qubit states
- Accurate calculation of the geometric measure of entanglement for multipartite quantum states
- Sharma-Mittal Quantum Discord
- Sudden transitions of trace distance discord of dipole-dipole coupled two qubits
- Evaluation of entanglement measures by a single observable
- Effects of intrinsic decoherence on discord-like correlation measures of two-qubit spin squeezing model
- Dynamics of measurement induced nonlocality under decoherence
- Qubit-environment Negativity versus Fidelity of conditional environmental states for an NV-center spin qubit interacting with a nuclear environment
- Geometric Rényi Divergence and its Applications in Quantum Channel Capacities
- Construction of genuinely multipartite entangled subspaces and the associated bounds on entanglement measures for mixed states
- Quantum discord and information deficit in spin chains
- Characterizing nonclassical correlation using affinity
- Geometric quantum discord and coherence in a dipolar interacting magnetic system
- A hierarchy of efficient bounds on quantum capacities exploiting symmetry
- Robustness of quantum correlation in quantum energy teleportation
- Finite temperature negativity Hamiltonians of the massless Dirac fermion
- Lower and upper bounds for entanglement of Rényi- entropy
- The hierarchies of "witnesses" and the properties and characterization of entangled states as super entanglement witnesses
- Entangled states in the role of witnesses
- Detecting quantum critical points at finite temperature via quantum teleportation: further models
- Detecting quantum critical points at finite temperature via quantum teleportation
- Witnessing nonclassical correlations via a single-shot experiment on an ensemble of spins using NMR
- Perturbative expansion of entanglement negativity using patterned matrix calculus
- Some measures for fermionic entanglement in the cosmological de Sitter spacetime
- Construction of genuinely entangled multipartite subspaces from bipartite ones by reducing the total number of separated parties
- Generalized approach to quantify correlations in bipartite quantum systems
- Quantum discord of states arising from graphs
- Finite temperature detection of quantum critical points: a comparative study
- Geometric Quantum Discord Signals Non-Factorization
- Computable entanglement conversion witness that is better than the negativity
- Entanglement properties of a measurement-based entanglement distillation experiment
- Lower bounds on concurrence and negativity from a trace inequality
- A measure of quantum correlations that lies approximately between entanglement and discord
- Finite temperature detection of quantum critical points via internal quantum teleportation
- Multipartite Gaussian Entanglement of Formation
- Optimization of Modified Quantum Discord in Projector Space
- The squashed entanglement of the noiseless quantum Gaussian attenuator and amplifier
- Problem of quantifying quantum correlations with non-commutative discord
- Quantum correlations beyond entanglement in a classical-channel model of gravity
- Embedded Quantum Correlations in thermalized quantum Rabi systems
- Geometric quantum discord of an arbitrary two-qudit state: the exact value and general upper bounds
- Unified Framework for Calculating Convex Roof Resource Measures
- Quantumness and the role of locality on quantum correlations
- Multipartite quantum and classical correlations in symmetric n-qubit mixed states
- Condition for zero and non-zero discord in graph Laplacian quantum states
- Extensive Long-Range Entanglement at Finite Temperatures from a Nonequilibrium Bias
- Efficient Characterization of Quantum Evolutions via a Recommender System
- Entropic witness for quantum memory in open system dynamics
- Computing coherence vectors and correlation matrices, with application to quantum discord quantification
- Quantum fidelity of symmetric multipartite states
- Finite-temperature quantum discordant criticality
- Partial-transpose-guided entanglement classes and minimum noise filtering in many-body Gaussian quantum systems
- Gaussian intrinsic entanglement for states with partial minimum uncertainty
- Detecting spacelike vacuum entanglement at all distances and promoting negativity to a necessary and sufficient entanglement measure in many-body regimes
- Analytic Formulas for Quantum Discord of Special Families of N-Qubit States
- Verifying Quantum Memory in the Dynamics of Spin Boson Models
- Gaussian multipartite quantum discord from classical mutual information
- Entanglement and fidelity across quantum phase transitions in locally perturbed topological codes with open boundaries
- Trade-off between Squashed Entanglement and Concurrence in Bipartite Quantum States
- Non-commutative measure of quantum correlations under local operations
- Entanglement quantification from collective measurements processed by machine learning
- Entanglement Meter: Estimation of entanglement with single copy in Interferometer
- Quantitative bounds to propagation of quantum correlations in many-body systems
- Entanglement Cost for Steering Assemblages
- One-way quantum deficit for systems
- Ballistic Entanglement Cloud after a Boundary Quench
- Entanglement cost hierarchies in quantum fragmented mixed states
- Effect of Weak Measurement Reversal on Quantum Correlations in a Correlated Amplitude Damping Channel, with a Neural Network Perspective
- Equivalence regimes for geometric quantum discord and local quantum uncertainty
- Fidelity based Measurement Induced Nonlocality over two-sided measurements
- Correlation energy and quantum correlations in a solvable model
- Analysis of quantum correlations within the ground state of a three level Lipkin model
- Quantum Information Approaches to Quantum Gravity
- Correlation and Entanglement dynamics for two atoms distributed in two isolated thermal cavities
- Extremal Steering Assemblages
- Quantum Versus Classical Advantages in Secret Key Distillation (and Their Links to Quantum Entanglement)
- Non-commutativity measure of quantum discord
- Generation and Detection of Quantum Correlations and Entanglement on a Spin-Based Quantum Information Processor
- Computing partial transposes and related entanglement functions
- Computable Measure of Total Quantum Correlation of Multipartite Systems
- Topological squashed entanglement: nonlocal order parameter for one-dimensional topological superconductors