Algorithm 950: Ncpol2sdpa---Sparse Semidefinite Programming Relaxations for Polynomial Optimization Problems of Noncommuting Variables
arXiv:1308.6029 · doi:10.1145/2699464
Abstract
A hierarchy of semidefinite programming (SDP) relaxations approximates the global optimum of polynomial optimization problems of noncommuting variables. Generating the relaxation, however, is a computationally demanding task, and only problems of commuting variables have efficient generators. We develop an implementation for problems of noncommuting problems that creates the relaxation to be solved by SDPA -- a high-performance solver that runs in a distributed environment. We further exploit the inherent sparsity of optimization problems in quantum physics to reduce the complexity of the resulting relaxations. Constrained problems with a relaxation of order two may contain up to a hundred variables. The implementation is available in Python. The tool helps solve problems such as finding the ground state energy or testing quantum correlations.
17 pages, 3 figures, 1 table, 2 algorithms, the algorithm is available at http://peterwittek.github.io/ncpol2sdpa/
References in corpus (3)
Cited by in corpus (57)
- Bell nonlocality in networks
- Optimal randomness certification from one entangled bit
- Self-testing through EPR-steering
- Bounding the sets of classical and quantum correlations in networks
- Semidefinite programming relaxations for quantum correlations
- Computing conditional entropies for quantum correlations
- A framework for quantum-secure device-independent randomness expansion
- Device-Independent Secret Sharing and a Stronger Form of Bell Nonlocality
- Efficient device-independent entanglement detection for multipartite systems
- Sparse Noncommutative Polynomial Optimization
- Experimentally feasible semi-device-independent certification of outcome POVMs
- A Genuine Multipartite Bell Inequality for Device-independent Conference Key Agreement
- Experimental certification of an informationally complete quantum measurement in a device-independent protocol
- Device-independent lower bounds on the conditional von Neumann entropy
- Characterising and bounding the set of quantum behaviours in contextuality scenarios
- Unveiling quantum entanglement in many-body systems from partial information
- Experimental robust self-testing of the state generated by a quantum network
- Device-independent quantum key distribution based on Bell inequalities with more than two inputs and two outputs
- Exponentially decreasing critical detection efficiency for any Bell inequality
- Semi-definite programming and quantum information
- Quantum prescriptions are more ontologically distinct than they are operationally distinguishable
- Measurement compatibility in Bell nonlocality tests
- Mutually Unbiased Balanced Functions & Generalized Random Access Codes
- Adaptive Hybridizable Discontinuous Galerkin discretization of the Grad-Shafranov equation by extension from polygonal subdomains
- Comment on "Fully device-independent conference key agreement" [Phys. Rev. A 97, 022307 (2018)]
- Certifying long-range quantum correlations through routed Bell tests
- Naturally restricted subsets of nonsignaling correlations: typicality and convergence
- Device independent security of quantum key distribution from monogamy-of-entanglement games
- Generalizing optimal Bell inequalities
- SymDPoly: symmetry-adapted moment relaxations for noncommutative polynomial optimization
- Experimental certification of more than one bit of quantum randomness in the two inputs and two outputs scenario
- Correlations constrained by composite measurements
- Fairness in Forecasting and Learning Linear Dynamical Systems
- Verifying the output of quantum optimizers with ground-state energy lower bounds
- Quantum Magic Rectangles: Characterization and Application to Certified Randomness Expansion
- Secure and robust randomness with sequential quantum measurements
- Generalized measurements on qubits in quantum randomness certification and expansion
- Quantum sets of the multicolored-graph approach to contextuality
- Quantum Strategies for Rendezvous and Domination Tasks on Graphs with Mobile Agents
- Fast semidefinite programming with feedforward neural networks
- Enhancing key rates of QKD protocol by Coincidence Detection
- Learning of Linear Dynamical Systems as a Non-Commutative Polynomial Optimization Problem
- Device-independent secret key rates via a post-selected Bell inequality
- Finding optimal Bell inequalities using the cone-projection technique
- Device-independent Shannon entropy certification
- Partial ignorance communication tasks in quantum theory
- A Fine-Grained Variant of the Hierarchy of Lasserre
- Long-distance device-independent quantum key distribution with standard optics tools
- Entangled systems are unbounded sources of nonlocal correlations and of certified random numbers
- Device Independent Quantum Key Activation
- Ruling Out Static Latent Homophily in Citation Networks
- Long-Distance Device-Independent Conference Key Agreement
- Positivity of state, trace, and moment polynomials, and applications in quantum information
- Quantum description of reality is epistemically incomplete
- Device-independent secure correlations in sequential quantum scenarios
- A Robust Unscented Transformation for Uncertain Moments
- Constraint-Aware Discrete Black-Box Optimization Using Tensor Decomposition