Semidefinite Programming for Quantum Information

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 291 papers112 conceptsfrozen 2026-10-04

In quantum information theory, many fundamental questions—such as "Is this state entangled?" or "How much 'magic' does this circuit possess?"—are notoriously difficult to answer. Determining the separability of a quantum state is generally NP-hard, and calculating the rates at which we can distill quantum resources often involves intractable optimizations over infinite-dimensional limits.

However, a powerful computational bridge has emerged: Semidefinite Programming (SDP). By mapping the abstract geometry of quantum states onto the structured world of convex optimization, researchers have transformed once-impossible theoretical questions into problems that can be solved in polynomial time on a standard laptop.

The Natural Symmetry of States and Solvers

The reason SDP is so effective for quantum mechanics lies in a shared mathematical foundation. A quantum state is represented by a density matrix $\rho$ that must be positive semidefinite ($\rho \ge 0$) and have a trace of one. Similarly, a semidefinite program is an optimization problem that minimizes a linear function over the intersection of the cone of positive semidefinite matrices and an affine space.

Because the constraints of quantum mechanics (positivity, linearity, and trace-preservation) mirror the constraints of SDP, we can represent quantum processes as "spectrahedrons"—geometric shapes that SDP solvers can navigate efficiently. As Mihailo Stojnic demonstrated in Optimal quantum detectors for unambiguous detection of mixed states, this allows us to find optimal measurement operators for state discrimination by simply framing the search as a standard optimization task.

Quantifying Resources as Optimization Problems

A central goal of modern research is to treat properties like entanglement, coherence, and "magic" (non-stabilizerness) as physical resources. To do this, we need to quantify them.

Xin Wang and Mark M. Wilde have pioneered the use of SDPs to calculate these resource measures. In Efficiently computable bounds for magic state distillation, they introduced "thauma" measures to quantify the magic required for fault-tolerant quantum computing. Because these measures are formulated as SDPs, they provide tight, computable bounds on the overhead of quantum protocols, moving the field from abstract existence proofs to practical benchmarking.

Similarly, Bartosz Regula and Gerardo Adesso showed in One-Shot Coherence Distillation that the maximum fidelity of distilling coherence from a single quantum state can be calculated exactly using SDP. This "one-shot" regime is critical for real-world quantum devices where we cannot assume an infinite supply of identical states.

Hierarchies for Intractable Problems

While some quantum problems fit perfectly into a single SDP, others—like the "separability problem"—remain fundamentally hard. To tackle these, researchers use SDP hierarchies.

The intuition is to create a sequence of increasingly complex SDPs that "bracket" the true answer. Andrew C. Doherty and Federico M. Spedalieri introduced this approach in Distinguishing Separable and Entangled States. They looked for "symmetric extensions" of a state; if no such extension exists at a certain level of the hierarchy, the state is guaranteed to be entangled. This method was later expanded in Detecting multipartite entanglement to handle systems with many parties.

This hierarchical approach has become a standard tool for certifying quantum properties in "black box" scenarios. For instance, Isadora Veeren and Martin Plávala used a hierarchy of SDPs in Semi-device-independent certification of number of measurements to prove that a device is performing a minimum number of unique, incompatible measurements, even when the device's inner workings are unknown.

Duality and the Search for Witnesses

One of the most powerful features of SDP is duality. Every SDP (the "primal") has a corresponding "dual" problem. In quantum information, this duality often has a deep physical meaning:

  • The Primal problem might find the maximum success probability of a task.
  • The Dual problem often provides a witness—a physical observable that proves a state has a certain property.

As explored by Oded Regev and Ronald de Wolf in Bounded-Error Quantum State Identification and Exponential Separations in Communication Complexity, analyzing the dual of an optimization problem allows researchers to bound the success probability of quantum state identification. This mathematical framework provides the rigorous limits needed to prove that quantum communication can be exponentially more efficient than classical communication.

Applications in Error Mitigation

In the current era of Noisy Intermediate-Scale Quantum (NISQ) devices, SDPs are being used to clean up the "noise" in quantum computations. Jiaqing Jiang and Kun Wang demonstrated in Physical Implementability of Linear Maps and Its Application in Error Mitigation that the cost of simulating a noise-free quantum gate can be calculated as an SDP. By minimizing the "negativity" of a quasiprobability decomposition, they can find the most efficient way to combine noisy physical operations to mimic an ideal, unphysical one.

This transition from abstract theory to computable optimization ensures that as quantum hardware scales, our ability to verify, quantify, and correct it scales as well. By leveraging the language of semidefinite programming, the field has turned the "weirdness" of quantum states into a structured, solvable engineering challenge.

Papers in this version

Showing 60 of 91 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 81 papers
  2. Version 1 · 2026-10-04 · 91 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_semidefinite_programming_for_state_discr_b8397f0f,
  title = {semidefinite programming for state discrimination},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/semidefinite-programming-for-state-discrimination/rdr_b8397f0f1d9f4ab1a345d5fd2938117a},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_semidefinite_programming_for_quantum_inf_b8397f0f_v1,
  title = {Semidefinite Programming for Quantum Information},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/semidefinite-programming-for-quantum-information/rdr_b8397f0f1d9f4ab1a345d5fd2938117a/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}