Discrimination of Non-Local Correlations
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. As proved by Pitowski, this problem is NP-complete, and is thus computationally intractable unless N...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2019-01-01
|
| Series: | Entropy |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1099-4300/21/2/104 |
| _version_ | 1818040904475213824 |
|---|---|
| author | Alberto Montina Stefan Wolf |
| author_facet | Alberto Montina Stefan Wolf |
| author_sort | Alberto Montina |
| collection | DOAJ |
| description | 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. As proved by Pitowski, this problem is NP-complete, and is thus computationally intractable unless NP is equal to P. 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. The first bound is linear in the number of measurements. The second bound scales with the number of measurements to the sixth power. The former holds only for a very high number of measurements, and is never observed in the performed numerical tests. We, then, introduce a simple algorithm for simulating the oracle. In all of the considered numerical tests, the simulation of the oracle contributes with a multiplicative factor to the overall running time and, thus, does not affect the sixth-power law of the oracle-assisted algorithm. |
| first_indexed | 2024-12-10T08:21:56Z |
| format | Article |
| id | doaj.art-0014025c96174d259b339ed7304b2557 |
| institution | Directory Open Access Journal |
| issn | 1099-4300 |
| language | English |
| last_indexed | 2024-12-10T08:21:56Z |
| publishDate | 2019-01-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Entropy |
| spelling | doaj.art-0014025c96174d259b339ed7304b25572022-12-22T01:56:20ZengMDPI AGEntropy1099-43002019-01-0121210410.3390/e21020104e21020104Discrimination of Non-Local CorrelationsAlberto Montina0Stefan Wolf1Facoltà di Informatica, Università della Svizzera italiana, 6900 Lugano, SwitzerlandFacoltà di Informatica, Università della Svizzera italiana, 6900 Lugano, SwitzerlandIn 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. As proved by Pitowski, this problem is NP-complete, and is thus computationally intractable unless NP is equal to P. 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. The first bound is linear in the number of measurements. The second bound scales with the number of measurements to the sixth power. The former holds only for a very high number of measurements, and is never observed in the performed numerical tests. We, then, introduce a simple algorithm for simulating the oracle. In all of the considered numerical tests, the simulation of the oracle contributes with a multiplicative factor to the overall running time and, thus, does not affect the sixth-power law of the oracle-assisted algorithm.https://www.mdpi.com/1099-4300/21/2/104local polytopequantum nonlocalitycommunication complexityoptimization |
| spellingShingle | Alberto Montina Stefan Wolf Discrimination of Non-Local Correlations Entropy local polytope quantum nonlocality communication complexity optimization |
| title | Discrimination of Non-Local Correlations |
| title_full | Discrimination of Non-Local Correlations |
| title_fullStr | Discrimination of Non-Local Correlations |
| title_full_unstemmed | Discrimination of Non-Local Correlations |
| title_short | Discrimination of Non-Local Correlations |
| title_sort | discrimination of non local correlations |
| topic | local polytope quantum nonlocality communication complexity optimization |
| url | https://www.mdpi.com/1099-4300/21/2/104 |
| work_keys_str_mv | AT albertomontina discriminationofnonlocalcorrelations AT stefanwolf discriminationofnonlocalcorrelations |