Fetching the paper…

Reading the bibliography…

Can non-local correlations be discriminated in polynomial time? · Around

2016

Can non-local correlations be discriminated in polynomial time?

Montina, Alberto, Wolf, Stefan

Original
PDF
Post on X

Understand

In view of the importance of quantum non-locality in cryptography, quantum computation and communication complexity, it is crucial to decide whether a given correlation exhibits non-locality or not.

In the light of a theorem by Pitowski, it is generally believed that this problem is computationally intractable.
In this paper, we first prove that the Euclidean distance of given correlations from the local polytope can be computed in polynomial time with arbitrary fixed error, granted the access to a certain oracle.
Namely, given a fixed error, we derive two upper bounds on the running time.

Built on

J. Bell, Physics 1
1964
Earlier work this paper cites.
A. Fine, Phys. Rev. Lett. 48
1982
Earlier work this paper cites.
D. Collins, N. Gisin, J. Phys. A: Math. Theor. 37
1989
Earlier work this paper cites.
S. Boyd, L. Vandenberghe, Convex Optimization
2004
Earlier work this paper cites.
J. Barrett, L. Hardy, and A. Kent, Phys. Rev. Lett. 95
2005
Earlier work this paper cites.
A. Acín, N. Gisin, and L. Masanes, Phys. Rev. Lett. 97
2006
Earlier work this paper cites.

Similar

V. Scarani et al., Phys. Rev. A 74
2006
Cited alongside, same era.
A. Acín, S. Massar, and S. Pironio, New J. Phys. 8
2006
Cited alongside, same era.
A. Acín at al., Phys. Rev. Lett. 98
2007
Cited alongside, same era.
H. Buhrman, R. Cleve, S. Massar, and R. de Wolf, Rev. Mod. Phys. 82
2010
Cited alongside, same era.
R. Colbeck and R. Renner, Nature Physics 8
2012
Cited alongside, same era.
I. Pitowski, Quantum Probability – Quantum Logic
Cited in the paper.

Then

E. Hänggi, R. Renner, S. Wolf, Theor. Comp. Sci. 486
2013
Later among the works it cites.
R. Gallego, Ll. Masanes, G. de la Torre, C. Dhara, L. Aolita, A. Acín, Nature Communications 4
2013
Later among the works it cites.
Ll. Masanes, R. Renner, M. Christandl, A. Winter, J. Barrett, IEEE Trans. Inf. Theory, 60
2014
Later among the works it cites.
C. Bernhard, B. Bessire, A. Montina, M. Pfaffhauser, A. Stefanov, S. Wolf, J. Phys. A: Math. Theor. 42
2014
Later among the works it cites.
A. Montina, S. Wolf, New J. Phys. 18
2016
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…