Solving large-scale optimization problems related to Bell's theorem

DOI10.1016/J.CAM.2013.12.003zbMATH Open1293.81011DBLPjournals/jcam/GondzioGHLZ14arXiv1204.3587OpenAlexW2153112940WikidataQ62476673 ScholiaQ62476673MaRDI QIDQ2252425FDOQ2252425

J. A. J. Hall, Jacek Gondzio, Wiesław Laskowski, Marek Żukowski, Jacek A. Gruca

Publication date: 17 July 2014

Published in: Journal of Computational and Applied Mathematics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1204.3587

zbMATH Keywords

interior point methodsquantum informationlarge-scale optimizationmatrix-free methods

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• A Simplex Method for Function Minimization
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Interior point methods 25 years later
• Extreme quantum entanglement in a superposition of macroscopically distinct states
• Regularized symmetric indefinite systems in interior point methods for linear and quadratic optimization
• Matrix-free interior point method
• The simplest examples where the simplex method cycles and conditions where EXPAND fails to prevent cycling
• Convergence of the Nelder--Mead Simplex Method to a Nonstationary Point
• Title not available (Why is that?)
• Spectral decomposition of Bell's operators for qubits
• Optimized unrolling of nested loops

Cited In (2)

• A quantum interior-point predictor–corrector algorithm for linear programming
• Highly noise resistant multiqubit quantum correlations

Uses Software

• LAPACK
• GLPK
• SciPy
• fminsearch

This page was built for publication: Solving large-scale optimization problems related to Bell's theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2252425)