Content deleted Content added
No edit summary |
|||
Line 1:
==Semidefinite Programming==
* The SDP problem (definition). Classical state-of-the-art algorithm and complexity. The quantum algorithm provides a quadratic improvement in the general case, and an exponential improvement, when the input matrices are low-rank. ▼
===The SDP problem===
* The quantum algorithm▼
Denote by <math>\mathbb{S}^n</math> the space of all <math>n \times n</math> real symmetric matrices, with the [[Inner product space|inner product]]:
<math>
\langle A,B\rangle_{\mathbb{S}^n} = {\rm tr}(A^T B) = \sum_{i=1,j=1}^n
A_{ij}B_{ij}.
</math>
The SDP problem can be written as:
:<math>
\begin{array}{rl}
{\displaystyle\min_{X \in \mathbb{S}^n}} & \langle C, X \rangle_{\mathbb{S}^n} \\
\text{subject to} & \langle A_k, X \rangle_{\mathbb{S}^n} \leq b_k, \quad k = 1,\ldots,m \\
& X \succeq 0
\end{array}
</math>
The classical state-of-the-art algorithm in terms of worst-case bounds is polynomial-timed.
▲
**Requirements
The algorithm inputs are [[Oracle machine|oracles]] for <math> A_i , C <\math>
The quantum algorithm reduces the problem to a [[Mathematical optimization#Feasibility problem |
The algorithm takes use in a [[Gibbs sampling |Gibbs sampler]], as a probabilistic oracle sampler for estimating the mixed [[quantum state|states]] of the [[density matrix]] through iterations.▼
▲The quantum algorithm reduces the problem to a [[Mathematical optimization#Feasibility problem | Feasibility problem]], performing a binary search on the solution. One algorithm iteration can either output a feasible solution with an objective smaller than some value, or indicate that the optimal objective is larger than an other value, when these values are determined by chosen input parameters. Therefore, it can be run again with different parameters, binary searching the optimal objective value and solution.
▲The algorithm takes use in a [[Gibbs sampling |Gibbs sampler]], as a probabilistic oracle for estimating
| |||