J. Gondzio, J. Gruca, J.A.J. Hall, W. Laskowski, M. Zukowski
Abstract
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 a
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 problems
which are orders of magnitude larger. 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.
Key words: Quantum Information, Large-Scale Optimization, Interior Point Methods, Matrix-Free Methods.