14.3 Quantum Semidefinite Programming
In Semidefinite Programming (SDP), one optimises a linear function subject to the constraint that an affine combination of symmetric matrices is positive semidefinite. Such a constraint is non-linear and non-smooth, but convex, so semidefinite programs are convex optimisation problems. Semidefinite programming unifies several standard problems (e.g., linear and quadratic programming) and finds many applications in engineering and combinatorial optimisation [317]. Similarly to finding a quantum counterpart to the classical kernel method, we can specify a quantum version of the SDP.
14.3.1 Classical semidefinite programming
The SDP can be generally defined as the following optimisation problem:
![X∈mMa+x(ℝ)Tr(CX ), subject to Tr(AjX ) ≤ bj, for all j ∈ [[M ]], N](https://static.packt-cdn.com/products/9781836209614/graphics/media/file1467.svg)
|
where [[M]] := {1,…,M}, Mn+(ℝ) denotes the set of positive semidefinite matrices of size N ×N. Here, Hermitian matrices (Aj)j=1,…,M and C in MN(ℝ), and (bj)j∈[[M]] ∈ℝM are the inputs...
