Convex separation from convex optimization for large-scale problems

Abstract

We present a scheme, based on Gilbert's algorithm for quadratic minimization [SIAM J. Contrl., vol. 4, pp. 61-80, 1966], to prove separation between a point and an arbitrary convex set $S\subset {\mathbb{R}}^n$ via calls to an oracle able to perform linear optimizations over $S$. Compared to other methods, our scheme has almost negligible memory requirements and the number of calls to the optimization oracle does not depend on the dimensionality $n$ of the underlying space. We study the speed of convergence of the scheme under different promises on the shape of the set $S$ and/or the location of the point, validating the accuracy of our theoretical bounds with numerical examples. Finally, we present some applications of the scheme in quantum information theory. There we find that our algorithm out-performs existing linear programming methods for certain large scale problems, allowing us to certify nonlocality in bipartite scenarios with upto $42$ measurement settings. We apply the algorithm to upper bound the visibility of two-qubit Werner states, hence improving known lower bounds on Grothendieck's constant $K_G(3)$. Similarly, we compute new upper bounds on the visibility of GHZ states and on the steerability limit of Werner states for a fixed number of measurement settings.

Added reference to the related paper arXiv:1609.06269

References in corpus (8)

• Non-locality and Communication Complexity
• Testing the Hilbert space dimension
• Grothendieck's constant and local models for noisy entangled quantum states
• Adaptive strategy for joint measurements
• Solving Large-Scale Optimization Problems Related to Bell's Theorem
• The device-independent outlook on quantum physics (lecture notes on the power of Bell's theorem)
• Can non-local correlations be discriminated in polynomial time?
• Convex Separation from Optimization via Heuristics

Cited by in corpus (12)

• Better local hidden variable models for two-qubit Werner states and an upper bound on the Grothendieck constant $K_G(3)$
• Quantum measurement incompatibility does not imply Bell nonlocality
• Convex optimization over classes of multiparticle entanglement
• Qutrit witness from the Grothendieck constant of order four
• Multipartite nonlocality and random measurements
• Hilbert-Schmidt distance and entanglement witnessing
• The Platonic solids and fundamental tests of quantum mechanics
• Certifying Quantum Separability with Adaptive Polytopes
• Bounding the detection efficiency threshold in Bell tests using multiple copies of the maximally entangled two-qubit state carried by a single pair of particles
• Keyring models: an approach to steerability
• Algorithm for evaluating distance-based entanglement measures
• Reliable optimization of arbitrary functions over quantum measurements