Source-linked AI summary
Computing quantum discord is NP-complete
Yichen Huang
TL;DR
The paper asks how hard it is to compute quantum correlations beyond entanglement, given the tractability contrast between classicality detection and quantitative measures. It proves NP-completeness for quantum discord and related quantities through complexity reductions, establishing computational intractability with applications across quantum information processing.
Problem
Quantum correlation exists beyond entanglement, but the computational complexity of quantitatively computing quantum discord was unresolved.
Method
The paper proves hardness and membership results using reductions from entanglement-measure problems, including a Koashi–Winter-based reduction for quantum discord.
Results
Computing quantum discord is NP-complete, while several entanglement measures and constrained Holevo capacity are NP-hard or NP-complete.
Takeaways & Limitations
The results apply to decoherence-related yield losses in quantum state merging, entanglement distillation, superdense coding, and quantum teleportation.
Takeaways & Limitations
Open questions remain about efficient approximation, tractable state classes, other quantum-correlation measures, and continuous-variable or Gaussian systems.
Abstract
from arXiv · showhide
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.
1 Introduction
Quantum discord captures quantum correlations beyond entanglement, but its computational complexity is substantially harder than detecting classicality. The paper proves that computing discord is NP-complete and derives related hardness results for quantum-information tasks and classical-state problems.
- Motivation: Quantum discord measures quantum correlation beyond entanglement and is linked to quantum speed-up in computation with little entanglement.It is also relevant to common randomness distillation, quantum state merging, entanglement distillation, and communication protocols.
- Motivation: The classicality problem is polynomial-time solvable, whereas separability detection is NP-complete under an inverse-polynomial promise gap.This contrast motivates studying the complexity of computing quantum discord itself.
- Main contribution: Computing quantum discord is proved NP-complete, implying believed exponential running time in the Hilbert-space dimension.The paper states that practical computation for moderate-size quantum systems is therefore not possible in practice.
- Main contribution: The results extend to several entanglement measures, constrained Holevo capacity, and direct applications in quantum-information processing.The paper also studies two classical-state problems, supporting generic computational intractability when working with classical states.
2 NP-hardness/NP-completeness of computing entanglement measures
The paper establishes hardness results for computing several entanglement measures by reducing from the promised-gap separability problem. The formulation uses finite-precision approximations and exposes both certificate-based membership and scope limitations.
- Definitions: Entanglement cost and distillable entanglement quantify asymptotic LOCC conversion rates involving maximally entangled states.Entanglement cost is the minimum formation rate, while distillable entanglement is the maximum extraction rate.
- Definitions: Entanglement of formation minimizes average entanglement entropy over pure-state ensembles realizing the target bipartite state.The ensemble cardinality can be restricted to at most m2n2 for an m × n state.
- Definitions: Relative entropy of entanglement measures distance to the separable-state set, while squashed and related measures optimize quantities over extensions or constrained states.The definitions include regularization, quantum-classical restrictions, and auxiliary-system extensions.
- Caveats: The formulation assumes polynomial-bit real numbers and approximate computational problems, with intractability persisting even when small errors are allowed.For the theorem’s threshold formulation, binary search can recover the target precision with repeated oracle calls.
- Hardness framework: The promised-gap separability problem is NP-complete for inverse-polynomial trace-distance separation, with related exponential-gap and quasi-polynomial-time results.These complexity statements provide the source problem for the reductions.
- Hardness results: Computing entanglement of formation and relative entropy of entanglement is NP-complete, while several other listed measures are NP-hard or NP-complete under inverse-polynomial gaps.The theorem uses a real threshold a and promise gap ǫ = 1/poly(m, n).
- Hardness results: The hardness proof reduces from separability using distance bounds, and NP membership follows from certificates such as optimal ensembles or closest separable states.The reduction sets a = 0 and ǫ = δ2/(2448mn log 2).
- Caveats: The stated hardness proof does not apply to distillable entanglement because an entangled state can have zero distillable entanglement.Whether computing some regularized measures efficiently remains open.
3 NP-completeness of computing quantum discord
The paper proves that computing quantum discord is NP-complete, using reductions from entanglement of formation through relations involving optimal measurements. The result applies to both POVM- and von Neumann-measurement definitions and their regularized variants.
- Quantum discord is defined as quantum mutual information minus classical correlation obtained by measuring subsystem B.
- The measurement-based classical correlation optimizes over von Neumann measurements or POVMs, with corresponding discord variants D_N and D_P.An optimal POVM can be restricted to at most n^2 operators when subsystem B has dimension n.
- Computing D_P(ρ_AB|B) is NP-complete under an inverse-polynomial promise gap ϵ = 1/poly(m,n).The same statement holds for D_N, J_N, and J_P, as well as computing regularized discord D∞.
- Membership in NP uses optimal measurements as certificates, while hardness follows from polynomial-time reductions from entanglement of formation.The reduction uses the Koashi–Winter relation for D_P and an analogous relation for D_N.
4 NP-completeness of computing constrained Holevo capacity
The paper proves NP-completeness for computing constrained Holevo capacity and NP-hardness for its regularized version. The proof reduces entanglement-of-formation computation to channel capacity using a channel derived from a bipartite state.
- The constrained Holevo capacity optimizes classical information transmission through a quantum channel over ensembles of pure input states.The ensemble decomposition can be restricted to at most n^2 states.
- Computing χ_Φ(ρ) is NP-complete under an inverse-polynomial promise gap ϵ = 1/poly(n_i,n_o).The regularized constrained capacity χ∞_Φ(ρ) is NP-hard to compute.
- Membership in NP uses an optimal pure-state ensemble as a certificate, and hardness follows by reducing entanglement of formation to constrained capacity.For a bipartite state σ_AB, the constructed channel has input dimension n_i = rank(σ_AB) = O(mn) and output dimension n_o = m.
- Unregularized Holevo capacity χ_Φ is also NP-complete under the same inverse-polynomial promise-gap formulation.
- The scaling of the promise gap for computing χ_Φ was not established in earlier work, while the complexity of χ∞_Φ remains open.
5 Applications
The paper connects computational hardness results to common randomness distillation, quantum state merging, and decoherence losses across several quantum-information protocols.
- Common randomness: Regularized classical correlation and regularized one-way classical deficit are NP-hard to compute, making one-way distillable common randomness computationally difficult.The paper identifies one-way distillable common randomness with regularized classical correlation and regularized one-way classical deficit.
- Quantum state merging: The minimum entanglement consumed in extended quantum state merging is an operational interpretation of quantum discord and is NP-complete to compute.
- Protocol applications: Quantum discord equals the minimum loss from decoherence in the yields of FQSW and descendant protocols, including distillation, superdense coding, and teleportation.Here, yield refers respectively to entanglement consumed, entanglement distilled, classical information encoded, or qubits teleported.
6 Computational complexity of classical states
The paper proves that two representative tasks involving classical states are NP-complete: linear optimization and detecting whether a convex set contains a classical state.
- State classes: A quantum-classical state has zero one-sided quantum discord for the measured subsystem, while classical-classical states form a more restricted class.
- Linear optimization over classical states: Proposition 1 establishes NP-completeness of linear optimization over classical-classical states, and the same holds for quantum-classical states.The promise gap is ε = 1/poly(m, n).
- Linear optimization over classical states: The optimization problem asks whether the maximum expectation tr(ρABO) over classical states is at least d or at most d−ε.
- Detecting classical states: Proposition 2 establishes NP-completeness of deciding whether a polynomially represented convex set contains a classical-classical state or is separated from all such states.The separation promise uses trace distance at least δ = 1/poly(m, n); the analogous result holds for quantum-classical states.
- Detecting classical states: The hardness proof for detecting classical states reduces the separability problem to convex-set intersection, using non-increase of trace norm under partial trace.
7 Conclusion and outlook
The paper concludes that computing quantum discord is NP-complete and that related entanglement measures, constrained Holevo capacity, and classical-state tasks are computationally hard.
- Conclusion: Computing quantum discord is NP-complete, and its algorithms are believed to require running time exponential in Hilbert-space dimension.The paper states that moderate-size quantum systems therefore make practical computation impossible.
- Conclusion: The results also establish NP-hardness or NP-completeness for several entanglement measures and constrained Holevo capacity.
- Conclusion: The paper presents NP-completeness results for two classical-state problems as evidence that working with classical states is generically computationally intractable.
- Outlook: Open problems include efficient approximation of quantum discord, efficient computation for important state classes, and the complexity of other quantum-correlation measures.
- Outlook: For continuous-variable systems, the complexity of Gaussian entanglement of formation and Gaussian quantum discord remains open, despite efficient separability testing for multimode Gaussian states.