Quantum optimization algorithms

Semidefinite Programming

• SDP has wide range applications, problems are scaling so it's important to find more efficient ways to solve them.
• 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 quantum algorithm
  • Requirements
  • Input format
  • Output format

The quantum algorithm reduces the problem to a feasibility problem, performing a binary search on the solution. One algorithm run 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.