Introduction

Ncpol2sdpa solves global polynomial optimization problems of either commutative variables or noncommutative operators through a semidefinite programming (SDP) relaxation. The optimization problem can be unconstrained or constrained by equalities and inequalities, and also by constraints on the moments. The objective is to be able to solve large scale optimization problems. Example applications include:

• When the polynomial optimization problem is defined over commutative variables, the generated SDP hierarchy is identical to Lasserre’s. In this case, the functionality resembles the MATLAB toolboxes Gloptipoly, and, with the chordal extension, SparsePOP.
• Relaxations of parametric and bilevel polynomial optimization problems.
• When the polynomials are over noncommutative operators, the generated SDP is a step in the Navascués-Pironio-Acín (NPA) hierarchy. The most notable example is calculating the maximum quantum violation of Bell inequalities, also in multipartite scenarios.
• Nieto-Silleras hierarchy for quantifying randomness and for calculating maximum guessing probability.
• Moroder hierarchy to enable PPT-style and other additional constraints.
• Sums-of-square (SOS) decomposition based on the dual solution.
• Ground-state energy problems: bosonic and fermionic systems, Pauli spin operators. This methodology closely resembles the reduced density matrix (RDM) method.
• Hierarchy for quantum steering.

The implementation has an intuitive syntax for entering problems and it scales for a larger number of noncommutative variables using a sparse representation of the SDP problem. Further details are found in the following paper:

• Peter Wittek. Algorithm 950: Ncpol2sdpa—Sparse Semidefinite Programming Relaxations for Polynomial Optimization Problems of Noncommuting Variables. ACM Transactions on Mathematical Software, 41(3), 21, 2015. DOI: 10.1145/2699464. arXiv:1308.6029.

Copyright and License

Ncpol2sdpa is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

Ncpol2sdpa is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

Acknowledgment

This work is supported by the European Commission Seventh Framework Programme under Grant Agreement Number FP7-601138 PERICLES, by the Red Espanola de Supercomputacion grants number FI-2013-1-0008 and FI-2013-3-0004, and by the Swedish National Infrastructure for Computing projects SNIC 2014/2-7 and SNIC 2015/1-162.