Theory Seminar

A new result on exponential quantum speed-ups for SDP

Cupjin Huang

University of Michigan
Friday, October 27, 2017
10:30am - 11:30am
EECS 3316

Add to Google Calendar

About the Event

The paper presented gives semidefinite program (SDP) quantum solvers with an exponential speed-up over classical ones. Specifically, it considers SDP instances with m constraint matrices of dimension n, each of rank at most r, and assume that the input matrices of the SDP are given as quantum states (after a suitable normalization). Then it shows there is a quantum algorithm that solves the SDP feasibility problem with accuracy eps by using √ m log m · poly(log n,r, eps^{-1} ) quantum gates. The dependence on n provides an exponential improvement over the work of Brandao and Svore [6] and the work of van Apeldoorn et al. [23], and demonstrates an exponential quantum speed-up when m and r are small. Paper is by Fernando G. S. L. Brandao, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore, and Xiaodi Wu

Additional Information

Sponsor(s): CSE

Open to: Public