Discrimination of Non-Local Correlations.

Area of Science:

• Quantum Information Science
• Computational Complexity Theory

Background:

• Quantum non-locality is fundamental to quantum cryptography, computation, and communication complexity.
• Deciding if a correlation exhibits non-locality is an NP-complete problem, posing computational challenges.

Purpose of the Study:

• To develop a polynomial-time algorithm for computing the Euclidean distance of correlations from the local polytope.
• To analyze the computational complexity and performance of the proposed algorithm, including oracle-assisted approaches.

Main Methods:

• Proving that the Euclidean distance from the local polytope can be computed in polynomial time with a fixed error, given access to a specific oracle.
• Deriving two upper bounds on the running time: one linear in the number of measurements (for very high numbers) and another scaling with the sixth power of measurements.
• Introducing and evaluating a simple algorithm for simulating the oracle.

Main Results:

• The Euclidean distance computation is achievable in polynomial time with arbitrary fixed error using an oracle.
• Two distinct upper bounds on running time were established, with the sixth-power scaling being more generally applicable in tests.
• Oracle simulation was found to contribute multiplicatively to runtime without altering the sixth-power scaling law.

Conclusions:

• The study presents a computationally feasible method for quantifying quantum non-locality via distance to the local polytope.
• The developed oracle simulation provides a practical approach for analyzing quantum correlations, maintaining the established complexity scaling.