Semidefinite Programming (SDP) is a class of convex optimization programs with vast applications in control theory, quantum information, combinatorial optimization, machine learning and operational research. In this talk, I will discuss how SDP can be used to address two major challenges in quantum computing research: near-term quantum advantage and device certification. Towards the first challenge, I will discuss how to design noisy intermediate-scale quantum (NISQ) algorithms, that bypass the local minima problem, one of the central problems faced by variational quantum algorithms. As an example, I will discuss a NISQ eigensolver that does not suffer from any trainability problem, such as the barren plateau or local minima problem. In the second part of the talk, I will discuss how can one use SDPs to give theoretical guarantees regarding the inner functioning of quantum devices under minimal assumptions. In particular, I will discuss the strategies to prove self-testing statements using tools from semidefinite programming and graph theory.

References:

https://arxiv.org/abs/2106.03891

https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.122.250403

https://journals.aps.org/rmp/abstract/10.1103/RevModPhys.94.015004

(Pizza and refreshments will be served after the talk.)