Abstract
Following the first paper on quantum algorithms for SDP-solving by Brandao and Svore in 2016, rapid developments have been made on quantum optimization algorithms. Recently Brandao et al. improved the quantum SDP-solver in the so-called quantum state input model, where the input matrices of the SDP are given as purified mixed states. They also gave the first non-trivial application of quantum SDP-solving by obtaining a more efficient algorithm for the problem of shadow tomography (proposed by Aaronson in 2017). In this talk we present a quantum SDP-solver, that combines all benefits of previous approaches. We then apply the results to the problem of shadow tomography to simultaneously improve the best known upper bounds on sample complexity due to Aaronson and gate complexity due Brandao et al., and show some other applications too. Finally, we discuss the limitations of the presented approaches.