Top

Quantum Information Processing

Published in:

01-06-2016

Computing the maximum violation of a Bell inequality is an NP-problem

Authors: J. Batle, C. H. Raymond Ooi, S. Abdalla, Armen Bagdasaryan

Published in: Quantum Information Processing | Issue 6/2016

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The number of steps required in order to maximize a Bell inequality for arbitrary number of qubits is shown to grow exponentially with the number of parties involved. The proof that the optimization of such correlation measure is an NP-problem based on an operational perspective involving a Turing machine, which follows a general algorithm. The implications for the computability of the so-called nonlocality for any number of qubits is similar to recent results involving entanglement or similar quantum correlation-based measures.

previous article Sum uncertainty relations based on Wigner–Yanase skew information

next article Quantum cloning disturbed by thermal Davies environment

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Lo, H.-K., Popescu, S., Spiller, T.: Introduction to Quantum Computation and Information. World Scientific, River-Edge (1998)CrossRefMATH

Galindo, A., Martín-Delgado, M.A.: Information and computation: classical and quantum aspects. Rev. Mod. Phys. 74, 347 (2002)ADSMathSciNetCrossRefMATH

Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)MATH

Williams, C.P., Clearwater, S.H.: Explorations in Quantum Computing. Springer, New York (1997)MATH

Williams, C.P.: Quantum Computing and Quantum Communications. Springer, Berlin (1998)

Ekert, A.: Quantum cryptography based on Bell’s theorem. Phys. Rev. Lett. 67, 661 (1991)ADSMathSciNetCrossRefMATH

Bennett, C.H., Brassard, G., Crepeau, C., Jozsa, R., Peres, A., Wootters, W.K.: Teleporting an unknown quantum state via dual classical and Einstein–Podolsky–Rosen channels. Phys. Rev. Lett. 70, 1895 (1993)ADSMathSciNetCrossRefMATH

Bennett, C.H., Wiesner, S.J.: Communication via one- and two-particle operators on Einstein–Podolsky–Rosen states. Phys. Rev. Lett. 69, 2881 (1993)ADSMathSciNetCrossRefMATH

Ekert, A., Jozsa, R.: Quantum computation and Shor’s factoring algorithm. Rev. Mod. Phys. 68, 773 (1996)ADSMathSciNetCrossRef

10.

Berman, G.P., Doolen, G.D., Mainieri, R., Tsifrinovich, V.I.: Introduction to Quantum Computers. World Scientific, Singapore (1998)CrossRefMATH

11.

Werner, R.F.: Quantum states with Einstein–Podolsky–Rosen correlations admitting a hidden-variable model. Phys. Rev. A 40, 4277 (1989)ADSCrossRef

12.

Ollivier, H., Zurek, W.H.: Quantum discord: a measure of the quantumness of correlations. Phys. Rev. Lett. 88, 017901 (2001)ADSCrossRefMATH

13.

Dakic, B., Vedral, V., Brukner, C.: Necessary and sufficient condition for nonzero quantum discord. Phys. Rev. Lett. 105, 190502 (2010)ADSCrossRefMATH

14.

Ferraro, A., Aolita, L., Cavalcanti, D., Cucchietti, F.M., Acín, A.: Almost all quantum states have nonclassical correlations. Phys. Rev. A 81, 052318 (2010)ADSCrossRef

15.

Datta, S., et al.: Quantum discord and the power of one qubit. Phys. Rev. Lett. 100, 050502 (2008)ADSCrossRef

16.

Lu, S., Fu, S.: Geometric measure of quantum discord. Phys. Rev. A 82, 034302 (2010)ADSMathSciNetCrossRefMATH

17.

Brukner, C., Zukowski, M., Zeilinger, A.: Quantum communication complexity protocol with two entangled qutrits. Phys. Rev. Lett. 89, 197901 (2002)ADSCrossRef

18.

Barrett, J., Hardy, L., Kent, A.: No signaling and quantum key distribution. Phys. Rev. Lett. 95, 010503 (2005)ADSCrossRef

19.

Acín, A., Gisin, N., Masanes, Ll: From Bell’s theorem to secure quantum key distribution. Phys. Rev. Lett. 97, 120405 (2006)ADSCrossRefMATH

20.

Acín, A., et al.: Device-independent security of quantum cryptography against collective attacks. Phys. Rev. Lett. 98, 230501 (2007)ADSCrossRef

21.

Bartkiewicz, K., Horst, B., Lemr, K., Miranowicz, A.: Entanglement estimation from Bell inequality violation. Phys. Rev. A 88, 052105 (2013)ADSCrossRef

22.

Campbell, S., Paternostro, M.: Multipartite nonlocality in a thermalized Ising spin chain. Phys. Rev. A 82, 042324 (2010)ADSCrossRef

23.

Gisin, N.: Bell’s inequality holds for all non-product states. Phys. Lett. A 154, 201 (1991)ADSMathSciNetCrossRef

24.

Batle, J., Casas, M.: Nonlocality and entanglement in the XY-model. Phys. Rev. A 82, 062101 (2010)ADSMathSciNetCrossRef

25.

Batle, J., Casas, M.: Nonlocality and entanglement in qubit systems. J. Phys. A Math. Theor. 44, 445304 (2011)ADSMathSciNetCrossRefMATH

26.

Pitowsky, I.: Quantum Probability, Quantum Logic, Lecture Notes in Physics, vol. 321. Springer, Heidelberg (1989)MATH

27.

Clauser, J.F., Horne, M.A., Shimony, A., Holt, R.A.: Proposed experiment to test local hidden-variable theories. Phys. Rev. Lett. 23, 880 (1969)ADSCrossRef

28.

Huang, Yichen: Computing quantum discord is NP-complete. New J. Phys. 16, 033027 (2014)ADSMathSciNetCrossRef

29.

Lawler, E.L., et al.: The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley, West Sussex, Chichester (1985)MATH

30.

Johnson, M.W., et al.: A scalable control system for a superconducting adiabatic quantum optimization processor. Supercond. Sci. Technol. 23, 065004 (2010)ADSCrossRef

31.

Berkley, A.J., et al.: A scalable readout system for a superconducting adiabatic quantum optimization system. Supercond. Sci. Technol. 23, 105014 (2010)ADSCrossRef

32.

Johnson, M.W., et al.: Quantum annealing with manufactured spins. Nature 473, 194 (2011)ADSCrossRef

33.

Brooke, J., et al.: Quantum annealing of a disordered magnet. Science 284, 779–781 (1999)ADSCrossRef

34.

Collins, D., Gisin, N.: A relevant two qubit Bell inequality inequivalent to the CHSH inequality. J. Phys. A Math. Gen. 37, 1775 (2004)ADSMathSciNetCrossRefMATH

35.

Tsirelson, B.S.: Quantum generalizations of Bell’s inequality. Lett. Math. Phys. 4, 93G100 (1980)MathSciNet

36.

Tsirelson, B.S.: Quantum analogues of the Bell inequalities. The case of two spatially separated domains. J. Sov. Math. 36, 557–570 (1987)CrossRef

37.

Tsirelson, B.S.: Some results and problems on quantum Bell-type inequalities. Hadron. J. Suppl. 8, 329–345 (1993)MathSciNetMATH

38.

Toner, B.: Monogamy of nonlocal quantum correlations. Proc. R. Soc. A 465, 59–69 (2009)ADSMathSciNetCrossRefMATH

39.

Mermin, N.D.: Extreme quantum entanglement in a superposition of macroscopically distinct states. Phys. Rev. Lett. 65, 1838 (1990)ADSMathSciNetCrossRefMATH

40.

Ardehali, M.: Bell inequalities with a magnitude of violation that grows exponentially with the number of particles. Phys. Rev. A 46, 5375 (1992)ADSMathSciNetCrossRef

41.

Belinskii, A.V., Klyshko, D.N.: Interference of light and Bell’s theorem. Phys. Usp. 36, 653 (1993)ADSCrossRef

42.

Gisin, N., Bechmann-Pasquinucci, H.: Bell inequality, Bell states and maximally entangled states for n qubits. Phys. Lett. A 246, 1 (1998)ADSMathSciNetCrossRefMATH

43.

Scarani, V., Acín, A., Schenck, E., Aspelmeyer, M.: Nonlocality of cluster states of qubits. Phys. Rev. A 71, 042325 (2005)ADSMathSciNetCrossRefMATH

44.

Svetlichny, G.: Distinguishing three-body from two-body nonseparability by a Bell-type inequality. Phys. Rev. D. 35, 3066 (1987)ADSMathSciNetCrossRef

45.

Collins, D., Gisin, N., Popescu, S., Roberts, D., Scarani, V.: Bell-type inequalities to detect true n-body nonseparability. Phys. Rev. Lett. 88, 170405 (2002)ADSCrossRef

46.

Seevinck, M., Svetlichny, G.: Bell-type inequalities for partial separability in N-particle systems and quantum mechanical violations. Phys. Rev. Lett. 89, 060401 (2002)ADSMathSciNetCrossRefMATH

47.

Boolos, G., Jeffrey, R.: Computability and Logic. Cambridge University Press, Cambridge (1999)MATH

48.

Kirkpatrick, S., Gelatt Jr., C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220, 671 (1983)ADSMathSciNetCrossRefMATH

49.

Avriel, M.: Nonlinear Programming: Analysis and Methods. Dover Publishing, Mineola (2003)MATH

50.

Williams, V.V.: Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, vol. 887 (2012)

51.

Chen, J.-L., Wu, C., Kwek, L.C., Oh, C.H.: Gisin’s theorem for three qubits. Phys. Rev. Lett. 93, 140407 (2004)ADSMathSciNetCrossRef

Title: Computing the maximum violation of a Bell inequality is an NP-problem
Authors: J. Batle
C. H. Raymond Ooi
S. Abdalla
Armen Bagdasaryan
Publication date: 01-06-2016
Publisher: Springer US
Published in: Quantum Information Processing / Issue 6/2016
Print ISSN: 1570-0755
Electronic ISSN: 1573-1332
DOI: https://doi.org/10.1007/s11128-016-1275-2

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 6/2016

Improvement of a quantum broadcasting multiple blind signature scheme based on quantum teleportation

Quantum cloning disturbed by thermal Davies environment

Fast generation of N-atom Greenberger–Horne–Zeilinger state in separate coupled cavities via transitionless quantum driving

Efficient quantum dialogue using entangled states and entanglement swapping without information leakage

Dynamical behavior of quantum correlations between two qubits coupled to an external environment

Study of a monogamous entanglement measure for three-qubit quantum systems