×

Solving large-scale optimization problems related to Bell’s theorem. (English) Zbl 1293.81011

Summary: Impossibility of finding local realistic models for quantum correlations due to entanglement is an important fact in foundations of quantum physics, gaining now new applications in quantum information theory. We present an in-depth description of a method of testing the existence of such models, which involves two levels of optimization: a higher-level non-linear task and a lower-level linear programming (LP) task. The article compares the performances of the existing implementation of the method, where the LPs are solved with the simplex method, and our new implementation, where the LPs are solved with an innovative matrix-free interior point method. We describe in detail how the latter can be applied to our problem, discuss the basic scenario and possible improvements and how they impact on overall performance. Significant performance advantage of the matrix-free interior point method over the simplex method is confirmed by extensive computational results. The new method is able to solve substantially larger problems. Consequently, the noise resistance of the non-classicality of correlations of several types of quantum states, which has never been computed before, can now be efficiently determined. An extensive set of data in the form of tables and graphics is presented and discussed. The article is intended for all audiences, no quantum-mechanical background is necessary.

MSC:

81P45 Quantum information, communication, networks (quantum-theoretic aspects)
81P40 Quantum coherence, entanglement, quantum correlations
81P68 Quantum computation
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q12 Quantum algorithms and complexity in the theory of computing
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bell, J. S., On the Einstein-Podolsky-Rosen paradox, Physics, 1, 195-200 (1964)
[2] Kaszlikowski, D.; Gnaciński, P.; Żukowski, M.; Miklaszewski, W.; Zeilinger, A., Violations of local realism by two entangled \(N\)-dimensional systems are stronger than for two qubits, Phys. Rev. Lett., 85, 4418-4421 (2000)
[3] Gruca, J.; Laskowski, W.; Żukowski, M.; Kiesel, N.; Wieczorek, W.; Schmid, C.; Weinfurter, H., Nonclassicality thresholds for multiqubit states: numerical analysis, Phys. Rev. A, 82, 012118 (2010)
[5] Gondzio, J., Matrix-free interior point method, Comput. Optim. Appl., 51, 457-480 (2012) · Zbl 1241.90179
[6] Fine, A., Hidden variables, joint probability, and the bell inequalities, Phys. Rev. Lett., 48, 291 (1982)
[7] Gruca, J.; Laskowski, W.; Żukowski, M., Nonclassicality of pure two-qutrit entangled states, Phys. Rev. A, 85, 022118 (2012)
[9] Nielsen, M.; Chuang, I., Quantum Computation and Quantum Information (2000), Cambridge University Press: Cambridge University Press Cambridge, United Kingdom · Zbl 1049.81015
[10] Greenberger, D. M.; Horne, M. A.; Zeilinger, A., Bell’s Theorem, Quantum Theory, and Conceptions of the Universe, 69 (1989), Kluwer Academic: Kluwer Academic Dordrecht, The Netherlands
[11] Scarani, V.; Gisin, N., Spectral decomposition of Bell’s operators for qubits, J. Phys. A: Math. Gen., 34, 6043 (2001) · Zbl 0981.81019
[12] Dantzig, G. B., Linear Programming and Extensions (1963), Princeton University Press: Princeton University Press Princeton · Zbl 0108.33103
[13] Nelder, J. A.; Mead, R., A simplex method for function minimization, Comput. J., 7, 308-313 (1965) · Zbl 0229.65053
[16] Hall, J. A.J.; McKinnon, K. I.M., The simplest examples where the simplex method cycles and conditions where expand fails to prevent cycling, Math. Program., 100, 133-150 (2004) · Zbl 1146.90473
[17] McKinnon, K. I.M., Convergence properties of the Nelder-Mead simplex method in low dimensions, SIAM J. Optim., 9, 148-158 (1998) · Zbl 0962.65049
[18] Press, W. H.; Teukolsky, S.; Vetterling, W.; Flannery, B., Numerical Recipes, The Art of Scientific Computing (2007), Cambridge University Press: Cambridge University Press Cambridge, United Kingdom · Zbl 1132.65001
[19] Wright, S. J., Primal-Dual Interior-Point Methods (1997), SIAM: SIAM Philadelphia · Zbl 0863.65031
[20] Gondzio, J., Interior point methods 25 years later, European J. Oper. Res., 218, 587-601 (2012) · Zbl 1244.90007
[21] Saunders, M., Cholesky-based methods for sparse least squares: the benefits of regularization, (Adams, L.; Nazareth, L., Linear and Nonlinear Conjugate Gradient-Related Methods (1996), SIAM: SIAM Philadelphia, USA), 92-100 · Zbl 0865.65022
[22] Altman, A.; Gondzio, J., Regularized symmetric indefinite systems in interior point methods for linear and quadratic optimization, Optim. Methods Softw., 11-12, 275-302 (1999) · Zbl 0957.90101
[23] Sarkar, V., Optimized unrolling of nested loops, Int. J. Parallel Program., 29, 545-581 (2001) · Zbl 1019.68029
[25] Mermin, N. D., Extreme quantum entanglement in a superposition of macroscopically distinct states, Phys. Rev. Lett., 65, 1838-1840 (1990) · Zbl 0971.81507
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.