Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1609.05011

Convex separation from convex optimization for large-scale problems

STEPHEN D. BRIERLEY, Miguel Navascués, Tamás Vértesi

Published Sep 16, 2016• 18 citations
arXivHTMLPDF

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.

DOI
10.48550/arxiv.1609.05011

Related papers

Convex optimization using quantum oracles

Joran van Apeldoorn, András Gilyén, Sander Gribling +1 more

We study to what extent quantum algorithms can speed up solving convex optimization problems. Following the classical literature we assume access to a convex set via various oracles, and we examine the efficiency of reductions between the different oracles. In particular, we show how a separation oracle can be implemented using O~(1) quantum queries to a membership oracle, which is an exponential quantum speed-up over the Ω(n) membership queries that are needed classically. We show that a quantum computer can very efficiently compute an approximate subgradient of a convex Lipschitz function. Combining this with a simplification of recent classical work of Lee, Sidford, and Vempala gives our efficient separation oracle. This in turn implies, via a known algorithm, that O~(n) quantum queries to a membership oracle suffice to implement an optimization oracle (the best known classical upper bound on the number of membership queries is quadratic). We also prove several lower bounds: Ω(n) quantum separation (or membership) queries are needed for optimization if the algorithm knows an interior point of the convex set, and Ω(n) quantum separation queries are needed if it does not.

arXiv:1809.00643•Quantum•Jan 13, 2020•35 citations

Quantum algorithms and lower bounds for convex optimization

Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li +1 more

While recent work suggests that quantum computers can speed up the solution of semidefinite programs, little is known about the quantum complexity of more general convex optimization. We present a quantum algorithm that can optimize a convex function over an n -dimensional convex body using O ~ ( n ) queries to oracles that evaluate the objective function and determine membership in the convex body. This represents a quadratic improvement over the best-known classical algorithm. We also study limitations on the power of quantum computers for general convex optimization, showing that it requires Ω ~ ( n ) evaluation queries and Ω ( n ) membership queries.

arXiv:1809.01731•Quantum•Jan 13, 2020•43 citations

Quantum State Local Distinguishability via Convex Optimization

Alessandro Cosentino

Entanglement and nonlocality play a fundamental role in quantum computing. To understand the interplay between these phenomena, researchers have considered the model of local operations and classical communication, or LOCC for short, which is a restricted subset of all possible operations that can be performed on a multipartite quantum system. The task of distinguishing states from a set that is known a priori to all parties is one of the most basic problems among those used to test the power of LOCC protocols, and it has direct applications to quantum data hiding, secret sharing and quantum channel capacity. The focus of this thesis is on state distinguishability problems for classes of quantum operations that are more powerful than LOCC, yet more restricted than global operations, namely the classes of separable and positive-partial-transpose (PPT) measurements. We \nbuild a framework based on convex optimization (on cone programming, in particular) to study such problems. Compared to previous approaches to the problem, the method described in this thesis provides precise numerical bounds and quantitative analytic results. By combining the duality theory of cone programming with the channel-state duality, we also establish a novel connection between the state distinguishability problem and the study of positive linear maps, which is a topic of independent interest in quantum information theory. \n \nWe apply our framework to several questions that were left open in previous works regarding the distinguishability of maximally entangled states and unextendable product sets. First, we exhibit small sets of orthogonal maximally entangled states in that are not perfectly distinguishable by LOCC. As a consequence of this, we show a gap between the power of PPT and separable measurements for the task of distinguishing sets consisting only of maximally entangled states. Furthermore, we prove tight bounds on the entanglement cost that is necessary to distinguish any sets of Bell states, thus showing that quantum teleportation is optimal for this task. Finally, we provide an easily checkable characterization of when an unextendable product set is perfectly discriminated by separable measurements, along with the first known example of an unextendable product set that cannot be perfectly discriminated by separable measurements.

•Aug 24, 2015•0 citations

Convex Set Approximation Problems in Quantum Information

Eric Baracho Dore Fernandes

This thesis investigates methods to approximate convex sets which involve minimizing the Hausdorff metric between a set and certain subsets. We begin by giving a lower bound for the Hausdorff metric between a hypersphere and a circumscribed simplex. We show that this bound is achieved by the regular simplex. Next, we form a lower bound on the Hausdorff distance between the convex hull of the joint numerical range of positive operator valued-measures and the probability simplex. An entanglement witness is a linear functional that separates the convex compact set of separable states from certain entangled states in the Hilbert space. We investigate the applications of our methods by exploring the problem of finding a polytope generated by entanglement witnesses that has minimal distance to the set of separable states.

•Feb 21, 2021•0 citations

Hilbert-Schmidt distance and entanglement witnessing

Palash Pandya, Omer Sakarya, Marcin Wieśniak

Gilbert proposed an algorithm for bounding the distance between a given point and a convex set. We apply the Gilbert's algorithm to get an upper bound on the Hilbert-Schmidt distance between a given state and the set of separable states. While Hilbert-Schmidt distance does not form a proper entanglement measure, it can nevertheless be useful for witnessing entanglement. We provide a few methods based on the Gilbert's algorithm that can reliably qualify a given state as strongly entangled or practically separable, while being computationally efficient. The method also outputs successively improved approximations to the closest separable state for the given state. We demonstrate the efficacy of the method with examples.

arXiv:1811.06599•Physical Review A•Jul 7, 2020•25 citations

Convex semidefinite tensor optimization and quantum entanglement

Liding Xu, Ye-Chao Liu, Sebastian Pokutta

The cone of positive-semidefinite (PSD) matrices is fundamental in convex optimization, and we extend this notion to tensors, defining PSD tensors, which correspond to separable quantum states. We study the convex optimization problem over the PSD tensor cone. While this convex cone admits a smooth reparameterization through tensor factorizations (analogous to the matrix case), it is not self-dual. Moreover, there are currently no efficient algorithms for projecting onto or testing membership in this cone, and the semidefinite tensor optimization problem, although convex, is NP-hard. To address these challenges, we develop methods for computing lower and upper bounds on the optimal value of the problem. We propose a general-purpose iterative refinement algorithm that combines a lifted alternating direction method of multipliers with a cutting-plane approach. This algorithm exploits PSD tensor factorizations to produce heuristic solutions and refine the solutions using cutting planes. Since the method requires a linear minimization oracle over PSD tensors, we design a spatial branch-and-bound algorithm based on convex relaxations and valid inequalities. Our framework allows us to study the white-noise mixing threshold, which characterizes the entanglement properties of quantum states. Numerical experiments on benchmark instances demonstrate the effectiveness of the proposed methods.

math.OCCross-listedarXiv:2511.05258•Nov 10, 2025•0 citations
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⊂RnS\subset\mathbb{R}^{n}S⊂Rn via calls to an oracle able to perform linear optimizations over SSS. 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 nnn of the underlying space. We study the speed of convergence of the scheme under different promises on the shape of the set SSS 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 424242 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 KG(3)K_G(3)KG​(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.
We study to what extent quantum algorithms can speed up solving convex optimization problems. Following the classical literature we assume access to a convex set via various oracles, and we examine the efficiency of reductions between the different oracles. In particular, we show how a separation oracle can be implemented using O~(1) quantum queries to a membership oracle, which is an exponential quantum speed-up over the Ω(n) membership queries that are needed classically. We show that a quantum computer can very efficiently compute an approximate subgradient of a convex Lipschitz function. Combining this with a simplification of recent classical work of Lee, Sidford, and Vempala gives our efficient separation oracle. This in turn implies, via a known algorithm, that O~(n) quantum queries to a membership oracle suffice to implement an optimization oracle (the best known classical upper bound on the number of membership queries is quadratic). We also prove several lower bounds: Ω(n) quantum separation (or membership) queries are needed for optimization if the algorithm knows an interior point of the convex set, and Ω(n) quantum separation queries are needed if it does not.
While recent work suggests that quantum computers can speed up the solution of semidefinite programs, little is known about the quantum complexity of more general convex optimization. We present a quantum algorithm that can optimize a convex function over an n -dimensional convex body using O ~ ( n ) queries to oracles that evaluate the objective function and determine membership in the convex body. This represents a quadratic improvement over the best-known classical algorithm. We also study limitations on the power of quantum computers for general convex optimization, showing that it requires Ω ~ ( n ) evaluation queries and Ω ( n ) membership queries.
Entanglement and nonlocality play a fundamental role in quantum computing. To understand the interplay between these phenomena, researchers have considered the model of local operations and classical communication, or LOCC for short, which is a restricted subset of all possible operations that can be performed on a multipartite quantum system. The task of distinguishing states from a set that is known a priori to all parties is one of the most basic problems among those used to test the power of LOCC protocols, and it has direct applications to quantum data hiding, secret sharing and quantum channel capacity. The focus of this thesis is on state distinguishability problems for classes of quantum operations that are more powerful than LOCC, yet more restricted than global operations, namely the classes of separable and positive-partial-transpose (PPT) measurements. We \nbuild a framework based on convex optimization (on cone programming, in particular) to study such problems. Compared to previous approaches to the problem, the method described in this thesis provides precise numerical bounds and quantitative analytic results. By combining the duality theory of cone programming with the channel-state duality, we also establish a novel connection between the state distinguishability problem and the study of positive linear maps, which is a topic of independent interest in quantum information theory. \n \nWe apply our framework to several questions that were left open in previous works regarding the distinguishability of maximally entangled states and unextendable product sets. First, we exhibit small sets of orthogonal maximally entangled states in that are not perfectly distinguishable by LOCC. As a consequence of this, we show a gap between the power of PPT and separable measurements for the task of distinguishing sets consisting only of maximally entangled states. Furthermore, we prove tight bounds on the entanglement cost that is necessary to distinguish any sets of Bell states, thus showing that quantum teleportation is optimal for this task. Finally, we provide an easily checkable characterization of when an unextendable product set is perfectly discriminated by separable measurements, along with the first known example of an unextendable product set that cannot be perfectly discriminated by separable measurements.
This thesis investigates methods to approximate convex sets which involve minimizing the Hausdorff metric between a set and certain subsets. We begin by giving a lower bound for the Hausdorff metric between a hypersphere and a circumscribed simplex. We show that this bound is achieved by the regular simplex. Next, we form a lower bound on the Hausdorff distance between the convex hull of the joint numerical range of positive operator valued-measures and the probability simplex. An entanglement witness is a linear functional that separates the convex compact set of separable states from certain entangled states in the Hilbert space. We investigate the applications of our methods by exploring the problem of finding a polytope generated by entanglement witnesses that has minimal distance to the set of separable states.
Gilbert proposed an algorithm for bounding the distance between a given point and a convex set. We apply the Gilbert's algorithm to get an upper bound on the Hilbert-Schmidt distance between a given state and the set of separable states. While Hilbert-Schmidt distance does not form a proper entanglement measure, it can nevertheless be useful for witnessing entanglement. We provide a few methods based on the Gilbert's algorithm that can reliably qualify a given state as strongly entangled or practically separable, while being computationally efficient. The method also outputs successively improved approximations to the closest separable state for the given state. We demonstrate the efficacy of the method with examples.
The cone of positive-semidefinite (PSD) matrices is fundamental in convex optimization, and we extend this notion to tensors, defining PSD tensors, which correspond to separable quantum states. We study the convex optimization problem over the PSD tensor cone. While this convex cone admits a smooth reparameterization through tensor factorizations (analogous to the matrix case), it is not self-dual. Moreover, there are currently no efficient algorithms for projecting onto or testing membership in this cone, and the semidefinite tensor optimization problem, although convex, is NP-hard. To address these challenges, we develop methods for computing lower and upper bounds on the optimal value of the problem. We propose a general-purpose iterative refinement algorithm that combines a lifted alternating direction method of multipliers with a cutting-plane approach. This algorithm exploits PSD tensor factorizations to produce heuristic solutions and refine the solutions using cutting planes. Since the method requires a linear minimization oracle over PSD tensors, we design a spatial branch-and-bound algorithm based on convex relaxations and valid inequalities. Our framework allows us to study the white-noise mixing threshold, which characterizes the entanglement properties of quantum states. Numerical experiments on benchmark instances demonstrate the effectiveness of the proposed methods.