Computing the maximum violation of a Bell inequality is an NP-problem
From MaRDI portal
Publication:332067
DOI10.1007/S11128-016-1275-2zbMATH Open1348.81072arXiv1503.00272OpenAlexW2290299531MaRDI QIDQ332067FDOQ332067
Authors: C. H. Raymond Ooi, J. Batle, S. Abdalla, A. Bagdasaryan 
Publication date: 27 October 2016
Published in: Quantum Information Processing (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1503.00272
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
Quantum measurement theory, state operations, state preparations (81P15) Quantum coherence, entanglement, quantum correlations (81P40)
Cites Work
- Optimization by simulated annealing
- Quantum cryptography based on Bell’s theorem
- Title not available (Why is that?)
- Necessary and sufficient condition for nonzero quantum discord
- Proposed experiment to test local hidden-variable theories
- Quantum states with Einstein-Podolsky-Rosen correlations admitting a hidden-variable model
- Quantum analogues of the Bell inequalities. The case of two spatially separated domains
- 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
- Information and computation: Classical and quantum aspects
- Nonlocality and entanglement in qubit systems
- Nonlocality of cluster states of qubits
- Monogamy of non-local quantum correlations
- Title not available (Why is that?)
- Title not available (Why is that?)
- A relevant two qubit Bell inequality inequivalent to the CHSH inequality
- Title not available (Why is that?)
- Extreme quantum entanglement in a superposition of macroscopically distinct states
- Communication via one- and two-particle operators on Einstein-Podolsky-Rosen states
- Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels
- Introduction to Quantum Computation and Information
- Quantum discord: a measure of the quantumness of correlations
- Geometric measure of quantum discord
- Computing quantum discord is NP-complete
- Title not available (Why is that?)
- Quantum probability - quantum logic
- From Bell's theorem to secure quantum key distribution
- Title not available (Why is that?)
- Title not available (Why is that?)
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)
