Quantum 2025 – scientific programme
Parts | Days | Selection | Search | Updates | Downloads | Help
THU: Thursday Contributed Sessions
THU 2: Quantum Information: Concepts and Methods I
THU 2.7: Talk
Thursday, September 11, 2025, 15:45–16:00, ZHG002
Sparse semidefinite programming in quantum information theory — •Lucas Vieira1,2 and Costantino Budroni3 — 1Dept. of Computer Science, TU Darmstadt, Darmstadt, 64289 Germany — 2IQOQI-Vienna, Austrian Academy of Sciences, Boltzmanngasse 3, 1090 Vienna, Austria — 3Dept. of Physics "E. Fermi", Univ. of Pisa, Largo B. Pontecorvo 3, 56127 Pisa, Italy
Large-scale semidefinite programs (SDPs) are ubiquitous in quantum information, typically arising from relaxations of harder underlying problems. These relaxations usually incur significant computational costs, requiring efficient representations before numerical tractability. Since relaxations may not yield feasible solutions to the original problem (e.g., the solution only satisfies a relaxed constraint), one typically prioritizes obtaining an optimal value for the objective function over its corresponding optimizer in the relaxation. Inspired by this, we introduce a heuristic method for constructing sparse representations of general SDPs, specifically targeting the sparse structure arising from their sparse objective: a typical scenario in quantum information. Unlike existing approaches, our heuristic method discards irrelevant variables and constraints by finding the effective sparsity implicit in an instance of a problem, not directly apparent from its full definition, but which emerges naturally from its structure. Our method works by iteratively assembling a self-sufficient subset of variables and constraints which, directly or indirectly, affect the objective function. This talk will outline our method and demonstrate its significant advantages in typical SDP relaxations encountered in quantum information.
Keywords: semidefinite programming; SDP; optimization; sparsity; entanglement detection