Convergent relaxations of polynomial optimization problems with non-commuting variables
arXiv:0903.4368 · doi:10.1137/090760155
Abstract
We consider optimization problems with polynomial inequality constraints in non-commuting variables. These non-commuting variables are viewed as bounded operators on a Hilbert space whose dimension is not fixed and the associated polynomial inequalities as semidefinite positivity constraints. Such problems arise naturally in quantum theory and quantum information science. To solve them, we introduce a hierarchy of semidefinite programming relaxations which generates a monotone sequence of lower bounds that converges to the optimal solution. We also introduce a criterion to detect whether the global optimum is reached at a given relaxation step and show how to extract a global optimizer from the solution of the corresponding semidefinite programming problem.
35 pages. v2: Improved notation and revised proof of Theorem 1
References in corpus (3)
Cited by in corpus (96)
- Bell nonlocality
- Secure device-independent quantum key distribution with causally independent measurement devices
- Self-testing of quantum systems: a review
- Specker's Parable of the Over-protective Seer: A Road to Contextuality, Nonlocality and Complementarity (PLUS AN ERRATUM)
- Device-independent witnesses of genuine multipartite entanglement
- Quantum theory based on real numbers can be experimentally falsified
- Bell nonlocality in networks
- A Combinatorial Approach to Nonlocality and Contextuality
- Security of practical private randomness generation
- Zero-error communication via quantum channels, non-commutative graphs and a quantum Lovasz theta function
- Physical characterization of quantum devices from nonlocal correlations
- Using complete measurement statistics for optimal device-independent randomness evaluation
- Bounding temporal quantum correlations
- Bounding the set of finite dimensional quantum correlations
- Family of Bell-like inequalities as device-independent witnesses for entanglement depth
- Algorithm 950: Ncpol2sdpa---Sparse Semidefinite Programming Relaxations for Polynomial Optimization Problems of Noncommuting Variables
- Nonlocality and conflicting interest games
- Security of device-independent quantum key distribution protocols: a review
- Quantum Inflation: A General Approach to Quantum Causal Compatibility
- Semidefinite programming relaxations for quantum correlations
- The convex Positivstellensatz in a free algebra
- Identifying Nonconvexity in the Sets of Limited-Dimension Quantum Correlations
- Device-Independent Randomness Generation in the Presence of Weak Cross-Talk
- A framework for the study of symmetric full-correlation Bell-like inequalities
- Characterizing finite-dimensional quantum behavior
- Computing conditional entropies for quantum correlations
- Efficient device-independent entanglement detection for multipartite systems
- Correlations in entanglement-assisted prepare-and-measure scenarios
- Sparse Noncommutative Polynomial Optimization
- Lower Bounds for Ground States of Condensed Matter Systems
- Device-independent lower bounds on the conditional von Neumann entropy
- Information Causality and Extremal Tripartite Correlations
- Closed sets of correlations: answers from the zoo
- Quantum Bilinear Optimization
- Product-state Approximations to Quantum Ground States
- Informationally restricted correlations: a general framework for classical and quantum systems
- Robust self-testing of steerable quantum assemblages and its applications on device-independent quantum certification
- Semidefinite programming hierarchies for constrained bilinear optimization
- Semi-definite programming and quantum information
- Bell inequalities for three systems and arbitrarily many measurement outcomes
- Extended nonlocal games and monogamy-of-entanglement games
- Optimization over trace polynomials
- Operator Positivstellensätze for noncommutative polynomials positive on matrix convex sets
- Randomness in post-selected events
- Local Randomness: Examples and Application
- Lower Bounding Ground-State Energies of Local Hamiltonians Through the Renormalization Group
- Optimal discrimination between real and complex quantum theories
- Device-Independent Bit Commitment based on the CHSH Inequality
- Device-independent quantification of measurement incompatibility
- Certified algorithms for equilibrium states of local quantum Hamiltonians
- Device-Independent Quantum Key Distribution Based on Routed Bell Tests
- Positive maps and trace polynomials from the symmetric group
- Limitations of semidefinite programs for separable states and entangled games
- Inflation: a Python library for classical and quantum causal compatibility
- Multipartite Nonlocality as a Resource and Quantum Correlations Having Indefinite Causal Order
- Custom Bell inequalities from formal sums of squares
- A convergent inflation hierarchy for quantum causal structures
- Certifying ground-state properties of quantum many-body systems
- Bounding the joint numerical range of Pauli strings by graph parameters
- A paradox in bosonic energy computations via semidefinite programming relaxations
- The future of secure communications: device independence in quantum key distribution
- Noncommutative polynomials nonnegative on a variety intersect a convex set
- Entropy Constraints for Ground Energy Optimization
- The inflation hierarchy and the polarization hierarchy are complete for the quantum bilocal scenario
- Certifying long-range quantum correlations through routed Bell tests
- Proposals for ruling out the real quantum theories in an entanglement-swapping quantum network with causally independent sources
- Certificates of quantum many-body properties assisted by machine learning
- Fast quantum simulation of electronic structure by spectrum amplification
- Probabilistic models on contextuality scenarios
- Synergies Between Operations Research and Quantum Information Science
- Certifying dimension of quantum systems by sequential projective measurements
- Device independent security of quantum key distribution from monogamy-of-entanglement games
- State polynomials: positivity, optimization and nonlinear Bell inequalities
- Prepare-and-measure scenarios with photon-number constraints
- Semidefinite programming in matrix unknowns which are dimension free
- Connector tensor networks: a renormalization-type approach to quantum certification
- The Coming Decades of Quantum Simulation
- Experimental certification of more than one bit of quantum randomness in the two inputs and two outputs scenario
- Verifying the output of quantum optimizers with ground-state energy lower bounds
- Uncertainty relations from state polynomial optimization
- Certifying steady-state properties of open quantum systems
- On characterising assemblages in Einstein-Podolsky-Rosen scenarios
- Noncommutative polynomials describing convex sets
- Entanglement for any definition of two subsystems
- Two convergent NPA-like hierarchies for the quantum bilocal scenario
- Experimental Detection of Non-local Correlations using a Local Measurement-Based Hierarchy on an NMR Quantum Processor
- Learning of Linear Dynamical Systems as a Non-Commutative Polynomial Optimization Problem
- Quantum channel coding: Approximation algorithms and strong converse exponents
- Ruling Out Static Latent Homophily in Citation Networks
- Single trusted qubit is necessary and sufficient for quantum realisation of extremal no-signaling correlations
- Quantum Key Distribution with Imperfections: Recent Advances in Security Proofs
- Mapping Phase Diagrams of Quantum Spin Systems through Semidefinite-Programming Relaxations
- Bell inequalities with overlapping measurements
- On trace-convex noncommutative polynomials
- Matrix Extreme Points and Free extreme points of Free spectrahedra
- Positivity of state, trace, and moment polynomials, and applications in quantum information