Computing the maximum violation of a Bell inequality is an NP-problem
From MaRDI portal
Abstract: The number of steps required in order to maximize a Bell inequality for arbitrary number of qubits is shown to grow exponentially with either the number of steps and the number of parties involved. The proof that the optimization of such correlation measure is a NP-problem is based on an operational perspective involving a Turing machine, which follows a general algorithm. The implications for the computability of the so called {it nonlocality} for any number of qubits is similar to recent results involving entanglement or similar quantum correlation-based measures.
Recommendations
- Computing the maximal violation of Bell inequalities for multipartite qubit via partially symmetric tensor
- A relevant two qubit Bell inequality inequivalent to the CHSH inequality
- Bell's inequalities and quantum communication complexity
- Computing quantum discord is NP-complete
- Near-optimal and explicit Bell inequality violations
Cites work
- scientific article; zbMATH DE number 1579275 (Why is no real title available?)
- scientific article; zbMATH DE number 3467029 (Why is no real title available?)
- scientific article; zbMATH DE number 515467 (Why is no real title available?)
- scientific article; zbMATH DE number 1128569 (Why is no real title available?)
- scientific article; zbMATH DE number 2046035 (Why is no real title available?)
- scientific article; zbMATH DE number 1476921 (Why is no real title available?)
- scientific article; zbMATH DE number 3895002 (Why is no real title available?)
- A relevant two qubit Bell inequality inequivalent to the CHSH inequality
- Bell inequality, Bell states and maximally entangled states for \(n\) qubits
- Bell-type inequalities for partial separability in \(N\)-particle systems and quantum mechanical violations
- Communication via one- and two-particle operators on Einstein-Podolsky-Rosen states
- Computing quantum discord is NP-complete
- Extreme quantum entanglement in a superposition of macroscopically distinct states
- From Bell's theorem to secure quantum key distribution
- Geometric measure of quantum discord
- Information and computation: Classical and quantum aspects
- Introduction to Quantum Computation and Information
- Monogamy of non-local quantum correlations
- Necessary and sufficient condition for nonzero quantum discord
- Nonlocality and entanglement in qubit systems
- Nonlocality of cluster states of qubits
- Optimization by simulated annealing
- Proposed experiment to test local hidden-variable theories
- Quantum analogues of the Bell inequalities. The case of two spatially separated domains
- Quantum cryptography based on Bell’s theorem
- Quantum discord: a measure of the quantumness of correlations
- Quantum probability - quantum logic
- Quantum states with Einstein-Podolsky-Rosen correlations admitting a hidden-variable model
- Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels
Cited in
(4)- Computing the maximal violation of Bell inequalities for multipartite qubit via partially symmetric tensor
- Solving large-scale optimization problems related to Bell's theorem
- On the computational complexity of detecting possibilistic locality
- Certifying optimality of Bell inequality violations: noncommutative polynomial optimization through semidefinite programming and local optimization
This page was built for publication: Computing the maximum violation of a Bell inequality is an NP-problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q332067)
