Convex Optimization Theory


The theoretical study of quantum systems is plagued with complex mathematical problems, and convex optimization theory is the appropriate tool to tackle them. This branch of Operations Research is concerned with the minimization of convex functions over convex regions of the hyperplane. Since any observable physical quantity happens to be convex-linear, many important problems in quantum mechanics, from the computation of ground state energies to the local value of Bell inequalities, fit within the framework of convex optimization theory.

In quantum information theory, the analysis of many communication protocols requires an optimization over all possible operators satisfying a number of polynomial constraints, and sometimes also over all possible Hilbert spaces where such operators act. In [1] we presented a converging hierarchy of computable lower bounds on the solution of the general problem

where P(X) and {Fi (X)} are arbitrary Hermitian polynomials of the noncommuting variables X≡(X1,…,Xm), and ρ is a quantum state. This work represents the foundations of the emerging field of Noncommutative Polynomial Optimization (NPO) theory [2]. The tools of NPO allowed, for the first time, to bound the quantum violation of general Bell inequalities [3]. Very quickly, NPO theory also found application in self-testing, see Black Box Quantum Theory [4] and even in quantum chemistry [5].

In this last regard, in [5] we describe an interesting effect: even though the convergence of our sequential schemes is not guaranteed for optimizations involving unbounded operators, we observe in [5] that, in practice, NPO solvers do provide converging sequences of lower bounds to the ground state energy of any Hamiltonian depending on the position and momentum of a finite number of particles. A detailed analysis showed that this convergence was solely due to the finite numerical precision of the computer. Once the precision of the computer was increased, convergence was lost! Under infinite precision, the sequence of lower bounds on the energy is actually constant, and typically represents a very poor approximation to the ground state energy of any Hamiltonian which is not quadratic. NPO theory thus provides a method that converges, not in spite of numerical errors, but because of them.

More recently, we devised new methods which allow the user to bound the dimensionality of the operator algebras optimized in NPO. This led to a systematic tool to derive dimension witnesses, or Bell-type inequalities which can only be violated by multipartite quantum systems with a sufficiently high Hilbert space dimension [6,7], see Black Box Quantum Theory.

Sometimes the computational resources needed to implement certain primitives of Convex Optimization theory, such as linear and semidefinite programming, are just too demanding for a normal desktop (or even a supercomputer). This is problematic, since many tasks in quantum information theory, including the implementation of the NPO hierarchies, rely on those basic primitives. Therefore, we have lately taken an interest in how to improve the performance of current algorithms in optimization theory.

Given any convex set of vectors, the membership problem (MEM) consists in deciding if a given vector belongs to it. Important problems in quantum information science can be cast as membership problems. E.g: deciding quantum separability, determining if a box is nonlocal (i.e., if it is compatible with the laws of classical physics). A related problem is the strong optimization problem (OPT), where, given a convex set S and a vector b-, we try to identify the point s ̅ in S with greatest overlap b ̅∙s ̅. While working with the tools of convex optimization theory, we noticed that there exist many situations where MEM is intractable in a normal desktop, but OPT can be carried with relative ease.

Figure 8. Schematic illustration of the iterative algorithm that reduces MEM to OPT.

We thus devised an iterative method to solve MEM using an oracle that can solve instances of OPT [8]. While there were other algorithms in the literature to address this problem, all of them were merely theoretical, since their implementation would require an unreasonable amount of computational memory resources. Remarkably, the memory requirements of our algorithm scale linearly with the dimensionality of the convex set. This allowed us to solve entanglement and nonlocality problems previously thought intractable in a normal desktop. It also allowed us to contribute to the field of functional analysis, by improving the known bounds for Grothendieck’s third-order constant KG (3).

Grothendieck’s nth order constant KG (n) is defined as the minimum value such that, for any matrix Aij, the following inequality holds:

The maximization in the left-hand side is performed on dichotomic variables si,tj∈{-1,1}, while the maximization in the right-hand side is over all n-dimensional normalized vectors v ̅i,v ̅j. Grothendieck constants allow computer scientists to devise approximation algorithms to solve one maximization problem given an oracle to solve the other. Since many combinatorial tasks can be mapped to the first maximization, it is a long-standing open problem in optimization theory to determine the exact value of the Grothendieck constants.

As it turns out, finding upper/lower bounds for amounts to verifying/refuting the existence of local hidden variable models for two-qubit Werner states. In these two papers [8, 9] we apply our reduction of MEM to OPT to prove that

Deriving the lower and the upper bound required, respectively, to solve the nonlocality problem in bipartite scenarios with N=42 and N=625 measurement settings per party. To get a grasp on how our algorithm improves over previous schemes, we note that past computations in the literature could not go beyond N=14.

[1] S. Pironio, M. Navascués and A. Acín, Convergent relaxations of polynomial optimization problems with non-commuting variables, SIAM J. Opt. 20, 5, 2157-2180 (2010).

[2] M. Navascués, S. Pironio and A. Acín, Noncommutative Polynomial Optimization. Handbook on Semidefinite, Cone and Polynomial Optimization, M.F. Anjos and J. Lasserre (eds); Springer, 2011.

[3] M. Navascués, S. Pironio and A. Acín, Bounding the set of quantum correlations, Phys. Rev. Lett. 98, 010401 (2007).

[4] T. H. Yang, T. Vértesi, J.-D. Bancal, V. Scarani and M. Navascués, Robust and versatile black-box certification of quantum devices, Phys. Rev. Lett. 113, 040401 (2014).

[5] M. Navascués, A. García-Sáez, A. Acín, S. Pironio and M. B. Plenio, A paradox in bosonic energy computations via semidefinite programming relaxations, New J. Phys. 15, 023026 (2013).

[6] M. Navascués and T. Vértesi, Bounding the set of finite-dimensional quantum correlations, Phys. Rev. Lett. 115, 020501 (2015).

[7] M. Navascués, A. Feix, M. Araújo and T. Vértesi, Characterizing finite-dimensional quantum behavior, Phys. Rev. A 92, 042117 (2015).

[8] S. Brierley, M. Navascués and T. Vértesi, Convex separation from convex optimization for large-scale problems, arXiv:1609.05011.

[9] F. Hirsch, M. T. Quintino, T. Vértesi, M. Navascués and N. Brunner, Better local hidden variable models for two-qubit Werner states and an upper bound on the Grothendieck constant KG(3), arXiv:1609.06114.